EXACT LEARNING VIA THE MONOTONE THEORY
Date
1993-09-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
Computer Science