BN Semantics 3 – Now it’s personal! Parameter Learning 1Building BNs from independence propertiesMinimal I-mapsObtaining a minimal I-mapMinimal I-map not unique (or minimal)Perfect maps (P-maps)Inexistence of P-maps 1Inexistence of P-maps 2Obtaining a P-mapI-EquivalenceSkeleton of a BNWhat about V-structures?Same V-structures not necessaryImmoralities & I-EquivalenceSlide 15Identifying the skeleton 1Identifying the skeleton 2Identifying immoralitiesFrom immoralities and skeleton to BN structuresWhat you need to knowAnnouncementsReviewThumbtack – Binomial DistributionMaximum Likelihood EstimationYour first learning algorithmLearning Bayes netsLearning the CPTsSlide 28Maximum likelihood estimation (MLE) of BN parameters – exampleMaximum likelihood estimation (MLE) of BN parameters – General caseTaking derivatives of MLE of BN parameters – General caseGeneral MLE for a CPTParameter sharing (basics now, more later in the semester)Using recommender systemLearning parameters of recommender system BNParameter sharing for recommender system BNMLE with simple parameter sharingWhat you need to know about learning BNs thus far1BN Semantics 3 – Now it’s personal!Parameter Learning 1Graphical Models – 10708Carlos GuestrinCarnegie Mellon UniversitySeptember 22nd, 2006Readings:K&F: 3.4, 14.1, 14.210-708 – Carlos Guestrin 20062 Building BNs from independence propertiesFrom d-separation we learned:Start from local Markov assumptions, obtain all independence assumptions encoded by graphFor most P’s that factorize over G, I(G) = I(P)All of this discussion was for a given G that is an I-map for PNow, give me a P, how can I get a G?i.e., give me the independence assumptions entailed by PMany G are “equivalent”, how do I represent this?Most of this discussion is not about practical algorithms, but useful concepts that will be used by practical algorithmsPractical algs next week10-708 – Carlos Guestrin 20063 Minimal I-mapsOne option: G is an I-map for PG is as simple as possibleG is a minimal I-map for P if deleting any edges from G makes it no longer an I-map10-708 – Carlos Guestrin 20064 Obtaining a minimal I-mapGiven a set of variables and conditional independence assumptionsChoose an ordering on variables, e.g., X1, …, Xn For i = 1 to nAdd Xi to the networkDefine parents of Xi, PaXi, in graph as the minimal subset of {X1,…,Xi-1} such that local Markov assumption holds – Xi independent of rest of {X1,…,Xi-1}, given parents PaXiDefine/learn CPT – P(Xi| PaXi)Flu, Allergy, SinusInfection, Headache10-708 – Carlos Guestrin 20065 Minimal I-map not unique (or minimal)Given a set of variables and conditional independence assumptionsChoose an ordering on variables, e.g., X1, …, Xn For i = 1 to nAdd Xi to the networkDefine parents of Xi, PaXi, in graph as the minimal subset of {X1,…,Xi-1} such that local Markov assumption holds – Xi independent of rest of {X1,…,Xi-1}, given parents PaXiDefine/learn CPT – P(Xi| PaXi)Flu, Allergy, SinusInfection, Headache10-708 – Carlos Guestrin 20066 Perfect maps (P-maps)I-maps are not unique and often not simple enoughDefine “simplest” G that is I-map for PA BN structure G is a perfect map for a distribution P if I(P) = I(G) Our goal:Find a perfect map!Must address equivalent BNs10-708 – Carlos Guestrin 20067 Inexistence of P-maps 1XOR (this is a hint for the homework)10-708 – Carlos Guestrin 20068 Inexistence of P-maps 2(Slightly un-PC) swinging couples example10-708 – Carlos Guestrin 20069 Obtaining a P-mapGiven the independence assertions that are true for PAssume that there exists a perfect map G*Want to find G*Many structures may encode same independencies as G*, when are we done?Find all equivalent structures simultaneously!10-708 – Carlos Guestrin 200610 I-EquivalenceTwo graphs G1 and G2 are I-equivalent if I(G1) = I(G2)Equivalence class of BN structuresMutually-exclusive and exhaustive partition of graphsHow do we characterize these equivalence classes?10-708 – Carlos Guestrin 200611 Skeleton of a BNSkeleton of a BN structure G is an undirected graph over the same variables that has an edge X–Y for every X!Y or Y!X in G(Little) Lemma: Two I-equivalent BN structures must have the same skeletonAHCEGDBFKJI10-708 – Carlos Guestrin 200612 What about V-structures?V-structures are key property of BN structureTheorem: If G1 and G2 have the same skeleton and V-structures, then G1 and G2 are I-equivalentAHCEGDBFKJI10-708 – Carlos Guestrin 200613 Same V-structures not necessaryTheorem: If G1 and G2 have the same skeleton and V-structures, then G1 and G2 are I-equivalentThough sufficient, same V-structures not necessary10-708 – Carlos Guestrin 200614 Immoralities & I-EquivalenceKey concept not V-structures, but “immoralities” (unmarried parents )X ! Z à Y, with no arrow between X and YImportant pattern: X and Y independent given their parents, but not given Z(If edge exists between X and Y, we have covered the V-structure)Theorem: G1 and G2 have the same skeleton and immoralities if and only if G1 and G2 are I-equivalent10-708 – Carlos Guestrin 200615 Obtaining a P-mapGiven the independence assertions that are true for PObtain skeletonObtain immoralitiesFrom skeleton and immoralities, obtain every (and any) BN structure from the equivalence class10-708 – Carlos Guestrin 200616 Identifying the skeleton 1When is there an edge between X and Y?When is there no edge between X and Y?10-708 – Carlos Guestrin 200617 Identifying the skeleton 2Assume d is max number of parents (d could be n)For each Xi and XjEij à trueFor each Uµ X – {Xi,Xj}, |U|· 2dIs (Xi Xj | U) ?Eij à trueIf Eij is trueAdd edge X – Y to skeleton10-708 – Carlos Guestrin 200618 Identifying immoralitiesConsider X – Z – Y in skeleton, when should it be an immorality?Must be X ! Z à Y (immorality):When X and Y are never independent given U, if Z2UMust not be X ! Z à Y (not immorality):When there exists U with Z2U, such that X and Y are independent given U10-708 – Carlos Guestrin 200619 From immoralities and skeleton to BN structuresRepresenting BN equivalence class as a partially-directed acyclic graph (PDAG)Immoralities force
View Full Document
Unlocking...