非表示:
キーワード:
-
要旨:
Constraint Satisfaction Problems (CSPs) are defined over a set of variables
whose state must satisfy a number of constraints. We study a class of
algorithms called Message Passing Algorithms, which aim at finding the
probability distribution of the variables
over the space of satisfying assignments. These algorithms involve passing
local messages (according to some message update rules) over the edges of a
factor graph constructed corresponding to the CSP. We focus on the Belief
Propagation (BP) algorithm, which
finds exact solution marginals for tree-like factor graphs. However,
convergence and exactness cannot be guaranteed for a general factor graph. We
propose a method for improving BP to account for cycles in the factor graph. We
also study another message passing algorithm known as Survey Propagation (SP),
which is empirically quite effective in solving random K-SAT instances, even
when the density is close to the satisfiability threshold. We contribute to the
theoretical understanding of SP by deriving the SP
equations from the BP message update rules.
