|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-97-012
Learning
with Restricted Focus of Attention
Shai
Ben-David
Technion, Israel
Eli
Dichterman
LSE and RHUL, University of London, UK
Abstract
We consider learning tasks in which the learner faces restrictions
on the amount of information he can extract from each example he encounters.
We introduce a formal framework for the analysis of such scenarios.
While being a natural refinement of the PAC learning model, some of
the fundamental PAC-learning results and techniques fail in the RFA
paradigm; learnability in the RFA model is no longer characterized
by the VC dimension, and many PAC learning algorithms are not applicable
in the RFA setting. Hence, the RFA formulation reflects the need for
new techniques and tools to cope with some fundamental constraints
of realistic learning problems. In this work we also present some
paradigms and algorithms that may serve as a first step towards answering
this need. Two main types of restrictions are considered here: In
the stronger one, called $k$-RFA, only $k$ of the $n$ attributes of
each example are revealed to the learner, while in the weakest one,
called $k$-wRFA, the restriction is made on the size of each observation
($k$ bits), and no restriction is made on how the observations are
extracted from the examples.
For the stronger $k$-RFA restriction we develop a general technique
for composing efficient $k$-RFA algorithms, and apply it to deduce,
for instance, the efficient $k$-RFA learnability of $k$-DNF formulas,
and the efficient $1$-RFA learnability of axis-aligned rectangles
in the Euclidean space $\R^n$. We also prove the $k$-RFA learnability
of richer classes of Boolean functions (such as $k$-decision lists)
with respect to a given distribution, and the efficient $(n-1)$-RFA
learnability (for fixed $n$), under product distributions, of classes
of subsets of $\R^n$ which are defined by mild surfaces.
For the weaker $k$-wRFA restriction, we show that for $k=O(\log
n)$, efficient $k$-wRFA learning is robust against classification
noise. As a straightforward application, we construct a new simple
noise-tolerant algorithm for the class of $k$-decision lists by constructing
an intuitive $k$-wRFA algorithm for this task.
Download Compressed Postscript
|