Article

Free access

Game theory, on-line prediction and boosting

Authors:

Yoav Freund,

Robert E. SchapireAuthors Info & Claims

COLT '96: Proceedings of the ninth annual conference on Computational learning theory

Pages 325 - 332

https://doi.org/10.1145/238061.238163

Published: 01 January 1996 Publication History

PDF eReader

References

[1]

David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1): 1-8, Spring 1956.

Crossref

Google Scholar

[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.

Digital Library

Google Scholar

[3]

Thomas S. Ferguson. Mathematical Statistics: A Decision Theoretic Approach. Academic Press, 1967.

Google Scholar

[4]

Dean Foster and Rakesh Vohra. Regret in on-line decision making, unpublished manuscript, 1996.

Google Scholar

[5]

Dean Foster and Rakesh V. Vohra. Asymptotic calibration. unpublished manuscript, 1995.

Google Scholar

[6]

Dean P. Foster and Rakesh V. Vohra. A randomization rule for selecting forecasts. Operations Research, 41(4):704-709, July-August 1993.

Digital Library

Google Scholar

[7]

Yoav Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256- 285, 1995.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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).

Digital Library

Google Scholar

[10]

Drew Fudenberg and David K. Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19:1065-1089, 1995.

Crossref

Google Scholar

[11]

Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, 1991.

Google Scholar

[12]

Mikael Goldmann, Johan Hfistad, and Alexander Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277-300, 1992.

Crossref

Google Scholar

[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 Scholar

[14]

Nick Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285-318, 1988.

Crossref

Google Scholar

[15]

Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation. 108:212-261, 1994.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[17]

Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2): 197-227, 1990.

Crossref

Google Scholar

[18]

Volodimir G. Vovk. Aggregating strategies. In Proceedings of the Third Annual Workshop on Computational Learning Theory, pages 371-383, 1990.

Digital Library

Google Scholar

Cited By

View all

Chang PFishman LNeel SSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Feature importance disparities for data bias investigationsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692309(6170-6201)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692309
Wei YFeng RWang ZHu D(2024)Enhancing Multimodal Cooperation via Sample-Level Modality Valuation2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02581(27328-27337)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02581
Markarian CFachkha CYassine N(2024)Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive AnalysisIEEE Access10.1109/ACCESS.2024.350454112(174723-174739)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3504541
Show More Cited By

Index Terms

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '96: Proceedings of the ninth annual conference on Computational learning theory

January 1996

344 pages

ISBN:0897918118

DOI:10.1145/238061

Chairmen:
Avrim Blum
Carnegie Mellon Univ., Pittsburgh, PA
,
Michael Kearns
AT&T Research

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: 01 January 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

9COLT96

Sponsor:

SIGAI
SIGACT
Univ degli Studi de Milano

9COLT96: 9th Annual Conference on Computational Learning Theory

June 28 - July 1, 1996

Desenzano del Garda, Italy

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

216
Total Citations
View Citations
3,084
Total Downloads

Downloads (Last 12 months)362
Downloads (Last 6 weeks)32

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chang PFishman LNeel SSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Feature importance disparities for data bias investigationsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692309(6170-6201)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692309
Wei YFeng RWang ZHu D(2024)Enhancing Multimodal Cooperation via Sample-Level Modality Valuation2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02581(27328-27337)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02581
Markarian CFachkha CYassine N(2024)Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive AnalysisIEEE Access10.1109/ACCESS.2024.350454112(174723-174739)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3504541
Zhou QHuang C(2024)A recommendation attack detection approach integrating CNN with BaggingComputers and Security10.1016/j.cose.2024.104030146:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.cose.2024.104030
Wei ZZhou YLi ZKulkarni MZhang Y(2024)Supporting equitable and responsible highway safety improvement funding allocation strategies – Why AI prediction biases matterAccident Analysis & Prevention10.1016/j.aap.2024.107585202(107585)Online publication date: Jul-2024
https://doi.org/10.1016/j.aap.2024.107585
Moriah MVermet FCharpentier A(2024)Measuring and mitigating biases in motor insurance pricingEuropean Actuarial Journal10.1007/s13385-024-00390-814:3(833-869)Online publication date: 9-Jul-2024
https://doi.org/10.1007/s13385-024-00390-8
Ghanimi RChouikri KGhanimi IGhanimi FSoulaymani A(2023)Un enfoque basado en el aprendizaje automático para el diagnóstico urgente de envenenamiento en situaciones de emergenciaData and Metadata10.56294/dm20231102(110)Online publication date: 3-Dec-2023
https://doi.org/10.56294/dm2023110
Mandal DTriantafyllou SRadanovic GKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Performative reinforcement learningProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619396(23642-23680)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619396
Uspenskiy VSaprankov VMazin VFilippov ABoyarskaya NMalashicheva AMoiseeva O(2023)Machine learning and artificial intelligence in the prediction, diagnosis and treatment of thoracic aortic diseases (literature review). Part 1Russian Journal for Personalized Medicine10.18705/2782-3806-2023-3-3-118-1313:3(118-131)Online publication date: 28-Jul-2023
https://doi.org/10.18705/2782-3806-2023-3-3-118-131
HAO JSHAO KLI KLI DMAO HHU SWANG Z(2023)Research and applications of game intelligenceSCIENTIA SINICA Informationis10.1360/SSI-2023-001053:10(1892)Online publication date: 16-Oct-2023
https://doi.org/10.1360/SSI-2023-0010
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Pou Game Guide

Castle Clash Game Guide

Angry Birds Epic Game: How to Download for Android, PC, IOS, Kindle + Tips