Bayes Nets Rong Jin Hidden Markov Model O0 O1 O2 O3 O4 q0 q1 q2 q3 q4 Inferring from observations oi to hidden variables qi This is a general framework for representing and reasoning about uncertainty Representing uncertain information with random variables nodes Representing the relationship between information with conditional probability distribution directed arcs Infer from observation shadowed nodes to the hidden variables circled nodes An Example of Bayes Network S It is sunny L Ali arrives slightly late O Slides are put on web late P S 0 2 P O 0 4 P S O P S P O P L S O 0 05 P L S O 0 4 P L S O 0 6 P L S O 0 7 Absence of an arrow Bayes Network Example Random S and O are independent Knowing S will not help predicate O P S 0 2 P O 0 4 P S O P S P O P L S O 0 05 Two arrows into L P L S on O O 0 4 L depends S and Knowing S and O will help P Lpredicate S OL 0 6 P L S O 0 7 P O 0 4 P S 0 2 S O L P L S O 0 05 P L S O 0 4 P L S O 0 6 P L S O 0 7 Inference in Bayes Network S 1 O 0 P L S 1 P O P L L 1 P S P O L 1 S 1 P O P S 0 2 P O 0 4 S O L P L S O 0 05 P L S O 0 4 P L S O 0 6 P L S O 0 7 Conditional Independence Formal definition A and B are conditional independent given C iff p A B C p A C Different from independence C A B Example A shoe size B glove size C heigh Shoe size is not independent from glove size Distinguish Two Cases C B A A shoe size B glove size C heigh Given C A and B are independent Without C A and B can be dependent S O Without L S and O are independent Given L S and O can be dependent L S It is sunny L Ali arrives slightly late O Slides are put on web late Another Example for Bayes Nets P C P C 0 5 Cloudy P R C 0 8 P R C 0 2 P R C 0 2 P S C 0 1 P S C 0 9 P S C 0 5 Rain Sprinkle P R C 0 8 P S C 0 5 WetGrass P W S R 1 P W S R 0 P W S R 0 1 P W S R 0 9 P W S R 0 1 P W S R 0 9 P W S R 0 01 P W S R 0 99 Inference questions W 1 P R W 1 P C W 1 C 1 P S P C P S R Bayes Nets Formalized A Bayes net also called a belief network is an augmented directed acyclic graph represented by the pair V E where V is a set of vertices E is a set of directed edges joining vertices No loops of any length are allowed Each vertex in V contains the following information The name of a random variable A probability distribution table indicating how the probability of this variable s values depends on all possible combinations of parental values Building a Bayes Net 1 2 3 4 Choose a set of relevant variables Choose an ordering for them Assume they re called X1 Xm where X1 is the first in the ordering X1 is the second etc For i 1 to m 1 Add the Xi node to the network 2 Set Parents Xi to be a minimal subset of X1 Xi 1 such that we have conditional independence of Xi and all other members of X1 Xi 1 given Parents Xi 3 Define the probability table of P Xi k Assignments of Parents Xi Example of Building Bayes Nets Suppose we re building a nuclear power station There are the following random variables GRL Gauge Reads Low CTL Core temperature is low FG Gauge is faulty FA Alarm is faulty AS Alarm sounds If alarm working properly the alarm is meant to sound if the gauge stops reading a low temp If gauge working properly the gauge is meant to read the temp of the core Bayes Net for Power Station GRL Gauge Reads Low CTL CTL Core temperature is low FG GRL FA FG Gauge is faulty FA Alarm is faulty AS Alarm sounds AS Inference with Bayes Nets Key issue computing joint probability P X1 x1 X2 x2 Xn 1 xn 1 Xn xn Using the conditional independence relations to simplify the computation P X n xn X n 1 xn 1 X 2 x2 X 1 x1 P X n xn X n 1 xn 1 X 2 x2 X 1 x1 P X n 1 xn 1 X 2 x2 X 1 x1 P X n xn X n 1 xn 1 X 2 x2 X 1 x1 P X n 1 xn 1 X 2 x2 X 1 x1 P X n 2 xn 2 X 2 x2 X1 x1 n P X i xi i 1 n X i 1 xi 1 K X1 x1 P X i xi Assignments of Parents X i i 1 Example for Inference P C P C 0 5 Cloudy P R C 0 8 P R C 0 2 P R C 0 2 P S C 0 1 P S C 0 9 P S C 0 5 Rain Sprinkle P R C 0 8 P S C 0 5 WetGrass P W S R 1 P W S R 0 P W S R 0 1 P W S R 0 9 P W S R 0 1 P W S R 0 9 P W S R 0 01 P W S R 0 99 Inference questions W 1 P R W 1 P C W 1 C 1 P S P C P S R Problem with Inference using Bayes Nets Inference Infer from observations EO to unknown variables Eu P Eu Eo P joint entry P Eu Eo joint entries matching Eo and Eu P Eo P joint entry joint entries matching Eo Suppose you have m binary valued variables in your Bayes Net and expression Eo mentions k variables How much work is the above computation Problem with Inference using Bayes Nets General querying of Bayes nets is NP complete Some solutions Belief propagation Take advantage of the structure of Bayes nets Stochastic simulation Similar to the sampling approaches for Bayesian average More Interesting Questions Learning Bayes nets Given the topological structure of a Bayes net learn all the conditional probability tables from examples Example Hierarchical mixture model Learning the topological structure of Bayes net Very very hard question Unfortunately the lecturer …