Logical Representations of Meaning

A parse tree gives the grouping of a sentence's words into phrases, but not what the sentence means. To answer Does Maharani serve vegetarian food? a system has to know what the question is asking and whether that is true of Maharani — and neither fact is in the syntax. What is needed is a meaning representation: a formal structure, built from a fixed vocabulary of symbols, that stands both for the meaning of the linguistic input and for a state of affairs in some world.¹ A representation like $\text{Serves}(\text{Maharani},\text{VegetarianFood})$ is at once a paraphrase of the English and a claim about the world that a knowledge base can confirm or deny.

This is a different theory of meaning from the distributional one. There, a word's meaning is a vector positioned by the company it keeps, and similarity is cosine distance; the representation is continuous, learned, and never true or false of anything. Here meaning is a symbolic structure with a truth value: it denotes objects and relations in a model, supports inference, and can be checked against facts. Embeddings show that dog and puppy are close; logic supports the conclusion that if every dog barks and Fido is a dog, then Fido barks. The two are complementary, and modern systems use both.

What a meaning representation must do

Before choosing a formalism, fix what the formalism is for. Jurafsky and Martin name five computational requirements, each motivated by a query a restaurant-advice system ought to answer.²

• Verifiability. The system must be able to compare the state of affairs a representation describes against a world modeled in a knowledge base. Given $\text{Serves}(\text{Maharani},\text{VegetarianFood})$, it matches the proposition against its facts and answers yes, no, or don't know.
• Unambiguous representation. A sentence like I wanna eat someplace close to ICSI has two readings (eat at a nearby place, or, Godzilla-style, devour a nearby place). The language is ambiguous, but each meaning representation must denote exactly one meaning, so the system can reason over a single unambiguous object. This is distinct from vagueness, where a representation is merely underspecified (I want Italian food commits to a cuisine but not a dish) — a vague representation is still a single representation.
• Canonical form. Distinct sentences that mean the same thing should map to the same representation. Does Maharani have vegetarian dishes?, Are vegetarian dishes served at Maharani?, and Does Maharani serve vegetarian fare? all ask one question; collapsing them onto one form means the knowledge base stores the fact once. The cost is pushed onto the parser, which must recognize that serve and have, and dishes, food, and fare, coincide here.
• Inference and variables. Can vegetarians eat at Maharani? is not literally a stored fact, yet follows from one by common-sense reasoning; the system must infer it. And find a restaurant where I can get vegetarian food names no restaurant at all, so it needs a variable: $\text{Serves}(x,\text{VegetarianFood})$, satisfied by any object that can replace $x$ and make the proposition match.
• Expressiveness. Finally the language must cover a wide range of subject matter. No single scheme covers everything, but first-order logic covers a great deal, which is why it is the workbench for the rest of this lesson.

Model-theoretic semantics

A formal representation says something about the world through a model: a formal construct standing for a particular state of affairs.³ The vocabulary of a representation splits in two. The non-logical vocabulary is the open-ended set of names for objects, properties, and relations — the predicates and constants. The logical vocabulary is the closed set of connectives, quantifiers, and operators that compose them. Every non-logical symbol must have a denotation in the model:

• Objects denote elements of the domain $\mathcal{D}$, the set of things being represented.
• Properties denote sets of domain elements — the denotation of red is the set of red things.
• Relations denote sets of tuples of domain elements — the denotation of Married is the set of married pairs.

This is the extensional view: a concept just is its extension, the things it picks out. An interpretation is the function mapping each non-logical symbol to its denotation. Take a restaurant world with patrons Matthew, Franco, Katie, Caroline (domain elements $a,b,c,d$), restaurants Frasca, Med, Rio ($e,f,g$), and cuisines Italian, Mexican, Eclectic ($h,i,j$). A property like Noisy denotes a subset of restaurants; Likes and Serves denote sets of tuples.

To evaluate Matthew likes Frasca, map Matthew to $a$, Frasca to $e$, and Likes to its set of pairs, then check whether $⟨a,e⟩$ is in that set. It is, so the sentence is true; if it were absent, false. Truth has become set membership.³ Non-mnemonic names ($a$ through $j$) are deliberate: whatever the system knows about these entities must come from the formal structure of the model, not from suggestive spellings.

Complex sentences need more than lookup. Katie likes the Rio and Matthew likes the Med is true exactly when both conjuncts are true in the model. This is a truth-conditional semantics: the meaning of a compound is fixed by the meanings of its parts and the meaning of the operator joining them. Determining the truth of the whole reduces to set operations on the parts plus a truth table for and — the principle we build on next, and the same compositionality that will let us build logical forms from parse trees later in the lesson.

First-order logic for meaning

First-order logic (FOL) is the well-understood, computationally tractable language that meets most of the desiderata and commits only to the mild ontology model theory already assumes — objects, properties, relations.⁴ Its syntax is itself a small context-free grammar.

Terms name objects and come in three kinds. Constants name specific objects ($\text{Maharani}$, $A$); like programming-language constants each refers to exactly one object, though one object may have several names. Functions name an object via another — $\text{LocationOf}(\text{Frasca})$ picks out Frasca's location without inventing a constant for it. Variables ($x$, $y$) let us assert and infer things about objects without naming any. Predicates name relations: the two-place $\text{Serves}(\text{Maharani},\text{VegetarianFood})$ asserts a relation holds between two objects, while the one-place $\text{Restaurant}(\text{Maharani})$ asserts category membership — a property of one object.

Connectives compose atomic formulas into larger ones, and because the grammar is recursive, a finite device generates infinitely many formulas. I only have five dollars and I don't have a lot of time becomes

built straight from the two clauses with $\wedge$ and $\neg$. The semantics of every connective is a truth table, evaluated against the model just as and was above.

Two facts about the table matter for translating English. $\vee$ is inclusive or, true when either or both disjuncts hold, unlike the exclusive or English often intends; and $\Rightarrow$ is the material conditional, true whenever its antecedent is false, which only loosely tracks any common-sense notion of implication or cause.⁵

Variables and quantifiers

Variables become useful only under quantifiers, the operators that say how to interpret them.⁶ The existential $\exists$ (there exists) asserts at least one object makes the formula true; the universal $\forall$ (for all) asserts every object does. An indefinite noun phrase usually signals $\exists$: a restaurant that serves Mexican food near ICSI is

This is true if some substitution for $x$ — say AyCaramba — makes all three conjuncts true. A universal reads differently. All vegetarian restaurants serve vegetarian food is naturally written with an implication:

For $\forall$ the formula must hold under every substitution. Split the objects into vegetarian restaurants and everything else. For a vegetarian restaurant like Maharani, both antecedent and consequent are true, so the implication is true. For a non-vegetarian restaurant — or even an irrelevant object like a carburetor — the antecedent is false, and the material conditional makes the whole implication vacuously true. So the universal is satisfied without making any absurd claim about carburetors.

The model-theoretic account of quantifiers reuses substitution: a formula with $\exists$ is true if some substitution of a domain term for the variable yields a formula true in the model, and a formula with $\forall$ is true if all such substitutions do.⁵

Evaluating a quantified formula against the model

Run one all the way through on the restaurant model from earlier, whose relevant facts were $\text{Serves}=\{(f,j),(g,i),(e,h)\}$ (restaurant, cuisine pairs) with Rio $=g$, Mexican $=i$. Evaluate some restaurant serves Mexican food, $\exists x\text{Restaurant}(x)\wedge \text{Serves}(x,\text{Mexican})$. The existential says: try every domain element in turn and stop at the first that makes the body true.

For $x=e$ (Frasca), $\text{Restaurant}(e)$ holds but $⟨e,i⟩\notin \text{Serves}$ — Frasca serves Italian $h$, not Mexican $i$ — so the body is false. Same for $x=f$ (Med, which serves Eclectic $j$). At $x=g$ (Rio), both $\text{Restaurant}(g)$ and $⟨g,i⟩\in \text{Serves}$ hold, so the body is true and the search halts: one witness proves the existential. The corresponding universal every restaurant serves Mexican food would demand the body hold for $e$, $f$, and $g$; it fails already at $e$, so the universal is false. The two quantifiers differ only in whether one satisfying substitution or all of them is required — the same substitution machinery, read with a different quantifier.

Inference

A representation must support inference: deriving propositions not explicitly stored. The most widely implemented rule is modus ponens:

If the antecedent of an implication is known and the implication holds, the consequent follows. Given $\text{VegetarianRestaurant}(\text{Leaf})$ and the rule above, we conclude $\text{Serves}(\text{Leaf},\text{VegetarianFood})$ — a fact never stored, now derived. Modus ponens runs two ways.⁷ Forward chaining fires every applicable rule as new facts arrive, so answers are precomputed and queries reduce to lookup, at the cost of inferring facts nobody asks for. Backward chaining runs the rule in reverse from a query: to prove a goal, find a rule whose consequent matches it, then recursively try to prove its antecedent — the strategy of the Prolog language. Both are sound but neither is complete: some valid inferences elude them, which is why a sound-and-complete but far costlier method, resolution, exists as a fallback.

The two directions reach the same conclusion by opposite motions. Suppose the knowledge base holds two rules and one fact:

plus the fact $\text{VegetarianRestaurant}(\text{Leaf})$, and ask can vegetarians eat at Leaf? — the goal $\text{OkFor}(\text{Leaf},\text{Vegetarians})$.

Forward chaining derives $\text{Serves}(\text{Leaf},\text{VegFood})$ from the fact and the first rule, then $\text{OkFor}(\text{Leaf},\text{Vegetarians})$ from that and the second rule — the query is now a stored fact and answering is a lookup. Backward chaining instead matches the goal against the consequent of rule 2, which reduces it to proving $\text{Serves}(\text{Leaf},\text{VegFood})$; that matches the consequent of rule 1, reducing it to $\text{VegetarianRestaurant}(\text{Leaf})$, which is a stored fact, so the proof closes. Forward chaining precomputes and may derive facts nobody wanted; backward chaining stays goal-directed but re-derives on each query.

Events, states, and the arity problem

Representing Leaf serves vegetarian fare as $\text{Serves}(\text{Leaf},\text{VegetarianFare})$ quietly assumes the predicate's arity equals the verb's number of arguments. That assumption breaks. Consider eat:⁸

These sentences pack anywhere from zero to four roles (eater, thing eaten, location, meal) in shifting combinations. But FOL predicates have fixed arity: they take a set number of arguments. Writing $\text{Eating}$ with two slots cannot represent I ate a turkey sandwich for lunch at my desk, and multiplying ${\text{Eating}}_2$, ${\text{Eating}}_3$, ${\text{Eating}}_4$ into separate predicates loses the fact that all are the same eating.

To address this, reify the event: introduce an existentially quantified event variable $e$ that stands for the eating itself, then hang each role on $e$ with its own predicate.⁸ I ate a turkey sandwich becomes

and the four-role version simply glues on more conjuncts:

This is the neo-Davidsonian representation, after Donald Davidson, who first reified events, and Terry Parsons, who reified the participants too.⁸ Its virtues restate the desiderata one for one: no predicate needs a fixed slot count, no more roles are postulated than the input mentions, and related sentences that share the event predicate stay logically connected for free — I ate is entailed by I ate a sandwich because dropping a conjunct is a valid inference. The role predicates ($\text{Eater}$, $\text{Eaten}$) are the thematic roles that semantic role labeling recovers from text; here they live inside the logical form as ordinary relations.

Time and aspect, briefly

Reifying the event also simplifies representing time. I arrived, I am arriving, and I will arrive share the tenseless core $\exists e\text{Arriving}(e)\wedge \text{Arriver}(e,\text{Speaker})\wedge \dots$; tense adds predicates about the event's interval.⁹ Introduce an interval $i$ and its endpoint $n$: a past event has $\text{IntervalOf}(e,i)\wedge \text{EndPoint}(i,n)\wedge \text{Precedes}(n,\text{Now})$, a future event flips the ordering to $\text{Precedes}(\text{Now},n)$, and a present event has $\text{MemberOf}(i,\text{Now})$. The mapping from tense to time is loose — we fly at 10 uses present tense for a future event — and complex tenses need a third coordinate, Reichenbach's reference point, separating event time, utterance time, and the vantage from which the event is viewed. Orthogonal to tense is aspect: whether an event is a momentary achievement (she found her gate), an extended activity (John is flying), a bounded accomplishment (Sally booked her flight), or an unchanging state (I know my gate) — Vendler's four classes.⁹

Where this continues

We have the symbolic core: a meaning representation must be checkable, unambiguous, canonical, inference-supporting, and expressive; a model gives its symbols a denotation so truth becomes set membership; first-order logic supplies terms, predicates, connectives, quantifiers, and modus-ponens inference; and the neo-Davidsonian event variable absorbs the shifting arity of real verbs so roles and tense attach as ordinary conjuncts.

What we have not done is compute a logical form from a sentence automatically. The lambda calculus that assembles a formula from a parse tree, the quantifier-scope ambiguity that one syntax tree leaves open, and the decidable description logics behind the Semantic Web continue in compositional semantics and description logics.