Machine learning lecture 22 Review graphs and probabilities Directed graphical models Bayesian networks Tommi S Jaakkola MIT CSAIL tommi csail mit edu x1 x2 d sep x3 x1 d sep from x2 given nothing indep assoc distribution x1 indep from x2 given nothing P x1 P x2 P x3 x1 x2 Tommi Jaakkola MIT CSAIL 2 Review graphs and probabilities Outline Directed graphical models Bayesian networks x1 Quantitative probabilistic inference diagnosis example marginalization and message passing cliques clique trees and the junction tree algorithm x2 d sep x3 x1 d sep from x2 given nothing indep x1 indep from x2 given nothing assoc distribution P x1 P x2 P x3 x1 x2 Undirected graphical models Markov Random Fields x1 x3 x2 separation indep x1 indep from x2 given x3 x1 separated from x2 given x3 assoc distribution 1 Z 13 x1 x3 23 x2 x3 Tommi Jaakkola MIT CSAIL 3 Three inference problems Tommi Jaakkola MIT CSAIL 4 Inference graph transformation Medical diagnosis example binary disease variables d and possible findings f P d1 d1 P d2 d2 P d3 d3 Diseases d f f1 P f1 d1 d2 f2 P f2 d2 d3 Findings 1 What are the marginal posterior probabilities over the diseases given observed findings f f1 fk 2 What is the most likely setting of all the underlying disease variables 3 Which test should we carry out next in order to get the most information about the diseases Tommi Jaakkola MIT CSAIL 5 Tommi Jaakkola MIT CSAIL 6 Inference graph transformation Inference graph transformation 12 d1 d2 P d1 d1 P d2 d2 12 d1 d2 P d3 d3 d1 f2 f1 P f1 d1 d2 P d2 Tommi Jaakkola MIT CSAIL 8 We have transformed the Bayesian network into an undirected graph model Markov random field P d3 d3 12 d1 d2 P d1 f2 f1 P f1 d1 d2 P f2 d2 d3 Inference graph transformation 23 d2 d3 d2 f2 23 d2 d3 P d3 P f2 d2 d3 Inference graph transformation P d1 d3 12 d1 d2 P d1 P d2 P f1 d1 d2 7 d1 P d3 d2 P f1 d1 d2 12 d1 d2 P d1 P d2 P f1 d1 d2 12 d1 d2 P d2 f1 P f2 d2 d3 Tommi Jaakkola MIT CSAIL 23 d2 d3 P d1 d1 23 d2 d3 P d2 d2 undirected interactions P d3 d3 d1 P f2 d2 d3 d2 f2 f1 12 d1 d2 P d1 P d2 P f1 d1 d2 P f1 d1 d2 23 d2 d3 P d3 P f2 d2 d3 d3 12 d1 d2 23 d2 d3 independence properties based on simple graph separation P f2 d2 d3 P d1 d2 d3 data 12 d1 d2 23 d2 d3 Joint distribution as a product of interaction potentials P d1 d2 d3 data 12 d1 d2 23 d2 d3 Tommi Jaakkola MIT CSAIL 9 Marginalization d1 d2 Tommi Jaakkola MIT CSAIL Marginalization and messages m1 2 d2 d3 d1 12 d1 d2 23 d2 d3 P d2 d3 data d2 d3 P d2 data d2 d3 12 d1 d2 It suffices to evaluate the following probabilities P d1 data P d1 d2 d3 data 10 23 d2 d3 P d1 d2 d3 data d1 P d1 d2 d3 data d1 d3 P d3 data P d1 d2 d3 data d1 d2 These will readily yield the posterior probabilities of interest P d1 data P d1 data P d 1 data d 1 Tommi Jaakkola MIT CSAIL 11 Tommi Jaakkola MIT CSAIL 12 Marginalization and messages Marginalization and messages m1 2 d2 d1 d2 12 d1 d2 P d2 d3 data m1 2 d2 d3 d1 d2 23 d2 d3 12 d1 d2 P d1 d2 d3 data P d2 d3 data d1 d1 d3 23 d2 d3 P d1 d2 d3 data d1 12 d1 d2 23 d2 d3 d1 12 d1 d2 23 d2 d3 12 d1 d2 23 d2 d3 d1 Tommi Jaakkola MIT CSAIL 13 Marginalization and messages Tommi Jaakkola MIT CSAIL 14 Marginalization and messages m1 2 d2 d1 d2 12 d1 d2 P d2 d3 data m1 2 d2 m2 3 d3 d3 d1 23 d2 d3 d2 12 d1 d2 P d1 d2 d3 data P d3 data d1 d1 d3 23 d2 d3 P d2 d3 data d2 12 d1 d2 23 d2 d3 12 d1 d2 23 d2 d3 d1 m1 2 d2 23 d2 d3 Tommi Jaakkola MIT CSAIL 15 Marginalization and messages Tommi Jaakkola MIT CSAIL 16 Marginalization and messages m1 2 d2 m2 3 d3 d1 d2 12 d1 d2 P d3 data m1 2 d2 m2 3 d3 d3 d1 23 d2 d3 12 d1 d2 P d2 d3 data P d3 data d2 d2 d2 d3 23 d2 d3 P d2 d3 data d2 m1 2 d2 23 d2 d3 1 d2 m1 2 d2 23 d2 d3 1 m1 2 d2 23 d2 d3 1 d2 Tommi Jaakkola MIT CSAIL 17 Tommi Jaakkola MIT CSAIL 18 Marginalization and messages Marginalization and messages m1 2 d2 m2 3 d3 d1 d2 12 d1 d2 P d3 data m1 2 d2 m3 2 d2 d3 d1 d2 23 d2 d3 12 d1 d2 P d2 d3 data d2 23 d2 d3 P d2 data d2 d3 P d2 d3 data d3 m1 2 d2 23 d2 d3 1 m1 2 d2 23 d2 d3 1 d2 m2 3 d3 1 Tommi Jaakkola MIT CSAIL 19 Marginalization and messages Tommi Jaakkola MIT CSAIL 20 Marginalization and messages m1 2 d2 m3 2 d2 d1 d2 12 d1 d2 P d2 data m1 2 d2 m3 2 d2 d3 d1 d2 23 d2 d3 12 d1 d2 P d2 d3 data P d2 data d3 d3 d3 23 d2 d3 P d2 d3 data d3 m1 2 d2 23 d2 d3 d3 m1 2 d2 23 d2 d3 m1 2 d2 23 d2 d3 d3 Tommi Jaakkola MIT CSAIL 21 Marginalization and messages d2 12 d1 d2 P d2 data 22 Message passing and trees The same message passing approach belief propagation works for any tree structured model m1 2 d2 m3 2 d2 d1 Tommi Jaakkola MIT CSAIL d3 23 d2 d3 m1 2 d2 d2 d1 12 d1 d2 m4 2 d2 P d2 d3 data d3 d3 m2 3 d3 d3 23 d2 d3 24 d2 d4 d4 m1 2 d2 23 d2 d3 m2 3 d3 m1 2 d2 23 d2 d3 m1 2 d2 m4 2 d2 23 d2 d3 d2 P d2 data d3 m1 2 d2 m3 2 d2 Tommi Jaakkola MIT CSAIL 23 Tommi Jaakkola MIT CSAIL 24 Back to the diagnosis problem Outline This does not look like a tree Quantitative probabilistic inference diagnosis example marginalization and message passing cliques clique trees and the junction tree algorithm Diseases Findings Tommi Jaakkola MIT CSAIL 25 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 …