Multi-class Adaboost

INTRODUCTION

The name of the analysed article is “Multi-class AdaBoost” witch is a special issue on data mining and machine learning. It was written by Ji Zhu who is a professor of statistics and EECS in department of statistics at Michigan University, Hui Zou who is a professor of statistics at Minnesota University, Saharon Rosset who is associate professor in the department of statistics and Operations research at Tel Aviv University and TREVOR HASTIE who is a professor of statistics and biomedical data science at Stanford University.

The article was published in the “Statistics and Its Interface (2009)”, Volume 2 p(349–360). This journal as defined in [5]: "is a quarterly peer-reviewed open access scientific journal covering the interface between the field of statistics and other disciplines. The journal was established in 2008 and is published by International Press. The editor-in-chief is Heping Zhang (Yale University)".

In this paper, the authors develops a new algorithm that directly extends the AdaBoost algorithm from solving the two-class classification problems to solving the multi-class classification problems. Before the authors spoke about their new algorithm, they started by giving us some information about other similar existent algorithms and their problems, then some information about the AdaBoost algorithm .

The paper is organized as follows: In section 2 , we will see the scientific context of the article. Some of the existing works on the subject are listed in section 3 . Section 4 will present the contribution of the article. In section 5, we will see the experiments and the validations that are presented in the article. The last Section (section 6) will summarize all the work.

Context of the work

As cited in [1]:" Boosting is a machine learning ensemble meta-algorithm for primarily reducing bias, and also variance in supervised learning, the original algorithm, proposed by Robert Schapire and Yoav Freund were not adaptive and could not take full advantage of the weak learners".

Few years after, Schapire and Freund developed AdaBoost [2], a new boosting algorithm witch can take full advantage of the weak learners, but this one was a good technique for only solving a two-class classification problems where the random guessing error rate is equal to 1/2, in the multi-class case the random guessing error rate is equal to (k-1)/K, where K is the number of class (if we have K=2 (two class) we will have the error rate equal to 1/2), in this case AdaBoost may fail, it's the main problem of this algorithm.

AdaBoost is a good technique for solving classification problem, it’s why the authors try to directly extend this algorithm and create a new one named (SAMME: Stagewise Additive Modeling using a Multi-class Exponential loss function).

Positioning

Several different algorithms have been developed to extend the Boosting algorithm, but most of them have been restricted to reducing the multi-class classification problem to multiple two-class problems, e.g.:
Schapire, R. (1997). Using output codes to boost multiclass learning problems and Schapire, R. and Singer, Y. (1999). Improved boosting algorithms using confidence-rated prediction.

Another multi-class boosting algorithm was proposed by Friedman, J., Hastie, T., and Tibshirani, R [3], Based on the statistical explanation that the success of AdaBoost can be understood by the fact that the population minimizer of exponential loss is one half of the log-odds. This algorithm looks very different from AdaBoost, hence it is not clear if the statistical view of AdaBoost still works in the multi-class case.