Predicting a binary sequence almost as well as the optimal biased coin

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Predicting a binary sequence almost as well as the optimal biased coin

Full text

Pdf (1.04 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the ninth annual conference on Computational learning theory table of contents

Desenzano del Garda, Italy

Pages: 89 - 98

Year of Publication: 1996

ISBN:0-89791-811-8

Author

Yoav Freund

AT&T Laboratories

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 35, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/238061.238072 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Abramowitz and Stegun. Handbook of Mathematical Functions. National Bureau of Standards, 1970.
	2	J. M. Bernardo. Reference posterior distributions for bayesian inference. J. Roy. Statistzc. Soc. Ser. B., 41:113-147, 1979.
	3	David Blackwell and M.A. Girshick. Theory of Games and Statistical Deczswns. Dover Publications, Inc, New York, 1954.
	4	Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
	5	Bertrand S. Clarke and Andrew R. Barron. Jeffrey's prior is asymptotically least favorable under entropic risk. d. Stat Planning and Inference, 41:37-60, 1994.
	6	T. Cover and E. Ordentlich. Universal portfolios with side information. Unpublished Manuscript, 1995.
	7	Thomas M. Cover. Behavior of sequential predictors of binary sequences.
	8	Thomas M. Cover. Universal portfolios. Mathematical Finance, 1(1):1-29, January 1991.
	9	L. D. Davisson. Universal noiseless coding. {EEE Trans. Inform. Theory, 19:783-795, 1973.
	10	M. Feder, N. Merhav, and M. Gutman. Universal prediction of individual sequences. IEEE Transactzons on Informatwn Theory, 38:1258-1270, 1992.
	11	Thomas S. Ferguson. Mathematgcal Statistics: A Decision Theoretic Approach. Academic Press, 1967.
	12	Dean P. Foster. Prediction in the worst case. The Annals of Statistics, 19(2):1084-1090, 1991.
	13	Yoav Freund. Predicting a binary sequence almost as well the the optimal biased coin. http ://www. research, art. com/orgs/ssr/people/yoav
	14	David Haussler. A general minimax result for relative entropy. Unpublished manuscript.
	15	David Haussler , Jyrki Kivinen , Manfred K. Warmuth, Tight worst-case loss bounds for predicting with expert advice, Proceedings of the Second European Conference on Computational Learning Theory, p.69-83, March 13-15, 1995
	16	Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993
	17	Nick Littlestone. Learning when irrelevant attributes abound. In 28th Annual Symposium on Foundatzons of Computer Science, pages 68-77, October 1987.
	18	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	19	J.D. Murray. Asymptotic Analys2s. Springer Verlag, 1973.
	20	Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
	21	Jorma Rissanen and Glen G. Langdon, Jr. Universal modeling and coding. IEE~ Transactions on Information Theory, IT-27(1):12-23, January 1981.
	22	J. Shtarkov. Coding of descrete sources with unknown statistics. In I. Csiszar and P. Elias, editors, Topics in Information Theory, pages 559-574. North Holland, Amsterdam, 1975.
	23	J. Shtarkov. Universal sequential coding of single measures Problems of Information Transmission, July 1987, 175-185.
	24	V. G. Vovk, A game of prediction with expert advice, Proceedings of the eighth annual conference on Computational learning theory, p.51-60, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225304]
	25	Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
	26	G. N. Watson. Theory of Bessel functions. Cambridge University Press, 1952.
	27	Qun Xie and Andrew Barron. Minimax redundancy for the class of memoryless sources. Unpublished Manuscript, 1995.
	28	Kenji Yamanishi. A decision-theoretic extension of stochastic complexity and its applications to learning. Unpublished Manuscript, 1995.
	29	Zhongxin Zhang , J. A. Hartigan, Discrete noninformative priors, 1994

CITED BY 9

	Katy S. Azoury , M. K. Warmuth, Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions, Machine Learning, v.43 n.3, p.211-246, June 2001
	Nicolò Cesa-Bianchi , Gábor Lugosi, Worst-Case Bounds for the Logarithmic Loss of Predictors, Machine Learning, v.43 n.3, p.247-264, June 2001
	Yoav Freund , Robert E. Schapire, Game theory, on-line prediction and boosting, Proceedings of the ninth annual conference on Computational learning theory, p.325-332, June 28-July 01, 1996, Desenzano del Garda, Italy
	Nicolò Cesa-Bianchi, Analysis of two gradient-based algorithms for on-line regression, Proceedings of the tenth annual conference on Computational learning theory, p.163-170, July 06-09, 1997, Nashville, Tennessee, United States
	Kenji Yamanishi, Minimax relative loss analysis for sequential prediction algorithms using parametric hypotheses, Proceedings of the eleventh annual conference on Computational learning theory, p.32-43, July 24-26, 1998, Madison, Wisconsin, United States
	Yoav Freund, Predicting a binary sequence almost as well as the optimal biased coin, Information and Computation, v.182 n.2, p.73-94, 01 May 2003
	V. Vovk, Derandomizing stochastic prediction strategies, Proceedings of the tenth annual conference on Computational learning theory, p.32-44, July 06-09, 1997, Nashville, Tennessee, United States
	Nicolò Cesa-Bianchi , Gábor Lugosi, Minimax regret under log loss for general classes of experts, Proceedings of the twelfth annual conference on Computational learning theory, p.12-18, July 07-09, 1999, Santa Cruz, California, United States
	V. Vovk, Derandomizing Stochastic Prediction Strategies, Machine Learning, v.35 n.3, p.247-282, June 1999