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 nonparametric 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.

Introduction

In machine learning, a fundamental trade-off exists between scalability and the quality of uncertainty estimation. Decision Forests are widely used for their efficiency on large datasets, typically scaling at $O(N \log N)$, but they often produce overconfident predictions, failing to properly account for regions with sparse training data. Conversely, Gaussian Processes (GPs) provide principled uncertainty estimates but suffer from cubic scaling ($O(N^3)$), making them impractical for large-scale applications. This paper introduces an extension of Mondrian Forests (MFs) to the regression setting, bridging the gap between the speed of forests and the uncertainty quality of GPs.

Methodology

The core of the approach lies in the Mondrian Process, a label-independent method for partitioning feature space. Unlike standard decision trees that partition the entire feature space, Mondrian trees only commit to splits within the bounding box of observed data.

Illustration of a Mondrian tree partitioning and its corresponding tree structure.

The model incorporates a hierarchical Gaussian prior on the mean parameters of every node. This hierarchy ensures that child nodes remain similar to their parents while allowing deeper nodes to capture finer details. A key innovation is the "branching off" mechanism: during prediction, the model calculates the probability that a test point would have branched off the existing tree structure. If a point is far from training data, it is more likely to branch off near the root, causing the prediction to revert to the global prior and naturally increasing uncertainty. Inference is performed efficiently using Gaussian Belief Propagation, which scales linearly with the number of nodes ($O(N)$).

Experimental Evaluation

The authors evaluated MFs against standard Random Forests, Extremely Randomized Trees (ERT), and approximate GPs across various benchmarks, including a toy 2D dataset, a massive Flight Delay dataset (up to 5 million points), and Bayesian optimization tasks.

Comparison of predictive uncertainty across different forest models. MF uncertainty (b) shows smoother and more principled behavior compared to ERT (c) and Breiman-RF (d).

On the Flight Delay dataset, MFs achieved significantly better Negative Log Predictive Density (NLPD) than approximate GPs, indicating superior calibration. Furthermore, in Bayesian optimization benchmarks, the well-calibrated uncertainty of MFs allowed for more effective exploration of the search space, outperforming the standard SMAC algorithm which relies on traditional Random Forests.

Discussion and Conclusion

Mondrian Forests provide a powerful middle ground for large-scale regression. By restricting splits to the data's range, they naturally capture the increase in uncertainty as test points move away from training data. While label-independent splits can occasionally be distracted by irrelevant features, the ensemble nature of the forest mitigates this effect.

A current limitation is the use of constant predictors at leaf nodes, which prevents extrapolation of trends beyond the training label range. Future work may explore the use of linear regressors at the leaves to address this. Overall, MFs offer a statistically rigorous yet computationally efficient alternative for applications where uncertainty matters.

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 nonparametric 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