Loading...
Please wait, while we are loading the content...
Maximum weight matching via max-product belief propagation (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Shah, Devavrat Bayati, Mohsen |
| Abstract | Abstract — The max-product “belief propagation ” algorithm is an iterative, local, message passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding and computer vision which involve graphs with many cycles, theoretical convergence results are only known for graphs which are tree-like or have a single cycle. In this paper, we consider a weighted complete bipartite graph and define a probability distribution on it whose MAP assignment corresponds to the maximum weight matching (MWM) in that graph. We analyze the fixed points of the max-product algorithm when run on this graph and prove the surprising result that even though the underlying graph has many short cycles, the maxproduct assignment converges to the correct MAP assignment. We also provide a bound on the number of iterations required by the algorithm. I. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Maximum Weight Matching Theoretical Convergence Result Many Application Area Weighted Complete Bipartite Graph Max-product Belief Propagation Algorithm Graphical Model Maxproduct Assignment Converges Correct Map Assignment Spectacular Success Maximum Weight Surprising Result Max-product Belief Propagation Iterative Decoding Many Short Cycle Many Cycle Map Assignment Corresponds Discrete Probability Distribution Single Cycle Max-product Algorithm Fixed Point Computer Vision Message Passing Algorithm Probability Distribution |
| Content Type | Text |
| Resource Type | Article |
