DOC PREVIEW
CMU CS 10708 - Learning P-maps Param. Learning

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Learning P-maps Param. LearningPerfect maps (P-maps)Inexistence of P-maps 1Obtaining a P-mapI-EquivalenceSkeleton of a BNWhat about V-structures?Same V-structures not necessaryImmoralities & I-EquivalenceSlide 10Identifying 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 23Maximum 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 CPTCan we really trust MLE?Bayesian LearningBayesian Learning for ThumbtackBeta prior distribution – P()Posterior distributionConjugate priorUsing Bayesian posteriorBayesian prediction of a new coin flipAsymptotic behavior and equivalent sample sizeBayesian learning corresponds to smoothingBayesian learning for multinomialBayesian learning for two-node BNVery important assumption on prior: Global parameter independenceGlobal parameter independence, d-separation and local predictionWithin a CPTPriors for BN CPTs (more when we talk about structure learning)An exampleWhat you need to know about parameter learning1Learning P-mapsParam. LearningGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversitySeptember 24th, 2008Readings:K&F: 3.3, 3.4, 16.1, 16.2, 16.3, 16.410-708 – Carlos Guestrin 2006-200810-708 – Carlos Guestrin 2006-20082Perfect maps (P-maps)I-maps are not unique and often not simple enoughDefine “simplest” G that is I-map for PA 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 2006-20083Inexistence of P-maps 1XOR (this is a hint for the homework)10-708 – Carlos Guestrin 2006-20084Obtaining a P-mapGiven the independence assertions that are true for PAssume 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 2006-20085I-EquivalenceTwo graphs G1 and G2 are I-equivalent if I(G1) = I(G2)Equivalence class of BN structuresMutually-exclusive and exhaustive partition of graphsHow do we characterize these equivalence classes?10-708 – Carlos Guestrin 2006-20086Skeleton of a BNSkeleton 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 2006-20087What about V-structures?V-structures are key property of BN structureTheorem: If G1 and G2 have the same skeleton and V-structures, then G1 and G2 are I-equivalentAHCEGDBFKJI10-708 – Carlos Guestrin 2006-20088Same V-structures not necessaryTheorem: If G1 and G2 have the same skeleton and V-structures, then G1 and G2 are I-equivalentThough sufficient, same V-structures not necessary10-708 – Carlos Guestrin 2006-20089Immoralities & I-EquivalenceKey concept not V-structures, but “immoralities” (unmarried parents )X ! Z  Y, with no arrow between X and YImportant 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 2006-200810Obtaining a P-mapGiven the independence assertions that are true for PObtain skeletonObtain immoralitiesFrom skeleton and immoralities, obtain every (and any) BN structure from the equivalence class10-708 – Carlos Guestrin 2006-200811Identifying the skeleton 1When is there an edge between X and Y?When is there no edge between X and Y?10-708 – Carlos Guestrin 2006-200812Identifying the skeleton 2Assume d is max number of parents (d could be n)For each Xi and XjEij  trueFor each U X – {Xi,Xj}, |U|≤dIs (Xi  Xj | U) ?Eij  falseIf Eij is trueAdd edge X – Y to skeleton10-708 – Carlos Guestrin 2006-200813Identifying immoralitiesConsider 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 Z2UMust 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 2006-200814From immoralities and skeleton to BN structuresRepresenting BN equivalence class as a partially-directed acyclic graph (PDAG)Immoralities force direction on some other BN edgesFull (polynomial-time) procedure described in reading10-708 – Carlos Guestrin 2006-200815What you need to knowMinimal I-map every P has one, but usually manyPerfect mapbetter choice for BN structurenot every P has onecan find one (if it exists) by considering I-equivalenceTwo structures are I-equivalent if they have same skeleton and immoralitiesAnnouncementsRecitation tomorrowDon’t miss it!No class on Monday 1610-708 – Carlos Guestrin 2006-200810-708 – Carlos Guestrin 2006-200817ReviewBayesian Networks Compact representation for probability distributionsExponential reduction in number of parametersExploits independencies Next – Learn BNsparametersstructureFluAllergySinusHeadacheNose10-708 – Carlos Guestrin 2006-200818Thumbtack – Binomial DistributionP(Heads) = , P(Tails) = 1-Flips are i.i.d.:Independent eventsIdentically distributed according to Binomial distributionSequence D of H Heads and T Tails10-708 – Carlos Guestrin 2006-200819Maximum Likelihood EstimationData: Observed set D of H Heads and T Tails Hypothesis: Binomial distribution Learning is an optimization problemWhat’s the objective function?MLE: Choose  that maximizes the probability of observed data:10-708 – Carlos Guestrin 2006-200820Your first learning algorithmSet derivative to zero:10-708 – Carlos Guestrin 2006-200821Learning Bayes netsKnown structure Unknown structureFully observable dataMissing datax(1)… x(m)Datastructure parametersCPTs


View Full Document

CMU CS 10708 - Learning P-maps Param. Learning

Documents in this Course
Lecture

Lecture

15 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

causality

causality

53 pages

lecture11

lecture11

16 pages

Exam

Exam

15 pages

Notes

Notes

12 pages

lecture

lecture

18 pages

lecture

lecture

16 pages

Lecture

Lecture

17 pages

Lecture

Lecture

15 pages

Lecture

Lecture

17 pages

Lecture

Lecture

19 pages

Lecture

Lecture

42 pages

Lecture

Lecture

16 pages

r6

r6

22 pages

lecture

lecture

20 pages

lecture

lecture

35 pages

Lecture

Lecture

19 pages

Lecture

Lecture

21 pages

lecture

lecture

21 pages

lecture

lecture

13 pages

review

review

50 pages

Semantics

Semantics

30 pages

lecture21

lecture21

26 pages

MN-crf

MN-crf

20 pages

hw4

hw4

5 pages

lecture

lecture

12 pages

Lecture

Lecture

25 pages

Lecture

Lecture

25 pages

Lecture

Lecture

14 pages

Lecture

Lecture

15 pages

Load more
Download Learning P-maps Param. Learning
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Learning P-maps Param. Learning and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Learning P-maps Param. Learning 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?