Timezone: »

 
Poster
Learning unbelievable marginal probabilities
Xaq S Pitkow · Yashar Ahmadian · Ken D Miller

Tue Dec 13 08:45 AM -- 02:59 PM (PST) @ None #None

Loopy belief propagation performs approximate inference on graphical models with loops. One might hope to compensate for the approximation by adjusting model parameters. Learning algorithms for this purpose have been explored previously, and the claim has been made that every set of locally consistent marginals can arise from belief propagation run on a graphical model. On the contrary, here we show that many probability distributions have marginals that cannot be reached by belief propagation using any set of model parameters or any learning algorithm. We call such marginals `unbelievable.' This problem occurs whenever the Hessian of the Bethe free energy is not positive-definite at the target marginals. All learning algorithms for belief propagation necessarily fail in these cases, producing beliefs or sets of beliefs that may even be worse than the pre-learning approximation. We then show that averaging inaccurate beliefs, each obtained from belief propagation using model parameters perturbed about some learned mean values, can achieve the unbelievable marginals.

Author Information

Xaq S Pitkow (University of Rochester)
Yashar Ahmadian (Columbia University)
Ken D Miller (Columbia University)

More from the Same Authors