Inference in Bayesian Networks Joseph E Gonzalez 10701 Recitation Convenient Probabilistic Model Compact Representation Resistant to Over fitting Captures underlying structure Creates a language for describing probability relationships Permits the construction of generic inference techniques Variable Elimination Variational Methods Belief Propagation 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 2 Joint Probability What can you compute with P X1 X2 Xn Joint probability Marginal Probability Conditional distributions P X1 X2 X3 Predictions Most likely explanations max P X1 X4 X2 X3 Samples from the distribution Information gain 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 3 What is a Bayesian Network P A f1 A P B f2 B P C A f3 C A P D B f4 D B P E C D f5 E C D P F D f6 F D P G E F f7 G E F Conditional Probability Distributions Tables Functions A B C D E F G Directed Acyclic Graph 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 4 Conditional Probability CPDs CPTs Conditional Probability CPD Distributions CPT Tables Can be Discrete Continuous P C A A T A F C T 0 3 0 6 C F 0 7 0 4 OR C A 2 2 2 1 P C A e 2 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 5 Graphs Describe Probability Distributions P A B C D E F G P A P B P C A P D B P E C D P F D P G E F A B C D E F G 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 6 Writing the Joint Probability Bayesian Network For a directed acyclic graph G V E P X1 X2 Xn n i 1 Where PaG Xi are the parents of Xi P Xi P aG Xi We say that P X1 Xn factors with respect to the graph G 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 7 Conditional Independence If influence can flow from node A to node B given observations then nodes A and B are not conditionally independent Open Closed Observed Unobserved 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 8 Independence A Indep B Yes A Indep G No A Indep B given G A B C D E F No G 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 9 Inference Computing Joint Assignment P A a B b B b Easy A B C D Computing Marginal Tricky to Hard E F Computing Conditional Requires Marginal G 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 10 Why is it hard to Marginalize Marginalize Unobserved Variables You want P X1 X2 but you have P X1 Xn P X1 X2 P X1 X2 x3 x4 xn x3 x4 xn for X3 1 b for X4 1 b for X5 1 b for X6 1 b 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 11 How can we save some work Simple Algebra Example Want to compute f1 a f2 b f3 c f4 d a b c d Rearrange the sums Much Easier f1 a f2 b f3 c f4 d a b c d 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 12 Return functions Coupled Variables Suppose we want to compute f1 a f2 b a f3 c b f4 d c a c b d Functions rather than constants a b f1 a f2 b a f3 c b c Cache Computation d f4 d c g1 c 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 13 What is a Function Assume variables are discrete g x1 x2 xn table x1 x2 xn Assume variables are discrete Each entry in the table is a cached marginalization 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 14 Example Graph Define Some Variables C H HW Grade P F E Exam Grade P F H E P Project Grade P F O Overall Grade P F O P C Class Attend T F Happy T F 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 15 Example Joint Probability C P C H E O P H P C P P P H C P E C E O P O H E P P H O P 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 16 Example Tables P O H E P H p E p O p O f P E C E p E f 0 95 0 05 C t 0 7 0 3 C f 0 4 0 6 P p H p E p P f 0 6 0 4 H p E f P p 0 6 0 4 P H C H p H f H p E f P f 0 3 0 7 C t 0 7 0 3 C f 0 4 0 6 H f E p P p 0 3 0 7 H f E p P f 0 2 0 8 H f E f P p 0 1 0 9 O p H f E f P f 0 01 0 99 P P P p P f 0 7 0 3 P O H t f H p 0 7 0 3 O p H f 0 8 0 2 O f H p 0 2 0 8 O f H f 0 1 0 9 P C C t C f 0 8 0 2 C H E O P 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 17 Happiness and Class Attendance P C H H O P E O P P C H E O P E P r C P P P H C P E C P O H E P P H O H O E P C H O P r C P H C P E C P H O E P P P P O H E P This becomes a function table g1 O H E 2007 Joseph E Gonzalez Machine Learning Department Carnegie Mellon University 18 The Function g1 g1 O H E P P O H E P P P P O H E P O p O f g1 O H E H p E p P p 0 95 0 05 O p H p E p 0 7 0 95 0 3 0 6 0 845 H p E p P f 0 6 0 4 O p H p E f 0 7 0 6 0 3 0 3 0 510 H p E f P p 0 6 0 4 O p H f E p 0 7 0 3 0 3 0 2 0 270 H p E f P f 0 3 0 7 O p H f E f 0 7 0 1 0 3 0 01 0 073 H f E p P p 0 3 0 7 O f H p E p 0 7 0 05 0 3 0 4 0 155 H f E p …
View Full Document
Unlocking...