Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-059 | 12th November 1996 00:00

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

RSS-Feed




TR96-059
Authors: Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz
Publication: 25th November 1996 15:29
Downloads: 1019
Keywords: 


Abstract:


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.



ISSN 1433-8092 | Imprint