nips nips2010 nips2010-257 nips2010-257-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alex Kulesza, Ben Taskar
Abstract: We present a novel probabilistic model for distributions over sets of structures— for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containing dissimilar structures are more likely. Our model is a marriage of structured probabilistic models, like Markov random fields and context free grammars, with determinantal point processes, which arise in quantum physics as models of particles with repulsive interactions. We extend the determinantal point process model to handle an exponentially-sized set of particles (structures) via a natural factorization of the model into parts. We show how this factorization leads to tractable algorithms for exact inference, including computing marginals, computing conditional probabilities, and sampling. Our algorithms exploit a novel polynomially-sized dual representation of determinantal point processes, and use message passing over a special semiring to compute relevant quantities. We illustrate the advantages of the model on tracking and articulated pose estimation problems. 1
[1] A. Borodin. Determinantal point processes, 2009.
[2] A. Borodin and A. Soshnikov. Janossy densities. I. Determinantal ensembles. Journal of Statistical Physics, 113(3):595–610, 2003.
[3] D. Daley and D. Vere-Jones. An introduction to the theory of point processes: volume I: elementary theory and methods. Springer, 2003.
[4] P. Felzenszwalb and D. Huttenlocher. Pictorial structures for object recognition. International Journal of Computer Vision, 61(1):55–79, 2005.
[5] M. Fischler and R. Elschlager. The representation and matching of pictorial structures. IEEE Transactions on Computers, 100(22), 1973.
[6] D. Forsyth and J. Ponce. Computer Vision: A Modern Approach. Prentice Hall, 2003.
[7] J. Hough, M. Krishnapur, Y. Peres, and B. Vir´ g. Determinantal processes and independence. a Probability Surveys, 3:206–229, 2006.
[8] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009.
[9] Z. Li and J. Eisner. First-and second-order expectation semirings with applications to minimum-risk training on translation forests. In Proc. EMNLP, 2009.
[10] O. Macchi. The coincidence approach to stochastic point processes. Advances in Applied Probability, 7(1):83–122, 1975.
[11] J. MacCormick and A. Blake. A probabilistic exclusion principle for tracking multiple objects. International Journal of Computer Vision, 39(1):57–71, 2000.
[12] C. D. Manning and H. Sch¨ tze. Foundations of Statistical Natural Language Processing. MIT u Press, Boston, MA, 1999.
[13] T. Nilsen and B. Graveley. Expansion of the eukaryotic proteome by alternative splicing. Nature, 463(7280):457–463, 2010.
[14] B. Sapp, C. Jordan, and B. Taskar. Adaptive pose priors for pictorial structures. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’10), 2010.
[15] T. Zhao and R. Nevatia. Tracking multiple humans in complex situations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26:1208–1221, 2004. 9