Gothenburg

Computational SemanticsGSLTJohan BosUniversity of Edinburgh: 

Computational Semantics GSLT Johan Bos University of Edinburgh

This course: 

This course This course is based on material from: Working with Discourse Representation Theory: An Advanced Course in Computational Semantics (by Patrick Blackburn & Johan Bos) It is a continuation of the introductory course Representation and Inference More information: www.comsem.org

Overview: 

Overview Discourse Representation Theory Building Discourse Representations Pronoun Resolution Presupposition Projection Implementation: various versions of CURT

Part I: 

Part I Discourse Representation Theory

Overview of DRT: 

Overview of DRT DRT employs a language based on box-like structures called DRSs We will be making heavy use of DRSs in this course, for different purposes DRSs are Pictures (something like “mental models”) DRSs are Programs (the dynamic perspective)

Interpreting Discourse: 

Interpreting Discourse Discourse: a sequence of several natural language sentences How can we represent the meaning of discourse? It is clearly not just the conjunction of the first-order representations of its individual sentences We will explain why with a few simple examples

Some examples showing that this is not straightforward: 

Some examples showing that this is not straightforward Example 1: Mia is a woman. She loves Vincent. FOL representation: A: woman(mia)&love(x,vincent) B: woman(mia)&love(mia,vincent)

Some examples showing that this is not straightforward: 

Some examples showing that this is not straightforward Example 2: A woman snorts. She collapses. FOL Representation A: y(woman(y)&snort(y))&collapse(x) B: y(woman(y)&snort(y))&collapse(y) C: y(woman(y)&snort(y)&collapse(y))

Some examples showing that this is not straightforward: 

Some examples showing that this is not straightforward Example 3: If a woman snorts, she collapses. FOL Representation: A: y(woman(y)&snort(y))collapse(x) B: y(woman(y)&snort(y))collapse(y) C: y(woman(y)&snort(y)collapse(y)) D: y(woman(y)&snort(y)collapse(y))

Context Change Potential: 

Context Change Potential We need to start with the right representation Basic FOL does not seem to give us the right means Manipulation with quantifier scope and free variables Not the right intuitions about how discourse works We need a representation that naturally mirrors the context change potential of an utterance

Discourse Representation Structures: 

Discourse Representation Structures A new discourse starts a new DRS: This DRS is meant to represent the meaning of an entire discourse When a new sentence is parsed, the DRS is expanded: The x in the top of the box is a discourse referent The expressions woman(x) and snort(x) are DRS-conditions

Processing subsequent sentences: 

Processing subsequent sentences Let’s now interpret: She collapses We will do three things: Add a new discourse referent Add condition collapse(y) Add a further condition x=y Why did we do this? She is a pronoun Pronouns introduce a discourse referent which get identified with an accessible discourse referent

Further examples of DRSs: 

Further examples of DRSs Proper names: Mia snorts Quantified NPs: Every man smokes. 

Further examples of DRSs: 

Further examples of DRSs Negation Mia does not have a car Disjunction Mia smokes or snorts  

Syntax of DRSs: 

Syntax of DRSs If x1…xn are discourse referents, and C1…Cn are conditions, then is a DRS

Terms: 

Terms A term  is either a constant or a discourse referent

Syntax of DRS-conditions: 

Syntax of DRS-conditions If R is a relation symbol of arity n, and tau 1…n are terms, then R(1…n) is a DRS-condition If 1 and 2 are terms then 1=2 is a DRS-condition If B is a DRS, then B is a DRS-condition If B1 and B2 are DRSs, then B1B2 and B1B2 are DRS-conditions

Semantics of DRSs: 

Semantics of DRSs Given that a DRS is supposed to be a picture, it seems natural to say that a DRS is satisfied in a model iff it is an accurate image of the information recorded inside the model For instance: Satisfied in a model iff It is possible to associate X and y with entities of the model such that x is a woman, y is a boxer, and x and y stand in the admire relation

Semantics of complex DRS-conditions: 

Semantics of complex DRS-conditions A negated DRS will be satisfied if it is not possible to embed it in the model A disjunctive DRS-condition will be satisfied if at least one of the disjuncts can be embedded in the model An implicative DRS-condition will be satisfied if every way of embedding the antecedent DRS, gives rise to an embedding of the consequent DRS

Accessibility: 

Accessibility Resolving anaphoric pronouns is subject to accessibility constraints Accessibility is a geometric concept, defined in terms of the ways DRSs are nested into each other A DRS B1 is accessible from DRS B2 when B1 equals B2, or when B1 subordinates B2

Subordination: 

Subordination A DRS B1 subordinates B2 iff: B1 immediately subordinates B2 There is a DRS B such that B1 subordinates B and B subordinates B2 B1 immediately subordinates B2 iff: B1 contains a condition B2 B1 contains a condition B2B or BB2 B1 contains a condition B2  B B1  B2 is a condition in some DRS B

The accessibility constraint: 

The accessibility constraint Suppose a pronoun has introduced a new discourse referent y into the universe of some DRS B. Then we are only free to add the condition y=x to the conditions of B if x is declared in an accessible DRS from B

Accessibility: examples: 

Accessibility: examples  A woman walks. She collapses. Every woman walks. ?She collapses.

Donkey Sentences: 

Donkey Sentences If a farmer owns a donkey, he beats it. Every farmer who owns a donkey beats it. 

Interpreting DRSs: 

Interpreting DRSs There are two popular ways of doing this: Embedding Semantics (Kamp & Reyle) Dynamic Semantics (Groenendijk & Stokhof) We will use the translation from DRSs to First-Order Logic

From DRT to First-Order Logic: 

From DRT to First-Order Logic DRT and First-Order Logic are obviously related: Given a vocabulary, we can use it to build either DRSs or first-order languages They are interpreted in the same models Translating DRSs into FOL (and back) is straightforward and efficient We will use the function (.)fo to translate DRSs into first-order formulas

Translating DRT to FOL:DRSs: 

Translating DRT to FOL: DRSs ( )fo = x1… xn((C1)fo&…&(Cn)fo)

Translating DRT to FOL:DRS-Conditions: 

Translating DRT to FOL: DRS-Conditions (R(x1…xn))fo = R(x1…xn) (x1=x2)fo = x1=x2 (B)fo = (B)fo (B1B2)fo = (B1)fo  (B2)fo

Translating DRT to FOL:Implicative DRS-conditions: 

Translating DRT to FOL: Implicative DRS-conditions ( B)fo = x1…xn(((C1)fo&…&(Cn)fo)(B)fo)

Implementation: 

Implementation DRT in Prolog: drs(D,C) (D and C Prolog lists) imp(B1,B2) or(B1,B2) not(B) Prolog Variables as discourse referents Compiling DRSs into First-Order logic: drs2fol.pl Show examples of the translation

Part II: 

Part II Building Discourse Representations

Building DRSs: 

Building DRSs We know now what DRT is, and developed some Prolog tools to work with DRSs But how can we construct DRSs for English discourses in a systematic and automatic way? There are various ways to do this – we will explore the lambda-based method

Building DRSs with lambdas: 

Building DRSs with lambdas We will use the lambda-calculus as a tool to build DRSs for sentences We will use  to mark missing information in the DRS We call this combination -DRT It will allow us to use a number of off-the-shelf tools, such as -conversion.

The Merge: 

The Merge We will introduce a new operator ; The ; indicates a merge between two DRSs: The merge is used to combine two DRSs into one larger DRS ( ; )

Merge Reduction: 

Merge Reduction Replacing a merged DRS for a new DRS by taking the union of the two universes and conditions: The merge is precisely the operation on DRSs we need to state in the lexical semantics ( ; )=

Merge-reduction can only be applied after -conversion: 

Merge-reduction can only be applied after -conversion Consider the example: A woman walks and a woman talks This is of course not the result we want! ( ; )=

Lexical Semantics:Nouns and proper names: 

Lexical Semantics: Nouns and proper names boxer: Vincent: x. u.( ;u@x)

Lexical Semantics:Determiners: 

Lexical Semantics: Determiners a: every: p.q.(( ;p@x);q@x) ;p@x) q@x p.q. (

Lexical Semantics:Verbs: 

Lexical Semantics: Verbs dances: admires: x. u.x.u@y.

Lexical Semantics:Adjectives: 

Lexical Semantics: Adjectives big: u.x.( ;u@x)

Example derivation: 

Example derivation S NP DET N VP IV Every man dances

Example derivation: 

Example derivation S NP DET N VP IV Every man dances z. y. ;p@x) q@x p.q. (

Example derivation: 

Example derivation S NP DET N VP IV Every man dances z. @y. ;p@x) q@x p.q. ( Application NPDET N

Example derivation: 

Example derivation S NP DET N VP IV Every man dances z. ;y. @x) q@x q. ( -conversion

Example derivation: 

Example derivation S NP DET N VP IV Every man dances z. ; ) q@x q. ( -conversion

Example derivation: 

Example derivation S NP DET N VP IV Every man dances z. q@x q. ;-reduction

Example derivation: 

Example derivation S NP DET N VP IV Every man dances z. q@x q. No operation required VPIV

Example derivation: 

Example derivation S NP DET N VP IV Every man dances @z. q@x q. Application SNP VP

Example derivation: 

Example derivation S NP DET N VP IV Every man dances  z. @x -conversion

Example derivation: 

Example derivation S NP DET N VP IV Every man dances  -conversion

Implementation: 

Implementation Grammar, Lexicon Semantic rules, lexical semantics Merge reduction Alpha-conversion for DRSs Prolog: lambdaDRT.pl alphaConversionDRT.pl, mergeDRT.pl

Adding Inference: 

Adding Inference Use theorem prover and model builder for performing inferences on DRSs We will use the translation from DRT to First-Order Logic We will apply this method to consistency and informativeness checking

Consistency Checking: 

Consistency Checking Assume B is the DRS of a discourse And  the translation of B: (B)fo= Now we give  to a model builder, and  to a theorem prover If the theorem prover finds a proof, B is inconsistent If the model builder finds a model, B is consistent

Informativeness Checking: 

Informativeness Checking Assume B is the DRS of a discourse And  the translation of B: (B)fo= Now we give  to a theorem prover, and  to a model builder If the theorem prover finds a proof, B is not informative If the model builder finds a model, B is informative

Demo of CURT (curtDRT.pl): 

Demo of CURT (curtDRT.pl) Examples: Showing readings and models Inference: consistency, informativeness What we really want: Pronouns!

Part III: 

Part III Pronoun Resolution

Pronoun Resolution: 

Pronoun Resolution We will concentrate on 3rd person singular personal pronouns in English: he/him/himself she/her/herself it/itself We will focus on anaphoric pronouns In this course we won’t consider Deictic pronouns Cataphoric use: After he lost the match, Butch left town. Pleonastic use of pronouns: It’s about nine o’clock in the morning.

Recall DRS structure constrains antecedents: 

Recall DRS structure constrains antecedents DRS implication: A woman snorts. She collapses Every woman snorts. *She collapses DRS negation: Mia ordered a five dollar shake. Vincent tasted it. Mia didn’t order a five dollar shake. Vincent tasted *it.

Grammatical agreement: 

Grammatical agreement In English, pronouns come with a gender and number feature Only refer to antecedents carrying the same feature values: he (singular, male): men/boys, male animals she (singular, female): women/girls, female animals, things regarded as female, e.g. vehicles or ships it (singular, neuter): things, animals, children

Ambiguity: 

Ambiguity Butch1 threw a TV2 at the window3. It{2,3} broke. Butch1 threw a vase2 at the wall3. It2 broke. Butch1 walks into his1 modest kitchen2. He1 opens the refrigerator3. He1 takes out a milk4 and drinks it4.

Reflexive Pronouns and Binding Theory: 

Reflexive Pronouns and Binding Theory Examples: Vincent1 goes to the toilet, and Jules2 enjoys himself2. Vincent1 enters the restaurant, and Jules2 watches him1. Pronouns obey rules of binding!

Implementation: 

Implementation Decide how to represent (unresolved) pronouns in DRSs Add pronouns to lexicon and grammar Design semantic templates for pronouns Extend ontology with semantic features of pronouns Add rules for the binding constraints Prolog: curtPDRT.pl

Representing pronouns: 

Representing pronouns We won’t resolve pronouns rightaway, but instead represent them with Alfa-DRSs first Example: he walks  ( )

Extend Grammar and Lexicon: 

Extend Grammar and Lexicon New grammar rules: T  S T T  S NP  Pro Pro  she Pro  her Pro  herself

Lexical Semantics: Pronouns: 

Lexical Semantics: Pronouns He/him/himself: She/her/herself: It/itself: u.( ;u@x) u.( u.( ;u@x) ;u@x)

Extend the ontology: 

Extend the ontology New axioms: x(plant(x)neuter(x)) x(object(x)neuter(x)) x(event(x)neuter(x)) x(man(x)male(x)) x(woman(x)female(x)) Axioms for disjointness: x(neuter(x)male(x)) x(neuter(x)female(x)) x(female(x)male(x))

Rules for Binding Theory (1): 

Rules for Binding Theory (1) Feature for reflexive noun phrases: VP  TV[ref:X] NP[ref:X] NP[ref:X]  Pro[ref:X] Pro[ref:yes]himself Pro[ref:no]him Lexical semantics for TVs: TV[ref:X,sem:u.x.u@y. ]love

Rules for Binding Theory (2): 

Rules for Binding Theory (2) This will give us: Vincent1 loves him1 Vincent1 loves himself1 Exclude DRSs if: The feature ref:yes is attached to conditions with different variables The feature ref:no is attached to conditions with identical variables

Demo of CURT (curtPDRT.pl): 

Demo of CURT (curtPDRT.pl) Examples: Vincent likes Mia. She smokes. Vincent likes himself/him/her/herself No man loves himself/herself If a man walks, he smokes. What do we learn from this: Use of expensive theorem proving for rather obvious cases Sometimes rather funny judgements (negation, implication)

Add sortal check: 

Add sortal check Some readings obtained are obviously wrong (inconsistent) Use information from ontology to weed out such cases This handles some cases, but not all Cases with equality Conflicts that cover more than one DRS It is a sound but incomplete inference technique, but it is efficient it to use complementary to our theorem prover

Part IV: 

Part IV Presupposition Projection

Presupposition Projection- Overview -: 

Presupposition Projection - Overview - We will learn what the typical problems associated with presuppositions are Concentrate on a DRT based approach of Rob van der Sandt Extend our earlier implementation of pronoun resolution Access to further inference methods

Presuppositions (1): 

Presuppositions (1) Examples: The couple that won the dance contest was pleased Jody loves her husband Vincent regrets that Mia is married These examples force us to take something for granted: There is a couple that won the dance contest Jody is married Mia is married

Presuppositions (2): 

Presuppositions (2) Given contexts with contrary information, these sentences do not make sense at all: Jody is not married. ?? She loves her husband. Mia is not married. Vincent regrets that Mia is married.

Presuppositions (3): 

Presuppositions (3) Whatever we’re dealing with here, it is not ordinary entailment Both: Jody loves her husband. Jody does not love her husband. imply that Jody is married

Presuppositions (4): 

Presuppositions (4) We are dealing with presuppositions! The sentences “Jody loves her husband” and “Jody doesn’t love her husband” both imply that Jody has a husband We say that “Jody has a husband” is presupposed by these sentences This presuppositions is triggered by the possessive pronoun “her”

Presupposition Triggers: 

Presupposition Triggers Definite NPs (the man, Mia’s husband) Factive verbs (to regret, to know) Implicative verbs (to manage) Certain adjectives (other, new) Clefts (it was Butch who killed Vincent) Iterative adverbs (too, again)

Dealing with Presupposition: 

Dealing with Presupposition Fine: why not go through our lexicon, mark all presupposition triggers, and when analysing a sentence, check if the context agrees with the presuppositions of that sentence. Issues we need to deal with: The Binding Problem The Projection Problem Presuppositional Accommodation

The Binding Problem: 

The Binding Problem Example: A boxer nearly escaped from his apartment. Trigger “his apartment” presupposes that someone has an apartment. But who? A boxer? Any boxer?

The Projection Problem: 

The Projection Problem Examples: (1) Mia’s husband is out of town (2) If Mia has a husband, then Mia’s husband is out of town. (3) If Mia dates Vincent, then Mia’s husband is out of town. Example (1) presupposes that Mia is married, (2) does not, and (3) does! Complex sentences sometimes neutralise presuppositions

Accommodation: 

Accommodation Accommodation can be thought of as a way of obtaining a robust and realistic treatment of presupposition Example: Vincent informed his boss. Presupposition: Vincent has a boss. What if we don’t have a clue whether Vincent has a boss or not? Accommodation: incorporating missed information as long as this not conflicting with other information

Van der Sandt’s Theory: 

Van der Sandt’s Theory We will use a method due to Rob van der Sandt Presuppositions are essentially extremely rich anaphoric pronouns Presuppositions introduce new DRSs that need to be incorporated in the discourse context This is a good way of dealing with the binding, projection, and accommodation problems

Presuppositions in DRT: 

Presuppositions in DRT We need to carry out two tasks: Select presupposition triggers in the lexicon Indicate what they presuppose We will use the alpha-operator Example: The woman collapses. Preliminary DRS:  ( )

Binding Presuppositions : 

Binding Presuppositions Example: A woman snorts. The woman collapses. Step 1: Merge with previous discourse.  ;( ( ))

Binding Presuppositions : 

Binding Presuppositions Example: A woman snorts. The woman collapses. Step 2: Identify with possible antecedent discourse referent  ;( ( ))

Binding Presuppositions : 

Binding Presuppositions Example: A woman snorts. The woman collapses. Step 3: Move information to antecedent  ;( ( ))

Binding Presuppositions : 

Binding Presuppositions Example: A woman snorts. The woman collapses. Step 4: replace  by merge ; ; ;( ( ))

Binding Presuppositions : 

Binding Presuppositions Example: A woman snorts. The woman collapses. Step 5: perform merge reduction

Binding Presuppositions : 

Binding Presuppositions Example: A woman snorts. The woman collapses. Note: we will use unification instead of explicit equality conditions

Accommodating Presuppositions: 

Accommodating Presuppositions Example: If Mia dates Vincent, then her husband is out of town  ( )

Global Accommodation: 

Global Accommodation Example: If Mia dates Vincent, then her husband is out of town  ( )

Global Accommodation: 

Global Accommodation Example: If Mia dates Vincent, then her husband is out of town 

Sometimes global accommodation is not a good option! (projection problem): 

Sometimes global accommodation is not a good option! (projection problem) Slightly different example: If Mia is married, then her husband is out of town 

Intermediate Accommodation: 

Intermediate Accommodation Example: If Mia is married, then her husband is out of town  ( )

Intermediate Accommodation: 

Intermediate Accommodation Example: If Mia is married, then her husband is out of town 

Local Accommodation: 

Local Accommodation Example: If Mia is married, then her husband is out of town 

Van der Sandt’s Algorithm: 

Van der Sandt’s Algorithm Generate a DRS for the input sentence, with all elementary presuppositions marked by  Merge this DRS with the DRS of the discourse so far processed Traverse the DRS, and on encountering an -DRS try to: Bind the presupposed information to an accessible antecedent, or Accommodate the information to a superordinated level of DRS Remove those DRSs from the set of potential readings that violate the acceptability constraints

The acceptability constraints: 

The acceptability constraints DRSs should not contain free variables DRSs should be consistent and informative DRSs should also be locally consistent and informative

Free Variable Check (1): 

Free Variable Check (1) Consider the example: Every man likes his car DRS obtained with Local Accommodation: 

Free Variable Check (2): 

Free Variable Check (2) Consider the example: Every man likes his car DRS obtained with Intermediate Accommodation: 

Free Variable Check (3): 

Free Variable Check (3) Consider the example: Every man likes his car DRS obtained with Global Accommodation: 

The presupposition projection problem solved: 

The presupposition projection problem solved Recall our example: If Mia is married, then her husband is out of town Local constraints play a crucial role here!  Locally uninformative Locally informative

The binding problem solved: 

The binding problem solved Example: A boxer nearly escaped from his apartment. Preliminary DRS:  ;( )) ( Final DRS:

Proper Names: 

Proper Names Proper Names can be treated as presupposition triggers Only global accommodation is permitted for proper names This assures they will always end up in the global (outermost) DRS, accessible for subsequent pronouns Example: Every man knows Mia. She is Marsellus’s wife. 

Implementation: 

Implementation Work in the lexicon Implementing accommodation Free variable trapping The Local Constraints Prolog: curtPPDRT.pl

Summary: 

Summary We’ve looked at various semantic phenomena: Pronouns, presupposition, … And we’ve implemented a fragment of English incorporating these phenomena We’ve hooked up first-order tools to do genuine inference

Whereto from here?: 

Whereto from here? Work on Representation Plurals Events Tense & Aspect Work on Inference Incremental inference Use sorts to reduce search space Model size estimation