Pattern Recognition and Machine Learning

8.4. Inference in Graphical Models 401 x 1 x 2 x 3 (a) x 1 x 2 x 3 f (b) x 1 x 2 x 3 fc fa fb (c) Figure 8.42 (a) A directed gra ...

402 8. GRAPHICAL MODELS (a) (b) (c) Figure 8.43 (a) A directed polytree. (b) The result of converting the polytree into an undir ...

8.4. Inference in Graphical Models 403 x 1 x 2 x 3 (a) x 1 x 2 x 3 f(x 1 ,x 2 ,x 3 ) (b) x 1 x 2 x 3 fa fb fc (c) Figure 8.45 (a ...

404 8. GRAPHICAL MODELS Figure 8.46 A fragment of a factor graph illustrating the evaluation of the marginalp(x). fs x μfs→x(x) ...

8.4. Inference in Graphical Models 405 Figure 8.47 Illustration of the factorization of the subgraph as- sociated with factor no ...

406 8. GRAPHICAL MODELS Figure 8.48 Illustration of the evaluation of the message sent by a variable node to an adjacent factor ...

8.4. Inference in Graphical Models 407 as illustrated in Figure 8.49(b). At this point, it is worth pausing to summarize the par ...

408 8. GRAPHICAL MODELS Figure 8.50 The sum-product algorithm can be viewed purely in terms of messages sent out by factor nodes ...

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 ...

410 8. GRAPHICAL MODELS x 1 x 2 x 3 x 4 (a) x 1 x 2 x 3 x 4 (b) Figure 8.52 Flow of messages for the sum-product algorithm appli ...

8.4. Inference in Graphical Models 411 Table 8.1 Example of a joint distribution over two binary variables for which the maximum ...

412 8. GRAPHICAL MODELS whereM is the total number of variables, and then substitute forp(x)using its expansion in terms of a pr ...

8.4. Inference in Graphical Models 413 the results (8.66) and (8.69) derived earlier for the sum-product algorithm, we can readi ...

414 8. GRAPHICAL MODELS Figure 8.53 A lattice, or trellis, diagram show- ing explicitly theKpossible states (one per row of the ...

8.4. Inference in Graphical Models 415 by the lines connecting the nodes. Once we know the most probable value of the fi- nal no ...

416 8. GRAPHICAL MODELS 8.4.6 Exact inference in general graphs The sum-product and max-sum algorithms provide efficient and exa ...

8.4. Inference in Graphical Models 417 clique and will grow exponentially with this number in the case of discrete variables. An ...

418 8. GRAPHICAL MODELS other messages would simply duplicate the previous message on the same link. For graphs that have a tree ...

Exercises 419 Table 8.2 The joint distribution over three binary variables. a b c p(a, b, c) 0 0 0 0.192 0 0 1 0.144 0 1 0 0.048 ...

420 8. GRAPHICAL MODELS Figure 8.54 Example of a graphical model used to explore the con- ditional independence properties of th ...