Understanding Random Forests: From Theory to Practice

By Gilles Louppe. 2014

873 citations recorded by the source corpus.

Data analysis and machine learning have become an integrative part of the modern scientific methodology, offering automated procedures for the prediction of a phenomenon based on past observations, unraveling underlying patterns in data and providing insights about the problem. Yet, caution should avoid using machine learning as a black-box tool, but rather consider it as a methodology, with a rational thought process that is entirely dependent on the problem under study. In particular, the use of algorithms should ideally require a reasonable understanding of their mechanisms, properties and limitations, in order to better apprehend and interpret their results. Accordingly, the goal of this thesis is to provide an in-depth analysis of random forests, consistently calling into question each and every part of the algorithm, in order to shed new light on its learning capabilities, inner workings and interpretability. The first part of this work studies the induction of decision trees and the construction of ensembles of randomized trees, motivating their design and purpose whenever possible. Our contributions follow with an original complexity analysis of random forests, showing their good computational performance and scalability, along with an in-depth discussion of their implementation details, as contributed within Scikit-Learn. In the second part of this work, we analyse and discuss the interpretability of random forests in the eyes of variable importance measures. The core of our contributions rests in the theoretical characterization of the Mean Decrease of Impurity variable importance measure, from which we prove and derive some of its properties in the case of multiway totally randomized trees and in asymptotic conditions. In consequence of this work, our analysis demonstrates that variable importances [...].

View Paper: https://www.semanticscholar.org/paper/9131b527b0e8269b3b1554aecd356bab060c9b86

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A high-bias, low-variance introduction to Machine Learning for physicists (2018, unknown): “A full discussion of decision trees (and random forests) lies beyond the scope of this review and we refer readers to the extensive literature on these topics (Lim et al., 2000; Loh, 2011; Louppe, 2014).”
A general approach for predicting the behavior of the Supreme Court of the United States (2016, background): “For details of the implementation, interested readers are directed to the scikit-learn documentation [28] and [31] in particular.”
Adaptive Machine Learning for Credit Card Fraud Detection (2015, background): “Louppe [245] derives three bounds for the time complexity of RF training procedure: i) best O(qmNb log(2)Nb), ii) worst O(qmN2 b logNb) and iii) average O(qmNb log (2)Nb), where Nb is the number of boostrap samples in each tree, m the number of trees in the forest”
Empirical methods for the estimation of Southern Ocean CO 2 : support vector and random forest regression (2017, unknown): “The sampling with replacement means that each training observation has a ∼ 63% chance of being chosen at least once for a particular tree (Louppe, 2014) This subsampling provides estimates that are robust to outliers as these have a chance of being omitted in training .”
Explainable AI for Trees: From Local Explanations to Global Understanding (2019, background): “It has been previously shown through a connection with mutual information (which is consistent) that the Gain method becomes consistent in the limit of an infinite ensemble of totally random fully developed trees [40].”
Tree Space Prototypes: Another Look at Making Tree Ensembles Interpretable (2016, background): “The connection between random forests and kernel methods has been pointed out [33, 45] and proximity itself can be expressed as a kernel [35].”