概率图lesson01

1Addr:9-323Tel:[phone]Email:[e-mail]icGraphicalModelandItsApplications(32,2)2n()nnnn:PCAFAMRFHMMKalmanTurbo-codingnnn(Uncertainty)3()nnnnnnnnnnn4n:40%nn(project):60%nnnnToolsavailablenBayesNetToolbox(BNT)forMatlabn~murphyk/Software/BNT/bnt.htmlnPNL(ProbabilisticNetworkLibrary):AC++versionofBNTn…5nR.G.Cowell,A.P.Dawid,S.L.LauritzenandD.J.Spiegelhalter.ProbabilisticNetworksandExpertSystems.Springer-Verlag.1999.TP182FP96nProbablythebestbookavailable,althoughthetreatmentisrestrictedtoexactinference.nJ.Pearl.ProbabilisticReasoninginIntelligentSystems:NetworksofPlausibleInference.MorganKaufmann.1988.TP18FP35nThebookthatgotitallstarted!Averyinsightfulbook,stillrelevanttoday.6()nF.V.Jensen.BayesianNetworksandDecisionGraphs.Springer.2001.2-2002\O212.8\J54nProbablythebestintroductorybookavailable.nM.I.Jordan(ed).LearninginGraphicalModels.MITPress.1999.O157.5FL43nLoosecollectionofpapersonmachinelearning,manyrelatedtographicalmodels.Oneofthefewbookstodiscussapproximateinference.nS.Lauritzen.GraphicalModels.Oxford.1996.2-97\O21\L38nThedefinitivemathematicalexpositionofthetheoryofgraphicalmodels.7nSpecialIssueonNewComputationalParadigmsforAcousticModelinginSpeechRecognition.nComputerSpeech&Language,Volume:17,Issue:2-3,April-July2003.nSpecialIssueonGraphicalModelsinComputerVision.nIEEETransactionsonPatternAnalysisandMachineIntelligence,Volume:25,Issue:7,July2003.nSpecialIssueOnCodesOnGraphsAndIterativeAlgorithms.nIEEETransactionsonInformationTheory,Volume:47,Issue:2,Feb2001.n…8nnnCapitallettersX,Y,Z,Xi:discreteorcontinuousrandomvariables(r.v.)nLowercaselettersx,y,z,xi:theirparticularvalues(ingeneral,vectorsinavectorspace)nA,B,C:setsofintegers,e.g.A={1,2,3}=1:3nXA:asetofr.v.indexedbyA,e.g.XA={X1,X2,X3}=X1:39()nnnn(probabilitymassfunction,pmf)n(probabilitydensityfunction,pdf)()()pxpXx=@nLetX={X1,…,Xn}=X1:nbearandomvector.()()()111(,...,),...,nnnpxxpXxXxpXxpx======10()nnnnnx,y,z:p(x,y,z)nx:p(x)=ΣyΣzp(x,y,z)ßmarginalizationnp(x,y,z)=p(x)p(y|x)p(z|x,y)ßchainrule(factorization)n:()()()|(|)pxpyxpxypy=11()nnnnnnTwor.v.XandYareindependent(writtenX⊥Y)ifandonlyifp(x,y)=p(x)p(y)p(x|y)=p(x),p(y|x)=p(y)nX⊥Y|Z:p(x,y|z)=p(x|z)p(y|z)12()nnnnnn()nX(expectation)[]()()ifiscontinuousifisdiscretexxpxdxXEXxpxX⎧⋅⎪=⎨⋅⎪⎩∫∑n(covariancematrix)[][]()[]()[][]TTTCovXEXEXXEXEXXEXEX⎡⎤⎡⎤=--=-⎣⎦⎣⎦13()nnnnnn()nnnnn141.11.21.3151.11.21.31.116nn1.117nnn18xx⎛⎞⎜⎟⎜⎟⎜⎟⎝⎠M916xx⎛⎞⎜⎟⎜⎟⎜⎟⎝⎠M116xx⎛⎞⎜⎟⎜⎟⎜⎟⎝⎠M1.118n(W,X)nW:discreteclassvariable,W∈{1,…,m}nX:observationvariablenGiventheobservationX=x,howdowechoosethebestW?MAPMaximumAPosteriori∀xp(w|x)wnTominimizethenumberofclassificationerrors,pickw*=argmaxwp(w|x)Inferunknownclasslabelfromobservation1.119n(W,X)nW:discreteclassvariable,W∈{1:m}nX:observationvariablenGiventheobservationX=x,howdowechoosethebestW?nTominimizethenumberofclassificationerrors,pickw*=argmaxwp(w|x)np(w,x)Learningfromdata!n(W,X)Samples:(w(1),x(1)),…,(w(N),x(N))1.120nInference:Computep(HiddenRv|ObservedRv)usingmodelp(HiddenRv,ObservedRv)n:inferwordsfromacousticsßp(words|acoustics)n:infercleansig.fromnoisysig.ßp(|)n:p(|)n:p(UserTurnLeft|VideoInput)1.121nInference:Computep(HiddenRv|ObservedRv)usingmodelp(HiddenRv,ObservedRv)nLearning:Estimatep(HiddenRv,ObservedRv)fromsamples1.122nnp(ClassLabel,ObservedData)p(ClassLabel|ObservedData)np(ClassLabel|ObservedData)n1.123QueriesnPerformprobabilisticqueriesaboutasetofRVsofinterestnp(X|Y=y)nFindthemostprobableassignmentstoonesubsetgivenanassignmenttoothersubset(e.g.,x*=argmaxxp(x|y)).nIsonesubsetindependentofsomeothersubset?X⊥Y?nIsonesubsetindependentofsomeothersubset,givenathirdsubset?X⊥Y|Z?nGiventheoveralljointdistribution,wecananswerthesequeriesnNeedtodothesefast241.11.21.31.225nAgraphisapairG=(X,E)nX={X1,…,XN}isafinitesetofvertices,alsocallednodes,ofGnEisasubsetofthesetXX={(Xi,Xj):i¹j},callededgesofG,nUndirectededge:both(Xi,Xj)and(Xj,Xi)belongtoEXi~XjnDirectededge:(Xi,Xj)∈Eand(Xj,Xi)∉EXi→XjwesaythatXiisaparentofXj,XjisachildofXi1.226X1X3X2X4nDirectedgraph:AlledgesinthegrapharedirectednUndirecedgraph:AlledgesinthegraphareundirectedX1X3X2X4X={X1,X2,X3,X4}E={{X1,X2},{X2,X1},{X1,X3},{X3,X1},{X2,X4},{X4,X2},{X3,X4},{X4,X3}}X={X1,X2,X3,X4}E={{X1,X2},{X1,X3},{X2,X4},{X3,X4}}271.11.21.31.328n:nAGMisaparsimoniousrepresentationofajointprobabilitydistribution,p(X1,…,XN)nThenodesrepresentrandomvariablesnTheedgesrepresentdependenceX1X3X2X41.329nGMsrepresentjointprobabilitydistributionsusingasetof“local”realtionshipsamongvariablesßfactorizationnDirectedgraphnParent-childrelationshipconditionaldistributionnLetXpirepresentsthesetofparentsofnodeXi11(,,)(|)iNNiipxxpxxp==∏KIfeachvariablexirangesoverrvaluesNr11iNirp+=∑Semantics:1.330()X1X3X2X4nDirectedgraph:AlledgesinthegrapharedirectedX={X1,X2,X3,X4}E={{X1,X2},{X1,X3},{X2,X4},{X3,X4}}123412131412(,,,)()(|)(|)(|,)pxxxxpxpxxpxxpxxx=r4(r+r2+r2+r3)nn?1.331ToyExampleofaBayesnetWetGrassSprinklerCloudyRain0.50.5p(C=1)p(C=0)0.10.910.50.50p(S=1|C)p(S=0|C)C0.80.210.20.80p(R=1|C)p(R=0|C)C0.990