More Web Proxy on the site http://driver.im/

Article

A permutation-augmented sampler for DP mixture models

Authors:

Michael I. Jordan,

Ben TaskarAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 545 - 552

https://doi.org/10.1145/1273496.1273565

Published: 20 June 2007 Publication History

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 projections 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.

References

[1]

Antoniak, C. E. (1974). Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems. Annals of Statistics, 2, 1152--1174.

[2]

Blei, D., & Jordan, M. I. (2005). Variational inference for Dirichlet process mixtures. Bayesian Analysis, 1, 121--144.

[3]

Dahl, D. B. (2003a). An improved merge-split sampler for conjugate Dirichlet process mixture models (Technical Report). University of Wisconsin.

[4]

Dahl, D. B. (2003b). Modal clustering in a univariate class of product partition models (Technical Report). University of Wisconsin.

[5]

Daume, H. (2007). Fast search for Dirichlet process mixture models. Artificial Intelligence and Statistics.

[6]

Escobar, M. D., & West, M. (1995). Bayesian density estimation and inference using mixtures. Journal of the American Statistical Association, 90, 577--588.

[7]

Ferguson, T. S. (1973). A Bayesian analysis of some non-parametric problems. Annals of Statistics, 1, 209--230.

[8]

Friedman, N., & Koller, D. (2000). Being Bayesian about Bayesian network structure: A Bayesian approach to structure discovery in Bayesian networks. Uncertainty in Artificial Intelligence (pp. 201--210).

Digital Library

[9]

Heller, K. A., & Ghahramani, Z. (2005). Bayesian hierarchical clustering. International Conference on Machine Learning.

Digital Library

[10]

Ishwaran, H., & James, L. F. (2001). Gibbs sampling methods for stick-breaking priors. Journal of the American Statistical Association, 96, 161--173.

[11]

Jain, S., & Neal, R. (2000). A split-merge Markov chain Monte Carlo procedure for the Dirichlet process mixture model (Technical Report). University of Toronto.

[12]

Johnson, W., & Lindenstrauss, J. (1984). Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics, 26, 189--206.

[13]

Kannan, R., Lovasz, L., & Simonovits, M. (1997). Random walks and an O*(n ⁵) volume algorithm for convex bodies. 11, 1--50.

Digital Library

[14]

Kurihara, K., Welling, M., & Teh, Y. W. (2007). Collapsed variational Dirichlet process mixture models. International Joint Conference on Artificial Intelligence.

Digital Library

[15]

Liu, J., & Wu, Y. (1999). Parameter expansion for data augmentation. Journal of the American Statistical Association, 94, 1264--1274.

[16]

Pitman, J. (2002). Combinatorial stochastic processes (Technical Report 621). Department of Statistics, UC Berkeley.

[17]

Pitman, J., & Yor, M. (1997). The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator. Annals of Probability, 25, 855--900.

[18]

Sudderth, E. B., Torralba, A. B., Freeman, W. T., & Willsky, A. S. (2006). Describing visual scenes using transformed Dirichlet processes. Advances in Neural Information Processing Systems (pp. 1297--1304).

[19]

Swendsen, R. H., & Wang, J. S. (1987). Nonuniversal critical dynamics in MC simulations. Physics Review Letters, 58, 86--88.

[20]

Tanner, M. A., & Wong, W. H. (1987). The calculation of posterior distributions by data augmentation. Journal of the American Statistical Association, 82, 528--540.

[21]

Teh, Y. W., Jordan, M., Beal, M., & Blei, D. (2006). Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101, 1566--1581.

[22]

West, M. (1995). Hyperparameter estimation in Dirichlet process mixture models (Technical Report). Duke University.

[23]

Xing, E. P., Sharan, R., & Jordan, M. I. (2004). Bayesian haplotype inference via the Dirichlet process. International Conference on Machine Learning (p. 111).

Digital Library

Cited By

Bouchard-Côté ADoucet ARoth A(2017)Particle gibbs split-merge sampling for Bayesian inference in mixture modelsThe Journal of Machine Learning Research10.5555/3122009.312203718:1(868-906)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3122037
Chang JFisher J(2013)Parallel sampling of DP mixture models using sub-clusters splitsProceedings of the 27th International Conference on Neural Information Processing Systems - Volume 110.5555/2999611.2999681(620-628)Online publication date: 5-Dec-2013
https://dl.acm.org/doi/10.5555/2999611.2999681
Niepert M(2012)Markov chains on orbits of permutation groupsProceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence10.5555/3020652.3020718(624-633)Online publication date: 14-Aug-2012
https://dl.acm.org/doi/10.5555/3020652.3020718
Show More Cited By

A permutation-augmented sampler for DP mixture models
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning

Recommendations

Partially collapsed parallel Gibbs sampler for Dirichlet process mixture models

Proposed representation for DP is ideally suited for distributed computing.Proposed sampler offers advantages in terms of both scalability and run-time.Proposed sampler outperforms existing parallel samplers for Dirichlet process mixtures in terms of ...
Tractable Bayesian learning of tree augmented Naive Bayes models
ICML'03: Proceedings of the Twentieth International Conference on International Conference on Machine Learning

Bayesian classifiers such as Naive Bayes or Tree Augmented Naive Bayes (TAN) have shown excellent performance given their simplicity and heavy underlying independence assumptions. In this paper we introduce a classifier taking as basis the TAN model and ...
The marginal likelihood of dynamic mixture models

Analytical results for reducing the parameter space dimension when computing the marginal likelihood are given for the broad class of dynamic mixture models. These results allow the integration of scale parameters out of the likelihood by Kalman ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Machine Learning Journal

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
243
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bouchard-Côté ADoucet ARoth A(2017)Particle gibbs split-merge sampling for Bayesian inference in mixture modelsThe Journal of Machine Learning Research10.5555/3122009.312203718:1(868-906)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3122037
Chang JFisher J(2013)Parallel sampling of DP mixture models using sub-clusters splitsProceedings of the 27th International Conference on Neural Information Processing Systems - Volume 110.5555/2999611.2999681(620-628)Online publication date: 5-Dec-2013
https://dl.acm.org/doi/10.5555/2999611.2999681
Niepert M(2012)Markov chains on orbits of permutation groupsProceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence10.5555/3020652.3020718(624-633)Online publication date: 14-Aug-2012
https://dl.acm.org/doi/10.5555/3020652.3020718
Liang PJordan MKlein DKaplan R(2010)Type-based MCMCHuman Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics10.5555/1857999.1858081(573-581)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.5555/1857999.1858081
Bouchard-Côté APetrov SKlein D(2009)Randomized pruningProceedings of the 23rd International Conference on Neural Information Processing Systems10.5555/2984093.2984110(144-152)Online publication date: 7-Dec-2009
https://dl.acm.org/doi/10.5555/2984093.2984110
Kurihara KTanaka SMiyashita SMcAllester D(2009)Quantum annealing for clusteringProceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence10.5555/1795114.1795152(321-328)Online publication date: 18-Jun-2009
https://dl.acm.org/doi/10.5555/1795114.1795152
Elsner MCharniak EJohnson MOstendorf MCollins MNarayanan SOard D(2009)Structured generative models for unsupervised named-entity clusteringProceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics10.5555/1620754.1620778(164-172)Online publication date: 31-May-2009
https://dl.acm.org/doi/10.5555/1620754.1620778
Kurihara KMurata TSato T(2008)Identification of MCMC samples for clusteringProceedings of the 3rd international conference on Large-scale knowledge resources: construction and application10.5555/1787800.1787805(27-37)Online publication date: 3-Mar-2008
https://dl.acm.org/doi/10.5555/1787800.1787805
Kurihara KMurata TSato T(2008)Identification of MCMC Samples for ClusteringLarge-Scale Knowledge Resources. Construction and Application10.1007/978-3-540-78159-2_3(27-37)Online publication date: 2008
https://doi.org/10.1007/978-3-540-78159-2_3

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten