A game of prediction with expert advice

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

A game of prediction with expert advice

Full text

Pdf (952 KB)

Source

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

Santa Cruz, California, United States

Pages: 51 - 60

Year of Publication: 1995

ISBN:0-89791-723-5

Author

V. G. Vovk

Research Council for Cybernetics, 40 ulitsa Vavilova, Moscow 117333 Russia

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 16, Citation Count: 12

Additional Information:

references cited by index terms

Tools and Actions:	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/225298.225304 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	V. M. Alekseev , V. M. Tikhomirov , S. V. Fomin, Optimal control, Plenum Press, New York, NY, 1987
	2	A. A. Borovkov (1986) Teoriya veroyatnostei, 2nd ed. Moscow: Nauka
	3	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]
	4	N. Cesa-Bianchi , Y. Freund , D. P. Helmbold , M. Warmuth, ON-LINE PREDICTION AND CONVERSION STRATEGIES, University of California at Santa Cruz, Santa Cruz, CA, 1994
	5	G. D. Cohen (1983) A nonconstructive upper bound on covering radius. IEEE Trans. Inform. Theory 29, 352-353
	6	A. P. Dawid (1984) Statistical theory. The prequential approach (with discussion). J. R. Statist. Soc. A 147, 278-292
	7	A. DeSantis, G. Markowsky, M. N. Wegman (1988) Learning probabilistic prediction functions. In: 29th FOCS, 110-119
	8	W. Feller (1971) An introduction to probability theory and its applications, vol. 2, 2nd ed. New York: Wiley
	9	D. P. Foster (1991) Prediction in the worst case. Ann. Statist. 19, 1084-1090
	10	Dean P. Foster , Rakesh V. Vohra, A randomization rule for selecting forecasts, Operations Research, v.41 n.4, p.704-709, July–Aug. 1993 [doi>10.1287/opre.41.4.704]
	11	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
	12	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
	13	Jyrki Kivinen , Manfred Warmuth, EXPONENTIATED GRADIENT VERSUS GRADIENT DESCENT FOR LINEAR PREDICTORS, University of California at Santa Cruz, Santa Cruz, CA, 1994
	14	Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993
	15	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	16	Nicholas Littlestone , Philip M. Long, On-line learning with linear loss constraints, Proceedings of the sixth annual conference on Computational learning theory, p.412-421, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168386]
	17	Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, On-line learning of linear functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.465-475, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103467]
	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	D. A. Martin (1990) An extension of Borel determinacy. Ann. Pure Appl. Logic 49, 279-293
	20	Ray J. Solomonoff, The discovery of algorithmic probability: A guide for the programming of true creativity, Proceedings of the Second European Conference on Computational Learning Theory, p.1-22, March 13-15, 1995
	21	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
	22	V. G. Vovk, Universal forecasting algorithms, Information and Computation, v.96 n.2, p.245-277, Feb. 1992 [doi>10.1016/0890-5401(92)90050-P]
	23	V. G. Vovk (1994) An optimality property of the Weighted Majority Algorithm. Manuscript, October 3
	24	D. Williams (1991) Probability with martingales. Cambridge: Cambridge University Press
	25	Kenji Yamanishi, Randomized approximate aggregating strategies and their applications to prediction and discrimination, Proceedings of the eighth annual conference on Computational learning theory, p.83-90, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225308]

CITED BY 12

	Avrim Blum , Adam Kalai, Universal portfolios with and without transaction costs, Proceedings of the tenth annual conference on Computational learning theory, p.309-313, July 06-09, 1997, Nashville, Tennessee, United States
	Kenji Yamanishi, Randomized approximate aggregating strategies and their applications to prediction and discrimination, Proceedings of the eighth annual conference on Computational learning theory, p.83-90, July 05-08, 1995, Santa Cruz, California, United States
	Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States
	Mark Herbster , Manfred K. Warmuth, Tracking the best regressor, Proceedings of the eleventh annual conference on Computational learning theory, p.24-31, July 24-26, 1998, Madison, Wisconsin, United States
	Yoav Freund, Predicting a binary sequence almost as well as the optimal biased coin, Proceedings of the ninth annual conference on Computational learning theory, p.89-98, June 28-July 01, 1996, Desenzano del Garda, Italy
	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
	Eiji Takimoto , Manfred K. Warmuth, Predicting nearly as well as the best pruning of a planar decision graph, Theoretical Computer Science, v.288 n.2, p.217-235, 16 October 2002
	V. Vovk , C. Watkins, Universal portfolio selection, Proceedings of the eleventh annual conference on Computational learning theory, p.12-23, July 24-26, 1998, Madison, Wisconsin, United States
	Avrim Blum , Adam Kalai, Universal Portfolios With and Without Transaction Costs, Machine Learning, v.35 n.3, p.193-205, June 1999
	Mark Herbster , Manfred K. Warmuth, Tracking the best linear predictor, The Journal of Machine Learning Research, 1, p.281-309, 9/1/2001
	Arindam Banerjee, On Bayesian bounds, Proceedings of the 23rd international conference on Machine learning, p.81-88, June 25-29, 2006, Pittsburgh, Pennsylvania
	Jun Zhou , Li Cheng , Walter F. Bischof, Prediction and change detection in sequential data for interactive applications, Proceedings of the 23rd national conference on Artificial intelligence, p.805-810, July 13-17, 2008, Chicago, Illinois

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

Additional Classification:
I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Design, Performance, Theory, Verification

Adobe Acrobat

QuickTime

Windows Media Player

Real Player