台大-李宏毅-B站机器学习视频-课件神经网络与深度学习Sequence

SequenceLabeling,SequenceLabeling,Sequence,Sequence,(sequence),(sequence),Application,NameentityrecognitionIdentifyingnamesofpeople,places,organizations,etc.fromasentenceHarryPotterisastudentofHogwartsandlivedonPrivetDrive.people,organizations,places,notanameentity,Ref:https:/www.ptt.cc/bbs/JinYong/M.1258625573.A.DC4.html,楊公再興之神,Canbedifficult,Ref:https:/www.ptt.cc/bbs/JinYong/M.1195128035.A.31A.html,馮氏埋香之塚,ExampleTask,POStagging,Annotateeachwordinasentencewithapart-of-speech.,Usefulforsubsequentsyntacticparsingandwordsensedisambiguation,etc.,ExampleTask,POStagging,Theproblemcannotbesolvedwithoutconsideringthesequences.,“saw”ismorelikelytobeaverbVratherthananounN,However,thesecond“saw”isanounNbecauseanounNismorelikelytofollowadeterminer.,Outline,Outline,HMM,Howyougenerateasentence?,Johnsawthesaw.,JusttheassumptionofHMM,PNVDN,HMMStep1,0.95,0.05,0.85,0.05,end,0.5,0.1,0.8,0.1,0.1,0.25,0.25,start,0.1,0.5,0.4,Det,Noun,PropNoun,Verb,P(“PNVDN”)=0.4*0.8*0.25*0.95*0.1,Slidecredit:RaymondJ.Mooney,Thisisthegrammarinyourbrain.,PN,N,D,V,MarkovChain,HMMStep2,Noun,cat,dog,saw,pen,bed,apple,Det,a,the,the,the,that,a,the,a,0.2,John,saw,the,saw,“PNVDN”,Slidecredit:RaymondJ.Mooney,0.17,0.63,0.17,P(“Johnsawthesaw“|“PNVDN”)=0.2*0.17*0.63*0.17,HMM,x:,y:,=|,|=|,P(x,y)=P(y)P(x|y),start,end,HowaboutP(x,y)=P(x)P(y|x)?,HMM,=1|,=11+1|,|,Transitionprobability,|,=1|,Emissionprobability,Step1,Step2,x:,y:,=1,2,=1,2,HMMEstimatingtheprobabilities,HowcanIknowP(V|PN),P(saw|V)?Obtainingfromtrainingdata,TrainingData:,1,1,2,2,3,3,HMMEstimatingtheprobabilities,=1|=11+1|=1|,+1=|=,=|=,Sosimple,(andaretags),(istag,andisword),DifferentfromwhatyoulearnedinDSP?,Latentinformationinspeechrecognition,Ref:.tw/tlkagk/courses/MLDS_2015_2/Lecture/Hidden%20(v7).ecm.mp4/index.html,HMMHowtodoPOSTagging?,WecancomputeP(x,y),x:,y:,Tobefound,Observed,=max,=max|,=max,Task:givenx,findy,EnumerateallpossibleyAssumethereare|S|tags,andthelengthofsequenceyisLThereare|S|LpossibleyViterbialgorithmSolvetheaboveproblemwithcomplexityO(L|S|2),HMMViterbiAlgorithm,=max,HMM-Summary,=max,F(x,y)=P(x,y)=P(y)P(x|y),P(y)andP(x|y)canbesimplyobtainedfromtrainingdata,notnecessarilysmall,HMM-Drawbacks,Inference:Toobtaincorrectresults,:,CanHMMguaranteethat?,P(V|N)=9/10,P(D|N)=1/10,P(a|V)=1/2,P(a|D)=1,Transitionprobability:,Emissionprobability:,yl=V,yl-1=N,yl=D,9/10,1/10,xl=a,xl=a,xl=c,1,1/2,1/2,=max,notnecessarilysmall,HMM-Drawbacks,Inference:Toobtaincorrectresults,:,CanHMMguaranteethat?,P(V|N)=9/10,P(D|N)=1/10,P(a|V)=1/2,P(a|D)=1,Transitionprobability:,Emissionprobability:,yl=?,yl-1=N,xl=a,V,P(yl|yl-1),P(xl|yl),=max,notnecessarilysmall,HMM-Drawbacks,Inference:Toobtaincorrectresults,:,CanHMMguaranteethat?,HighprobabilityforHMM,P(V|N)=9/10,P(D|N)=1/10,P(a|V)=1/2,P(a|D)=1,Transitionprobability:,Emissionprobability:,D,X9,X9,=max,HMM-Drawbacks,The(x,y)neverseeninthetrainingdatacanhavelargeprobabilityP(x,y).Benefit:Whenthereisonlylittletrainingdata,X9,X9,HighprobabilityforHMM,However,CRFcandealwiththisproblembasedonthesamemodel,Morecomplexmodelcandealwiththisproblem,Outline,CRF,|,P,=,=,isafeaturevector.Whatdoesitlooklike?isaweightvectortobelearnedfromtrainingdata,isalwayspositive,canbelargerthan1,=,P,=,P(x,y)forCRF,=1|=11+1|=1|,InHMM:,=1|+=11+1|+|,+=1|,P,verydifferentfromHMM?,P(x,y)forCRF,=1|=,|,Enumerateallpossibletagssandallpossiblewordt,Numberoftagsandwordtappearstogetherin,Logprobabilityofwordtgiventags,=1|+=11+1|+|,+=1|,P(x,y)forCRF,=1|,=,|,=2,=1,=1,=1,=0,=|+|+|+|+|,(foranyothersandt),=|2+|1+|1+|1,P(x,y)forCRF,=1|+=11+1|+|,+=1|,1|=|,=11+1|=,|,|=|,+|,P(x,y)forCRF,=,|,+,|,+|,=|,P,=,=,P,=,P(x,y)forCRF,=|1=,However,wedonotgiveanyconstraintsduringtraining,=,=,|,|,=|=,FeatureVector,hastwopartsPart1:relationsbetweentagsandwordsPart2:relationsbetweentags,Part1has|S|X|L|dimensions,Ifthereare|S|possibletags,|L|possiblewords,Whatdoes,looklike?,FeatureVector,hastwopartsPart1:relationsbetweentagsandwordsPart2:relationsbetweentags,Whatdoes,looklike?,:,Numberoftagsandconsecutivelyin,FeatureVector,hastwopartsPart1:relationsbetweentagsandwordsPart2:relationsbetweentags,Whatdoes,looklike?,Ifthereare|S|possibletags,|S|X|S|+2|S|dimensions,Defineany,youlike!,|=,CRFTrainingCriterion,Giventrainingdata:1,1,2,2,Findtheweightvectormaximizingobjectivefunction:,=argmaxO,Minimizewhatwedontobserve,Maximizewhatweobserve,O=1|,|,=,CRFGradientAscent,Gradientdescent,Findasetofparametersminimizingcostfunction,GradientAscent,FindasetofparametersmaximizingobjectivefunctionO,+,Oppositedirectionofthegradient,Thesamedirectionofthegradient,CRF-Training,Letmeshow,O=1|=1,verysimilar,CRF-Training,Ifwordtislabeledbytagsintrainingexamples,thenincrease,=,|,Ifwordtislabeledbytagsin,whichnotintrainingexamples,thendecrease,Aftersomemath,+,|=,CanbecomputedbyViterbialgorithmaswell,CRF-Training,=,|,StochasticGradientAscent,w+,|,Randompickadata,|=,CRFInference,Inference,=max|,=max,DonebyViterbiaswell,P,=max,CRFv.s.HMM,CRF:increase,decrease,Toobtaincorrectresults,HMMdoesnotdothat,:,CRFmorelikelytoachievethatthanHMM,X9,X9,yi=?,yi-1=N,xi=a,HMM:V,P(yi|yi-1),P(xi|yi),CRF:,0.1,CRF:D,SyntheticData,Generatingdatafromamixed-orderHMMTransitionprobability:|1+1|1,2Emissionprobability:|+1|,1ComparingHMMandCRFAlltheapproachesonlyconsider1-storderinformationOnlyconsideringtherelationof1andIngeneral,alltheapproacheshaveworseperformancewithsmaller,Ref:JohnD.Lafferty,AndrewMcCallum,andFernandoC.N.Pereira,“ConditionalRandomFields:ProbabilisticModelsforSegmentingandLabelingSequenceData”,ICML,2001,SyntheticData:CRFv.s.HMM,HMM,CRF,12,CRF,CRFHMM,Smaller,1-storderHMMassumptionisinaccurate,DataaregeneratedfromHMM,CRF-Summary,=argmax=1|,=argmax|,=argmax,w+,|,Outline,StructuredPerceptron,=argmax(,),=,:,+,=argmax,Viterbi,ThesameasCRF,StructuredPerceptronv.s.CRF,StructuredPerceptronCRF,+,=argmax,w+,|,Hard,Soft,StructuredSVM,=argmax(,),=,Viterbi,ThesameasCRF,Way1.GradientDescent,Way2.QuadraticProgramming(CuttingPlaneAlgorithm),Considermarginanderror:,StructuredSVMErrorFunction,Errorfunction:,:DifferencebetweenandCostfunctionofstructuredSVMistheupperboundof,Theoretically,canbeanyfunctionyoulikeHowever,youneedtosolveProblem2.1=max,+,:,:,ATTCGGGGAT,ATTAGGAGAA,Example,=3/10,Inthiscase,problem2.1canbesolvedbyViterbiAlgorithm,POSTagging,Ref:Nguyen,Nam,andYunsongGuo.Comparisonsofsequencelabelingalgorithmsandextensions.ICML,2007.,NameEntityRecognition,Ref:Tsochantaridis,Ioannis,etal.Largemarginmethodsforstructuredandinterdependentoutputvariables.JournalofMachineLearningResearch.2005.,PerformanceofDifferentApproaches,ConcludingRemarks,.tw/tlkagk/courses/MLDS_2015/Structured%20Lecture/Segmental%20CRF%20(v8).fsp/index.html(請用IE開啟),Theaboveapproachescancombinewithdeeplearningtohavebetterperformance.,Nextl