Self-Consistent Bayesian Nonparametric Space Partitions

This direction is merged into another direction: spatial self-consistency. Its last version stays readable and citable here.

Version 1 of 114 papers27 conceptsfrozen 2026-10-04

In machine learning, we often need to divide a high-dimensional space into regions of homogeneity—clusters where data points behave similarly. While traditional decision trees and random forests do this heuristically, Bayesian Nonparametric Space Partition (BNSP) models treat the partition itself as a random variable.

The goal is to define a generative process that can divide space into an arbitrary number of blocks, allowing the complexity of the model to grow naturally as more data arrives.

The Core Requirement: Self-Consistency

The defining challenge of BNSP models is maintaining self-consistency. As explained by Xuhui Fan and Bin Li in Bayesian Nonparametric Space Partitions: A Survey, a self-consistent process ensures that the distribution of a partition restricted to a small "window" of space is identical to the distribution of a partition generated directly on that window.

Think of this like a map: if you draw a map of a whole country and then zoom into a single city, the streets in that city should look the same as if you had only drawn the city map to begin with. This property is mathematically grounded in the Kolmogorov extension theorem. It is crucial for two reasons:

  1. Online Learning: You can extend a partition to accommodate new data points outside the original range without recomputing the entire structure.
  2. Infinite Domains: It allows models to be defined on unbounded spaces, as the local structure remains valid regardless of the global scale.

From Axis-Aligned to Oblique Cuts

The most famous example of a self-consistent partition is the Mondrian Process, which uses axis-aligned cuts (like a Piet Mondrian painting). However, real-world data often has diagonal correlations that axis-aligned cuts struggle to capture efficiently.

To solve this, Xuhui Fan and colleagues introduced The Binary Space Partitioning-Tree Process. This model allows for oblique (diagonal) cuts. The breakthrough here was proving that geometric flexibility does not have to sacrifice self-consistency. By ensuring the "measure" (the probability) of a potential cut line is proportional to the perimeter of the blocks, the model remains distributionally invariant across different domains.

Similarly, Shufei Ge and Yee Whye Teh developed Random Tessellation Forests. They demonstrated that by using stable STIT (Substitution Invariant Tessellation) processes, one can create Bayesian decision trees that split along arbitrary angles while remaining mathematically rigorous.

Alternative Geometries: Bounding Boxes and Permutations

While "cutting" the space is the standard approach, it can create unnecessary complexity in sparse regions. The Rectangular Bounding Process (RBP) by Xuhui Fan and Scott A Sisson takes a different path. Instead of partitioning the entire universe, it encloses data points within bounding boxes. This creates a more parsimonious model that only "cares" about the regions where data actually exists, while still satisfying the self-consistency required for streaming data.

Another innovative perspective comes from Masahiro Nakano and Akisato Kimura in the Baxter Permutation Process. They leverage a mathematical correspondence between permutations and "floorplans" (rectangular partitions). By placing a prior on permutations, they can represent complex relational data structures more simply than traditional hierarchical models.

Why It Works: Scale and Invariance

The success of these models often hinges on scale invariance. As Marcus Hutter noted in Exact Non-Parametric Bayesian Inference on Infinite Trees, applying uniform prior parameters across every level of a tree structure ensures the model's behavior is independent of the data's scale.

When a model is scale-invariant and self-consistent, it becomes a powerful tool for density estimation and clustering. It doesn't matter if you are looking at a handful of points in a unit square or millions of points across an infinite plane; the underlying logic of how the space is divided remains the same. This theoretical grounding allows BNSP models to bridge the gap between flexible, "infinite" nonparametrics and the practical requirements of efficient, online computation.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_self_consistent_bayesian_nonparametric_s_f2227753,
  title = {Self-Consistent Bayesian Nonparametric Space Partitions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/self-consistent-bayesian-nonparametric-space-partitions/rdr_f2227753d3964409aae0db5750b42bba},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_self_consistent_bayesian_nonparametric_s_f2227753_v1,
  title = {Self-Consistent Bayesian Nonparametric Space Partitions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/self-consistent-bayesian-nonparametric-space-partitions/rdr_f2227753d3964409aae0db5750b42bba/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}