nips nips2012 nips2012-111 nips2012-111-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Maksims Volkovs, Richard S. Zemel
Abstract: Bipartite matching problems characterize many situations, ranging from ranking in information retrieval to correspondence in vision. Exact inference in realworld applications of these problems is intractable, making efficient approximation methods essential for learning and inference. In this paper we propose a novel sequential matching sampler based on a generalization of the PlackettLuce model, which can effectively make large moves in the space of matchings. This allows the sampler to match the difficult target distributions common in these problems: highly multimodal distributions with well separated modes. We present experimental results with bipartite matching problems—ranking and image correspondence—which show that the sequential matching sampler efficiently approximates the target distribution, significantly outperforming other sampling approaches. 1
[1] A. Bouchard-Cote and M. I. Jordan. Variational inference over combinatorial spaces. In NIPS, 2010.
[2] C. Cadena, D. Galvez-Lopez, F. Ramos, J. D. Tardos, and J. Neira. Robust place recognition with stereo cameras. In IROS, 2010.
[3] T. S. Caetano, L. Cheng, Q. V. Le, and A. J. Smola. Learning graph matching. In ICML, 2009.
[4] O. Chapelle, Y. Chang, and T.-Y. Liu. The Yahoo! Learning to Rank Challenge. 2010.
[5] F. Dellaert, S. M. Seitz, C. E. Thorpe, and S. Thrun. EM, MCMC, and chain flipping for structure from motion with unknown correspondence. Machine Learning, 50, 2003.
[6] J.-P. Doignon, A. Pekec, and M. Regenwetter. The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika, 69, 2004.
[7] C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation methods for the web. In WWW, 2001.
[8] B. Huang and T. Jebara. Loopy belief propagation for bipartite maximum weight b-matching. In AISTATS, 2007.
[9] J. Huang, C. Guestrin, and L. Guibas. Fourier theoretic probabilistic inference over permutations. Machine Learning Research, 10, 2009.
[10] M. Huber and J. Law. Fast approximation of the permanent for very dense problems. In SODA, 2008.
[11] M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. 2004.
[12] Q. V. Le and A. Smola. Direct optimization of ranking measures. In arxiv: 0704.3359, 2007.
[13] T. Lu and C. Boutilier. Learning Mallows models with pairwise preferences. In ICML, 2011.
[14] R. D. Luce. Individual choice behavior: A theoretical analysis. Wiley, 1959.
[15] R. M. Neal. Probabilistic inference using Markov Chain Monte Carlo methods. Technical report, University of Toronto, 1993.
[16] C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, 1982.
[17] J. Petterson, T. S. Caetano, J. J. McAuley, and J. Yu. Exponential family graph matching and ranking. In NIPS, 2009.
[18] R. Plackett. The analysis of permutations. Applied Statistics, 24, 1975.
[19] T. Qin, T.-Y. Liu, X.-D. Zhang, D.-S. Wang, and H. Li. Global ranking using continuous conditional random fields. In NIPS, 2008.
[20] F. Ramos, D. Fox, and H. Durrant-Whyte. CRF-Matching: Conditional random fields for feature-based scan matching. In Robotics: Science and Systems, 2007.
[21] D. A. Ross, D. Tarlow, and R. S. Zemel. Learning articulated structure and motion. International Journal on Computer Vision, 88, 2010.
[22] R. Salakhutdinov. Learning deep Boltzmann machines using adaptive MCMC. In ICML, 2010.
[23] M. Taylor, J. Guiver, S. Robertson, and T. Minka. Softrank: Optimizing non-smooth rank metrics. In WSDM, 2008.
[24] W. R. Taylor. Protein structure comparison using bipartite graph matching and its application to protein structure classification. In Molecular Cell Proteomics, 2002.
[25] L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8, 1979.
[26] M. N. Volkovs and R. S. Zemel. Boltzrank: Learning to maximize expected ranking gain. In ICML, 2009.
[27] Y. Wang, F. Makedon, and J. Ford. A bipartite graph matching framework for finding correspondences between structural elements in two proteins. In IEBMS, 2004. 9