Message passing algorithms for Dirichlet diffusion trees

We demonstrate efficient approximate infer-ence for the Dirichlet Diffusion Tree (Neal, 2003), a Bayesian nonparametric prior over tree structures. Although DDTs provide a powerful and elegant approach for modeling hierarchies they haven’t seen much use to date. One problem is the computational cost of MCMC inference. We provide the first deterministic approximate inference methods for DDT models and show excellent perfor-mance compared to the MCMC alternative. We present message passing algorithms to ap-proximate the Bayesian model evidence for a specific tree. This is used to drive se-quential tree building and greedy search to find optimal tree structures, corresponding to hierarchical clusterings of the data. We demonstrate appropriate observation models for continuous and binary data. The empiri-cal performance of our method is very close to the computationally expensive MCMC alter-native on a density estimation problem, and significantly outperforms kernel density esti-mators. 1