Video 1: What we want from a meaning representation
ANLP Week 9/Unit 2 Meaning representations
Sharon Goldwater
(based on slides by Frank Keller, Bonnie Webber, Mirella Lapata, and others)
Sharon Goldwater ANLP Week 9/Unit 2
Recap: distributional semantics
• A useful way to represent meanings of individual words • Can deal with notions of similarity
• But less clear how to deal with compositionality
• Also, we still haven’t discussed how to do inference
Sharon Goldwater
ANLP Week 9/Unit 2 1
Example Question (6)
Sharon Goldwater ANLP Week 9/Unit 2 2
• Question
Did Poland reduce its carbon emissions since 1989?
• Text available to the machine
Due to the collapse of the industrial sector after the end of communism in 1989, all countries in Central Europe saw a fall in carbon emmissions.
Poland is a country in Central Europe.
• What is hard?
– we need to do inference
– a problem for sentential, not lexical, semantics
Sharon Goldwater ANLP Week 9/Unit 2 3
Meaning representations
Basic assumption
The symbols in our meaning representations correspond to objects, properties, and relations in the world.
• The world may be the real world, or (usually) a formalized and well-specified world: a model or knowledge base of known facts.
– Ex 1: a tiny world model containing 3 entities, and an exhaustive table of ‘who loves whom’ relations.
– Ex 2: GeoQuery database [1], containing ∼800 facts about US geography.
– Ex 3: Freebase [2], “A community-curated database of well- known people, places, and things” with over 2.6 billion facts.
[1] http://www.cs.utexas.edu/users/ml/nldata/geoquery.html, [2] https://www.freebase.com/ Sharon Goldwater ANLP Week 9/Unit 2 5
What do we want from an MRL?
Compositional: The meaning of a complex expression is a function of the meaning of its parts and of the rules by which they are combined.
Verifiable: Can use the MR of a sentence to determine whether the sentence is true with respect to some given model of the world.
• In Ex 1 above, can establish the truth value of everybody loves Mary by checking it against the model.
• Vector space is one kind of meaning representation. But not obvious how to deal with compositionality or inference.
• Instead, we can do this with representations that are symbolic and structured.
• Next lecture, semantic analysis: how to get from sentences to their meaning representations (using syntax to help).
• But first we need to define the semantics we’re aiming at, i.e., a meaning representation language (MRL).
Sharon Goldwater ANLP Week 9/Unit 2 4
What do we want from an MRL?
Compositional: The meaning of a complex expression is a function of the meaning of its parts and of the rules by which they are combined.
Sharon Goldwater
ANLP Week 9/Unit 2
6
Sharon Goldwater ANLP Week 9/Unit 2 7
What do we want from an MRL?
What do we want from an MRL?
Unambiguous: an MR should have exactly one interpretation. So, an ambiguous sentence should have a different MR for each sense.
• Ex: each interpretation of I made her duck or time flies like an arrow should have a distinct MR.
• The job of producing all possible MRs for a given sentence will go to the semantic analyzer.
• We also defer the question of choosing which interpretation is correct.
Sharon Goldwater ANLP Week 9/Unit 2 8
What do we want from an MRL?
Inference: we should be able to verify sentences not only directly, but also by drawing conclusions based on the input MR and facts in the knowledge base.
Canonical form: sentences with the same (literal) meaning should have the same MR.
• Ex: I filled the room with balloons should have the same canonical form as I put enough balloons in the room to fill it from floor to ceiling.
• Ex: Similarly, Tanjore serves vegetarian food and Vegetarian dishes are served by Tanjore.
• Simplifies inference and reduces storage needs; but also makes semantic analysis harder.
Sharon Goldwater ANLP Week 9/Unit 2 9
What do we want from an MRL?
Expressivity: the MRL should allow us to handle a wide range of meanings and express appropriate relationships between the words in a sentence.
• Ideally, we could express the meaning of any natural language sentence.
• In practice, we may use simpler MRLs that cover a lot of what we want.
• Ex: from the MR for a query
Did Poland reduce its carbon emissions?
• and the MRs for facts
Carbon emmissions have fallen for all countries in Central
Europe.
Poland is a country in Central Europe.
• we should be able to infer the answer: YES. Sharon Goldwater ANLP Week 9/Unit 2
10
• For example… Sharon Goldwater
ANLP Week 9/Unit 2 11
Video 2: Constants, predicates, functions, and connectives in FOL
FOL: First-order Logic (Predicate Logic)
• A pretty good fit to what we’d like. • Example FOL expressions:
– tall(Kim) ∨ tall(Pierre)
– likes(Sam, owner-of(Tanjore))
– ∃x.cat(x) ∧ owns(Marie,x)
– ∃x. movie(x) ∧ ∀y. person(y) ⇒ loves(y, x)
Sharon Goldwater ANLP Week 9/Unit 2 13
FOL: First-order Logic (Predicate Logic)
• Expressions are constructed from terms:
– constant and variable symbols that represent entities
– function symbols that allow us to indirectly specify entities
– predicate symbols that represent properties of entities and
relations between entities
• Terms can be combined into predicate-argument structures, which in turn are combined into complex expressions using:
– Logical connectives: ∨, ∧, ¬, ⇒
– Quantifiers: ∀ (universal quantifier, i.e., “for all”), ∃ (existential
quantifier, i.e. “exists”)
Sharon Goldwater ANLP Week 9/Unit 2 15
Sharon Goldwater
ANLP Week 9/Unit 2
12
FOL: First-order Logic (Predicate Logic)
• Expressions are constructed from terms:
– constant and variable symbols that represent entities
– function symbols that allow us to indirectly specify entities
– predicate symbols that represent properties of entities and
relations between entities
Sharon Goldwater
ANLP Week 9/Unit 2
14
Constants in FOL
Predicates in FOL
• Each constant symbol denotes exactly one entity: Scotland, EU, John, 2014
• Not all entities have a constant that denotes them: Lady Gaga’s right knee, this pen
• Several constant symbols may denote the same entity: The Evening Star ≡ Venus
Scotland ≡ Alba
Sharon Goldwater ANLP Week 9/Unit 2
The semantics of predicates
• •
•
Predicates with one argument represent properties of entities:
nation(Scotland), organization(EU), tall(John)
Predicates with multiple arguments represent relations between entities:
member-of(UK, EU), likes(John, Marie), introduced(John, Marie, Sue)
We write “/N” to indicate that a predicate has arity N (takes N arguments)
member-of/2, nation/1, tall/1, introduced/3
• A predicate of arity N denotes the set of N-tuples that satisfy it.
– likes/2 is the set of (x, y) pairs for which likes(x, y) is true. – In the following example world, a set of four pairs:
likes(John, Marie) likes(John, Kim) likes(Kim, UK)
likes(Marie, Kim) eats(Marie, pizza) lives-in(Marie, UK)
tall(Kim) nation(UK) nation(USA)
• If all arguments are instantiated, then the predicate-argument structure has a truth value (determined by comparing it to the set of facts in the world).
– So, likes(John, Kim) is true, whereas likes(John, UK) is false. Sharon Goldwater ANLP Week 9/Unit 2 18
ANLP Week 9/Unit 2 19
16
Sharon Goldwater ANLP Week 9/Unit 2 17
Functions in FOL
• Like constants, are used to specify (denote) unique entities.
• Unlike constants, they refer to entities indirectly, so we don’t need
to store as many constants.
president(EU), father(John), right-knee(Gaga)
• Syntactically, they look like unary predicates, but denote entities, not sets.
Sharon Goldwater
Figure 17.4
Logical connectives
Figure 17.4 Logical connectives
• Given FOL expressions P and Q, the meaning of an expression containing P and Q is determined from the meaning of each part and the logical connective.
• Given FOL expressions P and Q, the meaning of an expression containing P and Q is determined from the meaning of each part and the logical connective.
• True or false: Sharon is an MSc student ⇒ Sharon is Chinese
• True or false: Sharon is an MSc student ⇒ Sharon is Chinese
• True, because the antecedent is false.
Sharon Goldwater ANLP Week 9/Unit 2
Speech and Language Processing, Second Edition Daniel Jurafsky and James H. Martin
20
Copyright ©2009 by Pearson Education, Inc. Upper Saddle River, New Jersey 07458 All rights reserved.
Sharon Goldwater ANLP Week 9/Unit 2
21
Copyright ©2009 by Pearson Education, Inc. Upper Saddle River, New Jersey 07458 All rights reserved.
Sharon Goldwater
ANLP Week 9/Unit 2
22
∀x.likes(x, Kim) has an interpretation as either true or false. Sharon Goldwater ANLP Week 9/Unit 2 23
Variables and quantifiers in FOL
Speech and Language Processing, Second Edition Daniel Jurafsky and James H. Martin
Variables in FOL
• •
•
Variable symbols (e.g., x, y, z) range over entities.
An expression consisting only of a predicate with a variable among
its arguments is interpreted as a set:
likes(x, Kim) is the set of entities that like Kim.
A predicate with a variable among its arguments only has a truth value if it is bound by a quantifier.
Universal Quantifier (∀)
• Can be used to express general truths:
Cats are mammals has MR ∀x.cat(x) ⇒ mammal(x)
• This MR is true iff the conjunction of all similar expressions is true, where each of these substitutes a differerent constant for the variable.
Existential Quantifier (∃)
• Used to express that a property/relation is true of some entity,
without specifying which one:
Marie owns a cat has MR ∃x.cat(x) ∧ owns(Marie,x)
• This MR is true iff the disjunction of all similar expressions is true, where each of these substitutes a differerent constant for the variable.
(cat(Sam) ∧ owns(Marie, Sam)) ∨ (cat(Zoot) ∧ owns(Marie, Zoot)) ∨ (cat(Whiskers) ∧ owns(Marie, Whiskers)) ∨ (cat(UK) ∧ owns(Marie, UK)) ∨
…
Sharon Goldwater ANLP Week 9/Unit 2 25
Quantifier scoping
• Consider the following sentence: Everyone loves some movie
– No ambiguity in POS tags, syntactic structure, or word senses. – But this sentence is still ambiguous!
(cat(Sam) ⇒ mammal(Sam)) ∧ (cat(Zoot) ⇒ mammal(Zoot)) ∧ (cat(Whiskers) ⇒ mammal(Whiskers)) ∧ (cat(UK) ⇒ mammal(UK)) ∧
…
Sharon Goldwater ANLP Week 9/Unit 2
Existential Quantifier (∃)
24
• Why use ∧ not ⇒? Notice the difference between these two MRs: ∃x.cat(x) ∧ own(Marie, x) vs ∃x.cat(x) ⇒ own(Marie, x)
In English:
There is something that is a cat and Marie owns it vs
There is something that if it’s a cat, Marie owns it
• P ⇒ Q is true if the antecedent (left of the ⇒) is false.
• So the righthand MR is true if there is anything that’s not a cat!
– If cat(UK) is false, then cat(UK) ⇒ owns(Marie, UK) is true, and so is ∃x.cat(x) ⇒ own(Marie, x).
Sharon Goldwater ANLP Week 9/Unit 2 26
Sharon Goldwater
ANLP Week 9/Unit 2 27
Quantifier scoping
Quantifier scope ambiguity
• Consider the following sentence: Everyone loves some movie
– No ambiguity in POS tags, syntactic structure, or word senses. – But this sentence is still ambiguous!
• Two possible meanings:
(a) There is a single movie that everyone loves
(b) Everyone loves at least one movie, but the movies might be different
• This kind of ambiguity is called quantifier scope ambiguity Sharon Goldwater ANLP Week 9/Unit 2 28
Are we done?
• MRs in FOL are verifiable, unambiguous, canonical.
• Predicate-argument structure is a good match for natural
language
– Predicate-like elements: verbs, prepositions, adjectives
– Argument-like elements: nouns, NPs
• Determiners (a, some, every) and coordination (if, and, or) can
often be expressed with logical connectives and quantifiers.
• But what about compositionality?
• The two meanings have different MRs:
(a) ∃x. movie(x) ∧ (∀y. person(y) ⇒ loves(y, x))
(b) ∀y. person(y) ⇒ (∃x. movie(x) ∧ loves(y, x))
• In (a), the ‘∃’ has scope over the ‘∀’; in (b) it’s vice versa.
• Other examples of quantifier scope ambiguity: A boy gave flowers to each teacher
Every cat chased a dog
Sharon Goldwater ANLP Week 9/Unit 2 29
Video 4: Lambda expressions
Sharon Goldwater ANLP Week 9/Unit 2 30
Sharon Goldwater
ANLP Week 9/Unit 2 31
Compositionality
• Suppose we have the following words with the following meanings:
Lambda (λ) Expressions
• Extension to FOL, allows us to work with ‘partially constructed’
formulae.
• A λ-expression consists of:
– the Greek letter λ, followed by a variable (formal parameter); – a FOL expression that may involve that variable.
λx.sleep(x) ‘The function that takes an entity x to the FOL expression sleep(x)’
• This lambda is the same one used in Python!
Sharon Goldwater ANLP Week 9/Unit 2 33
Nested λ-expressions • Use one λ-expression as the body of another.
• Allows predicates with several arguments to accept them one by one.
word
Marie pizza loves
meaning
Marie pizza love(x,y)
• How do we get from there to the meaning of the sentence Marie loves pizza?
Sharon Goldwater
ANLP Week 9/Unit 2
32
λ-Reduction • A λ-expression can be applied to a term
λx.sleep(x) (Marie)
functor argument
λy. λx. love(x,y)
λz. λy. λx. give(x,y,z)
‘The function that takes y to (the function that takes x to the FOL expression love(x,y))’
‘The function that takes z to (the function that takes y to (the function that takes x to the FOL expression give(x,y,z)))’
• This expression can be simplified using λ-reduction: replace the formal parameter with the term and remove the λ. Result:
sleep(Marie)
Sharon Goldwater
ANLP Week 9/Unit 2
34
Sharon Goldwater ANLP Week 9/Unit 2 35
Nested λ-reduction
Video 5: Reifiying events
• Starting from binary predicate λy. λx. love(x,y) • Apply to first argument:
λy. λx. love(x,y) (pizza) becomes λx. love(x, pizza) • Apply to second argument:
λx. love(x, pizza) (Marie) becomes love(Marie, pizza)
Sharon Goldwater ANLP Week 9/Unit 2 36
This unit so far
• Discussed properties we want from a meaning representation:
– compositional – verifiable
– canonical form – unambiguous – expressive
– allowing inference
•Argued that first-order logic has all of these except
compositionality, and is a good fit for natural language.
• Adding λ-expressions to FOL allows us to compute meaning representations compositionally.
Sharon Goldwater
ANLP Week 9/Unit 2 37
Coming in the next unit
• We’ll see how to use λ-expressions in computing meanings for sentences: syntax-driven semantic analysis.
• But first: a final improvement to event representations
Sharon Goldwater ANLP Week 9/Unit 2 38
Sharon Goldwater
ANLP Week 9/Unit 2 39
Verbal (event) MRs: the story so far
Syntax:
NP give NP1 NP2 Semantics:
λz. λy. λx. Giving1(x,y,z) Applied to arguments:
λz. λy. λx. Giving1(x,y,z) (book)(Mary)(John)
As in the sentence:
John gave Mary a book.
Giving1(John, Mary, book)
Sharon Goldwater ANLP Week 9/Unit 2 40
Problem with event representations
• Predicates in First-order Logic have fixed arity
•Requires separate Giving predicate for each syntactic
subcategorisation frame (number/type/position of arguments). • Separate predicates have no logical relation, but they ought to.
– Ex. if Giving3(a, b, c, d, e) is true, then so are Giving2(a, b, c, d) and Giving1(a, b, c).
• See J&M for various unsuccessful ways to solve this problem; we’ll go straight to a more useful way.
But what about these?
John gave Mary a book for Susan.
Giving2(John, Mary, Book, Susan)
John gave Mary a book for Susan on Wednesday.
Giving3(John, Mary, Book, Susan, Wednesday)
John gave Mary a book for Susan on Wednesday in class.
Giving4(John, Mary, Book, Susan, Wednesday, InClass) John gave Mary a book with trepidation.
Giving5(John, Mary, Book, Susan, Trepidation)
Sharon Goldwater ANLP Week 9/Unit 2 41
Reification of events
• We can solve these problems by reifying events.
– Reify: to “make real” or concrete, i.e., give events the same status as entities.
– In practice, introduce variables for events, which we can quantify over.
Sharon Goldwater ANLP Week 9/Unit 2 42
Sharon Goldwater
ANLP Week 9/Unit 2 43
entails
∃ e, z. Giving(e) ∧ Giver(e, John) ∧ Givee(e, Mary)
∧ Given(e,z) ∧ Book(z) ∧ Time(e, Tuesday)
∃ e, z. Giving(e) ∧ Giver(e, John) ∧ Givee(e, Mary)
∧ Given(e,z) ∧ Book(z) ∧ Time(e, Tuesday)
• First-order logic can be used as a meaning representation language for natural language.
• λ-expressions can be used to compute meaning representations compositionally.
• Event reification allows entailment relationships.
• Next time, we will see how to use these tools in a syntax-driven
approach to semantic analysis.
Sharon Goldwater ANLP Week 9/Unit 2 47
Reification of events
Entailment relations
• We can solve these problems by reifying events.
– Reify: to “make real” or concrete, i.e., give events the same status as entities.
– In practice, introduce variables for events, which we can quantify over.
• MR for John gave Mary a book is now
∃ e, z. Giving(e) ∧ Giver(e, John) ∧ Givee(e, Mary)
∧ Given(e,z) ∧ Book(z)
• The giving event is now a single predicate of arity 1: Giving(e);
remaining conjuncts represent the participants (semantic roles). Sharon Goldwater ANLP Week 9/Unit 2 44
Entailment relations
• This representation automatically gives us logical entailment relations between events. (“A entails B” means “A ⇒ B”.)
• John gave Mary a book on Tuesday entails John gave Mary a book. Similarly,
• This representation automatically gives us logical entailment relations between events. (“A entails B” means “A ⇒ B”.)
• John gave Mary a book on Tuesday entails John gave Mary a book.
• Can add as many semantic roles as needed for the event.
Sharon Goldwater ANLP Week 9/Unit 2 46
Sharon Goldwater
ANLP Week 9/Unit 2 45
Summary