Article Free Access Share on The robustness of the p-norm algorithms Authors: Claudio Gentile DSI, Universita' di Milano, Via Comelico 39, 20135 Milano, Italy DSI, Universita' di Milano, Via Comelico 39, 20135 Milano, ItalyView Profile , Nick Littlestone NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile Authors Info & Claims COLT '99: Proceedings of the twelfth annual conference on Computational learning theoryJuly 1999 Pages 1–11https://doi.org/10.1145/307400.307405Published:06 July 1999Publication History 30citation766DownloadsMetricsTotal Citations30Total Downloads766Last 12 Months92Last 6 weeks32 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of learning linear discriminant concepts can be solved by various mistake-driven update procedures, including the Winnow family of algorithms and the well-known Perceptron algorithm.In this paper we define the general class of quasi-additive algorithms, which includes Perceptron and Winnow as special cases.We give a single proof of convergence that covers much of this class, including both Perceptron and Winnow but also many novel algorithms.Our proof introduces a generic measure of progress that seems to capture much of when and how these algorithms converge.Using this measure, we develop a simple general technique for proving mistake bounds, which we apply to the new algorithms as well as existing algorithms.When applied to known algorithms, our technique "automatically" produces close variants of existing proofs (and we generally obtain the known bounds, to within constants)thus showing, in a certain sense, that these seemingly diverse results are fundamentally isomorphic.

We consider a generalization of the mistakebound model (for learning {O, 1}-valued functions) in which the learner must satisfy a general constraint on the number M+ of incorrect 1 predictions and the number JW_ of incorrect O predictions.We describe a generalpurpose optimal algorithm for our formulation of this problem.We describe several applications of our general results, involving situations in which the learner wishes to satisfy linear inequalities in M+ and Tf_. 1.The learner receives z~E X from the environment, 2. The learner outputs a prediction & c {O, 1}, 3. The learner discovers the value ~(zt).Note that the learner only discovers the value of ~(zt ) after making the prediction in trial t.If At # ~(zt ), we say that the learner makes a mistake on trial t,and q This author gratefully acknowledges the support of a Lice Meitner Postdoctoral FeUowship from the Fends zur

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.>

We present an algorithm for the on-line learning of linear functions which is optimal to within a constant factor with respect to bounds on the sum of squared errors for a worst case sequence of trials.The bounds are logarithmic in the number of variables, Furthermore, the algorithm is shown to be optimally robust with respect to noise in the data (again to within a constant factor).We also discuss an application of our methods to the iterative solution of sparse systems of linear equations.

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.>

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.>

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.