JMLR: On the Proper Learning of Axis-Parallel Concepts
Redistributed
~From: "David 'Pablo' Cohn" <David...@acm.org>
~Date: 16 Jun 2003 10:56:28 -0700
~Subject: jmlr-announce: On the Proper Learning of Axis-Parallel Concepts
The Journal of Machine Learning Research (www.jmlr.org) is pleased to
announce publication of the eighth paper in Volume 4:
--------------------------
On the Proper Learning of Axis-Parallel Concepts
Nader H. Bshouty and Lynn Burroughs
JMLR 4(Jun):157-176, 2003
Abstract
We study the proper learnability of axis-parallel concept classes in the
PAC-learning and exact-learning models. These classes include union of
boxes, DNF, decision trees and multivariate polynomials.
For constant-dimensional axis-parallel concepts C we show that the
following problems have time complexities that are within a polynomial
factor of each other.
1. C is alpha-properly exactly learnable (with hypotheses of size at
most alpha times the target size) from membership and equivalence
queries.
2. C is alpha-properly PAC learnable (without membership queries)
under any product distribution.
3. There is an alpha-approximation algorithm for the MINEQUIC problem
(given a g in C find a minimal size f in C that is logically equivalent
to g).
In particular, if one has polynomial time complexity, they all do. Using
this we give the first proper-learning algorithm of constant-dimensional
decision trees and the first negative results in proper learning from
membership and equivalence queries for many classes.
For axis-parallel concepts over a nonconstant dimension 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^epsilon-properly learnable (epsilon < 1)
in polynomial time even with an NP-oracle (assuming Sigma_2^P <> P^NP).
----------------------------------------------------------------------------
This paper is available electronically at http://www.jmlr.org in
PostScript and PDF formats. The papers of Volumes 1, 2 and 3 are also
available electronically from the JMLR website, and in hardcopy from the
MIT Press; please see http://mitpress.mit.edu/JMLR for details.
-David Cohn, <david...@acm.org>
[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <com...@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]