ch15关于时间的概率推理人工智能课程北大计算机研究所

‡‡z„zzz‡vs.z„z„‡timeslide‡‡XttEttEtet‡‡t0t1Markovprocesses(Markovchains)ConstructaBayesnetfromthesevariables:parents?Markovassumption:XtdependsonboundedsubsetofX0:t1First-orderMarkovprocess:P(XtjX0:t1)=P(XtjXt1)Second-orderMarkovprocess:P(XtjX0:t1)=P(XtjXt2;Xt1)Xt−1XtXt−2Xt+1Xt+2Xt−1XtXt−2Xt+1Xt+2First−orderSecond−orderSensorMarkovassumption:P(EtjX0:t;E0:t1)=P(EtjXt)Stationaryprocess:transitionmodelP(XtjXt1)andsensormodelP(EtjXt)xedforalltChapter15,Sections1{54ExampletRaintUmbrellaRaint−1Umbrellat−1Raint+1Umbrellat+1Rt−1tP(R)0.3f0.7ttRtP(U)0.9t0.2fFirst-orderMarkovassumptionnotexactlytrueinrealworld!Possiblexes:1.IncreaseorderofMarkovprocess2.Augmentstate,e.g.,addTempt,PressuretExample:robotmotion.AugmentpositionandvelocitywithBatterytChapter15,Sections1{55InferencetasksFiltering:P(Xtje1:t)beliefstate|inputtothedecisionprocessofarationalagentPrediction:P(Xt+kje1:t)fork0evaluationofpossibleactionsequences;likelteringwithouttheevidenceSmoothing:P(Xkje1:t)for0ktbetterestimateofpaststates,essentialforlearningMostlikelyexplanation:argmaxx1:tP(x1:tje1:t)speechrecognition,decodingwithanoisychannelChapter15,Sections1{56FilteringAim:devisearecursivestateestimationalgorithm:P(Xt+1je1:t+1)=f(et+1;P(Xtje1:t))P(Xt+1je1:t+1)=P(Xt+1je1:t;et+1)=P(et+1jXt+1;e1:t)P(Xt+1je1:t)=P(et+1jXt+1)P(Xt+1je1:t)I.e.,prediction+estimation.PredictionbysummingoutXt:P(Xt+1je1:t+1)=P(et+1jXt+1)xtP(Xt+1jxt;e1:t)P(xtje1:t)=P(et+1jXt+1)xtP(Xt+1jxt)P(xtje1:t)f1:t+1=Forward(f1:t;et+1)wheref1:t=P(Xtje1:t)Timeandspaceconstant(independentoft)Chapter15,Sections1{57FilteringexampleRain1Umbrella1Rain2Umbrella2Rain00.8180.1820.6270.3730.8830.117TrueFalse0.5000.5000.5000.500Chapter15,Sections1{58SmoothingX0X11EEktEtXXkDivideevidencee1:tintoe1:k,ek+1:t:P(Xkje1:t)=P(Xkje1:k;ek+1:t)=P(Xkje1:k)P(ek+1:tjXk;e1:k)=P(Xkje1:k)P(ek+1:tjXk)=f1:kbk+1:tBackwardmessagecomputedbyabackwardsrecursion:P(ek+1:tjXk)=xk+1P(ek+1:tjXk;xk+1)P(xk+1jXk)=xk+1P(ek+1:tjxk+1)P(xk+1jXk)=xk+1P(ek+1jxk+1)P(ek+2:tjxk+1)P(xk+1jXk)Chapter15,Sections1{59SmoothingexampleRain1Umbrella1Rain2Umbrella2Rain0TrueFalse0.8180.1820.6270.3730.8830.1170.5000.5000.5000.5001.0001.0000.6900.4100.8830.117forwardbackwardsmoothed0.8830.117Forward{backwardalgorithm:cacheforwardmessagesalongthewayTimelinearint(polytreeinference),spaceO(tjfj)Chapter15,Sections1{510MostlikelyexplanationMostlikelysequence6=sequenceofmostlikelystates!!!!Mostlikelypathtoeachxt+1=mostlikelypathtosomextplusonemorestepmaxx1:::xtP(x1;:::;xt;Xt+1je1:t+1)=P(et+1jXt+1)maxxt0@P(Xt+1jxt)maxx1:::xt1P(x1;:::;xt1;xtje1:t)1AIdenticaltoltering,exceptf1:treplacedbym1:t=maxx1:::xt1P(x1;:::;xt1;Xtje1:t);I.e.,m1:t(i)givestheprobabilityofthemostlikelypathtostatei.Updatehassumreplacedbymax,givingtheViterbialgorithm:m1:t+1=P(et+1jXt+1)maxxt(P(Xt+1jxt)m1:t)Chapter15,Sections1{511ViterbiexampleRain1Rain2Rain3Rain4Rain5truefalsetruefalsetruefalsetruefalsetruefalse.8182.5155.0361.0334.0210.1818.0491.1237.0173.0024m1:1m1:5m1:4m1:3m1:2statespacepathsmostlikelypathsumbrellatruetruetruefalsetrueChapter15,Sections1{512HiddenMarkovmodelsXtisasingle,discretevariable(usuallyEtistoo)DomainofXtisf1;:::;SgTransitionmatrixTij=P(Xt=jjXt1=i),e.g.,0BB@0:70:30:30:71CCASensormatrixOtforeachtimestep,diagonalelementsP(etjXt=i)e.g.,withU1=true,O1=0BB@0:9000:21CCAForwardandbackwardmessagesascolumnvectors:f1:t+1=Ot+1Tf1:tbk+1:t=TOk+1bk+2:tForward-backwardalgorithmneedstimeO(S2t)andspaceO(St)Chapter15,Sections1{513CountrydancealgorithmCanavoidstoringallforwardmessagesinsmoothingbyrunningforwardalgorithmbackwards:f1:t+1=Ot+1Tf1:tO1t+1f1:t+1=Tf1:t0(T)1O1t+1f1:t+1=f1:tAlgorithm:forwardpasscomputesft,backwardpassdoesfi,biChapter15,Sections1{514CountrydancealgorithmCanavoidstoringallforwardmessagesinsmoothingbyrunningforwardalgorithmbackwards:f1:t+1=Ot+1Tf1:tO1t+1f1:t+1=Tf1:t0(T)1O1t+1f1:t+1=f1:tAlgorithm:forwardpasscomputesft,backwardpassdoesfi,biChapter15,Sections1{515CountrydancealgorithmCanavoidstoringallforwardmessagesinsmoothingbyrunningforwardalgorithmbackwards:f1:t+1=Ot+1Tf1:tO1t+1f1:t+1=Tf1:t0(T)1O1t+1f1:t+1=f1:tAlgorithm:forwardpasscomputesft,backwardpassdoesfi,biChapter15,Sections1{516CountrydancealgorithmCanavoidstoringallforwardmessagesinsmoothingbyrunningforwardalgorithmbackwards:f1:t+1=Ot+1Tf1:tO1t+1f1:t+1=Tf1:t0(T)1O1t+1f1:t+1=f1:tAlgorithm:forwardpasscomputesft,backwardpassdoesfi,biChapter15,Sections1{517CountrydancealgorithmCanavoidstoringallforwardmessagesinsmoothingbyrunningforwardalgorithmbackwards:f1:t+1=Ot+1Tf1:tO1t+1f1:t+1=Tf1:t0(T)1O1t+1f1:t+1=f1:tAlgorithm:forwardpasscomputesft,backwardpassdoesfi,biChapter15,Sections1{518CountrydancealgorithmCanavoidstoringallforwardmessagesinsmoothingbyrunningforwardalgorithmbackwards:f1:t+1=Ot+1Tf1:tO1t+1f1:t+1=Tf1:t0(T)1O1t+1f1:t+1=f1:tAlgorithm:forwardpasscomputesft,backwardpassdoesfi,biChapter15,Sections1{519CountrydancealgorithmCanavoidstoringallforwardmessagesinsmoothingbyrunningforwardalgorithmbackwards:f1:t+1=Ot+1Tf1:tO1t+1f1: