skip to main content
10.1145/238061.238163acmconferencesArticle/Chapter ViewAbstractPublication PagescoltConference Proceedingsconference-collections
Article
Free Access

Game theory, on-line prediction and boosting

Published:01 January 1996Publication History
First page image

References

  1. 1.David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1): 1-8, Spring 1956.Google ScholarGoogle ScholarCross RefCross Ref
  2. 2.Nicolb Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 382-391, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. 3.Thomas S. Ferguson. Mathematical Statistics: A Decision Theoretic Approach. Academic Press, 1967.Google ScholarGoogle Scholar
  4. 4.Dean Foster and Rakesh Vohra. Regret in on-line decision making, unpublished manuscript, 1996.Google ScholarGoogle Scholar
  5. 5.Dean Foster and Rakesh V. Vohra. Asymptotic calibration. unpublished manuscript, 1995.Google ScholarGoogle Scholar
  6. 6.Dean P. Foster and Rakesh V. Vohra. A randomization rule for selecting forecasts. Operations Research, 41(4):704-709, July-August 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 7.Yoav Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256- 285, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. 8.Yoav Freund. Predicting a binary sequence almost as well as the optimal biased coin. In Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 9.Yoav Freund and Robert E. Schapire. A decisiontheoretic generalization of on-line learning and an application to boosting. In Computational Learning Theory: Second European Conference, EuroCOLT '95, pages 23-37. Springer-Verlag, 1995. A draft of the journal version is available electronically (on our web pages, or by email request). Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. 10.Drew Fudenberg and David K. Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19:1065-1089, 1995.Google ScholarGoogle ScholarCross RefCross Ref
  11. 11.Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, 1991.Google ScholarGoogle Scholar
  12. 12.Mikael Goldmann, Johan Hfistad, and Alexander Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277-300, 1992.Google ScholarGoogle ScholarCross RefCross Ref
  13. 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.Google ScholarGoogle Scholar
  14. 14.Nick Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285-318, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. 15.Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation. 108:212-261, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. 16.Serge A. P!otkin, David B. Shmoys, and I~va Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257-301, May 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. 17.Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2): 197-227, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. 18.Volodimir G. Vovk. Aggregating strategies. In Proceedings of the Third Annual Workshop on Computational Learning Theory, pages 371-383, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Game theory, on-line prediction and boosting

                        Recommendations

                        Comments

                        Login options

                        Check if you have access through your login credentials or your institution to get full access on this article.

                        Sign in
                        • Published in

                          cover image ACM Conferences
                          COLT '96: Proceedings of the ninth annual conference on Computational learning theory
                          January 1996
                          344 pages
                          ISBN:0897918118
                          DOI:10.1145/238061

                          Copyright © 1996 ACM

                          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                          Publisher

                          Association for Computing Machinery

                          New York, NY, United States

                          Publication History

                          • Published: 1 January 1996

                          Permissions

                          Request permissions about this article.

                          Request Permissions

                          Check for updates

                          Qualifiers

                          • Article

                          Acceptance Rates

                          Overall Acceptance Rate35of71submissions,49%

                        PDF Format

                        View or Download as a PDF file.

                        PDF

                        eReader

                        View online with eReader.

                        eReader