Boosting as entropy projection
Published 6 July 1999
Jyrki Kivinen, Manfred K. Warmuth
Citations117
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.
TL;DR
It is shown how AdaBoost’s choice of the new distribution can be seen as an approximate solution to the following problem: Find a new distribution that is closest to the old distribution subject to the constraint that thenew distribution is orthogonal to the vector of mistakes of the current weak hypothesis.
Abstract
Article Free Access Share on Boosting as entropy projection Authors: Jyrki Kivinen Department of Computer Science, P.O. Box 26 (Teollisuuskatu 23), FIN-00014 University of Helsinki, Finland Department of Computer Science, P.O. Box 26 (Teollisuuskatu 23), FIN-00014 University of Helsinki, FinlandView Profile , Manfred K. Warmuth Computer Science Department, University of California, Santa Cruz, Santa Cruz, CA Computer Science Department, University of California, Santa Cruz, Santa Cruz, CAView Profile Authors Info & Claims COLT '99: Proceedings of the twelfth annual conference on Computational learning theoryJuly 1999 Pages 134–144https://doi.org/10.1145/307400.307424Online:06 July 1999Publication History 56citation740DownloadsMetricsTotal Citations56Total Downloads740Last 12 Months19Last 6 weeks5 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
Keywords
Computer ScienceDecision Sciences
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
The Annals of StatisticsAdditive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors)
6,842 Citations2000Jerome H. Friedman, Trevor Hastie +1 more
This work shows that this seemingly mysterious phenomenon of boosting can be understood in terms of well-known statistical principles, namely additive modeling and maximum likelihood, and develops more direct approximations and shows that they exhibit nearly identical results to boosting.
Computers & Operations ResearchNonlinear programming: theory and algorithms
5,829 Citations1993
The book is a solid reference for professionals as well as a useful text for students in the fields of operations research, management science, industrial engineering, applied mathematics, and also in engineering disciplines that deal with analytical optimization techniques.
Mathematics and Computers in SimulationLinear and nonlinear programming.
4,850 Citations1986
The linear and nonlinear programming is universally compatible with any devices to read and is available in the book collection an online access to it is set as public so you can download it instantly.
Machine LearningThe Strength of Weak Learnability
3,293 Citations1990Robert E. Schapire
In this paper, a method is described for converting a weak learning algorithm into one that achieves arbitrarily high accuracy, and it is shown that these two notions of learnability are equivalent.
USSR Computational Mathematics and Mathematical PhysicsThe relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming
2,659 Citations1967L.M. Bregman
This method can be regarded as a generalization of the methods discussed in [1–4] and applied to the approximate solution of problems in linear and convex programming.
Improved boosting algorithms using confidence-rated predictions
2,568 Citations1998Robert E. Schapire, Yoram Singer
Convex analysis and minimization algorithms
2,435 Citations1993Jean‐Baptiste Hiriart‐Urruty, Claude Lemaréchal
Information and ComputationBoosting a Weak Learning Algorithm by Majority
1,686 Citations1995Yoav Freund
An algorithm for improving the accuracy of algorithms for learning binary concepts by combining a large number of hypotheses, each of which is generated by training the given learning algorithm on a different set of examples, is presented.
Lecture notes in statisticsDifferential-Geometrical Methods in Statistics
1,647 Citations1985Шун-ичи Амари
IEEE Transactions on Pattern Analysis and Machine IntelligenceInducing features of random fields
1,044 Citations1997S. Della Pietra, V. Della Pietra +1 more
The random field models and techniques introduced in this paper differ from those common to much of the computer vision literature in that the underlying random fields are non-Markovian and have a large number of parameters that must be estimated.
Information and ComputationExponentiated Gradient versus Gradient Descent for Linear Predictors
880 Citations1997Jyrki Kivinen, Manfred K. Warmuth
The bounds suggest that the losses of the algorithms are in general incomparable, but EG(+/-) has a much smaller loss if only a few components of the input are relevant for the predictions, which is quite tight already on simple artificial data.
Medical Entomology and ZoologyEntropy optimization principles with applications
849 Citations1992J. N. Kapur, H. K. Kesavan
Applications of Jaynes' maximum entropy principle and Kullback's minimum cross-entropy principle are applied to develop new entropy optimization principles generalized principles of maximum entropy the four inverse maximum entropy principles.
The Annals of StatisticsWhy Least Squares and Maximum Entropy? An Axiomatic Approach to Inference for Linear Inverse Problems
804 Citations1991Imre Csiszár
Games and Economic BehaviorAdaptive Game Playing Using Multiplicative Weights
538 Citations1999Yoav Freund, Robert E. Schapire
A variant of the game-playing algorithm is proved to be optimal in a very strong sense and a new, simple proof of the min–max theorem, as well as a provable method of approximately solving a game.
Journal of Optimization Theory and ApplicationsAn iterative row-action method for interval convex programming
502 Citations1981Yair Censor, Arnold Lent
The iterative primal-dual method of Bregman for solving linearly constrained convex programming problems, which utilizes nonorthogonal projections onto hyperplanes, is represented in a compact form, and a complete proof of convergence is given for an almost cyclic control of the method.
Water science and technology libraryEntropy Optimization Principles and Their Applications
501 Citations1992J. N. Kapur, H. K. Kesavan
A state-of-the-art description of the theory and applications of the various entropy optimization principles is given and the relation between information-theoretic entropy and thermodynamic entropy is specially recalled in the context of the more general relationship that exist between what are designated as primary and secondary entropies.
Grundlehren der mathematischen WissenschaftenConvex Analysis and Minimization Algorithms II
422 Citations1993Jean‐Baptiste Hiriart‐Urruty, Claude Lemaréchal
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.
Using and combining predictors that specialize
239 Citations1997Yoav Freund, Robert E. Schapire +2 more
It is shown how to transform algorithms that assume that all experts are always awake to algorithms that do not require this assumption, and how to derive corresponding loss bounds.
Additive versus exponentiated gradient updates for linear prediction
226 Citations1995Jyrki Kivinen, Manfred K. Warmuth
The main methodological idea is using a distance function between weight vectors both in motivating the algorithms and as a potential function in an amortized analysis that leads to worst-case loss bounds.
Lecture notes in computer scienceAveraging Expert Predictions
131 Citations1999Jyrki Kivinen, Manfred K. Warmuth
A simplified algorithm in which the weights are as in the original Aggregating Algorithm, but the prediction is simply the weighted average of the experts' predictions, showing that for a large class of loss functions, even with the simplified prediction rule the additional loss of the algorithm over the loss ofThe best expert is at most c ln n.
IEEE Transactions on Information TheoryGeneral entropy criteria for inverse problems, with applications to data compression, pattern classification, and cluster analysis
99 Citations1990Lee K. Jones, C.L. Byrne
An optimal class of distances satisfying an orthogonality condition analogous to that enjoyed by linear projections in Hilbert space is derived and possess the geometric properties of cross entropy useful in speech and image compression, pattern classification, and cluster analysis.
Relative Information: Theories and Applications
93 Citations2011Guy Jumarie
This book presents a quantitative model of subjective information, a unified approach to discrete and continuous entropy, a theory of information for stochastic functions, and a model of Shannon entropy of deterministic maps which is quite different from Kolmogorov entropy.
Additive models, boosting, and inference for generalized divergences
82 Citations1999John Lafferty
A framework for designing incremental learning algorithms derived from generalized entropy functionals based on the use of Bregman divergences together with the associated class of additive models constructed using the Legendre transform is presented.
Tracking the best regressor
33 Citations1998Mark Herbster, Manfred K. Warmuth
This paper develops the methodology for lifting known static bounds to the shifting case and obtains bounds when the comparison class consists of linear neurons (linear combinations of experts).
Computational ComplexityOn-line learning of linear functions
31 Citations1995N. Littlestone, Manfred K. Warmuth +1 more
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 is presented.
arXiv (Cornell University)Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions
29 Citations2013Katy S. Azoury, Manfred K. Warmuth
Lecture notes in computer scienceA Geometric Approach to Leveraging Weak Learners
23 Citations1999Nigel Duffy, David P. Helmbold
The binary exponentiated gradient algorithm for learning linear functions
16 Citations1997Tom Bylander
A new online algorithm for learning linear functions, called the Binary Exponentiated Gradient algorithm, developed from a binary entropy distance function and the square loss function, and worst-case upper bounds on thesquare loss are demonstrated for BEG on arbitrary sequences of trials.
IEEE Transactions on Information TheoryBounds on approximate steepest descent for likelihood maximization in exponential families
10 Citations1994Nicolò Cesa‐Bianchi, Anders Krogh +1 more
An approximate steepest descent strategy is described, converging in families of regular exponential densities to maximum likelihood estimates of density functions, obtained by an application of the principle of minimum relative entropy subject to empirical constraints.