nips nips2013 nips2013-118 nips2013-118-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Byungkon Kang
Abstract: Determinantal Point Process (DPP) has gained much popularity for modeling sets of diverse items. The gist of DPP is that the probability of choosing a particular set of items is proportional to the determinant of a positive definite matrix that defines the similarity of those items. However, computing the determinant requires time cubic in the number of items, and is hence impractical for large sets. In this paper, we address this problem by constructing a rapidly mixing Markov chain, from which we can acquire a sample from the given DPP in sub-cubic time. In addition, we show that this framework can be extended to sampling from cardinalityconstrained DPPs. As an application, we show how our sampling algorithm can be used to provide a fast heuristic for determining the number of clusters, resulting in better clustering.
[1] A. Kulesza and B. Taskar. Determinantal point processes for machine learning. ArXiv, 2012.
[2] A. Kulesza and B. Taskar. k-DPPs: Fixed-size determinantal point processes. In Proceedings of ICML, 2011.
[3] A. Kulesza and B. Taskar. Learning determinantal point processes. In Proceedings of UAI, 2011.
[4] J.B. Hough, M. Krishnapur, Y. Peres, and B. Vir´ g. Determinantal processes and independence. a Probability Surveys, 3, 2006.
[5] I. Dhillon, Y. Guan, and B. Kulis. Kernel k-means, spectral clustering and normalized cuts. In Proceedings of ACM SIGKDD, 2004.
[6] G. Golub and C. van Loan. Matrix Computations. Johns Hopkins University Press, 1996.
[7] A. Daniel, D. Amit, H. Pierre, and P. Preyas. NP-hardness of euclidean sum-of-squares clustering. Machine Learning, 75:245–248, 2009.
[8] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Proceedings of NIPS, 2001.
[9] M. Ester, H. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of KDD, 1996.
[10] C. Fraley and A. E. Raftery. How many clusters? which clustering method? answers via model-based cluster analysis. The Computer Journal, 41(8), 1998.
[11] J. Gillenwater, A. Kulesza, and B. Taskar. Near-optimal MAP inference for determinantal point processes. In Proceedings of NIPS, 2012.
[12] D. Slate. Letter recognition data set. http://archive.ics.uci.edu/ml/ datasets/Letter+Recognition, 1991.
[13] G. H´ brail and A. B´ rard. Individual household electric power consumption data set. e e http://archive.ics.uci.edu/ml/datasets/Individual+household+ electric+power+consumption, 2012.
[14] C. Goutte, L. K. Hansen, M. G. Liptrot, and E. Rostrup. Feature-space clustering for fMRI meta-analysis. Human Brain Mapping, 13, 2001.
[15] V. Guruswami. Rapidly mixing Markov chains: A comparison of techniques. Unpublished manuscript, 2000. 9