nips nips2007 nips2007-128 nips2007-128-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sujay Sanghavi, Devavrat Shah, Alan S. Willsky
Abstract: We investigate the use of message-passing algorithms for the problem of finding the max-weight independent set (MWIS) in a graph. First, we study the performance of loopy max-product belief propagation. We show that, if it converges, the quality of the estimate is closely related to the tightness of an LP relaxation of the MWIS problem. We use this relationship to obtain sufficient conditions for correctness of the estimate. We then develop a modification of max-product – one that converges to an optimal solution of the dual of the MWIS problem. We also develop a simple iterative algorithm for estimating the max-weight independent set from this dual solution. We show that the MWIS estimate obtained using these two algorithms in conjunction is correct when the graph is bipartite and the MWIS is unique. Finally, we show that any problem of MAP estimation for probability distributions over finite domains can be reduced to an MWIS problem. We believe this reduction will yield new insights and algorithms for MAP estimation. 1
[1] M. Bayati, D. Shah and M. Sharma, “Max Weight Matching via Max Product Belief Propagation,” IEEE ISIT, 2005.
[2] D. Bertsekas, “Non Linear Programming”, Athena Scientific.
[3] M. Grtschel, L. Lovsz, and A. Schrijver, “Polynomial algorithms for perfect graphs,” in C. Berge and V. Chvatal (eds.) Topics on Perfect Graphs Ann. Disc. Math. 21, North-Holland, Amsterdam(1984) 325-356.
[4] K. Jung and D. Shah, “Low Delay Scheduing in Wireless Networks,” IEEE ISIT, 2007.
[5] C. Moallemi and B. Van Roy, “Convergence of the Min-Sum Message Passing Algorithm for Quadratic Optimization,” Preprint, 2006 available at arXiv:cs/0603058
[6] Luca Trevisan, “Inapproximability of combinatorial optimization problems,” Technical Report TR04-065, Electronic Colloquium on Computational Complexity, 2004.
[7] M. Wainwright and M. Jordan, “Graphical models, exponential families, and variational inference,” UC Berkeley, Dept. of Statistics, Technical Report 649. September, 2003.
[8] J. Yedidia, W. Freeman and Y. Weiss, “Generalized Belief Propagation,” Mitsubishi Elect. Res. Lab., TR2000-26, 2000.
[9] Y. Weiss, C. Yanover, T. Meltzer “MAP Estimation, Linear Programming and Belief Propagation with Convex Free Energies” UAI 2007 8