Nick Littlestone

NeurIPS Conference 1996 Conference Paper

An Apobayesian Relative of Winnow

• Nick Littlestone
• Chris Mesterharm

We study a mistake-driven variant of an on-line Bayesian learn(cid: 173) ing algorithm (similar to one studied by Cesa-Bianchi, Helmbold, and Panizza [CHP96]). This variant only updates its state (learns) on trials in which it makes a mistake. The algorithm makes binary classifications using a linear-threshold classifier and runs in time lin(cid: 173) ear in the number of attributes seen by the learner. We have been able to show, theoretically and in simulations, that this algorithm performs well under assumptions quite different from those embod(cid: 173) ied in the prior of the original Bayesian algorithm. It can handle situations that we do not know how to handle in linear time with Bayesian algorithms. We expect our techniques to be useful in deriving and analyzing other apobayesian algorithms.

ICML Conference 1995 Conference Paper

Comparing Several Linear-threshold Learning Algorithms on Tasks Involving Superfluous Attributes

• Nick Littlestone

FOCS Conference 1992 Conference Paper

Apple Tasting and Nearly One-Sided Learning

• David P. Helmbold
• Nick Littlestone
• Philip M. Long

In the standard on-line model the learning algorithm tries to minimize the total number of mistakes made in a series of trials. On each trial the learner sees an instance, either accepts or rejects that instance, and then is told the appropriate response. The authors define a natural variant of this model ('apple tasting') where the learner gets feedback only when the instance is accepted. They use two transformations to relate the apple tasting model to an enhanced standard model where false acceptances are counted separately from false rejections. They present a strategy for trading between false acceptances and false rejections in the standard model. From one perspective this strategy is exactly optimal, including constants. They apply the results to obtain a good general purpose apple tasting algorithm as well as nearly optimal apple tasting algorithms for a variety of standard classes, such as conjunctions and disjunctions of n boolean variables. They also present and analyze a simpler transformation useful when the instances are drawn at random rather than selected by an adversary. >

I&C Journal 1991 Journal Article

Equivalence of models for polynomial learnability

• David Haussler
• Michael Kearns
• Nick Littlestone
• Manfred K. Warmuth

In this paper we consider several variants of Valiant's learnability model that have appeared in the literature. We give conditions under which these models are equivalent in terms of the polynomially learnable concept classes they define. These equivalences allow comparisons of most of the existing theorems in Valiant-style learnability and show that several simplifying assumptions on polynomial learning algorithms can be made without loss of generality. We also give a useful reduction of learning problems to the problem of finding consistent hypotheses, and give comparisons and equivalences between Valiant's model and the prediction learning models of Haussler, Littlestone, and Warmuth (in “29th Annual IEEE Symposium on Foundations of Computer Science, ” 1988).

STOC Conference 1991 Conference Paper

On-Line Learning of Linear Functions

• Nick Littlestone
• Philip M. Long
• Manfred K. Warmuth

FOCS Conference 1989 Conference Paper

The Weighted Majority Algorithm

• Nick Littlestone
• Manfred K. Warmuth

The construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes is studied. It is assumed that the learner has reason to believe that one of some pool of known algorithms will perform well but does not know which one. A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. It is called the weighted majority algorithm and is shown to be robust with respect to errors in the data. Various versions of the weighted majority algorithm are discussed, and error bounds for them that are closely related to the error bounds of the best algorithms of the pool are proved. >

FOCS Conference 1988 Conference Paper

Predicting {0, 1}-Functions on Randomly Drawn Points (Extended Abstract)

• David Haussler
• Nick Littlestone
• Manfred K. Warmuth

The authors consider the problem of predicting (0, 1)-valued functions on R/sup n/ and smaller domains, based on their values on randomly drawn points. Their model is related to L. G. Valiant's learnability model (1984), but does not require the hypotheses used for prediction to be represented in any specified form. The authors first disregard computational complexity and show how to construct prediction strategies that are optimal to within a constant factor for any reasonable class F of target functions. These prediction strategies use the 1-inclusion graph structure from N. Alon et al. 's work on geometric range queries (1987) to minimize the probability of incorrect prediction. They then turn to computationally efficient algorithms. For indicator functions of axis-parallel rectangles and halfspaces in R/sup n/, they demonstrate how their techniques can be applied to construct computational efficient prediction strategies that are optimal to within a constant factor. They compare the general performance of prediction strategies derived by their method to those derived from existing methods in Valiant's learnability theory. >

FOCS Conference 1987 Conference Paper

Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm (Extended Abstract)

• Nick Littlestone

Valiant and others have studied the problem of learning various classes of Boolean functions from examples. Here we discuss on-line learning of these functions. In on-line learning, the learner responds to each example according to a current hypothesis. Then the learner updates the hypothesis, if necessary, based on the correct classification of the example. One natural measure of the quality of learning in the on-line setting is the number of mistakes the learner makes. For suitable classes of functions, on-line learning algorithms are available that make a bounded number of mistakes, with the bound independent of the number of examples seen by the learner. We present one such algorithm, which learns disjunctive Boolean functions, and variants of the algorithm for learning other classes of Boolean functions. The algorithm can be expressed as a linear-threshold algorithm. A primary advantage of this algorithm is that the number of mistakes that it makes is relatively little affected by the presence of large numbers of irrelevant attributes in the examples; we show that the number of mistakes grows only logarithmically with the number of irrelevant attributes. At the same time, the algorithm is computationaUy time and space efficient.