Constraint programming in computational linguistic

ConstraintProgramminginComputationalLinguisticsAlexanderKollerandJoachimNiehrenUniversityoftheSaarland,Saarbr¨ucken,GermanyConstraintprogrammingisaprogrammingparadigmthatwasoriginallyinventedincomputersciencetodealwithhardcombinatorialproblems.Recently,constraintprogramminghasevolvedintoatechnologywhichpermitstosolvehardindustrialschedulingandoptimizationproblems.Wearguethatexistingconstraintprogrammingtechnologycanbeusefulforapplicationsinnaturallanguageprocessing.Someproblemswhosetreatmentwithtraditionalmethodsrequiresgreatcaretoavoidcombi-natorialexplosionof(potential)readingsseemtobesolvableinaneffi-cientandelegantmannerusingconstraintprogramming.Weillustrateourclaimbytworecentexamples,onefromtheareaofunderspecifiedsemanticsandonefromparsing.1IntroductionThispaperisanoverviewoftechniquesofmodernconstraintprogram-ming(CP)andtheircurrentapplicationsincomputationallinguis-tics.WearguethatCPcanbethefoundationforefficient,elegantapproachestonotoriousproblemsinnaturallanguageprocessing.Constraintprogrammingisaparadigmthatemergedfromlogicpro-gramminginthemid-eighties(JaffarandLassez,1987;MarriottandStuckey,1998).Theaimofconstraintprogrammingistoprovideageneralplatformonwhich(typicallyNP-hard)combinatoricproblems,suchasschedulingandoptimization,canbesolvedefficiently.Tradi-tionally,onewoulduseagenerateandteststrategy,whereaspaceofmodelsisgeneratedandsearchedforsolutions;butthecomplexityand∗E-mail:[e-mail]@ps.uni-sb.de.SpecialthankstoDenysDuchier,whodevelopedmuchofthematerialwepresent.Wearealsogratefultoouranonymousreviewersforhelpfulcomments.TheresearchreportedherehasbeensupportedbytheCollaborativeResearchCenter(Sonderforschungsbereich)378oftheDFGandtheEspritWorkingGroupCCLII(EP22457).SubmittedforProceedingsofLLC8D.Barker-Plummer,D.Beaver,J.vanBenthem,P.ScottodiLuzio(eds.)Copyrightc2000,CSLIPublications12/AlexanderKoller,JoachimNiehrensizeoftheseproblemsmakesthesearchspacessohugethatthisstrat-egyisunfeasibleinpractice.CPfollowsastrategyofpropagateanddistributeinstead.Thecasedistinctionsthatconstitutesearchsteps(distribution)areputoffforaslongaspossible;first,simpledetermin-isticinferences(propagation)areapplied.Thatis,modeleliminationispreferredovermodelenumeration.Searchwillstillbenecessary,butgoodpropagationwillnarrowdownthepossiblechoicesinthedistri-butionsteps,thusreducingthesizeofthesearchspace,sometimesdramatically.Inthenineties,constraintprogramminghasevolvedintoamaturetechnology,andoff-the-shelfdevelopmentsystemsareavailable.CPhasbeenincorporatedintoseveralhostlanguages,e.g.C++(ILOG,1999)andProlog(Dincbasetal.,1988;AggounandBeldiceanu,1993;Aggounetal.,1995).TherearealsospecialprogramminglanguagesforCP,e.g.theconcurrentCPlanguageOz(Smolka,1995;MozartConsortium,1999)andothers(Smolka,1998;CaseauandLaburthe,1996).WewilluseOzinthispaper.CPhasbeenappliedsuccessfullytoschedulingandoptimizationproblemsinindustry(ILOG,1999;Ag-gounandBeldiceanu,1993).Themostusefulalgorithmsknownforconstraintpropagationapplytofinitedomain,finiteset,andarith-meticconstraints.Modernprogrammingsystemsallowprogrammerstocombinethesealgorithmsatahighlevelofabstraction.(Noticethattheword“constraint”in“constraintprogramming”hasonlyasuperficialrelationtoitsusagein“constraint-based”theoriese.g.ofgrammar,suchasHPSGandLFG.)ComputationallinguisticshasonlyrecentlybeendiscoveredasanapplicationofCP.Duchier(1999)presentedanapproachtoparsingdependencygrammarwhichisbasedonconstraintprogrammingwithfinitesets.Kolleretal.(1998)appliedconstraintprogrammingtose-manticunderspecification,andDuchierandGardent(1999),todis-course.Inalloftheseinstances,modeleliminationtechniquesareusedtocopewithambiguitieswhichcouldotherwisecauseseriouscombina-torialproblems.Inthispaper,wesurveythestateoftheartofconstraintpro-gramminginnaturallanguageprocessing.Ourgoalistoillustratethepowerofconstraintprogrammingatsuccessfulexamples,inthehopesofencouragingmorecomputationallinguiststoapplyCPfortheirownpurposes.InSection2,weexplainmodeleliminationinformallyandshowhowitcanbeusedinprincipletodealwithambiguities.InSection3,wediscussthebasicideasofConstraintProgramming.Thissectionalsointroducessomeofthemostimportanttypesofconstraints,inpartic-ConstraintProgramminginComputationalLinguistics/3ularfinitedomain,finiteset,andselectionconstraints.InSections4and5,wegothroughexamplesfromSection2inmoredetailandshowhowCPcanhelptosolvetheambiguityproblem.First,weimplementdominanceconstraints,asusedinacertainapproachtoscopeunder-specification.ThenwepresentaparserfordependencygrammarbasedonCP.WeconcludeandpointtofutureworkinSection6.ImplementationsofthesystemsdescribedinSections4and5,in-cludingsourcecodes,canbefoundonthe(Duchieretal.,1999).2ModelEliminationInthissection,wetakeacloser(butstillinformal)lookatmodelelimi-nation.Wefirstconsideranexamplethatshowshowmodeleliminationcanpreventcombinatorialexplosion,andintroducesthebasicintuition.Thenweturntotheproblemofhandlingambiguityincomputationallinguistics,wherecombinatorialexplosioncanbeaproblemtoo.Inthiscontext,modeleliminationisextremelyc