Game theory, on-line prediction and boosting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Game theory, on-line prediction and boosting

Full text

Pdf (805 KB)

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: 325 - 332

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Yoav Freund	AT&T Laboratories, 600 Mountain Avenue, Murray Hill, NJ
Robert E. Schapire	AT&T Laboratories, 600 Mountain Avenue, Murray Hill, NJ

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): 29, Downloads (12 Months): 111, Citation Count: 29

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.238163 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	David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1): 1-8, Spring 1956.
	2	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]
	3	Thomas S. Ferguson. Mathematical Statistics: A Decision Theoretic Approach. Academic Press, 1967.
	4	Dean Foster and Rakesh Vohra. Regret in on-line decision making, unpublished manuscript, 1996.
	5	Dean Foster and Rakesh V. Vohra. Asymptotic calibration. unpublished manuscript, 1995.
	6	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]
	7	Yoav Freund, Boosting a weak learning algorithm by majority, Information and Computation, v.121 n.2, p.256-285, Sept. 1995 [doi>10.1006/inco.1995.1136]
	8	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 [doi>10.1145/238061.238072]
	9	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
	10	Drew Fudenberg and David K. Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19:1065-1089, 1995.
	11	Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, 1991.
	12	Mikael Goldmann, Johan Hfistad, and Alexander Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277-300, 1992.
	13	James Hannan. Approximation to Bayes risk in repeated play. In M. Dresher, A. W. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 97-139. Princeton University Press, 1957.
	14	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]
	15	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]
	16	Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
	17	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	18	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

CITED BY 29

	Amy R. Greenwald , Jeffrey O. Kephart, Probabilistic pricebots, Proceedings of the fifth international conference on Autonomous agents, p.560-567, May 2001, Montreal, Quebec, Canada
	Philip M. Long, Minimum majority classification and boosting, Eighteenth national conference on Artificial intelligence, p.181-186, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.971-980, January 06-08, 2002, San Francisco, California
	Noga Alon , Baruch Awerbuch , Yossi Azar, The online set cover problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Eiji Takimoto , Akira Maruoka, Top-down decision tree learning as information based boosting, Theoretical Computer Science, v.292 n.2, p.447-464, 27 January 2003
	Roberto Esposito , Lorenza Saitta, A Monte Carlo analysis of ensemble classification, Proceedings of the twenty-first international conference on Machine learning, p.34, July 04-08, 2004, Banff, Alberta, Canada
	G. Rätsch , T. Onoda , K.-R. Müller, Soft Margins for AdaBoost, Machine Learning, v.42 n.3, p.287-320, March 2001
	Yan-Shi Dong , Ke-Song Han, Text classification based on data partitioning and parameter varying ensembles, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Theoretical Computer Science, v.324 n.2-3, p.137-146, 20 September 2004
	Gunnar Rätsch , Sebastian Mika , Bernhard Schölkopf , Klaus-Robert Müller, Constructing Boosting Algorithms from SVMs: An Application to One-Class Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1184-1199, September 2002
	Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Ron Meir , Gunnar Rätsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY, 2003
	Avrim Blum , Shuchi Chawla , Adam Kalai, Static optimality and dynamic search-optimality in lists and trees, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-8, January 06-08, 2002, San Francisco, California
	François Fleuret, Fast Binary Feature Selection with Conditional Mutual Information, The Journal of Machine Learning Research, 5, p.1531-1555, 12/1/2004
	R. Servedio, PAC Analogues of Perceptron and Winnow Via Boosting the Margin, Machine Learning, v.47 n.2-3, p.133-151, May-June 2002
	Jinbo Bi , Senthil Periaswamy , Kazunori Okada , Toshiro Kubota , Glenn Fung , Marcos Salganicoff , R. Bharat Rao, Computer aided detection via asymmetric cascade of sparse hyperplane classifiers, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Gunnar Rätsch , Ayhan Demiriz , Kristin P. Bennett, Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces, Machine Learning, v.48 n.1-3, p.189-218, 2002
	Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Journal of the ACM (JACM), v.53 n.5, p.845-879, September 2006
	Gilles Blanchard, Different Paradigms for Choosing Sequential Reweighting Algorithms, Neural Computation, v.16 n.4, p.811-836, April 2004
	Wenxin Jiang, Boosting with Noisy Data: Some Views from Statistical Theory, Neural Computation, v.16 n.4, p.789-810, April 2004
	Leo Breiman, Prediction games and arcing algorithms, Neural Computation, v.11 n.7, p.1493-1517, Oct. 1, 1999
	Holger Schwenk , Yoshua Bengio, Boosting Neural Networks, Neural Computation, v.12 n.8, p.1869-1887, August 2000
	Yijun Sun , Sinisa Todorovic , Jian Li, Increasing the Robustness of Boosting Algorithms within the Linear-programming Framework, Journal of VLSI Signal Processing Systems, v.48 n.1-2, p.5-20, August 2007
	Jerónimo Arenas-García , Vanessa Gómez-Verdejo , Aníbal R. Figueiras-Vidal, Fast evaluation of neural networks via confidence rating, Neurocomputing, v.70 n.16-18, p.2775-2782, October, 2007
	Jan-P. Calliess , Geoffrey J. Gordon, No-regret learning and a mechanism for distributed multiagent planning, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Finnegan Southey , Bret Hoehn , Robert C. Holte, Effective short-term opponent exploitation in simplified poker, Machine Learning, v.74 n.2, p.159-189, February 2009
	Anna Gambin , Ewa Szczurek , Janusz Dutkowski , Magda Bakun , Michał Dadlez, Classification of peptide mass fingerprint data by novel no-regret boosting method, Computers in Biology and Medicine, v.39 n.5, p.460-473, May, 2009
	Lance Fortnow , Russell Impagliazzo , Valentine Kabanets , Christopher Umans, On the Complexity of Succinct Zero-Sum Games, Computational Complexity, v.17 n.3, p.353-376, October 2008
	Robert E. Schapire, A brief introduction to boosting, Proceedings of the 16th international joint conference on Artificial intelligence, p.1401-1406, July 31-August 06, 1999, Stockholm, Sweden