关闭

关闭

关闭

封号提示

内容

首页 An Introduction to Probabilistic Graphical Mode…

An Introduction to Probabilistic Graphical Models .pdf

An Introduction to Probabilisti…

上传者: 书剑飘零 2010-12-01 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《An Introduction to Probabilistic Graphical Models pdf》,可适用于人文社科领域,主题内容包含PROBABILISTICGRAPHICALMODELSDavidMadiganRutgersUniversitymadiganstatrutger符等。

PROBABILISTICGRAPHICALMODELSDavidMadiganRutgersUniversitymadiganstatrutgerseduExpertSystems•Explosionofinterestin“ExpertSystems”intheearly’sIFtheinfectionisprimarybacteremiaANDthesiteofthecultureisoneofthesterilesitesANDthesuspectedportalofentryisthegastrointestinaltractTHENthereissuggestiveevidence()thatinfectionisbacteroid•Manycompanies(Teknowledge,IntelliCorp,Inference,etc),manyIPO’s,muchmediahype•AdhocuncertaintyhandlingUncertaintyinExpertSystemsIfAthenC(p)IfBthenC(p)WhatifbothAandBtrueThenCtruewithCF:p(pX(p))“Currentlyfashionableadhocmumbojumbo”AFMSmithEschewedProbabilisticApproach•Computationallyintractable•Inscrutable•Requiresvastamountsofdataelicitationeg,forndichotomousvariablesneednprobabilitiestofullyspecifythejointdistributionConditionalIndependenceXY|Z)|()|()|,(|||,zyfzxfzyxfZYZXZYX=!ConditionalIndependence•SupposeAandBaremarginallyindependentPr(A),Pr(B),Pr(C|AB)X=probabilities•SupposeAandCareconditionallyindependentgivenB:Pr(A),Pr(B|A)X,Pr(C|B)X=•ChainwithvariablesrequiresprobabilitiesversusABCCA|BPropertiesofConditionalIndependence(Dawid,)CI:ABPBAPCI:ABCPABPCI:ABCPAB|CPCI:ABandAC|BPABCPForanyprobabilitymeasurePandrandomvariablesA,B,andC:Someprobabilitymeasuresalsosatisfy:CI:AB|CandAC|BPABCPCIsatisfiedwheneverPhasapositivejointprobabilitydensitywithrespecttosomeproductmeasureMarkovPropertiesforUndirectedGraphsXXXXX(Global)SseparatesAfromBAB|S(Local)αVcl(α)|bd(α)(Pairwise)αβ|V{α,β}(G)(L)(P)XX,X|X,X()XX|X,X,X()Togofrom()to()needXX|X,XorCILauritzen,Dawid,LarsenLeimer()FactorizationsAdensityfissaidto“factorizeaccordingtoG”if:f(x)=ΠψC(xC)CεCProposition:IfffactorizesaccordingtoaUGG,thenitalsoobeystheglobalMarkovproperty“Proof”:LetSseparateAfromBinGandassumeLetCAbethesetofcliqueswithnonemptyintersectionwithASinceSseparatesAfromB,wemusthaveforallCinCAThen:“cliquepotentials”•cliquesaremaximallycompletesubgraphsSBAV!!=!="CB)()()()()(SBSACCCCCCCCCxfxfxxxfAA!!""==##$$MarkovPropertiesforAcyclicDirectedGraphs(BayesianNetworks)XX(Global)SseparatesAfromBinGan(A,B,S)mAB|S(Local)αnd(α)pa(α)|pa(α)(G)(L)Lauritzen,Dawid,LarsenLeimer()XXXXFactorizationsADGGlobalMarkovPropertyf(x)=Πf(xv|xpa(v))vεVAdensityfadmitsa“recursivefactorization”accordingtoanADGGiff(x)=Πf(xv|xpa(v))Lemma:IfPadmitsarecursivefactorizationaccordingtoanADGG,thenPfactorizesaccordingGM(andchordalsupergraphsofGM)Lemma:IfPadmitsarecursivefactorizationaccordingtoanADGG,andAisanancestralsetinG,thenPAadmitsarecursivefactorizationaccordingtothesubgraphGAFactorizationsDBACEFGHSp(A,B,C,D,E,F,G,H,S)=p(A)p(C|A)p(D|C)p(S|D,F)p(E|S)p(F|G)p(G|B)p(H|S,B)p(B)p(S|A,B,C,D,E,F,G,H)p(S|D,F)p(E|S)p(H|S,B){D,F,W,H,B}isthe“MarkovBlanket”ofSItcontainstheparentsofS,thechildrenofS,andtheotherparentsofthechildrenofSMarkovPropertiesforAcyclicDirectedGraphs(BayesianNetworks)(Global)SseparatesAfromBinGan(A,B,S)mAB|S(Local)αnd(α)pa(α)|pa(α)(G)(L)αnd(α)isanancestralsetpa(α)obviouslyseparatesαfromnd(α)pa(α)inGan(αnd(α))m(L)(factorization)inductiononthenumberofverticesdseparationAchainπfromatobinanacyclicdirectedgraphGissaidtobeblockedbySifitcontainsavertexγπsuchthateither:γSandarrowsofπdonotmeetheadtoheadatγ,orγSnorhasγanydescendentsinS,andarrowsofπdomeetheadtoheadatgTwosubsetsAandBaredseparatedbySifallchainsfromAtoBareblockedbySdseparationandglobalmarkovpropertyLetA,B,andSbedisjointsubsetsofadirected,acyclicgraph,GThenSdseparatesAfromBifandonlyifSseparatesAfromBinGan(A,B,S)mUG–ADGIntersectionACBABCABCACCA|BAC|BACDABCAB|C,DCD|A,BAC|BBABCAC|BUG–ADGIntersectionUGADGDecomposable•UGisdecomposableifchordal•ADGisdecomposableifmoral•Decomposable~closedformloglinearmodelsNoCIChordalGraphsandRIP•Chordalgraphs(uniquely)admitcliqueorderingsthathavetheRunningIntersectionPropertyTVLAXDBS{V,T}{A,L,T}{L,A,B}{S,L,B}{A,B,D}{A,X}•Theintersectionofeachsetwiththoseearlierinthelistisfullycontainedinpreviousset•Cancomputecondprobabilities(egPr(X|V))bymessagepassing(LauritzenSpiegelhalter,Dawid,Jensen)ProbabilisticExpertSystem•Computationallyintractable•Inscrutable•Requiresvastamountsofdataelicitation•ChordalUGmodelsfacilitatefastinference•ADGmodelsbetterforexpertsystemapplications–morenaturaltospecifyPr(v|pa(v))FactorizationsUGGlobalMarkovPropertyf(x)=ΠψC(xC)CεCADGGlobalMarkovPropertyf(x)=Πf(xv|xpa(v))vεVLauritzenSpiegelhalterAlgorithmBASCDψ(C,S,D)Pr(S|C,D)ψ(A,E)Pr(E|A)Pr(A)ψ(C,E)Pr(C|E)ψ(F,D,B)Pr(D|F)Pr(B|F)Pr(F)ψ(D,B,S)ψ(B,S,G)Pr(G|S,B)ψ(H,S)Pr(H|S)AlgorithmiswidelydeployedincommercialsoftwareEFGHBASCDEFGH•Moralize•TriangulateLSToyExampleABCPr(C|B)=Pr(C|B)=Pr(B|A)=Pr(B|A)=Pr(A)=ψ(A,B)Pr(B|A)Pr(A)ψ(B,C)Pr(C|B)ABCABBBCABABBCBCBBMessageSchedule:ABBCBCABBBBCBCBCBCPr(A|C)OtherTheoreticalDevelopmentsDotheUGandADGglobalMarkovpropertiesidentifyalltheconditionalindependencesimpliedbythecorrespondingfactorizationsYesCompletenessforADGsbyGeigerandPearl()forUGsbyFrydenberg()Graphicalcharacterizationofcollapsibilityinhierarchicalloglinearmodels(AsmussenandEdwards,)CollapsibilityCareLessSurvivalNoYesMoreCareLessSurvivalNoYesMoreClinicAClinicBCareLessSurvivalNoYesMorePooledCollapsibilityCareClinicSurvTheorem:AgraphicalloglinearmodelLiscollapsibleontoAiffeveryconnectedcomponentofAciscompleteBayesianLearningforDiscreteADG’s•Example:threebinaryvariables•Fiveparameters:LocalandGlobalIndependenceBayesianlearningConsideraparticularstatepa(v)ofpa(v)•ADGmodelsforafixedsetofverticesdecomposeintoMarkovequivalenceclasses:ABCABCABCAC|BAD|B,CBC|AacbdacbdacbdDDDacbdDAD|B,CBCEquivalenceClassesandChainGraphs•RepeatinganalysesforequivalentADGsleadstosignificantcomputationalinefficiencies•EnsuringthatequivalentADGshaveequalposteriorprobabilitiesimposessevereconstraintsonpriordistributions(GeigerandHeckerman,)•BayesianmodelaveragingproceduresthataverageacrossADGsassignweightstostatisticalmodelsthatareproportionaltoequivalenceclasssizesWhyisthisaproblemTheorem(VermaPearl,Glymouretal,Frydenberg,AMP):TwoADGsareMarkovequivalentifftheyhavethesameskeletonsandthesameimmoralitiesDefinitionTheessentialgraphD*associatedwithDisthegraphD*:=(D’|D’~D),acbdacbdacbdEquivalenceClassCharacterizationacbdacbdacbdDDDEssentialGraphsAMP()•Essentialgraphsarechaingraphs•D*istheuniquesmallestchaingraphMarkovequivalenttoD•AgraphG=(V,E)isequaltoD*forsomeADGDifandonlyifGsatisfiesthefollowingfourconditions:(i)Gisachaingraph(ii)ForeverychaincomponenttofG,Gtischordal(iii)TheconfigurationabcdoesnotoccurasaninducedsubgraphofG(iv)EveryarrowabGisstronglyprotectedinG:abc(a)abc(b)abc(c)abc(d)c(c!c)alsoMeek()andChickering()What’saChainGraph“Equivalence”:a~biffabChainComponents(“Boxes”)ChainGraphsUGADGDecomposable•ChaingraphMarkovproperty,Frydenberg()•Equivalenceresults(LWF,AMP,Meek,Studeny)CGACDCD|A,BBCD|AorCoxWermuth()

用户评论(2)

0/200
  • 嚼茶 2013-06-21 16:57:26

    确实是ppt,后悔没看评论就下载

  • summerice9 2011-04-08 08:04:50

    这个是介绍图模型的PPT,不是书

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/35
1下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部