jmlr jmlr2009 jmlr2009-36 jmlr2009-36-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, ranking, and data association. Representing uncertainty over permutations is challenging, since there are n! possibilities, and typical compact and factorized probability distribution representations, such as graphical models, cannot capture the mutual exclusivity constraints associated with permutations. In this paper, we use the “low-frequency” terms of a Fourier decomposition to represent distributions over permutations compactly. We present Kronecker conditioning, a novel approach for maintaining and updating these distributions directly in the Fourier domain, allowing for polynomial time bandlimited approximations. Low order Fourier-based approximations, however, may lead to functions that do not correspond to valid distributions. To address this problem, we present a quadratic program defined directly in the Fourier domain for projecting the approximation onto a relaxation of the polytope of legal marginal distributions. We demonstrate the effectiveness of our approach on a real camera-based multi-person tracking scenario. Keywords: identity management, permutations, approximate inference, group theoretical methods, sensor networks
Hamsa Balakrishnan, Inseok Hwang, and Claire Tomlin. Polynomial approximation algorithms for belief matrix maintenance in identity management. In Proceedings of the 43rd IEEE Conference on Decision and Control, Bahamas, 2004. Yaakov Bar-Shalom and Thomas E. Fortmann. Tracking and Data Association. Academic Press, 1988. John Bartholdi, Craig Tovey, and Michael Trick. Voting schemes for which it can be difficult to tell who won. Social Choice and Welfare, 6(2), 1989. Xavier Boyen and Daphne Koller. Tractable inference for complex stochastic processes. In UAI ’98: Uncertainty in Artificial Intelligence, 1998. Jin-Quan Chen. Group Representation Theory for Physicists. World Scientific, 1989. Michael Clausen and Ulrich Baum. Fast Fourier transforms for symmetric groups: Theory and implementation. Mathematics of Computations, 61(204):833–847, 1993. Joseph Collins and Jeffrey Uhlmann. Efficient gating in data association with multivariate distributed states. IEEE Transactions Aerospace and Electronic Systems, 28, 1992. James Cooley and John Tukey. An algorithm for the machine calculation of complex fourier series. Mathematical Computation, 19:297–301, 1965. 1067 H UANG , G UESTRIN AND G UIBAS Ingemar Cox and Sunita Hingorani. An efficient implementation of Reid’s multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking. In International Conference on Pattern Recognition, pages 437–443, 1994. Douglas E. Critchlow. Metric Methods for Analyzing Partially Ranked Data. Springer-Verlag, 1985. Persi Diaconis. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, 1988. Persi Diaconis. A generalization of spectral analysis with application to ranked data. The Annals of Statistics, 17(3):949–979, 1989. Michael Fligner and Joseph Verducci. Distance based ranking models. Journal of the Royal Statistical Society, 48, 1986. Richard Foote, Gagan Mirchandani, and Dan Rockmore. Two-dimensional wreath product transforms. Journal of Symbolic Computation, 37(2):187–207, 2004. Yoav Freund, Raj Iyer, Robert E. Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research (JMLR), 4:933–969, 2003. ISSN 1533-7928. Ulf Grenander. Probabilities on Algebraic Structures. Wiley, 1963. David P. Helmbold and Manfred K. Warmuth. Learning permutations with exponential weights. In COLT ’07: The Twentieth Annual Conference on Learning Theory, 2007. Jonathan Huang, Carlos Guestrin, and Leonidas Guibas. Efficient inference for distributions on permutations. In NIPS ’07: Advances in Neural Information Processing Systems, Vancouver, Canada, December 2007. Jonathan Huang, Carlos Guestrin, Xiaoye Jiang, and Leonidas Guibas. Exploiting probabilistic independence for permutations. In AISTATS ’09: Artificial Intelligence and Statistics, Clearwater Beach, Florida, April 2009. Gordon James and Adelbert Kerber. The Representation Theory of the Symmetric Group. AddisonWesley, 1981. Thorsten Joachims. Optimizing search engines using clickthrough data. In KDD ’02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 133–142, New York, NY, USA, 2002. ACM. Risi Kondor. Sn ob: a C++ library for fast Fourier transforms on the symmetric group, 2006. Available at http://www.cs.columbia.edu/˜risi/Snob/. Risi Kondor and Karsten M. Borgwardt. The skew spectrum of graphs. In ICML ’08: Proceedings of the 25th International Conference on Machine Learning, pages 496–503, 2008. Risi Kondor, Andrew Howard, and Tony Jebara. Multi-object tracking with representations of the symmetric group. In AISTATS ’07: Artificial Intelligence and Statistics, 2007. 1068 F OURIER T HEORETIC P ROBABILISTIC I NFERENCE OVER P ERMUTATIONS Ka-Lam Kueh, Timothy Olson, Dan Rockmore, and Ki-Seng Tan. Nonlinear approximation theory on finite groups. Technical Report PMA-TR99-191, Department of Mathematics, Dartmouth College, 1999. Serge Lang. Algebra. Addison-Wesley, 1965. Guy Lebanon and Yi Mao. Non-parametric modeling of partially ranked data. In John C. Platt, Daphne Koller, Yoram Singer, and Sam Roweis, editors, NIPS ’07: Advances in Neural Information Processing Systems, pages 857–864, Cambridge, MA, 2008. MIT Press. Colin Mallows. Non-null ranking models. Biometrika, 44, 1957. David Maslen. The efficient computation of Fourier transforms on the symmetric group. Mathematics of Computation, 67:1121–1147, 1998. Marina Meila, Kapil Phadnis, Arthur Patterson, and Jeff Bilmes. Consensus ranking under the exponential model. Technical Report 515, University of Washington, Statistics Department, April 2007. Francis Murnaghan. The analysis of the kronecker product of irreducible representations of the symmetric group. American Journal of Mathematics, 60(3):761–784, 1938. Katta G. Murty. An algorithm for ranking all the assignments in order of increasing cost. Operations Research, 16:682–687, 1968. Songhwai Oh and Shankar Sastry. A polynomial-time approximation algorithm for joint probabilistic data association. In Proceedings of the American Control Conference, Portland, OR, 2005. Songhwai Oh, Stuart Russell, and Shankar Sastry. Markov chain Monte Carlo data association for general multiple-target tracking problems. In Proceedings of the IEEE International Conference on Decision and Control, Paradise Island, Bahamas, 2004. Aubrey B. Poore. Multidimensional assignment and multitarget tracking. In Partitioning Data Sets, volume 19, pages 169–196. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1995. Lawrence Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257–286, 1989. Donald Reid. An algorithm for tracking multiple targets. IEEE Transactions on Automatic Control, 6:843–854, 1979. Daniel N. Rockmore. The FFT: An algorithm the whole family can use. Computing in Science and Engineering, 02(1):60–64, 2000. Bruce E. Sagan. The Symmetric Group. Springer, April 2001. ISBN 0387950672. Brad Schumitsch, Sebastian Thrun, Gary Bradski, and Kunle Olukotun. The information-form data association filter. In NIPS ’05: Advances in Neural Information Processing Systems, Cambridge, MA, 2005. MIT Press. 1069 H UANG , G UESTRIN AND G UIBAS Brad Schumitsch, Sebastian Thrun, Leonidas Guibas, and Kunle Olukotun. The identity management Kalman filter (imkf). In RSS ’06: Proceedings of Robotics: Science and Systems, Philadelphia, PA, USA, August 2006. Jean-Pierre Serre. Linear Representations of Finite Groups. Springer-Verlag, 1977. Jaewon Shin, Leonidas Guibas, and Feng Zhao. A distributed algorithm for managing multi-target identities in wireless ad-hoc sensor networks. In IPSN ’03: Information Processing in Sensor Networks, 2003. Jaewon Shin, Nelson Lee, Sebastian Thrun, and Leonidas Guibas. Lazy inference on object identities in wireless sensor networks. In IPSN ’05: Information Processing in Sensor Networks, 2005. Michael Taylor, John Guiver, Stephen Robertson, and Tom Minka. Softrank: optimizing nonsmooth rank metrics. In WSDM ’08: Proceedings of the international conference on Web search and web data mining, pages 77–86, New York, NY, USA, 2008. ACM. Audrey Terras. Fourier Analysis on Finite Groups and Applications. London Mathematical Society, 1999. Jack van Lint and Richard M. Wilson. A Course in Combinatorics. Cambridge University Press, 2001. Charles F. van Loan. The ubiquitous kronecker product. Journal of Computational and Applied Mathematics, 123(1-2):85–100, 2000. ISSN 0377-0427. Anatoly Vershik and Andrei Okounkov. A new approach to the representation theory of symmetric groups. ii. Journal of Mathematical Sciences, 131(2):5471–5494, 2006. Alan Willsky. On the algebraic structure of certain partially observable finite-state markov processes. Information and Control, 38:179–212, 1978. 1070