We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Belief propagation algorithms for finding the probable configurations over factor graph models.
- Authors
Wang, Zheng; Liu, Yunsheng; Wang, Guangwei
- Abstract
In this article, we study the belief propagation algorithms for solving the multiple probable configurations (MPC) problem over graphical models. Based on the loopy max-product methodology, we first develop an iterative belief propagation mechanism (IBPM), which aims to find the most probable configurations facing with the existence of multiple solutions. In applications ranging from low-density parity-check codes to combinatorial optimization one would like to find not just the best configurations but rather than the summary of all possible explanations. Not only can this problem be solved by our proposed loopy message-passing algorithm (LMPA), we also prove that, for tree factor graph models, this LMPA guarantees fast convergence. Moveover, we subsequently present a low-complexity approach to simplifying the message integration operation throughout the whole belief propagation circulation. Simulations built on various settings demonstrate that both IBPM and LMPA can accurately and rapidly approximate the MPC in acyclic graph with hundreds of variables.
- Subjects
COMPUTER algorithms; CONFIGURATION management; FACTOR analysis; GRAPH theory; PROBLEM solving; PARITY-check matrix
- Publication
Knowledge & Information Systems, 2014, Vol 39, Issue 2, p265
- ISSN
0219-1377
- Publication type
Article
- DOI
10.1007/s10115-013-0622-1