Mondrian Forests for Large-Scale Regression when Uncertainty Matters

Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh

Abstract

Many real-world regression problems demand a measure of the uncertainty associated with each prediction. Standard decision forests deliver efficient state-of-the-art predictive performance, but high-quality uncertainty estimates are lacking. Gaussian processes (GPs) deliver uncertainty estimates, but scaling GPs to large-scale data sets comes at the cost of approximating the uncertainty estimates. We extend Mondrian forests, first proposed by Lakshminarayanan et al. (2014) for classification problems, to the large-scale non-parametric regression setting. Using a novel hierarchical Gaussian prior that dovetails with the Mondrian forest framework, we obtain principled uncertainty estimates, while still retaining the computational advantages of decision forests. Through a combination of illustrative examples, real-world large-scale datasets, and Bayesian optimization benchmarks, we demonstrate that Mondrian forests outperform approximate GPs on large-scale regression tasks and deliver better-calibrated uncertainty assessments than decision-forest-based methods.

1. Introduction

In modern machine learning, point predictions are often insufficient. High-stakes applications, such as safety-critical systems or Bayesian optimization, require models that can quantify their own uncertainty. Historically, researchers have faced a stark trade-off between the high-quality uncertainty estimates of Gaussian Processes (GPs) and the computational scalability of Decision Forests. While GPs provide excellent "error bars," their $O(N^3)$ complexity makes them prohibitive for large datasets. Conversely, standard Random Forests scale efficiently to millions of points but rely on heuristic uncertainty estimates that are frequently overconfident, particularly in regions far from the training data.

This paper introduces an extension of Mondrian Forests (MFs) to the regression setting, bridging this gap by providing principled, GP-like uncertainty within a computationally efficient forest framework.

2. Methodology: Mondrian Trees and Hierarchical Priors

The core innovation of this work lies in the integration of Mondrian Trees with a novel hierarchical Gaussian prior. Unlike standard decision trees that partition the entire feature space based on labels, Mondrian trees partition space independently of labels, committing to splits only within the range of observed data.

Mondrian tree structure and hierarchical partitioning of the feature space.

2.1 Hierarchical Gaussian Prior

The authors place a Gaussian prior over the mean parameters of every node in the tree. A child node’s mean is centered around its parent’s mean, allowing for efficient hierarchical smoothing. Using Gaussian belief propagation, the posterior distribution can be computed in $O(N)$ time per tree.

2.2 The Branching Off Mechanism

A critical feature of MFs is the "branching off" mechanism. When predicting for a new test point, the model calculates the probability that the point would have branched off the existing tree structure at any level. If a point is located in a region far from the training data, it is statistically more likely to branch off early, causing the prediction to shrink toward the global prior. This mathematical property ensures that uncertainty naturally increases in unexplored regions of the feature space—a property lacking in traditional Extremely Randomized Trees (ERT).

3. Experimental Evaluation

The model was evaluated across toy datasets, massive real-world datasets, and Bayesian optimization benchmarks.

3.1 Large-Scale Scalability

On the Flight Delay dataset, which contains up to 5 million records, MFs demonstrated superior scalability and predictive performance. MFs achieved a significantly better Negative Log Predictive Density (NLPD) than state-of-the-art approximate GPs (such as rBCM), indicating that the MF's probability distribution is a superior fit for large-scale real-world data.

3.2 Uncertainty Calibration

One of the most significant findings is the superior calibration of MFs. Reliability diagrams show that MFs stay much closer to the ideal calibration line than Breiman’s Random Forests or ERTs, which tend to be overconfident.

Log of predictive variance for Mondrian Forest (MF) uncertainty, demonstrating principled behavior in unexplored regions.

As shown in the predictive variance plots, MFs provide a smooth and principled increase in uncertainty as test points move away from the training distribution, whereas standard forest methods often fail to capture this variance correctly.

4. Discussion and Conclusion

Mondrian Forests represent a significant step forward for large-scale regression where uncertainty matters. By leveraging label-independent splitting and hierarchical priors, they offer the speed of forests ($O(N \log N)$ training complexity) with the principled uncertainty of GPs.

While MFs are highly effective, they do face limitations. Like other forest-based models using constant leaf predictors, they struggle with extrapolation outside the observed $y$-range. Additionally, their label-independent splitting can make them sensitive to irrelevant features in high-dimensional settings. Future work may address these by incorporating more complex regressors, such as linear models, at the leaf nodes to improve extrapolation capabilities.

Summary updated

Abstract

Many real-world regression problems demand a measure of the uncertainty associated with each prediction. Standard decision forests deliver efficient state-of-the-art predictive performance, but high-quality uncertainty estimates are lacking. Gaussian processes (GPs) deliver uncertainty estimates, but scaling GPs to large-scale data sets comes at the cost of approximating the uncertainty estimates. We extend Mondrian forests, first proposed by Lakshminarayanan et al. (2014) for classification problems, to the large-scale non-parametric regression setting. Using a novel hierarchical Gaussian prior that dovetails with the Mondrian forest framework, we obtain principled uncertainty estimates, while still retaining the computational advantages of decision forests. Through a combination of illustrative examples, real-world large-scale datasets, and Bayesian optimization benchmarks, we demonstrate that Mondrian forests outperform approximate GPs on large-scale regression tasks and deliver better-calibrated uncertainty assessments than decision-forest-based methods.
BibTeX
@inproceedings{lakshminarayanan2016mondrian,
  author = {Balaji Lakshminarayanan and Daniel M. Roy and Yee Whye Teh},
  title = {{Mondrian Forests for Large-Scale Regression when Uncertainty Matters}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=HW4baNT0Llq},
}
Figure