ECCC-Report TR96-059https://eccc.weizmann.ac.il/report/1996/059Comments and Revisions published for TR96-059en-usMon, 25 Nov 1996 15:29:18 +0200
Paper TR96-059
| A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes |
Shai Ben-David,
Nader Bshouty,
Eyal Kushilevitz
https://eccc.weizmann.ac.il/report/1996/059
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.
Mon, 25 Nov 1996 15:29:18 +0200https://eccc.weizmann.ac.il/report/1996/059