Incremental Tree-Based Inference with Dependent Normalized Random Measures

Juho Lee, Seungjin ChoiAISTATS 2014 · OpenReview

Abstract

Normalized random measures (NRMs) form a broad class of discrete random measures that are used as priors for Bayesian nonparametric models. Dependent normalized random measures (DNRMs) introduce dependencies between these measures to model non-exchangeable data, such as temporal sequences. However, inference in these models is computationally demanding, typically requiring slow Markov Chain Monte Carlo (MCMC) methods. We present Incremental Bayesian Hierarchical Clustering (IBHC), a deterministic, tree-based inference method that enables efficient online clustering. By restricting the search space to tree-consistent partitions and employing a sequential insertion algorithm, IBHC achieves significant speedups over MCMC while maintaining high accuracy on both synthetic and real-world video segmentation tasks.

Introduction

In Bayesian statistics, NRMs like the Dirichlet Process are standard priors for clustering. These models typically assume exchangeability, meaning the order of observations does not affect the joint distribution. However, real-world data—such as video frames or sensor readings—are often dependent on time or location. While Dependent NRMs (DNRMs) offer the flexibility to model these dependencies, they are notoriously difficult to compute. Traditional MCMC sampling is slow, non-scalable, and unsuitable for streaming data. This paper addresses these challenges by introducing a fast, incremental inference algorithm that provides a deterministic approximation of the posterior, bridging the gap between model complexity and computational feasibility.

Methodology

Mixed Normalized Random Measures (MNRMs)

The authors extend Bayesian Hierarchical Clustering (BHC) to work with Mixed Normalized Random Measures (MNRMs). This adaptation allows the model to account for data points originating from a mixture of different underlying random measures, which is essential for modeling non-exchangeable data across varying time steps.

The Seq-Insert Algorithm

To achieve online processing, the paper introduces the Seq-Insert algorithm. Unlike the standard $O(n^2)$ batch process of BHC, IBHC processes each new data point $x_i$ as it arrives by traversing the existing tree structure and identifying the most probable insertion point.

The Seq-Insert algorithm identifies the optimal position for new data points within the existing tree structure, evaluating multiple insertion cases.

As illustrated in the figure, the algorithm evaluates whether a new point should become a sibling to an existing node or form a new leaf. This local update mechanism significantly reduces computational complexity while allowing the model to adapt dynamically as hyperparameters are tuned alongside the structure. This restriction to tree-consistent partitions provides a tight lower bound on the marginal likelihood that is much easier to compute than the full posterior.

Experiments and Results

Synthetic Benchmarks

The model was tested on a 2D time-varying Gaussian mixture model with 10,000 data points across 15 time steps. IBHC demonstrated remarkable efficiency, converging in just 36 seconds, compared to over 10,600 seconds (nearly 3 hours) for a standard Gibbs sampler to reach a similar log-likelihood.

Clustering results on a synthetic dataset, showing the algorithm's ability to accurately recover complex, time-varying cluster structures.

Video Segmentation

On the Chen’s Video Benchmark, IBHC was used to segment video frames by treating pixels as "supervoxels" with 60-bin color histograms. The method achieved the highest 2D and 3D segmentation accuracy among all tested methods, outperforming established offline algorithms like SWA and GBH. This demonstrates that the tree-based approximation is not only fast but also highly competitive in terms of accuracy for real-world computer vision tasks.

Discussion and Conclusion

IBHC provides a scalable alternative to MCMC for complex dependent Bayesian models. By focusing on tree-consistent partitions, the algorithm provides a tractable approximation that is computationally efficient. While the method shows some limitations in fine-grained temporal boundary recall compared to specialized offline methods, its speed and accuracy make it a powerful tool for online clustering and video analysis. Future work will focus on refining tree-splitting criteria and incorporating more sophisticated spatial-temporal constraints to improve boundary preservation in dynamic environments.

Summary updated

Abstract

Normalized random measures (NRMs) form a broad class of discrete random measures that are used as priors for Bayesian nonparametric models. Dependent normalized random measures (DNRMs) introduce de...
BibTeX
@inproceedings{lee2014incremental,
  author = {Juho Lee and Seungjin Choi},
  title = {{Incremental Tree-Based Inference with Dependent Normalized Random Measures}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=PGZ1-xSlOOf},
}
Figure