Random forests have a reputation among practitioners of being among the most effective classification techniques. Yet we don't encounter them much in the learning-theoretic literature, from which I surmise an absence of deep theoretical results. If one wanted to delve into this theory, where would one start?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ There is a new paper in upcoming SODA'15 that may be relevant. See meetings.siam.org/sess/dsp_talk.cfm?p=68795 $\endgroup$– Chandra ChekuriOct 28, 2014 at 1:02
-
$\begingroup$ @ChandraChekuri, I only see an abstract, but not a paper. Is there a full paper? And does it have anything to do with the random forests machine learning method (for supervised learning/classification tasks)? $\endgroup$– D.W.Oct 29, 2014 at 20:42
-
$\begingroup$ @D.W Write to the authors and see if they are willing to share a copy. I am aware of the results but haven't seen the paper myself. $\endgroup$– Chandra ChekuriOct 30, 2014 at 17:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Following Simone's answer, Gerard Biau has several very good papers looking at convergence and consistency for random forests. The analyses are for slightly simplified versions of the algorithm compared to Breiman 2001, but less simplified than previous results.
Biau's papers (along with his collaborators) are all available on his website:
http://www.lsta.upmc.fr/BIAU/publications.html
One that is particularly relevant are an "in press" work on consistency: http://www.lsta.upmc.fr/BIAU/sbv.pdf
There are 2-3 other papers with random forest content. I just joined cstheory, so I can't post more than two links but the above publications site has them all.
I hope this is of help. It looks like there is a burst of recent activity since 2008, after a period of largely empirical use of the method. And the good news is, theoretical investigations are seeming to show that the method is robust and has good properties.
$\begingroup$
$\endgroup$
I guess you already had a look at Breiman's 2001 paper about RF. I can just point out a few other references:
Empirical comparisons of different RF simplifications that allow proving theorems: Narrowing the Gap: Random Forests In Theory and In Practice
This is the newest reference I can provide. In this paper you can also find some citations of Biau's papers about initial work on theoretical results for RF.
If you are interested in theoretical results about variable importance in RF: Understanding variable importances in forests of randomized trees
Actually I just found out that last paper's author (Gilles Louppe) just posted on arxiv his PhD thesis (v2): Understanding Random Forests: From Theory to Practice
