Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-019 | 20th March 2002 00:00

On the proper learning of axis parallel concepts


Authors: Nader Bshouty, Lynn Burroughs
Publication: 22nd March 2002 15:40
Downloads: 1305


We study the proper learnability of axis parallel concept classes
in the PAC learning model and in the exact learning model with
membership and equivalence queries. These classes include union of boxes,
DNF, decision trees and multivariate polynomials.

For the {\it constant} dimensional axis parallel concepts $C$
we show that the following problems have the same time complexity
$C$ is ${\alpha}$-properly exactly learnable
(with hypotheses of size
at most ${\alpha}$ times the target size)
from membership and equivalence queries.
$C$ is ${\alpha}$-properly PAC learnable (without membership queries)
under any product distribution.
There is an ${\alpha}$-approximation algorithm
for the $\MinEqui C$ problem. (given a $g\in C$
find a minimal size $f\in C$ that is equivalent to
In particular, $C$ is ${\alpha}$-properly
learnable in polynomial time from membership and equivalence
queries {\bf if and only if} $C$ is ${\alpha}$-properly PAC
learnable in polynomial time under the product distribution
{\bf if and only if} $\MinEqui C$ has a polynomial
time ${\alpha}$-approximation algorithm.
Using this result we give the first proper learning algorithm
of decision trees over the constant dimensional domain and
the first negative results in proper learning from membership
and equivalence queries for many classes.

For the non-constant dimensional axis parallel concepts
we show that with the equivalence oracle
$(1)\Rightarrow (3)$. We use this to show that
(binary) decision trees are not properly learnable in polynomial time
(assuming P$\not=$NP) and DNF is not $s^\epsilon$-properly learnable
($\epsilon < 1$) in polynomial time even with an NP-oracle
(assuming $\Sigma_2^p\not=$ $P^{NP}$).

ISSN 1433-8092 | Imprint