Binary Space Partitioning Forest

Xuhui Fan, Bin Li, Scott A. SissonAISTATS 2019 · OpenReview

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.

The temporal evolution of the Binary Space Partitioning process over time $\tau$.

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 four-step algorithm for high-dimensional BSP-Tree construction using 2D projections.

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 diamonds dataset, 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 like hatco and concrete.
  • 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

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. It ca...
BibTeX
@inproceedings{fan2019binary,
  author = {Xuhui Fan and Bin Li and Scott A. Sisson},
  title = {{Binary Space Partitioning Forest}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=ZeNfA9TvDnW},
}
Figure