nips nips2007 nips2007-77 nips2007-77-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jonathan Huang, Carlos Guestrin, Leonidas Guibas
Abstract: Permutations are ubiquitous in many real world problems, such as voting, rankings and data association. Representing uncertainty over permutations is challenging, since there are n! possibilities, and typical compact representations such as graphical models cannot efficiently capture the mutual exclusivity constraints associated with permutations. In this paper, we use the “low-frequency” terms of a Fourier decomposition to represent such distributions compactly. We present Kronecker conditioning, a general and efficient approach for maintaining these distributions directly in the Fourier domain. Low order Fourier-based approximations can lead to functions that do not correspond to valid distributions. To address this problem, we present an efficient quadratic program defined directly in the Fourier domain to project the approximation onto a relaxed form of the marginal polytope. We demonstrate the effectiveness of our approach on a real camera-based multi-people tracking setting. 1
[1] Y. Ivanov, A. Sorokin, C. Wren, and I. Kaur. Tracking people in mixed modality systems. Technical Report TR2007-11, MERL, 2007.
[2] J. Shin, L. Guibas, and F. Zhao. A distributed algorithm for managing multi-target identities in wireless ad-hoc sensor networks. In IPSN, 2003.
[3] P. Diaconis. Group Representations in Probability and Statistics. IMS Lecture Notes, 1988.
[4] B. Schumitsch, S. Thrun, G. Bradski, and K. Olukotun. The information-form data association filter. In NIPS. 2006.
[5] R. Kondor, A. Howard, and T. Jebara. Multi-object tracking with representations of the symmetric group. In AISTATS, 2007.
[6] X. Boyen and D. Koller. Tractable inference for complex stochastic processes. In UAI, 1998.
[7] R. Kondor. Sn ob: a C++ library for fast Fourier transforms on the symmetric group, 2006. Available at http://www.cs.columbia.edu/˜risi/Snob/.
[8] A. Willsky. On the algebraic structure of certain partially observable finite-state markov processes. Information and Control, 38:179–212, 1978.
[9] F.D. Murnaghan. The analysis of the kronecker product of irreducible representations of the symmetric group. American Journal of Mathematics, 60(3):761–784, 1938.
[10] J. van Lint and R.M. Wilson. A Course in Combinatorics. Cambridge University Press, 2001. 8