11School of Computer ScienceThe Elimination AlgorithmProbabilistic Graphical Models (10Probabilistic Graphical Models (10--708)708)Lecture 4, Sep 26, 2007Eric XingEric XingReceptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X8Reading: J-Chap 3, KF-Chap. 8, 9Eric Xing 2z Questions?2Eric Xing 3Probabilistic Inferencez We now have compact representations of probability distributions: Graphical Modelsz A GM G describes a unique probability distribution Pz How do we answer queries about P?z We use inference as a name for the process of computing answers to such queriesEric Xing 4∑∑=11xxkk,,x,xPP )()( ee KLQuery 1: Likelihoodz Most of the queries one may ask involve evidencez Evidence e is an assignment of values to a set E variables in the domainz Without loss of generality E = { Xk+1, …, Xn}z Simplest query: compute probability of evidencez this is often referred to as computing the likelihood of e3Eric Xing 5∑===xx,XPX,PPX,PXP)()()()()|(eeeee∑==zezZYY )|()|( ,PePQuery 2: Conditional Probabilityz Often we are interested in the conditional probability distribution of a variable given the evidencez this is the a posteriori belief in X, given evidence ez We usually query a subset Y of all domain variables X={Y,Z} and "don't care" about the remaining, Z:z the process of summing out the "don't care" variables zis called marginalization, and the resulting P(y|e) is called a marginal prob.Eric Xing 6A CBA CB??Applications of a posteriori Beliefz Prediction: what is the probability of an outcome given the starting conditionz the query node is a descendent of the evidencez Diagnosis: what is the probability of disease/fault given symptomsz the query node an ancestor of the evidencez Learning under partial observationz fill in the unobserved values under an "EM" setting (more later)z The directionality of information flow between variables is not restricted by the directionality of the edges in a GMz probabilistic inference can combine evidence form all parts of the network4Eric Xing 7z In this query we want to find the most probable joint assignment (MPA) for some variables of interestz Such reasoning is usually performed under some given evidence e, and ignoring (the values of) other variables z :z this is the maximum a posteriori configuration of y.∑∈∈==zyyezyeyeY )|,(maxarg)|(maxarg)|(MPA PPYYQuery 3: Most Probable AssignmentEric Xing 8x y P(x,y)00 0.3501 0.0510 0.311 0.3Applications of MPAz Classification z find most likely label, given the evidencez Explanation z what is the most likely scenario, given the evidenceCautionary note:z The MPA of a variable depends on its "context"---the set of variables been jointly queriedz Example:z MPA of X ?z MPA of (X, Y) ?5Eric Xing 9Thm:Computing P(X = x| e) in a GM is NP-hardz Hardness does not mean we cannot solve inferencez It implies that we cannot find a general procedure that works efficiently for arbitrary GMsz For particular families of GMs, we can have provably efficient proceduresComplexity of InferenceEric Xing 10Approaches to inferencez Exact inference algorithmsz The elimination algorithmz Message-passing algorithm (sum-product, belief propagation)z The junction tree algorithms z Approximate inference techniquesz Stochastic simulation / sampling methodsz Markov chain Monte Carlo methodsz Variational algorithms6Eric Xing 11z A signal transduction pathway:z Query: P(e)z By chain decomposition, we getA B CED∑∑∑∑∑∑∑∑==dcbadcbadePcdPbcPabPaPe)P(a,b,c,d,eP)|()|()|()|()()(a naïve summation needs to enumerate over an exponential number of termsWhat is the likelihood that protein E is active?Marginalization and EliminationEric Xing 12A B CED∑∑∑ ∑∑∑∑∑==dcb adcbaabPaPdePcdPbcPdePcdPbcPabPaPeP)|()()|()|()|()|()|()|()|()()(Elimination on Chainsz Rearranging terms ...7Eric Xing 13z Now we can perform innermost summationz This summation "eliminates" one variable from our summation argument at a "local cost".A B CEDX∑∑∑∑∑∑∑==dcbdcb abpdePcdPbcPabPaPdePcdPbcPeP)()|()|()|()|()()|()|()|()(Elimination on ChainsEric Xing 14A B CED∑∑∑∑ ∑∑∑∑===dcdc bdcbcpdePcdPbpbcPdePcdPbpdePcdPbcPeP)()|()|()()|()|()|()()|()|()|()(XXElimination in Chainsz Rearranging and then summing again, we get8Eric Xing 15z Eliminate nodes one by one all the way to the end, we getz Complexity:z Each step costs O(|Val(Xi)|*|Val(Xi+1)|) operations: O(kn2)z Compare to naïve evaluation that sums over joint values of n-1 variables O(nk)A B CED∑=ddpdePeP )()|()(XXXXElimination in ChainsEric Xing 16z Rearranging terms ...A B CEDUndirected ChainsL===∑∑∑ ∑∑∑∑∑dcb adcbaabdecdbcZdecdbcabZeP),(),(),(),(),(),(),(),()(φφφφφφφφ119Eric Xing 17The Sum-Product Operationz In general, we can view the task at hand as that of computing the value of an expression of the form:where Fis a set of factorsz We call this task the sum-product inference task.∑∏∈zFφφEric Xing 18Outcome of eliminationz Let X be some set of variables, let Fbe a set of factors such that for each φ∈F, Scope[φ] ∈ X, let Y ⊂ X be a set of query variables, and let Z = X−Y be the variable to be eliminatedz The result of eliminating the variable Z is a factorz This factor does not necessarily correspond to any probability or conditional probability in this network. (example forthcoming)∑∏∈=zYFφφτ)(10Eric Xing 19Dealing with evidencez Conditioning as a Sum-Product Operationz The evidence potential:z Total evidence potential:z Introducing evidence --- restricted factors:⎩⎨⎧≠≡=iiiiiieEeEeE if 0 if ),(1δ∑∏∈×=ezeEeY,),(),(Fφδφτ∏∈=EeEIiiieE ),(),(δδEric Xing 20General idea:z Write query in the formz this suggests an "elimination order" of latent variables to be marginalizedz Iterativelyz Move all irrelevant terms outside of innermost sumz Perform innermost sum, getting a new termz Insert the new term into the productz wrap-up∑∑∑∏=nxxxiiipaxPXP32)|(),(1Le∑=1111xXXXP),(),()|(eeeφφInference on General GM via Variable Elimination11Eric Xing 21The elimination algorithmProcedure Elimination (G, // the GME, // evidenceZ, // Set of variables to be eliminatedX, // query variable(s) )1. Initialize (G)2. Evidence (E)3. Sum-Product-Elimination (F, Z, ≺)4. Normalization (F)Eric Xing 22The elimination algorithmProcedure Initialize (G, Z)1. Let Z1, . . . ,Zkbe an
View Full Document
Unlocking...