Abstract

This note studies the learnability of the class k-term DNF with a bounded number of negations per term. We study the case of learning with membership queries alone, and give tight upper and lower bounds on the number of negations that makes the learning task feasible. We also prove a negative result for equivalence queries. Finally, we show that a slight modification in our algorithm proves that the considered class is also learnable in the Simple PAC model, extending Li and Vitányi result for monotone k-term DNF.

Abstract

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 n^O(k) membership queries in O(n^(k^3)) time. We also show n^Omega(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k>1) and general monotone decision lists are not learnable with equivalence queries alone.

Abstract

We study a distribution dependent form of PAC learning that uses probability distributions related to Kolmogorov complexity. We relate the PACS model, defined by Denis, D'Halluin, and Gilleron, with the standard simple-PAC model and give a general technique that subsumes the results of Denis et al and Parekh and Honavar.

Abstract

We introduce a new representation class of Boolean functions---monotone term decision lists---which combines compact representation size with tractability of essential operations. We present many properties of the class which make it an attractive alternative to traditional universal representation classes such as DNF formulas or decision trees.
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 \ge 0$, $k$-term monotone decision lists are exactly and properly learnable with $n^{O(k)}$ membership queries in $n^{O(k^3)}$ time. We also show that $n^{\Omega (k)}$ membership queries are necessary for exact learning. In contrast, both $k$-term  monotone decision lists ($k \ge 2$) and general monotone term decision  lists are not learnable with equivalence queries alone. We also  show that a subclass of monotone term decision lists (disj-MDL) is learnable with equivalence and membership queries, while neither type of query alone suffices.
 

There is an abstract available.

Abstract

We prove the following results. Any Boolean function of O(log n) relevant variables can be exactly learned with a set of non-adaptive membership queries alone and a minimum  sized decision tree representation of the function constructed,  in polynomial time. In contrast, such a function cannot be exactly learned with equivalence queries alone using general decision trees and other representation classes as hypotheses.
Our results imply others which may be of independent interest. We show that truth-table minimization of decision trees can be done in polynomial time, complementing the well-known result of Masek that truth-table minimization of DNF formulas is NP-hard. The proofs  of our negative results show that general decision trees and related representations are not learnable in polynomial time using equivalence queries alone, confirming a folklore theorem.

Abstract

A new research frontier in AI and data mining seeks to develop methods to automatically discover relevant variables among many irrelevant ones. In this paper, we present four algorithms that output such crucial variables in PAC model with membership queries. The first algorithm executes the task under any unknown distribution by measuring the distance between virtual and real targets. The second algorithm exhausts virtual version space under an arbitrary distribution. The third algorithm exhausts universal set under the uniform distribution. The fourth algorithm measures influence of variables under the uniform distribution. Knowing the number $r$ of relevant variables, the first algorithm runs in almost linear time for $r$. The second and the third ones use less membership queries than the first one, but run in time exponential for $r$. The fourth one enumerates highly influential variables in quadratic time for $r$.
 

Abstract
 

We prove a new combinatorial characterization of polynomial learnability from equivalence queries, and state some of its consequences relating the learnability of a class with the learnability via equivalence and membership queries of its subclasses obtained by restricting the instance space. Then we propose and study two models of query learning in which there is a probability distribution on the instance space, both as an application of the tools developed from the combinatorial characterization and as models of independent interest.

Abstract

We introduce an abstract model of exact learning via queries that can be instantiated to all the query learning models currently in use, while being closer to them than previous unificatory attempts. We present a characterization of those Boolean function classes learnable in this abstract model, in terms of a new combinatorial notion that we introduce, the abstract identification dimension. Then we prove that the particularization of our notion to specific known protocols such as equivalence, membership, and membership and equivalence queries results in exactly the same combinatorial notions currently known to characterize learning in these models, such as strong consistency dimension, extended teaching dimension, and certificate size. Our theory thus fully unifies all these characterizations. For models enjoying a specific property that we identify, the notion can be simplified while keeping the same characterizations. From our results we can derive combinatorial characterizations of all those other models for query learning proposed in the literature. We can also obtain the first polynomial-query learning algorithms for specific interesting problems such as learning DNF with proper subset and superset queries.
 

Abstract

We introduce a new combinatorial dimension that gives a good approximation of the number of queries needed to learn in the exact learning model, no matter what set of queries is used. This new dimension generalizes previous dimensions providing upper and lower bounds for all sorts of queries, and not for just example-based queries as in previous works. Our new approach gives also simpler proofs for previous results. We present specific applications of our general dimension for the case of unspecified attribute value queries, and show that unspecified attribute value membership and equivalence queries are not more powerful than standard membership and equivalence queries for the problem of learning DNF formulas.