14710291
Learning Monotone Term Decision Lists
We study the learnability of monotone term decision lists in the exact model of equivalence and membership queries. We show that, for any constant k≥0, k-term monotone decision lists are exactly and properly learnable with nO(k) membership queries in O(nk3) time. We also show nΩ(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k≥2) and general monotone decision lists are not learnable with equivalence queries alone.
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).
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.
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.
5530551
Learning switch configurations
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.
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.
2292157
Information Retrieval on the World Wide Web
Effective search and retrieval are enabling technologies for realizing the full potential of the Web. The authors examine relevant issues, including methods for representing document content. They also compare available search tools and suggest methods for improving retrieval effectiveness.
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.
17056398
A Theoretical Framework for Association Mining Based on the Boolean Retrieval Model
Data mining has been defined as the non-trivial extraction of implicit, previously unknown and potentially useful information from data. Association mining is one of the important sub-fields in data mining, where rules that imply certain association relationships among a set of items in a transaction database are discovered. 
 
The efforts of most researchers focus on discovering rules in the form of implications between itemsets, which are subsets of items that have adequate supports. Having itemsets as both antecedent and precedent parts was motivated by the original application pertaining to market baskets and they represent only the simplest form of predicates. This simplicity is also due in part to the lack of a theoretical framework that includes more expressive predicates. 
 
The framework we develop derives from the observation that information retrieval and association mining are two complementary processes on the same data records or transactions. In information retrieval, given a query, we need to find the subset of records that matches the query. In contrast, in data mining, we need to find the queries (rules) having adequate number of records that support them. 
 
In this paper we introduce the theory of association mining that is based on a model of retrieval known as the Boolean Retrieval Model. The potential implications of the proposed theory are presented.