×

A game of prediction with expert advice. (English) Zbl 0945.68528


MSC:

68T05 Learning and adaptive systems in artificial intelligence

Software:

AdaBoost.MH
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Alekseev, V. M.; Tikhomirov, V. M.; Fomin, S. V., Optimal Control, (1987), Plenum New York · Zbl 0689.49001
[2] Borovkov, A. A., Teoriya Veroyatnostei, (1986), Nauka Moscow
[3] Cesa-Bianchi, N.; Freund, Y.; Haussler, D.; Helmbold, D. P.; Schapire, R. E.; Warmuth, M. K., How to use expert advice, Journal of the ACM, 44, 427-485, (1997) · Zbl 0890.68066
[4] Cesa-Bianchi, N.; Freund, Y.; Helmbold, D. P.; Warmuth, M. K., On-line prediction and conversion strategies, Mach. Learning, 25, 71-110, (1996)
[5] Cohen, G. D., A nonconstructive upper bound on covering radius, IEEE Trans. Inform. Theory, 29, 352-353, (1983) · Zbl 0545.94010
[6] Cover, T.; Ordentlich, E., Universal portfolios with side information, IEEE Trans. Inform. Theory, 42, 348-363, (1996) · Zbl 0851.90012
[7] Dawid, A. P., Statistical theory. the prequential approach (with discussion), J. Roy. Statist. Soc. Ser. A, 147, 278-292, (1984) · Zbl 0557.62080
[8] Dawid, A. P., Probability forecasting, Encyclopedia of Statistical Sciences, (1986), Wiley New York, p. 210-218
[9] DeSantis, A.; Markowsky, G.; Wegman, M. N., Learning probabilistic prediction functions, Proceedings, 29th Annual IEEE Symposium on Foundations of Computer Science, (1988), IEEE Los Alamitos, p. 110-119
[10] Feller, W., An Introduction to Probability Theory and Its Applications, (1971), Wiley New York · Zbl 0219.60003
[11] Foster, D. P., Prediction in the worst case, Ann. Statist., 19, 1084-1090, (1991) · Zbl 0725.62085
[12] Foster, D. P.; Vohra, R. V., A randomization rule for selecting forecasts, Oper. Res., 41, 704-709, (1993) · Zbl 0785.62091
[13] Freund, Y., Predicting a binary sequence almost as well as the optimal biased coin, Proceedings, 9th Annual ACM Conference on Computational Learning Theory, (1996), Assoc. Comput. Mach New York, p. 89-98
[14] Freund, Y.; Schapire, R. E., A decision-theoretic generalization of on-line learning and an application to boosting, (Vitányi, P., Computational Learning Theory, Lecture Notes in Computer Science, 904, (1995), Springer-Verlag Berlin), 23-37
[15] Haussler, D.; Kivinen, J.; Warmuth, M. K., Tight worst-case loss bounds for predicting with expert advice, Technical Report, (December 1994)
[16] Helmbold, D. P.; Schapire, R. E.; Singer, Y.; Warmuth, M. K., On-line portfolio selection using multiplicative updates, Proceedings, 13th international Conference on Machine Learning, (1996)
[17] Herbster, M.; Warmuth, M., Tracking the best expert, Proceedings, 12th International Conference on Machine Learning, (1995), Morgan Kaufmann, p. 286-294
[18] Kivinen, J.; Warmuth, M. K., Exponentialed gradient versus gradient descent for linear predictors, Inform. and Comput., 132, 1-63, (1997) · Zbl 0872.68158
[19] Li, M.; Vitányi, P., An Introduction to Kolmogorov’s Complexity and Its Applications, (1993), Springer-Verlag New York
[20] Littlestone, N., Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Mach. Learning, 2, 285-318, (1988)
[21] N. Littlestone, P. M. Long, On-line learning with linear loss constraints, June 1994 · Zbl 1045.68596
[22] Littlestone, N.; Long, P. M.; Warmuth, M. K., On-line learning of linear functions, J. Comput. Complexity, 5, 1-23, (1995) · Zbl 0816.68106
[23] Littlestone, N.; Warmuth, M. K., The weighted majority algorithm, Inform. and Comput., 108, 212-261, (1994) · Zbl 0804.68121
[24] Martin, D. A., An extension of Borel determinacy, Ann. Pure Appl. Logic, 49, 279-293, (1990) · Zbl 0721.03036
[25] Rissanen, J., A universal prior for integers and estimation by minimum description length, Ann. Statist., 11, 416-431, (1983) · Zbl 0513.62005
[26] Rissanen, J., Stochastic complexity (with discussion), J. Roy. Statist. Soc. Ser. B, 49, 223-239, (1987) · Zbl 0654.62008
[27] Rissanen, J., Stochastic complexity—an introduction, (Gammerman, A., Computational Learning and Probabilistic Reasoning, (1996), Wiley Chichester), 33-42
[28] Solomonoff, R. J., The discovery of algorithmic probability: A guide for the programming of true creativity, (Vitányi, P., Computational Learning Theory, Lectures Notes in Computer Science, 904, (1995), Springer-Verlag Berlin), 1-22
[29] Vapnik, V., The Nature of Statistical Learning Theory, (1995), Springer-Verlag New York · Zbl 0833.62008
[30] Vapnik, V., Structure of statistical learning theory, (Gammerman, A., Computational Learning and Probabilistic Reasoning, (1996), Wiley Chichester), 3-31
[31] Vovk, V., Aggregating strategies, (Fulk, M.; Case, J., Proceedings, 3rd Annual Workshop on Computational Learning Theory, (1990), Morgan Kaufmann San Mateo), 371-383
[32] Vovk, V., Universal forecasting algorithms, Inform. and Comput., 96, 245-277, (1992) · Zbl 0745.60038
[33] V. Vovk, An optimality property of the weighted majority algorithm
[34] Wallace, C.; Freeman, P. R., Estimation and inference by compact coding (with discussion), J. Roy. Statist. Soc. Ser. B, 49, 240-265, (1987) · Zbl 0653.62005
[35] Wallace, C., MML inference of predictive trees, graphs and nets, (Gammerman, A., Computational Learning and Probabilistic Reasoning, (1995), Wiley Chichester), 43-66
[36] Williams, D., Probability with Martingales, (1991), Cambridge Univ. Press Cambridge · Zbl 0722.60001
[37] Yamanishi, K., Randomized approximate aggregating strategies and their applications to prediction and discrimination, Proceedings, 8th Annual ACM Conference on Computational Learning Theory, (1995), Assoc. Comput. Mach New York, p. 83-90
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.