Computational
Linguistics
CSC 485 Summer 2020
8
8. Mildly Context-Sensitive Grammar Formalisms
Gerald Penn
Department of Computer Science, University of Toronto
Based on slides by David Smith, Dan Klein, Stephen Clark and Eva Banik
Copyright © 2017 Gerald Penn. All rights reserved.
Combinatory Categorial Grammar
15
Combinatory Categorial Grammar (CCG)
•
•
•
Categorial grammar (CG) is one of the oldest grammar formalisms
Combinatory Categorial Grammar now well established and computationally well founded (Steedman, 1996, 2000)
Account of syntax; semantics; prosody and information structure; automatic parsers; generation
16
Combinatory Categorial Grammar (CCG)
•
•
•
•
CCG is a lexicalized grammar
An elementary syntactic structure – for CCG a lexical category – is assigned to each word in a sentence
walked: S\NP “give me an NP to my left and I return a sentence”
A small number of rules define how categories can combine
Rules based on the combinators from Combinatory Logic
17
CCG Lexical Categories
• •
• • •
transitive verb: (S \NP )/NP respected
Atomic categories:S ,N ,NP ,PP ,…(not many more)
Complex categories are built recursively from atomic categories and slashes, which indicate the directions of arguments
•
intransitive verb: S \NP walked
Complex categories encode subcategorisation information
ditransitive verb: ((S \NP )/NP )/NP gave Complex categories can encode modification
•
PP nominal: (NP \NP )/NP
• •
PP verbal: ((S \NP )\(S \NP ))/NP
18
ccg Grammar Simple CCG Derivation
A Simple ccg Derivation
interleukin − 10 NP
inhibits production
(S \NP )/NP
S \NP S
NP
> <
> forward application < backward application
19
ccg Gram
Function Application Schemata
unction Application Rule Schemata
•
Forward (>) and backward (<) application:
X/Y Y ⇒ X (>) Y X\Y ⇒ X (<)
20
F
Classical Categorial Grammar
Classical Categorial Grammar
ccg Grammar
• •
‘Classical’ Categorial Grammar only has application rules Classical Categorial Grammar is context free
S
NP (S\NP)/NP NP
interleukin-10 inhibits production
S\NP
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2
21
2
0
Classical Categorial Grammar
ccg Grammar
Classical Categorial Grammar
• •
‘Classical’ Categorial Grammar only has application rules Classical Categorial Grammar is context free
S
NP V NP
interleukin-10 inhibits production
VP
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2
22
Extraction out of a Relative Clause
The company
which
(NP\NP)/(S/NP) NP
Microsoft bought
NP (S\NP)/NP S /(S \NP )S /NP
NP \NP
NP/N
NP
N
> T type-raising
> B forward composition
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
23
Extraction out of a Relative Clause
The company
which Microsoft bought
(NP\NP)/(S/NP) NP
S /(S \NP )S /NP
NP/N
NP
N
(S\NP)/NP
> T type-raising
NP
NP \NP
>T
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
24
Extraction out of a Relative Clause
The
NP/N
company
N
which Microsoft bought
NP
>T
S /NP
(NP\NP)/(S/NP) NP S/(S\NP)
(S\NP)/NP
>B
> T > B
type-raising
forward composition
NP
NP \NP
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
25
Extraction out of a Relative Clause
The company
NP/N N
which Microsoft bought
(NP\NP)/(S/NP) NP S/(S\NP)
(S\NP)/NP
>B >
>T
S /NP
NP
NP \NP
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
26
Extraction out of a Relative Clause
The
NP/N
company which Microsoft bought
N
(NP\NP)/(S/NP) NP (S\NP)/NP > >T
NP
S/(S\NP)
S /NP
NP \NP
<
>B >
NP
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
27
Forward Composition and Type-Raising
Forward composition (>B):
X/Y Y/Z ⇒ X/Z (>B)
Type-raising (T):
X ⇒T/(T\X) (>T)
X ⇒T\(T/X) (
S/(S\NP) S/NP S/NP
(S \NP )/NP S/NP
conj NP (S \NP )/NP NP >T
> T type-raising
S
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
29
“Non-constituents” in ccg – Right Node Raising
Google
sells
but
conj
S /NP S
Microsoft buys shares
NP S/(S\NP)
> T type-raising
> B forward composition
>T
S/(S\NP)
S/NP >B
(S \NP )/NP S/NP >B
NP (S \NP )/NP NP >T
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
30
“Non-constituents” in ccg – Right Node Raising
Google
sells
but
conj
Microsoft buys shares
NP S/(S\NP)
>T
S/(S\NP)
(S \NP )/NP S/NP >B
NP (S \NP )/NP NP >T
S /NP S
S/NP >B <Φ>
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
31
“Non-constituents” in ccg – Right Node Raising
Google
sells
but
conj
Microsoft buys shares
NP S/(S\NP)
>T
S/(S\NP)
S/NP >B
(S \NP )/NP S/NP >B
NP (S \NP )/NP NP >T
S /NP S
<Φ>
>
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
32
Combinatory Categorial Grammar
ccg is mildly context sensitive
Natural language is provably non-context free
Constructions in Dutch and Swiss German (Shieber, 1985) require more than context free power for their analysis
these have crossing dependencies (which ccg can handle)
•
• •
•
Type 0 languages Context sensitive languages Context free languages Regular languages
Mildly context sensitive languages = natural languages (?)
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
33
9(‘(:/(-+.&0:$)()*?+)$/+O<:/+3.$909('(:/(-+ + 91+:1;9$'(-+.&0:$)()*6 PP2+E0.:()* • ! Q<''1+R;$)$ST+ Categories encode argument sequences 2+E0.:()* CCG Semantics ! P$;9()0/$.1+ P0/&*$.(0'+ 2.0;;0. '&L(-0'(U&%+ • and lambda calculus semantic operations *.0;;0. Parallel syntactic combinator operations ! P0/&*$.(&:+&)-$%&+ 0.*<;&)/+ :&V<&)-&: ! W&.1+-'$:&'1+ .&'0/&%+/$+/4&+ '0;9%0+-0'-<'<: ! P0)+40I&+:3<.($<:+ 0;9(*<(/(&:+R541MT 34 P CCG Semantics Left arg. Right arg. Operation Result X/Y : f Y :a Forward application X : f(a) Y :a X\Y : f Backward application X : f(a) X/Y : f Y/Z : g Forward composition X/Z : λx.f(g(x)) X :a Type raising T/(T\X) : λf.f(a) etc. 35 Tree Adjoining Grammar 36 TAG Building Blocks • Elementary trees (of many depths) • Harry likes peanuts passionately. •αα Tree Substitution Grammar equivalent to TAG Building Blocks Substitution at ↓ 1 NP 2 S Harry H HHHH NP peanuts VP NP↓ VP HHH CFG HHH NP↓ VP HHH V NP↓ V TAG Building Blocks NP↓ Harry likes peanuts passionately. NP S α3 βα1 α2HH likes HHHH H VP* Adv passionately Harry likes α3 NP β VP 3 HHH 37 peanuts H H TAG Building Blocks TAG Building Blocks • Auxiliary trees for adjunction α1 NP α2 S • Adds extra power beyond CFG HHHHH NP↓ VP H TAG Building Blocks HH Harry likes peanuts passionately. α1NPα2S NPVP Harry H HH likes α3 NP β VP peanuts HHHHH VP* Adv Harry likes peanuts passionately. likes HHHH α3 β H NP↓ VP HH V NP↓ peanuts HH H VP* Adv passionately passionately Harry V NP↓ 38 TAG Building Blocks Harry likes peanuts passionately. α1 NP α2 S Harry HHHHH NP↓ VP Derivation TreeHHH Derived Tree S α1 likes HHHHHHHH V NP↓ HHHHHHH αNP VPH H 3 β H H HH HH NP VP1 H α2 β HH α3 Harry passionately peanuts HH peanuts VP* Adv passionately Semantics H H Harry(x) ∧ likes(e, x, y) ∧ peanuts(y) ∧ passionately(e) 4 Harry VP2 HHHH V 3 NP likes peanuts HHHH Adv passionately 39