11
$\begingroup$

In section 7 of the paper Random Forests (Breiman, 1999), the author states the following conjecture: "Adaboost is a Random Forest".

Has anyone proved, or disproved this? What has been done to prove or disprove this post 1999?

$\endgroup$
3
  • $\begingroup$ Please read stats.stackexchange.com/questions/77018/… Maybe you'll find your answer there $\endgroup$
    – user75008
    May 1 '15 at 6:11
  • $\begingroup$ @user75008 Thanks! So, section 7 provides another conjecture, such that if proven, shows that adaboost is equivalent to random forest. Has anyone shown this conjecture to be true? $\endgroup$
    – Alex
    May 1 '15 at 6:15
  • $\begingroup$ @user75008 I am reading your link, stats.stackexchange.com/questions/77018/…, do you think it suggests that Adaboost is not equivalent to Random Forest? $\endgroup$
    – Alex
    May 1 '15 at 6:26
4
$\begingroup$

Interesting question. A bunch of work on explaining ada boost via a few different tactics has been done since then.

I did a quick literature search and this somewhat odd paper appears to be the most recent one on the subject and also reviews a bunch of the intercedent work by Leo Breiman and others:

http://arxiv.org/pdf/1212.1108.pdf

I have no idea if their results are valid but they claim to have failed to prove Breiman's conjecture but to have proved a weakened version of it claiming adaboost is measure preserving but not necessarily ergodic.

They also present some empirical evidence that adaboost does in fact sometimes overfit.

I think that suggests adaboost may be related to a random forest but not entirely (or not always) equivalent in the way Breiman conjectured?

$\endgroup$
4
  • $\begingroup$ thanks, so I guess this is still an open question, but your last statement is telling. $\endgroup$
    – Alex
    May 6 '15 at 6:05
  • 1
    $\begingroup$ Yeah I think it is still open. I also think that interest has dropped off in analyzing AdaBoost as [stochastic] gradient boosting machines have become more popular. AdaBoost is a form of gradient descent (en.wikipedia.org/wiki/AdaBoost#Boosting_as_Gradient_Descent) and thinking in terms of explicitly randomized gradient descent may be more intuitive and more practical then the equivalency Brieman proposed. (Ie even if it were true it might be really hard to sample from the needed distribution in practice.) $\endgroup$ May 6 '15 at 14:46
  • $\begingroup$ I just saw this new paper on the subject: arxiv.org/pdf/1504.07676v1.pdf $\endgroup$ May 8 '15 at 15:33
  • $\begingroup$ Very interesting if true! "We conclude that boosting should be used like random forests: with large decision trees and without direct regularization or early stopping." $\endgroup$
    – Alex
    May 8 '15 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.