语言模型入门-N-gram概率模型与信息检索应用

NLP基础语言模型入门：N-gram概率模型与信息检索应用（自然语言处理/搜索引擎）作者：DjoerdHiemstra许可：Unknown(encyclopediaentry)【内容简介】百科全书条目，介绍语言模型的基本概念，包括N-gram模型和其在信息检索中的应用，适用于NLP入门学习。（学术资料，仅供参考）【关键词】语言模型、N-gram、信息检索、自然语言处理、概率模型【分类】科技>计算机与互联网>人工智能——————————————————————————————LANGUAGEMODELSDjoerdHiemstraUniversityofTwentehttp://www.cs.utwente.nl/~hiemstraSYNONYMSGENERATIVEMODELSDEFINITIONAlanguagemodelassignsaprobabilitytoapieceofunseentext,basedonsometrainingdata.Forexample,alanguagemodelbasedonabigEnglishnewspaperarchiveisexpectedtoassignahigherprobabilityto“abitoftext”thanto“awpittovtags”,becausethewordsintheformerphrase(orwordpairsorwordtriplesifso-calledN-GRAMMODELSareused)occurmorefrequentlyinthedatathanthewordsinthelatterphrase.Forinformationretrieval,typicalusageistobuildalanguagemodelforeachdocument.Atsearchtime,thetoprankeddocumentistheonewhich’languagemodelassignsthehighestprobabilitytothequery.HISTORICALBACKGROUNDThetermlanguagemodelsoriginatesfromprobabilisticmodelsoflanguagegenerationdevelopedforautomaticspeechrecognitionsystemsintheearly1980’s[9].Speechrecognitionsystemsusealanguagemodeltocomplementtheresultsoftheacousticmodelwhichmodelstherelationbetweenwords(orpartsofwordscalledphonemes)andtheacousticsignal.Thehistoryoflanguagemodels,however,goesbacktobeginningofthe20thcenturywhenAndreiMarkovusedlanguagemodels(Markovmodels)tomodellettersequencesinworksofRussianliterature[3].AnotherfamousapplicationoflanguagemodelsareClaudeShannon’smodelsoflettersequencesandwordsequences,whichheusedtoillustratetheimplicationsofcodingandinformationtheory[17].Inthe1990’slanguagemodelswereappliedasageneraltoolforseveralnaturallanguageprocessingapplications,suchaspart-of-speechtagging,machinetranslation,andopticalcharacterrecognition.Languagemodelswereappliedtoinformationretrievalbyanumberofresearchgroupsinthelate1990’s[4,7,14,15].Theybecamerapidlypopularininformationretrievalresearch.By2001,theACMSIGIRconferencehadtwoseparatesessionsonlanguagemodelscontaining5papersintotal[13].In2003,agroupofleadinginformationretrievalresearcherspublishedaresearchroadmap“ChallengesinInformationRetrievalandLanguageModeling”[1],indicatingthatthefutureofinformationretrievalandthefutureoflanguagemodelingcannotbeseenapartfromeachother.SCIENTIFICFUNDAMENTALSLanguagemodelsaregenerativemodels,i.e.,modelsthatdefineaprobabilitymechanismforgeneratinglanguage.Suchgenerativemodelsmightbeexplainedbythefollowingprobabilitymechanism:ImaginepickingatermTatrandomfromthispagebypointingatthepagewithclosedeyes.ThismechanismdefinesaprobabilityP(T|D),whichcouldbedefinedastherelativefrequencyoftheoccurrenceoftheevent,i.e.,bythenumberofoccurrencesofawordonthepagedividedbythetotalnumberoftermsonthepage.Supposetheprocessisrepeatedntimes,pickingoneatatimethetermsT1,T2,...,Tn.Then,assumingindependencebetweenthesuccessiveevents,theprobabilityofthetermsgiventhedocumentDisdefinedasfollows:P(T1,T2,···,Tn|D)=nYi=1P(Ti|D)(1)AsimplelanguagemodelingapproachwouldcomputeEquation1foreachdocumentinthecollection,andrankthedocumentsaccordingly.Apotentialproblemmightbethefollowing:Theequationwillassignzeroprobabilitytoasequenceoftermsunlessalltermsoccurinthedocument.So,alanguagemodelingsystemthatusesEquation1willnotretrieveadocumentunlessitcontainsallqueryterms.Thismightbereasonableforawebsearchenginethattypicallyprocessessmallqueriestosearchavastamountofdata,butformanyotherinformationretrievalapplicationsthisbehaviorisaproblem.Astandardsolutionistouselinearinterpolationsmoothing(seePROBABILITYSMOOTHING)ofthedocumentmodelP(T|D)withacollectionmodelP(T|C),whichisdefinedasfollows.P(T1,T2,···,Tn|D)=nYi=1λP(Ti|D)+(1−λ)P(Ti|C)(2)Thisway,atermthatdoesnotoccurinthedocumentwillnotbeassignedzeroprobabilitybutinsteadaprobabilityproportionaltoitsnumberofoccurrencesintheentirecollectionC.Here,λisanunknownprobabilitythatshouldbetunedtooptimizeretrievaleffectiveness.Linearinterpolationsmoothingwasusedinseveralearlylanguagemodelingapproaches[7,14].ImplementationAlthoughthelanguagemodelingequationsabovesuggesttheneedtocomputeprobabilitiesforalldocumentsinthecollection,thisisunnecessaryinpractice.Infact,mostlanguagemodelingapproachescanbeimplementedefficientlybytheuseofstandardinvertedindexsearchsystems.ThiscanbeseenbytheequationbelowwhichcanbederivedfromEquation2bytwobasictransformations:First,dividingitbytheprobabilityofthecollectiongroundmodel;andsecond,takingthelogarithm.P(T1,T2,···,Tn|D)∝nXi=1log1+λP(Ti|D)(1−λ)P(Ti|C)(3)Equation3doesnolongerproduceprobabilities,butitranksthedocumentsintheexactsameorderasEquation2,becausethecollectionmodeldoesnotdependonthedocument,andthelogarithmisastrictlymonotonicfunction.Takingthelogarithmpreventstheimplementationfromrunningoutoftheprecisionofits(floatingpoint)representationofprobabilities,whichcanbecomeverysmallbecausetheprobabilitiesaremultipliedforeveryqueryterm.Similartoforinstancevectorspacemodelsininformationretrieval,rankingisdefinedbyasimplesumoftermweights,forwhichtermsthatdonotmatchadocumentgetazeroweight.Interestingly,theresulting“termweight”canbeseenasavariantoftf.idfweights,whichareoftenusedinvectorspacemodels.DocumentpriorsTheequationsabovedefinetheprobabilityofaquerygivenadocument,butobviously,thesystemshouldrankbytheprobabilityofthedocumentsgiventhequery.ThesetwoprobabilitiesarerelatedbyBayes’ruleasfollows.P(D|T1,T2,···,Tn)=P(T1,T2,···,Tn|D)P(D)P(T1,T2,···,Tn)(4)Theleft-handsideofEquation4cannotbeuseddirectlybecausetheindependenceassumptionpresentedaboveassumestermindependencegiventhedocument.So,inordertocomputetheprobabilityofthedocumentDgiventhequery,Equation2needtobemultipliedbyP(D)anddividedbyP(T1,···,Tn).Again,asstatedinthepreviousparagraph,theprobabilitiesthemselvesareofnointerest,onlytherankingofthedocumentbytheprobabilitiesis.AndsinceP(T1,···,Tn)doesnotdependonthedocument,rankingthedocumentsbythenumeratoroftheright-handsideofEquation4willrankthembytheprobabilitygiventhequery.ThisshowstheimportanceofP(D):Themarginalprobability,orpriorprobabilityofthedocument,i.e.,itistheprobabilitythatthedocumentisrelevantifthequeryisignored.Forinstance,wemightassumethatlongdocumentsaremorelikelytobeusefullthanshortdocuments[7,14].Inwebsearch,suchaso-calledstaticranking(arankingthatisindependentofthequery)iscommonlyused.Forinstance,documentswithmanylinkspointingtothemaremorelikelytoberelevant,ordocumentswithshortURLsaremorelikelytoberelevant.Thepriorprobabilityofadocumentisapowerfulwaytoincorporatestaticrankinginthelanguagemodelingapproach[11].DocumentgenerationmodelsAnimplicitassumptionofthelanguagemodelspresenteduntilnowisthatthereismoreinformationavailableaboutthedocumentsthanaboutthequery.Insomeapplicationshowever,thesituationisreversed.Forinstanceintopictracking,asystemhasthetasktotrackastreamofchronologicallyorderedstories.Foreachstoryinthestream,thesystemhastodecideifitisontopic,ornot.Thetargettopicisusuallybasedonanumberofexamplestoriesonacertaintopic,thereismoreinformationavailableaboutthetopicthanaboutasinglestory.Unlikequerygenerationmodels,documentgenerationmodelsneedsomeformofnormalizationbecausedocumentswillhavedifferentlengths:Theprobabilityofgeneratingadocumenttendstobesmallerforlongdocumentsthanforshortdocuments.Therefore,severalnormalizationtechniquesmight2beapplied,suchasnormalizationbydocumentlengthandadditionalGaussiannormalization[10,18].Relevancefeedback,i.e,theusermarkedsomedocumentsasrelevant,isanothersituationinwhichthereismoreknowledgeavailableaboutthequerythanabouteachsingledocument.Ifsomerelevantdocumentsareknown,orifthetoprankeddocumentsareassumedtoberelevant,thenthosedocumentsmightbeusedtogenerateanew,improvedquery[20].Asanexample,considerthefollowingso-calledrelevancemodelsapproach[12]P(Q|T1,···,Tn)∝XdP(D=d)P(Q|D=d)nYi=1P(Ti=ti|D=d)(5)Here,theformuladefinestheprobabilityofanewwordQ,giventheoriginalqueryT1,···,Tnbymarginalizingoveralldocuments.Inpractice,onlythetoprankeddocumentsforthequeryT1,···areused.Interestingly,therelevancemodelmightbeusedtoinferotherinformationfromthetoprankeddocuments,forinstancethepersonthatismostoftenmentionedforacertainquery,so-calledexpertsearch[2].TranslationmodelsLanguagemodelsforinformationretrievalaregenerativemodels,andthereforeeasilycombinedwithothergenerativemodels.Toaddamodeloftermtranslation,thefollowingprobabilitymechanismapplies:ImaginepickinganEnglishtermTatrandomfromthispagebypointingatthepagewithclosedeyes(whichdefinesaprobabilityP(T|D)),andthentranslatethetermTbypickingfromtheterm’sentryinaEnglish-DutchdictionaryatrandomaDutchtermS(withprobabilityP(S|T)).Themodelmightbeusedinacross-languageretrievalsystemtorankEnglishdocumentsgivenaDutchqueryS1,···,Snbythefollowingprobability[4,6,12,19]:P(S1,S2,···,Sn|D)=nYi=1XtP(Si=si|Ti=t)(λP(Ti=t|D)+(1−λ)P(Ti=t|C))(6)Here,DutchisthesourcelanguageandEnglishthetargetlanguage.TheformulauseslinearinterpolationsmoothingofthedocumentmodelwiththetargetlanguagebackgroundmodelP(T|C)(Englishintheexample)attheright-handsideoftheformula.Insomeformulations,thetranslationmodelissmoothedwiththesourcelanguagebackgroundmodelP(S|C)whichaestimatedonauxiliarydata.Thetwobackgroundmodelsarerelatedasfollows:P(S|C)=PtP(S|T=t)P(T=t|C).Thetranslationprobabilitiesareoftenestimatedfromparallelcorpora,i.e.,fromtextsinthetargetlanguageanditstranslationsinthesourcelanguage[6,19].Translationmodelsmightalsobeusedinamonolingualsettingtoaccountforsynonymsandotherrelatedwords[4].AspectmodelsInaspectmodels,alsocalledprobabilisticlatentsemanticindexingmodels,documentsaremodeledasmixturesofaspectlanguagemodels.Intermsofagenerativemodelitcanbedefinedinthefollowingway[8]:1)selectadocumentDwithprobabilityP(D),2)pickalatentaspectZwithprobabilityP(Z|D),3)generateatermTwithprobabilityP(T|Z)independentofthedocument,4)repeatStep2andStep3untilthedesirednumberoftermsisreached.ThisleadstoEquation7.P(T1,T2,···,Tn|D)∝nYi=1Xz(P(Ti|Z=z)P(Z=z|D))(7)Theaspectsmightcorrespondwiththetopicsorcategoriesofdocumentsinthecollectionsuchas“health”,“family”,“Hollywood”,etc.TheaspectZisahidden,unobservedvariable,soprobabilitiesconcerningZcannotbeestimatedfromdirectobservations.Instead,theExpectationMaximization(EM)algorithmcanbeapplied[9].Thealgorithmstartsoutwitharandominitializationoftheprobabilities,andtheniterativelyre-estimatestheprobabilitiestoarriveatalocalmaximumofthelikelihoodfunction.IthasbeenshownthattheEMalgorithmissensitivetotheinitialization,andanunluckyinitializationresultsinanon-optimallocalmaximum.Asasolution,clusteringofdocumentshasbeenproposedtoinitializethemodels[16].AnotheralternativeislatentsemanticDirichletallocation[5]whichhaslessfreeparameters,andthereforeislesssensitivetotheinitialization.KEYAPPLICATIONSThisentryfocusesontheapplicationoflanguagemodelstoinformationretrieval.Theapplicationspresentedincludenewswireandnewspapersearch[4,5,15],websearch[11],cross-languagesearch[6,19],topicdetectionandtracking[10,18],andexpertsearch[2].However,languagemodelshavebeenusedinvirtuallyeveryapplicationthatneedsprocessingofnaturallanguagetexts,includingautomaticspeechrecognition,part-of-speechtagging,machinetranslation,andopticalcharacterrecognition.3CROSSREFERENCEPROBABILITYSMOOTHING,N-GRAMMODELSRECOMMENDEDREADING[1]JamesAllan(editor),JayAslam,NicholasBelkin,ChrisBuckley,JamieCallan,BruceCroft(editor),SueDumais,NorbertFuhr,DonnaHarman,DavidJ.Harper,DjoerdHiemstra,ThomasHofmann,EduardHovy,WesselKraaij,JohnLafferty,VictorLavrenko,DavidLewis,LizLiddy,R.Manmatha,AndrewMcCallum,JayPonte,JohnPrager,DragomirRadev,PhilipResnik,StephenRobertson,RoniRosenfeld,SalimRoukos,MarkSanderson,RichardSchwartz,AmitSinghal,AlanSmeaton,HowardTurtle,EllenVoorhees,RalphWeischedel,JinxiXu,andChengXiangZhai.ChallengesinInformationRetrievalandLanguageModeling.SIGIRForum37(1),2003[2]KristianBalog,LeifAzzopardi,andMaartendeRijke.Formalmodelsforexpertfindinginenterprisecorpora.InProceedingsofthe29thannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval(SIGIR’06),pages43–50,2006.[3]GelyP.Basharin,AmyN.Langville,andValeriyA.Naumov.ThelifeandworkofA.A.Markov.LinearAlgebraanditsApplications386,pages3–26,2004.[4]AdamBergerandJohnLafferty.Informationretrievalasstatisticaltranslation.InProceedingsofthe22ndACMConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR’99),pages222–229,1999.[5]DavidM.Blei,AndrewY.Ng,andMichaelI.Jordan.LatentDirichletallocation.JournalofMachineLearningResearch3(5):993–1022,2003.[6]DjoerdHiemstraandFranciskadeJong.Disambiguationstrategiesforcross-languageinformationretrieval.LectureNotesinComputerSciencevolume1696:ProceedingsoftheEuropeanConferenceonDigitalLibraries,Springer-Verlag,pages274–293,1999.[7]DjoerdHiemstraandWesselKraaij.Twenty-OneatTREC-7:Ad-hocandcross-languagetrack.InProceedingsoftheseventhTextRetrievalConferenceTREC-7,pages227–238.NISTSpecialPublication500-242,1998.[8]ThomasHofmann.Probabilisticlatentsemanticindexing.InProceedingsofthe22ndannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval(SIGIR’99),pages50–57,1999.[9]FrederickJelinek.StatisticalMethodsforSpeechRecognition.MITPress,1997.[10]HubertJin,RichSchwartz,SreenivasaSista,FrederickWalls.TopicTrackingforRadio,TVBroadcastandNewswire.InProceedingsoftheDARPABroadcastNewsWorkshop,1999.[11]WesselKraaij,ThijsWesterveld,andDjoerdHiemstra.Theimportanceofpriorprobabilitiesforentrypagesearch.InProceedingsofthe25thACMConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR’02),pages27–342002.[12]VictorLavrenkoandW.BruceCroft.Relevancemodelsininformationretrieval.InW.BruceCroftandJohnLafferty(eds.)LanguageModelingforInformationRetrieval,KluwerAcademicPublishers,pages11–56,2003.[13]DonaldH.Kraft,W.BruceCroft,DavidJ.Harper,andJustinZobel(eds.).Proceedingsofthe24thACMConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR’01).AssociationforComputingMachinery,2001.[14]DavidR.H.Miller,TimothyLeek,andRichardM.Schwartz.AhiddenMarkovmodelinformationretrievalsystem.InProceedingsofthe22ndACMConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR’99),pages214–221,1999.[15]JayM.PonteandW.BruceCroft.Alanguagemodelingapproachtoinformationretrieval.InProceedingsofthe21stACMConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR’98),pages275–281,1998.[16]RichardM.Schwartz,SreenivasaSista,TimothyLeek.UnsupervisedTopicDiscovery.InProceedingsoftheLanguageModelsforInformationRetrievalworkshop(LMIR),2001.[17]ClaudeE.Shannon.Amathematicaltheoryofcommunication.BellSystemTechnicalJournal,27:379–423,623–656,1948.[18]MartijnSpitters,WesselKraaij.Languagemodelsfortopictracking.InW.BruceCroftandJohnLafferty(eds.)LanguageModelingforInformationRetrieval,KluwerAcademicPublishers,pages95–124,2003.[19]JinxiXuandRalphWeischedel.Aprobabilisticapproachtotermtranslationforcross-lingualretrieval.InW.BruceCroftandJohnLafferty(eds.)LanguageModelingforInformationRetrieval,KluwerAcademicPublishers,pages125–140,2003.[20]ChengxiangZhaiandJohnLafferty.Model-basedfeedbackinthelanguagemodelingapproachtoinformationretrieval.InProceedingsoftheTenthACMInternationalConferenceonInformationandKnowledgeManagement(CIKM’01),pages403–410,2001.4PROBABILITYSMOOTHINGDjoerdHiemstraUniversityofTwentehttp://www.cs.utwente.nl/~hiemstraDEFINITIONProbabilitysmoothingisalanguagemodelingtechniquethatassignssomenon-zeroprobabilitytoeventsthatwereunseeninthetrainingdata.Thishastheeffectthattheprobabilitymassisdividedovermoreevents,hencetheprobabilitydistributionbecomesmoresmooth.MAINTEXTSmoothingovercomestheso-calledsparsedataproblem,thatis,manyeventsthatareplausibleinrealityarenotfoundinthedatausedtoestimateprobabilities.Whenusingmaximumlikelihoodestimates,unseeneventsareassignedzeroprobability.Incaseofinformationretrieval,mosteventsareunseeninthedata,evenifsimpleunigramlanguagemodelsareused(seeN-GRAMMODELS):Documentsarerelativelyshort(sayonaverageseveralhundredsofwords),whereasthevocabularyistypicallybig(maybemillionsofwords),sothevastmajorityofwordsdoesnotoccurinthedocument.Asmalldocumentabout“informationretrieval”mightnotmentiontheword“search”,butthatdoesnotmeanitisnotrelevanttothequery“textsearch”.Thesparsedataproblemisthereasonthatitishardforinformationretrievalsystemstoobtainhighrecallvalueswithoutdegradingvaluesforprecision,andsmoothingisameanstoincreaserecall(possiblydegradingprecisionintheprocess).Manyapproachestosmoothingareproposedinthefieldofautomaticspeechrecognition[1].Asmoothingmethodmaybeassimpleso-calledLaplacesmoothing,whichaddsanextracounttoeverypossibleword.Thefollowingequationsshowrespectively(8)theunsmoothed,ormaximumlikelihoodestimate,(9)Laplacesmoothing,(10)Linearinterpolationsmoothing,and(11)Dirichletsmoothing[3]:PML(T=t|D=d)=tf(t,d)/Pt′tf(t′,d)(8)PLP(T=t|D=d)=(tf(t,d)+1)/Pt′(tf(t′,d)+1)(9)PLI(T=t|D=d)=λPML(T=t|D=d)+(1−λ)PML(T=t|C)(10)PDi(T=t|D=d)=(tf(t,d)+µPML(T=t|C))/((Pt′tf(t′,d))+µ)(11)Here,tf(t,d)isthefrequencyofoccurrenceofthetermtinthedocumentd,andPML(T|C)istheprobabilityofatermoccurringintheentirecollectionC.Bothlinearinterpolationsmoothing(seealsotheentryLANGUAGEMODELS)andDirichletsmoothingassignaprobabilityproportionaltothetermoccurrenceinthecollectiontounseenterms.Here,λ(0<λ<1)andµ(µ>0)areunknownparametersthatshouldbetunedtooptimizeretrievaleffectiveness.Linearinterpolationsmoothinghasthesameeffectonalldocuments,whereasDirichletsmoothinghasarelativelybigeffectonsmalldocuments,butarelativelysmalleffectonbiggerdocuments.Manysmoothedestimatorsusedforlanguagemodelsininformationretrieval(includingLaplaceandDirichletsmoothing)areapproximationstotheBayesianpredictivedistribution[2].CROSSREFERENCELANGUAGEMODELS,N-GRAMMODELSRECOMMENDEDREADING[1]StanleyF.ChenandJoshuaGoodman.Anempiricalstudyofsmoothingtechniquesforlanguagemodeling.TechnicalReportTR-10-98,CenterforResearchinComputingTechnology.HarvardUniversity,August1998.[2]HugoZaragoza,DjoerdHiemstra,MichaelTipping,andStephenRobertson.BayesianExtensiontotheLanguageModelforAdHocInformationRetrieval.InProceedingsofthe26thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval,pages4-9,2003.[3]ChengXiangZhaiandJohnLafferty.Astudyofsmoothingmethodsforlanguagemodelsappliedtoinformationretrieval.ACMTransactionsonInformationSystems(TOIS)22(2),pages179-214,2004.5N-GRAMMODELSDjoerdHiemstraUniversityofTwentehttp://www.cs.utwente.nl/~hiemstraDEFINITIONInlanguagemodeling,n-grammodelsareprobabilisticmodelsoftextthatusesomelimitedamountofhistory,orworddependencies,wherenreferstothenumberofword