Blackburn and Bos: Representation and Inference of Natural Language

Chapter 2: Lambda Calculus

Wie kann der Prozess der Zuweisung von semantischen Repräsentationen (z.B. in Form von prädikatenlogischen Formeln) zu natürlichsprachlichen Ausdrücken automatisiert werden?

2.1 Compositionality

Gegeben einen natürlichsprachlichen Satz (z.B. “Vincent likes Mia”), gibt es einen systematischen Weg seine semantische Repräsentation zu konstruieren?

Wie können wir garantieren, dass “Vincent likes Mia” und “Mia likes Vincent” zwei verschiedene semantische Repräsentationen zugewiesen bekommen?

Lösungsidee: Die Wörter liefern Teile der semantischen Repräsentation (“MIA”, “LOVE(X,Y)”) und die Syntax steuert ihre Verklebung (“LOVE(VINCENT,MIA)”).

Syntax Syntaktische Analysen sollten hierarchisch sein = Sätze sollten zerlegt werden in Teile und Unterteile usw.

Semantische Komposition \(\approx\) Verkleben der Teile

Lexicon entries look approximately like this: LOVE(?,?), MIA, VINCENT.

Syntactic analysis of a sentence is a tree whose non-leaf nodes represent complex syntactic categories and whose leaves represent lexical items.

Wechsle zu [[https://swish.swi-prolog.org/p/CompSem_Petersen_Material_Kapitel_2.swinb]]

2.3 The Lambda Calculus

Zur Erinnerung: In Experiment 2 haben wir eine erste Lösung für unsere Aufgabe, automatisch zu einem sprachlichen Ausdruck eine semantische Repräsentation zu produzieren, gefunden.

2.4 Implementing Lambda Calculus

Was müssen wir tun?

1. entscheiden wie \(\lambda x. E\) und \(\mathcal{F}@\mathcal{A}\) repräsentiert werden sollen.
2. Implementierung von \(\beta\)-Konversion
3. Implementierung von \(\alpha\)-Konversion

1. Lambda-Abstraktion und Applikation in Prolog

• \(\lambda x. E\) repräsentieren wir als lam(x,E).
• \(\mathcal{F}@\mathcal{A}\) repräsentieren wir als app(F,A).

Grammatikregeln:

s(app(NP,VP))--> np(NP), vp(VP).
np(PN)--> pn(PN).
np(app(Det,Noun))--> det(Det), noun(Noun).
vp(IV)--> iv(IV).
vp(app(TV,NP))--> tv(TV), np(NP).

Lexikoneinträge:

noun(lam(X,woman(X)))--> [woman].
iv(lam(X,walk(X)))--> [walks].
pn(lam(X,app(X,mia)))--> [mia].
det(lam(U,lam(V,all(X,imp(app(U,X),app(V,X))))))--> [every].
det(lam(U,lam(V,some(X,and(app(U,X),app(V,X))))))--> [a].

Anfragen:

?- s(Sem,[mia,walks],[]).

Aufgabe: Laden Sie die Datei experiment3.pl und testen Sie ein paar Sätze.

Implementing \(\beta\)-conversion

• Problem: Der semantische Output gibt lediglich an, wie die Information zu verkleben ist, um die semantische Repräsentation des Satzes zu erhalten.
• Ziel: Ausführung aller \(\beta\)-Konversionen.
• Idee: Stack zur Verwaltung der Argumente.

Expression                                          Stack
app(app(lam(Z,lam(Y,invite(Y,Z))),mia),vincent)        []
app(lam(Z,lam(Y,invite(Y,Z))),mia)              [vincent]
lam(Z,lam(Y,invite(Y,Z)))                  [mia, vincent]
lam(Y,invite(Y,mia))                            [vincent]
invite(vincent,mia)                                    []

Aufgabe: Übertragen Sie die Darstellung von der Präfix- in die Infixnotation und erklären Sie wie der Stack eingesetzt wird (was geschieht bei funktionaler Applikation, was bei Abstraktion?).

Das folgende Bild zeigt, die Aufspaltung eines Ausdrucks, der keine funktionale Applikation ist:

Implementierung:

% aus betaConversion.pl
% ?- betaConvert(app(lam(U,app(U,mia)),lam(X,smoke(X))),Converted).
% introducing empty stack
betaConvert(X,Y):-
   betaConvert(X,Y,[]).

% no change for variables   
betaConvert(X,Y,[]):-
   var(X), !,
   Y=X.

% expression is application => push argument to stack
betaConvert(Expression,Result,Stack):-
   nonvar(Expression),
   Expression = app(Functor,Argument),
   alphaConvert(Functor,Converted), 
   betaConvert(Converted,Result,[Argument|Stack]), !.

% expression is abstraction => pop argument from stack
betaConvert(Expression,Result,[X|Stack]):-
   nonvar(Expression),
   Expression = lam(X,Formula),
   betaConvert(Formula,Result,Stack), !.

% other expression 
% => break down complex expression 
betaConvert(Expression,Result,[]):-
   nonvar(Expression), 
   \+(Expression= app(X,_), nonvar(X)),
   compose(Expression,Functor,SubExpressions),
   betaConvertList(SubExpressions,ResultSubExpressions),
   compose(Result,Functor,ResultSubExpressions).

% beta convert lists
betaConvertList([],[]).

betaConvertList([Expression|Others], [Result|Results]) :- 
     betaConvert(Expression,Result),
     betaConvertList(Others,Results).

• Laden Sie experiment3.pl und testen Sie einige Anfragen wie ?-s(Sem,[mia,walks],[]),betaConvert(Sem,SemConv).
• Erklären Sie was \(\alpha\)-Konversion macht und warum sie wichtig ist. Experimentieren Sie indem Sie den \(\alpha\)-Konversionsschritt auskommentieren.

Implementing \(\alpha\)-conversion

% aus alphaConversion.pl
% ?- alphaConvert(some(X,and(man(X),all(X,woman(X)))),R).

% initializing list of substitutions and difference list of free variables
alphaConvert(F1,F2):-
   alphaConvert(F1,[],[]-_,F2).

% expression is a variable
alphaConvert(X,Sub,Free1-Free2,Y):-
   var(X), 
   (
      memberList(sub(Z,Y),Sub),
      X==Z, !,
      Free2=Free1
   ;
      Y=X,
      Free2=[X|Free1]
   ).

% expression is a some(_,_)
alphaConvert(Expression,Sub,Free1-Free2,some(Y,F2)):-
   nonvar(Expression),
   Expression = some(X,F1),
   alphaConvert(F1,[sub(X,Y)|Sub],Free1-Free2,F2).

% expression is a all(_,_)
alphaConvert(Expression,Sub,Free1-Free2,all(Y,F2)):- 
   nonvar(Expression),
   Expression = all(X,F1),
   alphaConvert(F1,[sub(X,Y)|Sub],Free1-Free2,F2).

% expression is a lam(_,_)
alphaConvert(Expression,Sub,Free1-Free2,lam(Y,F2)):- 
   nonvar(Expression),
   Expression = lam(X,F1),
   alphaConvert(F1,[sub(X,Y)|Sub],Free1-Free2,F2).

% expression is something else
alphaConvert(F1,Sub,Free1-Free2,F2):-
   nonvar(F1),
   \+ F1 = some(_,_),
   \+ F1 = all(_,_),
   \+ F1 = lam(_,_),
   compose(F1,Symbol,Args1),
   alphaConvertList(Args1,Sub,Free1-Free2,Args2),
   compose(F2,Symbol,Args2).


alphaConvertList([],_,Free-Free,[]).

alphaConvertList([X|L1],Sub,Free1-Free3,[Y|L2]):-
   alphaConvert(X,Sub,Free1-Free2,Y),
   alphaConvertList(L1,Sub,Free2-Free3,L2).

• Formulieren Sie Anfragen an das Prädikat alphaConvert/2 und stellen Sie sicher, dass Sie es verstanden haben. Verfolgen Sie die Anfrage im trace-Modus. Beispiel ?- alphaConvert(all(X,love(X,Y)),Result).

% in alphaConversion.pl

alphabeticVariants(Term1,Term2):-
   alphaConvert(Term1,[],[]-Free1,Term3),
   alphaConvert(Term2,[],[]-Free2,Term4),
   Free1==Free2,
   numbervars(Free1,0,N),
   numbervars(Term3,N,M),
   numbervars(Term4,N,M),
   Term3=Term4.

Wozu benötigt man das Prädikat alphabeticVariants/2?

Aufgabe: Bearbeiten Sie die folgenden Aufgaben aus dem Buch:

2.5 Grammar Engineering

Unser Ziel ist eine größere Grammatik, die einen größeren Sprachbereicht umfasst.

Die Grammatik sollte
- modular
- erweiterbar
- wiederverwendbar
sein

EnglishGrammar.pl

• Die DCGs werden angereichert mit Attribut-Wert-Paaren, die z.B. Kongruenzphänomene steuern.
• combine/2 verbindet die Syntax mit der Semantik (sieh semRulesLambda.pl)

% S -> NP vP
s([coord:no,sem:Sem])--> 
   np([coord:_,num:Num,gap:[],sem:NP]), 
   vp([coord:_,inf:fin,num:Num,gap:[],sem:VP]), 
   {combine(s:Sem,[np:NP,vp:VP])}.

% NP -> D NP
np([coord:no,num:sg,gap:[],sem:NP])--> 
   det([mood:decl,type:_,sem:Det]), 
   n([coord:_,sem:N]), 
   {combine(np:NP,[det:Det,n:N])}.

% NP -> PN
np([coord:no,num:sg,gap:[],sem:NP])--> 
   pn([sem:PN]), 
   {combine(np:NP,[pn:PN])}.

% N -> Noun
n([coord:no,sem:N])--> 
   noun([sem:Noun]),
   {combine(n:N,[noun:Noun])}.

% VP -> IV
vp([coord:no,inf:Inf,num:Num,gap:[],sem:VP])--> 
   iv([inf:Inf,num:Num,sem:IV]), 
   {combine(vp:VP,[iv:IV])}.

% VP -> TV NP
vp([coord:no,inf:I,num:Num,gap:G,sem:VP])-->   
   tv([inf:I,num:Num,sem:TV]), 
   np([coord:_,num:_,gap:G,sem:NP]), 
   {combine(vp:VP,[tv:TV,np:NP])}.

Koordination wird über das Attribut coord gesteuert, um Linksrekursion zu vermeiden:

% NP -> NP and NP
np([coord:yes,num:pl,gap:[],sem:NP])--> 
   np([coord:no,num:sg,gap:[],sem:NP1]), 
   coord([type:conj,sem:C]), 
   np([coord:_,num:_,gap:[],sem:NP2]), 
   {combine(np:NP,[np:NP1,coord:C,np:NP2])}.


% NP -> NP or NP
np([coord:yes,num:sg,gap:[],sem:NP])--> 
   np([coord:no,num:sg,gap:[],sem:NP1]), 
   coord([type:disj,sem:C]), 
   np([coord:_,num:sg,gap:[],sem:NP2]), 
   {combine(np:NP,[np:NP1,coord:C,np:NP2])}.

Terminalregeln:

* `lexEntry/2` greift auf `englishLexicon.pl` zu.
* `semLex/2` greift auf `semLexLambda.pl` zu.

%  Lexical Rules

iv([inf:Inf,num:Num,sem:Sem])--> 
   {lexEntry(iv,[symbol:Sym,syntax:Word,inf:Inf,num:Num])},
   Word,
   {semLex(iv,[symbol:Sym,sem:Sem])}.

tv([inf:Inf,num:Num,sem:Sem])--> 
   {lexEntry(tv,[symbol:Sym,syntax:Word,inf:Inf,num:Num])},
   Word,
   {semLex(tv,[symbol:Sym,sem:Sem])}.

det([mood:M,type:Type,sem:Det])--> 
   {lexEntry(det,[syntax:Word,mood:M,type:Type])},
   Word,
   {semLex(det,[type:Type,sem:Det])}. 

pn([sem:Sem])--> 
   {lexEntry(pn,[symbol:Sym,syntax:Word])},
   Word,  
   {semLex(pn,[symbol:Sym,sem:Sem])}.

noun([sem:Sem])--> 
   {lexEntry(noun,[symbol:Sym,syntax:Word])},
   Word,
   {semLex(noun,[symbol:Sym,sem:Sem])}.

semRulesLambda.pl

% S= NP@VP
combine(s:app(A,B),[np:A,vp:B]).

combine(np:app(A,B),[det:A,n:B]).
combine(np:A,[pn:A]).
combine(vp:A,[iv:A]).
combine(vp:app(A,B),[tv:A,np:B]).

EnglishLexicon.pl

lexEntry(det,[syntax:[every],mood:decl,type:uni]).
lexEntry(det,[syntax:[a],mood:decl,type:indef]).

lexEntry(noun,[symbol:customer,syntax:[customer]]).
lexEntry(noun,[symbol:footmassage,syntax:[foot,massage]]).

lexEntry(pn,[symbol:mia,syntax:[mia]]).

lexEntry(iv,[symbol:snort,syntax:[snorts],inf:fin,num:sg]).
lexEntry(iv,[symbol:snort,syntax:[snort],inf:fin,num:pl]).

lexEntry(coord,[syntax:[and],type:conj]).
lexEntry(coord,[syntax:[or],type:disj]).

SemLexLambda.pl

semLex(det,M):-
   M = [type:uni,
        sem:lam(U,lam(V,all(X,imp(app(U,X),app(V,X)))))].

semLex(det,M):-
   M = [type:indef,
        sem:lam(P,lam(Q,some(X,and(app(P,X),app(Q,X)))))].

semLex(pn,M):-
   M = [symbol:Sym,
        sem:lam(P,app(P,Sym))].

semLex(noun,M):-
   M = [symbol:Sym,
        sem:lam(X,Formula)],
   compose(Formula,Sym,[X]).

semLex(iv,M):-
   M = [symbol:Sym,
        sem:lam(X,Formula)],
   compose(Formula,Sym,[X]).

semLex(tv,M):-
   M = [symbol:Sym,
        sem:lam(K,lam(Y,app(K,lam(X,Formula))))], 
   compose(Formula,Sym,[Y,X]).

semLex(coord,M):-
   M = [type:conj,
        sem:lam(X,lam(Y,lam(P,and(app(X,P),app(Y,P)))))];  
   M = [type:disj,
        sem:lam(X,lam(Y,lam(P,or(app(X,P),app(Y,P)))))].

1. Konsultieren sie die oben genannten 4 Dateien und
   verfolgen Sie den trace von einfachen Anfragen, wie ?- vp(L,[cleans,a,building],[]),member(sem:Sem,L). Benutzen Sie s (skip), um uninteressante Zwischenschritte zu überspringen.

2. Konsultieren Sie die Datei lambda.pl und machen Sie sich mit den angebotenen Prädikaten vertraut. Mit ?- info. erhalten Sie jeder Zeit eine Übersicht.

3. Bearbeiten Sie die folgenden Aufgaben aus dem Buch:

Exercise 2.5.1 Find out how copula verbs are handled in the lexicon and grammar, and how the semantic representations for sentences like Mia is a boxer and Mia is not Vincent are generated.

Exercise 2.5.2 Extend the grammar so that it handles expressions of the form Vincent is male, Mia and Vincent are cool, and Marsellus or Butch is big.

Exercise 2.5.3 Extend the grammar so that it handles expressions of the form Vincent and Jules are in a restaurant and Butch is on a motorbike.

Exercise 2.5.4 Add the preposition without to the lexicon, and define a new semantic macro that takes the implicit negation of this preposition into account. For instance, a man without a weapon should receive a representation such as :\(\exists X (man(X) \wedge \neg \exists Y (weapon(Y) \wedge with(X,Y)))\).

Exercise 2.5.5 Extend the grammar (the syntax rules and the lexicon) to cover plural forms of nouns. Introduce a new feature in the lexical entries to express number information. Then add entries for determiners and classify them as combining with singular nouns only (for instance the determiner a), combining with plural nouns only (for instance both, or all), or combining with either (for example the).