语音识别的搜索算法

8.0SearchAlgorithmsforSpeechRecognition

语音识别的搜索算法1

数字语音处理概论IntroductiontoDigitalSpeechProcessingASimplifiedBlockDiagramExampleInputSentence

thisisspeechAcousticModels

(th-ih-s-ih-z-s-p-ih-ch)Lexicon(th-ih-s)→this(ih-z)→is(s-p-iy-ch)→speechLanguageModel(this)–(is)–(speech) P(this)P(is|this)P(speech|thisis) P(wi|wi-1)bi-gram

languagemodel P(wi|wi-1,wi-2)tri-gramlanguagemodel,etcBasicApproachforLargeVocabularySpeechRecognitionFront-endSignalProcessingAcousticModelsLexiconFeatureVectorsLinguisticDecodingandSearchAlgorithmOutputSentenceSpeechCorporaAcousticModelTrainingLanguageModelConstructionTextCorporaLanguageModelInputSpeech2DTWandDynamicProgrammingDynamicTimeWarping(DTW)wellacceptedpre-HMMapproachfindanoptimalpathformatchingtwotemplateswithdifferentlengthgoodforsmall-vocabularyisolated-wordrecognitioneventodayTestTemplate[yj,j=1,2,...N]andReferenceTemplate[xi,i=1,2,..M]warpingbothtemplatestoacommonlengthL warpingfunctions:fx(m)=i,fy(m)=j,m=1,2,...Lendpointconstraints:fx(1)=fy(1)=1,fx(L)=M,fy(L)=N monotonicconstraints:fx(m+1)≥fx(m),fy(m+1)≥fy(m)matchingpair:

foreverym,m:indexformatchingpairsrecursiverelationship:

globalconstraints/localconstraintslackofagoodapproachtotrainagoodreferencepatternDynamicProgrammingreplacingtheproblembyasmallersub-problemandformulatinganiterativeprocedureReference:4.7upto4.7.3ofRabinerandJuang3DTWprogramming(reference)(test)referencetest4DTW5DTWfx(m)=i,fy(m)=j,m=1,2,...Lfx(1)=fy(1)=1,fx(L)=M,fy(L)=Nfx(m+1)≥fx(m),fy(m+1)≥fy(m)accumulatedminimumdistance67ViterbiAlgorithm

(P.21of4.0)δt(i)δt+1(j)δt(i)ittt+111ij

t+1(j)=max[

t(i)aij]

bj(ot+1)i

t(i)

=max

P[q1,q2,…qt-1,qt=i,o1,o2,…,ot|

]q1,q2,…qt-18ViterbiAlgorithm

(P.22of4.0)9ContinuousSpeechRecognitionExample:DigitStringRecognition―

One-stageSearchUnknownNumberofDigitsNoLexicon/LanguageModelConstraintsSearchovera3-dimGridSwitchedtotheFirstStateoftheNextModelattheEndofthePreviousModelMayResultwithSubstitution,DeletionandInsertion019019t012910RecognitionErrorsReference:

(T)Recognized:insertion(I)substitution(S)deletion(D)

AccuracyAligned11ContinuousSpeechRecognitionExample:DigitStringRecognition―Level-BuildingKnownNumberofDigitsNoLexicon/LanguageModelConstraintsHigherComputationComplexity,NoDeletion/Insertion01.901.901.901.9State01...901...9t01...901...9numberoflevels=numberofdigitsinanutteranceautomatictransitionfromthelaststateofthepreviousmodeltothefirststateofthenextmodel12Time(Frame)-SynchronousViterbiSearchforLarge-VocabularyContinuousSpeechRecognitionMAPPrincipleAnApproximationthewordsequencewiththehighestprobabilityforthemostprobablestatesequenceusuallyhasapproximatelythehighestprobabilityforallstatesequencesViterbisearch,asub-optimalapproachViterbiSearch―DynamicProgrammingreplacingtheproblembyasmallersub-problemandformulatinganiterativeproceduretime(frame)-synchronous:thebestscoreattimetisupdatedfromallstatesattimet-1TreeLexiconastheBasicWorkingStructurefromHMMfromLanguageModeleacharcisanHMM(phoneme,tri-phone,etc.)eachleafnodeisawordsearchprocessesforasegmentofutterancethroughsomecommonunitsfordifferentwordscanbesharedsearchspaceconstrainedbythelexiconthesametreecopyreproducedateachleafnodeinprinciple13BasicProblem2forHMM

(P.24of4.0)․ApplicationExampleofViterbiAlgorithm-Isolatedwordrecognition...Themodelwiththehighestprobabilityforthemostprobablepathusuallyalsohasthehighestprobabilityforallpossiblepaths.observation1£i£n

1£i£nBasicProblem1ForwardAlgorithm(forallpaths)BasicProblem2ViterbiAlgorithm(forasinglebestpath)14TreeLexiconstatestimeo1o2….ot….oT

1516Time(Frame)-SynchronousViterbiSearchforLarge–VocabularyContinuousSpeechRecognitionDefineKeyParametersD(t,qt,w):objectivefunctionforthebestpartialpathendingattimetinstateqtforthewordwh(t,qt,w):backtrackpointerforthepreviousstateatthepervioustimewhenthebestpartialpathendsattimetinstateqtforthewordwIntra-wordTransition―HMMonly,noLanguageModelInter-wordTransition―LanguageModelonly,noHMM(bi-gramasanexample)17TimeSynchronousViterbiSearchD(t,qt,w)ot

qtw18ViterbiAlgorithm

(P.21of4.0)δt(i)δt+1(j)δt(i)ittt+111ij

t+1(j)=max[

t(i)aij]

bj(ot+1)i

t(i)

=max

P[q1,q2,…qt-1,qt=i,o1,o2,…,ot|

]q1,q2,…qt-119qf(v)Qtt20Time(Frame)-SynchronousViterbiSearchforLarge-VocabularyContinuousSpeechRecognitionBeamSearchateachtimetonlyasubsetofpromisingpathsarekeptexample1:defineabeamwidthL(i.e.keepingonlyLpathsateachtime) example2:defineathresholdTh(i.e.allpathswithD<Dmax,t-Tharedeleted)veryhelpfulinreducingthesearchspaceTwo-passSearch(orMulti-passSearch)uselessknowledgeorlessconstraints(e.g.acousticmodelwithlesscontextdependencyorlanguagemodelwithlowerorder)inthefirststage,whilemoreknowledgeormoreconstraintsinrescoringinthesecondpathsearchspacesignificantlyreducedbydecouplingthecomplicatedsearchprocessintosimplerprocessesN-bestListandWordGraph(Lattice)

W1W2W1W6W5W3W4W5W7W8W9W10W9similarlyconstructedwithdynamicprogrammingiterationsN-bestListorWordGraphGenerationRescoringXN-bestListWordGraphWTime21

S:starting G:goaltofindtheminimumdistancepathBlindSearchAlgorithmsDepth-firstSearch:pickupanarbitraryalternativeandproceedBreath-firstSearch:considerallnodesonthesamelevelbeforegoingtothenextlevelnosenseaboutwherethegoalisAnExample–acitytravelingproblemSomeSearchAlgorithmFundamentalsSearchTree(Graph)2.8GEFCBADS3335544231010.37.03.05.78.5SABBAFDGECCCDEEG3711162611691411149612HeuristicSearchBest-firstSearchbasedonsomeknowledge,or“heuristicinformation” f(n)=g(n)+h*(n) g(n):distanceuptonoden h*(n):heuristicestimatefortheremainingdistanceuptoGheuristicpruningASC11.711.512.011.8EGh*(n):straight-linedistance22ABCDEFGL4L1L2L34323241813ListofCandidateStepsNodeg(n)

h*(n)

f(n)

A01515B4913C31215D257E7411F729

G11314L1909L2808L312012L4505HeuristicSearch:AnotherExampleProblem:Findapathwiththehighestscorefromrootnode“A”tosomeleafnode(oneof“L1”,”L2”,”L3”,”L4”)TopCandidateListA(15