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.
Introduction: The Online Learning Challenge
Random Forests (RFs) are a staple of the machine learning toolkit, prized for their accuracy and robustness. However, most standard implementations are "batch" algorithms—they need to see the entire dataset at once. While "online" versions exist for streaming data, they typically suffer from a significant performance gap compared to their batch counterparts.
In many real-world applications, data arrives in a stream (e.g., sensor logs, financial transactions). Re-training a standard Random Forest from scratch every time new data arrives is computationally ruinous. Existing online RFs attempt to solve this by updating trees leaf-by-leaf, but these methods often make "greedy" decisions early on based on limited data. As more data arrives, these early splits can become sub-optimal, and standard trees have no elegant way to "undo" or "re-route" them. Lakshminarayanan et al. introduce Mondrian Forests (MF), a novel class of random forests that can be trained incrementally while maintaining the predictive power of state-of-the-art batch methods.
Methodology: The Mondrian Process
The core innovation is the use of the Mondrian Process, a family of random hierarchical binary partitions. Unlike standard decision trees (like CART) which pick splits to maximize "purity" (e.g., Gini index), Mondrian Trees pick split dimensions and locations based solely on the geometry of the feature space.
Because splits don't consider labels, the model relies on a sophisticated labeling step. It uses Interpolated Kneser-Ney (IKN) smoothing—a technique borrowed from natural language processing—to smooth label estimates across the tree's hierarchy. This allows the model to maintain high accuracy even when splits are chosen independently of labels.
Incremental Growth and Projectivity
The "secret sauce" of Mondrian Forests is a property called projectivity. Due to the mathematical properties of Mondrian processes, the distribution of a tree restricted to a subset of data is the same as a tree grown only on that subset. In plain English: the order in which you see the data doesn't change the final model. This ensures that a model updated one data point at a time is mathematically identical to a model trained on the entire dataset at once.
Unlike traditional online trees that only grow at the leaves, Mondrian Trees can introduce new splits above existing ones or extend existing splits. This allows the tree to adapt its structure anywhere in the hierarchy as new data expands the known boundaries of the feature space, as illustrated in the step-by-step addition of data points above.
Experimental Results
The authors evaluated Mondrian Forests on four multi-class classification benchmarks: USPS (handwritten digits), Satimages (satellite pixels), Letter (English letters), and DNA (gene sequences). They compared MF against batch versions (Breiman-RF, Extremely Randomized Trees) and leading online versions (ORF-Saffari).
- Accuracy: On the USPS, Satimages, and Letter datasets, Mondrian Forests achieved accuracy nearly identical to state-of-the-art batch RFs and significantly outperformed existing online RFs.
- Speed: MF was consistently more than an order of magnitude faster (10x+) than re-trained batch RFs and other online methods.
- Data Efficiency: MF reached high accuracy much earlier in the data stream than other online methods, which often required multiple passes through the data to converge.
Discussion and Limitations
The most striking insight is that you can build an online learner that is statistically indistinguishable from a batch learner, removing the "online penalty" usually associated with streaming algorithms. Because the complexity scales with the depth of the tree, MFs are incredibly fast, processing $N$ points in $O(N \log N)$ time.
However, because Mondrian Trees split based on the range of features rather than label purity, they can be "distracted" by noise. If a dataset has many irrelevant dimensions (as seen in the DNA dataset), MF performance can drop. Future work may involve using feature selection or label-guided splits to mitigate this, as well as extending the framework to regression and more complex split types.
Summary updated