Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM9801February 1998 
Eli Dichterman
Abstract
This paper surveys recent studies of learning problems in which the learner faces restrictions on the amount of information he can extract from each example he encounters. Our main framework for the analysis of such scenarios is the RFA (Restricted Focus of Attention) model. While being a natural refinement of the PAC learning model, some of the fundamental PAClearning 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. We also present some paradigms and algorithms that may serve as a first step towards answering this need.
Two main types of restrictions can be considered in the general RFA setting: In the more stringent one, called kRFA, only k of the n attributes of each example are revealed to the learner, while in the more permissive one, called kwRFA, 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.
We show an informationtheoretic characterization of RFA learnability upon which we build a general tool for proving hardness results. We then apply this and other new techniques for studying RFA learning to two particularly expressive function classes, kdecisionlists (kDL) and kTOP, the class of thresholds of parity functions in which each parity function takes at most k inputs. Among other results, we show a hardness result for kRFA learnability of kDL, k <= n2. In sharp contrast, an (n1)RFA algorithm for learning (n1)DL is presented. Similarly, we prove that 1DL is learnable if and only if at least half of the inputs are visible in each instance. In addition, we show that there is a uniformdistribution kRFA learning algorithm for the class of kDL. For kTOP we show weak learnability by a kRFA algorithm (with efficient time and sample complexity for constant k) and strong uniformdistribution kRFA learnability of kTOP with efficient sample complexity for constant k. Finally, by combining some of our kDL and kTOP results, we show that, unlike the PAC model, weak learning does not imply strong learning in the kRFA model.
We also show a general technique for composing efficient kRFA algorithms, and apply it to deduce, for instance, the efficient kRFA learnability of kDNF formulas, and the efficient 1RFA learnability of axisaligned rectangles in the Euclidean space R^{n}. We also prove the kRFA learnability of richer classes of Boolean functions (such as kdecision lists) with respect to a given distribution, and the efficient (n1)RFA learnability (for fixed n), under product distributions, of classes of subsets of R^{n} which are defined by mild surfaces.
For the kwRFA restriction, we show that for k = O(log n), efficient kwRFA learning is robust against classification noise. As a straightforward application, we obtain a new simple noisetolerant algorithm for the class of kdecision lists, by constructing an intuitive kwRFA algorithm for this task.
A compressed (gzip) PostScript file (210 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you like a free hard copy of this report, please send the number of this report, LSECDAM9801, 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)171955 7732. Fax: +44(0)171955 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