P. M. Long.
On agnostic learning with
{0,*,1}-valued and real-valued hypotheses.
Proceedings of the 2001
Conference on Computational Learning Theory.
Abstract
We consider the problem of classification using a variant of
the agnostic learning model in which the algorithm's hypothesis is evaluated
by comparison with hypotheses that do not classify all possible
instances. Such hypotheses are formalized as functions from the instance
space X to {0,*,1}, where * is interpreted as "don't know". We provide
a characterization of the sets of {0,*,1}-valued functions that are learnable
in this setting. Using a similar analysis, we improve on sufficient
conditions for a class of real-valued functions to be agnostically learnable
with a particular relative accuracy; in particular, we improve by a
factor of two the scale at which scale-sensitive dimensions must be finite
in order to imply learnability.