Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-059 | 12th November 1996 00:00

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


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


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

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