Predicting a binary sequence almost as well as the optimal biased coin
Published 1 January 1996Open access
Yoav Freund
Citations68
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 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.
Abstract
Article Free Access Share on Predicting a binary sequence almost as well as the optimal biased coin Author: Yoav Freund AT&T Laboratories AT&T LaboratoriesView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 89–98https://doi.org/10.1145/238061.238072Online:01 January 1996Publication History 32citation359DownloadsMetricsTotal Citations32Total Downloads359Last 12 Months20Last 6 weeks2 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
American Journal of PhysicsHandbook of Mathematical Functions
40,436 Citations1966Donald A. McQuarrie
Texts in computer scienceAn Introduction to Kolmogorov Complexity and Its Applications
3,734 Citations2019Ming Li, Paul Vitányi
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
Journal of the Royal Statistical Society Series B (Statistical Methodology)Reference Posterior Distributions for Bayesian Inference
1,103 Citations1979José M. Bernardo
EconometricaA Simple Adaptive Procedure Leading to Correlated Equilibrium
1,077 Citations2000Sergiu Hart, Andreu Mas‐Colell
IEEE Transactions on Information TheoryThe context-tree weighting method: basic properties
934 Citations1995F.M.J. Willems, Yuri M. Shtarkov +1 more
The authors derive a natural upper bound on the cumulative redundancy of the method for individual sequences that shows that the proposed context-tree weighting procedure is optimal in the sense that it achieves the Rissanen (1984) lower bound.
IEEE Transactions on Information TheoryFisher information and stochastic complexity
841 Citations1996J. Rissanen
A sharper code length is obtained as the stochastic complexity and the associated universal process are derived for a class of parametric processes by taking into account the Fisher information and removing an inherent redundancy in earlier two-part codes.
Pacific Journal of MathematicsAn analog of the minimax theorem for vector payoffs
749 Citations1956David Blackwell
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.
ACM SIGACT NewsBook Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))
585 Citations1997William Gasarch
The complexity of a string is defined as the shortest description of x, and a formal definition is given that is equivalent to the one in the book.
IEEE Transactions on Information TheoryUniversal modeling and coding
463 Citations1981J. Rissanen, Glen G. Langdon
A general class of so-called first-in first-out (FIFO) arithmetic codes is described which require no alphabet extension devices and which therefore can be used in conjunction with the best models.
IEEE Transactions on Information TheoryUniversal prediction of individual sequences
377 Citations1992Meir Feder, Neri Merhav +1 more
IEEE Transactions on Information TheoryUniversal noiseless coding
372 Citations1973L. Davisson
This paper considers noiseless coding for sources with unknown parameters, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter.
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.
Journal of Statistical Planning and InferenceJeffreys' prior is asymptotically least favorable under entropy risk
296 Citations1994Bertrand Clarke, Andrew R. Barron
It is shown that, among continuous positive priors, Jeffreys’ prior uniquely achieves the asymptotic maximin value and, in the discrete parameter case, the Bayes risk reduces to the entropy of the prior so that the reference prior is seen to be the maximum entropy prior.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
193 Citations1987Nick Littlestone
IEEE Transactions on Information TheoryAsymptotic minimax regret for data compression, gambling, and prediction
176 Citations2000Qun Xie, Andrew R. Barron
In the discrete memoryless case, the Bayes procedure with the Dirichlet prior is asymptotically maximin and the minimax regret is shown to be k(m-1)/2logn/2/spl pi/k+kC/sub m/+o(1).
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.
IEEE Transactions on Information TheoryMinimax redundancy for the class of memoryless sources
107 Citations1997Qun Xie, Andrew R. Barron
It is shown in this paper that the minimax redundancy minus ((k-1)/2) log(n/(2/spl pi/e)) converges to log/spl int//spl radic/(det I(/spl theta/))d/spl Theta/=log (/spl Gamma/(1/2)/sup k///spl Gamma/2), where I( /spl theTA/) is the Fisher information and the integral is over the whole probability simplex.
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.
A game of prediction with expert advice
87 Citations1995Vladimir Vovk
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.
IEEE Transactions on Information TheoryA general minimax result for relative entropy
79 Citations1997David Haussler
It is shown that the minimax and maximin values of this game are always equal, and there is always a minimax strategy in the closure of the set of all Bayes strategies.
Discrete noninformative priors
9 Citations1994J. A. Hartigan, Zhongxin Zhang