17.7.2 Embodiment as the Basis for Meaning

Coming soon...

17.8 SUMMARY

This chapter has introduced the representational approach to meaning. The following are some of the highlights of this chapter:

• A major approach to meaning in computational linguistics involves the creation of formal meaning representations that capture the meaning-related content of linguistic inputs. These representations are intended to bridge the gap from language to commonsense knowledge of the world.

• The frameworks that specify the syntax and semantics of these representations are called meaning representation languages. A wide variety of such languages are used in natural language processing and artificial intelligence.

• Such representations need to be able to support the practical computational requirements of semantic processing. Among these are the need to determine the truth of propositions, to support unambiguous representations, to represent variables, to support inference, and to be sufficiently expensive.

• Human languages have a wide variety of features that are used to convey meaning. Among the most important of these is the ability to convey a predicate-argument structure.

• First Order Predicate Calculus is a well-understood computationally tractable meaning representation language that offers much of what is needed in a meaning representation language.

• Important classes of meaning including categories, events, and time can be captured in FOPC. Propositions corresponding to such concepts as beliefs and desires require extensions to FOPC including modal operators.

• Semantic networks and frames can be captured within the FOPC framework.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

NB. Not yet updated.

The earliest computational use of declarative meaning representations in natural language processing was in the context of question-answering systems (Green et al., 1961; Raphael, 1968; Lindsey, 1963). These systems employed ad-hoc representations for the facts needed to answer questions. Questions were then translated into a form that could be matched against facts in the knowledge base. Simmons (1965) provides an overview of these early efforts.

Woods (1967) investigated the use of FOPC-like representations in question answering as a replacement for the ad-hoc representations in use at the time. Woods (1973) further developed and extended these ideas in the landmark Lunar system. Interestingly, the representations used in Lunar had both a truth-conditional and a procedural semantics. Winograd (1972) employed a similar representation based on the Micro-Planner language in his SHRDLU system.

During this same period, researchers interested in the cognitive modeling of language and memory had been working with various forms of associative network representations. Masterman (1957) was probably the first to make computational use of a semantic network-like knowledge representation, although semantic networks are generally credited to Quillian (1968). A considerable amount of work in the semantic network framework was carried out during this era (Norman and Rumelhart, 1975; Schank, 1972; Wilks, 1975b, 1975a; Kintsch, 1974). It was during this period that a number of researchers began to incorporate Fillmore's notion of case roles (Fillmore, 1968) into their representations. Simmons (1973) was the earliest adopter of case roles as part of representations for natural language processing.

Detailed analyses by Woods (1975) and Brachman (1979) aimed at figuring out what semantic networks actually mean led to the development of a number of more sophisticated network-like languages including KRL (Bobrow and Winograd, 1977) and KL-ONE (Brachman and Schmolze, 1985). As these frameworks became more sophisticated and well-defined it became clear that they were restricted variants of FOPC coupled with specialized inference procedures. A useful collection of papers covering much of this work can be found in Brachman and Levesque (1985). Russell and Norvig (1995) describe a modern perspective on these representational efforts.

Linguistic efforts to assign semantic structures to natural language sentences in the generative era began with the work of Katz and Fodor (1963). The limitations of their simple feature-based representations and the natural fit of logic

to many of linguistic problems of the day quickly led to the adoption of a variety of predicate-argument structures as preferred semantic representations (Lakoff, 1972; McCawley, 1968). The subsequent introduction by Montague (1973) of truth-conditional model-theoretic framework into linguistic theory led to a much tighter integration between theories of formal syntax and a wide range of formal semantic frameworks. Good introductions to Montague semantics and its role in linguistic theory can be found in Dowty et al. (1981), Partee (1976).

The representation of events as reified objects is due to Davidson (1967). The approach presented here, which explicitly reifies event participants, is due to Parsons (1990). The use of modal operators and in the representation of knowledge and belief is due to Hintikka (1969). Moore (1977) was the first to make computational use of this approach. Fauconnier (1985) deals with a wide range of issues relating to beliefs and belief spaces from a cognitive science perspective. Most current computational approaches to temporal reasoning are based on Allen's notion of temporal intervals (Allen, 1984). ter Meulen (1995) provides a modern treatment of tense and aspect. Davis (1990) describes the use of FOPC to represent knowledge across a wide range of common sense domains including quantities, space, time, and beliefs.

A recent comprehensive treatment of logic and language can be found in van Benthem and ter Meulen (1997). The classic semantics text is Lyons (1977). McCawley (1993) is an indispensable textbook covering a wide range of topics concerning logic and language. Chierchia and McConnell-Ginet (1991) also provides broad coverage of semantic issues from a linguistic perspective. Heim and Kratzer (1998) is a more recent text written from the perspective of current generative theory.

EXERCISES

17.1 Choose a recipe from your favorite cookbook and try to make explicit all the common-sense knowledge that would be needed to follow it.

17.2 Proponents of information retrieval occasionally claim that natural language texts in their raw form are a perfectly suitable source of knowledge for question answering. Sketch an argument against this claim.

17.3 Peruse your daily newspaper for three examples of ambiguous sentences. Describe the various sources of the ambiguities.

17.4 Consider a domain where the word coffee can refer to the following concepts in a knowledge-based: a caffeinated or decaffeinated beverage, ground coffee used

to make either kind of beverage, and the beans themselves. Give arguments as to which of the following uses of coffee are ambiguous and which are vague.

a. I've had my coffee for today.

b. Buy some coffee on your way home.

c. Please grind some more coffee.

17.5 Encode in FOPC as much of the knowledge as you can that you came up with for Exercise 17.1

17.6 The following rule, which we gave as a translation for Example 17.24, is not a reasonable definition of what it means to be a vegetarian restaurant.

$ \forall xVegetarianRestaurant(x) \Rightarrow Serves(x, VegetarianFood) $

Give a FOPC rule that better defines vegetarian restaurants in terms of what they serve.

17.7 Give a FOPC translations for the following sentences:

a. Vegetarians do not eat meat.

b. Not all vegetarians eat eggs.

17.8 Give a set of facts and inferences necessary to prove the following assertions:

a. McDonalds is not a vegetarian restaurant.

b. Some vegetarians can eat at McDonalds.

Don't just place these facts in your knowledge base. Show that they can be inferred from some more general facts about vegetarians and McDonalds.

17.9 Give FOPC translations for the following sentences that capture the temporal relationships between the events.

a. When Mary's flight departed, I ate lunch.

b. When Mary's flight departed, I had eaten lunch.

17.10 Give a reasonable FOPC translation of the following example. If you're interested in baseball, the Rockies are playing tonight.

17.11 On Page 19 we gave the following FOPC translation for Example 17.21.

Have(Speaker, FiveDollars) ∧ ¬Have(Speaker, LotOfTime)

This literal representation would not be particularly useful to a restaurant-oriented question answering system. Give a deeper FOPC meaning representation for this example that is closer to what it really means.

17.12 On Page 19, we gave the following representation as a translation for the sentence Ay Caramba is near ICSI.

$$ Near(LocationOf(AyCaramba),LocationOf(ICSI)) $$

In our truth-conditional semantics, this formula is either true or false given the contents of some knowledge-base. Critique this truth-conditional approach with respect to the meaning of words like near.

Allen, J. (1984). Towards a general theory of action and time. Artificial Intelligence, 23(2), 123–154.

Bailey, D., Feldman, J., Narayanan, S., and Lakoff, G. (1997). Modeling embodied lexical development. In COGSCI-97, Stanford, CA, pp. 19–24. Lawrence Erlbaum.

Bobrow, D. G. and Winograd, T. (1977). An overview of KRL, a knowledge representation language. Cognitive Science, 1(1), 3–46.

Brachman, R. J. (1979). On the epistemological status of semantic networks. In Findler, N. V. (Ed.), Associative Networks: Representation and Use of Knowledge by Computers, pp. 3–50. Academic Press, New York.

Brachman, R. J. and Levesque, H. J. (Eds.). (1985). Readings in Knowledge Representation. Morgan Kaufmann, San Mateo, CA.

Brachman, R. J. and Schmolze, J. G. (1985). An overview of the KL-ONE knowledge representation system. Cognitive Science, 9(2), 171–216.

Chang, N., Gildea, D., and Narayanan, S. (1998). A dynamic model of aspectual composition. In COGSCI-98, Madison, WI, pp. 226–231. Lawrence Erlbaum.

Chierchia, G. and McConnell-Ginet, S. (1991). Meaning and Grammar. MIT Press, Cambridge, MA.

Davidson, D. (1967). The logical form of action sentences. In Rescher, N. (Ed.), The Logic of Decision and Action. University of Pittsburgh Press.

Davis, E. (1990). Representations of Commonsense Knowledge. Morgan Kaufmann, San Mateo, CA.

Dowty, D. R. (1979). Word Meaning and Montague Grammar. D. Reidel, Dordrecht.

Dowty, D. R., Wall, R. E., and Peters, S. (1981). Introduction to Montague Semantics. D. Reidel, Dordrecht.

Fauconnier, G. (1985). Mental Spaces: Aspects of Meaning Construction in Natural Language. MIT Press, Cambridge, MA.

Fillmore, C. J. (1968). The case for case. In Bach, E. W. and Harms, R. T. (Eds.), Universals in Linguistic Theory, pp. 1–88. Holt, Rinehart & Winston, New York.

Green, B. F., Wolf, A. K., Chomsky, C., and Laughery, K. (1961). Baseball: An automatic question answerer. In Proceedings of the Western Joint Computer Conference 19, pp. 219–224. Reprinted in Grosz et al. (1986).

Heim, I. and Kratzer, A. (1998). Semantics in a Generative Grammar. Blackwell Publishers, Malden, MA.

Hintikka, J. (1969). Semantics for propositional attitudes. In Davis, J. W., Hockney, D. J., and Wilson, W. K. (Eds.), Philosophical Logic, pp. 21–45. D. Reidel, Dordrecht, Holland.

Humphries, J. J., Woodland, P. C., and Pearce, D. (1996) In Using Accent-specific Pronunciation Modelling for Robust Speech Recognition.

Jackendoff, R. (1983). Semantics and Cognition. MIT Press, Cambridge, MA.

Katz, J. J. and Fodor, J. A. (1963). The structure of a semantic theory. Language, 39, 170–210.

Kintsch, W. (1974). The Representation of Meaning in Memory. Wiley, New York.

Lakoff, G. (1972). Linguistics and natural logic. In Davidson, D. and Harman, G. (Eds.), Semantics for Natural Language, pp. 545–665. D. Reidel, Dordrecht.

Lakoff, G. and Johnson, M. (1980). Metaphors We Live By. University of Chicago Press, Chicago, IL.

Lenat, D. B. and Guha, R. V. (1991). Building Large Knowledge-Based Systems: Representation and Inference in CYC. Addison-Wesley, Reading, MA.

Lindsey, R. (1963). Inferential memory as the basis of machines which understand natural language. In Feigenbaum, E. and Feldman, J. (Eds.), Computers and Thought, pp. 217–233. McGraw Hill.

Lyons, J. (1977). Semantics. Cambridge University Press, New York.

Masterman, M. (1957). The thesaurus in syntax and semantics. Mechanical Translation, 4(1), 1–2.

McCawley, J. D. (1968). The role of semantics in a grammar. In Bach, E. W. and Harms, R. T. (Eds.), Universals in Linguistic Theory, pp. 124–169. Holt, Rinehart & Winston, New York, NY.

McCawley, J. D. (1993). Everything that Linguists have Always Wanted to Know about Logic (2nd edition). University of Chicago Press, Chicago, IL.

McDermott, D. (1976). Artificial intelligence meets natural stupidity. SIGART Newsletter, 57.

Montague, R. (1973). The proper treatment of quantification in ordinary English. In Thomason, R. (Ed.), Formal Philosophy: Selected Papers of Richard Montague, pp. 247–270. Yale University Press, New Haven, CT.

Moore, R. (1977). Reasoning about knowledge and action. In IJCAI-77, pp. 223–227.

Murata, T. (1989). Petri nets: Properties, analysis, and applications. Proceedings of the IEEE, 77(4), 541–576.

Narayanan, S. (1997a). Knowledge-based Action Representations for Metaphor and Aspect (KARMA). Ph.D. thesis, University of California, Berkeley.

Narayanan, S. (1997b). Talking the talk is like walking the walk: A computational model of verbal aspect. In COGSCI-97, Stanford, CA, pp. 548–553.

Norman, D. A. and Rumelhart, D. E. (1975). Explorations in Cognition. Freeman, San Francisco, CA.

Parsons, T. (1990). Events in the Semantics of English. MIT Press, Cambridge, MA.

Partee, B. H. (Ed.). (1976). Montague Grammar. Academic Press, New York.

Quillian, M. R. (1968). Semantic memory. In Minsky, M. (Ed.), Semantic Information Processing, pp. 227–270. MIT Press, Cambridge, MA.

Raphael, B. (1968). SIR: A computer program for semantic information retrieval. In Minsky, M. (Ed.), Semantic Information Processing, pp. 33–145. MIT Press.

Regier, T. (1996). The Human Semantic Potential. MIT Press, Cambridge, MA.

Reichenbach, H. (1947). Elements of Symbolic Logic. Macmillan, New York.

Russell, S. and Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood Cliffs, NJ.

Schank, R. C. (1972). Conceptual dependency: A theory of natural language processing. Cognitive Psychology, 3, 552–631.

Simmons, R. F. (1965). Answering English questions by computer: A survey. Communications of the ACM, 8(1), 53–70.

Simmons, R. F. (1973). Semantic networks: Their computation and use for understanding English sentences. In Schank, R. C. and Colby, K. M. (Eds.), Computer Models of Thought and Language, pp. 61–113. W.H. Freeman and Co., San Francisco.

ter Meulen, A. (1995). Representing Time in Natural Language. MIT Press, Cambridge, MA.

van Benthem, J. and ter Meulen, A. (Eds.). (1997). Handbook of Logic and Language. MIT Press, Cambridge, MA.

Vendler, Z. (1967). Linguistics in Philosophy. Cornell University Press, Ithaca, NY.

Wilks, Y. (1975a). Preference semantics. In Keenan, E. L. (Ed.), The Formal Semantics of Natural Language, pp. 329–350. Cambridge Univ. Press, Cambridge.

Wilks, Y. (1975b). A preferential, pattern-seeking, semantics for natural language inference. Artificial Intelligence, 6(1), 53–74.

Winograd, T. (1972). Understanding Natural Language. Academic Press, New York.

Woods, W. A. (1967). Semantics for a Question-Answering System. Ph.D. thesis, Harvard University.

Woods, W. A. (1973). Progress in natural language understanding. In Proceedings of AFIPS National Conference, pp. 441–450.

Woods, W. A. (1975). What's in a link: Foundations for semantic networks. In Bobrow, D. G. and Collins, A. M. (Eds.), Representation and Understanding: Studies in Cognitive Science, pp. 35–82. Academic Press, New York.

Zwicky, A. and Sadock, J. (1975). Ambiguity tests and how to fail them. In Kimball, J. (Ed.), Syntax and Semantics 4, pp. 1–36. Academic Press, New York.

18 COMPUTATIONAL SEMANTICS

“Then you should say what you mean,” the March Hare went on.

“I do,” Alice hastily replied; “at least—at least I mean what I say—that’s the same thing, you know.”

“Not the same thing a bit!” said the Hatter. “You might just as well say that ‘I see what I eat’ is the same thing as ‘I eat what I see’!”

Lewis Carroll, Alice in Wonderland

This chapter presents a principled computational approach to the problem of semantic analysis, the process whereby meaning representations of the kind discussed in the last chapter are composed and associated with linguistic expressions. The automated creation of accurate and expressive meaning representations necessarily involves a wide range of knowledge-sources and inference techniques. Among the sources of knowledge that are typically involved are the meanings of words, the conventional meanings associated with grammatical constructions, knowledge about the structure of the discourse, common-sense knowledge about the topic at hand and knowledge about the state of affairs in which the discourse is occurring.

The focus of this chapter is a kind of syntax-driven semantic analysis that is fairly modest in its scope. In this approach, meaning representations are assigned to sentences based solely on knowledge gleaned from the lexicon and the grammar. When we refer to an expression's meaning, or meaning representation, we have in mind a representation that is both context independent and free of inference. Representations of this type correspond to the traditional notion of literal meaning discussed in the last chapter.

There are two motivations for proceeding along these lines: there are application domains, including question answering, where such primitive representations are sufficient to produce useful results, and these impoverished representations can serve as useful inputs to subsequent processes that can produce richer, more com-

plete, meaning representations. Chs. 21 and 24 will discuss how these meaning representations can be used in processing extended discourses and dialogs.

18.1 SYNTAX-DRIVEN SEMANTIC ANALYSIS

The approach detailed in this section is based on the principle of compositionality. The key idea behind this approach is that the meaning of a sentence can be constructed from the meanings of its parts. When interpreted superficially this principle is somewhat less than useful. We know that sentences are composed of words, and that words are the primary carriers of meaning in language. It would seem then that all this principle tells us is that we should compose the meaning representation for sentences from the meanings of the words that make them up.

Fortunately, the Mad Hatter has provided us with a hint as to how to make this principle useful. The meaning of a sentence is not based solely on the words that make it up, but also on the ordering and grouping of words, and on the relations among the words in the sentence. Of course, this is simply another way of saying that the meaning of a sentence is partially based on its syntactic structure. Therefore, in syntax-driven semantic analysis, the composition of meaning representations is guided by the syntactic components and relations provided by the kind of grammars discussed in Ch. 12.

Let's begin by assuming that the syntactic analysis of an input sentence serves as the input to a semantic analyzer. Figure 18.1 illustrates an obvious pipeline-oriented approach that follows directly from this assumption. An input is first passed through a parser to derive its syntactic analysis. This analysis is then passed as input to a semantic analyzer to produce a meaning representation. Note that

although this diagram shows a parse tree as input, other syntactic representations such as flat chunks, feature structures, or dependency structures can also be used. For the remainder of this chapter we'll assume tree-like inputs.

Before moving on, we should touch on the role of ambiguity in this story. As we've seen, ambiguous representations can arise from numerous sources including competing syntactic analyses, ambiguous lexical items, competing anaphoric references and as we'll see later in this chapter ambiguous quantifier scopes. In the syntax-driven approach presented here, we assume that syntactic, lexical and anaphoric ambiguities are not a problem. That is, we'll assume that some larger system is capable of iterating through the possible ambiguous interpretations and passing them individually to the kind of semantic analyzer described here.

Let's consider how such an analysis might proceed with the following example:

(18.1) Franco likes Frasca

Fig. 18.1 shows a simplified parse tree (lacking any feature attachments), along with a plausible meaning representation for this example. As suggested by the dashed arrows, a semantic analyzer given this tree as input might fruitfully proceed by first retrieving a skeletal meaning representation from the subtree corresponding to the verb likes. The analyzer would then retrieve or compose meaning representations corresponding to the two noun phrases in the sentence. Then using the representation acquired from the verb as a kind of template, the noun phrase meaning representations would be used to bind the appropriate variables in the verb representation, thus producing the meaning representation for the sentence as a whole.

Unfortunately, there are a number of serious difficulties with this simplified story. As described, the function used to interpret the tree in Fig. 18.1 must know, among other things, that it is the verb that carries the template upon which the final representation is based, where its corresponding arguments are and which argument fills which role in the verb's meaning representation. In other words, it requires a good deal of specific knowledge about this particular example and its parse tree to create the required meaning representation. Given that there are an infinite number of such trees for any reasonable grammar, any approach based on one semantic function for every possible tree is in serious trouble.

Fortunately, we have faced this problem before. Languages are not defined by enumerating the strings or trees that are permitted, but rather by specifying finite devices that are capable of generating the desired set of outputs. It would seem, therefore, that the right place for semantic knowledge in a syntax-directed approach is with the finite set of devices that are used to generate trees in the first place: the grammar rules and the lexical entries. This is known as the rule-to-rule

hypothesis (Bach, 1976).

Designing an analyzer based on this approach brings us back to the notion of parts and what it means for them to have meanings. The following section is an attempt to answer the following two questions:

• What does it mean for a syntactic constituent to have a meaning?

• What do these meanings have to be like so that they can be composed into larger meanings?

18.2 SEMANTIC AUGMENTATIONS TO CONTEXT-FREE GRAMMAR RULES

In keeping with the approach used in Ch. 16, we will begin by augmenting our context-free grammar rules with semantic attachments. These attachments are instructions that specify how to compute the meaning representation of a construction from the meanings of its constituent parts. Abstractly, our augmented rules have the following structure:

$$ A\to\alpha_{1}\dots\alpha_{n}\qquad\{f(\alpha_{j.s e m},\dots,\alpha_{k.s e m})\} $$

The semantic attachment to the basic context-free rule is shown in the \{\dots\} to the right of the rule's syntactic constituents. This notation states that the meaning representation assigned to the construction A, which we will denote as A.sem, can be computed by running the function f on some subset of the semantic attachments of A's constituents.

There are myriad ways to instantiate this style of rule-to-rule approach. Our semantic attachments could, for example, take the form of arbitrary programming language fragments. A meaning representation for a given derivation could then be constructed by passing the appropriate fragments to an interpreter in a bottom-up fashion and then storing the resulting representations as the value for the associated

non-terminals. $ ^{1} $ Such an approach would allow us to create any meaning representation we might like. Unfortunately, the unrestricted power of this approach would also allow us to create representations that have no correspondence at all with the kind of formal logical expressions described in the last chapter. Moreover, this approach would provide us with very little guidance as to how to go about designing the semantic attachments to our grammar rules.

For these reasons, more principled approaches are typically used to instantiate the rule-to-rule approach. We’ll introduce two such constrained approaches in this chapter. The first makes direct use of FOL and the $ \lambda $-calculus notation introduced in Ch. 17. This approach essentially uses a logical notation to guide the creation of logical forms in a principled fashion. The second approach, described later in Sec. 18.4 is based on the feature-structure and unification formalisms introduced in Ch. 16.

To get started, let's take a look at a very basic example along with a simplified target semantic representation.

(18.2) Maharani closed

Closed(Maharani)

Let's work our way bottom-up through the rules involved in this example's derivation. Starting with the proper noun, the simplest possible approach is to assign a unique FOL constant to it, as in the following.

$$ {\mathrm{P r o p e r N o u n}}\;\to\;{\mathrm{M a h a r a n i}}\qquad\left\{{\mathrm{M a h a r a n i}}\right\} $$

The non-branching NP rule that dominates this one doesn't add anything semantically, so we'll just copy the semantics of the ProperNoun up unchanged to the NP.

$$ NP\to ProperNoun\qquad\{ProperNoun.sem\} $$

Moving on to the VP, the semantic attachment for the verb needs to provide the name of the predicate, specify its arity and provide the means to incorporate an argument once it's discovered. We'll make use of a $ \lambda $-expression to accomplish these tasks.

$$ \begin{aligned}&VP\rightarrow Verb\quad\{Verb.sem\}\\&Verb\rightarrow closed\quad\{\lambda x.Closed(x)\}\\ \end{aligned} $$

This attachment stipulates that the verb closed has a unary predicate Closed as its representation. The $ \lambda $-notation gives us the means to leave unspecified, as the x variable, the entity that is closing. As with our earlier NP rule, the intransitive VP rule that dominates the verb simply copies upward the semantics of the verb below it.

Proceeding upward, it remains for the semantic attachment for the S rule to bring things together by inserting the semantic representation of the subject NP as the first argument to the predicate.

$$ S\to NP VP\qquad\{VP.sem(NP.sem)\} $$

Since the value of VP.sem is a $ \lambda $-expression and the value of NP.sem is a simply a FOL constant, we can create our desired final meaning representation by using $ \lambda $-reduction to apply the VP.sem to the NP.sem.

$$ \lambda x.Closed(x)(Maharani)\Longrightarrow Closed(Maharani) $$

This example illustrates a general pattern which will repeat itself throughout this chapter. The semantic attachments to our grammar rules will consist primarily of $ \lambda $-reductions, where one element of an attachment serves as a functor and the rest serve as arguments to it. As we'll see, the real work resides in the lexicon where the bulk of the meaning representations are introduced.

Although this example illustrates the basic approach, the full story is a bit more complex. Let's begin by replacing our earlier target representation with one that is more in keeping with the event-oriented representations introduced in the last chapter, and by considering an example with a more complex noun phrase as its subject.

(18.3) Every restaurant closed.

The target representation for this example should be the following.

$$ \forall x{R e s t a u r a n t}(x)\Rightarrow(\exists e{C l o s i n g}(e)\land{C l o s e d T h i n g}(e,x) $$

Clearly, the semantic contribution of the subject noun phrase in this example is much more extensive than in our previous one. In our earlier example, the FOL constant representing the subject was simply plugged into the correct place in Closed predicate via a single $ \lambda $-reduction. Here the final result involves a complex intertwining of the content provided by the NP and the content provided by the VP. We'll have to do some work if we want rely on $ \lambda $-reduction to produce what we want here.

The first step is to determine exactly what we’d like the meaning representation of Every restaurant to be. Let’s start by assuming that Every invokes the $ \forall $ quantifier and that restaurant specifies the category of concept that we’re quantifying over, which we’ll call the restriction of the noun phrase. Putting these together we might expect the meaning representation to be something like $ \forall x \text{Restaurant}(x) $. Although this is a valid FOL formula its not a terribly useful one, since it says that everything is a restaurant. What’s missing from it is the notion that noun phrases like every restaurant are normally embedded in expressions that stipulate something about the universally quantified variable. That is, we’re probably trying to

say something about all restaurants. This notion is traditionally referred to as the NP's nuclear scope. In this case, the nuclear scope of this noun phrase is closed.

We can capture these notions in our target representation by adding a dummy predicate, $Q$, representing the scope and attaching that predicate to the restriction predicate with an $\Rightarrow$ logical connective, leaving us with the following expression:

$$ \forall xRestaurant(x)\Rightarrow Q(x) $$

Ultimately, what we need to do to make this expression meaningful is to replace Q with the logical expression corresponding to the nuclear scope. Fortunately, the $ \lambda $-calculus can come to our rescue again. All we need to do is to permit $ \lambda $-variables to range over FOL predicates as well as terms. The following expression captures exactly what we need.

$$ \lambda Q.\forall xRestaurant(x)\Rightarrow Q(x) $$

The following series of grammar rules with their semantic attachments serve to produce this desired meaning representation for this kind of NP.

$$ NP\ \to Det\ Nominal\qquad\{Det.Sem(Nominal.Sem)\} $$

$$ Det\to every\quad\left\{\lambda P.\lambda Q.\forall x P(x)\Rightarrow Q(x)\right\} $$

$$ Nominal\ \to\ Noun\quad\{Noun.sem\} $$

$$ \mathrm{Noun}\rightarrow\mathrm{restaurant}\quad\left\{\lambda x\mathrm{Restaurant}(x)\right\} $$

The critical step in this sequence involves the $ \lambda $-reduction in the NP rule. This rule applies the $ \lambda $-expression attached to the Det to the semantic attachment of the Nominal, which is itself a $ \lambda $-expression. The following are the intermediate steps in this process.

$$ \lambda P.\lambda Q.\forall x P(x)\Rightarrow Q(x)(\lambda x.Restaurant(x)) $$

$$ \lambda Q.\forall x\lambda x.Restaurant(x)(x)\Rightarrow Q(x) $$

$$ \lambda Q.\forall x Restaurant(x)\Rightarrow Q(x) $$

The first expression is the expansion of the Det.Sem(Nominal.Sem) semantic attachment to the NP rule. The second formula is the result of this $ \lambda $-reduction. Note that this second formula has a $ \lambda $-application embedded in it. Reducing this expression in place gives us the final form.

Having revised our semantic attachment for the subject noun phrase portion of our example, let's move to the S and VP and Verb rules to see how they need to change to accommodate these revisions. Let's start with the S rule and work our way down. Since the meaning of the subject NP is now a $ \lambda $-expression, it makes sense to consider it as a functor to be called with the meaning of the VP as its argument. The following attachment accomplishes this.

$$ S\to NP VP\qquad\{NP.sem(VP.sem)\} $$

Note that we've flipped the role of functor and argument from our original proposal for this S rule.

The last attachment to revisit is the one for the verb close. We need to update it to provide a proper event-oriented representation and to make sure that it is interfaces well with the new S and NP rules. The following attachment accomplishes both goals.

$$ Verb\to close\qquad\{\lambda x.\exists e Closed(e)\land Closed(e,x)\} $$

This attachment is passed unchanged to the VP constituent via the intransitive VP rule. It is then combined with the meaning representation of Every restaurant as dictated by the semantic attachment for the S given earlier. The following expressions illustrate the intermediate steps in this process.

$$ \lambda Q.\forall xRestaurant(x)\Rightarrow Q(x)(\lambda y.\exists eClosed(e)\land Closed(e,y)) $$

$$ \forall x Restaurant(x)\Rightarrow\lambda y.\exists e Closed(e)\land Closed(e,y)(x) $$

$$ \forall x{R e s t a u r a n t}(x)\Rightarrow\exists e{C l o s e d}(e)\land{C l o s e d}(e,x) $$

These steps achieve our goal of getting the VP's meaning representation spliced in as the nuclear scope in the NP's representation.

As is always the case with any kind of grammar engineering effort we now need to make sure that our earlier simpler examples still work. One area that we need to revisit is our representation of proper nouns. Let's consider them in the context of our earlier example.

(18.4) Maharani closed

The S rule now expects the subject NP's semantic attachment to be a functor applied to the semantics of the VP, therefore our earlier representation of proper nouns as FOL constants won't do. Fortunately, we can once again exploit the flexibility of the $ \lambda $-calculus to accomplish what we need with the following expression.

$$ \lambda x.x(M a h a r a n i) $$

This trick turns a simple FOL constant into a $ \lambda $ $ \lambda $ expression, which when reduced serves to inject the constant into a larger expression. You should work through our original example with all of the new semantic rules to make sure that you can come up with the following intended representation:

$$ \exists e C l o s i n g(e)\land c l o s e d(M a h a r a n i) $$

As one final exercise, let's see how this approach extends to an expression involving a transitive verb phrase, as in the following.

(18.5) Matthew opened a restaurant.

If we've done things correctly we ought to be able to specify the semantic attachments for transitive verb phrases, for the verb open and for the determiner a, while leaving the rest of our rules alone.

Let's start by modeling the semantics for the determiner a on our earlier attachment for every.

$$ Det\to a\qquad\{\lambda P.\lambda Q.\exists x P(x)\land Q(x)\} $$

This rule differs from the attachment for every in two ways. First we’re using the existential quantifier $ \exists $ to capture the semantics of $ a $. And second we’ve replaced the $ \Rightarrow $ operator with a logical $ \land $. The overall framework remains the same with the $ \lambda $-variables $ P $ and $ Q $ standing in for the restriction and nuclear scopes to be filled in later. With this addition our existing NP rule will create the appropriate representation for a restaurant:

$$ \lambda Q\exists xRestaurant(x)\land Q(x) $$

Next let's move on to the Verb and VP rules. There are two arguments that need to be incorporated into the underlying meaning representation. One argument is available at the level of the transitive VP rule, and the second at the S rule. Let's assume the following form for the VP semantic attachment.

$$ VP\to Verb\,NP\qquad\{\mathit{Verb.Sem}(NP.Sem)\} $$

This attachment assumes that the verb's semantic attachment will be applied as a functor to the semantics of its noun phrase argument. And let's assume for now that the representations we developed earlier for quantified noun phrases and proper nouns will remain unchanged. With these assumptions in mind, the following attachment for the verb opened will do what we want.

$$ {V e r b~}\to{o p e n e d}\{\lambda w.\lambda z.w(\lambda x\exists e{O p e n i n g}(e)\land{O p e n e r}(e,z)\land{O p e n e d}(e,x))\} $$

With this attachment in place, the transitive VP rule will incorporate the variable standing for a restaurant as the second argument to opened, incorporate the entire expression representing the opening event as the nuclear scope of a restaurant and finally produce a $ \lambda $-expression suitable for use with our S rule. As with the previous example you should walk through this example step by step to make sure that you arrive at our intended meaning representation.

$$ \exists xRestaurant(x)\land\exists eOpening(e)\land Opener(e,Matthew)\land Opened(e,x) $$

The list of semantic attachments which we've developed for this small grammar fragment is shown in Fig. 18.2. Sec. 18.5 expands the coverage of this fragment to some of the more important constructions in English.

In walking through these examples, we have introduced three techniques that instantiate the rule-to-rule approach to semantic analysis introduced at the beginning of this section:

| Grammar Rule | Semantic Attachment |

| --- | --- |

| S $ \rightarrow $ NP VP | $ \{NP.sem(VP.sem)\} $ |

| NP $ \rightarrow $ Det Nominal | $ \{Det.sem(Nominal.sem)\} $ |

| NP $ \rightarrow $ ProperNoun | $ \{ProperNoun.sem\} $ |

| Nominal $ \rightarrow $ Noun | $ \{Noun.sem\} $ |

| VP $ \rightarrow $ Verb | $ \{Verb.sem\} $ |

| VP $ \rightarrow $ Verb NP | $ \{Verb.sem(NP.sem)\} $ |

| Det $ \rightarrow $ every | $ \{\lambda P.\lambda Q.\forall x P(x) \Rightarrow Q(x)\} $ |

| Det $ \rightarrow $ a | $ \{\lambda P.\lambda Q.\exists x P(x) \land Q(x)\} $ |

| Noun $ \rightarrow $ restaurant | $ \{\lambda r.Restaurant(r)\} $ |

| ProperNoun $ \rightarrow $ Matthew | $ \{\lambda m.m(Matthew)\} $ |

| ProperNoun $ \rightarrow $ Franco | $ \{\lambda f.f(Franco)\} $ |

| ProperNoun $ \rightarrow $ Franco | $ \{\lambda f.f(Frasca)\} $ |

| Verb $ \rightarrow $ closed | $ \{\lambda x.\exists e Closing(e) \land Closed(e,x)\} $ |

| Verb $ \rightarrow $ opened | $ \{\lambda w.\lambda z.w(\lambda x.\exists e Opening(e) \land Opener(e,z) \land Opened(e,x))\} $ |

| Figure 18.3 Semantic attachments for a fragment of our English grammar and lexicon. | |

1. Associating complex, function-like, $ \lambda $-expressions with lexical items

2. Copying of semantic values from children to parents in non-branching rules

3. Function-like application of the semantics of one of the children of a rule to the semantics of the other children of the rule via $ \lambda $-reduction.

These techniques serve to illustrate a general division of labor that guides the design of semantic attachments in this compositional framework. In general, it is the lexical rules that introduce quantifiers, predicates and terms into our meaning representations. The semantic attachments for grammar rules put these elements together in the right ways, but do not in general introduce new elements into the representations being created.

18.3 QUANTIFIER SCOPE AMBIGUITY AND UNDERSPECIFICATION

The grammar fragment developed in the last section appears to be sufficient to handle examples like the following that contain two or more quantified noun phrases.

(18.6) Every restaurant has a menu.

Systematically applying the rules given in Fig. 18.2 to this example produces the following perfectly reasonable meaning representation.

$$ \begin{array}{c}\forall x Restaurant(x)\Rightarrow\\\exists y Menu(y)\land\exists e Having(e)\land Haver(e,x)\land Had(e,y)\end{array} $$

This formula more or less corresponds to the common sense notion that all restaurants have menus.

Unfortunately, this isn't the only possible interpretation for this example. The following is also possible.

$$ \begin{array}{l}\exists y Menu(y)\land\forall x Restaurant(x)\Rightarrow\\\quad\exists e Having(e)\land Haver(e,x)\land Had(e,y)\end{array} $$

This formula asserts that there is one menu out there in the world and all restaurants share it. Now from a common sense point of view this seems pretty unlikely, but remember that our semantic analyzer only has access to the semantic attachments in the grammar and the lexicon in producing meaning representations. Of course, world knowledge and contextual information can be used to select between these two readings, but only if we are able to produce both.

This example illustrates that expressions containing quantified terms can give rise to ambiguous representations even in the absence of syntactic, lexical or anaphoric ambiguities. This is generally known as the problem of quantifier scoping. The difference between the two interpretations given above arises from which of the two quantified variables has the outer scope.

The approach outlined in the last section can not handle this phenomena. To fix this we’ll need the following capabilities.

• The ability to efficiently create underspecified representations that embody all possible readings without explicitly enumerating them

• A means to generate, or extract, all of the possible readings from this representation

• And the ability to choose among the possible readings

The following sections will outline approaches to the first two problems. The solution to the last, most important problem, requires the use of context and world knowledge and unfortunately remains a largely unsolved problem.