Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM9710June 1997 
Andreas Birkendorf, Eli Dichterman, Jeffrey ackson, Norbert Klasner, and Hans Ulrich Simon
Abstract
In the kRestrictedFocusofAttention (kRFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner. While the kRFA model is a natural extension of the PAC model, there are also significant differences. For example, it was previously known that learnability in this model is not characterized by the VCdimension and that many PAC learning algorithms are not applicable in the kRFA setting.
In this paper we further explore the relationship between the PAC and kRFA models, with several interesting results. First, we develop an informationtheoretic characterization of kRFA 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 prove a hardness result for kRFA learnability of kDL, k \leq 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.
If you would like a free copy of this report, please send the number of this report, CDAMLSE9710, 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