Mondrian Forests: Efficient Online Random Forests

By Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh. 2014

235 citations recorded by the source corpus.

Ensembles of randomized decision trees, usually referred to as random forests, are widely used for classification and regression tasks in machine learning and statistics. Random forests achieve competitive predictive performance and are computationally efficient to train and test, making them excellent candidates for real-world prediction tasks. The most popular random forest variants (such as Breiman's random forest and extremely randomized trees) operate on batches of training data. Online methods are now in greater demand. Existing online random forests, however, require more training data than their batch counterpart to achieve comparable predictive performance. In this work, we use Mondrian processes (Roy and Teh, 2009) to construct ensembles of random decision trees we call Mondrian forests. Mondrian forests can be grown in an incremental/online fashion and remarkably, the distribution of online Mondrian forests is the same as that of batch Mondrian forests. Mondrian forests achieve competitive predictive performance comparable with existing online random forests and periodically retrained batch random forests, while being more than an order of magnitude faster, thus representing a better computation vs accuracy tradeoff.

Subfields: Artificial Intelligence

How researchers see this paper

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

In Artificial Intelligence

Citations in the corpus

Kernel-Based Just-In-Time Learning for Passing Expectation Propagation Messages (2015, background): “A natural way to specify f is as code in a probabilistic program.”
Scaling Memory-Augmented Neural Networks with Sparse Reads and Writes (2016, positive): “Recent work in tree ensemble models, such as Mondrian forests [13], show promising results in maintaining balanced hierarchical set coverage in the online setting.”
Efficient Non-greedy Optimization of Decision Trees (2015, background): “The work in [15] proposes a means for training decision forests in an online setting by incrementally extending the trees as new data points are added.”
CILEA-NET: Curriculum-Based Incremental Learning Framework for Remote Sensing Image Classification (2021, background): “In [16], a random-forest-based approach was introduced, which grows hierarchically when a new set of data is encountered.”
Incremental on-line learning: A review and comparison of state of the art algorithms (2018, methodology): “This method has been lately applied in [34, 35].”
Mondrian Forests for Large-Scale Regression when Uncertainty Matters (2015, methodology): “[16] introduced Mondrian forests (MFs) for classification tasks.”
A random forest guided tour (2015, background): “Random forests have been extended to the online framework in several ways (Saffari et al. 2009; Denil et al. 2013; Lakshminarayanan et al. 2014).”
Deep learning for limit order books (2016, unknown): “Mondrian forests are a type of random forest which can be efficiently trained online; see Lakshminarayanan et al. (2014).”
Incremental learning algorithms and applications (2016, background): “Interestingly, there do exist tree classifiers which result is entirely invariant to the ordering of the training data, but at the price of unlimited resources [90].”
Ensemble learning for data stream analysis: A survey (2017, methodology): “Bagging-based OzaBag [139] Online Bagging ASHT [20] Ensemble of adaptive-size Hoeffding trees LevBag [18] Leveraging Bagging with increased resampling and output detection codes ORF [155, 43] Online Random Forest MF [113] Online Mondrian Forest”
Bayesian optimization for conditional hyperparameter spaces (2017, methodology): “Secondly, we propose to use an already existing kernel, the Laplace kernel, which has strong ties to random and Mondrian forests [12, 13].”
A survey on data preprocessing for data stream mining: Current status and future directions (2017, methodology): “However, there exist a plethora of methods modified to provide efficient online mode of operation [33, 34].”
On the asymptotics of random forests (2014, methodology): “For instance, Geurts et al. (2006) modiﬁed the procedure to reduce calculation time, while other authors extended the procedure to online settings (Denil et al., 2013; Lakshminarayanan et al., 2014, and the reference therein).”