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 402 articles , 1 standard article )

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

1 2 3 ... 19 20 21 next

  1. Baumann, P.; Hochbaum, D. S.; Yang, Y. T.: A comparative study of the leading machine learning techniques and two new optimization algorithms (2019)
  2. Lopes, Miles E.: Estimating the algorithmic variance of randomized ensembles via the bootstrap (2019)
  3. Vandoni, Jennifer; Aldea, Emanuel; Le Hégarat-Mascle, Sylvie: Evidential query-by-committee active learning for Pedestrian detection in high-density crowds (2019)
  4. V’yugin, Vladimir; Trunov, Vladimir: Online aggregation of unbounded losses using shifting experts with confidence (2019)
  5. Wu, Ying Nian; Gao, Ruiqi; Han, Tian; Zhu, Song-Chun: A tale of three probabilistic families: discriminative, descriptive, and generative models (2019)
  6. Yue, Mu; Li, Jialiang; Cheng, Ming-Yen: Two-step sparse boosting for high-dimensional longitudinal data with varying coefficients (2019)
  7. Darnstädt, Malte; Ries, Christoph; Simon, Hans Ulrich: Hierarchical design of fast minimum disagreement algorithms (2018)
  8. Duchi, John; Khosravi, Khashayar; Ruan, Feng: Multiclass classification, information, divergence and surrogate risk (2018)
  9. Kotłowski, Wojciech: On minimaxity of follow the leader strategy in the stochastic setting (2018)
  10. Lee, Simon C. K.; Lin, Sheldon: Delta boosting machine with application to general insurance (2018)
  11. Mukhopadhyay, Subhadeep; Nandi, Shinjini: LPiTrack: eye movement pattern recognition algorithm and application to biometric identification (2018)
  12. Orabona, Francesco; Pál, Dávid: Scale-free online learning (2018)
  13. Wang, Boxiang; Zou, Hui: Another look at distance-weighted discrimination (2018)
  14. Wang, Haifeng; Zheng, Bichen; Yoon, Sang Won; Ko, Hoo Sang: A support vector machine-based ensemble algorithm for breast cancer diagnosis (2018)
  15. Wang, Zhu: Robust boosting with truncated loss functions (2018)
  16. Zhang, Chong; Wang, Wenbo; Qiao, Xingye: On reject and refine options in multicategory classification (2018)
  17. Zhao, Junlong; Yu, Guan; Liu, Yufeng: Assessing robustness of classification using an angular breakdown point (2018)
  18. Alon, Noga; Cesa-Bianchi, Nicolò; Gentile, Claudio; Mannor, Shie; Mansour, Yishay; Shamir, Ohad: Nonstochastic multi-armed bandits with graph-structured feedback (2017)
  19. Denis, Christophe; Hebiri, Mohamed: Confidence sets with expected sizes for multiclass classification (2017)
  20. Edhan, Omer; Hellman, Ziv; Sherill-Rofe, Dana: Sex with no regrets: how sexual reproduction uses a no regret learning algorithm for evolutionary advantage (2017)

1 2 3 ... 19 20 21 next