8847864
Bounded degree graph inference from walks
Aslam and Rivest considered the problem of inferring the smallest edge-colored graph of degree bound k consistent with the sequence of colors seen in a walk of the graph. Using Church-Rosser properties of certain sets of rewrite rules, they gave a polynomial time algorithm for the case of k = 2. The straightforward implementation of their ideas results in an O(n^5) algorithm, where n is the length of the walk. In this paper, we develop their ideas further and give an O(n log n) algorithm for the same problem. We also show that if the degree bound k is greater than two, then the decision version of the problem is NP-complete, thus settling a conjecture of Aslam and Rivest.
45877632
On the Limits of Proper Learnability of Subclasses of DNF Formulas
Bshouty, Goldman, Hancock and Matar have shown that up to log n -term DNF formulas can be properly learned in the exact model with equivalence and membership queries. Given standard complexity-theoretical assumptions, we show that this positive result for proper learning cannot be significantly improved in the exact model or the PAC model extended to allow membership queries. Our negative results are derived from two general techniques for proving such results in the exact model and the extended PAC model. As a further application of these techniques, we consider read-thrice DNF formulas. Here we improve on Aizenstein, Hellerstein, and Pitt's negative result for proper learning in the exact model in two ways. First, we show that their assumption of NP ≠ co-NP can be replaced with the weaker assumption of P ≠ NP. Second, we show that read-thrice DNF formulas are not properly learnable in the extended PAC model, assuming RP ≠ NP.
9057261
How many queries are needed to learn?
We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. We give applications of this characterization, including results on learning a natural subclass of DNF formulas, and on learning with membership queries alone. Query complexity has previously been used to prove lower bounds on the time complexity of exact learning. We show a new relationship between query complexity and time complexity in exact learning: If any “honest” class is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then P = NP. In particular, we show that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for Γp4.
13141933
Read-Twice DNF Formulas are Properly Learnable
We show that read-twice DNF formulas-Boolean formulas in disjunctive normal form in which each variable appears at most twice-are exactly and properly learnable in polynomial time. Our algorithm uses membership queries and proper equivalence queries and is based on a simple, new characterization of minimal read-twice DNF formulas. The algorithm improves on earlier results of Hancock and Aizenstein and Pitt which showed that read-twice DNF formulas are learnable using more powerful equivalence queries, i.e., where the hypotheses could be arbitrary DNF formulas. We also improve on the time-complexity of these earlier algorithms. Other results which may be of independent interest outside of learning follow directly from this paper. Specifically, we show that read-twice DNF formulas can be tested for equivalence in polynomial time and that the smallest read-twice formula equivalent to a given one can be found in polynomial time.
1363140
Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be done more efficiently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding deciding if an order has width k can be done in O(kn2) time and whether a graph has Dilworth number k can be done in O(k2n2) time.For very small k we have even better results. We show that orders of width at most 3 can be recognized in O(n) time and of width at most 4 in O(nlog n).
5530551
Learning switch configurations
2452986
The Item-Set Tree: A Data Structure for Data Mining
Enhancements in data capturing technology have lead to exponential growth in amounts of data being stored in information systems. This growth in turn has motivated researchers to seek new techniques for extraction of knowledge implicit or hidden in the data. In this paper, we motivate the need for an incremental data mining approach based on data structure called the item-set tree. The motivated approach is shown to be effective for solving problems related to efficiency of handling data updates, accuracy of data mining results, processing input transactions, and answering user queries. We present efficient algorithms to insert transactions into the item-set tree and to count frequencies of itemsets for queries about strength of association among items. We prove that the expected complexity of inserting a transaction is ≅ O(1), and that of frequency counting is O(n), where n is the cardinality of the domain of items.
353294
Dynamic Data Mining
Business information received from advanced data analysis and data mining is a critical success factor for companies wishing to maximize competitive advantage. The use of traditional tools and techniques to discover knowledge is ruthless and does not give the right information at the right time. Data mining should provide tactical insights to support the strategic directions. In this paper, we introduce a dynamic approach that uses knowledge discovered in previous episodes. The proposed approach is shown to be effective for solving problems related to the efficiency of handling database updates, accuracy of data mining results, gaining more knowledge and interpretation of the results, and performance. Our results do not depend on the approach used to generate itemsets. In our analysis, we have used an Apriori-like approach as a local procedure to generate large itemsets. We prove that the Dynamic Data Mining algorithm is correct and complete.
34098191
Concept Based Retrieval Using Generalized Retrieval Functions
One of the essential goals in information retrieval is to bridge the gap between the way users would prefer to specify their information needs and the way queries are required to be expressed. Rule Based Information Retrieval by Computer (RUBRIC) is one of the approaches proposed to achieve this goal. This approach involves the use of production rules to capture user-query concepts (or topics). In RUBRIC, a set of related production rules is represented as an AND/OR tree, or alternatively by a disjunction of Minimal Term Sets (MTSs). The retrieval output is determined by the evaluation of the weighted Boolean expressions of the AND/OR tree, and processing efficiency can be enhanced by employing MTSs. However, since the weighted Boolean expression ignores the term-term association unless it is explicitly represented in the tree, the terminological gap between users' queries and their information needs may still remain. To solve this problem, we adopt the generalized vector space model (GVSM) and the p-norm based extended Boolean model. Experiments are performed for two variations of the RUBRIC model, extended with GVSM, as well as for the integrated use of RUBRIC with the p-norm based extended Boolean model. The results are compared to the original RUBRIC model based on recall-precision.
62608981
On the delusiveness of adopting a common space for modeling IR objects: are queries documents?
Many authors, who adopt the vector space model, take the view that documents, terms, queries, etc., are all elements within the same (conceptual) space. This view seems to be a natural one, given that documents and queries have the same vector notation. We show, however, that the structure of the query space can be very different from that of the document space. To this end, concepts like preference, similarity, term independence, and linearity, both in the document space and in the query space, are discussed. Our conclusion is that a more realistic and complete view of IR is obtained if we do not consider documents and queries to be elements of the same space. This conclusion implies that certain restrictions usually applied in the design of an IR system are obviated. For example, the retrieval function need not be restricted to the ones that have the possibility to be interpreted as a similarity measure. © 1993 John Wiley & Sons, Inc.
7141965
Visualizing association mining results through hierarchical clusters
We propose a new methodology for visualizing association mining results. Inter-item distances are computed from combinations of itemset supports. The new distances retain a simple pairwise structure, and are consistent with important frequently occurring itemsets. Thus standard tools of visualization, e.g. hierarchical clustering dendrograms can still be applied, while the distance information upon which they are based is richer. Our approach is applicable to general association mining applications, as well as applications involving information spaces modeled by directed graphs, e.g. the Web. In the context of collections of hypertext documents, the inter-document distances capture the information inherent in a collection's link structure, a form of link mining. We demonstrate our methodology with document sets extracted from the Science Citation Index, applying a metric that measures consistency between clusters and frequent itemsets.