Graphical Models and Bayesian Networks Required reading Ghahramani section 2 Learning Dynamic Bayesian Networks just 3 5 pages Optional reading Mitchell chapter 6 11 Bayesian Belief Networks Machine Learning 10 701 Tom M Mitchell Center for Automated Learning and Discovery Carnegie Mellon University November 1 2005 Graphical Models Key Idea Conditional independence assumptions useful but Na ve Bayes is extreme Graphical models express sets of conditional independence assumptions via graph structure Graph structure plus associated parameters define joint probability distribution over set of variables nodes Two types of graphical models today Directed graphs aka Bayesian Networks Undirected graphs aka Markov Random Fields 1 Graphical Models Why Care Among most important ML developments of the decade Graphical models allow combining Prior knowledge in form of dependencies independencies Observed data to estimate parameters Principled and general methods for Probabilistic inference Learning Useful in practice Diagnosis help systems text analysis time series models Marginal Independence Definition X is marginally independent of Y if Equivalently if Equivalently if 2 Conditional Independence Definition X is conditionally independent of Y given Z if the probability distribution governing X is independent of the value of Y given the value of Z Which we often write E g Bayesian Network Bayes network a directed acyclic graph defining a joint probability distribution over a set of variables Each node denotes a random variable StormClouds Lightning Thunder Each node is conditionally independent of its non descendents given its immediate parents Rain WindSurf A conditional probability distribution CPD is associated with each node N defining P N Parents N Parents P W Pa P W Pa L R 0 1 0 L R 0 1 0 L R 0 2 0 8 L R 0 9 0 1 WindSurf 3 Bayesian Networks Each node denotes a variable Edges denote dependencies CPD for each node Xi describes P Xi Pa Xi Joint distribution given by Node Xi is conditionally independent of its non descendents given its immediate parents Parents Pa X immediate parents Antecedents parents parents of parents Children immediate children Descendents children children of children Bayesian Networks CPD for each node Xi describes P Xi Pa Xi Chain rule of probability But in Bayes net 4 How Many Parameters StormClouds Lightning Parents P W Pa P W Pa L R 0 1 0 L R 0 1 0 L R 0 2 0 8 L R 0 9 0 1 Rain WindSurf Thunder WindSurf In full joint distribution Given this Bayes Net Bayes Net Inference P BattPower t Radio t Starts f Most probable explanation What is most likely value of Leak BatteryPower given Starts f Active data collection What is most useful variable to observe next to improve our knowledge of node X 5 Algorithm for Constructing Bayes Network Choose an ordering over variables e g X1 X2 Xn For i 1 to n Add Xi to the network Select parents Pa Xi as minimal subset of X1 Xi 1 such that Notice this choice of parents assures by chain rule by construction Example Bird flu and Allegies both cause Nasal problems Nasal problems cause Sneezes and Headaches 6 What is the Bayes Network for Na ve Bayes Bayes Network for a Hidden Markov Model Assume the future is conditionally independent of the past given the present Unobserved state St 2 St 1 St St 1 St 2 Observed output Ot 2 Ot 1 Ot Ot 1 Ot 2 7 Conditional Independence Revisited We said Each node is conditionally independent of its non descendents given its immediate parents Does this rule give us all of the conditional independence relations implied by the Bayes network No E g X1 and X4 are conditionally indep given X2 X3 But X1 and X4 not conditionally indep given X3 For this we need to understand D separation X1 X4 X2 X3 Explaining Away 8 X and Y are conditionally independent given Z iff X and Y are D separated by Z D connection If G is a directed graph in which X Y and Z are disjoint sets of vertices then X and Y are d connected by Z in G if and only if there exists an undirected path U between some vertex in X and some vertex in Y such that 1 for every collider C on U either C or a descendent of C is in Z and 2 no non collider on U is in Z X and Y are D separated by Z in G if and only if they are not D connected by Z in G See d Separation tutorial http www andrew cmu edu user scheines tutor d sep html See d Separation Applet http www andrew cmu edu user wimberly dsep dSep html A0 and A2 conditionally indep given A1 A3 9 Inference in Bayes Nets In general intractable NP complete For certain cases tractable Assigning probability to fully observed set of variables Or if just one variable unobserved Or for singly connected graphs ie no undirected loops Belief propagation For multiply connected graphs no directed loops Junction tree Sometimes use Monte Carlo methods Generate a sample according to known distribution Variational methods for tractable approximate solutions Learning in Bayes Nets Four categories of learning problems Graph structure may be known unknown Variables may be observed unobserved Easy case learn parameters for known graph structure using fully observed data Gruesome case learn graph and parameters from partly unobserved data More on these in next lectures 10 Java Bayes Net Applet http www pmr poli usp br ltd Software javabayes Home applet html What You Should Know Bayes nets are convenient representation for encoding dependencies conditional independence BN Graph plus parameters of CPD s Defines joint distribution over variables Can calculate everything else from that Though inference may be intractable Reading conditional independence relations from the graph N cond indep of non descendents given parents D separation Explaining away 11
View Full Document
Unlocking...