Machine learning lecture 23 Tommi S Jaakkola MIT CSAIL tommi csail mit edu Announcements Course evaluations on going Project submission Friday Dec 3 only electronic submissions pdf or ps see the course website if you need an extension and have a reason you need to ask Late submissions are not possible otherwise Final exam in class Wed Dec 8 a part of the lecture on Monday Dec 6 will be review comprehensive covers all the course material but the emphasis will be on the material since the midterm as promised EM and HMMs will be on the exam open book laptops fine if not connected Tommi Jaakkola MIT CSAIL 2 Exact inference All exact inference algorithms for Bayesian networks perform essentially the same calculations but operate on different representations The junction tree algorithm is a simple message passing algorithm over clusters of variables Preliminary steps 1 transform the Bayesian network into an undirected model via moralization marry parents 2 triangulate the resulting undirected graph add edges 3 identify the cliques clusters of the resulting triangulated graph 4 construct the junction tree from the cliques Tommi Jaakkola MIT CSAIL 3 Exact inference preliminary steps Moralization x1 x2 x3 x4 x5 original graph Tommi Jaakkola MIT CSAIL 4 Exact inference preliminary steps Moralization x1 x2 x3 x1 x4 x5 original graph Tommi Jaakkola MIT CSAIL x2 x3 x4 x5 marry parents 5 Exact inference preliminary steps Moralization x1 x2 x3 x1 x4 x5 original graph Tommi Jaakkola MIT CSAIL x2 x3 x1 x4 x5 marry parents x2 x3 x4 x5 moral graph 6 Exact inference preliminary steps Moralization x1 x2 x1 x3 x4 x2 x3 x5 x1 x4 x5 x2 x3 x4 x5 original graph marry parents moral graph Triangulation add edges so that any cycle of four or more nodes has a chord x1 x2 x3 x4 x5 already triangulated Tommi Jaakkola MIT CSAIL 7 Exact inference preliminary steps Moralization x1 x2 x1 x3 x4 x2 x1 x3 x5 x4 x2 x3 x5 x4 x5 original graph marry parents moral graph Triangulation add edges so that any cycle of four or more nodes has a chord x1 x2 x3 x1 x4 x5 x2 x3 x4 x5 already triangulated not triangulated Tommi Jaakkola MIT CSAIL 8 Exact inference preliminary steps Moralization x1 x2 x1 x3 x4 x2 x1 x3 x5 x4 x2 x3 x5 x4 x5 original graph marry parents moral graph Triangulation add edges so that any cycle of four or more nodes has a chord x1 x2 x3 x1 x4 x5 x2 x3 x2 x4 x5 x1 x3 x4 x5 already triangulated not triangulated not triangulated Tommi Jaakkola MIT CSAIL 9 Exact inference preliminary steps cont d Find the maximal cliques of the triangulated graph c1 x1 x2 x3 x4 x5 c1 x1 x2 x3 Tommi Jaakkola MIT CSAIL 10 Exact inference preliminary steps cont d Find the maximal cliques of the triangulated graph c1 x1 c1 x2 x3 x1 x4 x5 x2 x3 c2 x4 x5 c1 x1 x2 x3 c2 x2 x3 x4 Tommi Jaakkola MIT CSAIL 11 Exact inference preliminary steps cont d Find the maximal cliques of the triangulated graph c1 x1 c1 c1 x2 x3 x1 x4 x5 x2 x3 c2 x4 x5 x1 x2 x3 c2 x4 x5 c3 c1 x1 x2 x3 c2 x2 x3 x4 c3 x3 x4 x5 Tommi Jaakkola MIT CSAIL 12 Exact inference preliminary steps cont d Find the maximal cliques of the triangulated graph c1 x1 c1 c1 x2 x3 x1 x4 x5 x2 x3 c2 x4 x5 x1 x2 x3 c2 x4 x5 c3 c1 x1 x2 x3 c2 x2 x3 x4 c3 x3 x4 x5 Clique trees and junction trees c1 x1 x2 x3 c2 x2 x3 x4 c3 x3 x4 x5 clique tree Tommi Jaakkola MIT CSAIL 13 Exact inference preliminary steps cont d Find the maximal cliques of the triangulated graph c1 x1 c1 c1 x2 x3 x1 x4 x5 x2 x3 c2 x4 x1 x2 x3 x4 x5 x5 c2 c3 c1 x1 x2 x3 c2 x2 x3 x4 c3 x3 x4 x5 Clique trees and junction trees c1 x1 x2 x3 c2 x2 x3 x4 c3 x3 x4 x5 clique tree Tommi Jaakkola MIT CSAIL c1 x1 x2 x3 s12 x2 x3 c2 x2 x3 x4 c3 x3 x4 x3 x4 x5 s23 junction tree with separators 14 Exact inference potentials Associating graphs and potentials x1 P x1 x2 P x2 x3 P x3 x1 x2 x5 x4 P x4 x2 P x5 x3 x4 original graph w probs Tommi Jaakkola MIT CSAIL c1 x1 x2 x3 s12 x2 x3 c2 x2 x3 x4 c3 x3 x4 x3 x4 x5 s23 junction tree 15 Exact inference potentials Associating graphs and potentials x1 P x1 x2 P x2 x3 P x3 x1 x2 x5 x4 P x4 x2 P x5 x3 x4 original graph w probabilities P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x4 x2 x3 x4 x5 s23 P x5 x3 x4 junction tree w probs c1 x1 x2 x3 P x1 P x2 P x3 x1 x2 c2 x2 x3 x4 P x4 x2 c3 x3 x4 x5 P x5 x3 x4 s12 x2 x3 1 separator s23 x3 x4 1 separator Tommi Jaakkola MIT CSAIL 16 Exact inference message passing Select a root clique Collect evidence m1 2 x2 x3 s12 root c2 x2 x3 x2 x3 x4 c3 x3 x4 x3 x4 x5 s23 m3 2 x3 x4 c1 x1 x2 x3 Distribute evidence c1 x1 x2 x3 m2 1 x2 x3 s12 root c2 x2 x3 x2 x3 x4 c3 x3 x4 x3 x4 x5 s23 m2 3 x3 x4 Tommi Jaakkola MIT CSAIL 17 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x4 x2 x3 x4 x5 s23 P x5 x3 x4 Tommi Jaakkola MIT CSAIL 18 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x4 x2 x3 x4 x5 s23 P x5 x3 x4 Evaluate new separators X s0 12 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 19 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 P x4 x2 x3 x4 x5 s23 P x5 x3 x4 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 20 Exact inference message passing Collect evidence P x1 P x2 P x3 x1 x2 x1 x2 x3 s12 1 c 2 c1 x2 x3 x2 x3 x4 c3 x3 x4 1 …