A decision-theoretic generalization of on-line learning and an application to boosting. In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weight-update Littlestone-Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in $bfR^n$. In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line.

References in zbMATH (referenced in 311 articles , 1 standard article )

Showing results 1 to 20 of 311.
Sorted by year (citations)

1 2 3 ... 14 15 16 next

  1. Adamskiy, Dmitry; Koolen, Wouter M.; Chernov, Alexey; Vovk, Vladimir: A closer look at adaptive regret (2016)
  2. Buchbinder, Niv; Chen, Shahar; Naor, Joseph (Seffi); Shamir, Ohad: Unified algorithms for online learning and competitive analysis (2016)
  3. Geurts, Pierre; Wehenkel, Louis: Comments on: “A random forest guided tour” (2016)
  4. Manukyan, Artür; Ceyhan, Elvan: Classification of imbalanced data with a geometric digraph family (2016)
  5. Neu, Gergely; Bartók, Gábor: Importance weighting without importance weights: an efficient algorithm for combinatorial semi-bandits (2016)
  6. Nie, Jiazhong; Kotlowski, Wojciech; Warmuth, Manfred K.: Online PCA with optimal regret (2016)
  7. Xie, Jianwen; Lu, Yang; Zhu, Song-Chun; Wu, Ying Nian: Inducing wavelets into random fields via generative boosting (2016)
  8. Xu, Philippe; Davoine, Franck; Zha, Hongbin; Denœux, Thierry: Evidential calibration of binary SVM classifiers (2016)
  9. Ye, Lei; Wang, Can; Xu, Xin; Chen, Wei: Multi-class $\ell_2$-Boost with the scoring coding (2016)
  10. Berend, Daniel; Kontorovich, Aryeh: A finite sample analysis of the naive Bayes classifier (2015)
  11. Biau, Gérard; Cadre, Beno^ıt; Paris, Quentin: Cox process functional learning (2015)
  12. Feng, Hui-Min; Wang, Xi-Zhao: Performance improvement of classifier fusion for batch samples based on upper integral (2015)
  13. Geist, Matthieu: Soft-max boosting (2015)
  14. Khachay, Michael: Committee polyhedral separability: complexity and polynomial approximation (2015)
  15. Kim, Sangwook; Yu, Zhibin; Kil, Rhee Man; Lee, Minho: Deep learning of support vector machines with class probability output networks (2015)
  16. Kuang, Wei; Brown, Laura E.; Wang, Zhenlin: Selective switching mechanism in virtual machines via support vector machines and transfer learning (2015)
  17. Lee, Yoonkyung; Wang, Rui: Does modeling lead to more accurate classification? A study of relative efficiency in linear classification (2015)
  18. Lin, Tong; Xue, Hanlin; Wang, Ling; Huang, Bo; Zha, Hongbin: Supervised learning via Euler’s elastica models (2015)
  19. Mathlouthi, Walid; Fredette, Marc; Larocque, Denis: Regression trees and forests for non-homogeneous Poisson processes (2015)
  20. Naval, Smita; Laxmi, Vijay; Gaur, Manoj Singh; Vinod, P.: An efficient block-discriminant identification of packed malware (2015)

1 2 3 ... 14 15 16 next