Abstract
The Binary Space Partitioning (BSP)-Tree process is proposed to produce flexible 2-D partition structures which are originally used as a Bayesian nonparametric prior for relational modelling. This work extends the BSP-Tree to high-dimensional spaces, enabling its use in complex regression tasks through the "BSP-Forest" ensemble. By restricting cutting hyperplanes to 2D projections, the model captures complex feature dependencies with greater parsimony than traditional axis-aligned methods.
Introduction
Decision trees and random forests are staples of machine learning, typically relying on axis-aligned cuts to partition feature space. While computationally efficient, these orthogonal splits often struggle to model datasets with strong feature correlations, requiring deep trees to approximate simple diagonal boundaries. The Binary Space Partitioning (BSP)-Tree process offers a more flexible alternative by allowing angled cuts. A key advantage of the BSP-Tree is its self-consistency—the property that the probability distribution of partitions remains invariant when restricted to a sub-region. However, the original BSP-Tree was limited to 2D spaces due to the intractability of calculating probabilities for multidimensional cutting hyperplanes.
The BSP-Tree Process
The BSP-Tree process generates partitions over a continuous time parameter $\tau$. As time progresses, new cutting lines are sampled, further subdividing existing cells.
This process creates a hierarchical structure where each split is an angled line (in 2D), providing significantly more flexibility than traditional axis-aligned methods like the Mondrian process. Because it is self-consistent, the process can be defined on an infinite domain, and any finite observation is a valid restriction of that process.
High-Dimensional Extension: The BSP-Forest
To overcome the dimensionality barrier, the authors introduce a $d$-dimensional extension of the BSP-Tree. Instead of attempting to sample from the space of all possible $d$-dimensional hyperplanes, the algorithm randomly selects a pair of dimensions and performs a 2D angled cut on their projection. This hyperplane remains parallel to the other $d-2$ dimensions, ensuring mathematical tractability while preserving self-consistency.
The "BSP-Forest" is an ensemble of these trees, implemented as a Bayesian sum-of-trees model. To facilitate efficient inference, the authors utilize a Conditional-Sequential Monte Carlo (C-SMC) sampler. Leveraging the self-consistency property, they apply a "convex hull trick": rather than considering cuts across the entire bounding box of a node, they restrict candidate hyperplanes to the convex hull of the actual data points. This drastically reduces the search space in high-dimensional settings.
Key Results
The BSP-Forest demonstrates superior performance across several benchmarks:
- Accuracy: On the UCI
diamondsdataset, the BSP-Forest achieved a Root Mean Absolute Error (RMAE) of $0.005 \pm 0.0003$, significantly outperforming the Mondrian Forest ($0.013 \pm 0.004$). Similar gains were observed across other datasets likehatcoandconcrete. - Parsimony: Due to the efficiency of angled cuts, BSP-Forests typically require fewer splits (shallower trees) than axis-aligned forests to achieve comparable accuracy.
- Feature Selection: In tests using Friedman’s function, the model naturally prioritized the five informative dimensions over noise dimensions, demonstrating an inherent capability for feature selection without manual prompting.
Conclusion
By extending the BSP-Tree process to high dimensions via 2D projections, the authors have created a powerful new tool for Bayesian regression. The BSP-Forest combines the theoretical elegance of self-consistent processes with the practical power of angled partitions. While the $O(d^2)$ complexity of split candidates is higher than standard methods, the resulting gains in accuracy and model parsimony make it a compelling choice for complex, correlated datasets.
Summary updated