Recommended Reading Combinatory Categorial Grammar

Combinatory CategorialGrammarConstraining surface realisation inOpenCCGOpenCCG surface realisationsentence planOpenCCGrealiserLexiconGrammarsurface textSentence plans arehybrid logicdependency structuresWhat do the grammarand lexicon look like?Recommended Reading Michael White. 2006.Efficient Realization of Coordinate Structures inCombinatory Categorial Grammar. Research onLanguage and Computation, 4(1):39–75. Mark Steedman and Jason Baldridge. CombinatoryCategorial Grammar. To appear in Robert Borsley andKersti Borjars (eds.) Constraint-based approaches togrammar: alternatives to transformational syntax. Oxford:Blackwell. PDF (Will appear in February 2011.)Categorial GrammarCategorial grammars are lexicalised grammars a grammar is just a “dictionary” there are no language-specific grammar rules a grammar is a mapping from words to structuresrestaurantfoodservestheMapping notone-to-one!

Lexicalised grammarsMany kinds of lexicalised grammar Categorial grammars (including CCGs) Lexicalised Tree Adjoining Grammars (LTAGs) CFGs in Greibach Normal FormLexicalised grammars are more efficient thanarbitrary CFGs for NLG search space is simpler (Koller & Striegnitz, 2002)Categorial grammars (CGs)A CG is a mapping from words to categories i.e. a set of word-category pairsWhat do categories look like?restaurantfoodservestheCategoriesTwo kinds of category “atomic” categories “complex” categoriesAtomic categoriesEach CG is built around a finite set of atomiccategories simple, non-composite, atomic symbols similar to the symbols of a CFGExamples: S – sentence/clause NP – noun phrase N - noun PP – preposition phrase

Atomic categories in XMLUse atomcat elements with a type attribute atomcat type “S”/ atomcat type “NP”/ Complex categories Complex categories are built up from atomiccategory symbols From any finite set of atomic categories, canconstruct an infinite set of complex categoriesusing two operators– directional slash operators: / and \Traditional arithmetic notation is a useful analogyArithmetic notationArithmetic notation gives us a finite set of digits 0, 1, 2, . . ., 9And a small set of operators for describing an infiniteset of numbers: e.g., concatenation: 23, 456, 92789 addition: 2 7, 7 23, 456 65 subtraction: 45 - 6, (2 6) - (67- 34)Recursive definitionCategories are defined recursivelyAtomic categories constitute the “base” every atomic category is also a categoryThe recursion involves the slash operators if X and Y are both categories, then so is (X/Y) if X and Y are both categories, then so is (X\Y)

Simple examplesEmbedded examplescategorymeaningcategorymeaning(S\NP)verb phrase, intransitive verb((S\NP)/NP)transitive verb(NP/N)determiner((S\NP)/NP)/NPditransitive verb(N\N)noun post-modifier, relative clause((N\N)/NP)post-nominal (PP\NP)postposition((S\NP)\((S\NP)/NP))reflexive pronoun((N\N)/(S\NP))relative pronounNotational conveniencesDrop outermost parentheses (S\NP) S\NP ((N\N)/(S\NP)) (N\N)/(S\NP)Assume left associativity of / and \ ((S\NP)/NP)/NP S\NP/NP/NP (N\N)/(S\NP) N\N/(S\NP)Complex categories in XMLHow to represent S\NP: complexcat atomcat type “S”/ slash dir “\”/ atomcat type “NP”/ /complexcat

S\NP/NP in XMLN\N/(S\NP) in XML complexcat atomcat type “N”/ slash dir “\”/ atomcat type “N”/ slash dir “/”/ complexcat atomcat type “S”/ slash dir “\”/ atomcat type “NP”/ /complexcat /complexcat complexcat atomcat type “S”/ slash dir “\”/ atomcat type “NP”/ slash dir “/”/ atomcat type “NP”/ /complexcat Categories - summaryWhat does X/Y mean?The kind of word or phrase that combines witha following Y to form an X.atomiccategoriesslash operatorscomplexcategoriesX/YYXThis rule is called forward application.

eNP / NinPP/NPthe restaurantNPNPPPDeterminer: word that combines with afollowing N to give an NP, i.e., an NP/N.Preposition: word that combines with afollowing NP to give a PP, i.e., a PP/NP.DerivationsAttributive NPPAttributive adjective: word that combineswith a following N to give another N, i.e., anN/N.

Adjective stackinggreatN/NItalianN/NrestaurantNNWhat does X\Y mean?The kind of word or phrase that combines witha preceding Y to form an X.YX\YXNThis rule is called backward application.Intransitive verbsGiovanni’sNProcksS\NPSIntransitive verb: word that combines witha preceding NP to give an S, i.e., an S\NP.Postpositionsone floorNPabovePP\NPPPPostposition: word that combines with apreceding NP to give a PP, i.e., a PP\NP.

Transitive verbsGiovanni’sNPservesS\NP/NPRelative \NPN\NSNTransitive verb: word that combines with afollowing NP to give an intransitive verb, S\NP.Relative pronoun: word that combineswith a following intransitive verb S\NP togive a noun postmodifier N\N.AdverbsThe story so dverb: word that combines with afollowing intransitive verb S\NP to giveanother intransitive verb S\NP. A categorial grammar is a mapping fromwords to categories Categories can be atomic or complex Words are combined into phrases by forwardand backward application

Our lexiconWhat does our grammar do?Giovanni’s :- NPpasta :- NPserves :- S\NP/NP It tells us which strings of words aregrammatical and which are not.rocks :- S\NPrestaurant :- Ngreat :- N/N It assigns derivational structure to thegrammatical strings.a : NP/Nthat :- N\N/(S\NP)Remember HLDS? But what about semantics?Adding HLDS to our lexicon The input to the OpenCCG realiser is a hybridlogic dependency structureTwo steps: So our categorial lexicon needs to includeHLDS in some way1. Add a nominal to each atomic category symbol We need to be able to relate the grammaticalsentences with their HLDS (interpretation)2. Add a set of elementary predications of hybridlogic to each lexical category And also to relate HLDSs to the grammaticalsentences that can realise them (generation)Then relax and let forward and backward application(i.e. unification) take care of the rest!

Our lexicon again1. Adding nominals to categoriesGiovanni’s :- NPGiovanni’s :- NPx Subscripts to atomic category symbolspasta :- NPpasta :- NPxserves :- S\NP/NPserves :- Se\NPx/NPy Referential indices: unique labels forobject or event evoked by the wordrocks :- S\NProcks :- Se\NPxrestaurant :- Nrestaurant :- Nxgreat :- N/Ngreat :- Nx/Nxa : NP/Na : NPx/Nxthat :- N\N/(S\NP)that :- Nx\Nx/(Se\NPx)Adding nominals in XML Coindexed nominals indicate thereferent of the argument is the same asreferent of result, e.g., “great”Nominal coindexation in XML atomcat type “NP”/ atomcat type “NP” fs feat attr “index” lf nomvar name “X”/ /lf /feat /fs /atomcat By convention, use x, y, z for objects,and e, f, g for eventsNx\Nx complexcat atomcat type “N” fs feat attr “index” lf nomvar name “X”/ /lf /feat /fs /atomcat slash dir “\” atomcat type “N” fs feat attr “index” lf nomvar name “X”/ /lf /feat /fs /atomcat /complexcat

2. Adding EPs to categoriesIntransitive verbsGiovanni’s :- NPx : @x Giovanni’spasta :- NPx : @x pastaGiovanni’sNPyserves :- Se\NPx/NPy : @e serve, @e AGENT x,@e THEME yrocks :- Se\NPx : @e great, @e THEME x@y Giovanni’srocksSe\NPx@e great, @e THEME xrestaurant :- Nx : @e restaurant, @e THEME xgreat :- Nx/Nx : @e great, @e THEME xSe : @ea : NPx/Nx :great, @e THEME x, @x Giovanni’sthat :- Nx\Nx/(Se\NPx) :Transitive verbsGiovanni’sNPw@w Giovanni’sservesSe\NPx/NPy@e serve@e AGENT x@e THEME yAttributive adjectivespastaNPv@v pastaSe\NPx@e serve, @e AGENT x@e THEME y, @y pastaSe :@e serve, @e AGENT x, @e THEME y,@x Giovanni’s, @y pastagreatNz/Nz@g great@g THEME zItalianNy/NyrestaurantNx@f italian@f THEME y@e restaurant@e THEME xNx@e restaurant, @e THEME x,@f italian, @f THEME xNx : @e restaurant, @e THEME x,@f italian, @f THEME x, @g great, @g THEME x

So where are we? We ve seen how to define a lexicon in CG We ve learned about two important operators inCG, i.e., forward and backward application We ve seen how to combine words both– Syntactically (derivations, unification), andFrom CG to CCGCCG is an “extension” of CG.CCG has more rules: forward and backward type raising forward and backward composition– Semantically (set union of elementary predications) But, Combinatory Categorial Grammar gives usmuch moreForward type raisingXEverything else remains the same in particular the HLDS representations.Type Raising CCG includes type-raising rules, which turn arguments intofunctions over functions over such arguments Forward type raisingTXY/(Y\X)TY/(Y\X) Example:JohnNPS/(S\NP)JohnNPTTS/(S\NP) The rules are order preserving. Here we turn an NP into arightward looking function over leftward functions,preserving the linear order of constituents

Multiple derivationsQ1: I know what restaurant serves French food, but whatrestaurant serves Italian food?A1: BabboservesNPItalian food.S\NP/NPNPForward compositionX/YQ2: I know what kind of food Pierre s serves, but what kind offood does Babbo serve?servesNPS\NP/NPBX/ZS\NPA2: BabboY/ZItalian PCCG is more flexibleCCG generates more sentences: object relative clauses –“a restaurant that [John likes]S/NP” right node raising –“[John likes]S/NP but [Charles hates]S/NPGiovanni’s”CCG is more flexibleCCG allows one sentence to be derived inmany ways reflecting different intonation patterns allowing incremental (i.e. left-branching)derivations from a right-branching lexicon

Further Reading Jason Baldridge and Geert-Jan Kruijff. 2003. “Multi-ModalCombinatory Categorial Grammar”. In Proceedings of EACL2003. Mike White and Jason Baldridge. 2003. “Adapting ChartRealization to CCG”. In Proceedings of ENLG 2003. Jason Baldridge and Geert-Jan Kruijff. 2002. “Coupling CCGwith Hybrid Logic Dependency Semantics”. In Proceedings ofACL 2002.

hybrid logic dependency structures What do the grammar and lexicon look like? Categorial Grammar Categorial grammars are lexicalised grammars a grammar is just a “dictionary” there are no language-specific grammar rules a grammar is a mapping from words to stru