Hidden Markov Pólya Trees for High-Dimensional Distributions

Abstract

The Pólya tree (PT) process is a general-purpose Bayesian nonparametric model that has found wide application in a range of inference problems. It has a simple analytic form and the posterior computation boils down to beta-binomial conjugate updates along a partition tree over the sample space. Recent development in PT models shows that performance of these models can be substantially improved by (i) allowing the partition tree to adapt to the structure of the underlying distributions and (ii) incorporating latent state variables that characterize local features of the underlying distributions. However, important limitations of the PT remain, including (i) the sensitivity in the posterior inference with respect to the choice of the partition tree, and (ii) the lack of scalability with respect to dimensionality of the sample space. We consider a modeling strategy for PT models that incorporates a flexible prior on the partition tree along with latent states with Markov dependency. We introduce a hybrid algorithm combining sequential Monte Carlo (SMC) and recursive message passing for posterior sampling that can scale up to 100 dimensions. While our description of the algorithm assumes a single computer environment, it has the potential to be implemented on distributed systems to further enhance the scalability. Moreover, we investigate the large sample properties of the tree structures and latent states under the posterior model. We carry out extensive numerical experiments in density estimation and two-group comparison, which show that flexible partitioning can substantially improve the performance of PT models in both inference tasks. We demonstrate an application to a mass cytometry dataset with 19 dimensions and over 200,000 observations. Supplementary Materials for this article are available online.

Keywords:

• Bayesian nonparametrics
• Latent variable models
• Multi-scale inference
• Multivariate analysis
• Recursive partitioning

Supplementary Materials

Supplementary Materials for this article are available online. Supplementary Materials A provides details on the posterior computation. Supplementary Materials B describes the spike-and-slab prior used for the location variable. The details on density estimation with APT model and two-sample comparison with the MRS model can be found in Supplementary Materials C and D, respectively. All proofs are included in Supplementary Materials E. Supplementary Materials F details the proof of consistency for the MRS model with the flexible partitioning. Supplementary Materials G presents the result of an additional experiment for evaluating the performance of our HMPT model in density estimation. The details of the numerical experiments are provided in Supplementary Materials H, and the additional figures can be found in Supplementary Materials I.

Software and Data Availability Statement

An R package for our method is available at https://github.com/MaStatLab/HMPT and the code for the examples is at https://github.com/MaStatLab/HMPT_experiments.

Acknowledgments

We thank the associate editor and the referees for very helpful comments. LM’s research is partly supported by NSF grants DMS-2013930 and DMS-1749789. NA is supported by a fellowship from the Nakajima Foundation. The authors report there are no competing interests to declare.

Additional information

Funding

We thank the associate editor and the referees for very helpful comments. LM’s research is partly supported by NSF grants DMS-2013930 and DMS-1749789. NA is supported by a fellowship from the Nakajima Foundation. The authors report there are no competing interests to declare.