nips nips2007 nips2007-64 nips2007-64-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hai L. Chieu, Wee S. Lee, Yee W. Teh
Abstract: We describe a new algorithm, Relaxed Survey Propagation (RSP), for finding MAP configurations in Markov random fields. We compare its performance with state-of-the-art algorithms including the max-product belief propagation, its sequential tree-reweighted variant, residual (sum-product) belief propagation, and tree-structured expectation propagation. We show that it outperforms all approaches for Ising models with mixed couplings, as well as on a web person disambiguation task formulated as a supervised clustering problem. 1
[1] “Web person disambiguation task at SemEval,” 2007. [Online]. Available: http://nlp.uned.es/weps/taskdescription-2.html
[2] D. Battaglia, M. Kolar, and R. Zecchina, “Minimizing energy below the glass thresholds,” Physical Review E, vol. 70, 2004.
[3] A. Braunstein, M. Mezard, and R. Zecchina, “Survey propagation: An algorithm for satisfiability,” Random Struct. Algorithms, vol. 27, no. 2, 2005.
[4] B. A. Cipra, “The Ising model is NP-complete,” SIAM News, vol. 33, no. 6, 2000.
[5] C. Ding, “Spectral clustering,” ICML ’04 Tutorial, 2004.
[6] G. Elidan, I. McGraw, and D. Koller, “Residual belief propagation: Informed scheduling for asynchronous message passing,” in UAI, 2006.
[7] T. Finley and T. Joachims, “Supervised clustering with support vector machines,” in ICML, 2005.
[8] T. Heskes, “On the uniqueness of loopy belief propagation fixed points,” Neural Computation, vol. 16, 2004.
[9] T. Joachims, Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms. Norwell, MA, USA: Kluwer Academic Publishers, 2002.
[10] B. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Systems Technical Report, 1970.
[11] V. Kolmogorov, “Convergent tree-reweighted message passing for energy minimization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 10, 2006.
[12] V. Kolmogorov and R. Zabih, “What energy functions can be minimized via graph cuts?” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, 2004.
[13] F. Kschischang, B. Frey, and H. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, vol. 47, no. 2, 2001.
[14] E. Maneva, E. Mossel, and M. Wainwright, “A new look at survey propagation and its generalizations,” 2004. [Online]. Available: http://arxiv.org/abs/cs.CC/0409012
[15] T. Minka and Y. Qi, “Tree-structured approximations by expectation propagation,” in NIPS, 2004.
[16] J. M. Mooij and H. J. Kappen, “Sufficient conditions for convergence of loopy belief propagation,” in UAI, 2005.
[17] J. D. Park, “Using weighted MAX-SAT engines to solve MPE,” in AAAI, 2002.
[18] Y. Weiss and W. T. Freeman, “On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs,” IEEE Transactions on Information Theory, vol. 47, no. 2, 2001.
[19] M. Welling, T. Minka, and Y. W. Teh, “Structured region graphs: Morphing EP into GBP,” in UAI, 2005.
[20] J. S. Yedidia, W. T. Freeman, and Y. Weiss, “Constructing free-energy approximations and generalized belief propagation algorithms,” IEEE Transactions on Information Theory, vol. 51, no. 7, 2005.