PROBABILISTIC CONSTRAINT LOGIC PROGRAMMING

BerichtNr.117,November1997ISSN0947-6954/97ArbeitspapieredesSonderforschungsbereichs340SprachtheoretischeGrundlagenfurdieComputerlinguistikStefanRiezler:ProbabilisticConstraintLogicProgrammingUniversitatStuttgartUniversitatTubingenDeutschlandInformationssystemeGmbHArbeitspapieredesSFB340BerichtNr.117,Oktober1997PROBABILISTICCONSTRAINTLOGICPROGRAMMINGSTEFANRIEZLERAbstract.Thispaperaddressestwocentralproblemsforprobabilisticprocess-ingmodels:parameterestimationfromincompletedataandecientretrievalofmostprobableanalyses.Thesequestionshavebeenansweredsatisfactorilyonlyforprobabilisticregularandcontext-freemodels.Weaddresstheseproblemsforamoreexpressiveprobabilisticconstraintlogicprogrammingmodel.Wepresentalog-linearprobabilitymodelforprobabilisticconstraintlogicprogramming.Ontopofthismodelwedeneanalgorithmtoestimatethepa-rametersandtoselectthepropertiesoflog-linearmodelsfromincompletedata.ThisalgorithmisanextensionoftheimprovediterativescalingalgorithmofDellaPietra,DellaPietra,andLaerty(1995).Ouralgorithmappliestolog-linearmodelsingeneralandisaccompaniedwithsuitableapproximationmeth-odswhenappliedtolargedataspaces.Furthermore,wepresentanapproachforsearchingformostprobableanalysesoftheprobabilisticconstraintlogicprogrammingmodel.Thismethodcanbeappliedtotheambiguityresolutionprobleminnaturallanguageprocessingapplications.1.IntroductionRabiner(1989)identiedthreebasicproblemsofinterestthatmustbesolvedforaHiddenMarkovModeltobeusefulinreal-worldspeechrecognitionapplications:theparameterestimationproblem,theoptimalstatesequenceproblemandtheobservationsequenceprobabilityproblem.Theseproblemsgeneralizetoarbitraryprobabilisticsymbolprocessingmodelsinvariousreal-worldapplicationsinanobviousmanner.Thersttwoproblemscanbestatedinamoregeneralwayasfollows.ThisworkwassupportedbytheGraduiertenkollegIntegriertesLinguistikstudiumattheUniversityofTubingenandbytheTeilprojektB7oftheSonderforschungsbereich340oftheDeutscheForschungsgemeinschaft.IamgreatlyindebtedtoStevenAbneyforcoachingthisworkinmanyhelpfuldiscussions.Furthermore,IwouldliketothankGrahamKatzandDetlefPrescherfortheirvaluablecomments.ISSN0947-6954/97c1997DerAutor12STEFANRIEZLER1.LetanunanalyzedobservationsequenceO=O1;:::Onandaprob-abilisticprocessingmodelwithparametersetbegiven,andsup-posethatthevalueofisunknownandOformsarandomsamplefromthedistributioninvolving,howcanthemodelparametersbeestimated?2.GivenOiand,howcanthemostprobableanalysisoftheinputOibefoundeciently?Recentinterestinprobabilisticmodelsofnaturallanguageprocessingcanbeattributedtothefactthatsolutionstotheabove-mentionedgeneralproblemscanleadquitedirectlytoeective,butconceptuallysimpleandmathematicallyclearsolutionstovariousproblemsinnaturallanguageprocessing.Thisconnectioncanbeillustratedwiththeproblemofambiguityreso-lution(ordisambiguationorparseranking)asfollows:Grammarsdescrib-inganontrivialfragmentofnaturallanguagemayattachalargenumberofdierentanalysestosentencesofreasonablelength.Sincenotalloftheseanalysesareinaccordwithhumanperceptions,thereisclearlyaneedtodistinguishmoreplausibleanalysesofaninputfromlessplau-sibleortotallyspuriousones.Thesimplebuteectiveideaadoptedinprobabilisticgrammarsistoconnecttheplausibilityofananalysiswithitsprobability.Inthisveinthecorrect,i.e.,mostplausibleanalysisofastringisassumedtobethemostprobableanalysisofthestring.Asolutiontoproblem1willadaptthemodelparameterstotheinputcorpusOandthusjustifytheassumptionthatthecorrectparseofastringOiisthemostprobableparseofOiasproducedbythegrammarparametrizedby.Asolutiontoproblem2willyieldanalgorithmtosearchforthemostprobableparseofagiveninputstringOiasproducedbyaprobabilisticgrammarwithparameterset.Mostpopularapproachestosolvingtheseproblemsintheareaofnat-urallanguageprocessingarebasedonBaum’smaximizationtechnique,whichisknownasthe\Baum-Welchalgorithm(BaumandEagon1967;Baum,Petrie,Soules,andWeiss1970;Baum1972).Thisalgorithmesti-matestheparametersofaHiddenMarkovModel,i.e.,astochasticregulargrammar,inaframeworkofmaximumlikelihoodestimationfromincom-pletedata.Thismeans,theparametersareiterativelyreestimateduntilconvergencetoasetofvalueswhichlocallymaximizethelikelihoodfunc-tion,i.e.,theprobabilitythatthemodelassignstothegivenunanalyzedobservationsequence.Inthissensethemodelparametersareadjustedtobestdescribeagivenobservationsequence.Theestimationalgorithmcanbedenedinductivelyforwardsandbackwards,yieldingtheecientPROBABILISTICCONSTRAINTLOGICPROGRAMMING3\forward-backwardalgorithm1.Baker(1979)generalizedthisalgorithmtotheso-called\inside-outsidealgorithm2,whichecientlyestimatestheparametersofastochasticcontext-freegrammars.BothalgorithmsarespecialinstancesoftheEM-algorithmformaximum-likelihoodes-timationfromincompletedata(Dempster,Laird,andRubin1977).Adynamic-programmingapproachsimilartotheoneusedintheecientversionsoftheparameterestimationalgorithmscanbeusedtondthemostprobableanalysisofstochasticcontext-freeandstochasticregulargrammarsandisknownasthe\Viterbi-algorithm(Viterbi1967).TheclassofalgorithmsbaseduponBaum’smaxi