Linking Syntax and Semantics

Aim:

To describe an interpretation algorithm that uses the syntactic analysis of a sentence together with grammar rules augmented by feature information describing how the semantic analysis of a phrase is derived from the semantic analyses of its constituents. We shall show how this works for a simple grammar and then investigate a few more complicated examples, including the handling of auxiliary verbs, and prepositional phrases.
The concepts of lambda-expression and lambda-reduction are central to the handling of certain grammar rules.

Reference: Chapter 9 of Allen, J.: Natural Language Understanding, 2nd ed., Benjamin Cummings, 1995.

Keywords: CNP, common noun phrase, lambda reduction, VAR feature

Plan:

Every constituent must have an interpretation - lambda-expressions, lambda-reduction
Example: grammar rules with semantic interpretation via features
The var feature
Lexicon entries with sem features
Handling PPs and VPs with lambda-expressions
Handling different types of PPs

James Allen

James Allen, who wrote the textbook we follow in the NLP section of this course, is a professor in Computer Science at the University of Rochester in the USA. Allen is a distinguished researcher in the NLP field, and a former editor-in-chief of the important NLP journal Computational Linguistics. The picture is from his home page, which is linked above.

James Allen

Interpretation Algorithm

The interpretation algorithm is compositional.
So we must be able to write down a meaning expression for each phrase in a sentence: S, NP, VP, PP, N, V, ...
What is the meaning of a VP like kissed Sue in Jack kissed Sue ?
The logical form for Jack kissed Sue would be:

kiss1(k1, name(J1, 'Jack'), name(S1, 'Sue'))
Clearly there is something "missing" in _ kissed Sue, and we need to signal this in the logical form.

Lambda Expressions

The lambda calculus provides a formalism to express such logical forms with missing components.
lambda(X, kiss1(k1, X, name(S1, 'Sue')))

is a predicate that takes one argument.
The argument symbol X marks the "gap" in the VP.
Since it is a predicate, you can apply it to an argument (such as name(J1, 'Jack') ) as follows:

lambda(X, kiss1(k1, X, name(s1, 'Sue'))) (name(j1, 'Jack')) *

Lambda Expressions 2

We can use a step called lambda reduction (λ-reduction) to simplify *.
Let p(X) be a proposition about the variable X. Read lambda(X, p(X))(a) as "lambda(X, p(X)) applied to a". Lambda reduction says that lambda(X, p(X))(a) = p(X | a) - i.e. that to apply lambda(X, p(X)) to a you replace every occurrence^† of X in p(X) by a. (The "lambda(X, " and ")" are also dropped.)
Thus the expression marked * above reduces to:

kiss1(k1, name(j1, 'Jack'), name(s1, 'Sue'))

† technically, you replace every free occurrence of X in p(X) by a.

Lambda Expressions 3

PP modifiers can be handled similarly:
in the store as in The man in the store or The man is in the store has as meaning

lambda(X, at_loc(X, the<s1, store1>)).
This can be applied to the<m1, man1> to produce

at_loc(the<m1, man1> the<s1, store1>).

9.2 Grammar / Lexicon with Semantic Interpretation

We add a sem (semantic) feature to each lexical entry and grammatical rule to hold logical forms. E.g.

S(sem(?semvp(?semnp))) → NP(sem(?semnp)) VP(sem(?semvp))
Example: apply this rule to an NP with sem name(m1, 'Mary') and a VP with sem lambda(A, sees1(e8, A, name(j1, 'Jack')))
The sem feature of the S, ?semvp(?semnp), becomes
lambda(A, sees1(e8, A, name(j1, 'Jack'))) (name(m1, 'Mary'))
which simplifies to
sees1(e8, name(m1, 'Mary'), name(j1, 'Jack'))

Parse Tree with Logical Form (SEM) Features

The whole of the parse/semantic tree for this sentence (Mary sees Jack) is shown below (equivalent to Fig. 9.1 of Allen):

Semantic parse tree for 'Mary sees Jack'

Grammatical Rules with sem Features

Like Table 9.3 in Allen
1	S(sem(?semvp(?semnp))) → NP(sem(?semnp)) VP(sem(?semvp))
2	VP(var(?v), sem(lambda(a2, ?semv(?v, a2)))) → V[_none](sem(?semv))
3	VP(var(?v), sem(lambda(a3, ?semv(?v, a3, ?semnp)))) → V[np](sem(?semv)) NP(sem(?semnp))
4	NP(wh(-), var(?v), sem(pro(?v, ?sempro))) → PRO(sem(?sempro))
5	NP(var(?v), sem(name(?v, ?semname))) → NAME(sem(?semname))
6	NP(var(?v), sem(?semdet(?v, ?semcnp(?v)))) → DET(sem(?semdet)) CNP(sem(?semcnp))
7	CNP(sem(?semn)) → N(sem(?semn))

Head_feature(s, vp, np, cnp) = var

The var feature

The var feature is new and stores the "discourse variable" that corresponds to the constituent.
var features will be useful for handling certain forms of modifiers in the development that follows.
They are automatically generated by the parser when a lexical constituent is constructed for a word.
They are passed up the tree by treating var as a "head feature".

Implementing Features in Prolog

There are several choices for implementing features in Prolog. Let's consider a noun (N) with agr(3s). Here are three possibilities:
n(agr(3s))
n(agr/3s) works - remember that Prolog doesn't try to evaluate / unless is (or an arithmetic comparison operator) is used.
Positional coding: with this you decide that, say, the third argument in a term with a particular functor will always be the agr feature: n(…, …, 3s, …)

Implementing Features in Prolog 2

We will illustrate using the grammar rule VP → V (intransitive verb):

vp(P1, P2, vp(Verb), lambda(X, SemBody), VarV) :-
        v(P1, P2, Verb, SemV, VarV),
        SemBody =.. [SemV, VarV, X].

Note 1: The built-in infix predicate =.. (pronounced "univ") converts a list into a term, and works like this:
```
?- Term =.. [likes, mary, pizza].

Term = likes(mary, pizza)
```
Note 2: We are using positional coding for features in the vp term:
- the third argument is the syn feature, which is used to record the syntactic analysis of the phrase;
- the fourth argument is the sem feature, which is used to record the semantic analysis of the feature;
- the fifth argument is the var feature;
- (and the first two arguments, P1 and P2, are the start and finish positions of the phrase in the sentence, as with the Prolog syntax rules that we met earlier.)
- the λ-expression for the semantic interpretation is constructed just by writing it in the sem slot in the head of the rule.
- however the SemBody has to be constructed using univ, because it involves a term whose functor is only available as a variable (SemV).
- The var slot for the vp is filled by noting that the var of the vp is the same as the var of the v (var is a head feature for vp) so we just put VarV in the var slot in the head of the rule.

Implementing Features in Prolog 3

Let's see the vp rule in action - we need some facts. Let's suppose that v(2, 3, laugh, laugh1, l1) has already been proven using the rule for v, like the syntax rule for v that we saw earlier, but enhanced to provide a semantic analysis ( laugh1 ) and a var feature ( l1 ).

Then the query ?- vp(P1, P2, Syn, Sem, Var). results in the bindings:

P1 = 2
P2 = 3
Syn = vp(v(laugh))
Sem = lambda(_G300, laugh1(l1, _G300))
Var = l1

The _G300 in the Sem feature is the lambda variable; think of it as X. lambda(X, laugh1(l1, X)) says, roughly, that there is an instance l1 of laughing (strictly speaking, laugh1-ing), and someone (X) is the agent of this laughing, i.e. is the one who is doing the laughing.

Lexical Entries with Semantic Information

Like Table 9.2 of Allen
a det(agr(3s), sem(a))

can aux(subcat(base), sem(can1))

car n(sem(car1), agr(3s))

cry v(sem(cry1), vform(base), subcat(none))

decide v(sem(decides1), vform(base), subcat(none))

decide v(sem(decides_on1), vform(base), subcat(pp:on))

dog n(sem(dog1), agr(3s))

Like Table 9.2 of Allen
a	det(agr(3s), sem(a))
can	aux(subcat(base), sem(can1))
car	n(sem(car1), agr(3s))
cry	v(sem(cry1), vform(base), subcat(none))
decide	v(sem(decides1), vform(base), subcat(none))
decide	v(sem(decides_on1), vform(base), subcat(pp:on))
dog	n(sem(dog1), agr(3s))

Lexical Entries with Semantic Information 2

Like Table 9.2 of Allen (continued)
fish	n(sem(fish1), agr(3s))
fish	n(sem(plur(fish1)), agr(3p))
house	n(sem(house1), agr(3s))
has	aux(vform(pres), agr(3s), subcat(pastprt), sem(perf))
he	pro(sem(he1), agr(3s))
in	p(pform([loc, mot]), sem(at_loc1))
Jill	name(agr(3s), sem('Jill'))

Lexical Entries with Semantic Information 3

Like Table 9.2 of Allen (continued)
man	n(sem(man1), agr(3s))
men	n(sem(plur(man1)), agr(3p))
on	p(pform([loc, on]), sem(on_loc1))
saw	v(sem(sees1), vform(past), subcat(np))
see	v(sem(sees1), vform(base), subcat(np), irreg_past(+), en_pastprt(+))
she	pro(sem(she1), agr(3s))
the	det(sem(the), agr([3s, 3p]))
to	to(agr(-), vform(inf))

Handling Semantic Interpretation

The chart parser can be modified so that it handles semantic interpretation as follows:

When a lexical rule is instantiated for use, the var feature is set to a new discourse variable;
whenever a constituent is built, the sem is simplified by performing any lambda reductions that are possible.

Interpreting an example sentence: Jill saw the dog

The word Jill is parsed as a name. A new discourse variable, j1, is generated, and set as the var feature of the name.
This constituent is used with rule 5 to build an NP. Since var is a head feature, var j1 is passed up to the NP, and the sem is built using rule 5 to give sem name(j1, 'Jill')
The lexical entry for the word saw generates a V constituent with the sem past(sees1) and a new var ev1.
The lexical entry for the produces sem the.

Interpreting an example sentence 2

The lexical entry for dog produces a N constituent with sem dog1 and var d1. This in turn gives rise to a CNP constituent with the same sem and var, via rule 7 .
Rule 6 combines the sems the and dog1 with the var d1 to produce an NP with the sem the(d1, dog1(d1)) and var d1.
the(d1, dog1(d1)) is combined with the sem of the verb and its var by rule 3 to form a VP with var ev1 and sem

lambda(X, past(sees1)(ev1, X, the(d1, dog1(d1))))

Interpreting an example sentence 3

This is then combined with the subject NP name(j1, 'Jill') to form the sem

past(sees1)(ev1, name(j1, 'Jill'), the(d1, dog1(d1)))

and var ev1 (after lambda-reduction).

Completed Parse Tree for Jill saw the dog (Fig. 9.5 Allen)

Semantic parse tree for 'Jill Saw The Dog'

9.3 Prepositional Phrases and Verb Phrases

Auxiliary Verbs

Auxiliary verbs use the grammar rule:

VP(sem(lambda(A1, ?semaux(?semvp(A1))))) →
AUX(subcat(?v), sem(?semaux)) VP(vform(?v), sem(?semvp))
If the ?semaux is a modal operator like can1, and ?semvp is a λ-expression such as lambda(X, laughs1(e3, X)), then according to the rule above, the sem of the VP can laugh is

lambda(A1, can1( lambda(X, laughs1(e3, X)) (A1)))

Prepositional Phrases and Verb Phrases 2

This simplifies to lambda(A1, can1(laughs1(e3, A1)))
since lambda(X, laughs1(e3, X)) (A1) λ-reduces to laughs1(e3, A1)
In effect the variable for the subject is lifted through the can1 operator.
If there is more than one auxiliary, a similar process analyses the other auxiliary(ies).

Prepositional Phrases

PPs can modify an NP or a VP, or may be subcategorized for by a head word, in which case the preposition acts more as a flag for an argument than as an independent predicate.

Examples:

The man in the corner ate lunch.

PP modifies NP the man

The dog barked in the alley.

PP modifies VP barked

She is ready to take up the challenge.

up flags object of "take-up"

PP Modifying an NP

With a PP modifying an NP, the sem of the PP is a unary predicate to be applied to the sem of the NP:

PP(sem(lambda(Y, ?semp(Y, ?semnp))) → P(sem(?semp)) NP(sem(?semnp))
Given in the corner if the sem of the in is at_loc1, and the sem of the NP is the<c1, corner1>, then the sem of the PP would be the unary predicate

lambda(Y, at_loc1(Y, the<c1, corner1>))

PP Modifying an NP 2

In the context the man in the corner, we need a rule to attach the PP to the CNP (common noun phrase) man:

CNP(sem(lambda(N1, &(?semcnp(N1), ?sempp(N1))))) → CNP(sem(?semcnp)) PP(sem(?sempp))

[Here & means "and". It is used here as a prefix operator. Thus &(happy(fido), dog(fido)) would mean "Fido is happy and Fido is a dog". &(man1(x), in_loc1(x, the<c1, corner1>)) means "x is a man and (&) x is in the corner".

PP Modifying an NP 3

In Prolog, this rule would be:

cnp(P1, P3, cnp(SynCNP, SynPP),
            lambda(N1, &(SemCNPN1, LR_Result)),
            VarCNP) :-
    SemCNPN1 =.. [SemCNP, N1],
    cnp(P1, P2, SynCNP, SemCNP, VarCNP),
    pP(P2, P3, SynPP, SemPP, VarPP),
    lambda_reduce(SemPP,N1,LR_Result).

where lambda_reduce is defined by:

lambda_reduce(lambda(X, Predicate), Argument, Predicate) :-
     X = Argument.
lambda_reduce(Expression, _, Expression) :-
     Expression \= lambda(_, _).

PP Modifying an NP 4

The sem of man is the unary predicate MAN1, so the new sem of man in the corner is

lambda(N1, &(man1(N1), (lambda(Y, at_loc1(Y, the<c1, corner1>)) N1)))
As (lambda(Y, at_loc1(Y, the<c1, corner1>)) N1) simplifies to at_loc1(N1, the<c1, corner1>) , the whole expression becomes

lambda(N1, &(man1(N1), at_loc1(N1, the<c1, corner1>)))

PP Modifying an NP 5

Combining this with the using rule 6, we get the sem

the(m2, (lambda(N1, &(man1(N1), at_loc1(N1, the<c1, corner1>))) m2))

which simplifies to

the(m2, &(man1(m2), at_loc1(m2, the<c1, corner1>)))

PP Modifying a VP

Consider a PP modifying a VP: e.g. cry in the corner, as in Jill can cry in the corner.
The relevant syntactic rule would be VP → VP PP.
cry has logical form, i.e. sem, lambda(X, cries1(e1, X)) and var e1. The desired sem and var for cry in the corner are

lambda(A, &(cries1(e1, A), at_loc1(e1, the<c1, corner1>))) and e1

PP Modifying a VP 2

The appropriate semantically augmented rule is:

VP(var(?v), sem(lambda(X, &(?semvp(x), ?sempp(?v))))) →
VP(var(?v), sem(?semvp)) PP(sem(?sempp))

[NB: This VP rule will be superseded by two more specific ones soon.]

You are now in a position to do all of the exercises at http://www.cse.unsw.edu.au/~cs9414/Exercises/semantics.html

PP Modifying a VP 3

Parse tree for cry in the corner using this rule: (like Allen Fig. 9.6, corrected):

Semantic parse tree for 'cry in the corner'

PP as a subcategorized constituent in a VP

Consider the phrase decide on a couch meaning, say, (a) decide to buy a couch.
There is an ambiguity here - this phrase could also mean (b) to make a decision while sitting on a couch. The appropriate syntactic rule for sense (a) is

VP → V[_pp:on] PP[on]
The desired final logical form for the VP is

lambda(S, decides_on1(d1, S, a<c1, couch1>))

with a<c1, couch1> appearing as an argument.

PP as a subcategorized constituent in a VP 2

Subcategorized PPs can be handled by distinguishing between "predicate" PPs and "argument" PPs using a binary feature pred (+ for predicate, – for argument).
A PP is a predicate in cases like "in the corner" in the previous example, where the preposition is interpreted using the predicate at_loc1.
A PP is an argument when its interpretation, or rather the interpretation of its NP, appears as one of the arguments of the verb, as a<c1, couch1> does in the λ-expression above.

predicate: decide (while sitting) on a couch = pred +

argument: decide on (e.g. to buy) a couch = pred –

Using the pred Feature in Grammar Rules

With the pred feature available, we can have two rules for PPs, one for each case:

PP(pred(+), sem(lambda(X, ?semp(X, ?semnp)))) → P(sem(?semp)) NP(sem(?semnp))
- interprets preposition as predicate

PP(pred(–), pform(?pf), sem(?semnp)) → P(root(?pf)) NP(sem(?semnp))
- interprets the NP in the PP as an argument of the verb
Head feature for PP: pform

Logical Forms of pred(+) and pred(–) PPs

The two analyses are shown below (cf. Figure 9.8 of Allen).
The analyses use VP rules found in Grammar 9.7 in Allen - these rules supersede the VP rule that we used previously:

VP(var(?v), sem(lambda(X1, &(?semvp(X1), ?sempp(?v))))) →
VP(sem(?semvp)) PP(pred(+), sem(?sempp))

VP(var(?v), sem(lambda(X2, ?semv(?v) X2 ?sempp))) →
V[pp:on](sem(?semvp)) PP(pred(–), pform(on), sem(?sempp))

Parse Trees for pred(+) and pred(–)

The upper tree is for sense (a) in which couch is an argument (pred(–)), and the lower tree is for sense (b) in which couch is the location modifier for decides.

Semantic parse for decide-on a-couch

Semantic parse for decide on-a-couch

Summary: Semantic Interpretation

The semantic interpretation algorithm is feature-driven: reading the augmented grammar rules right to left provides a description of how to build the SEM feature of the phrase described by the grammar rule. When the semantic description has a gap (as with VP), the SEM feature is a lambda-expression.

CRICOS Provider Code No. 00098G

Copyright (C) Bill Wilson, 2009, except where another source is acknowledged.

The man	in the corner ate lunch.
	PP modifies NP the man

The dog barked	in the alley.
	PP modifies VP barked

She is ready to take	up the challenge.
	up flags object of "take-up"

predicate: decide (while sitting) on a couch	= pred +
argument: decide on (e.g. to buy) a couch	= pred –