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