|
NeuroCOLT
Technical Report NC-TR-94-018
On the Complexity
of Function Learning
Peter
Auer
Technische Universitaet Graz
Philip
M. Long
Duke University
Wolfgang
Maass
Technische Universitaet Graz
Gerhard
J. Woeginger
Technische Universitaet Graz
Abstract
The majority of results in computational learning theory are concerned
with concept learning, i.e. with the special case of function learning
for classes of functions with range {0,1}. Much less is known about
the theory of learning functions with a larger range such as N or
R. In particular relatively few results exist about the general structure
of common models for function learning, and there are only very few
nontrivial function classes for which positive learning results have
been exhibited in any of these models. We introduce in this
paper the notion of a binary branching adversary tree for function
learning, which allows us to give a somewhat surprising equivalent
characterization of the optimal learning cost for learning a class
of real-valued functions (in terms of a max-min definition which does
not involve any ``learning'' model). Another general structural
result of this paper relates the cost for learning a union of function
classes to the learning costs for the individual function classes.
Furthermore, we exhibit an efficient learning algorithm for learning
convex piecewise linear functions from $R^d$ into $R$. Previously,
the class of linear functions from $R^d$ into $R$ was the only class
of functions with multi-dimensional domain that was known to be learnable
within the rigorous framework of a formal model for on-line learning.
Finally we give a sufficient condition for an arbitrary class $\F$
of functions from $R$ into $R$ that allows us to learn the class of
all functions that can be written as the pointwise maximum of
$k$ functions from $\F$. This allows us to exhibit a number of further
nontrivial classes of functions from $R$ into $R$ for which there
exist efficient learning algorithms.
Download Compressed
Postscript
|