UIUC CS 598: Section EA Graphical ModelsTodayIndependent Random VariablesBayes’ TheoremConditional IndependenceExample: Family treesMarkov AssumptionMarkov Assumption ExampleI-MapsFactorizationFactorization TheoremFactorization ExampleConsequencesSummaryConditional IndependenciesProof (Outline)Implied Independenciesd-seperationPathsSlide 20Path BlockageSlide 22Slide 23Path Blockage -- General Cased-SeparationExampleSlide 27Slide 28SoundnessCompletenessSummary: StructureInferenceQueries: LikelihoodQueries: A posteriori beliefA posteriori beliefVariable EliminationSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Complexity of InferenceSlide 47Approaches to inferenceMarkov Network (Undirected Graphical Models)Complexity of variable eliminationUndirected graph representationConstructing the Moral GraphConstructing The Moral GraphSlide 54Chordal GraphsInduced WidthPolyTreesJunction TreeProperties of Junction TreeSlide 60PotentialsSlide 62Building Junction TreesTriangulatingIdentifying CliquesSlide 66Principle of InferenceExample: Create Join TreeExample: InitializationExample: Collect EvidenceExample: Collect Evidence (cont.)Example: Distribute EvidenceExample: Distribute Evidence (cont.)Example: Inference with evidenceExample: Inference with evidence (cont.)UIUC CS 598: Section EAGraphical ModelsDeepak RamachandranFall 2004(Based on slides by Eyal Amir (which were based on slides by Lise Getoor and Alvaro Cardenas (UMD) (in turn based on slides by Nir Friedman (Hebrew U)))Today1. Probabilistic graphical models2. Inference3. Junction TreesIndependent Random Variables•Two variables X and Y are independent if–P(X = x|Y = y) = P(X = x) for all values x,y–That is, learning the values of Y does not change prediction of X•If X and Y are independent then –P(X,Y) = P(X|Y)P(Y) = P(X)P(Y)•In general, if X1,…,Xp are independent, then P(X1,…,Xp)= P(X1)...P(Xp)–Requires O(n) parametersBayes’ TheoremGives us a way to compute Posterior Probabilities:P(X|Y)P(Y) = P(X, Y) = P(Y|X)P(X)Therefore, P(X|Y) = P(Y|X)P(X) P(Y)P(X) – prior , P(Y) – evidence, P(X|Y)- posteriorConditional Independence•Unfortunately, most random variables of interest are not independent of each other•A more suitable notion is that of conditional independence•Two variables X and Y are conditionally independent given Z if–P(X = x|Y = y,Z=z) = P(X = x|Z=z) for all values x,y,z–That is, learning the values of Y does not change prediction of X once we know the value of Z–notation: I ( X , Y | Z )Modeling assumptions:Ancestors can effect descendants' genotype only by passing genetic materials through intermediate generationsExample: Family treesNoisy stochastic process:Example: Pedigree•A node represents an individual’sgenotypeHomerBartMargeLisa MaggieMarkov Assumption•We now make this independence assumption more precise for directed acyclic graphs (DAGs)•Each random variable X, is independent of its non-descendents, given its parents Pa(X)•Formally,I (X, NonDesc(X) | Pa(X))DescendentAncestorParentNon-descendentXY1Y2Non-descendentMarkov Assumption Example•In this example:–I ( E, B )–I ( B, {E, R} )–I ( R, {A, B, C} | E )–I ( A, R | B,E )–I ( C, {B, E, R} | A)EarthquakeRadioBurglaryAlarmCallI-Maps•A DAG G is an I-Map of a distribution P if all Markov assumptions implied by G are satisfied by P(Assuming G and P both use the same set of random variables)Examples:X Yx y P(x,y)0 0 0.250 1 0.251 0 0.251 1 0.25X Yx y P(x,y)0 0 0.20 1 0.31 0 0.41 1 0.1Factorization•Given that G is an I-Map of P, can we simplify the representation of P?•Example: •Since I(X,Y), we have that P(X|Y) = P(X)•Applying the chain ruleP(X,Y) = P(X|Y) P(Y) = P(X) P(Y)•Thus, we have a simpler representation of P(X,Y)X YFactorization TheoremFrom assumption: )X(NonDesc)X(Pa}X,X{}X,X{)X(Paii1i,11i,1iiiip1))X(Pa|X(P)X,...,X(PThm: if G is an I-Map of P, theni1i1ip1)X,...,X|X(P)X,...,X(PProof:• By chain rule:• wlog. X1,…,Xp is an ordering consistent with G• Since G is an I-Map, I (Xi, NonDesc(Xi)| Pa(Xi))• We conclude, P(Xi | X1,…,Xi-1) = P(Xi | Pa(Xi) )))X(Pa|)X(Pa}X,X{,X(Iii1i,1i• Hence,Factorization ExampleP(C,A,R,E,B) = P(B)P(E|B)P(R|E,B)P(A|R,B,E)P(C|A,R,B,E)EarthquakeRadioBurglaryAlarmCallversusP(C,A,R,E,B) = P(B) P(E) P(R|E) P(A|B,E) P(C|A)Consequences•We can write P in terms of “local” conditional probabilitiesIf G is sparse,– that is, |Pa(Xi)| < k , each conditional probability can be specified compactly–e.g. for binary variables, these require O(2k) params. representation of P is compact–linear in number of variablesSummaryWe defined the following concepts• The Markov Independences of a DAG G–I (Xi , NonDesc(Xi) | Pai )•G is an I-Map of a distribution P–If P satisfies the Markov independencies implied by GWe proved the factorization theorem•if G is an I-Map of P, theniiin1)Pa|X(P)X,...,X(P•Let Markov(G) be the set of Markov Independencies implied by G•The factorization theorem showsG is an I-Map of P •We can also show the opposite:Thm: G is an I-Map of PConditional IndependenciesiiinPaXPXXP )|(),...,(1iiinPaXPXXP )|(),...,(1Proof (Outline)Example:XYZ)|()()|()|()(),(),,(),|(XYPXPXZPXYPXPYXPZYXPYXZP )|( XZPImplied Independencies•Does a graph G imply additional independencies as a consequence of Markov(G)?•We can define a logic of independence statements•Some axioms:–I( X ; Y | Z ) I( Y; X | Z )–I( X ; Y1, Y2 | Z ) I( X; Y1 | Z )d-seperation•A procedure d-sep(X; Y | Z, G) that given a DAG G, and sets X, Y, and Z returns either yes or no•Goal: d-sep(X; Y | Z, G) = yes iff I(X;Y|Z) follows from Markov(G)Paths•Intuition: dependency must “flow” along paths in the graph•A path is a sequence of neighboring variablesExamples:•R E A B•C A E REarthquakeRadioBurglaryAlarmCallPaths•We want to know when a path is–active -- creates dependency between end nodes–blocked -- cannot create dependency end nodes•We want to classify situations in which paths are active.BlockedUnblockedERAERAPath BlockageThree cases:–Common cause– – BlockedActiveBlockedUnblockedECAECAPath BlockageThree cases:–Common cause–Intermediate cause– BlockedActiveBlockedUnblockedEBACEBACEBACPath BlockageThree cases:–Common cause–Intermediate cause–Common EffectBlockedActivePath Blockage -- General
View Full Document
Unlocking...