0.25
0.5
0.75
1.25
1.5
1.75
2
Bounds and estimates for BP convergence on binary undirected graphical models
Published on Feb 25, 20074417 Views
Belief Propagation (BP) has become a popular method for inference on graphical models. Accurate approximations for intractable quantities (e.g. single-node marginals) can be obtained within rather mod
Related categories
Chapter list
Introduction00:45
Graphical model, exact probability distribution03:15
Belief Propagation04:53
BP for binary variables06:22
Norms and contractions07:51
Lemma 1.09:07
Example: 1-norm for binary variables11:58
Example: weighted 1-norm13:16
Beyond the binary case14:05
We can (try to) bound15:38
We can conclude18:01
Binary case: comparison of various bounds19:12
A very rough average-case analysis29:05
Conclusions32:43