We study the learnability of concept classes from membership
and equivalence queries. Using the partial order theory we develop
the Monotone theory that gives new techniques for learning concepts
over different domains.
Applying the monotone theory to boolean functions we show that
1) Any boolean function is learnable as decision tree.
2) Any boolean function is either learnable as DNF or as CNF (or both).
The first result solves the open problem of the learnability of
decision trees and the second result gives more evidence that DNFs are
not "very hard" to learn.
The Monotone theory is based on the theory of partially ordered sets.
Given a subclass of all isomorphic partial orders on a set $X$, we
define the DNF, CNF and decision tree representations and specify
conditions for which 1-2 are true. We show that under different choices
of the set $X$, the partial order ($X,<=$), and the set of isomorphisms, we
were able to find various learning algorithms for concepts with
different representation. As an example, using the Hamming partial
order over an abelian group with the set of all linear isomorphisms
we show that decision trees over any alphabet $ SIGMA $ is learnable and
any function $ f : SIGMA sup n -> SIGMA$ is learnable as a decision tree.
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at email@example.com