Jul 03, 2024

Wiki

Python

Aide

edit SideBar

Search

Adaboost


While Random Forests build several trees in parallel, boosting also builds trees (or other basic algorithms), but it does so in series. The tree

will have access to its predecessor, or more precisely to the error of the latter: it will concentrate its effort on correcting these errors. For a classification problem, the prediction is no longer a majority vote, but a weighted sum of each weak algorithm.

The first implementation of boosting, proposed by Yoav Freund and Robert Shapire, is called AdaBoost (adaptive boosting). It met a great success, both theoretically and practically, to the point of giving them the Gödel prize. At the beginning of the 1990's, Shapire and Freund each carried out work on the notion of a weak learner algorithm. Shapire showed that any weak learner can be efficiently transformed (boosted) into a robust algorithm. Later, Freund presented a new approach, boost-by-majority, which significantly improves Shapire's original approach.

Freund and Shapire share the following idea: a meta-algorithm makes successive weak algorithms work, each one having access to a different distribution of the problem, focusing on the observations that are difficult to treat, and thus forcing its successor to treat them correctly. The term boosting designates, in a broad sense, the methods working on this principle of serial assembly of weak learners.

In the case of Random Forests, the weak learners are unitary decision trees, built in a totally independent way. Each algorithm has the same vote for the final vote. Boosting is a little less democratic, and realizes a sum weighted by the final vote. The weighting coefficients in AdaBoost depend only on the errors $\varepsilon_i$ of each weak learner, as follows: $\alpha_i = \dfrac{1}{2} ln\left( \dfrac{1-\varepsilon_i}{\varepsilon_i} \right)$. And at the level of AdaBoost, the weak learner receives a different distribution of data than the -th, the errors of the latter having been overweighted.

Page Actions

Recent Changes

Group & Page

Back Links