Ising Models on Locally Tree-Like Graphs 2: With a Positive Field, Belief Propagation Converges Exponentially Fast from Every Positive Initial ConditionResearch Paper
Belief propagation (BP) is the message-passing algorithm used throughout artificial intelligence, coding theory and statistical physics to approximate marginals of graphical models. On graphs with cycles it is a heuristic: it may fail to converge, and when it converges its output need not be the true marginal. Rigorous guarantees had mostly been confined to…