TR96-059 Authors: Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

Publication: 25th November 1996 15:29

Downloads: 1317

Keywords:

This paper solves the open problem of exact learning

geometric objects bounded by hyperplanes (and more generally by any constant

degree algebraic surfaces) in the constant

dimensional space from equivalence queries only (i.e., in the on-line learning

model).

We present a novel approach that allows, under certain conditions,

the composition of learning algorithms for simple classes into an algorithm for

a more complicated class. Informally speaking,

it shows that if a class of concepts $C$ is learnable

in time $t$ using a small space then $C^\star$,

the class of all functions of the form $f(g_1,\ldots,g_m)$

with $g_1,\ldots,g_m\in C$ and {\it any} $f$, is learnable in

polynomial time in $t$ and $m$. We then show that

the class of halfspaces in a fixed dimension

space is learnable with a small space.