This paper deals with the UAV learning model of Goldman, Kwek and Scott [7]. ("UAV" is the acronym for "Unspecified Attribute Values".) As in [7], we consider exact learning within the UAV framework, where the learner has to exactly identify an unknown target concept by means of UAV membership (UAV-MQs) and/or UAV equivalence queries (UAV-EQs or UAV-ARB-EQs, respectively). A smooth transition between exact learning in the UAV setting and standard exact learning is obtained by putting a fixed bound r on the number of unspecified attribute values per instance. For r = 0, we obtain the standard model. For r = n (the total number of attributes), we obtain the (unrestricted) UAV model. Between these extremes, we find the hierarchies (UAV-MQ r ) 0rn , (UAV-EQ r ) 0rn , and (UAV-ARB-EQ r ) 0rn . Our main results are as follows. We present lower bounds on the number of ARB-EQs and UAV-MQs in terms of the Vapnik Chervonenkis dimension of the concept class. We show furthermore that a...

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 a 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 ~n -2.In sharp contrast, an (n -1)-RFA algorithm for learning (n -l)decision-lists 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 lc-RFA learning algorithm for the class of k-decision-lists

A simple method is presented which, loosely speaking, virtually removes noise or misfit from data, and thereby converts a "noise-free" algorithm A, which on-line learns linear functions from data without noise or misfit, into a "noise-tolerant" algorithm A nt which learns linear functions from data containing noise or misfit. Given some technical conditions, this conversion preserves optimality. For instance, the optimal noise-free algorithm B of Bernstein from [3] is converted into an optimal noisetolerant algorithm B nt . The conversion also works properly for all function classes which are closed under addition and contain linear functions as a subclass. In the second part of the paper, we show that Bernstein's on-line learning algorithm B can be converted into a batch learning algorithm B which consumes an (almost) minimal number of random training examples. This is true for a whole class of "pac-style" batch learning models (including learning with an (ffl; fl)- good model...