Clique TreesAmr AhmedOctober 23, 2008Outline• Clique Trees• Representation• Factorization•Inference•Inference• Relation with VERepresentation• Given a Probability distribution, P– How to represent it?– What does this representation tell us about P?•Cost of inference•Cost of inference• Independence relationships– What are the options?• Full CPT• Bayes Network (list of factors)• Clique TreeRepresentation• FULL CPT– Space is exponential– Inference is exponential–Can read nothingabout independence in P–Can read nothingabout independence in P– Just badRepresentation: the past• Bayes Network– List of Factors: P(Xi|Pa(Xi))• Space efficient– Independence•Read local Markov Ind.•Read local Markov Ind.• Compute global independence via d-seperation– Inference• Can use dynamic programming by leveraging factors• Tell us little immediately about cost of inference– Fix an elimination order– Compute the induced graph– Find the largest clique size» Inference is exponential in this largest clique sizeRepresentation: Today• Clique Trees (CT)– Tree of cliques– Can be constructed from Bayes network•Bayes Network + Elimination order CT•Bayes Network + Elimination order CT– What independence can read from CT about P?– How P factorizes over CT?– How to do inference using CT?– When should you use CT?The Big PictureFull CPTDifficultySATGradeCoherenceLetterIntelligenceList of local factorsTree of Cliques manyPDAG,manyChoose an Inference is Just summationHappyJobLetterVE operates in factors by caching computations (intermediate factors) within a single inference operation P(X|E)CT enables caching computations (intermediate factors) across multiple inference operations P(Xi,Xj) for all I,jPDAG,MinimalI-MAP,etcChoose an Elimination order,Max-spaning treeClique Trees: Representation• For set of factors F (i.e. Bayes Net)– Undirected graph– Each node i associated with a cluster Ci–Family preserving: for each factor f∈F, ∃node i–Family preserving: for each factor fj∈F, ∃node isuch that scope[fi] ⊆ Ci– Each edge i – j is associated with a separator Sij= Ci∩ CjClique Trees: Representation• Family preserving over factors• Running Intersection Property• Both are correct Clique treesDifficultySATGradeHappyJobCoherenceLetterIntelligenceCD GDIS G L J S H J GClique Trees: Representation• What independence can be read from CT– I(CT) subset I(G) subset I(P)• Use your intuition–How to block a path?DifficultySATGradeCoherenceIntelligence–How to block a path?• Observe a separator. Q4SATGradeHappyJobLetterGIHJCDSGIHJGIHDGC|,|,||⊥⊥⊥⊥Clique Trees: Representation• How P factorizes over CT (when CT is calibrated) Q4 (See 9.2.11) DifficultySATGradeHappyJobCoherenceLetterIntelligenceRepresentation Summary• Clique trees (like Bayes Net) has two parts– Structure– Potentials (the parallel to CPTs in BN)• Clique potentials• Separator Potential• Upon calibration, you can read marginals from the cliques and separator potentials• Initialize clique potentials with factors from BN–Distribute factors over cliques (family preserving)–Distribute factors over cliques (family preserving)– Cliques must satisfy RIP• But wee need calibration to reach a fixed point of these potentials (see later today)• Compare to BN– You can only read local conditionals P(xi|pa(xi)) in BN• You need VE to answer other queries– In CT, upon calibration, you can read marginals over cliques• You need VE over calibrated CT to answer queries whose scope can not be confined to a single cliqueClique tree Construction• Replay VE• Connect factors that would be generated if you DifficultySATGradeCoherenceLetterIntelligencegenerated if you run VE with this order• Simplify!– Eliminate factor that is subset of neighborHappyJobClique tree Construction (details)• Replay VE with order: C,D,I,H,S, L,J,GDifficultySATGradeHappyJobCoherenceLetterIntelligenceInitial factors: C, DC, GDI, SI, I, LG, JLS, HJGEliminate C: multiply CD, C to get factor with CD, then marginalize CTo get a factor with D. C CD DEliminate D: multiply D, GDI to get factor with GDI, then marginalize Eliminate D: multiply D, GDI to get factor with GDI, then marginalize D to get a factor with GI C CD D DGI GIEliminate I: multiply GI, SI, I to get factor with GSI, then marginalize I to get a factor with GS C CD D DGI GIGSIISIGSClique tree Construction (details)• Replay VE with order: C,D,I,H,S, L,J,GDifficultySATGradeHappyJobCoherenceLetterIntelligenceInitial factors: C, DC, GDI, SI, I, LG, JLS, HJGEliminate I: multiply GI, SI, I to get factor with GSI, then marginalize I to get a factor with GS C CD D DGI GIGSI GSISIEliminate H: just marginalize HJG to get a factor with JG C CD D DGI GIGSIISIGSHJGJGClique tree Construction (details)• Replay VE with order: C,D,I,H,S, L,J,GDifficultySATGradeHappyJobCoherenceLetterIntelligenceInitial factors: C, DC, GDI, SI, I, LG, JLS, HJGEliminate H: just marginalize HJG to get a factor with JG C CD D DGI GIGSI GSHJGJGISIHJGJGEliminate S: multiply GS, JLS to get GJLS, then marginalize S to get GJLC CD D DGI GIGSIISIGSHJGJGJLSGJLS GJLClique tree Construction (details)• Replay VE with order: C,D,I,H,S, L,J,GDifficultySATGradeHappyJobCoherenceLetterIntelligenceInitial factors: C, DC, GDI, SI, I, LG, JLS, HJGEliminate S: multiply GS, JLS to get GJLS, then marginalize S to get GJLCCDDDGIGIGSIGSHJGJGGJLSGJLGSIISIGSHJGJGJLSGJLSGJLEliminate L: multiply GJL, LG to get JLG, then marginalize L to get GJC CD D DGI GIGSIISIGSHJGJGJLSGJLS GJLLGEliminate L, G: JG GGClique tree Construction (details)• Summarize CT by removing subsumed nodesC CD D DGI GIGSIISIGSHJGJGJLSGJLS GJLLGGCD GDI GSI G L J S H J G- Satisfy RIP and Family preserving (always true for any Elimination order)- Finally distribute initial factor into the cliques, to get initial beliefs (which is the parallel of CPTs in BN) , to be used for inferenceClique tree Construction: Another method• From a triangulated graph– Still from VE, why?– Elimination order triangulation–Triangulation Max cliques–Triangulation Max cliques– Connect cliques, find max-spanning treeClique tree Construction: Another method (details)• Get choral graph (add fill edges) for the same order as before C,D,I,H,S, L,J,G.• Extract Max cliques from this graph and get maximum-spanning clique
View Full Document
Unlocking...