Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-97-01 February 1997

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. We call it RFA (Restricted Focus of Attention) learning. 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ⁿ. 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ⁿ 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.

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-97-01, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-171-955 7732. Fax: +44(0)-171-955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html