A Second-Order Perceptron Algorithm
Lecture notes in computer sciencePublished 1 January 2002
Nicolò Cesa‐Bianchi, Alex Conconi, Claudio Gentile
Citations21
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We introduce a variant of the Perceptron algorithm called second-order Perceptron algorithm, which is able to exploit certain spectral properties of the data. We analyze the second-order Perceptron algorithm in the mistake bound model of on-line learning and prove bounds in terms of the eigenvalues of the Gram matrix created from the data. The performance of the second-order Perceptron algorithm is affected by the setting of a parameter controlling the sensitivity to the distribution of the eigenvalues of the Gram matrix. Since this information is not preliminarly available to on-line algorithms, we also design a refined version of the second-order Perceptron algorithm which adaptively sets the value of this parameter. For this second algorithm we are able to prove mistake bounds corresponding to a nearly optimal constant setting of the parameter.
Keywords
Computer ScienceEngineering
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Matrix Analysis
22,234 Citations1985Roger A. Horn, Charles R. Johnson
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
Journal of the American Society for Information ScienceIndexing by latent semantic analysis
12,677 Citations1990Scott Deerwester, Susan Dumais +3 more
Psychological ReviewThe perceptron: A probabilistic model for information storage and organization in the brain.
11,746 Citations1958Frank F. Rosenblatt
This article will be concerned primarily with the second and third questions, which are still subject to a vast amount of speculation, and where the few relevant facts currently supplied by neurophysiology have not yet been integrated into an acceptable theory.
Cambridge University Press eBooksMatrix Analysis
10,056 Citations1985Roger A. Horn, Charles R. Johnson
TechnometricsRidge Regression: Biased Estimation for Nonorthogonal Problems
6,562 Citations2000Arthur E. Hoerl, Robert W. Kennard
International Statistical ReviewGeneralized Inverses: Theory and Applications
4,580 Citations1976Vijay K. Rohatgi, Adi Ben-Israel +1 more
ePrints Soton (University of Southampton)An Introduction to Support Vector Machines
4,120 Citations2000Nello Cristianini, John Shawe‐Taylor
WORLD SCIENTIFIC eBooksLeast Squares Support Vector Machines
3,640 Citations2002Johan A. K. Suykens, Tony Van Gestel +3 more
Stochastic modelling and applied probabilityA Probabilistic Theory of Pattern Recognition
3,277 Citations1996Luc Devroye, László Györfi +1 more
The Bayes Error and Vapnik-Chervonenkis theory are applied as guide for empirical classifier selection on the basis of explicit specification and explicit enforcement of the maximum likelihood principle.
Pattern Classification
2,474 Citations2001Duda, Richard O, Hart, Peter E +1 more
Online Computation and Competitive Analysis
2,367 Citations1998Allan Borodin, Ran El‐Yaniv
This book discusses competitive analysis and decision making under uncertainty in the context of the k-server problem, which involves randomized algorithms in order to solve the problem of paging.
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
TechnometricsRidge Regression: Biased Estimation for Nonorthogonal Problems
1,921 Citations1970Arthur E. Hoerl, Robert W. Kennard
Machine LearningQueries and Concept Learning
1,622 Citations1988Dana Angluin
This work considers the problem of using queries to learn an unknown concept, and several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries.
Machine LearningLearning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
1,376 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
ePrints Soton (University of Southampton)Ridge Regression Learning Algorithm in Dual Variables
802 Citations1998Craig Saunders, Alex Gammerman +1 more
A regression estimation algorithm which is a combination of the dual version of Ridge Regression is applied to the ANOVA enhancement of the infinitenode splines and the use of kernel functions, as used in Support Vector methods is introduced.
Journal of the ACMHow to use expert advice
647 Citations1997Nicolò Cesa‐Bianchi, Yoav Freund +4 more
This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts, and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context.
Machine LearningTracking the Best Expert
566 Citations1998Mark Herbster, Manfred K. Warmuth
The generalization allows the sequence to be partitioned into segments, and the goal is to bound the additional loss of the algorithm over the sum of the losses of the best experts for each segment to model situations in which the examples change and different experts are best for certain segments of the sequence of examples.
IEEE Transactions on Information TheoryOn the Generalization Ability of On-Line Learning Algorithms
442 Citations2004Nicolò Cesa‐Bianchi, Alex Conconi +1 more
This paper proves tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M/sub n/ associated with the on-line performance of the ensemble, and obtains risk tail bounds for kernel perceptron algorithms interms of the spectrum of the empirical kernel matrix.
Machine LearningRelative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions
292 Citations2001Katy S. Azoury, Manfred K. Warmuth
This work considers on-line density estimation with a parameterized density from the exponential family and uses a Bregman divergence to derive and analyze each algorithm to design algorithms with the best possible relative loss bounds.
Machine LearningThe Relaxed Online Maximum Margin Algorithm
230 Citations2002Yi Li, Philip M. Long
This work describes a new incremental algorithm for training linear threshold functions: the Relaxed Online Maximum Margin Algorithm, or ROMMA, and proves a mistake bound for ROMMA that is the same as that proved for the perceptron algorithm.
A New Approximate Maximal Margin Classification Algorithm
228 Citations2000Claudio Gentile
International Statistical ReviewCompetitive On‐line Statistics
216 Citations2001Volodya Vovk
This paper reviews some results in competitive on‐line statistics and includes the proofs for the performance of the Aggregating Algorithm in the problem of linear regression with square loss.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
193 Citations1987Nick Littlestone
IrInSubria (University of Insubria)Adaptive and self-confident on-line learning algorithms
186 Citations2002Peter Auer, Nicolò Cesa‐Bianchi +1 more
Machine LearningRelative Loss Bounds for Multidimensional Regression Problems
142 Citations2001Jyrki Kivinen, Manfred K. Warmuth
A unified treatment of on-line generalized linear regression with multidimensional outputs, i.e., neural networks with multiple output nodes but no hidden nodes, is studied, which generalizes earlier results for the gradient descent and exponentiated gradient algorithms to multiddimensional outputs, including multiclass logistic regression.
Machine LearningThe Robustness of the p-Norm Algorithms
142 Citations2003Claudio Gentile
A family of on-line algorithms, called p-norm algorithms, introduced by Grove, Littlestone and Schuurmans in the context of deterministic binary classification are studied, showing how to adapt these algorithms for use in the regression setting, and proving worst-case bounds on the square loss.
Machine LearningGeneral Convergence Results for Linear Discriminant Updates
124 Citations2001Adam J. Grove, Nick Littlestone +1 more
A single proof of convergence is given that covers a broad subset of algorithms in this class of “quasi-additive” algorithms, including both Perceptron and Winnow, but also many new algorithms, and demonstrates that the unifying principles are more broadly applicable.
Linear Hinge Loss and Average Margin
115 Citations1998Claudio Gentile, Manfred K. Warmuth
A unifying method for proving relative loss bounds for online linear threshold classification algorithms, such as the Perceptron and the Winnow algorithms, is described and a notion of "average margin" of a set of examples is introduced.
Artificial IntelligenceThe perceptron algorithm versus winnow: linear versus logarithmic mistake bounds when few input variables are relevant
87 Citations1997Jyrki Kivinen, Manfred K. Warmuth +1 more
It is shown that an adversary can force any additive algorithm to make (N + k −1) 2 mistakes in learning a monotone disjunction of at most k literals and that for k ⪡ N, Winnow clearly outperforms the Perceptron algorithm also on nonadversarial random data.
Machine LearningOn-line Prediction and Conversion Strategies
68 Citations1996Nicolò Cesa‐Bianchi, Yoav Freund +2 more
A deterministic algorithm using binomial weights that has a better worst case mistake bound than the best deterministic algorithm using exponential weights is presented.
The MIT Press eBooksOn the Generalization Ability of On-line Learning Algorithms
53 Citations2002Nicolò Cesa‐Bianchi, Alex Conconi +1 more
Using upper confidence bounds for online learning
50 Citations2002Peter Auer
It is shown how a standard tool from statistics, namely confidence bounds, can be used to elegantly deal with situations which exhibit an exploitation/exploration trade-off and extends the results for the adversarial bandit problem to shifting bandits.
Machine LearningRelative Loss Bounds for Temporal-Difference Learning
6 Citations2003Jürgen Forster, Manfred K. Warmuth