Search

We formalize the associative bandit problem framework introduced by Kaelbling as a learning-theory problem. The learning environment is modeled as a k-armed bandit where arm payoffs are conditioned on an observable input selected on each trial. We show that, if the payoff functions are constrained to a known hypothesis class, learning can be performed efficiently with respect to the VC dimension of this class. We formally reduce the problem of PAC classification to the associative bandit problem, producing an efficient algorithm for any hypothesis class for which efficient classification algorithms are known. We demonstrate the approach empirically on a scalable concept class.

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ d for fixed d . More specifically, let 𝒯 be any set of s halfspaces. Let x =(x 1 , …, x d ) be an arbitrary point in ℛ d . With each t ∈ 𝒯 we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, 𝒞 d s , that we study consists of all concepts formed by any Boolean function over I t1 , …, I ts for t i ∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ d given that the VC-dimension of 𝒞 has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.

Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration of k points in the real line. Each instance is a configuration of n points on the real line, where it is labeled according to whether or not it visually resembles the target pattern.We relate the concept class of geometric patterns to the landmark recognition problem and then present a polynomial-time algorithm that PAC-learns the class of one-dimensional geometric patterns when the negative examples are corrupted by a large amount of random misclassification noise.

I show that the linear threshold functions are polynomially learnable in the presence of classification noise, i.e., polynomial in n, 1/e, 1/δ, and 1/s, where n is the number of Boolean attributes, e and δ are the usual accuracy and confidence parameters, and s indicates the minimum distance of any example from the target hyperplane, which is assumed to be lower than the average distance of the examples from any hyperplane. This result is achieved by modifying the Perceptron algorithm—for each update, a weighted average of a sample of misclassified examples and a correction vector is added to the current weight vector. Similar modifications are shown for the Weighted Majority algorithm. The correction vector is simply the mean of the normalized examples. In the special case of Boolean threshold functions, the modified Perceptron algorithm performs O (n2e−2 ) iterations over O(n4e −2ln(n/(δe))) examples. This improves on the previous classification-noise result of Angluin and Laird to a much larger concept class with a similar number of examples, but with multiple iterations over the examples.

The Vapnik-Chervonenkis (V-C) dimension is an important combinatorial tool in the analysis of learning problems in the PAC framework. For polynomial learnability, we seek upper bounds on the V-C dimension that are polynomial in the syntactic complexity of concepts. Such upper bounds are automatic for discrete concept classes, but hitherto little has been known about what general conditions guarantee polynomial bounds on V-C dimension for classes in which concepts and examples are represented by tuples of real numbers. In this paper, we show that for two general kinds of concept class the V-C dimension is polynomially bounded in the number of real numbers used to define a problem instance. One is classes where the criterion for membership of an instance in a concept can be expressed as a formula (in the first-order theory of the reals) with fixed quantification depth and exponentially-bounded length, whose atomic predicates are polynomial inequalities of exponentially-bounded degree, The other is classes where containment of an instance in a concept is testable in polynomial time, assuming we may compute standard arithmetic operations on reals exactly in constant time. Our results show that in the continuous case, as in the discrete, the real barrier to efficient learning in the Occam sense is complexity-theoretic and not information-theoretic. We present examples to show how these results apply to concept classes defined by geometrical figures and neural nets, and derive polynomial bounds on the V-C dimension for these classes.

This paper deals with the learnability of Boolean functions. An intuitively appealing notion of dimensionality is developed and used to identify the most general class of Boolean function families that are learnable from polynomially many positive examples with one-sided error. It is then argued that although bounded DNF expressions lie outside this class, they must have efficient learning algorithms as they are well suited for expressing many human concepts. A framework that permits efficient learning of bounded DNF functions is identified.

Quantitative descriptions of data populations have played an important role in the data base design process, particularly where simulation has been employed. The new levels of fidelity and representation-independence made possible by recent advances in data description languages warrant a renewed interest in this technique. This paper presents a new approach to describing the quantitative characteristics of a data base at the representation-independent level. The terminology is based on the Entity Set level of the Data Independent Accessing Model (DIAM I), but the concept is applicable to the Relational Model or the Concept Class Model of DIAM II. The first section discusses the concepts of the approach. Beginning with the simple case of a steady-state system with independent probabilities, the discussion proceeds to introduce constant-change and variable-change dynamics and several orders of conditional biases. Section two presents a highly simplified but illustrative example to show the technique's ease of application and give some insight to its potential in a problem solving environment. Finally, an appendix is provided which reduces the technique to practicality through a comprehensive set of data collection forms that could be used as the basis for a powerful data dictionary facility.

Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. We find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. The methodology and results suggest concrete principles for designing realistic learning systems.

We extend the notion of class so that any Boolean combinations of classes is also a class. Boolean classes allow greater precision and conciseness in naming the class of objects governed a particular method. A class can be viewed as a predicate which is either true or false of any given object. Unlike predicates however classes have an inheritance hierarchy which is known at compile time. Boolean classes extend the notion of class, making classes more like predicates, while preserving the compile time computable inheritance hierarchy.

IN THE PAST SEVERAL YEARS, several papers1,2 have been written that have developed a description language that can be used to describe classes of objects. A class is a grouping of a number of objects such as all integral numbers, all five card poker hands, or all sentences generated by the rules of a given context free grammar. This description language is useful because all objects in a given class can be described using only one class description; also, many different classes can be described using this one description language. We shall use the word concept to mean the class description. Note that a concept describes a class of objects.This paper takes the description language and presents a computer program for reading in an object and a number of concepts; the program then finds whether or not this object belongs to one of the given classes described by a concept. The program was implemented by breaking the language into a series of rules (1), and then writing procedures (i.e. - individual computer sub-programs that are called from the main program) that break down a given string of symbols (the object and the concepts) according to these rules. The answers are of the following form: “yes, object included in (insert class name) class”; “no, object not included in given classes.”The objective of this paper is to: (1) - give a review of the Banerji formalism; (2) - formalize an example that will show how the language is used; and (3) - describe the computer program.