Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-97-10 June 1997

Abstract

In the k-Restricted-Focus-of-Attention (k-RFA) 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 k-RFA 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 VC-dimension and that many PAC learning algorithms are not applicable in the k-RFA setting.

In this paper we further explore the relationship between the PAC and k-RFA models, with several interesting results. First, we develop an information-theoretic characterization of k-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, k-decision-lists (k-DL) and k-TOP, 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 k-RFA learnability of k-DL, k \leq n-2. In sharp contrast, an (n-1)-RFA algorithm for learning (n-1)-DL is presented. Similarly, we prove that 1-DL 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 uniform-distribution k-RFA learning algorithm for the class of k-DL. For k-TOP we show weak learnability by a k-RFA algorithm (with efficient time and sample complexity for constant k) and strong uniform-distribution k-RFA learnability of k-TOP with efficient sample complexity for constant k. Finally, by combining some of our k-DL and k-TOP results, we show that, unlike the PAC model, weak learning does not imply strong learning in the k-RFA model.

If you would like a free copy of this report, please send the number of this report, CDAM-LSE-97-10, 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