关闭

关闭

关闭

封号提示

内容

首页 An Introduction to Probabilistic Graphical Model…

An Introduction to Probabilistic Graphical Models .pdf

An Introduction to Probabilisti…

书剑飘零
2010-12-01 0人阅读 0 0 0 暂无简介 举报

简介:本文档为《An Introduction to Probabilistic Graphical Models pdf》,可适用于人文社科领域

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:ABP⇒BAPCI:AB∪CP⇒ABPCI:AB∪CP⇒AB|CPCI:ABandAC|BP⇒AB∪CPForanyprobabilitymeasurePandrandomvariablesA,B,andC:Someprobabilitymeasuresalsosatisfy:CI:AB|CandAC|BP⇒AB∪CPCIsatisfiedwheneverPhasapositivejointprobabilitydensitywithrespecttosomeproductmeasureMarkovPropertiesforUndirectedGraphsXXXXX(Global)SseparatesAfromB⇒AB|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)m⇒AB|S(Local)αnd(α)pa(α)|pa(α)(G)⇔(L)Lauritzen,Dawid,LarsenLeimer()XXXXFactorizationsADGGlobalMarkovProperty⇔f(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)m⇒AB|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))FactorizationsUGGlobalMarkovProperty⇔f(x)=ΠψC(xC)CεCADGGlobalMarkovProperty⇔f(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)ABCABBBCAB¬A¬BBC¬B¬CB¬BMessageSchedule:ABBCBCABB¬BBC¬B¬CBC¬B¬CPr(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)Theconfigurationa→bcdoesnotoccurasaninducedsubgraphofG(iv)Everyarrowa→b∈GisstronglyprotectedinG: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)

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

    2013-06-21 16:57:26

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

    2011-04-08 08:04:50

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/35

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料