<p>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.  </p>

<p>Biau's papers (along with his collaborators) are all available on his website:</p>

<p><a href="http://www.lsta.upmc.fr/BIAU/publications.html">http://www.lsta.upmc.fr/BIAU/publications.html</a></p>

<p>One that is particularly relevant are an "in press" work on consistency:  <a href="http://www.lsta.upmc.fr/BIAU/sbv.pdf">http://www.lsta.upmc.fr/BIAU/sbv.pdf</a></p>

<p>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.  </p>

<p>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.  </p>

CC BY-SA 3.0
2014-10-31T22:21:12.740Z
2014-10-31T22:21:12.740Z
Mark Madsen
<p>I guess you already had a look at Breiman's 2001 paper about RF. I can just point out a few other references: </p>

<p>Empirical comparisons of different RF simplifications that allow proving theorems:  <a href="http://jmlr.org/proceedings/papers/v32/denil14.html" rel="nofollow">Narrowing the Gap: Random Forests In Theory and In Practice</a> </p>

<p>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.</p>

<p>If you are interested in theoretical results about variable importance in RF: <a href="http://nips.cc/Conferences/2013/Program/event.php?ID=3782" rel="nofollow">Understanding variable importances in forests of randomized trees</a></p>

<p>Actually I just found out that last paper's author (Gilles Louppe) just posted on arxiv his PhD thesis (v2): <a href="http://arxiv.org/abs/1407.7502" rel="nofollow">Understanding Random Forests: From Theory to Practice</a></p>

CC BY-SA 3.0
2014-10-27T22:56:59.360Z
2014-10-29T04:52:49.393Z
2014-10-29T04:52:49.393Z
Simone
<p>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?</p>

CC BY-SA 3.0
2014-10-28T01:02:25.693Z
There is a new paper in upcoming SODA'15 that may be relevant. See http://meetings.siam.org/sess/dsp_talk.cfm?p=68795
Chandra Chekuri
CC BY-SA 3.0
2014-10-29T20:42:26.243Z
@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)?
D.W.
CC BY-SA 3.0
2014-10-30T17:05:00.633Z
@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.
Chandra Chekuri
<machine-learning><lg.learning>
Theoretical results for random forests?
Aryeh
# Theoretical results for random forests?

(Asked by: username_0 on 2014-10-27)

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?

**Tags:** machine-learning, lg.learning

> **Comments:**
> **username_1**: There is a new paper in upcoming SODA'15 that may be relevant. See http://meetings.siam.org/sess/dsp_talk.cfm?p=68795  
> **username_2**: @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)?  
> **username_1**: @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.  

---

## 2 answers

### Answer by username_3 on 2014-10-31. Score: 5 | Accepted answer

Following username_4'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.


---

### Answer by username_4 on 2014-10-27. Score: 6

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](http://jmlr.org/proceedings/papers/v32/denil14.html)

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](http://nips.cc/Conferences/2013/Program/event.php?ID=3782)

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](http://arxiv.org/abs/1407.7502)


---

