## 1. Introduction: Goals and methods of computational linguistics


### 1.1 Goals of computational linguistics



The theoretical goals of computational linguistics include the
formulation of grammatical and semantic frameworks for characterizing
languages in ways enabling computationally tractable implementations of
syntactic and semantic analysis; the discovery of processing techniques
and learning principles that exploit both the structural and
distributional (statistical) properties of language; and the
development of cognitively and neuroscientifically plausible
computational models of how language processing and learning might
occur in the brain.


The practical goals of the field are broad and varied. Some of the most
prominent are: efficient text retrieval on some desired topic;
effective machine translation (MT); question answering (QA), ranging
from simple factual questions to ones requiring inference and
descriptive or discursive answers (perhaps with justifications); text
summarization; analysis of texts or spoken language for topic,
sentiment, or other psychological attributes; dialogue agents for
accomplishing particular tasks (purchases, technical trouble shooting,
trip planning, schedule maintenance, medical advising, etc.); and
ultimately, creation of computational systems with human-like
competency in dialogue, in acquiring language, and in gaining knowledge
from text.


### 1.2 Methods of computational linguistics



The methods employed in theoretical and practical research in
computational linguistics have often drawn upon theories and findings
in theoretical linguistics, philosophical logic, cognitive science
(especially psycholinguistics), and of course computer science.
However, early work from the mid-1950s to around 1970 tended to be
rather theory-neutral, the primary concern being the development of
practical techniques for such applications as MT and simple QA. In MT,
central issues were lexical structure and content, the characterization
of "sublanguages" for particular domains (for example, weather
reports), and the transduction from one language to another (for
example, using rather ad hoc graph transformation grammars or transfer
grammars). In QA, the concern was with characterizing the question
patterns encountered in a specific domain, and the relationship of
these question patterns to the forms in which answers might stored, for
instance in a relational database.


By the mid-1960s a number of researchers emboldened by the increasing
power and availability of general-purpose computers, and inspired by
the dream of human-level artificial intelligence, were designing
systems aimed at genuine language understanding and dialogue. The
techniques and theoretical underpinnings employed varied greatly. An
example of a program minimally dependent on linguistic or cognitive
theory was Joseph Weizenbaum's ELIZA program, intended to emulate (or
perhaps caricature) a Rogerian psychiatrist. ELIZA relied on matching
user inputs to stored patterns (brief word sequences interspersed with
numbered slots, to be filled from the input), and returned one of a set
of output templates associated with the matched input pattern,
instantiated with material from the input. While ELIZA and its modern
chatbot descendants are often said to rely on mere trickery, it can be
argued that human verbal behavior is to some degree reflexive in the
manner of ELIZA, i.e., we
function in "preprogrammed" or formulaic
manner in certain situations, for example, in exchanging greetings, or
in responding at a noisy party to comments whose contents, apart from
an occasional word, eluded us.


A very different perspective on linguistic processing was proffered in
the early years by researchers who took their cue from ideas about
associative processes in the brain. For example, M. Ross Quillian (1968)
proposed a model of word sense disambiguation based on "spreading
activation" in a network of concepts (typically corresponding to senses
of nouns) interconnected through relational links (typically
corresponding to senses of verbs or prepositions). Variants of this
"semantic memory" model were pursued by researchers such as Rumelhart,
Lindsay and Norman (1972), and remain as an active research paradigm in
computational models of language and cognition. Another psychologically
inspired line of work was initiated in the 1960s and pursued for over
two decades by Roger Schank and his associates, but in his case the
goal was full story understanding and inferential question answering. A
central tenet of the work was that the representation of sentential
meaning as well as world knowledge centered around a few (e.g., 11)
action primitives, and inference was driven by rules associated
primarily with these primitives; (a prominent exponent of a similar
view was Yorick Wilks). Perhaps the most important aspect of Schank's
work was the recognition that language understanding and inference were
heavily dependent on a large store of background knowledge, including
knowledge of numerous "scripts" (prototypical ways in which familiar
kinds of complex events, such as dining at a restaurant, unfold) and
plans (prototypical ways in which people attempt to accomplish their
goals) (Schank & Abelson 1977).


More purely AI-inspired approaches that also emerged in the 1960s
were exemplified in systems such as Sad Sam
(Lindsay 1963), Sir (Raphael 1968)
and Student (Bobrow 1968). These featured
devices such as pattern matching/transduction for analyzing and
interpreting restricted subsets of English, knowledge in the form of
relational hierarchies and attribute-value lists, and QA methods based
on graph search, formal deduction protocols and numerical algebra. An
influential idea that emerged slightly later was that knowledge in AI
systems should be framed procedurally rather than
declaratively--to know something is to be able to perform certain
functions (Hewitt 1969). Two quite impressive systems that exemplified
such a methodology were shrdlu (Winograd 1972)
and
Lunar (Woods et al. 1972), which contained
sophisticated proceduralized grammars and syntax-to-semantics
mapping rules, and were able to function fairly robustly in their
"micro-domains" (simulated blocks on a table, and a lunar rock
database, respectively). In addition, shrdlu featured
significant planning abilities, enabled by the
microplanner goal-chaining language (a precursor of
Prolog). Difficulties that remained for all of these approaches were
extending linguistic coverage and the reliability of parsing and
interpretation, and most of all, moving from microdomains, or coverage
of a few paragraphs of text, to more varied, broader domains. Much of
the difficulty of scaling up was attributed to the "knowledge
acquisition bottleneck"--the difficulty of coding or acquiring the
myriad facts and rules evidently required for more general
understanding. Classic collections containing several articles on the
early work mentioned in the last two paragraphs are Marvin
Minsky's *Semantic Information Processing* (1968) and Schank
and Colby's *Computer Models of Thought and Language* (1973).




Since the 1970s, there has been a gradual trend away from purely
procedural approaches to ones aimed at encoding the bulk of linguistic
and world knowledge in more understandable, modular, re-usable forms,
with firmer theoretical foundations. This trend was enabled by the
emergence of comprehensive syntactico-semantic frameworks such as
Generalized Phrase Structure Grammar (GPSG), Head-driven Phrase
Structure Grammar (HPSG), Lexical-Functional Grammar (LFG),
Tree-Adjoining Grammar (TAG), and Combinatory Categorial Grammar (CCG),
where in each case close theoretical attention was paid both to the
computational tractability of parsing, and the mapping from syntax to
semantics. Among the most important developments in the latter area
were Richard Montague's profound insights into the logical (especially
intensional) semantics of language, and Hans Kamp's and Irene Heim's
development of Discourse Representation Theory (DRT), offering a
systematic, semantically formal account of anaphora in language.




A major shift in nearly all aspects of natural language processing
began in the late 1980s and was virtually complete by the end of 1995:
this was the shift to corpus-based, statistical approaches (signalled
for instance by the appearance of two special issues on the subject by
the quarterly *Computational Linguistics* in 1993). The new
paradigm was enabled by the increasing availability and burgeoning
volume of machine-readable text and speech data, and was driven
forward by the growing awareness of the importance of the
distributional properties of language, the development of powerful new
statistically based learning techniques, and the hope that these
techniques would overcome the scalability problems that had beset
computational linguistics (and more broadly AI) since its
beginnings.


The corpus-based approach has indeed been quite successful in producing
comprehensive, moderately accurate speech recognizers, part-of-speech
(POS) taggers, parsers for learned probabilistic phrase-structure
grammars, and even MT and text-based QA systems and summarization
systems. However, semantic processing has been restricted to rather
shallow aspects, such as extraction of specific data concerning
specific kinds of events from text (e.g.,
location, date, perpetrators,
victims, etc., of terrorist bombings) or extraction of clusters of
argument types, relational tuples, or paraphrase sets from text
corpora. Currently, the corpus-based, statistical approaches are still
dominant, but there appears to be a growing movement towards
integration of formal logical approaches to language with corpus-based
statistical approaches in order to achieve deeper understanding and
more intelligent behavior in language comprehension and dialogue
systems. There are also efforts to combine connectionist and neural-net
approaches with symbolic and logical ones. The following sections will
elaborate on many of the topics touched on above. General references
for computational linguistics are Allen 1995, Jurafsky and
Martin 2009, and Clark et al. 2010.


## 2. Syntax and parsing


### 2.1 The structural hierarchy


Language is structured at multiple levels, beginning in the case of
spoken language with patterns in the acoustic signal that can be
mapped to *phones* (the distinguishable successive sounds of
which languages are built up). Groups of phones that are equivalent
for a given language (not affecting the words recognized by a hearer,
if interchanged) are the *phonemes* of the language. The
phonemes in turn are the constituents of *morphemes* (minimal
meaningful word segments), and these provide the constituents of
words. (In written language one speaks instead of characters,
graphemes, syllables, and words.) Words are grouped
into *phrases*, such as noun phrases, verb phrases, adjective
phrases and prepositional phrases, which are the structural components
of sentences, expressing complete thoughts. At still higher levels we
have various types of discourse structure, though this is generally
looser than lower-level structure.


Techniques have been developed for language analysis at all of these
structural levels, though space limitations will not permit a serious
discussion of methods used below the word level. It should be noted,
however, that the techniques developed for speech recognition in the
1980s and 1990s were very influential in turning NLP research towards
the new corpus-based, statistical approach referred to above. One
key idea was that of *hidden Markov
models* (HMMs), which model "noisy" sequences (e.g.,
phone sequences, phoneme sequences, or word sequences) as if generated
probabilistically by "hidden" underlying states and their transitions.
Individually or in groups, successive hidden states model the more
abstract, higher-level constituents to be extracted from observed noisy
sequences, such as phonemes from phones, words from phonemes, or parts
of speech from words. The generation probabilities and the state
transition probabilities are the parameters of such models, and
importantly these can be learned from training data. Subsequently the
models can be efficiently applied to the analysis of new data, using
fast dynamic programming algorithms such as the *Viterbi algorithm*.
These quite successful techniques were subsequently generalized to
higher-level structure, soon influencing all aspects on NLP.


### 2.2 Syntax


Before considering how grammatical structure can be represented,
analyzed and used, we should ask what basis we might have for
considering a particular grammar "correct", or a particular sentence
"grammatical," in the first place. Of course, these are primarily
questions for linguistics proper, but the answers we give certainly
have consequences for computational linguistics.


Traditionally, formal grammars have been designed to capture linguists'
intuitions about well-formedness as concisely as possible, in a way
that also allows generalizations about a particular language (e.g.,
subject-auxiliary inversion in English questions) and across languages
(e.g., a consistent ordering
of nominal subject, verb, and nominal
object for declarative, pragmatically neutral main clauses). Concerning
linguists' specific well-formedness judgments, it is worth noting that
these are largely in agreement not only with each other, but also with
judgments of non-linguists--at least for "clearly grammatical" and
"clearly ungrammatical" sentences (Pinker 2007). Also the discovery
that conventional phrase structure supports elegant compositional
theories of meaning lends credence to the traditional theoretical
methodology.


However, traditional formal grammars have generally not covered any
one language comprehensively, and have drawn sharp boundaries between
well-formedness and ill-formedness, when in fact people's (including
linguists') grammaticality judgments for many sentences are uncertain
or equivocal. Moreover, when we seek to process sentences "in the
wild", we would like to accommodate regional, genre-specific, and
register-dependent variations in language, dialects, and erroneous and
sloppy language (e.g., misspellings, unpunctuated run-on sentences,
hesitations and repairs in speech, faulty constituent orderings
produced by non-native speakers, and fossilized errors by native
speakers, such as "for you and I"--possibly a product of
schoolteachers inveighing against "you and me" in subject position).
Consequently linguists' idealized grammars need to be made
variation-tolerant in most practical applications. The way this need
has typically been met is by admitting a far greater number of phrase
structure rules than linguistic parsimony would sanction--say,
10,000 or more rules instead of a few hundred. These rules are not
directly supplied by linguists (computational or otherwise), but
rather can be "read off" corpora of written or spoken language that
have been decorated by trained annotators (such as linguistics
graduate students) with their basic phrasal tree
structure. Unsupervised grammar acquisition (often starting with
POS-tagged training corpora) is another avenue 
(see section 9), but
results are apt to be less satisfactory. In conjunction with
statistical training and parsing techniques, this loosening of grammar
leads to a rather different conception of what comprises a
grammatically flawed sentence: It is not necessarily one rejected by
the grammar, but one whose analysis requires some rarely used
rules.


As mentioned in section 1.2, the representations of grammars used
in computational linguistics have varied from procedural ones to ones
developed in formal linguistics, and systematic, tractably parsable
variants developed by computationally oriented linguists. Winograd's
shrdlu program, for example, contained code in
his programmar language expressing,



> 
> To parse a
> sentence, try parsing a noun phrase (NP); if this fails, return NIL,
> otherwise try parsing a verb phrase (VP) next and if this fails, or
> succeeds with words remaining, return NIL, otherwise return success.
> 
> 



Similarly Woods' grammar for lunar was based on a
certain kind of procedurally interpreted transition graph (an
augmented transition network, or ATN), where the sentence subgraph
might contain an edge labeled NP (*analyze an NP using the NP
subgraph*) followed by an edge labeled VP (analogously
interpreted). In both cases, local feature values (e.g.,
the *number* and *person* of a NP and VP) are
registered, and checked for agreement as a condition for success. A
closely related formalism is that of definite clause grammars (e.g.,
Pereira & Warren 1982), which employ Prolog to assert "facts" such
as that if the input word sequence contains an NP reaching from
index *I*1 to index *I*2 and a VP reaching from
index *I*2 to index *I*3, then the input contains a
sentence reaching from index *I*1 to index *I*3. (Again,
feature agreement constraints can be incorporated into such assertions
as well.) Given the goal of proving the presence of a sentence, the
goal-chaining mechanism of Prolog then provides a procedural
interpretation of these assertions.


At present the most commonly employed declarative representations
of grammatical structure are *context-free grammars*
(*CFGs*) as defined by Noam Chomsky (1956, 1957), because of
their simplicity and efficient parsability. Chomsky had argued that
only deep linguistic representations are context-free, while surface
form is generated by *transformations* (for example, in English
passivization and in question formation) that result in a
non-context-free language. However, it was later shown that on the one
hand, unrestricted Chomskian transformational grammars allowed for
computationally intractable and even undecidable languages, and on the
other, that the phenomena regarded by Chomsky as calling for a
transformational analysis could be handled within a context-free
framework by use of suitable *features* in the specification of
syntactic categories. Notably, *unbounded movement*, such as
the apparent movement of the final verb object to the front of the
sentence in "Which car did Jack urge you to buy?", was shown to be
analyzable in terms of a *gap* (or *slash*) feature of
type /NP[wh] that is carried by each of the two embedded VPs,
providing a pathway for matching the category of the fronted object to
the category of the vacated object position. Within
non-transformational grammar frameworks, one therefore speaks of
*unbounded* (or *long-distance*) *dependencies*
instead of unbounded movement. At the same time it should be noted
that at least some natural languages have been shown to be mildly
context-sensitive (e.g., Dutch and Swiss German exhibit cross-serial
dependencies where a series of nominals "NP1 NP2 NP3 ..."
need to be matched, in the same order, with a subsequent series
of verbs, "V1 V2 V3 ..."). Grammatical frameworks that
seem to allow for approximately the right degree of mild context
sensitivity include Head Grammar, Tree-Adjoining Grammar (TAG),
Combinatory Categorial Grammar (CCG), and Linear Indexed Grammar
(LIG). Head grammars allow insertion of a complement between the head
of a phrase (e.g., the initial verb of a VP, the final noun of a NP,
or the VP of a sentence) and an already present complement; they were
a historical predecessor of Head-Driven Phrase Structure Grammar
(HPSG), a type of unification grammar (see below) that has received
much attention in computational linguistics. However, unrestricted
HPSG can generate the recursively enumerable (in general only
semi-decidable) languages.


A typical (somewhat simplified) sample fragment of a context-free
grammar is the following, where phrase types are annotated with
feature-value pairs:




|  |  |  |
| --- | --- | --- |
| S[vform:*v*] |  - |  NP[pers:*p*
numb:*n* case:subj] VP[vform:*v* pers:*p*
numb:*n*] |
| VP[vform:*v* pers:*p*
numb:*n*] |  - |  V[subcat:\_np
vform:*v* pers:*p* numb:*n*] NP[case:obj] |
| 
NP[pers:3 numb:*n*] |  - |  Det[pers:3
numb:*n*] N[numb:*n*] |
|  NP[numb:*n*
pers:3 case:*c*] |  - | 
Name[numb:*n* pers:3 case:*c*] |


Here *v, n, p, c* are variables that can assume values such
as 'past', 'pres', 'base',
'pastparticiple', ... (i.e., various verb forms),
'1', '2', '3' (1st,
2nd, and 3rd person), 'sing',
'plur', and 'subj',
'obj'. The *subcat* feature indicates the
complement requirements of the verb. The lexicon would supply entries
such as



> 
> 
> 
> |  |  |  |
> | --- | --- | --- |
> | V[subcat:\_np
>  vform:*pres* numb:sing pers:3] | 
> - | **loves** |
> | 
> Det[pers:3 numb:sing] |  - | **a** |
> | 
> N[pers:3 numb:sing] |  - | **mortal** |
> | 
> Name[pers:3 numb:sing gend:fem case:subj] |  - | **Thetis**, |
> 
> 
> 


allowing, for example, a phrase structure analysis of the sentence
"Thetis loves a mortal" (where we have omitted the feature
names for simplicity, leaving only their values, and ignored the case
feature):



> 
> ![[a tree diagram: at the top,
> S[pres], a line connects the top node to first, NP[3 sing subj], which
> connects to, Name[3 sing subj], which connects to
> 'Thetis'.  A second line from the top node connects to
> VP[pres 3 sing] which in turn first connects to V[_np pres 3 sing]
> that connects to 'loves'.  Second it connects to NP[3
> sing] that in turn connects to Def[3 sing] (and that to
> 'a') and N[3 sing] (and that to 'mortal').]](fig1.png)   
> 
> **Figure 1**: Syntactic analysis of a sentence as a parse tree
> 


As a variant of CFGs, *dependency grammars* (*DGs*)
also enjoy wide popularity. The difference from CFGs is that
hierarchical grouping is achieved by directly subordinating words to
words (allowing for multiple *dependents* of
a *head* *word*), rather than phrases to phrases. For
example, in the sentence of figure 1 we would treat *Thetis*
and *mortal* as dependents of *loves*, using dependency
links labeled *subj* and *obj* respectively, and the
determiner *a* would in turn be a dependent
of *mortal*, *via* a dependency link *mod*
(for *modifier*). *Projective* dependency grammars are
ones with no crossing dependencies (so that the descendants of a node
form a continuous text segment), and these generate the same languages
as CFGs. Significantly, mildly non-projective dependency grammars,
allowing a head word to dominate two separated blocks, provide the
same generative capacity as the previously mentioned mildly
context-sensitive frameworks that are needed for some languages
(Kuhlmann 2013).


As noted at the beginning of this section, traditional formal
grammars proved too limited in coverage and too rigid in their
grammaticality criteria to provide a basis for robust coverage of
natural languages as actually used, and this situation persisted until
the advent of probabilistic grammars derived from sizable
phrase-bracketed corpora (notably the Penn Treebank). The simplest
example of this type of grammar is a *probabilistic context-free
grammar* or PCFG. In a PCFG, each phrase structure rule *X*
- *Y*1 ... *Y**k* is assigned a probability,
viewed as the probability that a constituent of type *X* will be
expanded into a sequence of (immediate) constituents of
types *Y*1, ..., *Y**k*. At the lowest level, the
expansion probabilities specify how frequently a given part of speech
(such as Det, N, or V) will be realized as a particular word. Such a
grammar provides not only a structural but also a distributional model
of language, predicting the frequency of occurrence of various phrase
sequences and, at the lowest level, word sequences. 


However, the simplest models of this type do not model the
statistics of actual language corpora very accurately, because the
expansion probabilities for a given phrase type (or part of speech) *X*
ignore the surrounding phrasal context and the more detailed
properties (such as head words) of the generated constituents. Yet
context and detailed properties are very influential; for example,
whether the final prepositional phrase in "She detected a
star with {binoculars, planets}" modifies *detected*
or *planets* is very dependent on word choice. Such modeling
inaccuracies lead to parsing inaccuracies (see next subsection), and
therefore generative grammar models have been refined in various ways,
for example (in so-called *lexicalized models*) allowing for
specification of particular phrasal head words in rules, or
(in *tree substitution grammars*) allowing expansion of
nonterminals into subtrees of depth 2 or more. Nevertheless, it seems
likely that fully accurate distributional modeling of language would
need to take account of semantic content, discourse structure, and
intentions in communication, not only of phrase
structure. Possibly *construction grammars* (e.g., Goldberg
2003), which emphasize the coupling between the entrenched patterns of
language (including ordinary phrase structure, cliches, and
idioms) and their meanings and discourse function, will provide a
conceptual basis for building statistical models of language
that are sufficiently accurate to enable more nearly human-like
parsing accuracy. 


### 2.3 Parsing



Natural language analysis in the early days of AI tended to rely on
template matching, for example, matching templates such as
(*X* has *Y*) or
(how many *Y* are there
on *X*) to the input to be analyzed. This of course
depended on having a very restricted discourse and task domain. By the
late 1960s and early 70s, quite sophisticated recursive parsing
techniques were being employed. For example, Woods'
lunar system used a top-down recursive parsing strategy
interpreting an ATN in the manner roughly indicated in 
section 2.2 (though ATNs in principle allow other
parsing styles). It also saved recognized constituents in a table,
much like the class of parsers we are about to describe. Later parsers
were influenced by the efficient and conceptually elegant CFG parsers
described by Jay Earley (1970) and (separately) by John Cocke, Tadao
Kasami, and Daniel Younger (e.g., Younger 1967). The latter algorithm,
termed the CYK or CKY algorithm for the three separate authors, was
particularly simple, using a bottom-up dynamic programming approach to
first identify and tabulate the possible types (nonterminal labels) of
sentence segments of length 1 (i.e., words), then the possible types
of sentence segments of length 2, and so on, always building on the
previously discovered segment types to recognize longer phrases. This
process runs in cubic time in the length of the sentence, and a parse
tree can be constructed from the tabulated constituents in quadratic
time. The CYK algorithm assumes a Chomsky Normal Form (CNF) grammar,
allowing only productions of form N*p* -
N*q* N*r*, or N*p*
- *w*, i.e., generation of two nonterminals or a word from
any given nonterminal. This is only a superficial limitation, because
arbitrary CF grammars are easily converted to CNF.



The method most frequently employed nowadays in fully analyzing
sentential structure is *chart parsing*. This is a
conceptually simple and efficient dynamic programming method closely
related to the algorithms just mentioned; i.e., it begins by assigning
possible analyses to the smallest constituents and then inferring
larger constituents based on these, until an instance of the top-level
category (usually S) is found that spans the given text or text
segment. There are many variants, depending on whether only complete
constituents are posited or incomplete ones as well (to be
progressively extended), and whether we proceed left-to-right through
the word stream or in some other order (e.g., some seemingly
best-first order). A common variant is a *left-corner* chart
parser, in which partial constituents are posited whenever their
"left corner"--i.e., leftmost constituent on the
right-hand side of a rule--is already in place. Newly completed
constituents are placed on an *agenda*, and items are
successively taken off the agenda and used if possible as left corners
of new, higher-level constituents, and to extend partially completed
constituents. At the same time, completed constituents (or rather,
categories) are placed in a chart, which can be thought of as a
triangular table of width *n* and height *n* (the number
of words processed), where the cell at indices (*i, j*),
with *j* > *i*, contains the
categories of all complete constituents so far verified reaching from
position *i* to position *j* in the input. The chart is
used both to avoid duplication of constituents already built, and
ultimately to reconstruct one or more global structural analyses. (If
all possible chart entries are built, the final chart will allow
reconstruction of all possible parses.) Chart-parsing methods carry
over to PCFGs essentially without change, still running within a cubic
time bound in terms of sentence length. An extra task is maintaining
probabilities of completed chart entries (and perhaps bounds on
probabilities of incomplete entries, for pruning purposes).



Because of their greater expressiveness, TAGs and CCGs are harder to
parse in the worst case (O(*n*6)) than CFGs
and projective DGs (O(*n*3)), at least with
current algorithms (see Vijay-Shankar & Weir 1994 for parsing
algorithms for TAG, CCG, and LIG based on bottom-up dynamic
programming). However, it does not follow that TAG parsing or CCG
parsing is impractical for real grammars and real language, and in
fact parsers exist for both that are competitive with more common
CFG-based parsers.
 


Finally we mention *connectionist* models of parsing,
which perform syntactic analysis using layered (artificial) neural
nets (ANNs, NNs) (see Palmer-Brown et al. 2002; Mayberry and
Miikkulainen 2008; and Bengio 2008 for surveys). There is typically a
layer of input units (nodes), one or more layers of hidden units, and
an output layer, where each layer has (excitatory and inhibitory)
connections forward to the next layer, typically conveying evidence
for higher-level constituents to that layer. There may also be
connections within a hidden layer, implementing cooperation or
competition among alternatives. A linguistic entity such as a phoneme,
word, or phrase of a particular type may be represented within a layer
either by a pattern of activation of units in that layer
(a *distributed* representation) or by a single activated unit
(a *localist* representation). 


One of the problems that connectionist models need to confront is that
inputs are temporally sequenced, so that in order to combine
constituent parts, the network must retain information about recently
processed parts. Two possible approaches are the use of *simple
recurrent networks* (*SRNs*)
and, in localist networks, sustained
activation. SRNs use one-to-one feedback connections from the hidden
layer to special *context units*
aligned with the previous layer
(normally the input layer or perhaps a secondary hidden layer), in
effect storing their current outputs in those context units. Thus at
the next cycle, the hidden units can use their own previous outputs,
along with the new inputs from the input layer, to determine their next
outputs. In localist models it is common to assume that once a unit
(standing for a particular concept) becomes active, it stays active for
some length of time, so that multiple concepts corresponding to
multiple parts of the same sentence, and their properties, can be
simultaneously active. A problem that arises is how the properties of
an entity that are active at a given point in time can be properly tied
to that entity, and not to other activated entities. (This is the
*variable binding* problem, which has spawned a variety of
approaches--see Browne and Sun 1999). One solution is to assume
that unit activation consists of pulses emitted at a globally fixed
frequency, and pulse trains that are in phase with one another
correspond to the same entity (e.g., see Henderson 1994). Much
current connectionist research borrows from symbolic processing
perspectives, by assuming that parsing assigns linguistic phrase
structures to sentences, and treating the choice of a structure as
simultaneous satisfaction of symbolic linguistic constraints (or
biases). Also, more radical forms of hybridization and modularization
are being explored, such as interfacing a NN parser to a symbolic
stack, or using a neural net to learn the probabilities needed in a
statistical parser, or interconnecting the parser network with
separate prediction networks and learning networks. For an overview
of connectionist sentence processing and some hybrid methods (see
Crocker 2010).


### 2.4 Coping with syntactic ambiguity



If natural language were structurally unambiguous with respect to some
comprehensive, effectively parsable grammar, our parsing technology
would presumably have attained human-like accuracy some time ago,
instead of levelling off at about 90% constituent recognition
accuracy. In fact, however, language is ambiguous at all structural
levels: at the level of speech sounds ("recognize speech"
vs. "wreck a nice beach"); morphology
("un-wrapped" vs. "unwrap-ped"); word category
(*round* as an adjective, noun, verb or adverb); compound word
structure (*wild goose chase*); phrase category
(nominal *that*-clause *vs.* relative clause in
"the idea **that he is entertaining**"); and modifier
(or complement) attachment ("He hit the man **with the
baguette**"). The parenthetical examples here have been chosen
so that their ambiguity is readily noticeable, but ambiguities are far
more abundant than is intuitively apparent, and the number of
alternative analyses of a moderately long sentence can easily run into
the thousands.


Naturally, alternative structures lead to alternative meanings, as
the above examples show, and so structural disambiguation is
essential. The problem is exacerbated by ambiguities in the meanings
and discourse function even of syntactically unambiguous words and
phrases, as discussed below (section 4). But
here we just mention some of the structural preference principles that
have been employed to achieve at least partial structural
disambiguation. First, some psycholinguistic principles that have been
suggested are *Right Association* (RA) (or *Late
Closure,* LC), *Minimal Attachment* (MA), and *Lexical
Preference* (LP). The following examples illustrate these
principles:



> 
> 
> (2.1) (RA)
>  He bought the book that I had selected **for Mary**.
> 
> (Note the preference for attaching *for Mary* to *selected* rather than *bought*.) 
> (2.2) (MA?) She carried the
> groceries **for Mary**.
> 
> (Note the preference for attaching *for Mary* to *carried*, rather than *groceries*,
> despite RA. The putative MA-effect might actually be an LP-like verb
> modification preference.)
> (2.3) (LP) She describes men who have
> worked on farms **as
> cowboys**.
> (Note the preference for
> attaching *as cowboys* to *describes*, rather
> than *worked*.)
> 
> 



Another preference noted in the literature is for parallel structure in
coordination, as illustrated by the following examples:



> 
> 
> (2.4)
> They asked for
> tea and coffee with sugar.
> (Note the preference for the grouping
> [[*tea and coffee*] *with sugar*], despite RA.)
> (2.5)
> John decided to
> buy a novel, and Mary, a biography.
> (The partially elided conjunct is
> understood as "Mary decided to buy a biography".)
> (2.6)  John submitted short stories
> to the editor, and poems too.
> (The partially elided conjunct is
> understood as 
> "submitted poems to the editor too".)
> 
> 
> 


Finally, the following example serves to illustrate the
significance of frequency effects, though such effects are hard to
disentangle from semantic biases for any single sentence (improvements
in parsing through the use of word and phrase frequencies provide more
compelling evidence): 



> 
> (2.7) What are the
> degrees of freedom that an object in space has?
> (Note the preference for attaching the
> relative clause to *degrees of freedom*, rather
> than *freedom*, attributable to the tendency of *degree(s)
> of freedom* to occur as a "multiword".)
> 
> 
> 


## 3. Semantic representation



Language serves to convey meaning. Therefore the analysis of
syntactic structure takes us only partway towards mechanizing that
central function, and the merits of particular approaches to syntax
hinge on their utility in supporting semantic analysis, and in
generating language from the meanings to be communicated.



This is not to say that syntactic analysis is of no value in
itself--it can provide a useful support in applications such as
grammar checking and statistical MT. But for the more ambitious goal
of inferring and expressing the meaning of language, an essential
requirement is a theory of semantic representation, and how it is
related to surface form, and how it interacts with the representation
and use of background knowledge. We will discuss logicist approaches,
cognitive science approaches, and (more briefly) emerging statistical
approaches to meaning representation.


### 3.1 Logicist approaches to meaning representation



Most linguistic semanticists, cognitive scientists, and
anthropologists would agree that in some sense, language is a mirror of
mind. But views diverge concerning how literally or non-literally this
tenet should be understood. The most literal understanding, which we
will term the *logicist* view,
is the one that regards language
itself as a logical meaning representation with a compositional,
indexical semantics--at least when we have added brackets as
determined by parse trees, and perhaps certain other augmentation
(variables, lambda-operators, etc.)
In itself, such a view makes no commitments about mental
representations, but application of Occam's razor and the presumed
co-evolution of thought and language then suggest that mentalese is
itself language-like. The common objection that "human thinking is not
logical" carries no weight with logicists, because logical meaning
representations by no means preclude nondeductive modes of inference
(induction, abduction, etc.);
nor are logicists impressed by the objection that people quickly forget
the exact wording of verbally conveyed information, because both
canonicalization of inputs and systematic discarding of all but major
entailments can account for such forgetting. Also assumption of a
language-like,
logical mentalese certainly does not preclude other modes of
representation and thought, such as imagistic ones, and synergistic
interaction with such modes (Paivio 1986; Johnston & Williams 2009).


#### Relating language to logic



Since Richard Montague (see especially Montague 1970, 1973) deserves
much of the credit for demonstrating that language can be logically
construed, let us reconsider the sentence structure in figure 1 and
the corresponding grammar rules and vocabulary, but this time
suppressing features, and instead indicating how logical
interpretations expressed in (a variant of) Montague's type-theoretic
intensional logic can be obtained compositionally. We slightly
"twist" Montague's type system so that the possible-world
argument always comes last, rather than first, in the denotation of a
symbol or expression. For example, a two-place predicate will be of
type (*e* - (*e* - (*s* - *t*)))
(successively applying to an entity, another entity, and finally a
possible world to yield a truth value), rather than Montague's type
(*s* - (*e* - (*e* - *t*))), where
the world argument is first. This dispenses with numerous applications
of Montague's intension ([?]) and extension
([?]) operators, and also slightly simplifies truth
conditions. For simplicity we are also ignoring contextual indices
here, and treating nouns and VPs as true or false of individuals,
rather than individual concepts (as employed by Montague to account
for such sentences as "The temperature is 90 and rising").




> 
> 
> 
> |  |  |  |  |  |  |
> | --- | --- | --- | --- | --- | --- |
> | S | - |  NP VP;  |  S'  | = | 
> NP'(VP') |
> | VP | - | V NP;  | VP' | = |  (l*x* NP'(l*y*
> V'(*y*)(*x*))) |
> | NP  | - |  Det N;  | NP'  | = |  Det'(N') |
> | NP  | - |  Name;  |  NP'  | = |  Name' |
> 
> 
> 



Here primed constituents represent the intensional logic translations
of the corresponding constituents. (Or we can think of them as
metalinguistic expressions standing for the set-theoretic denotations
of the corresponding constituents.) Several points should be noted.
First, each phrase structure rule is accompanied by a unique semantic
rule (articulated as the *rule-to-rule*
hypothesis by Emmon Bach (1976)),
where the denotation of each phrase is fully determined by the
denotations of its *immediate*
constituents: the semantics is
*compositional.* 



Second, in the S'-rule, the subject is assumed to be a second-order
predicate that is applied to the denotation of the VP (a monadic
predicate) to yield a sentence intension, whereas we would ordinarily
think of the subject-predicate semantics as being the other way
around, with the VP-denotation being applied to the subject. But
Montague's contention was that his treatment was the proper one,
because it allows all types of subjects--pronouns, names, and
quantified NPs--to be handled uniformly. In other words, an NP
always denotes a second-order property, or (roughly speaking) a set of
first-order properties (see also Lewis 1970). So for example,
*Thetis* denotes the set of all properties that Thetis (a
certain contextually determined individual with that name) has; (more
exactly, in the present formulation *Thetis* denotes a function
from properties to sentence intensions, where the intension obtained
for a particular property yields truth in worlds where the entity
referred to has that property); *some woman* denotes the union
of all properties possessed by at least one woman; and
*every woman* denotes the set of properties shared by all
women. Accordingly, the S'-rule yields a sentence intension that is
true at a given world just in case the second-order property denoted
by the subject maps the property denoted by the VP to such a
truth-yielding intension.


Third, in the VP'-rule, variables *x* and *y*
are assumed to be of type *e* (they take basic individuals as
values), and the denotation of a transitive verb should be thought of
as a function that is applied first to the object, and then to the
subject (yielding a function from worlds to truth values--a sentence
intension). The lambda-abstractions in the VP'-rule can be
understood as ensuring that the object NP, which like any NP denotes a
second-order property, is correctly applied to an ordinary property
(that of being the love-object of a certain *x*), and the
result is a predicate with respect to the (still open) subject
position. The following is an interpreted sample vocabulary:



> 
> 
> 
> |  |  |  |  |  |  |
> | --- | --- | --- | --- | --- | --- |
> | V | - | ***loves***; |  V'  | = | loves |
> |  Det  | - | ***a***; |  
>  Det'  | = |  l*P* l*Q*([?]*x*[*P*(*x*) [?]
> *Q*(*x*)]) |
> |  (For comparison: |
> | Det |  - | ***every***; | 
> Det' |  = |  l*P*
> l*Q*([?]*x*[*P*(*x*) [?] *Q*(*x*)]) |
> | N | - | ***mortal***; | 
>  N'  | = |  mortal |
> | Name | - | ***Thetis***; |  
> Name'  | = | l*P*(*P*(Thetis)) |
> 
> 
> 


Note the interpretation of the indefinite determiner
(on line 2)
as a generalized quantifier--in effect
a second-order predicate over two ordinary properties, where these
properties have intersecting truth domains. We could have used an
atomic symbol for this second-order predicate, but the above way of
expanding it shows the relation of the generalized quantifier to the
ordinary existential quantifier. Though it is a fairly self-evident
matter, we will indicate in section 4.1 how the sentence 
"Thetis loves a mortal" yields the following representation after some
lambda-conversions:



> 
>  ([?]*x* [mortal(*x*) [?]
> loves(*x*)(Thetis)]).
> 


(The English sentence also has a generic or habitual reading,
"Thetis loves mortals in general", which we ignore here.) This
interpretation has rather a classical look to it, but only because of
the reduction from generalized to ordinary quantifiers that we have
built into the lexical semantics of the indefinite *a* in the
above rules, instead of using an atomic symbol for it. Montague was
particularly interested in dealing satisfactorily with intensional
locutions, such as 
"John seeks a unicorn." This does not
require the existence of a unicorn for its truth--John has a certain
relation to the unicorn-property, rather than to an existing
unicorn. Montague therefore treated all predicate arguments as
intensions; i.e., he rendered 
"John seeks a unicorn"
as



>  seeks(l*Q*
> [?]*x*[unicorn([?]*x*)
> [?] *Q*([?]*x*)]) ([?]john),
> 


which can be reduced to a version where unicorn is extensionalized to
unicorn\*:



>  seeks(l*Q*
> [?]*x*[unicorn\*(*x*)
> [?] *Q*([?]*x*)]) ([?]john).
> 


But ultimately Montague's treatment of NPs, though it was in a sense
the centerpiece of his proposed conception of language-as-logic, was
not widely adopted in computational linguistics. This was in part
because the latter community was not convinced that an omega-order
logic was needed for NL semantics, found the somewhat complex treatment
of NPs in various argument positions and in particular, the treatment
of scope ambiguities in terms of multiple syntactic analyses, 
unattractive, and was preoccupied with other semantic issues, such as
adequately representing events and their relationships, and developing
systematic nominal and verb "ontologies" for broad-coverage NL
analysis. Nonetheless, the construal of language as logic left a strong
imprint on computational semantics, generally steering the field
towards compositional approaches, and in some approaches such as CCG,
providing a basis for a syntax tightly coupled to a type-theoretic
semantics (Bach et al. 1987;
Carpenter 1997).


An alternative to Montague's syntax-based approach to quantifier scope
ambiguity is to regard NPs of form Det+N (or strictly, Det+N-bar) as
initially unscoped higher-order predicates in an underspecified logical
form, to be subsequently "raised" so as to apply to a first-order
predicate obtained by lambda-abstraction of the vacated term position.
For example, in the sentence 
"Everyone knows a poem", with the object
existentially interpreted, we would have the underspecified LF



> 
> knows<a(poem)> <every(person)> 
> 
> 



 (without reducing
determiners to classical quantifiers) and we can now "raise"
<a(poem)>  to yield



> 
> a(poem)(l*y*
> knows(*y*)<every(person)> , 
> 
> 



and then "raise"
<every(person)>  to yield either



> 
> a(poem)(l*y*
> every(person)(l*x* knows(*y*)(*x*))),
> 
> 



 or



> 
> every(person)(l*x*
> a(poem)(l*y* knows(*y*)(*x*))).
> 
> 



 Thus we obtain a reading according to which there is a poem that
everyone knows, and another according to which everyone knows some
poem (not necessarily the same one). (More on scope disambiguation
will follow in section 4). A systematic version
of this approach, known as Cooper storage (see Barwise & Cooper
1981) represents the meaning of phrases in two parts, namely a
sequence of NP-interpretations (as higher-order predicates) and the
logical matrix from which the NP-interpretations were extracted.


But one can also take a more conventional approach, where first of
all, the use of "curried" (Schonfinkel-Church-Curry)
functions in the semantics of predication is avoided in favor of
relational interpretations, using lexical semantic formulas such
as **loves'** =
l*y*l*x*(loves(*x*, *y*)), and
second, unscoped NP-interpretations are viewed as unscoped restricted
quantifiers (Schubert & Pelletier 1982). Thus the unscoped LF
above would be knows(<[?]poem> ,
<[?]person> ), and scoping of quantifiers, along with
their restrictors, now involves "raising" quantifiers to
take scope over a sentential formula, with simultaneous introduction
of variables. The two results corresponding to the two alternative
scopings are then



>  ([?]*y*: poem(*y*))([?]*x*:
> person(*x*))knows(*x*, *y*), 
> 
> 



and



> 
> ([?]*x*:
> person(*x*))([?]*y*: poem(*y*))knows(*x*, *y*). 
> 
> 



While this strategy departs
from the strict compositionality of Montague Grammar, it achieves
results that are often satisfactory for the intended purposes and does
so with minimal computational fuss. A related approach to logical form
and scope ambiguity enjoying some current popularity is *minimal
recursion semantics* (MRS) (Copestake et al.
2005), which goes even further in fragmenting the meaningful parts of
an expression, with the goal of allowing incremental constraint-based
assembly of these pieces into unambiguous sentential LFs. Another
interesting development is an approach based on
*continuations*, a notion taken
from programming language theory (where a
continuation is a program execution state as determined by the steps
still to be executed after the current instruction). This also allows
for a uniform account of the meaning of quantifiers, and provides
a handle on such phenomena as "misplaced modifiers", as in 
"He had a quick cup of coffee" (Barker 2004).


An important innovation in logical semantics was *discourse
representation theory* (DRT) (Kamp 1981; Heim 1982), aimed at a
systematic account of anaphora. In part, the goal was to provide a
semantic explanation for (in)accessibility of NPs as referents of
anaphoric pronouns, e.g., in contrasting examples such as "John
doesn't drive a car; \*he owns it," vs. "John drives a
car; he owns it". More importantly, the goal was to account for
the puzzling semantics of sentences involving donkey anaphora, e.g.,

"If John owns a donkey, he beats it." Not only is the
NP *a donkey*, the object of the if-clause, accessible as
referent of the anaphoric *it*, contrary to traditional
syntactic binding theory (based on the notion of C-command), but
furthermore we seem to obtain an interpretation of the type
"John beats every donkey that he owns", which cannot be
obtained by "raising" the embedded indefinite *a
donkey* to take scope over the entire sentence. There is also a
weaker reading of the type, "If John owns a donkey, he beats a
donkey that he owns", and this reading also is not obtainable
via any scope analysis. Kamp and Heim proposed a dynamic process of
sentence interpretation in which a discourse representation structure
(DRS) is built up incrementally. A DRS consists of a set
of *discourse referents* (variables) and a set of
*conditions*, where these
conditions may be simple predications or
equations over discourse referents, or certain logical combinations of
DRS's (not of conditions). The DRS for the sentence under consideration
can be written linearly as



>  [: [*x*, *y*: john(*x*),
> donkey(*y*)] **=** [*u*, *v*:
> he(*u*), it(*v*),
> beats(*u*, *v*), *u*=*x*, *v*=*y*]]
> 



or diagrammed as



> 
> ![[a box with a horizontal line
> breaking it into two.  The top half takes up about one-sixth of the
> space and is empty.  The bottom half contains two other boxes side by
> side with a double right arrow connecting them.  The left box is also
> divided in two parts horizontally; the top half has 'x,y';
> the bottom half has three lines containing 'john(x)',
> 'donkey(y)', and 'owns(x,y)' respectively.
> The right box is also divided in two parts horizontally; the top half
> has 'u,v'; the bottom half has five lines containing
> 'he(u)', 'it(u)', 'beats(u,v)',
> 'u=x', and 'v=y' respectively.]](fig2.png)   
> 
> **Figure 2**: DRS for "If John owns a donkey, he beats it"
> 


Here *x, y, u, v* are discourse referents introduced
by *John, a donkey, he,* and *it*, and the
equations *u=x, v=y* represent the result of reference
resolution for *he* and *it*. Discourse referents in the
antecedent of a conditional are accessible in the consequent, and
discourse referents in embedding DRSs are accessible in the embedded
DRSs. Semantically, the most important idea is that discourse
referents are evaluated dynamically. We think of a variable assignment
as a *state*, and this state changes as we evaluate a DRS
outside-to-inside, left-to-right. For example (simplifying a bit), the
conditional DRS in figure 4 is true (in a given model) if every
assignment with domain {*x*,
*y*} that makes the antecedent true can be extended to an
assignment (new state) with domain
{*x*, *y*, *u*, *v*} that makes the consequent
true.


On the face of it, DRT is noncompositional (though DRS construction
rules are systematically associated with phrase structure rules); but
it can be recast in compositional form, still of course with a dynamic
semantics. A closely related approach, *dynamic predicate
logic* (DPL) retains the classical quantificational
syntax, but in effect treats existential quantification as
nondeterministic assignment, and provides an overtly compositional
alternative to DRT (Groenendijk & Stokhof 1991). Perhaps
surprisingly, the impact of DRT on practical computational linguistics
has been quite limited, though it certainly has been and continues to
be actively employed in various projects. One reason may be that
donkey anaphora rarely occurs in the text corpora most intensively
investigated by computational linguists so far (though it is arguably
pervasive and extremely important in generic sentences and
generic passages, including those found in lexicons or sources such as
Common Sense Open Mind--see sections
 4.3 and 8.3). Another reason
is that reference resolution for non-donkey pronouns (and definite
NPs) is readily handled by techniques such as Skolemization of
existentials, so that subsequently occurring anaphors can be
identified with the Skolem constants introduced earlier. Indeed, it
turns out that both explicit and implicit variants of Skolemization,
including functional Skolemization, are possible even for donkey
anaphora (e.g., in sentences such as "If every man has a gun, many
will use it"--see Schubert 2007). Finally, another reason for
the limited impact of DRT and other dynamic semantic theories may be
precisely that they are dynamic: The evaluation of a formula in
general requires its preceding and embedding context, and this
interferes with the kind of knowledge modularity (the ability to use
any given knowledge item in a variety of different contexts) desirable
for inference purposes. Here it should be noted that straightforward
translation procedures from DRT, DPL, and other dynamic theories to
static logics exist (e.g., to FOL, for nonintensional versions of the
dynamic approaches), but if such a conversion is desirable for
practical purposes, then the question arises whether starting with a
dynamic representation is at all advantageous.


#### Thematic roles and (neo-)Davidsonian representations



A long-standing issue in linguistic semantics has been the theoretical
status of thematic roles in the argument structure of verbs and
other argument-taking elements of language (e.g., Dowty 1991). The
syntactically marked cases found in many languages correspond
intuitively to such thematic roles as *agent,
theme, patient, instrument,
recipient, goal*, and so on, and in English, too, the sentence
subject
and object typically correspond respectively to the agent and theme or
patient of an action, and other roles may be added as an indirect
object or more often as prepositional phrase complements and adjuncts.
To give formal expression to these intuitions, many computational
linguists decompose verbal (and other) predicates derived from language
into a core predicate augmented with explicit binary relations
representing thematic roles. For example, the sentence



> 
> (3.1)John kicked the ball to the fence
> 


might be represented (after referent determination) as



> [?]*e*(kick(*e*) [?] before(*e*,
> Now1) [?] agent(*e*, John)
> [?] theme(*e*, Ball2) [?] goal-loc(*e*, Fence3)),
> 


where *e* is thought of as the kicking event. Such a
representation is called *neo-Davidsonian*, acknowledging
Donald Davidson's advocacy of the view that verbs tacitly introduce
existentially quantified events (Davidson 1967a). The prefix
*neo-* indicates that all arguments and adjuncts are
represented in terms of thematic roles, which was not part of
Davidson's proposal but is developed, for example, in (Parsons
1990). (Parsons attributes the idea of thematic roles to the 4th
century BCE Sanskrit grammarian Panini.) One
advantage of this style of representation is that it absolves the
writer of the interpretive rules from the vexing task of
distinguishing verb complements, to be incorporated into the argument
structure of the verb, from adjuncts, to be used to add modifying
information. For example, it is unclear in (3.1) whether *to the
fence* should be treated as supplying an argument of
*kick*, or whether it merely modifies the action of John
kicking the ball. Perhaps most linguists would judge the latter answer
to be correct (because an object can be kicked without the intent of
propelling it to a goal location), but intuitions are apt to be
ambivalent for at least one of a set of verbs such as *dribble,
kick, maneuver, move* and *transport*.


However, thematic roles also introduce new difficulties. As pointed out
by Dowty (1991), thematic
roles lack well-defined semantics. For
example, while (3.1) clearly involves an animate agent acting causally
upon a physical object, and the PP evidently supplies a goal location,
it is much less clear what the roles should be in (web-derived)
sentences such as (3.2-3.4), and what semantic content they would
carry:



> 
> (3.2) The surf tossed the
> loosened stones against our feet.
> 
> (3.3) A large truck in front
> of him blocked his view of the traffic light.
> (3.4) Police used a sniffer
> dog to smell the suspect's luggage.
> 
> 
> 


As well, the uniform treatment of complements and adjuncts in terms
of thematic relations does not absolve the computational linguist from
the task of identifying the subcategorized constituents of verb
phrases (and similarly, NPs and APs), so as to guide syntactic and
semantic expectations in parsing and interpretation. And these
subcategorized constituents correspond closely to the complements of
the verb, as distinct from any adjuncts. Nevertheless, thematic role
representations are widely used, in part because they mesh well with
*frame-based* knowledge representations for domain
knowledge. These are representations that characterize a concept in
terms of its type (relating this to supertypes and subtypes in an
inheritance hierarchy), and a set of slots (also called
*attributes* or *roles*) and corresponding values, with
type constraints on values. For example, in a purchasing domain, we
might have a purchase predicate, perhaps with supertype
acquire, subtypes like
purchase-in-installments,
purchase-on-credit, or
purchase-with-cash, and attributes with typed values
such as (buyer (a person-or-group)), (seller (a
person-or-group)), (item (a thing-or-service)), (price (a
monetary-amount)), and perhaps time, place, and other
attributes. Thematic roles associated with relevant senses of verbs
and nouns such as *buy, sell, purchase, acquire, acquisition,
take-over, pick up, invest in, splurge on,* etc., can easily be
mapped to standard slots like those above. This leads into the
issue of canonicalization, which we briefly discuss below under a
separate heading.


#### Expressivity issues


A more consequential issue in computational semantics has been the
expressivity of the semantic representation employed, with respect to
phenomena such as event and temporal reference, nonstandard quantifiers
such as *most*, plurals,
modification, modality and other forms of
intensionality, and reification. Full discussion of these phenomena
would be out of place here, but some commentary on each is warranted,
since the process of semantic interpretation and understanding (as well
as generation) clearly depends on the expressive devices available in
the semantic representation.



*Event and situation reference* are essential in view of the fact that
many sentences seem to describe events or situations, and to qualify and
refer to them. For example, in the sentences



> 
> (3.5) Molly barked last night for
> several minutes. **This** woke up the neighbors.
> 
> 


the barking event is in effect predicated to have occurred last
night and to have lasted for several minutes, and the demonstrative
pronoun
*this* evidently refers directly
to it; in addition the past tense places
the event at some point prior to the time of speech (and would do so
even without the temporal adverbials). These temporal and causal
relations are readily handled within the Davidsonian (or
neo-Davidsonian) framework mentioned above:



> 
> (3.5') bark(Molly, *E*) [?]
> last-night(*E*, *S*) [?] before(*E*, *S*)
> [?]
> duration(*E*)=minutes(*N*) [?] several(*N*).
> cause-to-wake-up(*E*, Neighbors, *E*') [?] before(*E*', *S*).
> 
> 


However, examples (3.6) and (3.7) suggest that events can be
introduced by negated or quantified formulas, as was originally
proposed by Reichenbach (1947):



> 
> (3.6) No
> rain fell for a month, and this caused widespread crop
> failures.
> (3.7) Each superpower imperiled the
> other with its nuclear arsenal.
> This situation persisted for
> decades.
> 
> 
> 


Barwise and Perry (1983) reconceptualized this idea in their
Situation Semantics, though this lacks the tight coupling between
sentences and events that is arguably needed to capture causal
relations expressed in language. Schubert (2000) proposes a solution
to this problem in an extension of FOL incorporating an operator that
connects situations or events with sentences *characterizing*
them.


Concerning *nonstandard quantifiers* such as *most*,
we have already sketched the generalized quantifier approach of
Montague Grammar, and pointed out the alternative of using restricted
quantifiers; an example might be (*Most x:
dog*(*x*))*friendly*(*x*). Instead of
viewing *most* as a second-order predicate, we can specify its
semantics by analogy with classical quantifiers: The sample formula is
true (under a given interpretation) just in case a majority of
individuals satisfying
*dog*(*x*) (when used as value of *x*) also
satisfy *friendly*(*x*). Quantifying determiners such
as *few, many, much, almost all,* etc., can be treated
similarly, though ultimately the problem of vagueness needs to be
addressed as well (which of course extends beyond quantifiers to
predicates and indeed all aspects of a formal semantic
representation). Vague quantifiers, rather than setting rigid
quantitative bounds, seem instead to convey probabilistic information,
as if a somewhat unreliable measuring instrument had been applied in
formulating the quantified claim, and the recipient of the information
needs to take this unreliability into account in updating
beliefs. Apart from their vagueness, the quantifiers under discussion
are not first-order definable (e.g., Landman 1991), so that they
cannot be completely axiomatized in FOL. But this does not prevent
practical reasoning, either by direct use of such quantifiers in
the logical representations of sentences (an approach in the spirit
of *natural logic*), or by reducing them to set-theoretic or
mereological relations within an FOL framework.


*Plurals*, as for instance in



> 
> (3.8) People
> gathered in the town square,
> 
> 


present a problem in that the argument of a predicate can be an
entity comprised of multiple basic individuals (those we ordinarily
quantify over, and ascribe properties to). Most approaches to this
problem employ a plural operator, say, *plur*, allowing us to
map a singular predicate *P* into a plural predicate
*plur*(*P*), applicable to collective entities. These
collective entities are usually assumed to form a join semilattice
with atomic elements (singular entities) that are ordinary individuals
(e.g., Scha 1981; Link 1983; Landman 1989, 2000). When an overlap
relation is assumed, and when all elements of the semilattice are
assumed to have a supremum (completeness), the result is a complete
Boolean algebra except for lack of a bottom element (because there is
no null entity that is a part of all others). One theoretical issue is
the relationship of the semilattice of plural entities to the
semilattice of material parts of which entities are
constituted. Though there are differences in theoretical details
(e.g., Link 1983; Bunt 1985), it is agreed that these semilattices
should be aligned in this sense: When we take the join
of material parts of which several singular or plural entities are
constituted, we should obtain the material parts of the join of those
singular or plural entities. Note that while some verbal predicates,
such as (intransitive) *gather*, are applicable only to
collections, others, such as *ate a pizza*, are variously
applicable to individuals or collections. Consequently, a sentence
such as



> 
> (3.9) The
> children ate a pizza,
> 
> 


allows for both a collective reading, where the children as a group
ate a single pizza, and a distributive reading, where each of the
children ate a pizza (presumably a different one!) One way of dealing
with such ambiguities in practice is to treat plural NPs as ambiguous
between a collection-denoting reading and an "each member of the
collection" reading. For example *the children* in (3.9)
would be treated as ambiguous between *the collection of
children* (which is the basic sense of the phrase) and *each of
the children*. This entails that a reading of type *each of the people* 
should also be available in (3.8) -- but we can assume that this is ruled out 
because (intransitive) *gather* requires a collective argument. 
In a sentence such as



> 
> (3.10) Two poachers caught three aracaris,
> 
> 


we then obtain four readings, based on the two interpretations of
each NP. No readings are ruled out, because both catching and being
caught can be individual or collective occurrences. Some theorists
would posit additional readings, but if these exist, they could be
regarded as derivative from readings in which at least one of the
terms is collectively interpreted. But what is uncontroversial is that
plurals call for an enrichment in the semantic representation language
to allow for collections as arguments. In an expression such
as *plur*(*child*), both the *plur* operator,
which transforms a predicate into another predicate, and the resulting
collective predicate, are of nonstandard types.


*Modification* is a pervasive
phenomenon in all languages, as illustrated
in the following sentences:



> 
> (3.11) Mary is very smart.
> (3.12) Mary is an international
> celebrity.
> 
> (3.13) The rebellion failed utterly.
> 
> 



In (3.11), *very* functions as a predicate modifier, in
particular a subsective modifier, since the set of things that
are *very*(*P*) is a subset of the things that
are *P*. Do we need such modifiers in our logical forms? We
could avoid use of a modifier in this case by supposing
that *smart* has a tacit argument for the degree of smartness,
where *smart*(*x, d*) means that *x* is smart to
degree *d*; adding that *d* > *T* for some
threshold *T* would signify that *x* is very smart.
Other degree adjectives could be handled similarly. However, such a
strategy is unavailable for *international celebrity* in
(3.12). *International* is again subsective (and not
intersective--an international celebrity is not something that is
both international and a celebrity), and while one can imagine
definitions of the particular combination, *international
celebrity*, in an ordinary FOL framework, requiring such
definitions to be available for constructing initial logical forms
could create formidable barriers to broad-coverage
interpretation. (3.13) illustrates a third type of predicate
modification, namely VP-modification by an adverb. Note that the
modifier cannot plausibly be treated as an implicit
predication *utter*(*E*) about a Davidsonian event
argument of *fail*. Taken together, the examples indicate the
desirability of allowing for monadic-predicate modifiers in a semantic
representation. Corroborative evidence is provided in the immediately
following discussion.



*Intensionality* has already been mentioned in connection with
Montague Grammar, and there can be no doubt that a semantic
representation for natural language needs to capture intensionality in
some way. The sentences



> 
> (3.14) John believes that our universe is
> infinite.
> 
> (3.15) John looked happy.
> (3.16) John designed a starship.
> (3.17) John wore a fake beard.
> 
> 
> 


all involve intensionality. The meaning (and thereby the truth
value) of the attitudinal sentence (3.14) depends on the meaning
(intension) of the subordinate clause, not just its truth value
(extension). The meaning of (3.15) depends on the meaning of
*happy*, but does not require *happy* to be a property
of John or anything else. The meaning of (3.16) does not depend on the
actual existence of a starship, but does depend on the meaning of that
phrase. And *fake beard* in (3.17) refers to something other
than an actual beard, though its meaning naturally depends on the
meaning of *beard*. A Montagovian analysis certainly would
deal handily with such sentences. But again, we may ask how much of
the expressive richness of Montague's type theory is really essential
for computational linguistics. To begin with, sentences such as (3.14)
are expressible in classical modal logics, without committing to
higher types. On the other hand (3.16) resists a classical modal
analysis, even more firmly than Montague's "John seeks a
unicorn," for which an approximate classical paraphrase is
possible: "John tries (for him) to find a unicorn". A
modest concession to Montague, sufficient to handle
(3.15)-(3.17), is to admit intensional predicate modifiers into
our representational vocabulary. We can then treat *look* as a
predicate modifier, so that *look*(*happy*) is a new
predicate derived from the meaning of *happy*. Similarly we can
treat *design* as a predicate modifier, if we are willing to
treat *a starship* as a predicative phrase, as we would in
"The Enterprise is a starship". And finally, *fake*
is quite naturally viewed as a predicate modifier, though unlike most
nominal modifiers, it is not intersective (#*John wore something
that was a beard and was fake*) or even subsective (#*John wore
a particular kind of beard*). Note that this form of
intensionality does not commit us to a higher-order logic--we are
not quantifying over predicate extensions or intensions so far, only
over individuals (aside from the need to allow for plural entities, as
noted). The rather compelling case for intensional predicate modifiers
in our semantic vocabulary reinforces the case made above (on the
basis on extensional examples) for allowing predicate
modification.


*Reification*, like the
phenomena already enumerated, is also pervasive
in natural languages. Examples are seen in the following sentences.



> 
> (3.18) Humankind may be on a path to
> self-destruction.
> (3.19) Snow is white.
> 
> (3.20) Politeness is a virtue.
> 
> (3.21) Driving recklessly is
> dangerous.
> 
> (3.22) For John to sulk is unusual.
> 
> (3.23) That our universe
> is infinite is a discredited notion.
> 
> 


(3.18)-(3.21) are all examples of predicate
reification. *Humankind* in (3.18) may be regarded as the name
of an abstract kind derived from the nominal predicate *human,*
i.e., with lexical meaning *K*(*human*),
where *K* maps predicate intensions to individuals. The status
of abstract kinds as individuals is evidenced by the fact that the
predicate "be on a path to self-destruction" applies as
readily to ordinary individuals as to kinds. The name-like character
of the term is apparent from the fact that it cannot readily be
premodified by an adjective. The subjects in (3.19) and (3.20) can be
similarly analyzed in terms of kinds *K*(*snow*) and
*K*(*-ness*(*polite*)). (Here -*ness* is a
predicate modifier that transforms the predicate *polite*,
which applies to ordinary (usually human) individuals, into a
predicate over quantities of the abstract stuff, politeness.) But in
these cases the *K* operator does not originate in the lexicon,
but in a rule pair of type "NP - N, NP' =
*K*(N')". This allows for modification of the nominal
predicate before reification, in phrases such as *fluffy snow*
or *excessive politeness.* The subject of (3.21) might be
rendered logically as something like
*Ka*(-*ly*(*reckless*)(*drive*)), where
*Ka* reifies action-predicates, and -*ly* 
transforms a monadic predicate intension into a subsective predicate
modifier. Finally (3.22) illustrates a type of sentential-meaning
reification, again yielding a kind; but in this case it is a kind of
situation--the kind whose instances are characterized by John
sulking. Here we can posit a reification operator *Ke* that
maps sentence intensions into kinds of situations. This type of
sentential reification needs to be distinguished from
*that*-clause reification, such as appears to be involved in
(3.14). We mentioned the possibility of a modal-logic analysis of
(3.14), but a predicative analysis, where the predicate applies to a
reified sentence intension (a proposition) is actually more plausible,
since it allows a uniform treatment of that-clauses in contexts like
(3.14) and (3.23). The use of reification operators is a departure
from a strict Montgovian approach, but is plausible if we seek to
limit the expressiveness of our semantic representation by taking
predicates to be true or false of individuals, rather than of objects
of arbitrarily high types, and likewise take quantification to be over
individuals in all cases, i.e., to be first-order.


Some computational linguists and AI researchers wish to go much
further in avoiding expressive devices outside those of standard
first-order logic. One strategy that can be used to deal with
intensionality within FOL is to functionalize all predicates, save one
or two. For example, we can treat predications, such as that Romeo
loves Juliet, as values of functions that "hold" at particular times:
***Holds***(*loves*(*Romeo, Juliet*), *t*). Here
*loves* is regarded as a function that yields a reified
property, while ***Holds*** (or in some
proposals, ***True***), and perhaps equality, are the only
predicates in the representation language. Then we can formalize
(3.14), for example, without recourse to intensional semantics as



> 
> ***Holds***(*believes*(*John, infinite*(*Universe*)), *t*)
> 


(where *t* is some specific time). *Humankind* in
(3.18) can perhaps be represented as the set of all humans as a
function of time:



> 
>  [?]*x*[?]*t*[***Holds***(*member*(*x*,
>  *Humankind*), *t*)
>  - *Holds*(*human*(*x*), *t*)],
> 


(presupposing some axiomatization of naive set theory); and, as
one more example, (4.22) might be rendered as



> 
> ***Holds***(*unusual*(*sulk*(*John*))*, t*)
> 



(for some specific time *t*). However, a difficulty with this
strategy is encountered for quantification within intensional
contexts, as in the sentence "John believes that every galaxy
harbors some life-form." While we can represent the
(implausible) wide-scope reading "For every galaxy there is some
life-form such that John believes that the galaxy harbors that
life-form," using the ***Holds*** strategy, we cannot readily
represent the natural narrow-scope reading because FOL disallows
variable-binding operators within functional terms (but see McCarthy
1990). An entirely different approach is to
introduce "eventuality" arguments into all predicates, and
to regard a predication as providing a fact about the actual world
only if the eventuality corresponding to that predication has been
asserted to "occur" (Hobbs 2003). The main practical
impetus behind such approaches is to be able to exploit existing FOL
inference techniques and technology. However, there is at present no
reason to believe that any inferences that are easy in FOL are
difficult in a meaning representation more nearly aligned with the
structure of natural language; on the contrary, recent work in
implementing *natural logic* (MacCartney & Manning 2009)
suggests that a large class of obvious inferences can be most readily
implemented in syntactically analyzed natural language
(*modulo* some adjustments)--a framework closer to
Montagovian semantics than an FOL-based approach.


#### Canonicalization, thematic roles (again), and primitives


Another important issue has been *canonicalization*
(or *normalization*):
What transformations should be applied to initial
logical forms in
order to minimize difficulties in making use of linguistically derived
information? The uses that should be facilitated by the choice of
canonical representation include the interpretation of further texts in
the context of previously interpreted text (and general knowledge), as
well as inferential question answering and other inference tasks.


We can distinguish two types of canonicalization: *logical
normalization* and *conceptual canonicalization*. An
example of logical normalization in sentential logic and FOL is the
conversion to clause form (Skolemized, quantifier-free conjunctive
normal form). The rationale is that reducing multiple logically
equivalent formulas to a single form reduces the combinatorial
complexity of inference. However, full normalization may not be
possible in an intensional logic with a "fine-grained"
semantics, where for instance a belief that the Earth is round may
differ semantically from the belief that the Earth is round and the
Moon is either flat or not flat, despite the logical equivalence of
those beliefs.


*Conceptual canonicalization* involves more radical changes:
We replace the surface predicates (and perhaps other elements of the
representational vocabulary) with canonical terms from a smaller
repertoire, and/or decompose them using thematic roles or frame slots.
For example, in a geographic domain, we might replace the relations
(between countries) *is next to, is adjacent to, borders on, is a
neighbor of, shares a border with,* etc., with a single canonical
relation, say *borders-on*. In the domain of physical,
communicative, and mental events, we might go further and decompose
predicates into configurations of primitive predicates. For example,
we might express "*x* walks" in the manner of Schank
as



> 
> [?]*e, e*'(ptrans(*e, x, x*) [?]
> move(*e', x, feet-of*(*x*))
> [?] by-means-of(*e', e*)),
> 
> 



where ptrans(*e, x, y*) is a primitive
predicate expressing that event *e* is a physical transport by
agent *x* of object *y*, move
expresses bodily motion by an agent, and
by-means-of expresses the instrumental-action
relation between the move
event and the ptrans event.
As discussed earlier, these multi-argument predicates might be further
decomposed, with ptrans(*e, x, y*) rewritten as
ptrans(*e*)
[?] agent(*e, x*)
[?] theme(*e, y*), and so on. As in
the case of logical normalization, conceptual canonicalization is
intended to simplify inference, and to minimize the need for the
axioms on which inference is based.


A question raised by canonicalization, especially by the stronger
versions involving reduction to primitives, is whether significant
meaning is lost in this process. For example, the concept of being
neighboring countries, unlike mere adjacency, suggests the idea of
side-by-side existence of the populations of the countries, in a way
that resembles the side-by-side existence of neighbors in a local
community. More starkly, reducing the notion of walking to transporting
oneself by moving one's feet fails to distinguish walking from running,
hopping, skating, and perhaps even bicycling. Therefore it may be
preferable to regard conceptual canonicalization as inference of
important entailments, rather than as replacement of superficial
logical forms by equivalent ones in a more restricted vocabulary.
Another argument for the latter position is computational: If we
decompose complex actions, such as dining at a restaurant, into
constellations of primitive predications, we will need to match the
many primitive parts of such constellations even in answering simple
questions such as 
"Did John dine at a restaurant?". We will comment
further on primitives in the context of the following subsection.


### 3.2 Psychologically motivated approaches to meaning



While many AI researchers have been interested in semantic
representation and inference as practical means for achieving
linguistic and inferential competence in machines, others have
approached these issues from the perspective of modeling human
cognition. Prior to the 1980s, computational modeling of NLP and
cognition more broadly were pursued almost exclusively within a
representationalist paradigm, i.e.,
one that regarded all intelligent
behavior as reducible to symbol manipulation (Newell and Simon's
physical symbol systems hypothesis). In the 1980s, connectionist (or
neural) models enjoyed a resurgence, and came to be seen by many as
rivalling representationalist approaches. We briefly summarize these
developments under two subheadings below. 


#### Representationalist approaches



> 
> "A physical symbol system has the necessary and sufficient means
> for general intelligent action."
> -Allen Newell and Herbert Simon
> (1976: 116)
> 
> 
> 



Some of the cognitively motivated researchers working within a
representationalist paradigm have been particularly concerned with
*cognitive architecture*, including the associative linkages
between concepts, distinctions between types of memories and types of
representations (e.g., episodic *vs.* semantic memory,
short-term vs. long-term memory, declarative vs. procedural
knowledge), and the observable processing consequences of such
architectures, such as sense disambiguation, similarity judgments,
and cognitive load as reflected in processing delays. Others have been
more concerned with uncovering the actual internal conceptual
vocabulary and inference rules that seem to underlie language and
thought. M. Ross Quillian's semantic memory model, and models
developed by Rumelhart, Norman and Lindsay (Rumelhart et al. 1972;
Norman et al. 1975) and by Anderson and Bower (1973) are
representative of the former perspective, while Schank and his
collaborators (Schank and Colby 1973; Schank and Abelson 1977; Schank
and Riesbeck 1981; Dyer 1983) are representative of the latter. A
common thread in cognitively motivated theorizing about semantic
representation has been the use of graphical semantic memory
models, intended to capture direct relations as well as more
indirect associations between concepts, as illustrated in Figure 3:



> 
> ![[two trees, all parents connect
> to their nodes by solid arrowed lines unless otherwise indicated.  The
> first, on the left, with a boxed parent of the word
> 'plant' and nodes of 'plant1' (which itself
> has nodes of 'structure' [connected by a line labeled
> 'isa'], 'living' [connected by a line labeled
> 'prop'], 'animal' [connected by a line labeled
> '-prop'], 'with3' [connected with a line
> labeled 'prop' and with a node 'leaf'],
> 'get2' [connected with a line labeled 'prop'
> and also a reverse line labeled 'subj', it has two nodes,
> 'food' connected with a line labeled 'obj' and
> 'from', the latter also has nodes 'air',
> 'earth' and a dash boxed 'water' {the
> connection lines of these three nodes are also connected with a dashed
> arc labeled 'or'}]), 'plant2' (which itself
> has a node of 'apparatus' connected by a line labeled
> 'isa' and two dashed lines going to nowhere), and
> 'plant3' (which itself has three dashed lines going to
> nowhere); the connection lines of the three plant nodes are also
> connected with a solid arc labeled 'or'.  The second tree
> with a boxed parent of the word 'water' has two dashed
> lines going nowhere and a node 'supply5' (which itself has
> three nodes, 'person' connected with a line labeled
> 'subj', the dash boxed 'water' from the first
> tree connected with a line labeled 'obj', and
> 'To2' [which itself has a node 'object']); the
> three lines under the top parent are connected by a dashed arc labeled
> 'or']](fig3.png)   
> 
> **Figure 3**
> 


This particular example is loosely based on Quillian
(1968). Quillian suggested that one of the functions of semantic
memory, conceived in this graphical way, was to enable word sense
disambiguation through spreading activation. For example, processing
of the sentence, 
"He watered the plants", would involve
activation of the terms *water* and
*plant*, and this activation would spread to concepts
immediately associated with (i.e., directly linked to) those terms,
and in turn to the neighbors of those concepts, and so on. The
preferred senses of the initially activated terms would be those that
led to early "intersection" of activation signals originating from
different terms. In particular, the activation signals propagating
from sense 1 (the living-plant sense) of *plant* would
reach the concept for the stuff, *water*, in four steps (along
the pathways corresponding to the information that plants may get food
from water), and the same concept would be reached in two steps from
the term *water*, used as a verb, whose semantic representation
would express the idea of supplying water to some target
object. Though the sense of *plant* as a manufacturing
apparatus would probably lead eventually to the *water* concept
as well, the corresponding activation path would be longer, and so the
living-plant sense of *plant* would "win".


Such conceptual representations have tended to differ from logical ones
in several respects. One, as already discussed, has been the emphasis
by Schank and various other researchers (e.g.,
Wilks 1978; Jackendoff
1990) on "deep" (canonical) representations and primitives. An often
cited psychological argument for primitives is the fact that people
rather quickly forget the exact wording of what they read or are told,
recalling only the "gist"; it is this gist that primitive decomposition
is intended to derive. However, this involves a questionable assumption
that subtle distinctions between, say, walking to the park,
ambling to the park, or
traipsing to the park are simply ignored
in the interpretive process, and as noted earlier it neglects the
possibility that seemingly insignificant semantic details are
pruned from memory after a short time, while major entailments are
retained for a longer time.



Another common strain in much of the theorizing about conceptual
representation has been a certain diffidence concerning logical
representations and denotational semantics. The relevant semantics of
language is said to be the transduction from linguistic utterances to
internal representations, and the relevant semantics of the internal
representations is said to be the way they are deployed in
understanding and thought. For both the external language and the
internal (mentalese) representation, it is said to be irrelevant
whether or not the semantic framework provides formal truth conditions
for them. The rejection of logical semantics has sometimes been
summarized in the dictum that one cannot compute with possible worlds.


However, it seems that any perceived conflict between conceptual
semantics and logical semantics can be resolved by noting that these
two brands of semantics are quite different enterprises with quite
different purposes. Certainly it is entirely appropriate for conceptual
semantics to focus on the mapping from language to symbolic structures
(in the head, realized ultimately in terms of neural assemblies or
circuits of some sort), and on the functioning of these structures in
understanding and thought. But logical semantics, as well, has a
legitimate role to play, both in considering how words (and larger
linguistic expressions) relate to the world and how the symbols and
expressions of the internal semantic representation relate to the
world. This role is *metatheoretic*
in that the goal is not to
posit cognitive entities that can be computationally manipulated, but
rather to provide a framework for theorizing about the relationship
between the symbols people use, externally in language and internally
in their thinking, and the world in which they live. It is surely
undeniable that utterances are at least sometimes intended to be
understood as claims about things, properties, and relationships
in the world, and as such are at least sometimes true or false. It would be hard
to understand how language and thought could have evolved as useful
means for coping with the world, if they were incapable of capturing
truths about it.



Moreover, logical semantics shows how certain syntactic manipulations
lead from truths to truths regardless of the specific meanings of the
symbols involved in these manipulations (and these notions can be
extended to uncertain inference, though this remains only very
partially understood). Thus, logical semantics provides a basis for
assessing the soundness (or otherwise) of inference rules. While human
reasoning as well as reasoning in practical AI systems often needs to
resort to unsound methods (abduction, default reasoning, Bayesian
inference, analogy, etc.), logical semantics nevertheless provides an
essential perspective from which to classify and study the properties
of such methods. A strong indication that cognitively motivated
conceptual representations of language are reconcilable with logically
motivated ones is the fact that all proposed conceptual representations
have either borrowed deliberately from logic in the first place (in
their use of predication, connectives, set-theoretic notions, and
sometimes quantifiers) or can be transformed to logical representations
without much difficulty, despite being cognitively motivated.


#### Connectionist approaches


As noted earlier, the 1980s saw the re-emergence of connectionist
computational models within mainstream cognitive science theory (e.g.,
Feldman and Ballard 1982; Rumelhart and McClelland 1986; Gluck and
Rumelhart 1990). We have already briefly characterized connectionist
models in our discussion of connectionist parsing. But the
connectionist paradigm was viewed as applicable not only to specialized
functions, but to a broad range of cognitive tasks including
recognizing objects in an image, recognizing speech,
understanding language, making inferences, and guiding physical
behavior. The emphasis was on learning, realized by adjusting the
weights of the unit-to-unit connections in a layered neural network,
typically by a *back-propagation*
process that distributes credit or
blame for a successful or unsuccessful output to the units involved in
producing the output (Rumelhart and McClelland 1986).


From one perspective, the renewal of interest in connectionism and
neural modeling was a natural step in the endeavor to elaborate
abstract notions of cognitive content and functioning to the point
where they can make testable contact with brain theory and
neuroscience. But it can also be seen as a paradigm shift, to the
extent that the focus on subsymbolic processing began to be linked to a
growing skepticism concerning higher-level symbolic processing as
models of mind, of the sort associated with earlier semantic
network-based and rule-based architectures. For example, Ramsay et al.
(1991) argued that the demonstrated capacity of connectionist
models to perform cognitively interesting tasks undermined the
then-prevailing view of the mind as a physical symbol system. But
others have continued to defend the essential role of symbolic
processing. For example, Anderson (1983, 1993) contended that while
theories of symbolic thought need to be grounded in neurally plausible
processing, and while subsymbolic processes are well-suited for
exploiting the statistical structure of the environment, nevertheless
understanding the interaction of these subsymbolic processes required a
theory of representation and behavior at the symbolic level.


What would it mean for the semantic content of an utterance to be
represented in a neural network, enabling, for example, inferential
question-answering? The anti-representationalist (or "eliminativist")
view would be that no particular structures can be or need to be
identified as encoding semantic content. The input modifies the
activity of the network and the strengths of various connections in a
distributed way, such that the subsequent behavior of the network
effectively implements inferential question-answering. However, this
leaves entirely open how a network would learn this sort of behavior.
The most successful neural net experiments have been aimed at mapping
input patterns to class labels or to other very restricted sets of
outputs, and they have required numerous labeled examples (e.g.,
thousands of images labeled with the class of the objects depicted) to
learn their task. By contrast, humans excel at "one-shot"
learning, and can perform complex tasks based on such learning. 


A less radical alternative to the eliminativist position, termed the
*subsymbolic hypothesis*, was
proposed by Smolensky (1988), to the effect
that mental processing cannot be fully and accurately described in
terms of symbol manipulation, requiring instead a description at the
level of subsymbolic features, where these features are represented in
a distributed way in the network. Such a view does not preclude the
possibility that
assemblies of units in a connectionist system do in fact encode symbols
and more complex entities built out of symbols, such as predications
and rules. It merely denies that the behavior engendered by these
assemblies can be adequately modelled as symbol manipulation.
In fact, much of the neural net research over the past two or three
decades has sought to understand how neural nets can encode symbolic
information (e.g., see Smolensky et al.
1992; Browne and Sun 2001). 


Distributed schemes associate a set of units and their activation
states with particular symbols or values. For example, Feldman (2006)
proposes that concepts are represented by the activity of a cluster of
neurons; triples of such clusters representing a concept, a role, and a
filler (value) are linked together by *triangle
nodes* to represent
simple attributes of objects. Language understanding is treated as a
kind of simulation that maps language onto a more concrete domain of
physical action or experience, guided by background knowledge in the
form of a temporal Bayesian network.


Global schemes encode symbols in overlapping fashion over all units.
One possible global scheme is to view the activation states of the
units, with each unit generating a real value between [?]1 and 1, as
propositions: State *p*
entails state *q*
(equivalently, *p* is at
least as specific as *q*) if
the activation *q**i* of each unit *i*
in state *q* satisfies *p**i*
[?] *q**i* [?] 0, or
*q**i* = 0, or 0 [?] *q**i* [?]
*p**i* depending on whether the
activation *p**i* of that unit in state*p* is negative, zero, or positive respectively. Propositional
symbols can then be interpreted in terms of such states, and truth
functions in terms of simple max-min operations and sign inversions
performed on network states. (See Blutner, 2004; however, Blutner
ultimately focuses on a localist scheme in which units represent
atomic propositions and connections represent biconditionals.)
Holographic neural network schemes (e.g., Manger et al. 1994;
Plate 2003) can also be viewed as global; in the simplest cases these
use one "giant neuron" that multiplies an input vector whose
components are complex numbers by a complex-valued matrix; a component
of the resultant complex-valued output vector, written in polar
coordinates as *re**i*th,
supplies a classification through the value of *th* and a
confidence level through the value of *r*. A distinctive
characteristic of such networks is their ability to classify or
reconstruct patterns from partial or noisy inputs.


The status of the subsymbolic hypothesis remains an issue for debate
and further research. Certainly it is unclear how symbolic approaches
could match certain characteristics of neural network approaches, such
as their ability to cope with novel instances and their graceful
degradation in the face of errors or omissions. On the other hand, some
neural network architectures for storing knowledge and performing
inference have been shown (or designed) to be closely related to "soft
logics" such as fuzzy logic (e.g.,
Kasabov 1996; Kecman 2001) or
"weight-annotated Poole systems" (Blutner 2004), suggesting the
possibility that neural network models of cognition may ultimately be
characterizable as implementations of such soft logics. Researchers
more concerned with practical advances than biologically plausible
modeling have also explored the possibility of hybridizing the
symbolic and subsymbolic approaches, in order to gain the advantages of
both (e.g., Sun 2001). A quite
formal example of this, drawing on ideas
by Dov Gabbay, is d'Avila Garcez (2004).


Finally, we should comment on the view expressed in some of the
cognitive science literature that mental representations of language
are primarily imagistic (e.g., Damasio 1994; Humphrey 1992). Certainly
there is ample evidence for the reality and significance of mental
imagery (Johnson-Laird 1983; Kosslyn 1994). Also creative thought
often seems to rely on visualization, as observed early in the 20th
century by Poincare (1913) and Hadamard (1945). But as was
previously noted, symbolic and imagistic representations may well
coexist and interact synergistically. Moreover, cognitive scientists
who explore the human language faculty in detail, such as Steven
Pinker (1994, 2007) or any of the representationalist or connectionist
researchers cited above, all seem to reach the conclusion that the
content derived from language (and the stuff of thought itself) is in
large part symbolic--except in the case of the eliminativists
who deny representations altogether. It is not hard to see, however,
how raw intuition might lead to the meanings-as-images hypothesis. It
appears that vivid *consciousness* is associated mainly with
the visual cortex, especially area V1, which is also crucially
involved in mental imagery (e.g., Baars 1997: chapter 6). Consequently
it is entirely possible that vast amounts of non-imagistic encoding
and processing of language go unnoticed, while any evoked imagistic
artifacts become part of our conscious experience. Further, the very
act of introspecting on what sort of imagery, if any, is evoked by a
given sentence may promote construction of imagery and awareness
thereof.


### 3.3 Statistical semantics



In its broadest sense, statistical semantics is concerned with
semantic properties of words, phrases, sentences, and texts, engendered
by their distributional characteristics in large text corpora. For
example, terms such as *cheerful, exuberant,* and *depressed*
may be
considered semantically similar to the extent that they tend to occur
flanked by the same (or in turn similar) nearby words. (For some
purposes, such as information retrieval, identifying labels of
documents may be used as occurrence contexts.) Through careful
distinctions among various occurrence contexts, it may also be
possible to factor similarity into more specific relations such as
synonymy, entailment, and antonymy. One basic difference between
(standard) logical semantic relations and relations based on
distributional similarity is that the latter are a matter of degree.
Further, the underlying abstractions are very different, in that
statistical semantics does not relate strings to the world, but only to
their contexts of occurrence (a notion similar to, but narrower than,
Wittgenstein's notion of meaning as use). However, statistical
semantics does admit elegant formalizations. Various concepts of
similarity and other semantic relations can be captured in terms of
vector algebra, by viewing the occurrence frequencies of an expression
as values of the components of a vector, with the components
corresponding to the distinct contexts of occurrence. In this way, one
arrives at a notion of semantics based on metrics and operators in
vector spaces, where vector operators can mimic Boolean operators in
various ways (Gardenfors 2000; Widdows 2004; Clarke 2012).


But how does this bear on meaning representation of natural language
sentences and texts? In essence, the representation of sentences
in statistical semantics consists of the sentences themselves. The idea
that sentences can be used directly, in conjunction with distributional
knowledge, as objects enabling inference is a rather recent and
surprising one, though it was foreshadowed by many years of work on
question answering based on large text corpora. The idea has gained
traction as a result of recent efforts to devise statistically based
algorithms for determining *textual
entailment*, a program pushed forward
by a series of Recognizing Textual Entailment (RTE) Challenges
initiated in 2005, organized by the PASCAL Network of Excellence, and
more recently by the National Institute of Standards and Technology
(NIST). Recognizing textual entailment requires judgments as to whether
one given linguistic string entails a second one, in a sense of
entailment that accords with human intuitions about what a person would
naturally infer (with reliance on knowledge about word meanings,
general knowledge such as that any person who works for a branch of a
company also works for that company, and occasional well-known specific
facts). For example, 
"John is a fluent French speaker" textually
entails 
"John speaks French",
while 
"The gastronomic capital of France is Lyon" does not entail that 
"The capital of France is Lyon". Some
examples are intermediate; e.g.,

"John was born in France" is
considered to heighten the probability that John speaks French, without
fully entailing it (Glickman and Dagan 2005). Initial results in the
annual competitions were poor (not far above the random guessing mark),
but have steadily improved, particularly with the injection of some
reasoning based on ontologies and on some general axioms about the
meanings of words, word classes, relations, and phrasal patterns
(e.g., de Salvo Braz et al. 2005).


It is noteworthy that the conception of sentences as meaning
representations echoes Montague's contention that language *is* logic. Of
course, Montague understood "sentences" as unambiguous syntactic trees.
But research in textual entailment seems to be moving towards a similar
conception, as exemplified in the work of Dagan et al. (2008),
where statistical entailment relations are based on syntactic trees,
and these are generalized to templates that may replace subtrees by
typed variables. Also Clarke (2012) proposes a very general
vector-algebraic framework for statistical semantics, where "contexts"
for sentences might include (multiple) parses and even (multiple)
logical forms for the sentences, and where statistical sentence
meanings can be built up compositionally from their proper parts. One
way of construing degrees of entailment in this framework is in terms
of the entailment probabilities relating each possible logical form of
the premise sentence to each possible logical form of the hypothesis in
question.


### 3.4 Which semantics in practice?



Having surveyed three rather different brands of semantics, we are
left with the question of which of these brands serves best in
computational linguistic practice. It should be clear from what has
been said above that the choice of semantic "tool" will depend on the
computational goals of the practitioner. If the goal, for example, is
to create a dialogue-based problem-solving system for circuit fault
diagnosis, emergency response, medical contingencies, or vacation
planning, then an approach based on logical (or at least symbolic)
representations of the dialogue, underlying intentions, and relevant
constraints and knowledge is at present the only viable option. Here it
is of less importance whether the symbolic representations are based on
some presumed logical semantics for language, or some theory of mental
representation--as long as they are representations that can be
reasoned with. The most important limitations that disqualify
subsymbolic and statistical representations of meaning for such
purposes are their very limited inferential reach and response
capabilities. They provide classifications or one-shot inferences
rather than reasoning chains, and they do not generate plans,
justifications, or extended linguistic responses. However, both neural
net techniques and statistical techniques can help to improve semantic
processing in dialogue systems, for example by disambiguating word
senses, or recognizing which of several standard plans is being
proposed or followed, on the basis of observed utterances or actions.


On the other hand, if the computational goal is to demonstrate
human-like performance in a biologically plausible (or biologically
valid!) model of some form of language-related behavior, such as
learning to apply words correctly to perceived objects or
relationships, or learning to judge concept similarity, or to assess
the tone (underlying sentiment) of a discourse segment, then symbolic
representations need not play any role in the computational modeling.
(However, to the extent that language is symbolic, and is a cognitive
phenomenon, subsymbolic theories must ultimately explain how language
can come about.) In the case of statistical semantics, practical
applications such as question-answering based on large textual
resources, retrieval of documents relevant to a query, or machine
translation are at present greatly superior to logical systems that
attempt to fully understand both the query or text they are confronted
with and the knowledge they bring to bear on the task. But some of the
trends pointed out above in trying to link subsymbolic and statistical
representations with symbolic ones indicate that a gradual convergence
of the various approaches to semantics is taking place.



## 4. Semantic interpretation


### 4.1 Mapping syntactic trees to logical forms



For the next few paragraphs, we shall take *semantic interpretation*
to refer to the process of deriving meaning representations from a word
stream, taking for granted the operation of a prior or concurrent
parsing phase. In other words, we are mapping syntactic trees to
logical forms (or whatever our meaning representation may be). Thus,
unlike interpretation in the sense of assigning external denotations to
symbols, this is a form of "syntactic semantics" (Rapaport 1995).


In the heyday of the proceduralist paradigm, semantic interpretation
was typically accomplished with sets of rules that matched patterns to
parts of syntactic trees and added to or otherwise modified the
semantic representations of input sentences. The completed
representations might either express facts to be remembered, or might
themselves be executable commands, such as formal queries to a database
or high-level instructions placing one block on another in a robot's
(simulated or real) world.


When it became clear in the early 1980s, however, that syntactic
trees could be mapped to semantic representations by using
compositional semantic rules associated with phrase structure rules in
one-to-one fashion, this approach became broadly favored over pure
proceduralist ones. In our earlier discussion in section 3.1) of
meaning representations within logicist frameworks, we already
foreshadowed the essentials of logical form computation. There we saw
sample interpretive rules for a small number of phrase structure rules
and vocabulary. The semantic rules, such as NP'
= Det'(N'), clearly indicate how logical
forms of lower-level constituents should be combined to yield those of
higher-level constituents. In the following figure, the sentence

"Thetis loves a mortal" has been interpreted by applying the
earlier set of lexical and interpretive rules to the nodes of the
phrase structure tree in a bottom-up, left-to-right sweep:




> 
> ![[a tree.  Parent is S-prime =
> NP-prime(VP) = [?]z[mortal(z) [?] loves(z)(Thetis)].  First node is
> NP-prime = Name-prime = lPP(Thetis) with a node of Name-prime =
> lPP(Thetis) which has a node Thetis (in bold).  Second node is
> VP-prime = lxNP-prime(lyV-prime(y)(x)) = lx([?]z[mortal(z) [?]
> loves(z)(x)]) with first a node of V-prime = loves which has a node
> loves (in bold) and with second a node of NP-prime =
> Det-prime(N-prime) lQ([?]z[mortal(z) [?] Q(z)]) which itself has a left
> node of Def-prime = lP lQ([?]z[P(z) [?] Q(z)]) which has a node of a (in
> bold) and a right node of N-prime = mortal which has a node of mortal
> (in bold)]](fig4.png)  
> 
> **Figure 4**: Semantic interpretation of the parse tree of Figure 1
> 


The interpretive rules are repeated at the tree nodes from 
section 3.1, and the result of applying
the combinatory rules (with lambda-conversions where possible) are
shown as well. As can be seen, the Montagovian treatment of NPs as
second-order predicates leads to some complications, and these are
exacerbated when we try to take account of quantifier scope
ambiguity. We mentioned Montague's use of multiple parses, the
Cooper-storage approach, and the unscoped-quantifier approach to this
issue in section 3.1. In the
unscoped-quantifier approach, with a relational interpretation of the
verb, the respective interpretations of the leaf nodes (words) in
Figure 4 would become *Thetis*,
l*y*l*x*(*loves*(*x, y*),
l*P* <<[?]*P*> >),
and *mortal*, and S' at the root would
become *loves*(*Thetis*,
<[?]*mortal*> ), to be scoped uniquely to
([?]*x*: *mortal*(*x*)
*loves*(*Thetis, x*)). It is easy to see that multiple
unscoped quantifiers will give rise to multiple permutations of
quantifier order when the quantifiers are brought to the sentence
level. Thus we will have multiple readings in sentences such as
"Every man loves a certain woman".



### 4.2 Subordinating the role of syntax



At this point we should pause to consider some interpretive methods
that do not conform with the above very common but not universally
employed syntax-driven approach. First, Schank and his collaborators
emphasized the role of lexical knowledge, especially primitive actions
used in verb decomposition, and knowledge about stereotyped patterns
of behavior in the interpretive process, nearly to the exclusion
of syntax. For example, a sentence beginning 
"John went ..." would lead to the generation of
a ptrans conceptualization (since go is lexically
interpreted in terms of ptrans), where John fills the
agent role and where a phrase interpretable as a location is expected,
as part of the configuration of roles that attach to
a ptrans act. If the sentence then continues as
"... *to the restaurant*", the expectation is
confirmed, and at this point instantiation of a restaurant script is
triggered, creating expectations about the likely sequence of actions
by John and other agents in the restaurant (e.g., Schank and Abelson
1977). These ideas had considerable appeal, and led to unprecedented
successes in machine understanding of some paragraph-length stories.
Another approach to interpretation that subordinates syntax to
semantics is one that employs domain-specific semantic grammars (Brown
and Burton 1975). While these resemble context-free syntactic grammars
(perhaps procedurally implemented in ATN-like manner), their
constituents are chosen to be meaningful in the chosen application
domain. For example, an electronics tutoring system might employ
categories such as *measurement, hypothesis*,
or *transistor* instead of NP, and *fault-specification*
or *voltage-specification* instead of VP. The importance of
these approaches lay in their recognition of the fact that knowledge
powerfully shapes our ultimate interpretation of text and
dialogue, enabling understanding even in the presence of noisy,
flawed, and partial linguistic input. Nonetheless, most of the 
NL understanding community since the 1970s has treated syntactic
parsing as an important aspect of the understanding process, in part
because modularization of this complex process is thought to be
crucial for scalability, and in part because of the very plausible
Chomskian contention that human syntactic intuitions operate reliably
even in the absence of clear meaning, as in his famous sentence
"Colorless green ideas sleep furiously".


Statistical NLP has only recently begun to be concerned with
deriving interpretations usable for inference and question answering
(and as pointed out in the previous subsection, some of the literature
in this area assumes that the NL text itself can and should be used
as the basis for inference). However, there have been some noteworthy
efforts to build statistical semantic parsers that learn to produce
LFs after training on a corpus of LF-annotated sentences, or a corpus
of questions and answers (or other exchanges) where the learning is
"grounded" in a database or other supplementary models. We
will mention examples of this type of work, and comment on its
prospects, in section 8.


### 4.3 Coping with semantic ambiguity and underspecification



We noted earlier that language is potentially ambiguous at all
levels of syntactic structure, and the same is true of semantic
content, even for syntactically unambiguous words, phrases and
sentences. For example, words like *bank*,
*recover*, and *cool* have
multiple meanings even as members of the same lexical category; nominal
compounds such as *ice bucket, ice
sculpture, olive oil,* or *baby
oil* leave unspecified the underlying relation between the
nominals (such as constituency or purpose). At the sentential level,
even for a determinate parse there may be quantifier scope ambiguities
("Every man admires a certain woman"--*Rosa Parks* vs. *his mother*); and habitual and generic
sentences often involve temporal/atemporal ambiguities
("Racehorses are (often) skittish"), among others.


Many techniques have been proposed for dealing with the various
sorts of semantic ambiguities, ranging from psychologically
motivated principles, to knowledge-based methods,
heuristics, and statistical approaches. Psychologically
motivated principles are exemplified by Quillian's spreading
activation model (described earlier) and the use of *selectional
preferences* in word sense disambiguation. For example,
in 
"The job took five hours," *took* might be
disambiguated to the sense of taking up time because that sense of the
verb prefers a temporal complement, and *job* might be
disambiguated to *task* (rather than, say, *occupation*)
because of the direct associative link between the concept of a task
and its time demands. Examples of knowledge-based disambiguation would
be the disambiguation of *ice sculpture* to a constitutive
relation based on the knowledge that sculptures may be carved or
constructed from solid materials, or the disambiguation of *a man
with a hat* to a *wearing*-relation based on the knowledge
that a hat is normally worn on the head. (The possible meanings may
first be narrowed down using heuristics concerning the limited types
of relations typically indicated by nominal compounding or by*with*-modification.) Heuristic principles used in scope
disambiguation include *island constraints* (quantifiers such
as *every* and *most* cannot expand their scope beyond
their local clause) and differing wide-scoping tendencies for
different quantifiers (e.g., *each* is apt to assume wider
scope than *some*). Statistical approaches typically extract
various features in the vicinity of an ambiguous word or phrase that
are thought to influence the choice to be made, and then make that
choice with a classifier that has been trained on an annotated text
corpus. The features used might be particular nearby words or their
parts of speech or semantic categories, syntactic dependency
relations, morphological features, etc.. Such techniques have
the advantage of learnability and robustness, but ultimately will
require supplementation with knowledge-based techniques. For example,
the correct scoping of quantifiers in contrasting sentence pairs such
as



> 
> 
> (4.1) **Every** child at the picnic was roasting
> a wiener.
> (4.2)
> **Every** child at the picnic was watching **a** hot
> air balloon overhead,
> 
> 


seems to depend on world knowledge in
a way unlikely to be captured as a word-level statistical regularity.


Habitual and generic sentences present particularly challenging
disambiguation problems, as they may involve temporal/atemporal
ambiguities (as noted), and in addition may require augmentation with
quantifying adverbs and constraints on quantificational domains
missing from the surface form. For example,



> 
> 
> (4.3)
> Racehorses are (often) skittish when they are
> purebred


without the quantifying adverb *often* is unambiguously
atemporal, ascribing enduring skittishness to purebred racehorses
*in general*. (Thus *in general* appears to be the
implicit default adverbial.) But when the quantifying adverb is
present, the sentence admits both an atemporal reading according to
which many purebred racehorses are characteristically skittish, as
well as a temporal reading to the effect that purebred racehorses
*in general* are subject to frequent episodes of
skittishness. If we replace *purebred* by *at the starting
gate*, then only the episodic reading of *skittish*
remains available, while *often* may quantify over racehorses,
implying that many are habitually skittish at the starting gate, or it
may quantify over starting-gate situations, implying that racehorses
in general are often skittish in such situations; furthermore, making
formal sense of the phrase *at the starting gate* evidently
depends on knowledge about horse racing scenarios. 


The interpretive challenges presented by such sentences are (or should
be) of great concern in computational linguistics, since much of
people's general knowledge about the world is most naturally expressed
in the form of generic and habitual sentences. Systematic
ways of interpreting and disambiguating such sentences would
immediately provide a way of funneling large amounts of knowledge into
formal knowledge bases from sources such as lexicons, encyclopedias,
and crowd-sourced collections of generic claims such as those in Open
Mind Common Sense (e.g., Singh
et al. 2002; Lieberman et al. 2004; Havasi et
al. 2007). Many theorists assume that the logical forms of such
sentences should be tripartite structures with a quantifier that
quantifies over objects or situations, a restrictor that limits the
quantificational domain, and a nuclear scope (main clause) that makes
an assertion about the elements of the domain (e.g., see Carlson
2011; Cohen 2002; or Carlson & Pelletier
1995). The challenge lies in specifying a mapping from surface
structure to such a logical form. While many of the principles
underlying the ambiguities illustrated above are reasonably well
understood, general interpretive algorithms are still lacking. It
appears that such algorithms will involve stepwise elaboration of an
initially incomplete, ambiguous logical form, rather than a
straightforward syntax-semantics transduction, since the features on
which the correct formalization depends transcend syntax: They include
ones such as Carlson's individual-level/stage-level distinction among
verb phrases and his object-level/kind-level distinction among verb
arguments (Carlson 1977, 1982), as well as pragmatic features such as
the given/new distinction (influenced by phrasal accent), lexical
presuppositions, linguistic context, and background knowledge.


## 5. Making sense of text


The dividing line between semantic interpretation (computing and
disambiguating logical forms) and discourse understanding--making
sense of text--is a rather arbitrary one. However, heavily context-
and knowledge-dependent aspects of the understanding process, such as
resolving anaphora, interpreting context-dependent nominal compounds,
filling in "missing" material, determining implicit temporal and causal
relationships (among other "coherence relations"), interpreting loose
or figurative language and certainly, integrating linguistically
derived information with preexisting knowledge are generally counted as
aspects of discourse processing.


### 5.1 Dealing with reference and various forms of "missing material"


Language has evolved to convey information as efficiently as
possible, and as a result avoids lengthy identifying descriptions and
other lengthy phrasings where shorter ones will do. One aspect of this
tendency towards "shorthand" is seen in *anaphora*,
the phenomenon of coreference between an earlier, potentially more
descriptive NP and a later anaphoric pronoun or definite NP (with a
determiner like *the* or
*these*). (The reverse sequencing, *cataphora*, is seen
occasionally as well.) Coreference is yet another source of ambiguity
in language, scarcely noticeable by human language users (except in
ambivalent cases such as "When Flight 77 hit the Pentagon's
wall, it disintegrated"), but problematic for machines.


Determining the (co)referents of anaphors can be approached in a
variety of ways, as in the case of semantic disambiguation. Linguistic
and psycholinguistic principles that have been proposed include
*gender* *and number agreement* of coreferential terms,
*C-command* principles (e.g., an anaphor must be a pronoun if
its referent is a sibling of one of its ancestors in the parse tree),
(*non*)*reflexive constraints* (e.g., the subject and
object cannot be coreferential in a simple clause such as

"**John** blamed **him** for the accident"),
recency/salience (more recent/salient referents are preferred), and
*centering* (the most likely term to be pronominalized in an
utterance is the "center of attention"). An early
heuristic algorithm that employed several features of this type to
interpret anaphors was that of Hobbs (1979). But selectional
preferences are important as well. For example, in the sentence
"He bumped against **the sauce boat** containing **the
raspberry syrup**, spilling **it**," the pronoun can be
determined to be coreferential with *the raspberry syrup*
rather than *the sauce boat* because
*spill* prefers a liquid (or loose aggregate) as its
object. With the alternative continuation, "... knocking
**it** over," the choice of coreferent would be reversed,
because *knock over* prefers something solid and upright as its
object. More subtle world knowledge may be involved as well, as in
Terry Winograd's well-known example, "**The city council**
refused **the women** a parade permit because **they**
feared/advocated violence," where
*they* may refer to the city council or the women, depending on
the choice of verb and the corresponding stereotypes that are
evoked. Another complication concerns reference to collections of
entities, related entities (such as parts), propositions, and events
that can become referents of pronouns (such as *they, this,*
and *that*) or of definite NPs (such as *this situation*
or *the door* (*of the house*)) without having appeared
explicitly as a noun phrase. Like other sorts of ambiguity,
coreference ambiguity has been tackled with statistical techniques.
These typically take into account factors like those mentioned, along
with additional features such as antecedent animacy and prior
frequency of occurrence, and use these as probabilistic evidence in
making a choice of antecedent (e.g., Haghighi & Klein 2010).
Parameters of the model are learned from a corpus annotated with
coreference relations and the requisite syntactic analyses.


Coming back briefly to nominal compounds of form N N, note that
unlike conventional compounds such as *ice bucket* or *ice
sculpture*--ones approachable using an enriched lexicon,
heuristic rules, or statistical techniques--some compounds can
acquire a variety of meanings as a function of context. For
example, *rabbit guy* could refer to entirely different things
in a story about a fellow wearing a rabbit suit, or one about a rabbit
breeder, or one about large intelligent leporids from outer
space. Such examples reveal certain parallels between compound nominal
interpretation and anaphora resolution: At least in the
more difficult cases, N N interpretation depends on previously seen
material, and on having understood crucial aspects of that previous
material (in the current example, the concepts of wearing a rabbit
suit, being a breeder of rabbits, or being a rabbit-like creature). In
other words N N interpretation, like anaphora resolution, is
ultimately knowledge-dependent, whether that knowledge comes from
prior text, or from a preexisting store of background knowledge. A
strong version of this view is seen in the work of Fan et
al. (2009), where it is assumed that in technical contexts, even
many seemingly conventional compounds require knowledge-based
elaboration. For example, in a chemistry context, *HCL
solution* is assumed to require elaboration into something
like: *solution whose base is a chemical whose basic structural
constituents are HCL molecules*. Algorithms are provided (and
tested empirically) that search for a relational path (subject to
certain general constraints) from the modified N to the modifying N,
selecting such a relational path as the meaning of the N N
compound. As the authors note, this is essentially a
spreading-activation algorithm, and they suggest more general
application of this method
 (see section 5.3 on integrated interpretive
methods).


While anaphors and certain nominal compounds can be regarded as
abbreviated encodings of semantic content, other forms of
"shorthand" leave out semantically essential material
altogether, requiring the reader or hearer to fill it in. One
pervasive phenomenon of this type is of course *ellipsis*, as
illustrated earlier in sentences
 (2.5) and (2.6), or by the following
examples.



> 
> (5.1)  Shakespeare made up
> words, and so can you. 
> 
>  (5.2) Felix is under more pressure than I am.
> 
> 


In (5.1), so is a place-holder for the VP make up words (in an
inverted sentence), and (5.2) tacitly contains a final predicate
something like *under amount x of pressure*, where that amount
*x* needs to be related to the (larger) amount of pressure
experienced by Felix. Interpreting ellipsis requires filling in of
missing material; this can often be found at the surface level as a
sequence of consecutive words (as in the gapping and bare ellipsis
examples 2.5 and 2.6), but as seen in (5.1) and (5.2), may
instead (or in addition) require adaptation of the imported material
to fit semantically into the new context. Further complications arise
when the imported material contains referring expressions, as in the
following variant of (5.2):



> 
> (5.2') 
>  Felix is under more pressure from his boss than I
> am.
> 


Here the missing material may refer either to Felix's boss
or *my* boss (called the *strict* and *sloppy*
reading respectively), a distinction that can be captured by regarding
the logical form of the antecedent VP as containing only one, or two,
occurrences of the lambda-abstracted subject variable, i.e.,
schematically,



>  
> l*x*[*x is under more pressure from Felix's boss*],  
>  versus   
> 
> l*x*[*x is under more pressure from x's boss*].
> 
> 
> 


The two readings can be thought of as resulting respectively from
scoping *his boss* first, then
filling in the elided material, and the
reverse ordering of these operations (Dalrymple et al. 1991; see also
Crouch 1995; Gregory and Lappin 1997). Other challenging forms of
ellipsis are event ellipsis, as in (5.3) (where *forgot* stands for
*forgot to bring*), entirely
verbless sentences such as (5.4) and (5.5),
and subjectless, verbless ones like (5.6) and (5.7):



> 
> (5.3) I forgot the keys
> 
> (5.4) Hence this proposal 
> (5.5) Flights from Rochester to Orlando, May 28?
> 
> (5.6) What a pity.
> (5.7) How about the Delta
> flight instead?
> 
> 


In applications these and some other forms of ellipsis are handled,
where possible, by (a) making strong use of domain-dependent
expectations about the types of information and speech acts that are
likely to occur in the discourse, such as requests for flight
information in an air travel adviser; and (b) interpreting utterances
as providing augmentations or modifications of domain-specific
knowledge representations built up so far. Corpus-based approaches to
ellipsis have so far focused mainly on identifying instances of VP
ellipsis in text, and finding the corresponding antecedent material, as
problems separate from that of computing correct logical forms (e.g.,
see Hardt 1997; Nielsen 2004).


Another refractory missing-material phenomenon is that of *implicit
arguments*. For example, in the sentence



> 
> (5.8) Some carbon monoxide
> leaked into the car from the exhaust, but its
> concentration was too low to pose any hazard,
> 


the reader needs to conceptually expand *its concentration*
into *its concentration in the air in the interior of the car*,
and *hazard* into
*hazard for occupants of the car*.
In this example, lexical knowledge to
the effect that concentration (in the chemical sense) refers to
the concentration of some substance in some medium could at least
provide the "slots" that need to be filled, and a similar comment
applies in the case of *hazard*.
However, not all of the fillers for
those slots are made explicitly available by the text--the carbon
monoxide referred to provides one of the fillers, but the air in the
interior of the car, and potential occupants of the car (and that they
rather than, say, the upholstery would be at risk) are a matter of
inference from world knowledge.


Finally, another form of shorthand that is common in certain
contexts is *metonymy*, where a
term saliently related to an intended
referent stands for that referent. For example, in an airport context,



> 
> (5.9) Is this **flight 574**?
> 
> 


might stand for 
"Is this **the departure lounge for flight 574**?"
Similarly, in appropriate contexts *cherry*
can stand for *cherry ice
cream*, and *BMW* can
stand for *BMW's stock market index:*



> 
> (5.10) I'd like two scoops
> of **cherry**.
> (5.11) **BMW** rose 4 points.
> 
> 


Like other types of underspecification, metonymy has been
approached both from knowledge-based and corpus-based
perspectives. Knowledge that can be brought to bear includes
selectional preferences (e.g., companies in general do not literally
rise), lexical concept hierarchies (e.g., as provided by
WordNet), generic knowledge about the types of metonymy relations
commonly encountered, such as *part-for-whole, place-for-event,
object-for-user, producer-for-product,* etc. (Lakoff and Johnson
1980), rules for when to conjecture such relations (e.g., Weischedel
and Sondheimer 1983), named-entity knowledge, and knowledge about
related entities (e.g., a company may have a stock market index, and
this index may rise or fall) (e.g., Bouaud et al. 1996; Onyshkevych
1998). Corpus-based methods (e.g., see Markert and Nissim 2007) often
employ many of these knowledge resources, along with linguistic and
statistical features such as POS tags, dependency paths and
collocations in the vicinity of a potential metonym. As for other
facets of the interpretive process (including parsing), use of deep
domain knowledge for metonym processing can be quite effective in
sufficiently narrow domains, while corpus-based, shallow methods scale
better to broader domains, but are apt to reach a performance plateau
falling well short of human standards.


### 5.2 Making connections


Text and spoken language do not consist of isolated sentences, but
of connected, interrelated utterances, forming a coherent
whole--typically, a temporally and causally structured narrative,
a systematic description or explanation, a sequence of instructions,
or a structured argument for a conclusion (or in dialogue, as
discussed later, question-answer exchanges, requests followed by
acknowledgments, mixed-initiative planning, etc.).



This structure is already apparent at the level of pairs of consecutive
clauses, such as



> 
> (5.12) John looked out at the sky. It was dark
> with
> thunderclouds.
> (5.13) John looked out at the sky, and decided to
> take along
> his umbrella.
> 
> 



In (5.12), we understand that John's looking at the sky *temporally
overlaps t*he presence of the dark clouds in the sky (i.e., the
dark-cloud situation at least contains the end of the looking event).
At a deeper level, we also understand that John *perceived* the
sky to be dark with thunderclouds, and naturally assume that John took
the clouds to be harbingers of an impending storm, as *we
ourselves* would. In (5.13), the two clauses appear to
report *successive* events and furthermore, the first event is
understood to have led causally to the second--John's decision
was driven by whatever he saw upon looking at the sky; and based on
our knowledge of weather and the function of umbrellas, and the fact
that "everyone" possesses that knowledge, we further infer
that John perceived potential rainclouds, and intended to fend off any
rain with his umbrella in an imminent excursion.


The examples show that interpreting extended multi-clausal
discourses depends on both narrative conventions and world knowledge;
(similarly for descriptive, instructional or argumentative text) . In
particular, an action sentence followed by a static observation, as in
(5.12), typically suggests the kind of action-situation overlap we
noted, and successively reported actions or events, as in (5.13),
typically suggest temporal sequencing and perhaps a causal connection,
especially if one of the two clauses is *not* a volitional action. These
suggestive inferences presumably reflect the narrator's adherence to a
Gricean principle of orderliness, though such an observation is little
help from a computational perspective. The concrete task is to
formulate coherence principles for narrative and other forms of
discourses and to elucidate, in a usable form, the particular
syntactico-semantic properties at various levels of granularity that
contribute to coherence.


Thus various types of rhetorical or coherence relations (between
clauses or larger discourse segments) have been proposed in the
literature, e.g., by Hobbs (1979), Grosz & Sidner (1986), and Mann
& Thompson (1988). Proposed coherence relations are ones like
elaboration, exemplification, parallelism, and contrast. We defer
further discussion of rhetorical structure
to section 6 (on language generation).


### 5.3 Dealing with figurative language



> 
> "[I'm] behind the eight ball, ahead
> of the curve, riding the wave, dodging the bullet and pushing the
> envelope. I'm on point, on task, on message and off drugs... I'm
> in the moment, on the edge, over the top and under the radar. A
> high-concept, low-profile, medium-range ballistic missionary."
> -George Carlin
> ("Life is worth losing", first broadcast on HBO, November
> 5, 2005)
> 
> 
> 


We have already commented on processing metonymy, which is
conventionally counted as a figure of speech--a word or phrase
standing for something other than its literal meaning. However, while
metonymy is essentially an abridging device, other figurative modes,
such as metaphor, simile, idioms, irony, personification, or hyperbole
(overstatement) convey meanings, especially connotative ones, not
easily conveyed in other ways. We focus on metaphor here, as it is in
a sense a more general form of several other tropes. Moreover, it has
received the most attention from computational linguists, because the
argument can be made that metaphor pervades language, with no sharp
demarcation between literal and metaphorical usage (e.g., Wilks 1978;
Carbonell 1980; Lakoff and Johnson 1980; Barnden 2006). For example,
while "The temperature dropped" can be viewed as involving
a sense of
*drop* that is synonymous with *decrease*, it can also
be viewed as a conventional metaphor comparing the decreasing
temperature to a falling object. As a way of allowing for examples of
this type, Wilks offered a processing paradigm in which selectional
constraints (such as a physical-object constraint on the subject
of *drop*) are treated as mere preferences rather than firm
requirements.


However, processing metaphor requires more than relaxation of
preferences; it is both context-dependent and profoundly
knowledge-dependent. For example,



> 
> (5.14) He threw in the towel
> 
> 
> 



can be a literal description of a mundane act in a laundromat setting,
a literal description of a symbolic act by a boxer's handler, or a
stock metaphor for conceding defeat in any difficult endeavor. But to
grasp the metaphorical meaning fully, including the connotation of a
punishing, doomed struggle, requires a vivid conception of what a
boxing match is like.


In approaching metaphor computationally, some authors, e.g., Dedre
Gentner (see Falkenhainer et al.
1989), have viewed it as depending on
shared properties and relational structure (while allowing for
discordant ones), directly attached to the concepts being compared. For
example, in comparing an atom to the solar system, we observe a
*revolves-around* relation between electrons and the nucleus on
the one hand and between planets and the sun on the other. But others
have pointed out that the implicit comparison may hinge on properties
reached only indirectly. In this view, finding a metaphor for a
concept is a process of moving away from the original concept in a
knowledge network in a series of steps, each of which transforms some
current characteristic into a related one. This is the process termed
"slippage" by Hofstadter et al. (1995). Others (e.g.,
Martin 1990, drawing on Lakoff and Johnson 1980) emphasize preexisting
knowledge of conventional ways of bridging metaphorically from one
concept to another, such as casting a nonliving thing as a living
thing.


In view of the dependence of metaphor on context and extensive
knowledge, and the myriad difficulties still confronting all aspects
of language understanding, it is not surprising that no general system
for processing metaphor in context exists, let alone for using
metaphor creatively. Still, Martin's MIDAS program was able to
interpret a variety of metaphors in the context of a language-based
Unix adviser, relying on knowledge about the domain and about
metaphorical mapping, hand-coded in the KODIAK knowledge
representation language. Also, several other programs have
demonstrated a capacity to analyze or generate various examples of
metaphors, including the Structure Mapping Engine (SME) (Falkenhainer
et al. 1989), Met\* (Fass 1991), ATT-Meta (Barnden 2001), KARMA
(Narayanan 1997) and others. More recently, Veale and Hao (2008)
undertook an empirical study of a slippage-based approach to metaphor,
using attributes collected from WordNet and the web. In a similar
spirit, but taking SME as his inspiration, Turney (2008) implemented a
"Latent Relation Mapping Engine" (LRME) to find the best
mapping between the elements of two potentially comparable
descriptions (of equal size); the idea is to use web-based
co-occurrence statistics to gauge not only the attribute similarity of
any two given concepts (such as *electron* and *planet*)
but also the relational similarity of any two given pairs of concepts
(such as *electron:nucleus* and *planet:sun*), using
these as metrics in optimizing the mapping.


### 5.4 Integrated methods



Obviously, the many forms of syntactic, semantic, and pragmatic
ambiguity and underspecification enumerated in the preceding sections
interact with one another and with world knowledge. For example, word
sense disambiguation, reference resolution, and metaphor interpretation
are interdependent in the sentence



> 
> (5.15) The Nebraska Supreme Court
> threw out the chair because it deemed electrocution to be a cruel form
> of capital punishment.
> 


Note first of all that *it* could refer syntactically to
*the Nebraska Supreme Court* or to *the chair,* but
world knowledge rules out the possibility of a neuter-gendered chair
manifesting a mental attitude. Note as well that if *it* is
replaced by *he*, then *the chair* is
reinterpreted as a person and becomes the referent of the pronoun; at
the same time, *threw out* is then reconstrued as a metaphor
meaning *removed from office* (with an implication of
ruthlessness).


Thus it seems essential to find a uniform framework for jointly
resolving all forms of ambiguity and underspecification, at least to
the extent that their resolution impacts inference. Some frameworks
that have been proposed are *weighted abduction, constraint
solving,* and 
*"loose-speak" interpretation*. Weighted
abduction (Hobbs et al. 1993) is based on the idea that the
task of the hearer or reader is to *explain* the word sequence
comprising a sentence by viewing the meaning of that sentence as
a logical consequence of general and contextual knowledge along with
some assumptions, to be kept as "lightweight" as possible. The
constraint-solving approach views syntax, semantics, pragmatics,
context, and world knowledge as supplying *constraints* on
interpretations that need to be satisfied simultaneously. Often
constraints are treated as defeasible, or ranked, in which case the
goal is to minimize constraint violations, particularly of relatively
strong constraints. (There is a connection here to
*Optimality Theory* in cognitive language modeling.)
Loose-speak interpretation (Fan et al. 2009, cited previously
in connection with nominal compound interpretation) sets aside
syntactic ambiguity but tries to deal with pervasive semantic
looseness in the meanings of nominal compounds, metonymy, and other
linguistic devices. It does so by expanding semantic triples (from the
preliminary logical form) of type <*Class*1,
relation, *Class*2> , where the relation cannot
properly relate the specified classes, into longer chains containing
that relation and terminating at those classes. Finding such chains
depends on background knowledge about the relations that are possible
in the domain of interest.


#### Prospects


The methods just mentioned have been applied in restricted tasks,
but have not solved the problem of comprehensive language
interpretation. They all face efficiency problems, and--since they
all depend on a rich base of linguistic and world knowledge--the
knowledge acquisition bottleneck. We comment on the efficiency issue
here, but leave the discussion of knowledge acquisition to 
section 8.


In view of the speed with which people disambiguate and comprehend
language, one may surmise that these processes more closely resemble
fitting the observed texts or utterances to familiar patterns, than
solving complex inference or constraint satisfaction problems. For
example, in a sentence such as



> 
> (5.16) He dropped the cutting board on the glass
> and it
> didn't break,
> 
> 


the pronoun is understood to refer to the glass, even though world
knowledge would predict that the glass broke, whereas the cutting board
did not. (The idea that communication focuses on the unexpected is of
no help here, because the referent remains unchanged if we change
*didn't break* to *broke*.) This would be expected if
the interpretive
process simply found a match between the concept of a fragile object
breaking and the glass breaking (regardless of the exact logical
structure), and used that match in choosing a referent. The
processing of the example from Winograd,
 in section 5.1, concerning
refusal of a parade permit to a group of women, may similarly depend in
part on the familiarity of the idea that people who (seek to) parade
may advocate some cause. Note that in



> 
> (5.17) The city council granted the women a
> parade permit
> because they did not advocate
> violence
> 
> 
> 


the women are still preferred as the referent of *they*, even though it
is generally true that stalwarts of society, such as city councillors,
do not advocate violence.


If disambiguation and (at least preliminary) interpretation in
language understanding turn out to be processes guided more by learned
patterns than by formalized knowledge, then methods similar to those
used in feature-based statistical NLP may be applicable to their
effective mechanization.


## 6. Language generation


Because language generation is a purposeful activity motivated by
internal goals, it is difficult to draw a boundary between
goal-directed thinking and the ensuing production of linguistic output.
Often the process is divided into *content
planning, microplanning,
surface realization*, and *physical
presentation*. While the last three of
these stages can be thought of as operating (in the order stated) on
relatively small chunks of information (e.g., resulting in one or two
sentences or other utterance types), content planning is often
regarded as a continual process of goal-directed communicative
planning, which successively hands over small clusters of ideas to the
remaining stages for actual generation when appropriate. We discuss the
latter transduction first, in order to highlight its relationship to
understanding.


The transduction of a small set of internally represented ideas into
written or oral text is in an obvious sense the inverse of the
understanding process, as we have outlined it in the preceding sections
2-5. In other words, starting from a few internally represented ideas
to be communicated, we need to proceed to an orderly linear arrangement
of these ideas, to a surface-oriented logical form that is concise and
nonrepetitive and appropriately indexical (e.g., in the use of *I, you,
here, now*, and referring expressions), and finally to an actual
surface
realization and physical presentation of that realization as spoken or
written text. Most or all of the kinds of knowledge involved in
understanding naturally come into play in generation as well--whether
the knowledge is about the structure of words and phrases, about the
relationship between structure and meaning representation, about
conventional (or creative) ways of phrasing ideas, about discourse
structure and relations, or about the world.


Despite this inverse relationship, language generation has
traditionally received less attention from computational linguists than
language understanding, because if the content to be verbalized is
available in an unambiguous, formal representation, standard output
templates can often be used for generation, at least in sufficiently
narrow domains. Even for unrestricted domains, the transduction from an
explicit, unambiguous internal semantic representation to a word
sequence is much less problematic than reconstruction of an explicit
semantic representation from an ambiguous word sequence. A similar
asymmetry holds at the level of speech recognition and generation,
accounting for the fact that serviceable speech generators (e.g.,
reading machines for the blind) have been available much longer (since
about 1976) than serviceable speech recognizers (appearing around 1999).


The microplanning process that leads from a few internal ideas to a
surface-oriented, indexical representation typically starts by
identifying "chunks" expected to be verbalized as
particular types of syntactic constituents, such as NPs, VPs or
PPs. This is often followed by making choices of more surface-oriented
concepts (or directly, lexical heads) in terms of which the chunks
will be expressed. The nature of these processes depends very much on
the internal representation. For example, if the representation is
framed in terms of very abstract primitives, thematic relations, and
attribute-value descriptions of entities, then the chunks might be
sets of thematic relations centered around an action, and sets of
salient attributes of entities to be referred to. If the internal
representation is instead more language-like, then chunks will be
relatively small, often single propositions, and the lexical choice
process will resemble internal paraphrasing of the logical forms. If
more than one idea is being verbalized, ordering decisions will need
to be made. For example, reporting that a bandit brandishing a gun
entered a local liquor store might be reported in that order, or as
"A bandit entered a local liquor store, brandishing a
gun". In dialogue, if a contribution involves both supplying and
requesting information, the request should come last. In other cases
transformations to more concise forms may be needed to bring the
represented ideas stylistically closer to surface form. For example,
from logical forms expressing that *John ate a burrito containing
chicken meat* and *Mary ate a burrito containing chicken
meat*, a more compact surface-oriented LF might be generated to
the effect that *John and Mary each had a chicken
burrito*. More subtle stylistic choices might be made as
well--for example, in casual discourse, *eating* might be
described as *polishing off* (assuming that the internal
representation allows for such surface-oriented distinctions).
Furthermore, as already mentioned, a surface-oriented LF needs to
introduce contextually appropriate referring expressions such as
definite descriptions and pronouns, in conformity with pragmatic
constraints on the usage of such expressions.


The above outline is simplified in that it neglects certain
subtleties of discourse and context. A sentence or other utterance
type generally involves both *new* and *old* (*given,
presupposed*) information, and furthermore, some of the concepts
involved may be more strongly focused than others. For example, in the
sentence "The item you ordered costs **ninety** dollars, not
nine," the existence and identity of the item, and the fact that
it was ordered, are presumed to be part of the common ground in the
current context (old), and so is the addressee's belief that the cost
of the item is $9; only the corrected cost of $90 is new
information. The emphasis on *ninety* draws attention to the
part of the presumed belief that is being corrected. Thus it is not
only conceptual content that needs to be available to the
microplanning stage, but also indications as to what is new and what
is old, and what aspects are to be stressed or focused. The planner
needs at least to apply knowledge about the phrasing of new and old
information (e.g., the use of indefinite vs. definite NPs), about the
lexical presuppositions and implicatures of the items used (e.g., that
*succeeding* presupposes *trying*, that *regretting
that ph* presupposes that *ph*, or that *some*
implicates *not all*), about the presuppositions of stress
patterns, and about focusing devices (such as stress and
topicalization). The effect of applying these sorts of pragmatic
knowledge will be to appropriately configure the surface-oriented LFs
that are handed off to the surface realizer, or, for pragmatic
features that cannot be incorporated into the LFs, to annotate the LFs
with these features (e.g., stress marking).


The penultimate step is surface realization, using knowledge about the
syntax-semantics interface. In systems for restricted domains, this
knowledge might consist of heuristic rules and templates (perhaps tree
schemas) for verbalizing LFs. More broadly-aimed generators might make
use of *invertible* grammars,
ones formulated in rule-to-rule fashion and
allowing transduction from logical forms to surface forms in much the
same way as the "forward" transduction from surface phrase structure to
logical form. Sophisticated generators also need to take account of
pragmatic annotations, such as stress, mentioned above. Finally, the
linguistically expressed content needs to be physically presented as
spoken or written text, with due attention to articulation, stress, and
intonation, or, for written text, punctuation, capitalization, choice
of *a* or *an* as indefinite article, italics, line breaks, and so on.


Returning now to content planning, this process may be expansive or
very limited in scope; for example, it may be aimed at providing
details of a complex object, set of events, or argument, or it may seek
to present no more than a single fact, greeting or acknowledgment. We
leave discussion of the strongly interactive type of content planning
needed for dialogue to the following section, while we comment here on
the more expansive sorts of text generation. In this case the
organization of the information to be presented is the central concern.
For example, the events of a narrative or the steps of a procedure
would generally be arranged chronologically; arguments for a conclusion
might be arranged so that any subarguments intended to buttress the
presumptions of that step (immediately) precede it; descriptions of
objects might proceed from major characteristics and parts to details.


An early method of producing well-organized, paragraph-length
descriptions and comparisons was pioneered in the TEXT system of
McKeown (1985), which used ATN-like organizational schemas to sequence
sections of the description of a type of object, such as the object's
more general type, its major parts and distinctive attributes, and
illustrative examples. Later work by Hovy (1988) and Moore and Paris
(1988) tied content planning more closely to communicative goals by
relying on rhetorical structure theory (RST) (Mann and Thompson
1987). RST posits over 20 possible coherence relations between spans
of text (usually adjacent). For example, a statement of some claim
may be followed by putative evidence for the claim, thus establishing
an *evidence* relation between the claim (called the
*nucleus*, because it is the main point) and the cited evidence
(called a *satellite* because of its subsidiary role). Another
example is the *volitional result* relation, where the nuclear
text span describes a situation or event of interest, and the
satellite describes a deliberate action that caused the situation or
event. Often these relations are signalled by discourse markers (cue
words and phrases), such as *but, when, yet,* or *after
all*, and it is important in text generation to use these markers
appropriately. For example, the use of *when* in the following
sentence enhances coherence,



> 
> (6.1) John
> hung up the phone when the caller asked for his social
> security number,
> 


by signalling a possible volitional result relation. Text spans
linked by rhetorical relations may consist of single or multiple
sentences, potentially leading to a recursive (though not necessarily
strictly nested) structure. Rhetorical relations can serve
communicative goals such as concept comprehension (e.g., via
elaboration of a definition), belief (via presentation of evidence),
or causal understanding (e.g., via a volitional result relation, as in
(6.1)), and in this way tighten the connection between content
planning and communicative goals.


## 7. Making sense of, and engaging in, dialogue



> "We
> can ask just how it is that rhetoric somehow moves us ...
> Aristotle locates the essential nature of rhetorical undertakings in
> the ends sought rather than in the purely formal properties."
> 
> -Daniel N. Robinson, *Consciousness and Mental Life,* (2007:
> 171-2)
> 
> 
> 



Dialogue is interactive goal-directed (purposive) behavior, and in that
sense the most natural form of language. More than in narrative or
descriptive language, the flow of surface utterances and speaker
alternation reflect the interplay of underlying speaker goals and
intentions. By themselves, however, utterances in a dialogue are
ambiguous as to their purpose, and an understanding of the discourse
context and the domain of discourse are required to formulate or
understand them. For example,



> 
> (7.1) Do you know what day this is?
> 
> 
> 


could be understood as a request for an answer such as

"Thursday, June 24", as a reminder of the importance of the
day, or as a test of the addressee's mental alertness.


The immediate goal of such an utterance is to change the mental state
(especially beliefs, desires and intentions) of the hearer(s), and
*speech act theory* concerns the
way in which particular types of speech
acts effect such changes, directly or indirectly (Austin 1962; Grice
1968; Searle 1969). To choose speech acts sensibly, each participant
also needs to take account of the mental state of the other(s); in
particular, each needs to *recognize*
the other's beliefs, desires and
intentions. Discourse conventions in cooperative conversation are
adapted to facilitate this process: The speakers employ locutions that
reveal their intended effects, and their acknowledgments and
turn-taking consolidate mutual understanding. In this way
mixed-initiative dialogue and potentially, cooperative domain action
are achieved.


In the previous discussion of *content
planning* in language generation,
we said little about the formation of communicative intentions in this
process. But in the context of purposive dialogue, it is
essential to consider how a dialogue agent might arrive at the
intention to convey certain ideas, such as episodic, instructional or
descriptive information, a request, an acknowledgment and/or
acceptance of a request, an answer to a question, an argument in
support of a conclusion, etc.


As in the case of generating extended descriptions, narrative,
arguments, *etc.*, using RST, a
natural perspective here is one centered
around goal-directed planning. In fact, the application of this
perspective to dialogue historically preceded its application to
extended discourses. In particular, Cohen and Perreault (1979) proposed
a reasoning, planning, and plan recognition framework that represents
speech acts in terms of their preconditions and effects. For example, a
simple INFORM speech act might have the following preconditions
(formulated for understandability from a first-person speaker
perspective):


* The
hearer (my dialogue partner) does not know whether a certain
proposition *X* is true;
* the hearer wants to be told by me
whether *X* is true; and
* I do in fact know whether *X* is
true.



The effect of implementing the INFORM as an utterance is then that the
hearer *knows whether X is true.* An important feature of such
a framework is that it can account for indirect speech acts (Allen and
Perreault 1980). For example, question (7.1), as an indirect request
for the date or day of the week, can be viewed as indicating the
speaker's awareness that the hearer can perform the requested
information-conveying act only if the knowledge-precondition of that
act is satisfied. Furthermore, since the hearer recognizes that
questioning a precondition of a potential act is one indirect way of
requesting the act, then (unless the context provides evidence to the
contrary) the hearer will make the inference that the speaker wants
the hearer to perform the information-conveying speech act. Note that
the reasoning and planning framework must allow for iterated
modalities such as "I believe that you want me to tell you what
today's date is", or "I believe (because of the request I
just made) that you know that I want you to pass the salt shaker to
me". Importantly, there must also be allowance for mutual
beliefs and intentions, so that a common ground can be maintained as
part of the context and collaboration can take place. A belief is
mutual if each participant holds the belief, and the participants
mutually believe that they mutually hold the belief. The mutual
knowledge of the participants in a dialogue can be assumed to include
the overt contents of their utterances and common general knowledge,
including knowledge of discourse conventions.


Since the ultimate purpose of a dialogue may be to accomplish something
in the world, not only in the minds of the participants, reasoning,
goal-directed planning, and action need to occur at the domain level as
well. The goals of speech acts are then not ends in themselves, but
means to other ends in the domain, perhaps to be accomplished by
physical action (such as equipment repair). As a result, task-oriented
dialogues are apt to be structured in a way that follows or "echoes"
the structure of the domain entities and the way they can be
purposefully acted upon. Such considerations led to Grosz and Sidner's
theory of dialogue structure in task-oriented dialogues (Grosz and
Sidner 1986). Their theory centers around the idea of shifts of
attention mediated by pushing and popping of "focus spaces" on a stack.
Focus spaces hold in them structured representations of the domain
actions under consideration. For example, setting a collaborative goal
of attaching a part to some device would push a corresponding focus
space onto the stack. As dictated by knowledge about the physical task,
the participants might next verbally commit to the steps of using a
screwdriver and some screws to achieve the goal, and this part of the
dialogue would be mediated by pushing corresponding subspaces onto the
focus stack. When a subtask is achieved, the corresponding focus space
is popped from the stack.


Implementation of reasoning and planning frameworks covering both the
iterated modalities needed for plan-based dialogue behavior and the
realities of a task domain has proved feasible for constrained
dialogues in restricted domains (e.g.,
Smith et al. 1995), but
quickly
comes up against a complexity barrier when the coverage of language and
the scope of the domain of discourse are enlarged. Planning is in
general NP-hard, indeed PSPACE-complete even in propositional planning
formalisms (Bylander 1994), and plan recognition can be exponential in
the number of goals to be recognized, even if all plans available for
achieving the goals are known in advance (Geib 2004).


In response to this difficulty, researchers striving to build usable
systems have experimented with a variety of strategies. One is to
pre-equip the dialogue system with a hierarchy of carefully engineered
plans suitable for the type of dialogue to be handled (such as
tutoring, repair, travel planning or schedule maintenance), and to
choose the logical vocabulary employed in NLU/NLG so that it meshes
smoothly with both the planning operators and with the surface
realization schemas aimed at the target domain. (As a noteworthy
example of this genre, see Moore & Paris 1993.) In this way
domain and
text planning and surface realization become relatively
straightforward, at least in comparison with systems that attempt to
synthesize plans from scratch, or to reason extensively about the
world, the interlocutor, the context, and the best way to express an
idea at the surface level. But while such an
approach is entirely defensible for an experimental system intended to
illustrate the role of plans and intentions in a specialized domain, it
leaves open the question of how large amounts of linguistic knowledge
and world knowledge could be incorporated into a dialogue system, and
used *inferentially* in
planning communicative (and other) actions.


Another strategy for achieving more nearly practical performance has
been to precode (and to some extent learn) more "reactive" (as opposed
to deliberative) ways of participating in dialogue. Reactive techniques
include (i) formulaic, schema-based responses (reminiscent of ELIZA)
where such responses are likely to be appropriate; (ii) rule-based
intention and plan recognition; e.g.,
an automated travel agent
confronted with the elliptical input 
"Flights to Orlando" can usually
assume that the user wishes to be provided with flight options from the
user's current city to Orlando, in a time frame that may have been
established previously; (iii) statistical domain plan recognition based
on probabilistic modeling of the sequences of steps typically taken in
pursuit of the goals characteristic of the domain; and (iv) discourse
state modeling by classifying speech acts (or utterance acts) and
dialogue states into relatively small numbers of types, and viewing
transitions between dialogue states as events determined by the current
state and current type of speech act. For example, in a state where the
dialogue system has no immediate obligation, and the user asks a
question, the system assumes the obligation of answering the question,
and transitions to a state where it will try to discharge that
obligation.


However, systems that rely primarily on reactive techniques tend to
lack deep understanding and behavioral flexibility. Essentially,
knowledge-based inference and planning are replaced by rote behavior,
conditioned by miscellaneous features of the current discourse state
and observations in the world. Furthermore, deliberate reasoning and
plan synthesis seem necessary for an agent that can acquire effective
goal-directed plans and behaviors autonomously. Although random trial
and error (as in reinforcement learning), supervised learning, and
learning by imitation are other learning options, their potential is
limited. Random trial and error is apt to be impractical in the
enormously large state space of linguistic and commonsense behavior;
supervised learning (of appropriate choices based on contextual
features) seems at best able to induce rote plan recognition and
discourse state transitions (reactive behaviors of types (iii) and
(iv) above); and imitation is possible only when relevant, readily
observable exemplary behaviors can be presented to the
learner--and by itself, it can lead only to rote, rather than
reasoned, behavior.


Integrating reactive methods with deliberate reasoning and planning may
be enabled in future by treating intentions and actions arrived at by
reactive methods as tentative, to be verified and potentially modified
by more deliberate reasoning if time permits. Excessive reasoning
with iterated modalities could also be avoided with stronger
assumptions about the attainment of mutual belief. For example,
we might assume that both speaker and hearer spontaneously perform
forward inferences about the world and about each other's mental states
based on discourse events and common knowledge, and that such forward
inferences directly become mutual knowledge (on a "likemindedness"
assumption), thus shortcutting many modally nested inferences.


## 8. Acquiring knowledge for language


We have noted the dependence of language understanding and use on vast
amounts of shallow and deep knowledge, about the world, about lexical
and phrasal meaning, and about discourse and dialogue structure and
conventions. If machines are to become linguistically competent, we
need to impart this knowledge to them.


Ideally, the initial, preprogrammed knowledge of a machine would be
restricted to the kinds of human knowledge thought to be innate (e.g.,
object persistence, motion continuity, basic models of animacy and
mind, linguistic universals, means of classifying/taxonomizing the
world, of organizing events in time, of abstracting from experience,
and other such knowledge and know-how). The rest would be learned in
human-like fashion. Unfortunately, we do not have embodied agents with
human-like sensory and motor equipment or human-like innate mental
capabilities; so apart from the simplest sort of verbal learning by
robots such as verbal labeling of objects or actions, or using spatial
prepositions or two-word sentences (e.g.,
Fleischman and Roy 2005;
McClain and Levinson 2007; Cour et al.
2008), most current work on
knowledge acquisition uses either (1) *hand-coding*,
(2) *knowledge
extraction from text corpora*, or (3) *crowdsourcing* coupled with some
method of converting collected, verbally expressed "facts" to a usable
format. We focus in this section on the acquisition of general
background knowledge needed to support language understanding and
production, leaving discussion of linguistic knowledge acquisition to
section 9.


### 8.1 Manual knowledge encoding


The best-known manually created body of commonsense knowledge is the
Cyc or ResearchCyc knowledge base (KB) (Lenat 1995). This contains an ontology of a
few hundred thousand concepts and several million facts and rules,
backed up by an inference engine. It has been applied to analysis,
decision support and other types of projects in business, education and
military domains. However, the Cyc ontology and KB contents have been
motivated primarily by knowledge engineering considerations (often for
specific projects) rather than by application to language
understanding, and this is reflected in its heavy reliance on 
very specific predicates expressed as concatenations of English words,
and on higher-order operators. For example, the relation between
killing and dying is expressed using the predicates *lastSubEvents,
KillingByOrganism-Unique*, and *Dying*,
and relies on a higher-order
relation *relationAllExists*
that can be expanded into a quantified
conditional statement. This remoteness from language makes it difficult
to apply the Cyc KB to language understanding, especially if the goal
is to extract relevant concepts and axioms from this KB and integrate
them with concepts and axioms formalized in a more linguistically
oriented representation (as opposed to adopting the CycL language, Cyc
KB, axioms about English, and inference mechanisms wholesale)
(e.g., Conesa et al. 2010).


Other examples of hand-coded knowledge bases are the Component
Library (CLib) (Barker et al. 2001), and a collection of commonsense
psychological axioms by Hobbs and Gordon (2005). CLib provides a broad
upper (i.e., high-level) ontology of several hundred concepts, and
axioms about basic actions (conveying, entering,
breaking, *etc.*) and resultant change. However, the
frame-based Kleo knowledge representation used in CLib
is not close to language, and the coverage of the English lexicon is
sparse. The psychological axioms of Hobbs and Gordon are naturally
narrow in focus (memories, beliefs, plans, and goals), and it remains
to be seen whether they can be used effectively in conjunction with
language-derived logical forms (of the "flat" type favored by Hobbs)
for inference in discourse contexts.


Knowledge adaptation from semi-formalized sources can, for example,
consist of extracting part-of-speech and subcategorization information
as well as stock phrases and idioms from appropriate dictionaries. It
may also involve mapping hypernym hierarchies, meronyms (parts), or
antonyms, as catalogued in sources like WordNet, into some form usable
for disambiguation and inference. The main limitations of manually
coded lexical knowledge are its grounding in linguistic intuitions
without direct consideration of its role in language understanding,
and its inevitable incompleteness, given the ever-expanding and
shifting vocabulary, jargon, and styles of expression in all living
languages. 


Besides these sources of lexical knowledge, there are also sources of
world knowledge in semi-formalized form, such as tabulations and
gazetteers of various sorts, and "info boxes" in online knowledge
resources such as Wikipedia (e.g.,
the entries for notable personages
contain a box with summary attributes such as date of birth, date of
death, residence, citizenship, ethnicity, fields of endeavor, awards,
and others). But to the extent that such sources provide knowledge in a
regimented, and thus easily harvested form, they do so only for named
entities (such as people, organizations, places, and movies) and a few
entity types (such as biological species and chemical compounds).
Moreover, much of our knowledge about ordinary concepts, such as that
of a *tree* or that of *driving a car*, is not easily captured in the form
of attribute-value pairs, and is generally not available in that form.


### 8.2 Knowledge extraction from text


Knowledge extraction from unconstrained text has in recent years been
referred to as *learning by reading*.
The extraction method may be either
direct or indirect. A direct method takes sentential information from
some reliable source, such as word sense glosses in WordNet or
descriptive and narrative text in encyclopedias such as Wikipedia, and
maps this information into a (more) formal syntax for expressing
generic knowledge. Indirect methods abstract (more or less) formal
generic knowledge from the patterns of language found in miscellaneous
reports, stories, essays, weblogs, etc.


Reliably extracting knowledge by the direct method requires
relatively deep language understanding, and consequently is far from a
mature technology. Ide and Veronis (1994) provide a survey of early
work on deriving knowledge from dictionary definitions, and the
difficulties faced by that enterprise. For the most part knowledge
obtained in this way to date has been either low in quantity or in
quality (from an inference perspective). More recent work that shows
promise is that of Moldovan and Rus (2001), aimed at interpreting
WordNet glosses for nominal artifact concepts, and that of Allen et
al. (2013), aimed at forming logical theories of small clusters of
related verbs (e.g., sleeping, waking up, *etc.*) by
interpreting their WordNet glosses.


The most actively researched approach to knowledge extraction from
text in the last two decades has been the indirect one, beginning with
a paper by Marti Hearst demonstrating that hyponymy relations could be
rather simply and effectively discovered by the use of lexicosyntactic
extraction patterns (Hearst 1992). For example, extraction patterns
that look for noun phrases separated by "such as" or
"and other" will match word sequences like "seabirds
such as penguins and albatrosses" or "beans, nuts, and
other legumes", leading to hypotheses that
*seabird* is a hypernym of *penguin* and
*albatross*, and that *beans* and *nuts* are
hyponyms of *legumes*. By looking for known hyponym-hypernym
pairs in close proximity, Hearst was able to expand the initial set of
extraction patterns and hence the set of hypotheses. Many variants
have been developed since then, with improvements such as automation
of the bootstrapping and pattern discovery methods, often with machine
learning techniques applied to selection, weighting and combination of
local features in the immediate vicinity of the relata of
interest. Relations other than hyponymy that have been targeted, of
relevance to language understanding, include part-of relations, causal
relations, and telic relations (such as that the use of
*milk* is to *drink* it). 


While knowledge extraction using Hearst-like patterns is narrowly
aimed at certain predetermined types of knowledge, other approaches
are aimed at open information extraction (OIE). These seek to
discover a broad range of relational knowledge, in some cases
including entailments (in a rather loose sense) between different
relations. An early and quite successful system of this genre was Lin
and Pantel's DIRT system (Discovery of Inference Rules from Text),
which used collocational statistics to build up a database of
"inference rules" (Lin and Pantel 2001). An example of a
rule might be "*X* finds a solution to *Y*
[?] *X* solves *Y*." The statistical techniques
used included clustering of nominals into similarity groups based on
their tendency to occur in the same argument positions of the same
verbs, and finding similar relational phrases (such as "finds a
solution to" and "solves"), based their tendency to
connect the same, or similar, pairs of nominals. Many of the rules
were later refined by addition of type constraints to the variables,
obtained by abstracting from particular nominals via WordNet (Pantel
et al. 2007). 


An approach to OIE designed for maximum speed is exemplified by the
TextRunner system (Banko et al. 2007). TextRunner is
extraction pattern-based, but rather than employing patterns tuned to
a few selected relations, it uses a range of patterns obtained
automatically from a syntactically parsed training corpus, weighted
via Bayesian machine learning methods to extract miscellaneous
relations sentence-by-sentence from text. A rather different approach,
termed "open knowledge extraction" (OKE), derives logical forms from
parsed sentences, and simplifies and abstracts these so that they will
tend to reflect general properties of the world. This is exemplified
by the Knext system (KNowledge EXtraction from Text)
(e.g., Schubert and Tong 2003). For example, the sentence 
"I read a very informative book about China" allows KNEXT to abstract
"factoids" to the effect that a person may occasionally read a book,
and that books may occasionally be informative, and may occasionally
be about a country. (Note that the specific references to the speaker
and China have been abstracted to classes.) Another interesting
development has been the extraction of script-like sequences of
relations from large corpora by collocational methods (see Chambers
and Jurafsky 2009). For example, the numerous newswire reports about
arrest and prosecution of criminals can be mined to abstract typical
event types involved, in chronological order, such as arrest,
arraignment, plea, trial, and so on. A difficulty in all of this work
is that most of the knowledge obtained is too ambiguously and
incompletely formulated to provide a basis for inference chaining (but
see for example Van Durme et al. 2009; Gordon and Schubert
2010; Schoenmackers et al. 2010).


### 8.3 Crowdsourcing



The crowdsourcing approach to the acquisition of general knowledge
consists of soliciting verbally expressed information, or annotations
of such information, from large numbers of web users, sometimes using
either small financial rewards or the challenge of participating in
simple games as inducements (Havasi et al. 2007; von Ahn
2006). Crowdsourcing has proved quite reliable for simple
annotation/classification tasks (e.g., Snow et al.
2008; Hoffmann et al. 2009). However, general knowledge
offered by non-expert users is in general much less carefully
formulated than, say, encyclopedia entries or word sense glosses in
lexicons, and still requires natural language processing if formal
statements are to be abstracted. Nevertheless, the
Open Mind Common Sense
 project has produced a
relational network of informal commonsense knowledge (ConceptNet),
based on simple English statements from worldwide contributors, that
proved useful for improving interpretation in speech recognition and
other domains (Lieberman et al. 2004; Faaborg et al.
2005). 


The overall picture that emerges is that large-scale resources of
knowledge for language, whether lexical or about the world, still
remain too sparse and too imprecise to allow scaling up of
narrow-domain NLU and dialogue systems to broad-coverage
understanding. But such knowledge is expected to prove crucial
eventually in general language understanding, and so the quest for
acquiring this general knowledge remains intensely active.


## 9. Statistical NLP



> "All
> the thousands of times you've heard clause-final auxiliary
> verbs uncontracted strengthen the probability that they're not allowed
> to contract."
> 
> -Geoff Pullum (2011)
> 
> 


We have already referred to miscellaneous statistical models and
techniques used in various computational tasks, such as
(in section 2) HMMs in POS tagging,
probabilistic grammar modeling and parsing, statistical semantics,
semantic disambiguation (word senses, quantifier scope, etc.), plan
recognition, discourse modeling, and knowledge extraction from
text. Here we try to provide a brief, but slightly more systematic
taxonomy of the types of tasks addressed in statistical NLP, and some
sense of the modeling techniques and algorithms that are most commonly
used and have made statistical NLP so predominant in recent years,
challenging the traditional view of computational linguistics.


This traditional view focuses on deriving meaning, and rests on the
assumption that the syntactic, semantic, pragmatic, and world knowledge
employed in this derivation is "crisp" as opposed to probabilistic;
i.e., the distributional properties of language are a mere byproduct of
linguistic communication, rather than an essential factor in language
understanding, use, or even learning. Thus the emphasis, in this
view, is on formulating nonprobabilistic syntactic, semantic,
pragmatic, and KR theories to be deployed in language understanding and
use. Of course, the problem of ambiguity has always been a focal issue
in building parsers and language understanding systems, but the
prevailing assumption was that ambiguity resolution could be
accomplished by supplementing the interpretive routines with some
carefully formulated heuristics expressing syntactic and semantic
preferences.


However, experience has revealed that the ambiguities that afflict
the desired mappings are far too numerous, subtle, and interrelated to
be amenable to heuristic arbitration. Instead, linguistic phenomena
need to be treated as effectively stochastic, and the distributional
properties resulting from these stochastic processes need to be
systematically exploited to arrive at reasonably reliable hypotheses
about underlying structure. (The Geoff Pullum quote above is relevant
to this point: The inadmissiblity of contracting the first occurrence
of *I am* to *I'm* in "I'd rather be hated for who
I am, than loved for who I am not" is not easily ascribed to any
grammatical principle, yet--based on positive evidence
alone--becomes part of our knowledge of English usage.) Thus the
emphasis has shifted, at least for the time being, to viewing NLP as a
problem of uncertain inference and learning in a stochastic
setting.


This shift is significant from a philosophical perspective, not
just a practical one: It suggests that traditional thinking about
language may have been too reliant on introspection. The limitation of
introspection is that very little of what goes on in our brains when
we comprehend or think about language is accessible to consciousness
(see for example the discussion of "two-channel
experiments" in Baars 1997). We consciously register
the *results* of our understanding and thinking, apparently in
symbolic form, but not the understanding and
thinking *processes* themselves; and these symbolic
abstractions, to the extent that they lack quantitative or
probabilistic dimensions, can lead us to suppose that the underlying
processing is nonquantitative as well. But the successes of
statistical NLP, as well as recent developments in cognitive science
(e.g., Fine et al. 2013; Tenenbaum et al. 2011; Chater and
Oaksford 2008) suggest that language and thinking are not only
symbolic, but deeply quantitative and in particular probabilistic.


For the first twenty years or so, the primary goals in statistical
NLP have been to assign labels, label sequences, syntax trees,
or translations to linguistic inputs, using statistical language
models trained on large corpora of observed language use. More fully,
the types of tasks addressed can be grouped roughly as follows (where
the appended keywords indicate typical applications):


* *text/document classification:* authorship, Reuters news
 category, sentiment analysis;
* *classification of selected words or phrases in sentential or
 broader contexts:* word sense disambiguation, named entity
 recognition, multiword expression recognition;
* *sequence labeling:* acoustic features - phones
 - phonemes - words - POS tags;
* *structure assignment to sentences:* parsing, semantic
 role labeling, quantifier scoping;
* *sentence transduction:* MT, LF computation;
* *structure assignment to multi-sentence texts:* discourse
 relations, anaphora, plan recognition;
* *large-scale relation extraction:* knowledge extraction,
 paraphrase and entailment relations.


These
groups may seem to differ haphazardly, but as we will further discuss,
certain techniques and distinctions are common to many of them, notably


* *in modeling:* numeric and discrete features, vector
 models, log-linear models, Markov models; generative versus
 discriminative models, parametric versus non-parametric
 models;
* *in learning from data:* maximum likelihood estimation,
 maximum entropy, expectation maximization, dynamic programming;
 supervised versus unsupervised learning; and
* *in output computation:* dynamic programming; unique
 outputs versus distributions over outputs.


We now try to provide some intuitive insight into the most
important techniques and distinctions involved in the seven groups of
tasks above. For this purpose, we need not comment further on
quantifier scoping (in the fourth group) or any of the items in the
sixth and seventh groups, as these are for the most part covered
elsewhere in this article. In all cases, the two major requirements
are the development (aided by learning) of a probabilistic model
relating linguistic inputs to desired outputs, and the algorithmic use
of the model in assigning labels or structures to previously unseen
inputs. 


**Text and document classification**: In classifying substantial
documents, the features used might be normalized occurrence
frequencies of particular words (or word classes) and
punctuation. Especially for shorter texts, various discrete features
may be included as well, such as 0, 1-valued functions indicating the
presence or absence of certain key words or structural features. In
this way documents are represented as numerical vectors, with
values in a high-dimensional space, with separate classes
presumably forming somewhat separate clusters in that space. A variety
of classical pattern recognition techniques are applicable to the
problem of learning to assign new documents (as vectors) to the
appropriate class (e.g., Sebestyen 1962; Duda and Hart 1973). Perhaps
the simplest approach (most easily applied when features are binary)
is a naive Bayesian one, which assumes that each class generates
feature values that are independent of one another. The generative
frequencies are estimated from the training data, and class membership
probabilities for an unknown document (vector) are computed via Bayes'
rule (which can be done using successive updates of the prior class
probabilities). Choosing the class with the highest resultant
posterior probability then provides a decision criterion. A common
generative model for real-valued features, allowing for feature
interactions, views the known members of any given class as a sample
of a multivariate normal (Gaussian) random variable. Learning in this
case consists of estimating the mean and covariance matrix of each
class (an example of maximum likelihood estimation).


A traditional *discriminative* approach, not premised on any
generative model, involves the computation of hyperplanes that
partition the clusters of known class instances from one another
(optimizing certain metrics involving in-class and between-class
variance); new instances are assigned to the class into whose
partition they fall. *Perceptrons* provide a related technique,
insofar as they decide class membership on the basis of a linear
combination of feature values; their particular advantage is that they
can learn incrementally (by adjusting feature weights) as more and
more training data become available. Another durable discriminative
approach--not dependent on linear separability of classes--is the
**k* nearest neighbors* (kNN) method, which assigns an unknown
text or document to the class that is most prevalent among its *k*
(e.g., 1-5) nearest neighbors in vector space. While all the
previously mentioned methods depended on parameter estimation (e.g.,
generative probabilities, Gaussian parameters, or coefficients of
separating planes), kNN uses no such parameters--it is
*nonparametric*; however, finding a suitable measure of
proximity or similarity can be challenging, and errors due to
haphazard local data point configurations in feature space are hard to
avoid. Another nonparametric discriminative method worth mentioning is
the use of *decision trees*, which can be learned using
information-theoretic techniques; they enable choice of a class by
following a root-to-leaf path, with branches chosen via tests on
features of a given input vector. A potentially useful property is
that learned decision trees can provide insight into what the most
important features are (such insight can also be provided by
*dimensionality reduction* methods). However, decision trees
tend to converge to nonglobal optima (global optimization is NP-hard),
and by splitting data, tend to block modeling of feature interactions;
this defect can be alleviated to some extent through the use of
*decision forests*. 


Having mentioned some of the traditional classification methods, we
now sketch two techniques that have become particularly prominent in
statistical NLP since the 1990s. The first, with mathematical roots
dating to the 1950s, is *maximum entropy* (MaxEnt), also called
*(multinomial) logistic regression* (e.g., Ratnaparkhi
1997). Features in this case are any desired 0, 1-valued (binary)
functions of both a given linguistic input and a possible class. (For
continuous features, supervised or unsupervised
*discretization* methods may be applied, such as entropy-based
partitioning into some number of intervals.) Training data provide
occurrence frequencies for these features, and a distribution is
derived for the *conditional probability of a class, given a
linguistic input*. (As such, it is a discriminative method.) As
its name implies, this conditional probability function is a
maximum-entropy distribution, constrained to conform with the binary
feature frequencies observed in the training data. Its form (apart
from a constant multiplier) is an exponential whose exponent is a
linear combination of the binary feature values for a given input and
given class. Thus it is a *log-linear* model (a distribution
whose logarithm is linear in the features)--a type of model now
prevalent in many statistical NLP tasks. Note that since its
logarithm is a linear combination of binary feature values for any
given input and any given class, choosing the maximum-probability
class for a given input amounts to linear decision-making, much as in
some of the classical methods; however, MaxEnt generally provides
better classification performance, and the classification
probabilities it supplies can be useful in further computations (e.g.,
expected utilities).


Another method important in the emergence and successes of
statistical NLP is the *support vector machine* (SVM) method
(Boser et al. 1992; Cortes and Vapnik 1995). The great
advantage of this method is that it can in principle distinguish
arbitrarily configured classes, by implicitly projecting the original
vectors into a higher- (or infinite-) dimensional space, where the
classes are linearly separable. The projection is mediated by a
*kernel function*--a similarity metric on pairs of vectors,
such as a polynomial in the dot product of the two vectors. Roughly
speaking, the components of the higher-dimensional vector correspond
to terms of the kernel function, if it were expanded out as a sum of
products of the features of the original, unexpanded pair of
vectors. But no actual expansion is performed, and moreover the
classification criterion obtained from a given training corpus only
requires calculation of the kernel function for the given feature
vector (representing the document to be classified) paired with
certain special "support vectors", and comparison of a linear
combination of the resulting values to a threshold. The support
vectors belong to the training corpus, and define two parallel
hyperplanes that separate the classes in question as much as possible
(in the expanded space). (Hence this is a "max-margin" discriminative
method.) SVMs generally provide excellent accuracy, in part because
they allow for nonlinear feature interaction (in the original space),
and in part because the max-margin method focuses on class separation,
rather than conditional probability modeling of the classes. On the
other hand, MaxEnt classifiers are more quickly trainable than SVMs,
and often provide satisfactory accuracy. General references covering
the classification methods we have sketched are (Duda et al.
2001; Bishop 2006). 


**Classification of selected words or phrases in sentential or
broader contexts**: As noted earlier, examples include WSD, named
entity recognition, and sentence boundary detection. The only point of
distinction from text/document classification is that it is not a
chunk of text as a whole, but rather a word or phrase in the context
of such a chunk that is to be classified. Therefore features are
chosen to reflect both the features of the target word or phrase (such
as morphology) and the way it relates to its context, in terms of,
e.g., surrounding words or word categories, (likely) local syntactic
dependency relations, and features with broader scope such as word
frequencies or document class. Apart from this difference in how
features are chosen, the same (supervised) learning and classification
methods discussed above can be applied. However, sufficiently
large training corpora may be hard to construct. For example, in
statistical WSD (e.g., Yarowsky 1992; Chen et al.
2009), since thousands of words have multiple senses in sources
such as WordNet, it is difficult to construct a
sense-annotated training corpus that contains sufficiently many
occurrences of all of these senses to permit statistical
learning. Thus annotations are typically restricted to the
senses of a few polysemous words, and statistical WSD has been shown
to be feasible for the selected words, but broad-coverage WSD tools
remain elusive.



**Sequence labeling**: There is a somewhat arbitrary line between
the preceding task and sequence labeling. For example, it is quite
possible to treat POS tagging as a task of classifying words in a text
in relation to their context. However, such an approach fails to
exploit the fact that the classifications of adjacent words are
interdependent. For example, in the sentence (from the web) 
"I don't fish like most people", the occurrence of *don't*
should favor classification of *fish* as a verb, which in turn
should favor classification of *like* as a preposition. (At
least such preferences make sense for declarative sentences; replacing
'I' by 'why' would change matters--see
below.) Such cascaded influences are not easily captured through
successive independent classifications, and they motivate generative
sequence models such as HMMs. For POS tagging, a labeled training
corpus can supply estimates of the probability of any POS for the next
word, given the POS of the current word. If the corpus is large
enough, it can also supply estimates of word "emission" probabilities
for a large proportion of words generally seen in text, i.e.,
their probability of occurring, given the POS label. (Smoothing
techniques are used to fill in non-zero probabilities for unknown
words, given a POS.) We previously mentioned the *Viterbi
algorithm* as an efficient dynamic programming algorithm for
applying an HMM (trained as just mentioned) to the task of assigning a
maximum-probability POS tag sequence to the words of a text. Two
related algorithms, the *forward* and *backward*
algorithms, can be used to derive *probabilities* of the
possible labels at each word position *i*, which may be more
useful than the "best" label sequence for subsequent higher-level
processing. The *forward* algorithm in effect (via dynamic
programming) sums the probabilities of all label sequences up to
position *i* that end with a specified label *X* at word
position *i* and that generate the input up to (and including)
that word. The *backward* algorithm sums the probabilities of
all label sequences that begin with label *X* at position
*i*, and generate the input from position
*i*+1 to the end. The product of the forward
and backward probabilities, normalized so that the probabilities of
the alternative labels at position *i* sum to 1, give the
probability of *X* at *i*, conditioned on the entire
input.


 All learning methods referred to so far have been *supervised
learning* methods--a corpus of correctly labeled texts was
assumed to be available for inferring model parameters. But methods
have been developed for *unsupervised* (or
*semi-supervised*) learning as well. An important unsupervised
method of discovering HMM models for sequence labeling is the
*forward-backward* (or *Baum-Welch*) algorithm. A simple
version of this algorithm in the case of POS tagging relies on a
lexicon containing the possible tags for each word (which are easily
obtained from a standard lexicon). Some initial, more or less
arbitrarily chosen values of the HMM transition and emission
probabilities are then iteratively refined based on a training corpus.
A caricature of the iterative process would be this: We use the
current guesses of the HMM parameters to tag the training corpus; then
we re-estimate those parameters just as if the corpus were
hand-tagged. We repeat these two steps till convergence. The actual
method used is more subtle in the way it uses the current HMM
parameters. (It is a special case of *EM*--*Expectation
Maximization*.) Rather than re-estimating the parameters based on
occurrence frequencies in the current "best" tag sequence, it uses the
*expected* number of occurrences of particular pairs of
successive states (labels), dividing this by the *expected*
number of occurrences of the first member of the pair. These expected
values are determined by the conditional probability distribution over
tag sequences, given the training corpus and the current HMM
parameters, and can be obtained using the forward and backward
probabilities as described above (and thus, conditioned on the entire
corpus). Revised emission probabilities for any *X* -
*w* can be computed as the sum of probabilities of
*X*-labels at all positions where word *w* occurs in the
corpus, divided by the sum of probabilities of *X*-labels at
all positions, again using (products of) forward and backward
probabilities.


Unfortunately EM is not guaranteed to find a globally optimal
model. Thus good results can be achieved only by starting with a
"reasonable" initial HMM, for example assigning very low
probabilities to certain transitions (such as determiner -
determiner, determiner - verb, adjective - verb).
*Semi-supervised* learning might start with a relatively small
labeled training corpus, and use the corresponding HMM parameter
estimates as a starting point for unsupervised learning from further,
unlabeled texts. 


A weakness of HMMs themselves is that the Markov assumption
(independence of non-neighbors, given the neighbors) is violated by
longer-range dependencies in text. For example, in the context of a
relative clause (signaled by a noun preceding that clause), a
transitive verb may well lack an NP complement ( "I collected
the money he **threw** down on the table."), and as a result,
words following the verb may be tagged incorrectly (*down* as a
noun). A discriminative approach that overcomes this difficulty is
the use of *conditional random fields* (CRFs). Like HMMs (which
they subsume), these allow for local interdependence of hidden states,
but employ features that depend not only on adjacent pairs of these
states, but also on any desired properties of the entire input.
Mathematically, the method is very similar to MaxEnt (as discussed
above). The feature coefficients can be learned from training data
either by gradient ascent or by an incremental dynamic programming
method related to the Baum-Welch algorithm, called *improved
iterative scaling* (IIS) (Della Pietra et al. 1997; Lafferty et
al. 2001). CRFs have been successful in many applications other than
POS tagging, such as sentence and word boundary detection (e.g., for
Chinese), WSD, extracting tables from text, named entity recognition,
and--outside of NLP--in gene prediction and computer
vision.


**Structure assignment to sentences**: The use of probabilistic
context-free grammars (PCFGs) was briefly discussed in 
section 2. Supervised learning of PCFGs can be
implemented much like supervised learning of HMMs for POS tagging. The
required conditional probabilities of phrase expansion are easily
estimated if a large corpus annotated with phrase bracketings (a
treebank) is available (though estimates of *POS* - word
expansion probabilities are best supplemented with additional data).
Once learned, a PCFG can be used to assign probabilistically weighted
phrase structures to sentences using the chart parsing method
mentioned in
section 2--again a dynamic programming method. 


Also, unsupervised learning of PCFGs is possible using the EM
approach. This is important, since it amounts to grammar
*discovery*. The only assumption we start with, theoretically,
is that there is some maximum number of nonterminal symbols, and each
can be expanded into any two nonterminals or into any word (Chomsky
normal form). Also we associate some more or less arbitrary initial
expansion probabilities with these rules. The probabilities are
iteratively revised using expected values of the frequency of
occurrence of the possible expansions, based on the current PCFG
model, conditioned on the corpus. The analogue of the forward-backward
algorithm for computing these expectations is the
*inside-outside* algorithm. Inside probabilities specify the
probability that a certain proper segment of a given sentence will be
derived from a specified nonterminal symbol. Outside probabilities
specify the probability that *all but* a certain segment of the
given sentence will be derived from the start (sentence) symbol, where
that "missing" segment remains to be generated from a specified
nonterminal symbol. The inside and outside probabilities play roles
analogous to the backward and forward probabilities in HMM learning
respectively. Conceptually, they require summations over exponentially
many possible parse trees for a given sentence, but in fact inside
probabilities can be computed efficiently by the CYK algorithm
(section 2), and outside probabilities can also be computed
efficiently, using a top-down recursive "divide and conquer" algorithm
that makes use of previously computed inside probabilities.


Modest successes have been achieved in learning grammars in this
way. The complexity is high (cubic-time in the size of the training
corpus as well as in the number of nonterminals), and as noted, EM
does not in general find globally optimal models. Thus it is
important to place some constraints on the initial grammar, e.g.,
allowing nonterminals to generate either pairs of nonterminals or
words, but not both, and also severely limiting the number of allowed
nonterminals. A method of preferring small rule sets over large ones,
without setting a fixed upper bound, is the use of a *Dirichlet
process* that supplies a probability distribution over the
probabilities of an unbounded number of rules. (This method is
nonparametric, in the sense that it does not commit to any fixed
number of building blocks or parameters in the modeling.) Whatever
method of bounding the rules is used, the initial PCFG must be
carefully chosen if a reasonably good, meaningful rule set is to be
learned. One method is to start with a linguistically motivated
grammar and to use "symbol splitting" (also called
"state splitting") to generate variants of nonterminals
that differ in their expansion rules and
probabilities. Recent *spectral algorithms* offer a relatively
efficient, and globally optimal, alternative to EM (Cohen et
al. 2013), and they can be combined with symbol splitting. 


Like HMMs, PCFGs are generative models, and like them suffer from
insufficient sensitivity of local choices to the larger context. CRFs
can provide greater context-sensitivity (as in POS tagging and other
types of sequence labeling); though they are not directly suited to
structure assignment to text, they can be used to learn shallow
parsers, which assign phrase types only to nonrecursive phrases (core
NPs, PPs, VPs, etc.) (Sha and Pereira 2003).



In the current grammar-learning context, we should also mention
connectionist models once more. Such models have shown some capacity
for learning to parse from a set of training examples, but achieving
full-scale parsing in this way remains a challenge. Also a
controversial issue is the capacity of nonsymbolic NNs to
exhibit *systematicity* in unsupervised learning, i.e.,
demonstrating a capacity to generalize from unannotated examples. This
requires, for example, the ability to accept or generate sentences
wherein verb arguments appear in positions different from those seen
in the training set. According to Brakel and Frank (2009),
systematicity can be achieved with simple recurrent networks
(SRNs). However, computational demonstrations have generally been
restricted to very simple, English-like artificial languages, at least
when inputs were unannotated word streams.



A structure assignment task that can be viewed as a step towards
semantic interpretation is *semantic role labeling*
(Palmer et al. 2010). The goal is to assign thematic roles
such as *agent, theme, recipient, etc.* to core phrases or
phrasal heads in relation to verbs (and perhaps other
complement-taking words). While this can be approached as a sequence
labeling problem, experimental evidence shows that computing parse
trees and using resulting structural features for role assignment (or
jointly computing parse trees and roles) improves precision. A
frequently used training corpus for such work is PropBank, a version
of the Penn Treebank annotated with "neutral" roles *arg0, arg1,
arg2,* etc.


**Sentence transduction**: The most intensively studied type of
statistical sentence transduction to date has been *statistical
MT* (SMT) (e.g., Koehn 2010; May 2012). Its successes beginning in
the late 1980s and early 90s came as something of a surprise to the
NLP community, which had been rather pessimistic about MT prospects
ever since the report by Bar-Hillel (1960) and the ALPAC report
(Pierce et al. 1966), negatively assessing the results of a
major post-WW2 funding push in MT by the US government. MT came to be
viewed as a large-scale engineering enterprise that would not have
broad impacts until it could be adequately integrated with semantics
and knowledge-based inference. The statistical approach emerged in the
wake of successful application of "noisy channel" models to speech
recognition in the late 1970s and during the 80s, and was propelled
forward by new developments in machine learning and the increasing
availability of large machine-readable linguistic corpora, including
parallel texts in multiple languages.


 The earliest, and simplest type of translation method
was *word-based*. This was grounded in the following sort of
model of how a foreign-language sentence *f* (say, in
French) is generated from an English sentence *e* (which we
wish to recover, if the target language is English): First, *e*
is generated according to some simple model of English, for instance
one based on bigram frequencies. Individual words of *e* are
then assumed to generate individual words of *f* with some
probability, allowing for arbitrary word-order scrambling (or biased
in some way). In learning such a model, the possible correspondences
and word-translation probabilities can be estimated from parallel
English-French corpora, whose sentences and words have
been *aligned* by hand or by statistical techniques. Such a
model can then be used for "decoding" a given French
sentence *f* into an English sentence *e* by Bayesian
inference--we derive *e* as the English sentence with highest
posterior probability, given its French "encoding" as *f*. This
is accomplished with dynamic programming algorithms, and might use an
intermediate stage where the *n* best choices of *e* are
computed (for some predetermined *n*), and subsequently
re-ranked discriminatively using features of *e* and *f*
ignored by the generative model.


However, the prevailing SMT systems (such as *Google
Translate* or *Yahoo! Babel Fish*) are
*phrase-based* rather than word-based. Here
"phrase" refers to single words or groups of words that
tend to occur adjacent to each other. The idea is that phrases are
mapped to phrases, for example, the English word pair *red
wine* to French phrases *vin rouge, du vin rouge*, or
*le vin rouge*. Also, instead of assuming arbitrary word order
scrambling, *reordering models* are used, according to which a
given phrase may tend to be swapped with the left or right neighboring
phrase or displaced from the neighbors, in the translation
process. Furthermore, instead of relying directly on a Bayesian
model, as in the word-based approach, phrase-based approaches
typically use a log-linear model, allowing for incorporation of
features reflecting not only the language model (such as trigram
frequencies), the phrase translation model (such as phrase translation
frequencies), and the reordering model, but also miscellaneous
features such as the number of words created, the number of phrase
translations used, and the number of phrase reorderings (with larger
penalties for larger displacements).


While phrase-based SMT models have been quite successful, they are
nonetheless prone to production of syntactically disfluent or
semantically odd translations, and much recent research has sought to
exploit linguistic structure and patterns of meaning to improve
translation quality. Two major approaches to syntactic transfer
are *hierarchical phrase-based translation*
and *tree-to-string* (*TTS*) *transduction*
models. Hierarchical phrase-based approaches use *synchronous
grammar* rules, which simultaneously expand partial derivations of
corresponding sentences in two languages. These are automatically
induced from an aligned corpus, and the lowest hierarchical layer
corresponds to phrase-to-phrase translation rules like those in
ordinary phrase-based translation. While quite successful, this
approach provides little assurance that "phrases" in the
resulting synchronous grammars are semantically coherent units, in the
linguistic sense. TTS models obtain better coherency through use of
parsers trained on phrase-bracketed text corpora (treebanks). The
encoding of English sentences into French (in keeping with our
previously assumed language pair) is conceptualized as beginning with
a parsed English sentence, which is then transformed by (learned)
rules that progressively expand the original or partially transformed
pattern of phrases and words until all the leaves are French
words.


Apart from MT, another important type of sentence transduction
is *semantic parsing*, in the sense of mapping sentences in
some domain to logical forms usable for question answering. (Note that
semantic role labeling, discussed above, can also be viewed as a step
towards semantic parsing.) Several studies in this relatively recent
area have employed supervised learning, based on training corpora
annotated with LFs (e.g., Mooney 2007; Zettlemoyer & Collins 2007)
or perhaps syntactic trees along with LFs (e.g., Ge and Mooney
2009). Typical domains have been QA about geography (where LFs are
database queries), about Robocup soccer, or about travel
reservations. Even unsupervised learning has been shown to be possible
in restricted domains, such as QA based on medical abstracts (Poon and
Domingos 2009) or the travel reservation domain (Poon 2013). Ideas
used in this work include forming synonym clusters of nominal terms
and verbal relations much as in Lin and Pantel's DIRT system, with
creation of logical names (reflecting their word origins) for these
concepts and relations; and learning (via *Markov logic,* a
generalization of *Markov networks*) to annotate the nodes of
dependency parse trees with database entities, types, and relations on
the basis of a travel reservation dialogue corpus (where the data
needed for the travel agent's answers are known to lie in the
database). Whether such methods can be generalized to less restricted
domains and forms of language remains to be seen. The recent creation
of a general corpus annotated with an "abstract meaning
representation", AMR, is likely to foster progress in that direction
(Banarescu et al. 2013).


The topics we have touched on in this section are technically
complex, so that our discussion has necessarily been shallow. General
references for statistical language processing are Manning and
Schutze 1999 and Jurafsky and Martin 2009. Also the
statistical NLP community has developed remarkably comprehensive
toolkits for researchers, such as MALLET (MAchine Learning for
LanguagE Toolkit), which includes brief explanations of many of the
techniques. 


What are the prospects for achieving human-like language learning
in machines? There is a growing recognition that statistical learning
will have to be linked to perceptual and conceptual modeling of the
world. Recent work in the area of *grounded language learning*
is moving in that direction. For example, Kim and Mooney (2012)
describe methods of using sentences paired with graph-based
descriptions of actions and contexts to hypothesize PCFG rules for
parsing NL instructions into action representations, while learning
rule probabilities with the inside-outside algorithm. However, they
assumed a very restricted domain, and the question remains how far the
modeling of perception, concept formation, and of semantic and
episodic memory needs to be taken to support unrestricted language
learning. As in the case of world knowledge acquisition by
machines (see the preceding section), the modeling capabilities may
need to achieve equivalence with those of a newborn, allowing for
encoding percepts and ideas in symbolic and imagistic languages of
thought, for taxonomizing entity types, recognizing animacy and
intentionality, organizing and abstracting spatial relations and
causal chains of events, and more. Providing such capabilities is
likely to require, along with advances in our understanding of
cognitive architecture, resolution of the very issues concerning the
representation and use of linguistic, semantic, and world knowledge
that have been the traditional focus in computational
linguistics. 


## 10. Applications



As indicated at the outset, applications of computational
linguistics techniques range from those minimally dependent on
linguistic structure and meaning, such as document retrieval and
clustering, to those that attain some level of competence in
comprehending and using language, such as dialogue agents that provide
help and information in limited domains like personal scheduling,
flight booking, or help desks, and intelligent tutoring systems. In the
following we enumerate some of these applications. In several cases
(especially machine translation) we have already provided considerable
detail, but the intent here is to provide a bird's eye view of
the state of the art, rather than technical elucidations.


With the advent of ubiquitous computing, it has become increasingly
difficult to provide a systematic categorization of NLP applications:
Keyword-based retrieval of documents (or snippets) and database access
are integrated into some dialogue agents and many voice-based services;
animated dialogue agents interact with users both in tutoring systems
and games; chatbot techniques are incorporated into various useful or
entertaining agents as a backends; and language-enabled robots, though
distinctive in combining vision and action with language, are gradually
being equipped with web access, QA abilities, tutorial functions, and
no doubt eventually with collaborative problem solving abilities. Thus
the application categories in the subsections that follow, rather than
being mutually exclusive, are ever more interwined in practice.



### 10.1 Machine translation (again)


One of the oldest MT systems is SYSTRAN,
which was developed as a rule-based system beginning in the 1960s, and
has been extensively used by US and European government agencies, and
also in Yahoo! Babel Fish and (until 2007) in Google Translate. 
In 2010, it was hybridized with statistical MT techniques. As mentioned, Google
Translate currently uses phrase-based MT, with English serving as an
interlingua for the majority of language pairs. Microsoft's Bing
Translator employs dependency structure analysis together with
statistical MT. Other very comprehensive translation systems include
Asia Online and WorldLingo. Many systems for small language groups
exist as well, for instance for translating between Punjabi and Hindi
(the Direct MT system), or between a few European languages (e.g.,
OpenLogos, IdiomaX, and GramTrans).


Translations remain error-prone, but their quality is usually
sufficient for readers to grasp the general drift of the source
contents. No more than that may be required in many cases, such as
international web browsing (an application scarcely anticipated in
decades of MT research). Also, MT applications on hand-held devices,
designed to aid international travellers, can be sufficiently accurate
for limited purposes such as asking directions or emergency help,
interacting with transportation personnel, or making purchases or
reservations, When high-quality translations are required,
automatic methods can be used as an aid to human translators, but
subtle issues may still absorb a large portion of a translator's time.


### 10.2 Document retrieval and clustering applications



Information retrieval has long been a central theme of information
science, covering retrieval of both structured data such as are found
in relational databases as well as unstructured text documents (e.g.,
Salton 1989). Retrieval criteria for the two types of data are not
unrelated, since both structured and unstructured data often require
*content-directed* retrieval. For example, while users of an
employee database may wish at times to retrieve employee records by
the unique name or ID of employees, at other times they may wish to
retrieve all employees in a certain employment category, perhaps with
further restrictions such as falling into a certain salary bracket.
This is accomplished with the use of "inverted files" that
essentially index entities under their attributes and values rather
than their identifiers. In the same way, text documents might be
retrieved *via* some unique label, or they might instead be
retrieved in accord with their *relevance* to a certain query
or topic header. The simplest notion of relevance is that the
documents should contain the terms (words or short phrases) of the
query. However, terms that are distinctive for a document should
be given more weight. Therefore a standard measure of relevance, given
a particular query term, is the *tf-idf* (*term
frequency-inverse document frequency*) for the term, which
increases (e.g.,
logarithmically) with the frequency of occurrences of
the term in the document but is discounted to the extent that it occurs
frequently in the set of documents as a whole. Summing the tf-idf's of
the query terms yields a simple measure of document relevance.


Shortcomings of this method are first, that it underrates term
co-occurrences if each term occurs commonly in the document collection
(for instance, for the query "rods and cones of the eye",
co-occurrences of *rods*, *cones*, and *eye* may
well characterize relevant documents, even though all three terms
occur quite commonly in non-physiological contexts), and second, that
relevant documents might have few occurrences of the query terms,
while containing many semantically related terms. Some of the vector
methods mentioned in connection with document clustering can be used
to alleviate these shortcomings. We may reduce the dimensionality of
the term-based vector space using LSA, obtaining a much smaller
"concept space" in which many terms that tend to co-occur
in documents will have been merged into the same dimensions
(concept). Thus sharing of concepts, rather than sharing of specific
terms, becomes the basis for measuring relevance.


Document clustering is useful when large numbers of documents need
to be organized for easy access to topically related items, for
instance in collections of patent descriptions, medical histories or
abstracts, legal precedents, or captioned images, often in hierarchical
fashion. Clustering is also useful in exploratory data analysis (e.g.,
in exploring
token occurrences in an unknown language), and indirectly supports
various NLP applications because of its utility in improving language
models, for instance in providing word clusters to be used for backing
off from specific words in cases of data sparsity.


Clustering is widely used in other areas, such as biological and
medical research and epidemiology, market research and grouping and
recommendation of shopping items, educational research, social network
analysis, geological analysis, and many others.


Document retrieval and clustering often serve as preliminary steps
in information extraction (IE) or text mining, two overlapping
areas concerned with extracting useful knowledge from documents, such
as the main features of named entities (category, roles in relation to
other entities, location, dates, etc.) or of particular types of
events, or inferring rule-like correlations between relational terms
(e.g., that purchasing of one
type of product correlates with
purchasing another).


We will not attempt to survey IE/text mining applications
comprehensively, but the next two subsections, on summarization and
sentiment analysis, are subareas of particular interest here because of
their emphasis on the semantic content of texts.



### 10.3 Knowledge extraction and summarization


Extracting knowledge or producing summaries from unstructured text are ever more
important applications, in view of the deluge of documents issuing
forth from news media, organizations of every sort, and individuals.
This unceasing stream of information makes it difficult to gain an
overview of the items relevant to some particular purpose, such as
basic data about individuals, organizations and consumer products, or
the particulars of accidents, earthquakes, crimes, company take-overs,
product maintenance and repair activities, medical research results,
and so on.


One commonly used method in both knowledge extraction and certain
types of "rote" summarization relies on the use of
extraction patterns; these are designed to match the kinds of
conventional linguistic patterns typically used by authors to express
the information of interest. For example, text corpora or
newswire might be mined for information about companies, by keying in
on known company names and terms such as "Corp.", 
".com", "headquartered at", and "annual
revenue of", as well as parts of speech and dependency
relations, and matching regular-expression patterns against local text
segments containing key phrases or positioned close to them. As
another example, summarization of earthquake reports might extract
expected information such as the epicenter of the quake, its magnitude
on the Richter scale, the time and duration of the event, affected
population centers, extent of death tolls, injuries, and property
damage, consequences such as fires and tsunamis, etc. Extraction
patterns can usually be thought of as targeting particular attributes
in predetermined attribute-value frames (e.g., a frame for company
information or a frame for facts about an earthquake), and the
filled-in frames may themselves be regarded as summaries, or may be
used to generate natural-language summaries. Early systems of this
type were FRUMP (DeJong 1982) and JASPER (Andersen et al. 1992). Among
the hundreds of more modern extraction systems, a particularly
successful one in competitions has been SRI's
"Fastus" (Hobbs et al. 1997).


Note that whether a pattern-based system is viewed as a knowledge
extraction system or summarization system depends on the text it is
applied to. If all the information of interest is bundled together in a
single, extended text segment (as in the case of earthquake reports),
then the knowledge extracted can be viewed as a summary of the segment.
If instead the information is selectively extracted from miscellaneous
sentences scattered through large text collections, with most of the
material being ignored as irrelevant to the purposes of extraction,
then we would view the activity of the system as information extraction
rather than summarization.


When a document to be summarized cannot be assumed to fall into
some predictable category, with the content structured and expressed
in a stereotyped way, summarization is usually performed by selecting
and combining "central sentences" from the document. A
sentence is central to the extent that many other sentences in the
document are similar to it, in terms of shared word content or some
more sophisticated similarity measure such as one based on the tf-idf
metric for terms, or a cosine metric in a dimensionality-reduced
vector space (thus it is as if we were treating individual sentences
as documents, and finding a few sentences whose
"relevance" to the remaining sentences is
maximal). However, simply returning a sequence of central sentences
will not in general yield an adequate summary. For example, such
sentences may contain unresolved pronouns or other referring
expressions, whose referents may need to be sought in non-central
sentences. Also, central "sentences" may actually be
clauses embedded in lengthier sentences that contain unimportant
supplementary information. Heuristic techniques need to be applied to
identify and excise the extra material, and extracted clauses need to
be fluently and coherently combined. In other cases, complex
descriptions should be more simply and abstractly paraphrased. For
example, an appropriate condensation of a sentence such as "The
tornado carried off the roof of a local farmhouse, and reduced its
walls and contents to rubble" might be "The tornado
destroyed a local farmhouse." But while some of these issues are
partially addressed in current systems, human-like summarization will
require much deeper understanding than is currently
attainable. Another difficulty in this area (even more so than in
machine translation) is the evaluation of summaries. Even human
judgments differ greatly, depending, for instance, on the sensitivity
of the evaluator to grammatical flaws, versus inadequacies in
content.


### 10.4 Sentiment analysis



Sentiment analysis refers to the detection of positive or negative
attitudes (or more specific attitudes such as belief or contempt) on
the part of authors of articles or blogs towards commercial products,
films, organizations, persons, ideologies, etc. This has become a very
active area of applied computational linguistics, because of its
potential importance for product marketing and ranking, social network
analysis, political and intelligence analysis, classification of
personality types or disorders based on writing samples, and other
areas. The techniques used are typically based on sentiment lexicons
that classify the affective polarity of vocabulary items, and on
supervised machine learning applied to texts from which word and
phrasal features have been extracted and that have been hand-labeled
as expressing positive or negative attitudes towards some
theme. Instead of manual labeling, existing data can sometimes be used
to provide *a priori* classification information. For example,
average numerical ratings of consumer products or movies produced by
bloggers may be used to learn to classify unrated materials belonging
to the same or similar genres. If fact, affective lexical categories
and contrast relations may be learnable from such data; for example,
frequent occurrences of phrases such as *great movie*
or *pretty good movie* or *terrible movie* in blogs
concerning movies with high, medium, and low average ratings may well
suggest that *great*, *pretty good*, and*terrible* belong to a contrast spectrum ranging from a very
positive to a very negative polarity. Such terminological knowledge
can in turn boost the coverage of generic sentiment lexicons. However,
sentiment analysis based on lexical and phrasal features has obvious
limitations, such as obliviousness to sarcasm and irony ( "This
is the most subtle and sensitive movie since The Texas Chainsaw
Massacre"), quotation of opinions contrasting with the author's
("According to the ads, Siri is the greatest app since iTunes,
but in fact ..."), and lack of understanding of entailments
("You'll be much better off buying a pair of woolen undies for
the winter than purchasing this item"). Thus researchers are
attempting to integrate knowledge-based and semantic analysis with
superficial word- and phrase-based sentiment analysis.



### 10.5 Chatbots and companionable dialogue agents



Current chatbots are the descendants of Weizenbaum's ELIZA
(see section 1.2), and are typically used (often with an animated
"talking head" character) for entertainment, or to engage
the interest of visitors to the websites of certain
"dotcoms". They may be equipped with large hand-crafted
scripts (keyword-indexed input-response schemas) that enable them to
answer simple inquiries about the company and their products, with some
ability to respond to miscellaneous topics and to exchange greetings
and pleasantries. A less benign application is the use of chatbots
posing as visitors to social network sites, or interactive game sites,
with the aim of soliciting private information from unwitting human
participants, or recommending websites or products to them. As a
result, many social networking sites have joined other bot-targeted
sites in using CAPTCHAS to foil bot entry.



*Companionable dialogue agents* (also called *relational agents*) have
so far relied rather heavily on chatbot techniques, i.e., authored
input patterns and corresponding outputs. But the goal is to transcend
these techniques, creating agents (often with talking heads or other
animated characters) with personality traits and capable of showing
emotion and empathy; they should have semantic and episodic memory,
learning about the user over the long term and providing services to
the user. Those services might include, besides companionship and
support: advice in some areas of life, health and fitness, schedule
maintenance, reminders, question answering, tutoring (e.g., in
languages), game playing, and internet services. Yorick Wilks has
suggested that ideally such characters would resemble "Victorian
companions", with such characteristics as politeness, discretion,
modesty, cheerfulness, and well-informedness (Wilks 2010).


However, such goals are far from being achieved, as speech
recognition, language understanding, reasoning and learning are not
nearly far enough advanced. As a noteworthy example of the state of
the art, we might mention the HWYD ("How Was Your Day")
system of Pulman et al. (2010), which won a best demonstration prize
at an autonomous agents conference. The natural language processing in
this system is relatively sophisticated. Shallow syntactic and
semantic processing is used to find instantiations of some 30
"event templates", such as ones for "argument at
work between *X* and *Y*," or "meeting
with *X* about *Y*". The interpretation process
includes reference and ellipsis resolution, relying on an information
state representation maintained by the dialogue manager. Goals
generated by the dialogue manager lead to responses via planning,
which involves instantiation and sequencing of response paradigms. The
authors report the system's ability to maintain consistent dialogues
extending over 20 minutes.


Systems of a rather different sort, aimed at clinically
well-founded health counseling, have been under development as
well. For example, the systems described in (Bickmore et
al. 2011) rely on an extensive, carefully engineered
formalization of clinically proven counseling strategies and
knowledge, expressed within a description logic (OWL) and a
goal-directed task description language. Such systems have proved to
perform in a way comparable to human counselors. However, though
dialogues are plan-driven, they ultimately consist of scripted system
utterances paired with multiple-choice lists of responses offered to
the client.


Thus companionable systems remain very constrained in the dialogue
themes they can handle, their understanding of language, and 
their ability to bring extensive general knowledge to a conversation,
let alone to use such knowledge inferentially.


### 10.6 Virtual worlds, games, and interactive fiction



Text-based adventure (quest) games, such as Dungeons and Dragons, Hunt
the Wumpus (in its original version), and Advent began to be developed
in the early and middle 1970s, and typically featured textual
descriptions of the setting and challenges confronting the player, and
allowed for simple command-line input from the player to select
available actions (such as "open box", "take
sword" or "read note"). While the descriptions of
the settings (often accompanied by pictures) could be quite elaborate,
much as in adventure fiction, the input options available to the
player were, and have largely remained, restricted to simple
utterances of the sort that can be anticipated or collected in
pre-release testing by the game programmers, and for which responses
can be manually prepared. Certainly more flexible use of NL (
"fend off the gremlin with the sword!", "If I give
you the gold, will you open the gate for me?") would enliven the
interaction between player and the game world and the characters in
it. In the 1980s and 90s text-based games declined in favor of games
based primarily on graphics and animation, though an online
interactive fiction community grew over the years that drove the
evolution of effective interactive fiction development software. A
highly touted program (in the year 2000) was Emily Short's
'Galatea', which enabled dialogue with an animated
sculpture. However, this is still an elaborately scripted program,
allowing only for inputs that can be heuristically mapped to one of
various preprogrammed responses. Many games in this genre also make
use of chatbot-like input-output response patterns in order to gain a
measure of robustness for unanticipated user inputs.




The most popular PC video games in the 1990s and beyond were Robyn and
Rand Miller's Myst, a first-person adventure game, and Maxis Software's
The Sims, a life-simulation game. Myst, though relying on messages in
books and journals, was largely nonverbal, and The Sims' chief
developer, Will Wright, finessed the problem of natural language
dialogue by having the inhabitants of SimCity babble in Simlish, a
nonsense language incorporating elements of Ukrainian, French and
Tagalog.


Commercial adventure games and visual novels continue to rely on
scripted dialogue trees--essentially branching alternative
directions in which the dialogue can be expected to turn, with
ELIZA-like technology supporting the alternatives. More sophisticated
approaches to interaction between users and virtual characters are
under development in various research laboratories, for example at the
Center for Human Modeling and Simulation at the University of
Pennsylvania, and the USC-affiliated Institute for Creative
Technologies. While the dialogues in these scenarios are still based
on carefully designed scripts, the interpretation of the user's spoken
utterances exploits an array of well-founded techniques in speech
recognition, dialogue management, and reasoning. Ongoing research can
be tracked at venues such as IVA (Intelligent Virtual Agents), AIIDE
(AI and Interactive Digital Entertainment), and AAMAS (Autonomous
Agents and Multiagent Systems).


### 10.7 Natural language user interfaces



The topic of NL user interfaces subsumes a considerable variety of
NL applications, ranging from text-based systems minimally dependent on
understanding to systems with significant comprehension and inference
capabilities in text- or speech-based interactions. The following
subsections briefly survey a range of traditional and current
applications areas.



#### Text-based question answering


Text-based QA is practical to the extent that the types of
questions being asked can be expected to have ready-made answers
tucked away somewhere in the text corpora being accessed by the QA
system. This has become much more feasible in this age of burgeoning
internet content than a few decades ago, though questions still need
to be straightforward, factual ones (e.g., 
"Who killed President Lincoln?") rather than ones requiring inference (e.g., 
"In what century did Catherine the Great live?", let alone

"Approximately how many 8-foot 2-by-4s do I need to build a
4-foot high, 15-foot long picket fence?").


Text-based QA begins with question classification (e.g., yes-no
questions, who-questions, what-questions, when-questions, etc.),
followed by information retrieval for the identified type of question,
followed by narrowing of the search to paragraphs and finally sentences
that may contain the answer to the question. The successive narrowing
typically employs word and other feature matching, and ultimately
dependency and role matching, and perhaps limited textual inference to
verify answer candidates. Textual inference may, for instance, use
WordNet hypernym knowledge to try to establish that a given candidate
answer sentence supports the truth of the declarative version of the
question. Since the chosen sentence(s) may contain irrelevant material
and anaphors, it remains to extract the relevant material (which may
also include supporting context) and generate a well-formed,
appropriate answer. Many early text-based QA systems up to 1976 are
discussed in Bourne & Hahn 2003. Later surveys (e.g., Maybury
2004) have tended to include the full spectrum of QA methods, but TREC
conference proceedings 
(https://trec.nist.gov/) 
feature numerous papers
on implemented systems for text-based QA.


In open-domain QA, many questions are concerned with properties of
named entities, such as birth date, birth place, occupation, and other
personal attributes of well-known present and historical individuals,
locations, ownership, and products of various companies, facts about
consumer products, geographical facts, and so on. For answering such
questions, it makes sense to pre-assemble the relevant factoids into a
large knowledge base, using knowledge acquisition methods like those in
section 8. Examples of systems containing an abundance of factoids
about named entities are several developed at the University of
Washington, storing factoids as text fragments, and various
systems that map harvested factoids into RDF
(Resource Description Framework) triples
 (see references in Other Internet Resources). Some
of these systems obtain their knowledge not only from open information
extraction and targeted relation extraction, but also from such sources
as Wikipedia "infoboxes" and (controlled) crowdsourcing. Here we are
also stretching the notion of question answering, since several of the
mentioned systems require the use of key words or query patterns for
retrieval of factoids.


From a general user perspective, it is unclear how much added
benefit can be derived from such constructed KBs, given the remarkable
ability of Google and other search engines to provide rapid answers
even to such questions as "Which European countries are
landlocked?" (typed without quotes--with quotes, Google
finds the top answer using True Knowledge), or "How many Supreme
Court justices did Kennedy appoint?" Nonetheless, both Google
and Microsoft have recently launched vast "knowledge
graphs" featuring thousands of relations among hundreds of
millions of entities. The purpose is to provide direct answers (rather
then merely retrieved web page snippets) to query terms and natural
language questions, and to make inferences about the likely intent of
users, such as purchasing some type of item or service.



#### Database front-ends



Natural-language front ends for databases have long been considered an
attractive application of NLP technology, beginning with such systems
as LUNAR (Woods et al. 1972) and REL (Thompson et al. 1969; Thompson
& Thompson 1975). The attractiveness lies in the fact that
retrieval and manipulation of information from a relational (or other
uniformly structured) database can be assumed to be handled by an
existing db query language and process. This feature sharply limits
the kinds of natural language questions to be expected from a user,
such as questions aimed at retrieving objects or tuples of objects
satisfying given relational constraints, or providing summary or
extremal properties (longest rivers, lowest costs, and the like) about
them. It also greatly simplifies the interpretive process and
question-answering, since the target logical forms--formal db
queries--have a known, precise syntax and are executed
automatically by the db management system, leaving only the work of
displaying the computed results in some appropriate linguistic,
tabular or graphical form.


Numerous systems have been built since then, aimed at applications
such as navy data on ships and their deployment
(Ladder: Hendrix et al. 1978),
land-use planning (Damerau 1981), geographic QA
(Chat-80: Pereira & Warren 1982),
retrieval of company records and product records for insurance
companies, oil companies, manufacturers, retailers, banks,
etc. (Intellect: Harris 1984), compilation
of statistical data concerning customers, services,
assets, *etc.*, of a company (Cercone et al. 1993), and
many more (e.g., see Androutsopoulos & Ritchie 2000). However, the
commercial impact of such systems has remained scant, because they
have generally lacked the reliability and some of the functionalities
of traditional db access.


#### Inferential (knowledge-based) question answering


We have noted certain limited inferential capabilities in text-based
QA systems and NL front ends for databases, such as the ability to
confirm entailment relations between candidate answers and questions,
using simple sorts of semantic relations among the terms involved, and
the ability to sort or categorize data sets from databases and compute
averages or even create statistical charts.


However, such limited, specialized inference methods fall far short
of the kind of general reasoning based on symbolic knowledge that has
long been the goal in AI question answering. One of the earliest
efforts to create a truly inferential QA system was the ENGLAW project
of L. Stephen Coles (Coles 1972). ENGLAW was intended as a prototype
of a kind of system that might be used by scientists and engineers to
obtain information about physical laws. It featured a KB of axioms (in
first-order logic) for 128 important physical laws, manually coded
with the aid of a reference text. Questions (such as "In the
Peltier Effect, does the heat developed depend on the direction of the
electric current?") were rendered into logic via a
transformational grammar parser, and productions (aided by various
Lisp functions) that map phrase patterns to logical expressions. The
system was not developed to the point of practical usefulness, but its
integration of reasoning and NLP technologies and its methods of
selectively retrieving axioms for inferential QA were noteworthy
contributions.


An example of a later larger-scale system aimed at practical goals
was BBN's JANUS system (Ayuso et al.
1990). This was intended for naval
battle management applications, and could answer questions about the
locations, readiness, speed and other attributes of ships, allowing for
change with the passage of time. It mapped English queries to a very
expressive initial representation language with an "intension" operator
to relate formulas to times and possible worlds, and this was in turn
mapped into the NIKL description logic, which proved adequate for the
majority of inferences needed for the targeted kinds of QA.


Jumping forward in time, we take note of the web-based
Wolfram|Alpha (or WolframAlpha) answer engine, developed by Wolfram
Research and consisting of 15 million lines of Mathematica code
grounded in curated data bases, models, and algorithms for thousands
of different domains. (Mathematica is a mathematically oriented
high-level programming language developed by the British scientist
Stephen Wolfram.) The system is tilted primarily towards quantitative
questions (e.g., "What is the GDP of France?", or
"What is the surface area of the Moon?") and often
provides charts and graphics along with more direct answers. The
interpretation of English queries into functions applied to various
known objects is accomplished with the pattern matching and symbol
manipulation capabilities of Mathematica. However, the comprehension
of English is not particularly robust at the time of writing. For
example "How old was Lincoln when he died?", "At
what age did Lincoln die?" and other variants were not
understood, though in many cases of misunderstanding, Wolfram|Alpha
displays enough retrieved information to allow inference of an
answer. A related shortcoming is that Wolfram|Alpha's quantitative
skills are not supplemented with significant qualitative reasoning
skills. For example, "Was Socrates a man?" (again, at the
time of writing) prompts display of summary information about
Socrates, including an image, but no direct answer to the
question. Still, Wolfram|Alpha's quantitative abilities are not only
interesting in stand-alone mode, but also useful as augmentations of
search engines (such as Microsoft Bing) and of voice-based personal
assistants such as Apple's Siri (see below).


Another QA system enjoying wide recognition because of its
televised victory in the Jeopardy! quiz show is IBM's
"Watson" (Ferrucci 2012; Ferrucci et al. 2010; Baker
2011). Like Wolfram|Alpha, this is in a sense a brute force program,
consisting of about a million lines of code in Java, C++, Prolog and
other languages, created by a core team of 20 researchers and software
engineers over the course of three years. The program runs 3000
processes in parallel on ninety IBM Power 750 servers, and has access
to 200 million pages of content from sources such as Wordnet,
Wikipedia (and its structured derivatives YAGO and DBpedia), thesauri,
newswire articles, and literary texts, amounting to several terabytes
of human knowledge. (This translates into roughly 1010
clausal chunks--a number likely to be around 2 orders of
magnitude greater than the number of basic facts over which any one
human being disposes.)


Rather than relying on any single method of linguistic or semantic
analysis, or method of judging relevance of retrieved passages and
textual "nuggets" therein, Watson applies multiple methods to the
questions and candidate answers, including methods of question
classification, focal entity detection, parsing, chunking, lexical
analysis, logical form computation, referent determination, relation
detection, temporal analysis, and special methods for question-answer
pairs involving puns, anagrams, and other twists common in Jeopardy!.
Different question analyses are used separately to retrieve relevant
documents, and to derive, analyze and score potential answers from
passages and sentences in those documents. In general, numerous
candidate answers to a question are produced, and their analyses
provide hundreds of features whose weights for obtaining ranked answers
with corresponding confidence levels are learned by ML methods applied
to a corpus of past Jeopardy! questions and answers (or officially,
answers and questions, according to the peculiar conceit of the
Jeopardy! protocol). Watson's wagers are based on the confidence levels
of its potential answers and a complex regression model.


How well does Watson fit under our heading of inferential,
knowledge-based QA? Does it actually *understand* the questions
and the answers it produces? Despite its impressive performance
against Jeopardy! champions, Watson reasons, and understands English
in only very restricted senses. The program exploits the fact that the
target of a Jeopardy! question is usually a named entity, such
as *Jimmy Carter, Islamabad*, or *Black Hole of
Calcutta*, though other types of phrases are occasionally
targeted. Watson is likely to find multiple sentences that mention a
particular entity of the desired type, and whose syntactic and
semantic features are close to the features of the question, thereby
making the named entity a plausible answer without real understanding
of the question. For example, a "recent history" question
asking for the president under whom the US gave full recognition to
Communist China (Ferrucci 2012) might well zero in on such sentences
as



> 
> Although
> he was the president who restored full diplomatic
> relations with China in 1978, Jimmy Carter has never visited that country
> ...
> (New York Times, June 27, 1981)
> 
> 
> 
> 



or




> 
> 
> Exchanges
> between the two countries' nuclear scientists had begun
> soon after President Jimmy Carter officially recognized China in 1978.
> (New York Times, Feb. 2, 2001)
> 
> 
> 



While the links between such sentences and the correct answer are
indirect (e.g., dependent on resolving *he* and *who* to
*Jimmy Carter*, and associating *restored diplomatic
relations* with *recognized*, and *Communist China*
with *China*), correct analysis of those links is not a
requirement for success--it is sufficient for the cluster of
sentences favoring the answer Jimmy Carter (in virtue of their word
and phrasal content and numerous other features) to provide a larger
net weight to that answer than any competing clusters. This type of
statistical evidence combination based on stored texts seems unlikely
to provide a path to the kind of understanding that even first-graders
betray in answering simple commonsense questions, such as "How
do people keep from getting wet when it rains?", or "If
you eat a cookie, what happens to the cookie?" At the same time,
vast data banks utilized in the manner of Watson can make up for
inferential weakness in various applications, and IBM is actively
redeveloping Watson as a resource for physicians, one that should be
able to provide diagnostic and treatment possibilities that even
specialists may not have at their fingertips. In sum, however, the
goal of open-domain QA based on genuine understanding and
knowledge-based reasoning remains largely unrealized.



#### Voice-based web services and assistants



Voice-based services, especially on mobile devices, are a rapidly
expanding applications area. Services range from organizers (for
grocery lists, meeting schedules, reminders, contact lists, etc.), to
in-car "infotainment" (routing, traffic conditions, hazard warnings,
iTunes selection, finding nearby restaurants and other venues, etc.),
to enabling use of other miscellaneous apps such as email dictation,
dialing contacts, financial transactions, reservations and placement of
orders, Wikipedia access, help-desk services, health advising, and
general question answering. Some of these services (such as
dialing and iTunes selection) fall into the category of hands-free
controls, and such controls are becoming increasingly important in
transport (including driverless or pilotless vehicles), logistics
(deployment of resources), and manufacturing. Also chatbot
technology and companionable dialogue agents (as discussed in 
section 10.5) 
are serving as general backends to more specific voice-based
services.


The key technology in these services is of course speech
recognition, whose accuracy and adaptability has been gradually
increasing. The least expensive, narrowly targeted systems
(e.g., simple organizers) exploit strong expectations about user
inputs to recognize, interpret and respond to those inputs; as such
they resemble menu-driven systems. More versatile systems, such as car
talkers that can handle routing, musical requests, searches for
venues, etc., rely on more advanced dialogue management
capabilities. These allow for topic switches and potentially for the
attentional state of the user (e.g., delaying answering a driver's
question if the driver needs to attend to a turn). The greatest
current "buzz" surrounds advanced voice-based assistants, notably
iPhone's Siri (followed by Android's Iris, True Knowledge's Evi,
Google Now, and others). While previous voice control and dictation
systems, like Android's Vlingo, featured many of the same
functionalities, Siri adds personality and improved dialogue handling
and service integration--users feel that they are interacting
with a lively synthetic character rather than an app. Besides Nuance
SR technology, Siri incorporates complex techniques that were to some
extent pushed forward by the Calo (Cognitive Assistant
that Learns and Organizes) project carried out by SRI International
and multiple universities from 2003-2008 (Ambite et al. 2006;
CALO [see Other Internet Resources]). 
These techniques include aspects of NLU, ML, goal-directed and
uncertain inference, ontologies, planning, and service delegation. But
while delegation to web services, including Wolfram|Alpha QA, or
chatbot technology provides considerable robustness, and there is
significant reasoning about schedules, purchasing and other targeted
services, general understanding is still very shallow, as users soon
discover. Anecdotal examples of serious misunderstandings are
"Call me an ambulance" eliciting the response "From
now on I will call you 'an ambulance'". However, the
strong interest and demand in the user community generated by these
early (somewhat) intelligent, quite versatile assistants is likely to
intensify and accelerate research towards ever more life-like virtual
agents, with ever more understanding and common sense.


### 10.8 Collaborative problem solvers and intelligent tutors



We discuss collaborative problem solving systems (also referred to as
"mixed-initiative" or "task-oriented" dialogue
systems) and tutorial dialogue systems (i.e., tutorial systems in
which dialogue plays a pivotal role) under a common heading because
both depend on rather deep representations or models of the domains
they are aimed at as well as the mental state of the users they
interact with.



However, we should immediately note that collaborative problem solving
systems typically deal with much less predictable domain situations
and user inputs than tutorial systems, and accordingly the former
place much greater emphasis on flexible dialogue handling than the
latter. For example, collaborators in emergency evacuation (Ferguson
and Allen 1998, 2007) need to deal with a dynamically changing domain,
at the same time handling the many dialogue states that may occur,
depending on the participants' shared and private beliefs, goals,
plans and intentions at any given point. By contrast, in a domain such
as physics tutoring (e.g., Jordan et al. 2006; Litman and
Silliman 2004), the learner can be guided through a network of
learning goals with authored instructions, and corresponding to those
goals, finite-state dialogue models can be designed that classify
student inputs at each point in a dialogue and generate a prepared
response likely to be appropriate for that input.



It is therefore not surprising that tutorial dialogue systems are
closer to commercial practicality, with demonstrated learning benefits
relative to conventional instruction in various evaluations, than
collaborative problem solving systems for realistic applications.
Tutorial dialogue systems have been built for numerous domains and
potential clienteles, ranging from K-12 subjects to computer literacy
and novice programming, qualitative and quantitative physics, circuit
analysis, operation of machinery, cardiovascular physiology, fire
damage control on ships, negotiation skills, and more (e.g., see Boyer
et al. 2009; Pon-Barry et al. 2006). Among the most successful
tutorial systems are reading tutors (e.g., Mostow and Beck 2007; Cole
et al. 2007), since the materials presented to the learner (in a
"scaffolded" manner) are relatively straightforward to
design in this case, and the responses of the learner, especially when
they consist primarily of reading presented text aloud, are relatively
easy to evaluate. For the more ambitious goal of fostering reading
comprehension, the central problem is to design dialogues so as to
make the learner's contributions predictable, while also making the
interaction educationally effective (e.g., Aist and Mostow 2009).


Some tutoring systems, especially ones aimed at children, use
animated characters to heighten the learner's sense of
engagement. Such enhancements are in fact essential for systems
aimed at learners with disabilities like deafness (where mouth and
tongue movements of the virtual agent observed by the learner can help
with articulation), autism, or aphasia (Massaro et al. 2012; Cole et
al. 2007). As well, if tutoring is aimed specifically at
training
interpersonal skills, implementation of life-like characters (virtual
humans) becomes an indispensable part of system development (e.g., Core
et al. 2006; Campbell et al. 2011).


Modeling the user's state of mind in tutoring systems is primarily a
matter of determining which of the targeted concepts and skills have,
or have not yet, been acquired by the user, and diagnosing
misunderstandings that are likely to have occurred, given the session
transcript so far. Some recent experimental systems can also adapt
their strategies to the user's apparent mood, such as frustration or
boredom, as might be revealed by the user's inputs, tone of voice, or
even facial expressions or gestures analyzed via computer vision. 
Other prototype systems can be viewed as striving towards more general
mental modeling, by incorporating ideas and techniques from
task-oriented dialogue systems concerning dialogue states, dialogue
acts, and deeper language understanding (e.g., Callaway et al. 2007).


In task-oriented dialogue systems, as already noted, dialogue
modeling is much more challenging, since such systems are expected not
only to contribute to solving the domain problem at hand, but to
understand the user's utterances, beliefs, and intentions, and to hold
their own in a human-like, mixed-initiative dialogue. This requires
domain models, general incremental collaborative planning methods,
dialogue management that models rational communicative interaction, and
thorough language understanding (especially intention recognition) in
the chosen domain. Prototype systems have been successfully built
for domains such as route planning, air travel planning, driver and
pedestrian guidance, control and operation of external devices,
emergency evacuation, and medication advising (e.g., Allen et al. 2006;
Rich and Sidner 1998; Buhler and Minker 2011; Ferguson and Allen
1998, 2007), and these hold very significant practical promise.
However, systems that can deal with a variety of reasonably complex
problems, especially ones requiring broad commonsense knowledge about
human cognition and behavior, still seem out of reach at this time.


### 10.9 Language-enabled robots



As noted at the beginning of 
section 10, robots are beginning to be
equipped with web services, question answering abilities, chatbot
techniques (for fall-back and entertainment), tutoring functions, and
so on. The transfer of such technologies to robots has been slow,
primarily because of the very difficult challenges involved in just
equipping a robot with the hardware and software needed for basic
visual perception, speech recognition, exploratory and goal-directed
navigation (in the case of mobile robots), and object manipulation.
However, the keen public interest in intelligent robots and their
enormous economic potential (for household help, eldercare, medicine,
education, entertainment, agriculture, industry, search and rescue,
military missions, space exploration, and so on) will surely continue
to energize the drive towards greater robotic intelligence and
linguistic competence.


A good sense of the state of the art and difficulties in human-robot
dialogue can be gained from (Scheutz et
al. 2011). Some of the dialogue
examples presented there, concerning boxes and blocks, are reminiscent
of Winograd's shrdlu, but they also exhibit the
challenges involved in
real interaction, such as the changing scenery as the robot moves,
speech recognition errors, disfluent and complex multi-clause
utterances, perspective-dependent utterances (
"Is the red box to the left of the blue box?"), and deixis 
("Go down there"). In
addition, all of this must be integrated with physical action planned
so as to fulfill the instructions as understood by the robot. While the
ability of recent robots to handle these difficulties to some degree is
encouraging, many open problems remain, such as the problems of speech
recognition in the presence of noise, better, broader linguistic
coverage, parsing, and dialogue handling, adaptation to novel problems,
mental modeling of the interlocutor and other humans in the
environment, and greater general knowledge about the world and the
ability to use it for inference and planning (both at the domain level
and the dialogue level).


While task-oriented robot dialogues involve all these challenges,
we should note that some potentially useful interactions with
"talking" robots require little in the way of linguistic
skills. For example, the Rubi robot described in
(Movellan et al. 2009), displayed objects on its
screen-equipped "chest" to toddlers, asking them to touch
and name the objects. This resulted in improved word learning by the
toddlers, despite the simplicity of the interaction. Another example
of a very successful talking robot with no real linguistic skills was
the "museum tour guide" Rhino
(Burgard et al. 1999). Unlike Rubi it was able
to navigate among unpredictably moving humans, and kept its audience
engaged with its prerecorded messages and with a display of its
current goals on a screen. In the same way, numerous humanoid robots
(for example, Honda's Asimo) under past and present development across
the world still understand very little language and rely mostly on
scripted output. No doubt their utility and appeal will continue to
grow, thanks to technologies like those mentioned above--games,
companionable agent systems, voice-based apps, tutors, and so on; and
these developments will also fuel progress on the deeper aspects of
perception, motion, manipulation, and meaningful dialogue.