A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

Yoav Freund, Robert E. Schapire, 1997, Journal of Computer and System Sciences

About this paperEnglishbeside English

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Journal of Computer and System Sciences – SS1504

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 55, 119–139 (1997) ARTICLE NO. SS971504

Trong phần đầu của bài báo, chúng tôi xem xét bài toán phân bổ động các tài nguyên giữa một tập các lựa chọn trong một khung trực tuyến trường hợp xấu nhất. Mô hình mà chúng tôi nghiên cứu có thể được diễn giải như một sự mở rộng rộng và trừu tượng của mô hình dự đoán trực tuyến đã được nghiên cứu kỹ sang một thiết lập lý thuyết quyết định tổng quát. Chúng tôi chỉ ra rằng quy tắc Littlestone–Warmuth cập nhật trọng số nhân có thể được thích nghi với mô hình này, tạo ra các cận yếu hơn một chút trong một số trường hợp, nhưng áp dụng được cho một lớp bài toán học rộng hơn đáng kể. Chúng tôi chỉ ra cách thuật toán học thu được có thể được áp dụng cho nhiều loại bài toán khác nhau, bao gồm cờ bạc, dự đoán nhiều kết quả, trò chơi lặp lại và dự đoán các điểm trong Rn\mathbb{R}^n. Trong phần thứ hai của bài báo, chúng tôi áp dụng kỹ thuật cập nhật trọng số nhân để suy ra một thuật toán boosting mới. Thuật toán boosting này không yêu cầu bất kỳ kiến thức trước nào về hiệu năng của thuật toán học yếu. Chúng tôi cũng nghiên cứu các khái quát hóa của thuật toán boosting mới cho bài toán học các hàm có miền giá trị, thay vì là nhị phân, là một tập hữu hạn tùy ý hoặc một đoạn bị chặn của đường thẳng thực. © 1997 Academic Press

References

  1. E. B. Baum and D. Haussler, What size net gives valid generalization?, Adv. Neural Inform. Process. Systems I," pp. 81–90, Morgan Kaufmann, 1989.
  2. D. Blackwell, An analog of the minimax theorem for vector payoffs, Pacific J. Math. 6, No. 1 (Spring 1956), 1–8.
  3. L. Breiman, Bias, variance, and arcing classifiers, Technical Report #460, Statistics Dept., University of California, 1996; available from ftp://ftp.stat.berkeley.edu/pub/users/breiman/arcall.ps.Z., 1996.
  4. N. Cesa-Bianchi, Y. Freund, D. P. Helmholt, D. Haussler, R. E. Schapire, and M. K. Warmuth, How to use expert advice, in “Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, 1993,” pp. 382–391.
  5. T. H. Chung, Approximate methods for sequential decision making using expert advice, in “Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994,” pp. 183–189.
  6. T. M. Cover, Universal portfolios, Math. Finance 1, No. 1 (Jan. 1991), 1–29.
  7. T. G. Dietterich and G. Bakiri, Solving multiclass learning problems via error-correcting output codes, J. Artif. Intell. Res. 2 (January 1995), 263–286.
  8. H. Drucker and C. Cortes, Boosting decision trees, Adv. Neural Inform. Process. Systems 8 (1996).
  9. H. Drucker, R. Schapire, and P. Simard, Boosting performance in neural networks, Int. J. Pattern Recognition Artif. Intell. 7, No. 4 (1993), 705–719.
  10. Y. Freund, “Data Filtering and Distribution Modeling Algorithms for Machine Learning,” Ph.D. thesis, University of California at Santa Cruz, 1993; retrievable from ftp.cse.ucsc.edu/pub/tr/ucsc-crl-93-37.ps.Z.
  11. Y. Freund, Boosting a weak learning algorithm by majority, Inform. and Comput. 121, No. 2 (September 1995), 256–285; an extended abstract appeared in “Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990.”
  12. Y. Freund and R. E. Schapire, Experiments with a new boosting algorithm, in “Machine Learning: Proceedings of the Thirteenth International Conference, 1996,” pp. 148–156.
  13. Y. Freund and R. E. Schapire, Game theory, on-line prediction and boosting, in “Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996,” pp. 325–332.
  14. J. Hannan, Approximation to Bayes risk in repeated play, “Contributions to the Theory of Games,” Vol. III (M. Dresher, A. W. Tucker, and P. Wolfe, Eds.), pp. 97–139, Princeton Univ. Press, Princeton, NJ, 1957.
  15. D. Haussler, J. Kivinen, and M. K. Warmuth, Tight worst-case loss bounds for predicting with expert advice, *in* “Computational Learning Theory: Second European Conference, EuroCOLT ’95,” pp. 69–83, Springer-Verlag, New York/Berlin, 1995.
  16. J. C. Jackson and M. W. Craven, Learning sparse perceptrons, *Adv. Neural Inform. Process. Systems* **8** (1996).
  17. M. Kearns, Y. Mansour, A. Y. Ng, and D. Ron, An experimental and theoretical comparison of model selection methods, *in* “Proceedings of the Eighth Annual Conference on Computational Learning Theory, 1995.”
  18. M. J. Kearns and U. V. Vazirani, “An Introduction to Computational Learning Theory,” MIT Press, Cambridge, MA, 1994.
  19. J. Kivinen and M. K. Warmuth, Using experts for predicting continuous outcomes, *in* “Computational Learning Theory: EuroCOLT ’93,” pp. 109–120, Springer-Verlag, New York/Berlin, 1994.
  20. N. Littlestone and M. K. Warmuth, The weighted majority algorithm, *Inform. and Comput.* **108** (1994), 212–261.
  21. J. R. Quinlan, Bagging, boosting, and C4.5, *in* “Proceedings, Fourteenth National Conference on Artificial Intelligence, 1996.”
  22. R. E. Schapire, The strength of weak learnability, *Machine Learning* **5**, No. 2 (1990), 197–227.
  23. V. N. Vapnik, “Estimation of Dependences Based on Empirical Data,” Springer-Verlag, New York/Berlin, 1982.
  24. V. G. Vovk, A game of prediction with expert advice, *in* “Proceedings of the Eighth Annual Conference on Computational Learning Theory, 1995.”
  25. V. G. Vovk, Aggregating strategies, *in* “Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990,” pp. 321–383.
  26. R. S. Wenocur and R. M. Dudley, Some special Vapnik–Chervonenkis classes, *Discrete Mathematics* **33** (1981), 313–318.

Read off the page by a vision model reading the page images using gpt-5. Translated into Tiếng Việt by gpt-5, against glossary version 6. Translated from the English.