Bounds and estimates for BP convergence on binary undirected graphical models thumbnail
Pause
Mute
Subtitles
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Bounds and estimates for BP convergence on binary undirected graphical models

Published on Feb 25, 20074421 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