Machine learning lecture 23 Tommi S Jaakkola MIT CSAIL tommi csail mit edu Outline Exact inference quickly message passing in junction trees Approximate inference belief propagation sampling Review for the final what is important what is not Tommi Jaakkola MIT CSAIL 2 Exact inference key steps Baysian network moralization triangulation x1 x2 x1 x3 x4 x5 x2 x1 x3 x4 x3 x5 original graph x2 x4 x5 moral graph already triangulated Cliques clique graph and junction tree c1 x1 x2 x3 c2 c1 x1 x2 x3 x4 x5 cliques Tommi Jaakkola MIT CSAIL c3 c2 x2 x3 x4 c3 x3 x4 x5 clique tree c1 x1 x2 x3 c3 x3 x4 x5 s12 x2 x3 c2 x2 x3 x4 x3 x4 s23 junction tree 3 Exact inference potentials Associating graphs and potentials x1 P x1 x2 P x2 x4 P x4 x2 x3 P x3 x1 x2 x5 P x5 x3 x4 original graph w probabilities P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c1 x2 x3 c3 x3 x4 x5 P x5 x3 x4 x3 x4 s23 c2 x2 x3 x4 1 P x4 x2 junction tree w probs c1 x1 x2 x3 c2 x2 x3 x4 c3 x3 x4 x5 P x1 x5 s12 x2 x3 s23 x3 x4 Tommi Jaakkola MIT CSAIL 4 Exact inference message passing Select a root clique Collect evidence c1 x1 x2 x3 c3 x3 x4 x5 m1 2 x2 x3 s12 root c2 x2 x3 x2 x3 x4 x3 x4 s23 m3 2 x3 x4 Distribute evidence c1 x1 x2 x3 c3 x3 x4 x5 Tommi Jaakkola MIT CSAIL m2 1 x2 x3 s12 root c2 x2 x3 x2 x3 x4 x3 x4 s23 m2 3 x3 x4 5 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c1 x2 x3 c3 x3 x4 x5 P x5 x3 x4 Tommi Jaakkola MIT CSAIL x3 x4 s23 c2 x2 x3 x4 1 P x4 x2 6 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c1 x2 x3 c3 x3 x4 x5 P x5 x3 x4 x3 x4 s23 c2 x2 x3 x4 1 P x4 x2 Evaluate new separators X 0 s12 x2 x3 c1 x1 x2 x3 P x2 x3 x1 s0 23 x3 x4 X c3 x3 x4 x5 1 x5 Tommi Jaakkola MIT CSAIL 7 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c1 x2 x3 c3 x3 x4 x5 P x5 x3 x4 x3 x4 s23 c2 x2 x3 x4 1 P x4 x2 Messages not explicitly used in the algorithm s0 12 x2 x3 P x2 x3 m1 2 x2 x3 s12 x2 x3 1 s0 23 x3 x4 1 m3 2 x3 x4 s23 x3 x4 1 Tommi Jaakkola MIT CSAIL 8 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c1 x2 x3 c3 x3 x4 x5 P x5 x3 x4 x3 x4 s23 c2 x2 x3 x4 1 P x4 x2 Update clique potentials based on messages s0 12 x2 x3 s0 23 x3 x4 c2 x2 x3 x4 c2 x2 x3 x4 x x x x s12 z2 3 s23 z3 4 m1 2 x2 x3 m3 2 x3 x4 P x2 x3 1 P x4 x2 P x2 x3 x4 followed by s12 s0 12 and s23 s0 23 Tommi Jaakkola MIT CSAIL 9 Exact inference message passing Distribute evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 P xc2 x3 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x2 x3 x4 x3 x4 x5 s23 P x5 x3 x4 Tommi Jaakkola MIT CSAIL 10 Exact inference message passing Distribute evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 P xc2 x3 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x2 x3 x4 x3 x4 x5 s23 P x5 x3 x4 Evaluate new separators X 0 s12 x2 x3 c2 x2 x3 x4 P x2 x3 x4 s0 23 x3 x4 X c2 x2 x3 x4 P x3 x4 x2 Tommi Jaakkola MIT CSAIL 11 Exact inference message passing Distribute evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 P xc2 x3 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x2 x3 x4 x3 x4 x5 s23 P x5 x3 x4 Messages not explicitly used in the algorithm s0 12 x2 x3 P x2 x3 1 m2 1 x2 x3 s12 x2 x3 P x2 x3 s0 23 x3 x4 P x3 x4 m2 3 x3 x4 s23 x3 x4 1 Tommi Jaakkola MIT CSAIL 12 Exact inference message passing Distribute evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 P xc2 x3 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x2 x3 x4 x3 x4 x5 s23 P x5 x3 x4 Update clique potentials based on messages s0 12 x2 x3 c1 x1 x2 x3 P x1 x2 x3 c1 x1 x2 x3 s12 x2 x3 s0 23 x3 x4 c3 x3 x4 x5 c3 x3 x4 x5 P x3 x4 x5 s23 x3 x4 followed by s12 s0 12 and s23 s0 23 Tommi Jaakkola MIT CSAIL 13 Exact inference After the collect and distribute steps the marginal probabilities are stored locally at the clique potentials and the separators P x1 x2 x3 c1 x1 x2 x3 c3 x3 x4 x5 P x3 x4 x5 s12 P x2 x3 c2 x2 x3 x2 x3 x4 P x2 x3 x4 x3 x4 s23P x3 x4 P x1 x2 x3 P x2 x3 x4 P x3 x4 x5 P x1 x5 P x2 x3 P x3 x4 More generally the resulting potentials would be proportional to the posterior marginals e g P x1 x2 x3 data which can be easily normalized Tommi Jaakkola MIT CSAIL 14 Outline Exact inference quickly message passing in junction trees Approximate inference belief propagation sampling Review for the final what is important what is not Tommi Jaakkola MIT CSAIL 15 Approximate inference motivation We cannot solve the medical diagnosis problem s with exact inference algorithms Diseases d f Diseases Findings Findings the largest clique has over 100 variables the corresponding potential function or table would involve more than 2100 elements Tommi Jaakkola MIT CSAIL 16 Approximate inference belief propagation The message passing algorithm is appropriate when the model is a clique tree we need a unique path of influence between any sets of variables We can still apply the message passing algorithm even if the model is not a tree message passing operations are defined locally m1 2 x2 x1 x2 m4 2 x2 x3 x4 convergence accuracy Tommi Jaakkola MIT CSAIL 17 Approximate inference belief propagation m1 2 x2 x1 x2 m4 2 x2 x3 x4 a set of locally consistent messages fixed point of the algorithm always exists the accuracy of the resulting marginals related to the …