Boosting. Foundations and algorithms. (Q2893108)

Suppose we have access to a learning algorithm that produces weak classifiers, i.e., classifiers that perform slightly better than random guessing, with high probability. Can we combine these classifiers with the help of data such that with high probability the resulting classifier performs arbitrarily well? This fundamental question in machine learning was first raised by M.~Kearns and G.~Valiant in 1994 when working in the probably approximately correct (PAC) learning framework. The authors of this book, who won the Gödel Prize for their work in 2003, gave a positive answer by inventing the first boosting algorithms around 1996. This book, which is the first solely focussed on this topic, provides a comprehensive introduction to boosting algorithms.NEWLINENEWLINEAfter a gentle introduction to machine learning in general and boosting in particular, the book is devided into 4 parts, where the first two parts contain the core material on boosting and the third and fourth part discuss more advanced material and extensions.NEWLINENEWLINEIn the first part, the basic statistical analysis is presented. To this end, the authors provide an introduction to uniform deviation bounds, VC-dimension, and compression bounds in Chapter 2. The subsequent chapter considers AdaBoosts training error, and the fourth chapter combines these results to establish generalization error bounds for AdaBoost. In addition, it shows the equivalence between weak and strong learnability. In Chapter 5, the authors present their preferred view on boosting as a margin maximization scheme.NEWLINENEWLINEThe second part contains three very nice chapters presenting rather different interpretations of boosting. The relationship of AdaBoost to game theory and online learning is explored in Chapter 6, while Chapter 7 shows that AdaBoost is greedily minimizing a particular empirical risk. In the third and last chapter of this part, the authors then interpret AdaBoost as an iterative projection algorithm and prove some of its convergence properties.NEWLINENEWLINEIn the third part of the book, extensions of AdaBoost to learning scenarios more coomplicated than binary classification are presented. The first such extension that uses confidence-rated weak learners is introduced in Chapter 9. Multiclass classification is considered in Chapter 10, and the final Chapter 11 introduces a boosting algorithm for the ranking problem.NEWLINENEWLINEIn the fourth and final part of the book some advanced material on boosting is presented. The highlight of this part is probably Chapter 12, which presents a complete proof of Adaboost's universal consistency. Chapter 13 revisits game theoretic aspects of boosting, and the last chapter introduces a continuous time modification of AdaBoost.NEWLINENEWLINEThis book is certainly much welcomed in the machine learning community as it presents the first comprehensive introduction to boosting and its theory. Its gentle style and the extensive number of interesting exercises at the end of each chapter makes it serve well as a textbook, in particular for advanced graduate courses in computer science, while the bibliographic notes nicely link to the existing literature on boosting. The mathematically oriented reader may however be warned that the book's style is not as rigorous as in mathematical textbooks, since the book obviously targets more towards computer scientists. Moreover, the author's preference towards the margin maximization view of boosting seems to rely more on philosophical reasoning than on compelling arguments. Nonetheless, the book is undoubtedly an excellent introduction to boosting.