How to use expert advice

ABSTRACT

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.

REFERENCES

• 1: BIRGE, L., AND MASSART, P. 1993. Rates of convergence for minimum contrast estimators. Prob. Theory Rel. Fields 97, 113-150.
• 2: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 3: 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]
• 4: Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , Manfred K. Warmuth, On-line prediction and conversion strategies, Machine Learning, v.25 n.1, p.71-110, Oct. 1996 [doi>10.1023/A:1018348209754]
• 5: Thomas H. Chung, Approximate methods for sequential decision making using expert advice, Proceedings of the seventh annual conference on Computational learning theory, p.183-189, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181097]
• 6: COVER, T.M. 1965. Behaviour of sequential predictors of binary sequences. In Transactions of the 4th Prague Conference on Information Theory, Statistical Decision Functions, Random Processes. Publishing House of the Czechoslovak Academy of Sciences.
• 7: COVER, T. M., AND SHANAR, A. 1977. Compound Bayes predictors for sequences with apparent Markov structure. IEEE Trans. Syst. Man Cybernet. SMC-7, 6 (June), 421-424.
• 8: DAWID, A. P. 1984. Statistical theory: The prequential approach. J. Roy. Stat. Soc., Series A, 278-292.
• 9: DAWlD, A. 1991. Prequential analysis, stochastic complexity and Bayesian inference. In Bayesian Statistics, vol. 4. Oxford University Press, pp. 109-125.
• 10: DAWlD, A.P. 1996. Prequential data analysis. Curt. Iss. Stat. Inference, to appear.
• 11: Alfredo DeSantis , George Markowsky , Mark N. Wegman, Learning probabilistic prediction functions, Proceedings of the first annual workshop on Computational learning theory, p.312-328, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 12: FEDER, M., MERHAV, N., AND GUTMAN, M. 1992. Universal prediction of individual sequences. IEEE Trans. Inf. Theory 38, 1258-1270.
• 13: Amos Fiat , Dean P. Foster , Howard Karloff , Yuval Rabani , Yiftach Ravid , Sundar Vishwanathan, Competitive algorithms for layered graph traversal, Proceedings of the 32nd annual symposium on Foundations of computer science, p.288-297, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185381]
• 14: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 15: Amos Fiat , Yuval Rabani , Yiftach Ravid, Competitive k-server algorithms, Journal of Computer and System Sciences, v.48 n.3, p.410-428, June 1994 [doi>10.1016/S0022-0000(05)80060-1]
• 16: GALAMBOS, J. 1987. The Asymptotic Theory of Extreme Order Statistics, 2nd ed. R. E. Kreiger.
• 17: HANNAN, J. 1957. Approximation to Bayes risk in repeated play. In Contributions to the Theory of Games, vol. 3. Princeton University Press, Princeton, N.J., pp. 97-139.
• 18: HAUSSLER, D., AND BARRON, A. 1992. How well do Bayes methods work for on-line prediction of { + 1, -1 } values? In Proceedings of the 3rd NEC Symposium on Computation and Cognition. SIAM.
• 19: David Haussler , Michael Kearns, Equivalence of models for polynomial learnability, Information and Computation, v.95 n.2, p.129-161, Dec. 1991 [doi>10.1016/0890-5401(91)90042-Z]
• 20: David Haussler , Michael Kearns , Robert E. Schapire, Bounds on the Sample Complexity of Bayesian Learning Using Information Theory and the VC Dimension, Machine Learning, v.14 n.1, p.83-113, Jan. 1994 [doi>10.1023/A:1022698821832]
• 21: David Haussler , Jyrki Kivinen , Manfred K. Warmuth, Tight worst-case loss bounds for predicting with expert advice, Proceedings of the Second European Conference on Computational Learning Theory, p.69-83, March 13-15, 1995
• 22: D. Haussler , N. Littlestone , M. K. Warmuth, Predicting {0, 1}-functions on randomly drawn points, Information and Computation, v.115 n.2, p.248-292, Dec. 1994 [doi>10.1006/inco.1994.1097]
• 23: Simon Haykin, Neural Networks: A Comprehensive Foundation, Prentice Hall PTR, Upper Saddle River, NJ, 1994
• 24: David P. Helmbold , Manfred K. Warmuth, On weak learning, Journal of Computer and System Sciences, v.50 n.3, p.551-573, June 1995 [doi>10.1006/jcss.1995.1044]
• 25: Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
• 26: Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward Efficient Agnostic Learning, Machine Learning, v.17 n.2-3, p.115-141, Nov./Dec. 1994 [doi>10.1007/BF00993468]
• 27: Jyrki Kivinen , Manfred K. Warmuth, Using experts for predicting continuous outcomes, Proceedings of the first European conference on Computational learning theory, p.109-120, October 1994, Royal Holloway, Univ. of London, United Kingdom
• 28: Nick Littlestone, From on-line to batch learning, Proceedings of the second annual workshop on Computational learning theory, p.269-284, December 1989, Santa Cruz, California, United States
• 29: Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, On-line learning of linear functions, Computational Complexity, v.5 n.1, p.1-23, Jan. 1995 [doi>10.1007/BF01277953]
• 30: 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]
• 31: MERHAV, N., AND FEDER, M. 1993. Universal schemes for sequential decision for individual data sequences. IEEE Trans. Inf. Theory, 39, 4, 1280-1292.
• 32: RISSANEN, J. 1978. Modeling by shortest data description. Automatica 14, 465-471.
• 33: RISSANEN, J. 1986. Stochastic complexity and modeling. Ann. Star. 14, 3, 1080-1100.
• 34: RISSANEN, J., AND LANGDON, G. G., JR. 1981. Universal modeling and coding. IEEE Trans. Inf. Theory IT-27, 1 (Jan.), 12-23.
• 35: SEUNG, n. S., SOMPOLINSKY, n., AND TISHBY, N. 1992. Statistical mechanics of learning from examples. Phys. Rev A 45, 8, 6056-6091.
• 36: SHTARKOV, YU. M. 1975. Coding of discrete sources with unknown statistics. In Topics in Information Theory. North-Holland, Amsterdam, The Netherlands, pp. 559-574.
• 37: SHTARKOV, YU. M. 1987. Universal sequential coding of single messages. Prob. Inf. Transm. 23 (July-September), 175-186.
• 38: SOMPOLINSKY, H., TISHBY, N., AND SEUNG, H. S. 1992. Learning from examples in large neural networks. Phys. Rev. Lett. 65, 1683-1686.
• 39: STONE, C. J. 1977. Cross-validation: A review. Math. Operationforsch. Statist. Ser Statist. 9, 127-139.
• 40: TALAGRAND, M. 1994. Sharper bounds for Gaussian and empirical processes. Ann. Prob. 22, 1, 28-76.
• 41: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 42: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 43: VAPNIK, V. 1992. Principles of risk minimization for learning theory. In Advances in Neural Information Processing Systems, vol. 4. John E. Moody, Steve J. Hanson, and Richard P. Lippman, eds. Morgan Kaufmann, San Mateo, Calif.
• 44: 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
• 45: V. G. Vovk, Universal forecasting algorithms, Information and Computation, v.96 n.2, p.245-277, Feb. 1992 [doi>10.1016/0890-5401(92)90050-P]
• 46: VOVK, V.G. 1993. A logic of probability, with application to the foundations of statistics. J. Roy. Statis Soc, Ser. B-Methodolical 55, 2, 317-351.
• 47: Kenji Yamanishi, A loss bound model for on-line stochastic prediction algorithms, Information and Computation, v.119 n.1, p.39-54, May 15, 1995 [doi>10.1006/inco.1995.1076]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Automatic analysis of algorithms
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms

Keywords:
algorithms