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 >=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 >= 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. |