Underspecified Representations

Scope Ambiguities

Beispiele:

Jeder Mann liebt einen Hund. (2 Lesarten)
Jeder Hund jagt eine Katze in jedem Zimmer.

Aufgaben:

Gib für die Beispiele jeweils alle Lesarten an.
Wählen sie für jede Lesart des zweiten Satzes ein Modell mit 2 Katzen, zwei Hunden und 2 Zimmern, so dass die Aussage in dem Modell erfüllt ist.

Terminology:

has scope over / out-scopes
narrow scope vs. wide scope
weak vs. strong reading

Warum bekommen wir mit unserem bisherigen Vorgehen immer nur eine Lesart?
Bekommmen wir die schwächere oder die stärkere Lesart?

Every owner of a hash bar gives every criminal a big kahuna burger.

18 Lesarten:

Einige Lesarten sind äquivalent, andere implizieren einander. Die Lesarten zerfallen in zwei logisch unabhängige Gruppen:

Montague’s Approach

Vorgehen (Montagues Trick):

Beispiel: Every boxer loves a woman
an die Stelle der Quantorenphrase a woman tritt zunächst das indizierte Pronomen her-3 mit einer entsprechend indizierten Variable z₃ als Platzhalter.
Dieses wird im Syntaxbaum nach oben durchgereicht.
Abschließend wird es durch die Quantorenphrase ersetzt, indem die indizierte Variable Lambda-abstrahiert wird.
Hierbei dient die Quantorenphrase als Funktor und die Lambda-Abstraktion des Ausdrucks mit der indizierten Variable als Argument.

Storage Methods

Cooper Storage

Die Paare \((\beta,i)\) heißen indizierte Bindungsoperatoren (indexed binding operators)

Nur quantifizierte NP’s können den Store verändern.
Trifft man auf eine quantifizierte NP hat man die Wahl
1. der Store bleibt unverändert und die Semantik der NP wird direkt in die Repräsentation eingebaut
2. es wird ein Platzhalter gesetzt und die Semantik der NP für die spätere Verarbeitung im Store gespeichert.
Der Ausdruck \(\lambda P.P @ z_i\) entspricht der Semantik der indizierten Pronomen von Montague.
a woman kann also auf zwei Arten gespeichert werden
1. \(\langle \lambda P. \exists y (\text{woman}(y) \wedge P @ y) \rangle\)
2. \(\langle \lambda Q. Q @ z_7, (\lambda P. \exists y (\text{woman}(y) \wedge P @ y),7) \rangle\)
Trifft innerhalb des Ableitungsbaums ein Funktor \(\langle \phi, (\alpha,j),\ldots (\alpha',k)\rangle\) auf ein Argument \(\langle \psi, (\beta,j),\ldots (\beta',k)\rangle\), so ist der Speicher des Mutterknotens \(\langle \phi @ \psi, (\alpha,j),\ldots (\alpha',k)(\beta,j),\ldots (\beta',k)\rangle\).

Um den Store wieder aufzulösen, müssen die gespeicherten quantifizierten NP’s eingesetzt werden: Retrieval

Warum bekommen wir mit dieser Methode alle Lesarten?

Implementing Cooper Storage

Repräsentationen:

% representing binding operators:
bo(QUant,Ind)

% representing stores example
[walk(X),bo(lam(P,all(Y,imp(boxer(Y),app(P,X)))),X)]

Neue semantische Makros: semLexStorage.pl

% noun macro in semLexStorage.pl: 
semLex(noun,M):-
   M = [symbol:Sym,
        sem:[lam(X,Formula)]],
   compose(Formula,Sym,[X]).

% noun macro in semLexLambda.pl: 
semLex(noun,M):-
   M = [symbol:Sym,
        sem:lam(X,Formula)],
   compose(Formula,Sym,[X]).

Neue semantische Regeln: semRulesCooper.pl

% semantische Regel für VP -> V NP  in semRulesCooper.pl
combine(vp:[app(A,B)|S],[tv:[A],np:[B|S]]).

% semantische Regel für VP -> V NP  in semRulesLambda.pl
combine(vp:app(A,B),[tv:A,np:B]).

%%%%%%%%%%%%%%%

% semantische Regel für NP -> D N  in semRulesCooper.pl
% Warum gibt es zwei Regeln?
combine(np:[lam(P,app(P,X)),bo(app(A,B),X)|S],[det:[A],n:[B|S]]).
combine(np:[app(A,B)|S],[det:[A],n:[B|S]]).


% semantische Regel für NP -> D N  in semRulesLambda.pl
combine(np:app(A,B),[det:A,n:B]).

%%%%%%%%%%%%%%%

% semantische Regel für S -> NP VP  in semRulesCooper.pl
combine(s:S,[np:[A|S1],vp:[B|S2]]):-
   appendLists(S1,S2,S3),
   sRetrieval([app(A,B)|S3],Retrieved),
   betaConvert(Retrieved,S).

% semantische Regel für S -> NP VP  in semRulesLambda.pl
combine(s:app(A,B),[np:A,vp:B]).

cooperStorage.pl übernimmt die Rolle von lambda.pl und stellt die Prädikate sRetrieval/2 und filterAlphabeticVariants/2 zur Verfügung.

sRetrieval/2 übernimmt die Auflösung des Stores:

sRetrieval([S],S).

sRetrieval([Sem|Store],S):-
   selectFromList(bo(Q,X),Store,NewStore),
   sRetrieval([app(Q,lam(X,Sem))|NewStore],S).

filterAlphabeticVariants/2 löscht alphabetische Varianten aus einer Liste von Formeln.

filterAlphabeticVariants(L1,L2):-
   selectFromList(X,L1,L3),
   memberList(Y,L3),
   alphabeticVariants(X,Y), !,
   filterAlphabeticVariants(L3,L2).

filterAlphabeticVariants(L,L).

Das zentrale Prädikat ist cooperStorage/2:

cooperStorage(Sentence,Sems2):-
   setof(Sem,t([sem:Sem],Sentence,[]),Sems1),
   filterAlphabeticVariants(Sems1,Sems2).

Aufgaben:

Laden sie cooperStorage.pl und testen sie ein paar Sätze.
Wie viele Ergebnisse erhalten sie für ‘every boxer loves a person’?
Kommentieren sie in cooperStorage/0 die Verwendung von filterAlphabeticVariants/2 aus und schreiben sie statt dessen Sems1=Sems2. Wie viele Ergebnisse erhalten sie für ‘every boxer loves a person.’? Warum?
Testen sie auch Negation ‘every boxer does not love a criminal’. Sind die Ergebnisse vollständig und korrekt?
Welche Lesarten erhalten sie für ‘mia knows every owner of a hash bar.’?
Erweitern sie die Grammatik um ditransitive Verben (give/gives). Testen sie den Satz ‘every boxer gives every criminal a foot massage’. Sind die Analysen korrekt?

Keller Storage

Wir haben gesehen, dass wir manchmal zu viele Analysen mit dem Cooper Storage erhalten.

?- cooperStorage.

> mia knows every owner of a hash bar.

1 all A ((some B (hashbar(B) & of(A,B)) & owner(A)) > know(mia,A))
2 all A ((of(A,B) & owner(A)) > some C (hashbar(C) & know(mia,A)))
3 some A (hashbar(A) & all B ((of(B,A) & owner(B)) > know(mia,B)))
true.

Das Problem ist, dass wir es mit verschachtelten NP’s zu tun haben: ‘a hash bar’ ist eine sub-NP von ‘every owner of a hash bar’.

Cooper Storage ignoriert verschachtelte NP’s.

Aufgabe:

Laden sie kellerStorage.pl und testen sie ein paar Sätze.
Wie viele Ergebnisse erhalten sie für ‘every boxer loves a criminal’?
Testen sie auch Negation ‘every boxer does not love a criminal’. Sind die Ergebnisse vollständig und korrekt?
Welche Lesarten erhalten sie für ‘mia knows every owner of a hash bar.’?
Erweitern sie die Grammatik um ditransitive Verben (give/gives). Testen sie den Satz ‘every boxer gives every criminal a foot massage’. Sind die Analysen korrekt?

Probleme mit Storage Methods

Nicht ausdrucksstark genug (es gibt keine direkte Möglichkeit, bestimmte Lesarten auszufiltern). Beispiel: Der Satz “mia or a man dances” erhält zwei Lesarten, nur die erste ist erwünscht:
1. (dance(mia) v some A (man(A) & dance(A)))
2. some A (man(A) & (dance(mia) v dance(A)))
Negation kann auch zu Skopus-Ambiguität führen, wird aber nicht korrekt behandelt.
Beispiel: Der Satz “every boxer does not die” erhält nur die Lesart “all A (boxer(A) > ~ die(A))”.
Die Lesart “~ all A (boxer(A) > die(A))” fehlt.
Für die Negation würde man einen zusätzlichen Skopus-Mechanismus brauchen (das ist nicht erwünscht)
Keine einfache Möglichkeit, Constraints (Einschränkungen) auf den Lesarten zu haben

Hole Semantics

Ideen:

Wie bei den Storage-Methoden wird einem Satz an der Spitze des Ableitungsbaums eine unterspezifizierte semantische Repräsentation (USR) zugeordnet.
eine USR in Hole Semantik ist eine Menge von Constraints (constraint-basierter Ansatz)
jede logische Formel, die die Constraints in der USR erfüllt ist eine zulässige semantische Repräsentation des Satzes.
die Storage-Methoden sind nicht constraint-basiert sondern generierend: aus dem Storage (USR) lassen sich die semantischen Repräsentationen berechnen.

Prädikatenlogische Ausdrücke werden auf zwei Ebenen verwendet:

für die SRL (semantic representation language): Die Sprache in der wir die semantischen Repräsentationen der sprachlichen Ausdrücke formulieren (Prädikatenlogik 1. Stufe erweitert um den Lambdaoperator)
für die URL (underspecified representation langauge): Die Sprache in der wir die Constraints über Ausdrücke in SRL formulieren (Prädikatenlogik 1. Stufe mit Sorten)

Die semantischen Repräsentationen (sprich die prädiktenlogischen Formeln) werden dabei als Bäume aufgefasst und in der URL werden Constraints über diese Bäume ausgedrückt.

Beispiel zur Motivation:

Der Satz “every boxer loves a woman” hat zwei Lesarten, zu denen die folgenden Formeln und Bäume gehören:

Diese beiden Bäume werden repräsentiert durch folgende unterspezifizierte Repräsentation:

Um aus einer solchen underspecified representation eine specified semantic representation zu erlangen, müssen den Löchern \(h_i\) Labels zugewiesen werden \(l_j\). Diesen Vorgang nennt man Plugging. Ein Plugging ist eine injektive Funktion von der Menge der Löcher in die Menge der Labels. Hier ein exemplarisches Plugging, für das Beispiel von oben:

Underspecified Representation Languages (URLs)

Zunächst werden die Underspecified Representation Lanuages definiert, sprich die sprachen in denen die unterspezifizierten Repräsentationen geschrieben werden. Es gibt zu jeder semantischen Repräsentationssprache (SRL) eine URL, da das Vokabular der SRL in der URL reflektiert werden muss, um über die SRL sprechen zu können. Zu URLs:

URLs sind Sprachen erster Ordnung mit Sorten
“URLs are designed for talking about the way the subformulas that make up an SRL formula are embedded inside one another”
Mit URLs kann man die formula trees (Formelbäume) beschreiben

Vokabulare von URLs:

Alle logischen Operatoren sowie die (Prädikats)konstanten der SRL werden in der korrespondierenden URL abgebildet. Die Stelligkeit in der URL ist dabei jeweils um 1 höher als in der SRL, da ein Extraargument für den Label des Ausdrucks eingeführt wird.

Die Variablen einer URL werden Sorten zugeordnet. Dabei stehen \(h,h',h_i,\ldots\) für Löcher (holes), \(l,l',l_i,\ldots\) für Labels und \(v,v',v_i,\ldots\) für Meta-Variblen.
Unter Knoten (nodes) werden die Löcher (holes) und Labels zusammengefasst
Meta-Terme sind alle Meta-Variablen und URL-Konstanten.

Nur eine Teilmenge aller Formeln der URL werden zur unterspezifizierten Repräsentation von semantischen Repräsentationen benötigt, nämlich die existentiell abgelschlossenen konjunktiven Formeln, die underspecified semantic representations (USRs) genannt werden:

underspecified semantic representations (USRs)

basic USRs:

allgemeine USRs:

Zurück zu dem Beispiel:

In der obigen Abbildung wird folgende USR dargestellt:

Die USR besteht aus den existentiell abgeschlossenen Konjunkten:

\(\exists l_1\exists l_2\exists v_1 (l_1:ALL(v_1,l_2)),\ldots \exists l_7(l_7:LOVE(v_1,v_2))\); jedes dieser Konjunkte beschreibt einen der 7 Ecken des Graphen ohne die \(h_0\)-Ecke.
\(l_7\leq h_1, \ldots l_4\leq h_0\); jeder dieser Konjunkte beschreibt eine der gestrichelten Linien im Graphen; dies sind die Dominanzconstraints.

Plugging

Eine USR beschreibt alle semantischen Repräsentationen (SR), die die USR erfüllen. Um aus einer USR die SRs, die sie erfüllen zu ermitteln, muss man den Löchern in der USR Labels zuordnen und anschließend überprüfen, ob die Dominanzconstraints erfüllt sind. Die nennt man Plugging. Ein Plugging ist eine injektive Abbildung von der Menge der Löcher einer USR in die Menge der Labels.

Für das Beispiel gibt es zwei zulässige Pluggings:

Plugging 1

\(P_1(h_0) = l_1, P_1(h_1) = l_4, P_1(h_2) = l_7\)

Plugging 2

\(P_2(h_0) = l_4, P_2(h_1) = l_7, P_2(h_2) = l_1\)

Welche Lesarten werden mit diesen Pluggings repräsentiert?
Warum sind andere Pluggings nicht möglich?

Implementing Hole Semantics

Example USR in Prolog notation

** USRs are made with lambdas, for example:

\(\lambda v. \lambda h. \lambda l. (l:BOXER(v) \wedge l \leq h)\)

Semantic Macros (semLexHole.pl)

semLex(noun,M):-
   M = [symbol:Sym,
        sem:lam(X,lam(H,lam(L,and(pred1(L,Sym,X),leq(L,H)))))].

semLex(det,M):-
   M = [type:wh,
        sem:lam(N,lam(V,lam(H,lam(L,some(H1,some(L1,some(L2,some(X,and(hole(H1),
                and(label(L1),and(label(L2),and(que(L2,X,L1,H1),and(leq(L,H1),
                    and(leq(L2,H),and(app(app(app(N,X),H),L1),
                        app(app(app(V,X),H),L))))))))))))))))].
semLex(tv,M):-
   M = [symbol:Sym,
        sem:lam(Z,lam(X,app(Z,lam(Y,lam(H,lam(L,and(pred2(L,Sym,X,Y),leq(L,H))))))))].

semLex(av,M):-
   M = [pol:neg, 
        sem:lam(V,lam(X,lam(H,lam(L,some(S,some(N,and(hole(S),and(label(N),and(not(N,S), and(leq(N,H),and(leq(L,S),app(app(app(V,X),H),L))))))))))))];

   M = [pol:pos,
        sem:lam(V,lam(X,lam(H,lam(L,app(app(app(V,X),H),L)))))].

Semantic Rules (semRulesHole.pl)


combine(t:U,[s:S]):- 
   betaConvert(some(T,and(hole(T),some(L,and(label(L),app(app(S,T),L))))),U).

The Plugging ALgorithm (pluggingAlgorithm.pl)

/*========================================================================
     Declaration of dynamic predicates
========================================================================*/

:- dynamic plug/2, leq/2, hole/1, label/1.
:- dynamic some/3, all/3, que/4.
:- dynamic not/2, or/3, imp/3, and/3.
:- dynamic pred1/3, pred2/4, eq/3.


/*========================================================================
   Main Plugging Predicate (all pluggings)
========================================================================*/

plugUSR(USR,Sem):-
   numbervars(USR,0,_),          % 1 Skolemise USR
   initUSR, 
   assertUSR(USR),               % 2 Break down and assert USR
   top(Top),  
   findall(H,hole(H),Holes),
   findall(L,
           (label(L),\+ parent(_,L)),
           Labels),
   plugHoles(Holes,Labels,[]),   % 3 Calculate a plugging
   url2srl(Top,Sem).             % 4 Construct SRL formula


/*========================================================================
   Asserting immediate dominance relations to the Prolog database
========================================================================*/
    
parent(A,B):- imp(A,B,_).
parent(A,B):- imp(A,_,B).
parent(A,B):- or(A,B,_).
parent(A,B):- or(A,_,B).
parent(A,B):- and(A,B,_).
parent(A,B):- and(A,_,B).
parent(A,B):- not(A,B).
parent(A,B):- all(A,_,B).
parent(A,B):- some(A,_,B).
parent(A,B):- que(A,_,B,_).
parent(A,B):- que(A,_,_,B).
parent(A,B):- plug(A,B).


/*========================================================================
   Transitive Closure of Dominance
========================================================================*/

dom(X,Y):- dom([],X,Y).

dom(L,X,Y):- 
   parent(X,Y), 
   \+ memberList(parent(X,Y),L).

dom(L,X,Y):- 
   leq(Y,X), 
   \+ memberList(leq(Y,X),L).

dom(L,X,Z):- 
   parent(X,Y), 
   \+ memberList(parent(X,Y),L),
   dom([parent(X,Y)|L],Y,Z).

dom(L,X,Z):- 
   leq(Y,X), 
   \+ memberList(leq(Y,X),L),
   dom([leq(Y,X)|L],Y,Z).


/*========================================================================
   Plugging Holes with Labels
========================================================================*/

plugHoles([],_,Plugs):-
   admissiblePlugging(Plugs).

plugHoles([H|Holes],Labels1,Plugs):-
   admissiblePlugging(Plugs),
   selectFromList(L,Labels1,Labels2),
   plugHoles(Holes,Labels2,[plug(H,L)|Plugs]).


/*========================================================================
   Check whether plugging is propers
========================================================================*/

admissiblePlugging(Plugs):-
   retractall(plug(_,_)), 
   findall(X,(memberList(X,Plugs),assert(X)),_),
   \+ dom(A,A),
   \+ ( parent(A,B), parent(A,C), \+ B=C, dom(B,D), dom(C,D)).
   
 
/*========================================================================
    Top of a USR
========================================================================*/

top(X):- dom(X,_), \+ dom(_,X), !.


/*========================================================================
   From USRs to FOLs
========================================================================*/

url2srl(H,F):-
   hole(H),
   plug(H,L),
   url2srl(L,F).

url2srl(L,all(X,F)):-
   all(L,X,H),
   url2srl(H,F).

url2srl(L,some(X,F)):-
   some(L,X,H),
   url2srl(H,F).

url2srl(L,que(X,F1,F2)):-
   que(L,X,H1,H2),
   url2srl(H1,F1),
   url2srl(H2,F2).

url2srl(L,imp(F1,F2)):-
   imp(L,H1,H2),
   url2srl(H1,F1),
   url2srl(H2,F2).

url2srl(L,and(F1,F2)):-
   and(L,H1,H2),
   url2srl(H1,F1),
   url2srl(H2,F2).

url2srl(L,or(F1,F2)):-
   or(L,H1,H2),
   url2srl(H1,F1),
   url2srl(H2,F2).

url2srl(L,not(F)):-
   not(L,H),
   url2srl(H,F).

url2srl(L,eq(X,Y)):-
   eq(L,X,Y).

url2srl(L,F):-
   pred1(L,Symbol,Arg),
   compose(F,Symbol,[Arg]).

url2srl(L,F):-
   pred2(L,Symbol,Arg1,Arg2),
   compose(F,Symbol,[Arg1,Arg2]).


/*========================================================================
   Assert USR to Prolog database
========================================================================*/

assertUSR(some(_,F)):-   
    assertUSR(F).

assertUSR(and(F1,F2)):-
    assertUSR(F1),
    assertUSR(F2).

assertUSR(F):- 
    \+ F=and(_,_),
    \+ F=some(_,_),
    assert(F).

Übung

Schauen Sie sich den Output von holeSemanticsTestSuite. Werden alle Lesarten produziert? Werden nur die richtigen Lesarten produziert?
Implementieren Sie die ditransitiven Verben in Hole Semantics

Warnung:

Die Umsetzung der Negation ist nicht gut, es kommt zu falschen Ergebnissen.