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
constant dimensional axis parallel concepts
C we show that the following problems have the same time complexity
| 1. |
C is α-properly exactly learnable (with hypotheses of size at most α times the target size) from membership and equivalence
queries.
|
| 2. |
C is α-properly PAC learnable (without membership queries) under any product distribution.
|
| 3. |
There is an α-approximation algorithm for the MinEqui
C problem. (given a g ∈ C find a minimal size f ∈ C that is equivalent to g).
|
In particular, C is α-properly learnable in poly time from membership and equivalence queries if and only if
C is α-properly PAC learnable in poly time under the product distribution if and only if
MinEqui
C has a poly time α-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) ⇒ (3). We use this to
show that (binary) decision trees are not properly learnable in polynomial time (assuming P≠NP) and DNF is not sε-properly learnable (∈ < 1) in polynomial time even with an NP-oracle (assuming Σ
2
p ≠ P
NP
).
This research was supported by the fund for promotion of research at the Technion. Research no. 120-025. Part of this research
was done at the University of Calgary, Calgary, Alberta, Canada and supported by NSERC of Canada.
This research was supported by an NSERC PGS-B Scholarship, an Izaak Walton Killam Memorial Scholarship, and an Alberta Informatics
Circle of Research Excellence (iCORE) Fellowship.