自然语言处理NLP.ppt

1 StatisticalNLP Lecture8 StatisticalInference n gramModelsoverSparseData 2 Overview StatisticalInferenceconsistsoftakingsomedata generatedinaccordancewithsomeunknownprobabilitydistribution andthenmakingsomeinferencesaboutthisdistribution Therearethreeissuestoconsider DividingthetrainingdataintoequivalenceclassesFindingagoodstatisticalestimatorforeachequivalenceclassCombiningmultipleestimators 3 FormingEquivalenceClassesI ClassificationProblem trytopredictthetargetfeaturebasedonvariousclassificatoryfeatures ReliabilityversusdiscriminationMarkovAssumption Onlythepriorlocalcontextaffectsthenextentry n 1 thMarkovModelorn gramSizeofthen grammodelsversusnumberofparameters wewouldlikentobelarge butthenumberofparametersincreasesexponentiallywithn Thereexistotherwaystoformequivalenceclassesofthehistory buttheyrequiremorecomplicated methods willusen gramshere 4 StatisticalEstimatorsI Overview Goal ToderiveagoodprobabilityestimateforthetargetfeaturebasedonobserveddataRunningExample Fromn gramdataP w1 wn spredictP wn w1 wn 1 Solutionswewilllookat MaximumLikelihoodEstimationLaplace s Lidstone sandJeffreys Perks LawsHeldOutEstimationCross ValidationGood TuringEstimation 5 StatisticalEstimatorsII MaximumLikelihoodEstimation PMLE w1 wn C w1 wn N whereC w1 wn isthefrequencyofn gramw1 wnPMLE wn w1 wn 1 C w1 wn C w1 wn 1 ThisestimateiscalledMaximumLikelihoodEstimate MLE becauseitisthechoiceofparametersthatgivesthehighestprobabilitytothetrainingcorpus MLEisusuallyunsuitableforNLPbecauseofthesparsenessofthedata UseaDiscountingor Smoothingtechnique 6 StatisticalEstimatorsIII SmoothingTechniques Laplace PLAP w1 wn C w1 wn 1 N B whereC w1 wn isthefrequencyofn gramw1 wnandBisthenumberofbinstraininginstancesaredividedinto AddingOneProcessTheideaistogivealittlebitoftheprobabilityspacetounseenevents However inNLPapplicationsthatareverysparse Laplace sLawactuallygivesfartoomuchoftheprobabilityspacetounseenevents 7 StatisticalEstimatorsIV SmoothingTechniques LidstoneandJeffrey Perks Sincetheaddingoneprocessmaybeaddingtoomuch wecanaddasmallervalue PLID w1 wn C w1 wn N B whereC w1 wn isthefrequencyofn gramw1 wnandBisthenumberofbinstraininginstancesaredividedinto and 0 Lidstone sLawIf 1 2 Lidstone sLawcorrespondstotheexpectationofthelikelihoodandiscalledtheExpectedLikelihoodEstimation ELE ortheJeffreys PerksLaw 8 StatisticalEstimatorsV RobustTechniques HeldOutEstimation Foreachn gram w1 wn wecomputeC1 w1 wn andC2 w1 wn thefrequenciesofw1 wnintrainingandheldoutdata respectively LetNrbethenumberofbigramswithfrequencyrinthetrainingtext LetTrbethetotalnumberoftimesthatalln gramsthatappearedrtimesinthetrainingtextappearedintheheldoutdata Anestimatefortheprobabilityofoneofthesen gramis Pho w1 wn Tr NrN whereC w1 wn r 9 StatisticalEstimatorsVI RobustTechniques Cross Validation HeldOutestimationisusefulifthereisalotofdataavailable Ifnot itisusefultouseeachpartofthedatabothastrainingdataandheldoutdata DeletedEstimation Jelinek Mercer 1985 LetNrabethenumberofn gramsoccurringrtimesintheathpartofthetrainingdataandTrabbethetotaloccurrencesofthosebigramsfrompartainpartb Pdel w1 wn Tr01 Tr10 N Nr0 Nr1 whereC w1 wn r Leave One Out Neyetal 1997 10 StatisticalEstimatorsVI RelatedApproach Good TuringEstimator IfC w1 wn r 0 PGT w1 wn r Nwherer r 1 S r 1 S r andS r isasmoothedestimateoftheexpectationofNr IfC w1 wn 0 PGT w1 wn N1 N0N SimpleGood Turing Gale Sampson 1995 Asasmoothingcurve useNr arb withb 1 andestimateaandbbysimplelinearregressiononthelogarithmicformofthisequation logNr loga blogr ifrislarge Forlowvaluesofr usethemeasuredNrdirectly 11 CombiningEstimatorsI Overview Ifwehaveseveralmodelsofhowthehistorypredictswhatcomesnext thenwemightwishtocombinetheminthehopeofproducinganevenbettermodel CombinationMethodsConsidered SimpleLinearInterpolationKatz sBackingOffGeneralLinearInterpolation 12 CombiningEstimatorsII SimpleLinearInterpolation Onewayofsolvingthesparsenessinatrigrammodelistomixthatmodelwithbigramandunigrammodelsthatsufferlessfromdatasparseness Thiscanbedonebylinearinterpolation alsocalledfinitemixturemodels Whenthefunctionsbeinginterpolatedalluseasubsetoftheconditioninginformationofthemostdiscriminatingfunction thismethodisreferredtoasdeletedinterpolation Pli wn wn 2 wn 1 1P1 wn 2P2 wn wn 1 3P3 wn wn 1 wn 2 where0 i 1and i i 1TheweightscanbesetautomaticallyusingtheExpectation Maximization EM algorithm 13 CombiningEstimatorsII Katz sBackingOffModel Inback offmodels differentmodelsareconsultedinorderdependingontheirspecificity Ifthen gramofconcernhasappearedmorethanktimes thenann gramestimateisusedbutanamountoftheMLEestimategetsdiscounted itisreservedforunseenn grams Ifthen gramoccurredktimesorless thenwewilluseanestimatefromashortern gram back offprobability normalizedbytheamountofprobabilityremainingandtheamountofdatacoveredbythisestimate Theprocesscontinuesrecursively 14 CombiningEstimatorsII GeneralLinearInterpolation Insi