The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
How to use expert advice
Open accessAbstract
We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. We measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictins. We show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. Our upper and lower bounds have matching leading constants in most cases. We then show how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context. We also compare our analysis to the case in which log loss is used instead of the expected number of mistakes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Neural Networks: A Comprehensive Foundation
Haykin, S. (1998) · Cited by 30,070
Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference
(2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.001.0001 · Cited by 8,890
Neural networks: A comprehensive foundation
Tadeusiewicz, R. (1995) · Control Engineering Practice · doi:10.1016/0967-0661(95)90080-2 · Cited by 7,218
Modeling by shortest data description
Rissanen, J. (1978) · Automatica · doi:10.1016/0005-1098(78)90005-5 · Cited by 6,011
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
Estimation of Dependences Based on Empirical Data
Vapnik, V. (2006) · Information Science and Statistics · doi:10.1007/0-387-34239-7 · Cited by 2,238
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
Self-citationLearnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839
Self-citationThe Asymptotic Theory of Extreme Order Statistics
Angus, J. E. (1990) · Technometrics · doi:10.1080/00401706.1990.10484616 · Cited by 1,830
Contributions to the theory of games.
(1960) · Journal of the Franklin Institute · doi:10.1016/0016-0032(60)90366-5 · Cited by 1,824
Cited by
Pattern Recognition and Neural Networks
Ripley, B. D. (1996) · Cambridge University Press eBooks · doi:10.1017/cbo9780511812651 · Cited by 6,459
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
Self-citation(2002) · doi:10.1137/s0097539701398375 · Cited by 2,275
Foundations of Machine Learning
Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018) · doi:10.7551/mitpress/10290.001.0001 · Cited by 1,122
Large margin classification using the perceptron algorithm
Freund, Y., & Schapire, R. E. (1998) · Proceedings of the eleventh annual conference on Computational learning theory · doi:10.1145/279943.279985 · Cited by 1,071
Self-citationCan machine learning be secure?
Barreno, M., Nelson, B., Sears, R., Joseph, A. D., & Tygar, J. D. (2006) · Proceedings of the 2006 ACM Symposium on Information, computer and communications security · doi:10.1145/1128817.1128824 · Cited by 836
Gambling in a rigged casino: The adversarial multi-armed bandit problem
Auer, P., Cesa-Bianchi, N., Freund, Y., & Schapire, R. E. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492488 · Cited by 742
Self-citationLarge Margin Classification Using the Perceptron Algorithm
Freund, Y., & Schapire, R. E. (1999) · Machine Learning · doi:10.1023/a:1007662407062 · Cited by 604
Self-citationEfficient algorithms for online decision problems
Kalai, A., & Vempala, S. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.016 · Cited by 591
Herbster, M., & Warmuth, M. K. (1998) · Machine Learning · doi:10.1023/a:1007424614876 · Cited by 560
Self-citationAdaptive Game Playing Using Multiplicative Weights
Freund, Y., & Schapire, R. E. (1999) · Games and Economic Behavior · doi:10.1006/game.1999.0738 · Cited by 515
Self-citationOn the Generalization Ability of On-Line Learning Algorithms
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.833339 · Cited by 426
Self-citationDistributed learning in wireless sensor networks
Predd, J. B., Kulkarni, S. B., & Poor, H. V. (2006) · IEEE Signal Processing Magazine · doi:10.1109/msp.2006.1657817 · Cited by 369
Machine Learning for Information Extraction in Informal Domains
Freitag, D. (2000) · Machine Learning · doi:10.1023/a:1007601113994 · Cited by 350
Adaptive regularization of weight vectors
Crammer, K., Kulesza, A., & Dredze, M. (2013) · Machine Learning · doi:10.1007/s10994-013-5327-x · Cited by 337
Yang, Y. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753168262 · Cited by 312
Blum, A., Hopcroft, J., & Kannan, R. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108755528 · Cited by 304
Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions
Azoury, K. S., & Warmuth, M. K. (2001) · Machine Learning · doi:10.1023/a:1010896012157 · Cited by 298
Self-citationA Game of Prediction with Expert Advice
Vovk, V (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1556 · Cited by 281
Distributed Learning in Wireless Sensor Networks
Predd, J. B., Kulkarni, S. R., & Poor, H. V. (2007) · Wireless Sensor Networks · doi:10.1002/9780470061794.ch8 · Cited by 264
Using additive expert ensembles to cope with concept drift
Kolter, J. Z., & Maloof, M. A. (2005) · Proceedings of the 22nd international conference on Machine learning - ICML '05 · doi:10.1145/1102351.1102408 · Cited by 261
Smart Experts for Network State Estimation
Edalat, Y., Ahn, J.-S., & Obraczka, K. (2016) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2016.2586506 · Cited by 27
Metadata
- Authors
- Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D. P., Schapire, R. E., & Warmuth, M. K.
- Venue
- Journal of the ACM
- Published
- 1997-05
- Volume
- 44
- Issue
- 3
- Pages
- 427-485
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1979675141
- Cited by
- 634
- References
- 48
- FWCI
- 26.34
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.