Mondrian Forests: Efficient Online Random Forests

Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh

TL;DR

Mondrian Forests (MF) introduce a novel class of random forests that can be trained incrementally (online) while maintaining the exact same statistical distribution as if they were trained on the entire dataset at once (batch). This approach achieves state-of-the-art accuracy comparable to batch random forests but is over an order of magnitude faster than existing online alternatives.

What Problem Does This Paper Address?

Random forests are a staple of machine learning due to their robustness and accuracy. However, most popular versions (like Breiman’s random forest) are "batch" algorithms—they need to see all the training data at once. In a world of streaming data, we need "online" algorithms that can update themselves as new examples arrive.

Existing online random forests have a major flaw: they usually require significantly more data than their batch counterparts to reach the same level of accuracy. Furthermore, the structure of an online-grown tree often depends on the order in which data arrives, leading to a "distributional shift" compared to batch trees. The authors sought a method that is computationally efficient, truly incremental, and statistically consistent with batch training.

Methods

The core innovation is the use of the Mondrian process, a stochastic process that defines a distribution over hierarchical partitions of space.

  1. Mondrian Trees: Unlike standard decision trees (like CART) which choose splits to maximize "label purity" (e.g., Information Gain), Mondrian trees choose splits based on the geometry of the data. Specifically, they sample split times and locations within the bounding box of the observed features.
  2. Projectivity: This is the "killer feature" of Mondrian processes. It ensures that a tree grown incrementally by adding points one-by-one has the same probability distribution as a tree grown from a static batch of the same points.
  3. Online Updates: When a new data point arrives, the algorithm can introduce a new split above an existing split (if the new point is far outside the current bounding box), extend an existing split, or split a leaf node.
  4. Label Smoothing: Because splits are label-independent, the authors use a hierarchical Bayesian model—specifically Hierarchical Normalized Stable Processes (HNSP)—to smooth predictions. This allows the forest to make intelligent guesses even in regions of the feature space with very few training examples.

Key Insights and Ideas

  • Splitting Without Labels: One of the most surprising insights is that you don't actually need to look at labels to pick good split points. As long as you have a robust label-smoothing mechanism (like HNSP), geometric splits are highly effective and much easier to update online.
  • The "Above" Split: Standard online trees only grow downwards. Mondrian trees are unique because they can "re-parent" an existing structure. If a new outlier appears, the algorithm can instantly create a new root or internal node above the current tree to account for it.
Sequential online updates in a Mondrian Tree, demonstrating the unique "above" split when new data points arrive.
  • Computational Efficiency: Re-training a batch random forest every time a new point arrives scales at $O(N^2 \log N)$. Mondrian Forests scale at $O(N \log N)$, making them viable for massive, high-velocity data streams.

Key Results

The authors evaluated Mondrian Forests on four standard multi-class classification benchmarks: usps (handwritten digits), satimages (satellite image pixels), letter (alphabet recognition), and dna (genetic sequence classification).

Performance comparison of Mondrian Forests (MF) against batch and online baselines across four datasets.
  • Accuracy: On the usps, satimages, and letter datasets, MF achieved accuracy nearly identical to state-of-the-art batch random forests (Breiman-RF and Extremely Randomized Trees).
  • Speed: MF was consistently more than an order of magnitude faster than re-trained batch versions and significantly faster than other online methods like ORF-Saffari.
  • Data Efficiency: MF outperformed other online methods (ORF-Saffari) when limited to a single pass over the data, proving it learns more from fewer examples.

Limitations and Future Work

  • Irrelevant Features: Because Mondrian trees split based on the range of features rather than label correlation, they can be "distracted" by noisy or irrelevant features. This was evident in the dna dataset, where MF performed worse than Breiman-RF unless the features were pre-filtered.
  • Axis-Aligned Splits: The current implementation uses axis-aligned splits (splitting on one dimension at a time). Extending this to "hyperplane splits" (diagonal cuts) could improve performance in complex spaces.
  • Scaling to High Dimensions: While rectangles are efficient, representing them explicitly in very high-dimensional spaces could become a bottleneck.
  • Beyond Classification: The paper focuses on classification, but the framework could be extended to regression and theoretical bias-variance analysis.

Summary updated

Abstract

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 re-trained batch random forests, while being more than an order of magnitude faster, thus representing a better computation vs accuracy tradeoff.
BibTeX
@inproceedings{lakshminarayanan2014mondrian,
  author = {Balaji Lakshminarayanan and Daniel M. Roy and Yee Whye Teh},
  title = {{Mondrian Forests: Efficient Online Random Forests}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=ryWMq8W_WH},
}
Figure