A game of prediction with expert advice
Published 1 January 1995
Vladimir Vovk
Citations87
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
The following problem is considered: at each point of discrete time the learner must make a prediction; he is given the predictions made by a pool of experts, and each prediction and the outcome, which is disclosed after the learners has made his prediction, determine the incurred loss.
Abstract
Article Free Access Share on A game of prediction with expert advice Author: V. G. Vovk Research Council for Cybernetics, 40 ulitsa Vavilova, Moscow 117333 Russia Research Council for Cybernetics, 40 ulitsa Vavilova, Moscow 117333 RussiaView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 51–60https://doi.org/10.1145/225298.225304Online:05 July 1995Publication History 37citation466DownloadsMetricsTotal Citations37Total Downloads466Last 12 Months9Last 6 weeks0 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 Science
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
Journal of the Franklin InstituteAn introduction to probability theory and its applications
29,966 Citations1958
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
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
The Annals of StatisticsA Universal Prior for Integers and Estimation by Minimum Description Length
1,667 Citations1983J. Rissanen
Estimation based upon the principle of minimizing the total number of binary digits required to rewrite the observed data, when each observation is given with some precision is studied.
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.
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.
Machine LearningLearning quickly when irrelevant attributes abound: A new linear-threshold algorithm
501 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
IEEE Transactions on Information TheoryUniversal portfolios with side information
355 Citations1996Thomas M. Cover, Erik Ordentlich
This is an individual sequence result which shows the difference between the exponential growth wealth of the best state-constant rebalanced portfolio and the universal portfolio with side information is uniformly less than (d/(2n))log (n+1)+(k/n)log 2 for every stock market and side-information sequence and for all time n.
How to use expert advice
132 Citations1993Nicolò 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 known in this context.
Learning probabilistic prediction functions
94 Citations1988Alfredo De Santis, George Markowsky +1 more
The question of how to learn rules, when those rules make probabilistic statements about the future, is considered and two results related to these distinct goals are given.
Lecture notes in computer scienceTight worst-case loss bounds for predicting with expert advice
88 Citations1995David Haussler, Jyrki Kivinen +1 more
This work considers on-line algorithms for predicting binary or continuous-valued outcomes, when the algorithm has available the predictions made by N experts, and shows that for a large class of loss functions, with binary outcomes the total loss of the algorithm proposed by Vovk exceeds the total losses of the best expert at most by the amount c ln N, where c is a constant determined by the loss function.
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.
Predicting a binary sequence almost as well as the optimal biased coin
68 Citations1996Yoav Freund
It is shown that for the case of the logarithmic loss, the derived algorithm is equivalent to the Bayes algorithm with Jeffreys prior, that was studied by Xie and Barron under probabilistic assumptions.
IEEE Transactions on Information TheoryA nonconstructive upper bound on covering radius
61 Citations1983Gérard Cohen
A nonconstructive upper bound is given on t(n,k) , which coincides asymptotically with the known lower bound, namely n-1 t (n,nR) = H-1 (1-R)+O(n^{-l}\log n) , where H^{-1} is the inverse of the binary entropy function.
Operations ResearchA Randomization Rule for Selecting Forecasts
61 Citations1993Dean P. Foster, Rakesh Vohra
A randomized strategy for selecting/combining forecasts that is better than the forecasts used to produce it in a sense made precise is proposed in this paper.
Annals of Pure and Applied LogicAn extension of borel determinacy
54 Citations1990Donald A. Martin
It is proved that all Δ11 games on arbitrary trees that belong both to (ω2+1)–Π11 and to its dual are determinacy-based.
Information and ComputationUniversal forecasting algorithms
47 Citations1992Vladimir Vovk
There is a “universal forecasting algorithm” which for any given bound Γ on time of forecasting computes forecasts within time Γ, and the quality of these forecasts is not much lower than that of any simple forecasting system (the complexity of the “rival” forecasting system may increase as Γ increases).
Journal of the Operational Research SocietyComputational Learning and Probabilistic Reasoning
35 Citations1997Alex Gammerman
This book is devoted to two interrelated techniques in solving some important problems in machine intelligence and pattern recognition, namely probabilistic reasoning and computational learning.
Machine LearningOn-line prediction and conversion strategies
34 Citations1996Nicolò Cesa‐Bianchi, Yoav Freund +2 more
This work presents a deterministic algorithm using binomial weights that has a better worst case mistake bound than the best deterministic algorithm using exponential weights and shows that it is better to use sums of binomials as weights.
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.
Elsevier eBooksTracking the Best Expert**The authors were supported by NSF grant IRI-9123692.
30 Citations1995Mark Herbster, Manfred K. Warmuth
Randomized approximate aggregating strategies and their applications to prediction and discrimination
12 Citations1995Kenji Yamanishi
Methods of efficient approximation of Bayes methods (aggregating strategy) are introduced and their effectiveness in the on-line prediction and discrimination scenarios and the algorithms introduced use randomizing techniques based on the Markov chain Monte Carlo method are demonstrated.
Information and ComputationOn-line learning with linear loss constraints
5 Citations2000David P. Helmbold, N. Littlestone +1 more
On-line learning with linear loss constraints
2 Citations1993N. Littlestone, Philip M. Long
A generalization of the mistake-bound model (for learning {0, 1}-valued functions) in which the learner must satisfy a general constraint on the number of incorrect 1 predictions and the number M"- of incorrect 0 predictions is considered.