Today’s Lecture

Today’s lectureExact inference in graphical models.Variable EliminationElimination as Graph TransformationTreewidthSum-product belief propagationMax-product belief propagationJunction tree algorithm (during tutorial)Figures from Koller book as well as Nowozin et al.Zemel & Urtasun (UofT)CSC 412Feb 9, 20163 / 56

Inference: conditional probabilitiesToday we will look into exact inference in graphical models.We will focus on conditional probability queriesp(Y E e) P(Y, e)P(e)Let W X Y E be the random variables that are neither the query northe evidence. Each of the distributions can be computed by marginalizingover the other variables:XXp(Y, e) P(Y, e, w),P(e) P(y, e, w)wy,wNaively marginalizing over all unobserved variables requires an exponentialnumber of computations. Why?Is there a more efficient algorithm?Zemel & Urtasun (UofT)CSC 412Feb 9, 20164 / 56

Probabilistic inference in practiceProbabilistic inference in NP-hard (both Directed and Undirected models)Should we give up?NP-hardness simply says that there exist difficult inference problemsReal-world inference problems are not necessarily as hard as these worst-caseinstancesIt is easy to do inference in some graphs, e.g., inference in hidden Markovmodels (HMMs) and other tree-structured modelsZemel & Urtasun (UofT)CSC 412Feb 9, 20165 / 56

Variable Elimination (VE)Exact algorithm for probabilistic inference in any graphical modelRunning time will depend on the graph structureUses dynamic programming to avoid enumerating all assignmentsLet’s first look at computing marginal probabilities p(Xi ) in Directedmodels, and then generalize this to conditional queries on MRFsZemel & Urtasun (UofT)CSC 412Feb 9, 20166 / 56

Basic idea of variable eliminationLet’s start with a simple chain A B C D, and we want to computeP(D)This is nothing but computing a tableBy the chain rule we can write the joint distributionp(A, B, C , D) p(A)p(B A)p(C B)p(D C )To compute p(D), we can marginalize all other variablesXp(D) p(A a, B b, C c, D)a,b,cThis looks exponential, but · · ·Zemel & Urtasun (UofT)CSC 412Feb 9, 20167 / 56

Let’s be a bit more explicit.There is structure on the summation (repeated terms)Let’s modify the computation to first computeP(a1 )P(b 1 a1 ) P(a2 )P(b 1 a2 )P(a1 )P(b 2 a1 ) P(a2 )P(b 2 a2 )Zemel & Urtasun (UofT)CSC 412Feb 9, 20168 / 56

Let’s be a bit more explicit.Let’s modify the computation to first computeP(a1 )P(b 1 a1 ) P(a2 )P(b 1 a2 )andP(a1 )P(b 2 a1 ) P(a2 )P(b 2 a2 )Then we getWe define τ1 : Val(B) , τ1 (b i ) P(a1 )P(b i a1 ) P(a2 )P(b i a2 )Zemel & Urtasun (UofT)CSC 412Feb 9, 20169 / 56

Let’s be a bit more explicit.We now haveWe can once more reverse the order of the product and the sum and getWe have other repetitive patterns.Zemel & Urtasun (UofT)CSC 412Feb 9, 201610 / 56

Let’s be a bit more explicit.We define τ2 : Val(C ) , withτ2 (c 1 ) τ1 (b 1 )P(c 1 b 1 ) τ1 (b 2 )P(c 1 b 2 )τ2 (c 2 ) τ1 (b 1 )P(c 2 b 1 ) τ1 (b 2 )P(c 2 b 2 )Thus we can compute the marginal P(D) asZemel & Urtasun (UofT)CSC 412Feb 9, 201611 / 56

Even more explicit.The joint isP(D) Xa,b,cp(a, b, c, D) XP(a)P(b a)P(c b)P(D c)a,b,cXXXcbP(D c)P(c b)P(b a)P(a)aWe can push the summation insideXXXP(D) P(D c)P(c b)P(b a)P(a) {z}cabψ1 (a,b) Let’s call ψ1 (A, B) P(A)P(B A) and τ1 (B) {zτ1 (b)}Pψ1 (A, B).PWe can define ψ2 (B, C ) τ1 (B)P(C B) and τ2 (C ) B ψ1 (B, C ).AThis procedure is dynamic programming: computation is inside out insteadof outside in.Zemel & Urtasun (UofT)CSC 412Feb 9, 201612 / 56

Complexity of a chainGeneralizing to a chain X1 X2 · · · Xn , and each node has k states.We can compute at each step i 1 up to n 1XP(Xi 1 ) P(Xi 1 xi )P(xi )xiWe need to multiply P(xi ) with each CPD P(Xi 1 Xi ) for each value of xi .P(Xi ) has k values, and the CPD P(Xi 1 Xi ) has k 2 values.k 2 multiplications and k(k 1) additions.The cost of the total chain is O(nk 2 ).In comparison, generating the full joint and summing it up has complexityO(k n ).We have done inference over the joint without generating it explicitly.Zemel & Urtasun (UofT)CSC 412Feb 9, 201613 / 56

Summary so farWorst case analysis says that computing the joint is NP-hard.In practice due to the structure of the Bayesian network some subexpressionsin the joint depend only on a subset of variables.We can catch up computations that are otherwise computed exponentiallymany times.This depends on our having a good variable elimination orderingZemel & Urtasun (UofT)CSC 412Feb 9, 201614 / 56

Sum-product InferenceWe want an algorithm to compute P(Y) for directed and undirected modelsThis can be reduced to the following sum-product inference taskXYτ (Y) φ(zScope[φ] Z , yScope[φ] Y ) Yzφ Φwhere Φ is a set of potentials or factorsFor directed models, Φ is given by the conditional probability distributionsfor all variables,Φ {φXi }ni 1 {p(Xi XPa(Xi ) )}ni 1where the sum is over the set Z X YFor MRFs, the factors Φ correspond to the set of potentialsSum productPreturns unnormalized distributions, so we normalize bydividing by y τ (y)Zemel & Urtasun (UofT)CSC 412Feb 9, 201615 / 56

Variable eliminationLet φ(X, Y ) be a factor where X is a set of variables and Y /XFactor marginalization of φ over Y (also called ”summing out Y in φ”) tobe a new factorXτ (X) φ(X, Y )YWe only sum up the entries that X matches upZemel & Urtasun (UofT)CSC 412Feb 9, 201616 / 56

Sum-product Variable EliminationOrder the variables Z (called the elimination ordering)Iteratively marginalize out variable Zi one at a timeFor each i123Multiply all factors that have Zi in their scope, generating a newproduct factorMarginalize this product factor over Zi , generating a smaller factorRemove the old factors from the set of all factors, and add the new oneZemel & Urtasun (UofT)CSC 412Feb 9, 201617 / 56

Zemel & Urtasun (UofT)CSC 412Feb 9, 201618 / 56

Some propertiesIf we sum out all the variables in a normalized distribution, what do we get?If we sum out all the variables in an unnormalized distribution, what do weget?Important property is that sum and product are commutative, and theproduct is associative, i.e., (φ1 φ2 )φ3 φ1 (φ2 φ3 ).Therefore, if X / Scope(φ1 ) thenXX(φ1 φ2 ) φ1φ2XZemel & Urtasun (UofT)XCSC 412Feb 9, 201619 / 56

Chain example againLet’s look at the chain againP(A, B, C , D) φA φB φC φDThe marginal distribution over DXP(D) φA φB φC φDA,B,C!! XCφDXBφCX(φB φA )Awhere we have used the limited scope of the factors.Marginalizing involves taking the product of all CPDs and sum over all butthe variables in the query.We can do this in any order we want; some more efficient than others.Effective as the scope is limited, we push in some of the summations.Zemel & Urtasun (UofT)CSC 412Feb 9, 201620 / 56

Example of Directed GraphThe joint distributionp(C , D, I , G , S, L, H, J) p(C )p(D C )p(I )p(G D, I )p(L G )P(S I )P(J S, L)p(H J, G )with factorsΦ {φc (C ), φD (C , D), φI (I ), φG (G , D, I ), φL (L, G ),φS (S, I ), φJ (J, S, L), φH (H, J, G )}Let’s do variable elimination with ordering {C , D, I , H, G , S, L} on the board!Zemel & Urtasun (UofT)CSC 412Feb 9, 201621 / 56

Example of Directed GraphZemel & Urtasun (UofT)CSC 412Feb 9, 201622 / 56

Elimination OrderingWe can pick any order we want, but some orderings introduce factors withmuch larger scope.Alternative ordering.Zemel & Urtasun (UofT)CSC 412Feb 9, 201623 / 56

Semantics of FactorsIn the chain example the factors were marginal or conditional probabilities,but this is not true in general.The result of eliminating X is not a marginal or conditional probability ofthe networkXτ (A, B, C ) P(X )P(A X )P(C B, X )XZemel & Urtasun (UofT)CSC 412Feb 9, 201624 / 56

How to introduce evidence?But we wanted to answer conditional probability queriesp(Y E e) p(Y, e)p(e)Apply variable elimination algorithm to the task of computing P(Y, e).Replace each factor φ Φ that has E Scope[φ] 6 0 withφ0 (xScope[φ] E ) φ(xScope[φ] E , eE Scope[φ] )Then eliminate the variables X Y E. The return factor φ (Y) is p(Y, e)To obtain the conditional p(Y e) normalize the resulting product of factors– the normalization constant is p(e).Zemel & Urtasun (UofT)CSC 412Feb 9, 201625 / 56

Sum-product VE for conditional distributionsZemel & Urtasun (UofT)CSC 412Feb 9, 201626 / 56

ExampleWe want to compute P(J).To compute P(J i 1 , h0 )Zemel & Urtasun (UofT)CSC 412Feb 9, 201627 / 56

Complexity of Variable EliminationLet n be the number of random variables and m the number of initial factors.At each step we pick a variable Xi and multiply all factors involving thevariable, resulting in a single factor ψi . The variable gets sum out of ψi ,resulting in a new factor τi with scope(τ ) scope(φ) Xi .Let Ni be the number of entries in the factor ψi , and let Nmax maxi Ni .Therefore the total cost is O(mk Nmax ), with k Val(X ) .Problem: Nmax can be as large as nZemel & Urtasun (UofT)CSC 412Feb 9, 201628 / 56

Complexity in Graph termsLet’s try to analyze the complexity in terms of the graph structure.The algorithm does not care if the graph is directed or undirected, onlydepends on the scope of the factors.Let GΦ be the undirected graph with one node per variable, where we havean edge iff there exists a factor φ Φ such that Xi , Xj Scope(φ).Ignoring evidence, this is either the original MRF or the ”moralized” directedgraphZemel & Urtasun (UofT)CSC 412Feb 9, 201629 / 56

Elimination as Graph TransformationWhen a variable X is eliminated:We create a single factor ψ that contains X and all of the variables Y withwhich it appears in factors.We eliminate X from ψ, replacing it with a new factor τ that contains all ofthe variables Y, but not X . Let’s call this ΦX .How does this modify the graph from GΦ to GΦX ?Constructing ψ generates edges between all of the variables Y Y.Some of these edges were in GΦ , some are new.The new edges are called fill edges.The step of removing X from φ to construct τ removes X and all it’sincident edges from the graph.Zemel & Urtasun (UofT)CSC 412Feb 9, 201630 / 56

ExampleZemel & Urtasun (UofT)(Graph)(Elim. C )(Elim. D)(Elim. I )CSC 412Feb 9, 201631 / 56

Induced GraphWe can summarize the computation cost using a single graph that is theunion of all the graphs resulting from each step of the eliminationWe call this the induced graph IΦ, where is the elimination orderingNmax is the size of the largest clique in IΦ, The running time is O(mk Nmax ), exponential in the size of the largest cliqueof the induced graphZemel & Urtasun (UofT)CSC 412Feb 9, 201632 / 56

Example(Induced graph)Zemel & Urtasun (UofT)(Maximal Cliques)CSC 412Feb 9, 201633 / 56

Example(Maximal Cliques)(VE)The maximal cliques in IG, areZemel & Urtasun (UofT)C1 {C , D}C2 {D, I , G }C3 {G , L, S, J}C4 {G , J, H}CSC 412Feb 9, 201634 / 56

Induced WidthThe width of an induced graph is #nodes in the largest clique -1.We define the induced width wG, to be the width of the graph IG, induced by applying VE to G using ordering .We define the tree width or minimal induced width of a graph K to bewG min w (IK, ) The treewidth provides a bound on the best running time achievable by VE on a distribution that factorizes over G: O(mk wG 1 )Finding the best elimination ordering (also computing the tree width) isNP-hardUse heuristics to find a good elimination orderingZemel & Urtasun (UofT)CSC 412Feb 9, 201635 / 56