nips nips2011 nips2011-43 nips2011-43-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: David Adametz, Volker Roth
Abstract: A Bayesian approach to partitioning distance matrices is presented. It is inspired by the Translation-invariant Wishart-Dirichlet process (TIWD) in [1] and shares a number of advantageous properties like the fully probabilistic nature of the inference model, automatic selection of the number of clusters and applicability in semi-supervised settings. In addition, our method (which we call fastTIWD) overcomes the main shortcoming of the original TIWD, namely its high computational costs. The fastTIWD reduces the workload in each iteration of a Gibbs sampler from O(n3 ) in the TIWD to O(n2 ). Our experiments show that the cost reduction does not compromise the quality of the inferred partitions. With this new method it is now possible to ‘mine’ large relational datasets with a probabilistic model, thereby automatically detecting new and potentially interesting clusters. 1
[1] J. Vogt, S. Prabhakaran, T. Fuchs, and V. Roth. The Translation-invariant Wishart-Dirichlet Process for Clustering Distance Data. In Proceedings of the 27th International Conference on Machine Learning, 2010.
[2] P. McCullagh and J. Yang. How Many Clusters? Bayesian Analysis, 3:101–120, 2008.
[3] Y. W. Teh. Dirichlet Processes. In Encyclopedia of Machine Learning. Springer, 2010.
[4] J. Sethuraman. A Constructive Definition of Dirichlet Priors. Statistica Sinica, 4:639–650, 1994.
[5] B. A. Frigyik, A. Kapila, and M. R. Gupta. Introduction to the Dirichlet Distribution and Related Processes. Technical report, Departement of Electrical Engineering, University of Washington, 2010.
[6] W. Ewens. The Sampling Theory of Selectively Neutral Alleles. Theoretical Population Biology, 3:87–112, 1972.
[7] D. Blei and M. Jordan. Variational Inference for Dirichlet Process Mixtures. Bayesian Analysis, 1:121–144, 2005.
[8] R. Neal. Markov Chain Sampling Methods for Dirichlet Process Mixture Models. Journal of Computational and Graphical Statistics, 9(2):249–265, 2000.
[9] P. McCullagh. Marginal Likelihood for Distance Matrices. Statistica Sinica, 19:631–649, 2009.
[10] B. Sch¨ lkopf, A. Smola, and K.-R. M¨ ller. Nonlinear Component Analysis as a Kernel Eigeno u value Problem. Neural Computation, 10(5):1299–1319, July 1998.
[11] J.A. Diaz-Garcia, J.R. Gutierrez, and K.V. Mardia. Wishart and Pseudo-Wishart Distributions and Some Applications to Shape Theory. Journal of Multivariate Analysis, 63:73–87, 1997.
[12] H. Uhlig. On Singular Wishart and Singular Multivariate Beta Distributions. Annals of Statistics, 22:395–405, 1994.
[13] M. Srivastava. Singular Wishart and Multivariate Beta Distributions. Annals of Statistics, 31(2):1537–1560, 2003.
[14] M. Farach, S. Kannan, and T. Warnow. A Robust Model for Finding Optimal Evolutionary Trees. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 137–145, 1993. 9