A Permutation-Augmented Sampler for DP Mixture Models
Abstract
We introduce a new inference algorithm for Dirichlet process mixture models. While Gibbs sampling and variational methods focus on local moves, the new algorithm makes more global moves. This is done by introducing a permutation of the data points as an auxiliary variable. The algorithm is a blocked sampler which alternates between sampling the clustering and sampling the permutation. The key to the efficiency of this approach is that it is possible to use dynamic programming to consider all exponentially many clusterings consistent with a given permutation. We also show that random pro jections can be used to effectively sample the permutation. The result is a stochastic hill-climbing algorithm that yields burn-in times significantly smaller than those of collapsed Gibbs sampling.
Cite
Text
Liang et al. "A Permutation-Augmented Sampler for DP Mixture Models." International Conference on Machine Learning, 2007. doi:10.1145/1273496.1273565Markdown
[Liang et al. "A Permutation-Augmented Sampler for DP Mixture Models." International Conference on Machine Learning, 2007.](https://mlanthology.org/icml/2007/liang2007icml-permutation/) doi:10.1145/1273496.1273565BibTeX
@inproceedings{liang2007icml-permutation,
title = {{A Permutation-Augmented Sampler for DP Mixture Models}},
author = {Liang, Percy and Jordan, Michael I. and Taskar, Benjamin},
booktitle = {International Conference on Machine Learning},
year = {2007},
pages = {545-552},
doi = {10.1145/1273496.1273565},
url = {https://mlanthology.org/icml/2007/liang2007icml-permutation/}
}