Source-linked AI summary
Mondrian Forests: Efficient Online Random Forests
Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh
TL;DR
Existing online random forests may require more training data than batch methods for comparable accuracy. This paper constructs Mondrian forests from Mondrian processes, enabling online updates that preserve the batch distribution while achieving competitive accuracy and substantially faster training. The method is limited by sensitivity to irrelevant features and computational cost that grows linearly with dimensionality.
Problem
Existing online random forests require more training data than batch counterparts to achieve comparable predictive performance, motivating efficient online random forests.
Method
Mondrian forests ensemble independently sampled Mondrian trees and incrementally extend each tree using Mondrian-process projectivity.
Results
Mondrian forests achieve competitive accuracy with batch random forests on the same data fraction and are at least an order of magnitude faster than retrained batch versions and ORF-Saffari.
Takeaways & Limitations
Online Mondrian forests match the batch tree distribution irrespective of observation order and provide a favorable computation-versus-accuracy tradeoff.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces Mondrian forests, a random-forest class built from Mondrian processes, for efficient online learning. It presents the approach and evaluates its empirical performance.
- Mondrian forests are a novel class of random forests whose individual tree structures are generated by Mondrian processes.
- The paper targets online learning while retaining the accuracy, scalability, and robustness associated with random forests.
- The approach is described at a high level before detailed treatment of tree structures, label models, incremental updates, and predictions.
- Empirical performance is demonstrated in Section 7, followed by a discussion of future work in Section 8.
2 Approach
Mondrian forests average predictions from independently sampled Mondrian trees and update those trees online using Mondrian-process properties. The update preserves the batch tree distribution while scaling with tree depth.
- A Mondrian forest samples independent Mondrian trees, each producing a class-label distribution, and averages their predictions.
- As the number of trees increases, the ensemble average converges to the expected prediction under the Mondrian-tree distribution.
- At each online iteration, a tree is extended to incorporate the next labeled example while preserving its existing structure on earlier data.
- The incrementally trained tree has the same distribution as a batch-trained tree on the accumulated data, regardless of observation order.
- Online updates can be sampled efficiently because their complexity scales with tree depth, typically logarithmically in the number of examples.
- The approach defines the Mondrian-tree distribution, label distribution, and update distribution used for incremental training and prediction.
3 Mondrian trees
Mondrian trees restrict Mondrian-process partitions to observed data and augment decision trees with split times, a lifetime budget, and data-bounded splits. Their projectivity enables consistent incremental growth.
- Decision-tree structure: A decision tree hierarchically partitions the input space into blocks and assigns a label-prediction rule to test points.
- Decision-tree structure: Each internal decision-tree node splits its block by dimension δj and threshold ξj, producing left and right child blocks.
- Mondrian-process structure: Mondrian processes are random hierarchical binary partitions whose later-time partitions refine those at earlier times.
- Mondrian-process structure: Mondrian trees represent Mondrian-process partitions only on finite observed data, making the random structure representable for training.
- Mondrian-tree construction: The sampling procedure draws split times from exponential distributions and, when splitting occurs, samples a dimension and location from the block’s uniform split distribution.
- Mondrian-tree construction: Mondrian trees associate every node with a split time, use lifetime λ to control splitting, and commit splits only within the training-data extent of each block.
- Incremental construction: Projectivity permits a tree on D1:N to be extended consistently when DN+1 arrives by sampling from the conditional distribution on the enlarged dataset.
4 Label distribution: model, hierarchical prior, and predictive posterior
The label model smooths leaf predictions using a hierarchical Bayesian structure in which node label distributions resemble their parents. Predictions are obtained by marginalizing these distributions.
- The predictive label distribution at a test point is based on its leaf and is smoothed using information from nearby nodes through a hierarchical Bayesian model.
- The model assumes labels within each block are conditionally independent of features given the tree structure.
- Each node has a categorical label distribution, and a test point receives the distribution associated with its unique leaf node.
- A hierarchical normalized stable process prior links each node’s label distribution to its parent’s distribution.
- The base distribution is uniform over the K labels, while the discount parameter controls variation around the base distribution.
- The predictive distribution is obtained by integrating over node label distributions using posterior inference.
- Exact inference is intractable, so the method uses interpolated Kneser-Ney smoothing, whose online update complexity is linear in tree depth.
5 Online training and prediction
Mondrian trees support incremental updates that preserve consistency with the existing partition while allowing new splits, split extensions, and leaf splitting. Predictions for external points are obtained by analytically averaging over possible tree extensions.
- Incremental updates: Online updates can introduce a split above an existing split, extend a split's extent, or split an existing leaf.These three operations distinguish Mondrian updates from standard online decision-tree procedures.
- Incremental updates: A new point is routed recursively through the tree, updating node extents and continuing into the child containing the point.The update algorithm traverses from the root and recurses until the relevant leaf or insertion location is reached.
- Incremental updates: Mondrian blocks pause when all labels in a leaf are identical and resume splitting when more than one unique label appears.This makes the implementation comparable to random-forest procedures that stop splitting pure leaves.
- Incremental updates: New split timing is sampled from an exponential distribution whose rate depends on the additional extent outside the current block.If the sampled time precedes the existing split time, a new split is introduced while preserving the existing partition structure.
- Prediction: For a test point outside the tree, prediction averages analytically over every possible extension, with computational complexity linear in tree depth.A single sampled extension could be overconfident, motivating integration over possible extensions.
6 Related work
The paper situates Mondrian forests among randomized batch and online forests, emphasizing that existing online methods update candidate splits locally and typically require additional safeguards or passes through data.
- Random-forest variants: Random forests decorrelate randomized trees primarily through bagging or random subsampling of candidate splits.Classic tree induction otherwise selects splits greedily using criteria such as information gain.
- Random-forest variants: Breiman-RF uses bagging and feature subsampling, whereas ERT randomly selects split locations and does not use bagging.ERT considers random locations for selected features rather than all possible locations along a dimension.
- Online forests: Existing online random forests maintain candidate splits and quality scores at each leaf, updating scores only where new data arrive.They introduce hyperparameters such as minimum leaf size to reduce the risk of selecting noisy splits.
- Online forests: Prior incremental-tree methods were not generalized to online random forests, and the paper therefore compares Mondrian forests with online and batch forest variants instead.The authors omit single-tree comparisons because random forests are known to outperform individual decision trees.
- Bayesian tree models: Bayesian decision-tree models define distributions over trees, whereas Mondrian forests perform ensemble model combination rather than Bayesian model averaging.The paper also notes that typical Bayesian tree distributions lack the Mondrian process's projectivity property.
7 Empirical evaluation
Experiments compare Mondrian forests with online and batch random forests across training-data fractions and training time. Mondrian forests match batch accuracy closely on several datasets while offering substantially faster training, with weaker performance under irrelevant features.
- Experimental design: The evaluation compares MF and ORF-Saffari with Breiman-RF and three ERT variants across 100 training mini-batches.Performance is measured against both fraction of training data and training time.
- Accuracy: MF achieves accuracy very close to batch RF variants on usps, satimages, and letter using the same fraction of training data.It significantly outperforms ORF-Saffari at the same data fraction.
- Training time: MF is at least an order of magnitude faster than retrained batch forests and ORF-Saffari on usps, satimages, and letter.The comparison uses test accuracy versus training time, while ORF-Saffari includes additional passes through the data.
- Training time: Under balanced-tree assumptions, MF costs O(N log N), compared with O(N^2 log N) for retrained batch random forests.The reported average forest depth scales as O(log N).
- Feature relevance: With irrelevant features, label-independent split selection performs worse on dna, while filtering to relevant attributes significantly improves MF and ERT-1.The comparison includes MF† and ERT-1† trained on the most relevant 60 of 180 attributes.
8 Discussion
The discussion presents Mondrian forests as efficient incremental random forests with batch-comparable accuracy and strong online advantages, while identifying limitations for irrelevant or high-dimensional features.
- Conclusions: Mondrian forests can be trained incrementally in an efficient manner.This is the paper's central methodological contribution.
- Conclusions: MF outperforms existing online random forests in training time and in the number of instances needed to reach a target test accuracy.It also achieves competitive accuracy with batch forests trained on the same data fraction.
- Limitations: MF is unable to handle many irrelevant features because its splits are chosen independently of labels.The paper points to label-guided tree methods as one possible direction for addressing this issue.
- Limitations: MF computational complexity is linear in the number of dimensions because tree rectangles are represented explicitly.The authors identify high-dimensional data as a potentially expensive setting and defer addressing it to future work.
- Future work: Future extensions include regression, theoretical bias-variance analysis, and hyperplane rather than axis-aligned splits.These are presented as possible directions for extending the framework.
A Posterior inference and prediction using the HNSP
The HNSP uses hierarchical Bayesian label distributions on Mondrian-tree nodes, with approximate posterior inference and predictive probabilities computed recursively. Online updates modify counts along affected tree paths, while predictions average over possible test-point branch locations and across trees.
- Hierarchical Bayesian inference: HNSP posterior inference is a special case of hierarchical PYP inference, adapted here to multinomial likelihoods.The paper sketches the batch and online procedures before describing predictive posterior computation.
- Hierarchical Bayesian inference: IKN smoothing approximates inference by limiting each restaurant's tables serving a particular dish to one.Counts and table assignments are computed in a bottom-up pass through the tree.
- Online inference: Adding one labeled example updates posterior counts only along the path from its leaf to the root, stopping when an unchanged table assignment is reached.This procedure is summarized by the online count-update algorithms.
- Predictive inference: Predictive probabilities are computed recursively from node counts, table assignments, discounts, and parent distributions in a top-down pass.A discount near 1 emphasizes the parent distribution, whereas a discount near 0 emphasizes local counts.
- Prediction: For a test point outside a leaf block, the tree averages predictions over possible branch-off locations using truncated-exponential split-time expectations.If the point lies inside an existing leaf block, its prediction is based directly on that leaf's posterior mean.
- Prediction: A Mondrian forest averages the predictive probability distributions produced by its M constituent trees.Each tree's prediction accounts for whether and where the test point separates from the existing tree.
C Computational complexity
Mondrian trees support incremental processing with costs tied to tree depth, while repeatedly retraining batch random forests incurs substantially greater cumulative complexity.
- Incremental complexity: Processing the nth example in a balanced Mondrian tree costs at most O(log n), including insertion and bottom-up posterior-count updates.Forest computation multiplies this cost by M but can be parallelized across trees.
- Incremental complexity: O(N log N) is the large-N overall cost for processing N examples in a Mondrian tree.This follows from summing logarithmic per-example costs and applying Stirling's approximation.
- Batch comparison: Offline random forests and extremely randomized trees have expected complexity O(n log n) for n training points.This is the per-training-set complexity cited for the batch methods.
E Depth of trees
Measured average tree depth in Mondrian forests suggests logarithmic scaling with the number of training examples rather than linear scaling.
- Depth measurement: Average leaf depth, weighted by the fraction of data points at each leaf, was measured across datasets.The reported values include standard deviations and use the experimental setup described in Section 7.
- Depth scaling: The observed forest depth scales as log N rather than N.This empirical pattern supports the logarithmic depth assumption used in the complexity analysis.
F Comparison to dynamic trees
Compared with dynamic trees, Mondrian forests perform better on most reported datasets and retain the benefits of ensemble model combination. On dna, feature-selected MF reaches similar accuracy to dynamic trees.
- Model comparison: Dynamic trees approximate the Bayesian posterior over decision trees with weighted particles, unlike MF's ensemble model combination.The distinction matters because dynamic trees' posterior can converge toward a single tree, whereas MF continues averaging multiple trees.
- Experimental setup: The experiment uses 100 dynamic-tree particles and two passes, comparing them with MF and other random-forest variants.All methods other than dynamic trees use the same performance values as in Fig. 3.
- Experimental setup: Figure 4 plots test accuracy against fraction of training data for multiple datasets.The y-axis is test accuracy in both rows, and the setup matches Fig. 3.
- Results: MF achieves significantly higher test accuracy than dynamic trees on usps, satimages, and letter.This is the reported cross-dataset comparison in Figure 4.
- Results: On dna, dynamic trees outperform MF, while MF† with feature selection achieves similar performance to dynamic trees.The authors associate this result with the usefulness of labels for guiding splits.
- Results: All batch random-forest methods outperform dynamic trees, suggesting that model combination helps on these real-world datasets.The paper interprets this pattern as evidence that a single decision tree is insufficient for these datasets.