Pattern Recognition and Machine Learning

8.4. Inference in Graphical Models 409

Figure 8.51 A simple factor graph used to illustrate the
sum-product algorithm.

x 1 x 2 x 3

x 4

fa fb

fc

graph whose unnormalized joint distribution is given by

̃p(x)=fa(x 1 ,x 2 )fb(x 2 ,x 3 )fc(x 2 ,x 4 ). (8.73)

In order to apply the sum-product algorithm to this graph, let us designate nodex 3

as the root, in which case there are two leaf nodesx 1 andx 4. Starting with the leaf

nodes, we then have the following sequence of six messages

μx 1 →fa(x 1 )=1 (8.74)

μfa→x 2 (x 2 )=

∑

x 1

fa(x 1 ,x 2 ) (8.75)

μx 4 →fc(x 4 )=1 (8.76)

μfc→x 2 (x 2 )=

∑

x 4

fc(x 2 ,x 4 ) (8.77)

μx 2 →fb(x 2 )=μfa→x 2 (x 2 )μfc→x 2 (x 2 ) (8.78)

μfb→x 3 (x 3 )=

∑

x 2

fb(x 2 ,x 3 )μx 2 →fb. (8.79)

The direction of flow of these messages is illustrated in Figure 8.52. Once this mes-

sage propagation is complete, we can then propagate messages from the root node

out to the leaf nodes, and these are given by

μx 3 →fb(x 3 )=1 (8.80)

μfb→x 2 (x 2 )=

∑

x 3

fb(x 2 ,x 3 ) (8.81)

μx 2 →fa(x 2 )=μfb→x 2 (x 2 )μfc→x 2 (x 2 ) (8.82)

μfa→x 1 (x 1 )=

∑

x 2

fa(x 1 ,x 2 )μx 2 →fa(x 2 ) (8.83)

μx 2 →fc(x 2 )=μfa→x 2 (x 2 )μfb→x 2 (x 2 ) (8.84)

μfc→x 4 (x 4 )=

∑

x 2

fc(x 2 ,x 4 )μx 2 →fc(x 2 ). (8.85)