Some Uses of Higher Order Logic in Computational Linguistics

Description

Niveau: Supérieur
Some Uses of Higher-Order Logic in Computational Linguistics Dale A. Miller and Gopalan Nadathur Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 – 3897 April 1986 Abstract Consideration of the question of meaning in the framework of linguistics often requires an allusion to sets and other higher-order notions. The traditional ap- proach to representing and reasoning about meaning in a computational setting has been to use knowledge rep- resentation systems that are either based on first-order logic or that use mechanisms whose formal justifications are to be provided after the fact. In this paper we shall consider the use of a higher-order logic for this task. We first present a version of definite clauses (positive Horn clauses) that is based on this logic. Predicate and function variables may occur in such clauses and the terms in the language are the typed ?-terms. Such term structures have a richness that may be exploited in representing meanings. We also describe a higher-order logic programming language, called ?Prolog, which rep- resents programs as higher-order definite clauses and in- terprets them using a depth-first interpreter. A virtue of this language is that it is possible to write programs in it that integrate syntactic and semantic analyses into one computational paradigm. This is to be contrasted with the more common practice of using two entirely differ- ent computation paradigms, such as DCGs or ATNs for parsing and frames or semantic nets for semantic pro- cessing.

• has been


• most natural


• essentially higher-order definite


• natural language


• order logic


• can themselves


• higher-order logics


• variable


• over higher-order


• language can

Sujets

• Has Been
• Natural language
• Higher-order logic
• Variable

Informations

• Publié par: chaeh
• Nombre de lectures: 13
• Langue: English

Extrait

SomeUsesofHigher-OrderLogic inComputationalLinguistics DaleA.MillerandGopalanNadathur ComputerandInformationScience UniversityofPennsylvania Philadelphia,PA19104–3897 April1986 Abstract Considerationofthequestionofmeaninginthe frameworkoflinguisticsoftenrequiresanallusionto setsandotherhigher-ordernotions.Thetraditionalap- proachtorepresentingandreasoningaboutmeaningin acomputationalsettinghasbeentouseknowledgerep- resentationsystemsthatareeitherbasedonfirst-order logicorthatusemechanismswhoseformaljustifications aretobeprovidedafterthefact.Inthispaperweshall considertheuseofahigher-orderlogicforthistask. Wefirstpresentaversionofdefiniteclauses(positive Hornclauses)thatisbasedonthislogic.Predicate andfunctionvariablesmayoccurinsuchclausesand thetermsinthelanguagearethetypedλ-terms.Such termstructureshavearichnessthatmaybeexploitedin representingmeanings.Wealsodescribeahigher-order logicprogramminglanguage,calledλProlog,whichrep- resentsprogramsashigher-orderdefiniteclausesandin- terpretsthemusingadepth-firstinterpreter.Avirtueof thislanguageisthatitispossibletowriteprogramsinit thatintegratesyntacticandsemanticanalysesintoone computationalparadigm.Thisistobecontrastedwith themorecommonpracticeofusingtwoentirelydiffer- entcomputationparadigms,suchasDCGsorATNsfor parsingandframesorsemanticnetsforsemanticpro- cessing.Weillustratesuchanintegrationinthislan- guagebyconsideringasimpleexample,andweclaim thatitsusemakesthetaskofprovidingformaljustifica- tionsforthecomputationsspecifiedmuchmoredirect. ThisworkhasbeensupportedbyNSFgrantsMCS-82- 19196-CER,MCS-82-07294,AICentergrantsMCS-83- 05221,USArmyResearchOfficegrantARO-DAA29- 84-9-0027,andDARPAN000-14-85-K-0018. 1 1.Introduction Therepresentationofmeaning,andtheuseofsuch arepresentationtodrawinferences,isanissueofcentral concerninnaturallanguageunderstandingsystems.A theoreticalunderstandingofmeaningisgenerallybased onlogic,andithasbeenrecognizedthatahigher-order logicisparticularlywellsuitedtothistask.Montague, forexample,usedsuchalogictoprovideacompositional semanticsforsimpleEnglishsentences.Inthecompu- tationalframework,knowledgerepresentationsystems aregiventhetaskofrepresentingthesemanticalno- tionsthatareneededinnaturallanguageunderstand- ingprograms.Whiletheformaljustificationsthatare providedforsuchsystemsareusuallylogical,theactual formalismsusedareoftendistantlyrelatedtologic.Our approachinthispaperistorepresentmeaningsdirectly byusinglogicalexpressions,andtodescribetheprocess ofinferencebyspecifyingmanipulationsonsuchexpres- sions.Asitturnsout,mostprogramminglanguagesare poorlysuitedforanapproachsuchasours.Prolog,for instance,permitstherepresentationandtheexamina- tionofthestructureoffirst-orderterms,butitisnot easytousesuchtermstorepresentfirst-orderformulas whichcontainquantification.Lispontheotherhandal- lowstheconstructionoflambdaexpressionswhichcould encodethebindingoperationsofquantifiers,butdoes notprovidelogicalprimitivesforstudyingtheinternal structureofsuchexpressions.Alanguagethatisbased onahigher-orderlogicseemstobethemostnaturalve- hicleforanapproachsuchasours,andinthefirstpartof thispaperweshalldescribesuchalanguage.Weshall thenusethislanguagetodescribecomputationsofa kindthatisneededinanaturallanguageunderstanding system. Beforeweembarkonthistask,however,weneedto considertheargumentsthatareoftenmadeagainstthe computationaluseofahigher-orderlogic.Indeed,sev- eralauthorsinthecurrentliteratureoncomputational linguisticsandknowledgerepresentationhavepresented reasonsforpreferringfirst-orderlogicoverhigher-order logicinnaturallanguageunderstandingsystems,and amongstthesethefollowingthreeappearfrequently. (1)Go¨delshowedthatsecond-orderlogicisessentially incomplete,i.e.truesecond-orderlogicstatements arenotrecursivelyenumerable.Hence,theorem proversforthislogiccannotbe,eventheoretically,