Chapter 7

Natural Language
Processing

0

PREVIEW

The documents and user queries under consideration in information retrieval
are often available as natural language formulations. It is important therefore to
be aware of the automatic methods currently used to process natural language
texts. This chapter describes the state of the art in the automatic processing of
natural language material with emphasis On applications in information re­trieval.
The various levels of linguistic methods are examined first and the role oflinguistic methods in information retrieval is described. This is followed by ageneral examination of modern language understanding systems. The compo­
nents of language processing systems are then covered in detail with emphasison the syntactic process which is of greatest interest in information retrieval.
The main features of several grammatical models are described, includingphrase structure grammars, transformational grammars, and augmented transi­tion network grammars. This is followed by a discussion of applications of syn­tactic analysis in information retrieval.
The full scope of language understanding may not be needed in information
retrieval. Language understanding is, however, an essential component in thedesign of question-answering systems. The chapter closes with a description of257

CHAPTER 7

258

linguistic methods useful for question answering. The structure of knowledge
representation systems is covered and the language processing component ofcertain well-known experimental question-answering systems is described toprovide an example of the potential of the currently available automatic lan­
guage processing techniques.
1

COMPONENTS OF NATURAL LANGUAGE SYSTEMSAInterest in Natural Language Processing

This chapter is devoted to a study of the problems which arise when natural
language data are processed by computers. In particular, the main approaches
to natural language processing are covered, and an attempt is made to provide astate-of-the-art view of different efforts in this area.
One may want to question the wisdom of examining linguistic proceduresin an information retrieval context, particularly when the material in the earlier
chapters makes it clear that linguistic methods play only a minor role in re­trieval at the present time. The fact is however that a large part of the informa­tion stored in bibliographic retrieval systems consists of natural language data,
and that many users would prefer, given the choice, to approach a retrieval sys­
tem by using natural language formulations of their information needs. Further­more, even if the currently usable language processing techniques appear inad­
equate for full utilization under operational retrieval conditions, there is always
the hope that new developments may render the linguistic techniques more at­
tractive in the future.
Precisely what does one expect to gain in using linguistic approaches in the
retrieval context? The most immediate aim is surely the possible use of freelanguage formulations by retrieval system users, both for the submission of ini­tial query statements and for the various interactive processes in which queries
or documents are adjusted based on information obtained from the user popula­tion. The use of natural language search statements could raise the efficiency aswell as the effectiveness of the retrieval operations by making possible the for­mulations of precise requests that correctly reflect user needs and by simpli­
fying the user-system interactions.
A second application of natural language processing is the use of complex
analysis techniques for the content representation of the input documents. In­
deed, when the analysis system is confined to the use of single words for thecontent description of queries and documents, a user query dealing with “com­putational complexity” and indexed by the terms “compute” and “complex”
is just as likely to cover extraneous topics such as “computation with complex
numbers” as the actual subject area of interest. Of course, phrases can be auto­
matically assigned to documents and search requests by using term co-occur­
rence statistics and word adjacency operators; but the statistical techniques areimperfect. In particular, they do not distinguish between cases such as “blind
Venetian” and “ Venetian blind.” However, if accurate linguistic techniques
were usable to combine single terms into meaningful larger units, then com-

NATURAL LANGUAGE PROCESSING

259

plete structured index descriptions might be generated consisting, for example,of noun-verb-noun combinations or of sentence units of even larger scope. Sub­stantial improvements in text analysis and hence in retrieval should result.
Another important problem in retrieval is the construction of synonym dic­tionaries and thesauruses in which related words are grouped into affinity
classes. Under current conditions thesauruses are constructed manually, or au­
tomatically by using word co-occurrence information. However, if linguistic
descriptions were available to characterize the individual text units, a thesau­
rus class might be defined as the set of words occurring in similar contexts inthe documents of a collection.
In addition to the free-language query submission and automatic indexing
applications, a variety of extensions to the normal information retrieval process
come easily to mind in which sophisticated language analysis techniques basedon the use of deductive and contextual information obtainable from texts would
play a major role. The following possibilities may be cited in this connection[1-5]:
1 Automatic question-answering systems might be designed where thesystem is expected to give explicit answers to incoming search requests(“What is the boiling point of water?” Answer: 100 degrees Celsius), as op­
posed to merely furnishing bibliographic references expected to contain the an­swer.
2 Automatic abstracting systems could become practical where the docu­
ment texts are automatically reduced to abstract-length excerpts that informthe reader about the content of the corresponding documents.
3 Foreign language documents could be treated automatically making it
possible, for example, to extend the automatic indexing techniques to include
documents originally available in languages other than English.
4 Sophisticated treatment of the full text of natural language documents
could be considered as required, for example, for text analysis and text concor­
dance generation.
Because of the difficulties that are inherent in a complete linguistic analysis
of natural language texts, many of these problems are currently approached bycreating a simplified situation— for example, by restricting the allowable dis­course area to a narrow topic slice, or by imposing limitations on the variety ofnatural language forms that are actually handled by the system. These restric­
tions might be given up in the future, assuming sufficient gains in understanding
the natural language phenomena.
B

Levels of Language Processing

It is customary to recognize several different levels of language processing.
These may be characterized as the phonological, morphological, lexical, syn­tactic, semantic, and pragmatic levels.
The phonological level deals with the treatment of speech sounds asneeded, for example, for the handling of speech understanding or speech gen-260

CHAPTER 7

eration systems. This level of linguistic processing is not of immediate interestin the retrieval context and is not discussed further in this volume.
The morphological level of linguistic processing is concerned with the pro­cessing of individual word forms and of recognizable portions of words. The
recognition and removal of word suffixes and prefixes and the generation ofword stems (used earlier to enhance search recall) are based on morphologicalknowledge.
The lexical level deals with the procedures operating on full words. In in­formation retrieval this covers operations such as common word deletion, dic­tionary processing of individual words, and the replacement of words by the­saurus classes. In syntactic parsing applications where an attempt is made toobtain a structural description of a sentence, a preliminary lexical operation
normally identifies a set of linguistic features (for example, noun, adjective,
preposition, etc.) for each text word to be used later in the main syntactic anal­
ysis process.
The syntactic level is designed to group the words of a sentence into struc­tural units such as prepositional phrases, and subject-verb-object groupingsthat collectively represent the grammatical structure of the sentence. A syntac­
tic analysis is normally based on the surrounding structure in which the individ­
ual words are embedded in a sentence and on the use of syntactic featurescharacterizing the individual words. Most currently available syntactic analysis
systems are sufficiently advanced to permit the recognition of the principal
structural characteristics of English text.
The semantic level adds contextual knowledge to the purely syntactic pro­
cess in order to restructure the text into units that represent the actual meaningof a text. Thus a syntactic analysis for the utterance “John is easy to please”
would designate “John” as the subject of the sentence, whereas the semantic
process would designate “John” as the complement, as indicated by the se­mantic interpretation, “It is easy for someone (unnamed) to please John.” Avariety of such preestablished semantic characterizations of the terms are nor­mally used to obtain satisfactory semantic interpretations.
Finally, the pragmatic level uses additional information about the social
environment in which a given document exists, about the relationships that
normally prevail in the world between various entities, and about the world-atlarge to help in the text interpretation. For example, knowledge of the size ofpigs and pens, respectively, and of the normal habitat of pigs permits an unam­
biguous interpretation of the sentence, “The pig is in the pen.”
The morphological and lexical operations were examined in Chapter 3 aspart of the automatic indexing operations. The principal interest in the present
discussion is then confined to the syntactic, semantic, and pragmatic levels of
linguistic processing.
In dealing with the various linguistic procedures, one must consider the
degree to which the individual levels are easily recognized and independent ofeach other. Unhappily this question, like so many others in language pro­cessing, is pontroversial. All knowledgeable observers agree that automatic

NATURAL LANGUAGE PROCESSING

261

language processing raises complicated issues, that the use of the context inwhich individual words occur is essential for automatic text interpretation, andthat syntax and semantics are related in that semantic knowledge is needed to
avoid ambiguities in the syntax, whereas syntactic information helps in produc­
ing useful semantic output [6].
Unfortunately, beyond the general realization that the language analysis
task is difficult, there is little agreement about how to handle the job. It is un­
clear which levels of language processing are most important and how the cor­
responding techniques are best applied. One school of thought points to the factthat human processes are highly integrated and concludes that a language anal­
ysis system must necessarily be based on the global use of many different ap­
proaches at each point in the process:U nderstanding is a com pletely integrated process; the idea o f building modular sy s­
tem s (w here, for exam ple, the syntactic phase is isolated from the sem antic) has
hampered advances in parsing, b ecau se the full range o f our know ledge should o b ­viously be available to help disam biguate, find appropriate word sen ses, and ju st as
importantly help u s know what to ignore [7].

This viewpoint is supported by the fact that in some of the existing question-an­
swering systems dealing with restricted topic areas, a sophisticated syntactic
analysis system proves unnecessary, since the few semantic patterns acceptedby these systems are completely understood and procedures to handle thesepatterns can be provided in advance.
Many other observers prefer the modular viewpoint of language analysis.
This uses a large dictionary storing linguistic features for the words in the lan­
guage, and a grammar designed to produce a rigorous analysis of the possible
sentences in the language. A semantic analysis system is then added to trans­
form the syntactic output into formalized units of meaning. Most people still
feel that a syntactic analysis system is essential when unrestricted natural lan­
guage input is processed [8]. Since the syntax alone can be helpful in certain
retrieval tasks, whereas the semantic processing is not as yet well understood,
a good deal of emphasis is placed on syntax in the present chapter.
C

Language Understanding Systems

The earliest uses of computers for language processing date back to the 1950s
when programs were written that could translate short excerpts of text fromone language to another— often from Russian or German into English [9,10].
Substantial effort was invested in the construction of mechanized dictionaries
useful for the translation of large unrestricted texts. But when these dictionJaries were actually put to the test by using them on large samples of input, it
turned out that the translation task became too difficult. New programs had tobe written to take care of problems that had not been met in considering thq
earlier text samples, and the new modifications interfered with the earlier pro­grams which were originally thought to be adequate. When it proved impossi-

262

CHAPTER 7

ble to reach a steady-state condition after some 10 or 15 years of work, the ma­chine translation work was generally given up in favor of more fundamental
work in language analysis and understanding [11].
Thus small text samples were intensively studied in an attempt to deter­mine all the information contained in or derivable from the sample, and systems
were built that could automatically answer direct questions dealing with thespecific and restricted topic areas covered by particular text samples. Unfortu­
nately, the lessons learned earlier through the machine translation work had tobe learned all over again: while it was comparatively simple to deal with 250word text samples and 300-word dictionaries, the extensions to larger portionsof the language were neither assured nor forthcoming even after substantial ef­
fort.
While the general understanding of how human beings analyze language
has been increased by recent psychological experiments, it has not been possi­
ble so far to translate this understanding into automatic programs that can satis­
factorily process large samples of unrestricted natural language texts [12].
The early approaches to language analysis tended to be word-oriented.
Each word was assumed to represent one or more well-defined units of mean­ing, and when words were combined the available grammars more often thannot produced a number of acceptable output analyses. For example, given stan­
dard dictionary entries for the words “time” and “flies” as
Time: singular noun or transitive verb
Flies: plural noun or transitive verb or intransitive verb
many standard grammatical analysis systems would produce at least two ac­
ceptable results for the sentence, “Time flies” :1 A declarative statement in which “time” is interpreted as a noun sub­ject of the sentence and “flies” is the intransitive verb
2 An imperative sentence where “time” is interpreted as a transitive
verb and “flies” is the plural noun complement
The first interpretation is of course the one normally assumed whereas thelatter must be termed semantically improbable because flies are not the type of
insects that are normally timed. For longer sentences, such.as for example thewell-known “Time flies like an arrow,” the number of acceptable syntactic out­
puts could be much larger than two.
Refinements were introduced into the early syntactic analysis systems in
the form of transformations defined on the standard syntactic output. Thus
given an accepted syntactic interpretation for the sentence “ John hit the ball”
another acceptable analysis would be produced for the passive form “The ball
was hit by John.” Formally defined transformations could then account forequivalences between active and passive moods, and between declarative andthe corresponding interrogative forms of a sentence.

NATURAL LANGUAGE PROCESSING

263

Even though the complexity of the syntactic analysis systems grew rap­
idly, it became clear that many issues of syntactic “well-formed-ness” were
not explainable by syntax alone, and that a sentence-by-sentence analysis
based purely on syntax was not sufficient to analyze many texts. For example,
it is not possible using simple syntactic considerations to explain the fact thatthe sentence “John and his sister went to Paris” is acceptable, whereas“John’s sister and he went to Paris” is not.
Clearly some semantic features must be incorporated in the syntactic pro­
cess before a sentence can finally be interpreted. For example, by recognizing
semantic usages for ambiguous words such as “ball,” and taking into accountthe context in which a given word occurs, it becomes possible to produce cor­
rect interpretations for sentences such as “He played with the ball” and “Hewent to the ball” [13].
One direct link between syntax and semantics is provided by the introduc­tion of case grammar [14]. In case grammar a sentence is considered as a tense­
less proposition consisting of a verb and related noun phrases and embedded
sentences, plus a modularity specifying tense, mood, and aspect. By using a dic­tionary to store partial semantic characterizations, Or cases, for each noun, andthen classifying the verbs according to which cases could be related to them,
one could then specify the permissible patterns in the language by using a finite
set of relations between verbs and nouns (also known as case fram es). Typicalcases for nouns are agent (A), object (O), instrument (I), indirect object (D),and so on. Typical case frames for the word “write” could be(A)— with (I)(A )-(O )(A)— to (D)(A)— (O) to (D) with (I)as in “The author writes with a pen,” “The author writes a letter,” “The au­thor writes to his publisher,” “The author writes a letter to his publisher with apen.” It was found experimentally that a relatively small number of caseframes could account for a vast number of different sentences in the language.
The case frames could also effectively constrain the accepted utterances to in­clude meaningful sentences only.
In recent years, most of the interest in computational linguistics has been
devoted to the integration of various linguistic approaches into complete lan­
guage processing systems. A complete language processing system of the kind
useful in information retrieval can then be viewed as a three-part structure [1]:1 First a standardized, formal representation is constructed of the mean­ing of each sentence or unit of discourse; typically units of meaning are ex­
tracted for each component from a dictionary, and the components are thenassembled into a formal sentence representation using the constraints imposedby the syntax.

264

CHAPTER 7

2 This formally restricted input is then compared with a stored knowl­edge base in order to augment the initial descriptions and to identify additional
relationships between entities.
3 Finally, a desired task is performed which uses the combined informa­tion provided by the available input augmented by the stored knowledge; forexample, inference procedures may be used to derive and formulate answers torequests for information.
A feeling exists that knowledge may be organized around conceptual enti­
ties such as objects, relations, events, and scenes, with associated descriptions
and procedures. Given such conceptual structures the reasoning process— forexample, the process needed to generate answers in response to incoming
queries— consists in a matching and recognition process. The objects andevents provided at the input (for example, the incoming user queries) are com­pared against stored knowledge structures. Then special “reasoning strate­gies” including inferencing capabilities are used to derive a desired output.
Many people feel that the information included in the stored knowledge struc­tures should be clustered so that similar objects may appear in close proximity.
In this way related elements can share common properties and the comparisonand search process in the knowledge base may be simplified [15].
Beyond these general perceptions about knowledge representation, there
is no agreement about what structures are actually needed and how they are to
be represented in an operational system. One unsolved problem concerns theusefulness of representing knowledge by a small number of primitive concepts.
If useful semantic primitives could be identified, the construction and manipu­
lation of the knowledge base would be substantially simplified. All processes
could then be reduced to the manipulation of only those primitive entities forwhich specific rules would be established.
In the so-called conceptual dependency model only six conceptual catego­ries are recognizedincluding real world objects, real world actions, attributesof objects, attributes of actions, times, and locations. These categories are re­lated in only 16 different ways [16]. In situations where the number of primitive
concepts is small, the reasoning and inferencing processes are relatively sim­ple. Since only a small number of entities are available in each category, thepossible events that may occur can be established and stored in advance. For
example, five “acts” are allowed in conceptual dependency describing physi­
cal actions that people can perform (termed “propel,” “move,” “ingest,”“ expel,” and “grasp”). For each act, a small set of inferences is defined as true
with varying degrees of certainty when the particular act occurs.
Many people, however, do not believe that it is possible or realistic to rep­resent knowledge using semantic primitives. Instead it is suggested that humanbeings use a variety of redundant descriptions to represent each object, andthat the particular description used in a given instance depends on circum­
stances. The holistic view of knowledge representation is based on a redundant
characterization of each object consisting in part of comparisons with other ob-

NATURAL LANGUAGE PROCESSING

265

jects. When enough comparisons with other objects are stored, a given entity isthen assumed to be completely described. A table might, for example, be char­acterized in part by saying that it is more similar to a chair than to a lamp. As
more information is obtained about an object, the new data are simply added tothe existing descriptions.
Regardless of one’s views about the primitive components in a knowledge
base, it becomes necessary to make a choice about the structures actually used
to represent knowledge and the types of knowledge to be represented by them.
Two principal structural representations are described in the literature. The
first is the semantic graph or semantic net [17]. Such a graph consists of nodes
and of branches, or links connecting certain pairs of nodes. In a semantic graphthe nodes are used to represent the main concepts of interest, including objects,
events, assertions, actions, abstractions, and functions, as well as attributes
and characteristics of objects. Links between nodes identify hierarchical andcontextual relations between the concepts, as well as other special information
relating to the concepts. The nodes of a particular semantic net might, for ex­
ample, represent the individual members of a given family, and the links be­
tween pairs of nodes could identify the relationship between certain membersof the family, such as husband-wife or father-son. Other nodes representing
properties of certain persons, such as age, profession, or marital status, could
be linked to the nodes representing the corresponding persons. The hierarchi­
cal arrangement of topic classes contained in a conventional library classifica­tion system represents a form of semantic net in which the relationships be­
tween concepts is restricted to hierarchical inclusion.
The other type of knowledge structure that is much discussed is variously
known as a “frame,” “ script,” or “ schema” [6,18,19]. A frame is a compli­
cated data structure, typically representing a complex object such as a livingroom, a birthday party, or a restaurant. In particular, the frame would include
the collection of knowledge associated with the concept being represented, in­cluding both the information that is always true of a given environment— forexample, the fact that a restaurant contains tables and chairs, and customers
eating food— and also information that may be true only in particular instances— for example, that a certain person would be located in a certain restaurant. A
frame may be viewed as an extended notion of case, in the sense that the frame
circumscribes an area of discourse by defining a context within which certain
things are allowed to happen.
A script is a frame that also contains the timing sequence in which eventsare expected to happen. Certain portions of the script could store events thatmight be expected to happen— for example, that after having eaten in a restau­rant, the customer is expected to pay the bill. In addition prescriptions of what
would happen if the expectations were not confirmed could also be stored— forexample, the fact that a customer who refused to pay the bill would be asked by
the restaurant owner to wash dishes.
Given a stored collection of frames or scripts, the process of understanding
a new statement implies that the new information must fit with the collection of

266

CHAPTER 7

knowledge already stored. In particular, the interpretation of a sentence would
depend on the contents of certain frames, and might also lead to the modifica­tion of certain frames in accordance with the new available knowledge. Since
the frames specify sequences of events, a comparison of a particular event withthe knowledge stored in the frames makes it possible to draw inferences. Thus,
the inference might be that the customer who does not pay the bill at the restau­rant forgot a wallet or lost it, or that it was stolen.
At the present time, the specific structure of a frame is not completely un­derstood, and no established methods exist for searching collections of frames,
updating the stored information, and drawing appropriate inferences. Nor isthere any agreement about what stored knowledge base is actually needed andhow this store should be represented. There is, however, agreement that acomplete language processing system must be based not only on linguistic tech­niques (such as lexical analysis, parsing, and the application of semantic rules)
but also on a large variety of stored knowledge about the particular topic andthe situation being discussed. Further the generally available “common sense”
know-how about time, events, states, actions, motivations, and beliefs must be
available. A complete automatic language understanding system will not be­come practical until satisfactory solutions are provided for the construction andmanipulation of the required knowledge structures.
Fortunately, a good deal can be accomplished in various applications
areas, including information retrieval in particular, without totally mastering
the language understanding problem. The remainder of this chapter is con­cerned with language processing methods that might actually be used in various
practical situations.

2

LANGUAGE PROCESSING AND INFORMATION RETRIEVAL

Before describing the language processing methods to be used in information
retrieval, it is important to point out that a variety of views have been ex­pressed concerning the importance of linguistic methods in information re­trieval. On the one hand, some individuals are convinced that to retrieve items“ about” certain subjects, it is necessary to use all available facts pertaining tothese items. This operation necessarily requires an analysis of meaning which
is not substantially different in information retrieval from other areas of lan­
guage understanding. In particular, a desirable indexing, or content analysis,
approach would then consist of translating the document or query into someformal language consisting of concepts and relationships between the concepts.
This introduces the notion of a semantic network and of translations from one
language (the input) to another (the formalized index descriptions). Necessarily
then, it is argued the full power of language processing tools is needed in infor­
mation retrieval [20].
To support this view, one can point to the growing use of semantic tools inanalyzing linguistic structures— semantic markers are increasingly included as
entries in dictionaries and thesauruses, and relationship indicators specified in

NATURAL LANGUAGE PROCESSING

267

semantic nets are usable to form phrases and to disambiguate terms. Even
when complete networks with semantic relationships are not available, somesyntactic tools such as the previously mentioned case grammar utilize word
identifiers (agent, object, instrument) that have semantic connotations.
The opposite view about the importance of language analysis in retrieval
comes to very different conclusions. In particular, a good deal of evidence
points to the importance and usefulness of statistical, probabilistic, or vector
space techniques of the kind discussed in Chapters 3 and 4 for both indexing
and classification. On the other hand, no comparable evidence now shows that
linguistic methods are effective in retrieval. The reason may be that a funda­
mental difference exists between information retrieval on the one hand and cer­tain other language processing tasks on the other. In retrieval one needs to ren­der a document retrievable, rather than to convey the exact meaning of the
text. Thus, two items dealing with the same subject matter but coming to differ­ent conclusions are treated identically in retrieval, that is, either they are both
retrieved or they are both rejected. In a question-answering or language trans­
lation situation, these documents would of course be treated differently. This
amounts to a qualitative difference between document retrieval on the one
hand and question-answering or language translation systems on the other. For
example, to answer a specific question about an apple it is helpful to have somedetailed knowledge about apples. To retrieve documents about apples, it may
be unnecessary to understand precisely what the concept of apple actually en­tails. Instead, it may be sufficient to detect rough similarities between docu­
ments and concepts—for example, it might be enough to know that an apple ismore similar to a pear than to an elephant. The notion of vector matching andvector similarity computation was used extensively in the earlier chapters forclassification and retrieval purposes.
This view of information retrieval rejects the notion that information re­trieval is simply an early stage of more refined question answering [21]. Ques­
tion answering makes it necessary to understand the topic area in order to per­mit the generation of inferences leading to specific answers. Information
retrieval, on the other hand, simply provides references to the users designed
to fill an information need. To quote from Sparck Jones:
The w hole idea o f meaning representation is dubiously relevant to docum ent re­trieval in anything like its present form . . . one can get quite good (retrieval) re­sults with sim ple term s and w eights [22].

This is not to say that some well-established linguistic procedures could
not lead to improvements in retrieval effectiveness. This idea is further ex­
plored in the next few sections.

3

SYNTACTIC ANALYSIS SYSTEMS

Among the many kinds of syntactic analysis systems, three stand out as espe­
cially important: the phrase structure grammars, which are believed to model

268

CHAPTER 7

many of the basic structural properties of the language elements, the transfor­
mational grammars, which account for syntactically distinct representatons ofsome semantically equivalent fragments, and finally the transition network
grammars, which are most often used in modem automatic language processing
systems. These three syntactic models are briefly presented in this section.
*A

Phrase Structure Grammars

Many observers feel that a purely syntactic analysis of the language does not dovery much for people interested in language processing. In this view syntax is
an adjunct to a more complete analysis process. However, syntax is better un­derstood than most other linguistic procedures, and it is actually used in some
retrieval systems. Linguists are noted for their work on generative grammars.
These are grammars designed to generate grammatically correct sentences.
One of the main properties of a useful grammar is simplicity., in the sense that asmall grammar should account for the generation or the analysis of a large num­
ber of sentences. A particular type of grammar, known as “ phrase structure”
grammar, is simple and is usable both for sentence generation and for sentence
analysis. This type of grammar is therefore examined first.t
Consider “ rewrite rules” of the form
S -* A + B(1)

which stands for “ the variable S can be rewritten as A followed by B .” Thesymbol “ + ” separates the variables. When presenting rewrite rules, capitalletters denote nonterminal elements, that is, elements that can be rewritten fur­ther, by appearing on the left side of some rewrite rule.
The rewrite rule
S —» john + ran(2)says that the symbol S can be rewritten as “john” followed by “ ran.” S de­notes the sentence symbol. The symbols “john” and “ ran” are both terminal
elements (that cannot be rewritten further) as indicated by the lowercase
letters. Thus, expression (2) generates the sentence “john ran .”In principle, it is possible to use one rewrite rule for each sentence to begenerated. Thus one could write
S - » john + ran | sally + jumped | . . .

(3)where the bar | stands for the logical connective OR. The result would be a huge
grammar which would not be parsimonious or simple. Consider the sentences
1.
2.

the man hit the ballthe man hit the mant T h e e x a m p le s u s e d in t h e s e q u e l a r e t a k e n fr o m le c t u r e n o t e s p r e p a r e d b y J u s tin F is h e r .

NATURAL LANGUAGE PROCESSING

3.
4.
5.
6.
7.
8.

269

the ball hit the ballthe ball hit the man
the man took the ballthe man took the man
the ball took the ballthe ball took the man

ignoring for the moment the inherent semantic anomalies. The eight sample
sentences could in principle be generated by eight rewrite rules of the form S -*■sentence. If the word “rock” were added to the vocabulary, 10 additional sentences could be produced:
9. the man hit the rock10. the ball hit the rock11. the rock hit the man
12. the rock hit the ball
13. the rock hit the rock14. the man took the rock15. the ball took the rock16. the rock took the man
17. the rock took the ball
18. the rock took the rockSuppose now that the following grammar had been used for the original eight
sentencesS-» NP + VP
NP —» T + N
T —» the,N —» man | ballV P ^ V + NP»
V —> hit | took

(4)

where NP stands for “noun phrase,” VP represents “verb phrase,” and T, V,
and N are symbols, respectively, for “ article,” “verb,” and “ noun.” Whenthe grammar (4) is used for sentence generation, the addition of the word“rock” requires only one new rule, namely
N —» rockinstead of the 10 additional rules in the direct system of sentence generation.
It turns out that it is useful to represent the sentence generation in tree

270

C H A P T E R

7

S

B

A

Figure 7 - 1

R e w rite

ru le

S

-»

A

+

B.

form. The simple rewrite rule (1) would appear in tree form as shown in Fig.
7-1. In the direct sentence generation system, the derivation tree for sentence 1
would then appear as shown in Fig. 7-2. On the other hand, when the grammar(4) is used to generate sentence 1, the derivation tree appears as in Fig. 7-3. The
tree of Fig. 7-3 is more complicated than that of Fig. 7-2, but it tells something
about the structure of the sentence. In particular, Fig. 7-3 exhibits the constitu­
ent phrases of the sentence— for example, the fact that “ the” and “man” gotogether to form the noun phrase “ the man.” For this reason a tree of the typeshown in Fig. 7-3 is known as a “phrase structure tree,” or “phrase marker,”and a grammar such as (4) is known as a “phrase structure grammar” [23-25]
A phrase structure grammar is used to exhibit the constituent phrases ofthe sentences. In the case of sentence 1 the constituent structure is represented
as((the man) (hit(the ball)))( 5)which corresponds quite well to one’s intuition about this sentence. That is, asegmentation such as((the) (man hit the) (ball))would be curious because the initial “the” is obviously associated with“man,” etc. A good grammar should then produce a constituent structure
which conforms to linguistic intuition.
A grammar such as that of expression (4) is known as a “context-free”
phrase structure grammar because the nonterminal symbols of the left-handside of the rewrite rules can be replaced by the right sides of the rules regard­
less of the context in which these symbols may appear. That is, no contextual
restrictions apply to any rewrite rule.
Consider now the sentences.
19. john phoned mary
20. john phoned up mary
21. john phoned mary up
s

the

man

hit

the

ball

Figure 7-2

D irects e n te n c e

g en eratio n .

NATURAL LANGUAGE PROCESSING

271

S

Figure 7-3

Phrase structure sentence generation.

The word “ up” is dependent on “ phoned,” and “ phoned up” intuitively is aconstituent phrase. The first two sentences, 19 and 20, are easily handled by thecontext-free grammar:
S-» NP + VP
NP —» john | mary
VP —> V + NP
V —* phoned | phoned + up
But to handle sentence 21, one needs additional rules such as
VP -» V' + NP + PARTV' —> phoned
PART
up

(7)

Use of (7) produces the phrase marker of Fig. 7-4, corresponding to the consti-sFigure 7-4 Phrase marker fo r “ John
phoned Mary up.”

272

C H A P T E R

7tuent structure (john(phoned mary up)). Intuitively “phoned mary up” is a con­stituent, but a context-free phrase structure grammar is unable to exhibit thephrase. This shows that context-free grammars do not reflect the full complex­
ity of the language. In this case, they cannot handle discontinuous constituents
such as “up” in “phoned up.”
Another problem is due to the agreement expected in the number of sub­ject and verb. Consider the following grammar:
S
NP + VP
NP —» T '+ NTthe
N -* man | men | ball | balls
VP
V + NP
V —» have | has( 8)This generates sentences such as “the man has the ball” or “the men have theball.” Unfortunately, the grammar also generates “the man have the ball,”“the men has the ball,” and so on. This problem can be fixed by making dis­tinctions between singular and plural noun phrases, labeled NPSand NPp, re­spectively, and between singular and plural verb phrases and verbs, denoted
VPS, Vs, VPp, and Vp.
A new grammar can now be generated that will ensure agreement in num­
ber between subject and verb:

S^ NPS + VPS| NPp + VPp
NPS—» T + Ns
T —» theNs —*■man | ball
N P —» T+ N
i ^ jrP
1 ~ -^ P
Np —» men | balls
VPS—» Vs + NPS|V S + NPp
Vs —» has
VPp^ Vp + NPS| Vp + NPp
Vp —» have^

The new grammar (9) can now distinguish between the two trees of Fig. 7-5.
Problems such as the discontinuous constituents and the subject-verb
agreement led to the development of more powerful grammars than simple
phrase structure systems, including in particular the transformational gram­mars.

N A T U R A L

Figure 7 - 5

L A N G U A G E

P h ra s e

P R O C E S S IN G

m a rk e rs

illu stra tin g

2 73

su b je c t-v e rb

a g re e m e n t.

B Transformational Grammars

The basic innovation in the transformational grammars is the introduction ofcontext-sensitive rewrite rules of the typew A x —» w y x( 10)

where A is a nonterminal variable of the grammar and y is a string of terminal
or nonterminal characters. The rule specifies that when the variable A appears
in the context w and x (that is, is preceded by w and followed by x, where either
w or x might be unspecified), then A can be replaced by the string y.
A context-sensitive rewrite rule could be added to grammar (6) to generate
sentence 21 as follows:phoned + up + NP —» phoned + NP + up

( 11)leading to the following progression of transformations for the generation ofsentence 21:
NP + VP
john + VP■john + V + NP
■john + phoned + up + NP
• john + phoned + NP + up
•john + phoned + mary + up

( 12)

Subject-verb agreement can similarly be handled by introducing contex­
tual symbols sing and pi, standing for singular and plural, and rewrite rules such
as

274

C H A P T E RNVsing + havepi + haveman + singman + piball + singball + pi

man | ball
have
has
have
man
men
ball
balls

7

(13)

where the underline under man, ball, have indicates that these are nonterminal
symbols covering varying forms of the corresponding terms.
A more convincing argument for the need for transformational grammars
can perhaps be made by giving examples of related sentences that intuitively
ought to be handled by a practical grammar:
22.
23.
24.
25.
26.
27.
28.
29.

Chomsky proved the theorem
the theorem was proved by Chomsky
Chomsky did not prove the theorem
did Chomsky prove the theorem?
was the theorem proved by Chomsky?
the theorem was not proved by Chomsky
did not Chomsky prove the theorem?
was not the theorem proved by Chomsky?

It is obvious that all these sentences can be generated from the first one by suit­able sequences of transformations, including in particular active-passive, posi­
tive-negative, and declarative-interrogative transformations. A feature list for
the eight sentences is shown in Table 7-1.
Assuming that sentence 22 can be generated by a rule such as
S

NPt + V + ed + NP2

where NP, and NP2 denote specific instances of particular noun phrases, it iseasy to devise context-sensitive transformation rules that will generate thetransformed sentences:
Active-passive:
NPt + V + ed + NP2 —» NP2 + was + V + ed + by + NPt
Positive-negative:
NPi + V + ed + NP2 NPt + did not + V + NP2
Declarative-interrogative:
NPj + V + ed + NP2~> did + NPX+ V + NP2

275

NATURAL LANGUAGE PROCESSING

Table 7-1

Feature List for Sentences 22 to 29

ActivePositive

Declarative

/

■J
J

y
y
y

X

y
y

X

X

y
y

X
X

X

X

y

v/

X

X

X

X

X

Sentence
number
22
23
24
25
26
27
28
29

The remaining rules, such as passive-interrogative or negative-interrogative,
are equally simple to generate.
The language analysis, or recognition process, using a phrase structure
grammar is straightforward since it consists in a sequential application of therewrite rules to the initial sentence symbol (S), and terminates when the com­plete sentence of terminal symbols has been generated and no nonterminals re­main.
The recognition process using a transformational grammar is more com­
plex. A transformational grammar may be separated into two parts. The first is;
known as the base component of the grammar that generates the so-called deep
structure of a sentence reflecting the actual syntactic and semantic interpreta­tion of the input. Second, there is the transformational component that oper­
ates on the output of the base component and generates the surface structure of
the sentence reflecting the actual phonetic representation. The sentence gen­eration process using a transformational grammar is outlined in Fig. 7-6. Sen­tences that are semantically identical but structurally different will exhibit thesame deep structure but different surface structures [26].
To utilize a transformational grammar for the analysis of natural language
input, it is necessary to reverse the process of Fig. 7-6 as follows:
1 A standard parsing system is used first to obtain one or more trees ex-,hibiting the surface structure of the input.
2 Reverse transformations must then be applied to the surface structures;to obtain the underlying deep structure.
This process must be repeated for each initial surface tree and for all alternativeintermediary trees obtained when more than one reverse transformation ap­
plies.
Unfortunately, while the number of transformations that produce a surface
structure from the underlying deep structure is normally small, this is not true
when the process is reversed. Experience indicates that the reverse process ex-

CHAPTER 7

276
Input
grammar and lexicon
Base component fo rtransformational grammar

Generalized phrase marker
representing deep structure

Transformational
component o f grammar

Derived phrase marker
representing surface structure

O utput

Figure 7-6 Sentence generation usingtransformational grammar.

plodes except when the number of generated surface trees is very small or
when enough information is provided for each node in the surface trees to se­lect only those inverse transformations that are likely to lead to correct deep
structures. There is some hope that for sufficiently restricted topic areas appro­
priate statements of surface structure/deep structure relations might be gen­erated so as to render a transformational analysis useful in practice [8,27],**C

Augmented Transition Network Grammars

The augmented transition network (ATN) grammars offer all the facilities in­herent in transformational grammars. In addition their structure is sufficiently
simple to render a practical application reasonable. As a result, ATN grammars
have been chosen for incorporation into most practical language processing
systems [28-30].
Several grammatical systems including the ATN operations are based on
the notion of a finite state machine represented as a graph. A finite state graphconsists of nodes and branches between certain pairs of nodes. Each node sym­
bolizes a state of the machine, and the branches represent transitions from one
state to another. A transition from state A to state B takes place when the sym­
bol attached to branch AB occurs at the input.
Consider as an example the simple finite state graph of Fig. 7-7. The start isassumed to be in state S. If the next input symbol is “ a,” a transition is madefrom S to state Q j. If the initial input symbol is not “ a,” the recognition pro­
cess fails because no other path is provided for leaving state S. Assuming thatthe first symbol is in fact an “a,” two possibilities are open in state Qt: either
the next input symbol is a “b ,” in which case the machine stays in state Qx, or
the recognition process ends at the pop exit. The pop marker does not repre­
sent a new state but simply designates a compulsory exit from the graph. Whenthe pop is reached after the last input symbol has been read, the input is ac-

277

NATURAL LANGUAGE PROCESSING
b

0

Pop

Figure 7-7

Simple finite state graph.

cepted, that is, a correct analysis has been obtained. It is clear from the graphof Fig. 7-7 that the only sentences actually accepted are of the form
abbb . . . b, also written abn for some value of n > 0.
Machines such as that of Fig. 7-7 are not capable of accepting all contextfree languages. Suppose, however, that a collection of graphs were available
and that it were possible to jump from one graph to another by labeling certain
branches with the start state of some graph. An example of such a network is
given in Fig. 7-8. It may be seen that once arrived in state Qx, the current status
can be saved and the graph can be started again at state S. A push-down store,
or stack, is used to store the current status before proceeding back to the begin­ning state. A stack uses a last-in first-out discipline, very much like the usual
stack of plates in a cafeteria line. That is, only the top item is accessible (theone last placed onto the stack). In the example of Fig. 7-8, the branch in state
Qj is labeled push S to indicate that the current state (QJ is “pushed” onto thestack before going back to state S, unless a “b” is recognized at the input, inwhich case the alternative transition to state Q2 would be made without goingback to S.
When the pop symbol is reached and the stack is empty, the input is ac­
cepted. If the stack is not empty when a pop is reached, the top symbol is readfrom the stack and a return is made to the state from which the original pushoccurred. It can be verified that the graph of Fig. 7-8 accepts the input sentencea"b" for n > 0, that is, a string of a’s followed by a string of the exact same
number of b’s. Such a sentence is context-free.
Consider as an example the input aabb. The details of the analysis are pre­sented in Table 7-2. The first “a” is recognized, causing a transition from S to
Qi- Before returning to S to accept the second “a,” the current state (Q,) isstored in the stack. When the second “ a” is read from the input, a second tran­
sition occurs from S to Qx. When the first “b” is read, a transition is made to Q2from where the pop exit is reached. Since the stack is not empty, the stack con­tents reveal that a return to state Qx is in order which now makes possible theacceptance of the final “b” symbol.
In practical transition networks, there may be ambiguity in the node labels.
That is, from a given state several possible transitions to other states may bepossible. Then it is wise to arrange the possible paths according to the probabil­
ity that a given path will lead to a correct acceptance of the input. The most
PushS

0

a

Figure 7-8

b

0

Pop

Finite state graph recognizing context-free languages.

278

CHAPTER 7

Table 7-2 Recognition Process of aabb by Finite
State Graph of Fig. 7-8
Current state
S

Q,

s

Q,
q2
Pop

Q,
Q,
Pop

Input string remaining
to be recognized
aabb
abb
abb
bb
b
b
b
—
AcceptStack contents
—
—

Qi
a.
Q,
Q,
—
—

probable path is then taken first. If that path does not lead to a satisfactory ter­mination— for example, the input may be exhausted before the final pop isreached— a backtracking mechanism may be used to return to the point of am­
biguity in order to try the next alternative path.
Consider as an example the finite state graph of Fig. 7-9, and assume thatthe input is abb. It is clear that if the upper path is taken from S to Qx when the“a” is read, a “jam” occurs in the sense that the pop exit is reached with a final“b” still unrecognized. The lower path of Fig. 7-9 will, however, properly rec­ognize the input sentence.
A first sample transition network grammar for English is presented in Fig.
7-10. This consists of three graphs whose initial states represent sentences (S),noun phrases (NP), and prepositional phrases (PP), respectively. The transi­
tions from one graph to another are indicated by push labels as before: from theS-graph one can reach the NP-graph in three different ways from states S, Q2,
and Q4, respectively; the PP-graph can also be reached from state Q5 of the
S-graph, and transfers are provided both ways between the NP- and the PPgraphs.
Suppose that the sentence to be recognized starts with a noun phrase, apush would then occur from state S to the NP-graph. Assuming that the nounphrase were actually recognized, one of the pop exits would be reached in the
NP-graph after states Q7 or Q8. The highest entry in the stack would read\

NATURAL LANGUAGE PROCESSING_ . Push NP

PREPQ9 )---------

279

Pop

S: sentence

AUX: auxiliary verb

NP: noun phrase

ADJ: adjective

NPR: proper name

PP: prepositional phrase

DET: determiner

PREP: preposition

Figure 7-10

N:nounA sim ple transition network gram m ar fo r English.

S(NP), indicating that the original transfer came from state S and that a nounphrase was expected to occur. If a noun phrase is found, then the conditions of
the arc from S to Qr are fulfilled, and a return can be made from the NP-graphto state Q: of the S-network. The push label thus indicates that a transition is inorder to another state; at the same time it designates the return state fromwhich the Original recognition process must be resumed after the temporarytransfer. The return must be made to the state pointed to by the push branch.
The complete recognition process is shown in Table 7-3 for the sample
input “ the tall man in the Stetson is John W ayne” using the grammar of Fig.
7-10. It may be noted that a backtracking jump is made from state Q6 on line 9
to state Qg on line 10, because the input fails to substantiate either the adjectiveor the noun required at state Qe. Instead “ Stetson” is classified as a proper
name (NPR) which is correctly recognized by the alternative path from the NP
node.
The transition network grammars actually generate a phrase structure tree
instead of merely providing the output “ accept” or “ reject.” When a particulargraph is started, a node is created with the name of the graph. Each time an

280

CHAPTER 7

Table 7-3 Recognition Process of “The Tall Man in the Stetson Is John Wayne”
Using Grammar of Fig. 7r10
Current
state
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

S
NP

Qa
Qa

Qy

PP

Qa
NP

Qa
Qa
Pop

Q10
Pop
Pop

Q,
Qa
NP

Qa
Qa

Input string remaining to be recognized
the tall man in the Stetson is John Wayne
the tall man in the Stetson is John Waynetall man in the Stetson is John Wayne
man in the Stetson is John Waynein the Stetson is John Waynein the Stetson is John Wayne
the Stetson is John Wayne
the Stetson is John Wayne
Stetson is John Wayne
is John Wayne
is John Wayne
is John Wayne
is John Wayne
is John Wayne
is John Wayne
John Wayne
John Wayne
Wayne—

Stack contents
—

S(NP)
S(NP)
S(NP)
S(NP)
S(NP)Q7(PP)S(NP)Q7(PP)S(NP)Q7(PP)Q9(NP)S(NP)Q7(PP)Q9(NP)S(NP)Q7(PP)Q9(NP)S(NP)Q7(PP)Q9(NP)S(NP)'Qr(PP)
S(NP)Q7(PP)
S(NP)
—

—
Q4(NP)
Q4(NP)
Q4(NP)

Pop

—

—

Qa

—

—

Accept—Pop

input word is recognized (that is, when a transition is completed) an appropri­
ate terminal node of the tree is created. When a pop is reached, the currently
active subtree is attached to the node representing the next higher level subtree
to which the process now returns. The tree building process for the sample sen­tence of Table 7-3 is illustrated in detail in Fig. 7-11.
The problems previously mentioned for the standard context-free phrase
structure grammars are of course still present with transition networks of thetype illustrated in Fig. 7-10. In particular the grammar could equally well accept
the sentence “the tall man in the Stetson are John Wayne.” This kind of prob­
lem can be taken care of by a larger grammar of the same type which distin­
guishes plural noun phrases (P.NP) from singular noun phrases (S.NP), plural
verbs (P.V) from singular verbs (S.V), and so on. This solution produces anunwieldy grammar and requires a great deal of backtracking.
The solution is to use an augmented transition network grammar whichadds to the basic apparatus a set of storage registers, tests on the content of thestorage registers, and actions consisting either of storage register settings or ofstructure building operations that change the structure of the output tree. The
storage registers are used principally to store information about the number ortype of a noun or the tense of a verb. For example, when analyzing “the tall
Figure 7-11 (o p p o site ) Tree building process for sample sentence of Table 7-3.

Line number
in Table 7-3

Line number
in Table 7-3

©

©
IMP

3

4

ADJ)

the

tall

(Continued)281

Line number
in Table 7-3©

282

Line number
in Table 7-3

15 nothing changes
16

283

284

C H A P T E R

7man,” a “ singular” identifier is stored in a register to specify the number of“ man.” Later on when the verb is analyzed, a test is performed prior to making
the corresponding transition on the graph to ensure that the number of the verb
currently being processed is the same as the number of the noun previously
stored away in the register. The result is that the fragment “is John Wayne”
would be accepted whereas “are John Wayne” would be rejected.
The structure building operations may be quite complex as required, forexample, to rearrange a phrase structure tree following the analysis of a pas­
sive sentence. Alternative grairimatical analysis systems have been suggested
including some that scan a sentence in right-to-left instead of left-to-right order,some based on simultaneously following several analysis paths instead of back­tracking when an ambiguity is detected, and some where the input is scanned
many times instead of only once. Many people feel that ATN grammars are
simpler to deal with operationally than other syntactic formalisms. Several of
the question-answering systems mentioned later in this chapter use ATN gram­mars to handle the syntactic analysis part.
4

SYNTACTIC ANALYSIS IN INFORMATION RETRIEVAL

Syntactic analysis methods can be used in standard bibliographic retrieval sys­
tems in two main ways: on the one hand, a syntactic identification may enhance
the indexing operation by making possible the assignment to the documents
and queries of syntactically correct phrases replacing the single terms that arenormally used. On the other hand, it may be possible by using syntactic ap­
proaches to obtain a more detailed view of the document contents, leading todirected retrieval activities that would take into account individual document
portions such as sentences and paragraphs.
The latter possibility has led to the so-called passage retrieval, where at­
tempts are made to retrieve individual passages or sentences of documents
rather than complete documents only [31-33]. Passage retrieval is based on theanalysis of the full text of documents, the aim being to retrieve either answer
reporting passages, that is, passages from which an answer to a question caneffectively be inferred, or alternatively answer indicative passages which indi­cate that the same document also contains an answer reporting passage. Pas­
sage retrieval may be advantageous because answers to questions could be im­mediately available instead of merely references to answers.
The basic idea in passage retrieval is the construction of detailed queries
followed by the retrieval of all passages that contain all aspects of the query. A
syntactic analysis system might be used to control the detailed comparison be­
tween queries and document passages. In addition, a thesaurus that expands
the original query by including synonyms and other related words is alsoneeded.
Connected passages might also be retrieved by choosing appropriate an­swer reporting, or answer indicative passages, and then adding follow-up sen­tences starting with connecting terms, such as “however,” “these,” or “ on

N A T U R A L

L A N G U A G E

P R O C E S S IN G

285

the other hand.” The follow-up sentences should also exhibit additional
matches with the query. In tests performed with experimental collections, thepassage retrieval technique produced fairly high recall results exceeding 60 per­cent in many cases [31-32].
A possibly more immediate use of syntactic techniques in information re­trieval is provided by its application to the indexing task, and particularly to the
choice of noun phrases or prepositional phrases for indexing purposes. One
possibility consists in using a simplified syntactic analysis that assigns one ormore syntactic markers to each text word, and defining an indexing phrase as
consisting of sets of contiguous words representing a specified sequence of syn­tactic markers [34-37].
One particular technique for the detection of indexing phrases uses the fol­lowing basic indexing procedure [34-35]:
1 A recognition dictionary is used to assign one of 16 possible syntactic
categories to each word (one particular category identifies the corresponding
word as a “throw-away” word to be disregarded).
2 A form at dictionary stores a total of 77 permissible syntactic formats
for the phrases to be assigned to the text; these formats range in complexity
from a single noun (N) to a sequence of five nouns (ZZZZZ) none of which is
sufficiently meaningful to be permitted to stand alone.
3 The indexing cycle consists in accumulating sequences of non-throw­away words of up to five words from the input, the length of a sequence being
determined by the occurrence of delimiters such as punctuation signs. The syn­tactic markers corresponding to the input words are obtained from the recogni­tion dictionary, and the format dictionary is used to determine whether the
input sequence of markers corresponds to one of the permissible formats in the
dictionary. If so, the corresponding phrase is accepted as an indexing phrase. If
no match occurs with one of the stored formats, the candidate phrase is short­ened by deletion of one word and the operation is repeated.
In tests comparing this simple automatic indexing process against a con­ventional manual indexing method, slightly lower recall but slightly higher pre­cision were obtained for the machine process compared with the manual meth­odology, indicating again that conceptually quite simple automatic methods canbe competitive with the conventional manual procedures [36].
An alternative method of generating indexing phrases consists, of course,
in performing a full syntactic analysis of a text, or text excerpt such as an ab­
stract, and in assigning those phrases as index terms whose components exhibit
specified syntactic relations between them [38]. Such a process was used in an
early implementation of the SMART system in the hope of avoiding ambiguitiesof the “Venetian blind” versus “blind Venetian” type.
In the SMART system, a dictionary of criterion trees was used to record
the allowable syntactic patterns between phrase components. A criterion tree
is a structure including term specifications, syntactic indicators, and syntactic
relations obtaining between certain terms. A typical criterion phrase specifica-

286

C H A P T E R— ^NP)---©
102,107

Figure 7-12

©

©

11

S a m p le

p h ra se

11: ANALYSYNTHESSYNTHET102: LANGULINGUINTERLINGU©

©
crite rio n

7

107: PHRASESENTENCE
SUBJECT
102,107
WORD

sp e cifica tio n .

tion is shown in Fig. 7-12. The example of Fig. 7-12 exhibits the syntactic rela­tions which are specified between the word classes. Each word class is given a
numeric code (11, 102, and 107 in the example), and a dictionary is used to sub­stitute one or more actual words or word stems for each class. The left-handtree of Fig. 7-12 covers phrases such as language analysis, linguistic analysis,
and interlingual synthesis. The right-hand tree represents analysis of words,
synthesis of language, analysis for sentences, etc.
The flexibility of the criterion tree process stems from three main charac­
teristics:
1 Word stems rather than individual words are used in the dictionary asclass entries; a single word stem represents many words.
2 Class numbers, rather than words or word stems are attached to thenodes of the syntactic trees.
3 A variety of syntactic connection patterns is provided between theword classes.
As a result, a small criterion tree dictionary can account for a large number ofpotential indexing phrases.
When the criterion tree dictionary is used for indexing purposes, the index
terms and phrases are generated using the normal indexing process. A contextfree phrase structure grammar is then used to determine the syntactic structureof the indexing phrases. Finally, a check of the preconstructed criterion tree
dictionary reveals whether the actual syntactic pattern in the phrases matches
an entry in the tree dictionary. If so a phrase is accepted; otherwise it is re­jected.
The existing experimental evidence unfortunately shows that the criterion
tree dictionary does not operate as well as expected [39]. In fact, the statisticalphrase construction methods described in Chapters 3 and 4 would normallyoutperform the syntactic phrase procedures. Since the syntactic processing is
expensive to perform, there is obviously no point in going that route unless sub­stantial improvements in recall and precision are obtainable. The disappointing
results of the early tests may be due to two principal causes:

N A T U R A L

L A N G U A G E

P R O C E S S IN G

287

1 A phrase structure grammar was used to perform the syntactic anal­ysis, rather than a more sophisticated transformational or ATN grammar; it isconceivable that a more refined syntactic process could provide more accurate
retrieval results.
2 The syntactic restrictions imposed on the indexing phrases are oftenvery confining, with the result that satisfactory phrases are rejected because
the components do not obey the preestablished restrictions.
An example may be used to illustrate the second argument. The loosest kind ofsyntactic connection between two O r more phrase components is a requirement
to have the components appear in a common subtree of the syntactic phrase
marker. Unfortunately, even such a loosely formulated syntactic restriction
will cause the rejection of some phrases that appear essential for content identi­
fication. Consider a sentence such as “Experts in linguistics may study sen­tence generation and analysis.” Most syntactic analysis systems would notplace the terms “linguistics” and “ analysis” into a common subtree, andhence the phrase “linguistic analysis” would not be assigned to a document
containing that sentence, even though no other phrase would appear to be more
pertinent.
The conclusion is that the role of linguistic methodologies in general and ofsyntactic analysis in particular is still unresolved for information retrieval. Be­fore reaching a final conclusion in this area, it is wise to wait for the appearanceof more sophisticated language analysis methods that are at the same time suffi­
ciently efficient to permit incorporation into operational retrieval frameworks.
Such methods should then be thoroughly evaluated to determine their actual
value in information retrieval.
5**A

LINGUISTIC METHODS IN QUESTION ANSWERING
Knowledge Representation

While some question exists about the usefulness of language processing in in­formation retrieval, most experts feel that the linguistic methodology cannot be
bypassed in question-answering systems. It is not possible in the present con­text to examine in detail the components and structure of modern question-an­
swering systems. A brief look at some of the more notable features must suf­
fice.
Consider first the problem of knowledge representation. It was seen earlier
that stored knowledge structures are needed in many language processing sys­tems. They are required both for the representation of knowledge in the topic
area under discussion and also to supply “ common sense” knowledge that isnormally available to human beings.
Before examining the various types of knowledge structures, it may be
useful to look briefly at some of the characteristics of question-answering sys­tems. Such systems may be considered to be extensions of the normal database management and document retrieval systems in the following sense:

288

C H A P T E R

7

1 The data records used as a basis for question answering may in princi­
ple be more general and of greater scope than those common in business pro­cessing or in bibliographic retrieval. In any case, they are not normally re­stricted to the simple tabular format common in data base systems, or to theprocessing of bibliographic records alone.
2 The queries allowed in question answering are also more general thanthose common in data base systems or in document retrieval. In data base sys­
tems the normal query specifies the values of certain attributes attached to therecords— for example, a request for personnel records could refer to items
whose profession equals engineer, whose age is 33, with length of service ex­ceeding 10 years. In document retrieval, queries consist of keyword identifiers
possibly interconnected by Boolean operators. In question-answering systems,on the other hand, a greater variety of queries may be allowed. For ease of in­teraction one would also like to allow natural language queries, and furnish nat­ural language answers.
3 External knowledge intrudes because the answering process in a ques­tion-answering system depends on a knowledge of the social context and on theprevailing conversational framework in addition to the normally required sub­ject knowledge. In particular, the problem of determining the focus of a query
plays a role in general question answering, when it does not normally in database management or in document retrieval. That is, in question answering it
becomes necessary to decide why users are asking a question in addition toascertaining what they want to know before formulating an answer. (A user
who asks, “Why did you fly to Stockholm?” does not want a reply stating “be­cause it was too far to walk,” even though such an answer might be formallycorrect.)
The knowledge structures needed to cope with this expanded environment
normally take the form of semantic nets. These consist of nodes to represent
the concepts, events, characteristics, and values of interest in a system, as wellas branches specifying the relationships between nodes. The branches may belabeled with “case” labels, such as agent, object, instrument, source, or desti­
nation, to simplify the interpretation of the graph [40-45]. A typical semantic
network representing the operation of bolting two objects together using nuts
and bolts is shown in Fig. 7-13. The branches of Fig. 7-13 designate timing in­formation as well as whole-part and subset-superset relationships.
A wide variety of semantic nets has been introduced in the literature. Twomain types may be distinguished, the logical networks and the conceptual net­
works. In the logical network, the graph is interpreted as a logical statement
about properties holding for various entities. The basic primitives in a logicalnetwork are predicates defined for the entities under discussion. A predicate isa logical function of one or more variables producing a truth value (true or
false) when the variables are replaced by appropriate actions, objects, instru­
ments, and so on.
Typical predicates defined for a given area of study could be “is a memberof,” “is the father of,” “isaprim e number.” When the variable slots inapredicate are filled with appropriate entities, a predicate becomes a proposition,

N A T U R A L

L A N G U A G E

Figure 7-13
toc o n n e c t

S a m p letw ose m a n tic

o b je cts).

289

P R O C E S S IN Gn e tw o rk

(d e scrib in gab o ltin go p e ra tio nu sin gn u ts a n d

b o lts(A d a p te d fro m re fe re n c e 46.)

that is, a statement with a truth value. Typical propositions involving the predi­
cates introduced earlier are “John is the father of Mary,” “ 17 is a prime num­ber,” “x is a member of class y .” Figure 7-14 illustrates the logical net repre­
sentation of a sample proposition.
Two or more distinct propositions can be combined into a compound prop­
osition using logical relationships, such as the Boolean connectives AND, OR,
NOT. Thus, given two propositions such as “x is a member of y” and “y is amember of z ,” a new proposition would be stated as “x is a member of y AND
y is a member of z .” More generally, using a logical model, a semantic network
can be provided with a precise semantic interpretation, and with the inference
rules and procedural steps necessary to construct answers in response to cer­tain questions. In other words, since the components of the logical net include
all the apparatus of the predicate calculus, the question-answering process ef­
fectively becomes a theorem-proving task guided by precise logical rules.
Consider a query such as “is x a member of z?” Given the stored proposi­tions, “x is a member of y” and “y is a member of z ,” the compound proposi­tion “x is a member of y AND y is a member of z ” is generated. From this theformal inference rules may be usable to derive a new proposition “ x is a mem­ber of z ” which can then be used to answer the question affirmatively.

290

C H A P T E R

Figure 7-14
g iv e so b je ct

T yp ical(b o o k

rep rese n ta tio n1) torecip ie n tofa(M a ry ).”

A:
R:
0:

agent
recipientobjectPRED.:

predicatep ro p o sitio na salo g ica ln e tw o rk ,“ A g e n t

7(John )(F ro m re fe re n ce 47.)

It is clear that given a proper choice of predicates and logical characteris­tics describing the data, a wide variety of different kinds of information can be
represented. For example, normal index terms, values of attributes, as well as
hierarchical and other relationships between entities may be represented. A
logical network could then serve as a specification of the semantic and/or syn­tactic characteristics of many types of records, including commercial files, doc­
ument collections, and other kinds of artifacts.
However, for some purposes the logical framework may be somewhat con­fining for the representation of general knowledge. It may then be convenient toallow for more general conceptual networks, where once again the nodes repre­
sent the basic concepts and entities of interest. The relationships between con­cepts represented by the branches are then essentially open-ended. A variety ofrelationships represented by portions of conceptual semantic nets are pre­sented in Fig. 7-15.
In one formalism, the following components are recognized [45]:
1 Concepts that are considered as the essential constants or parametersof the world
2 Events that represent the actions which occur in the topic area underconsideration
3 Characteristics that are used to modify concepts, events, or other char­acteristics
4 Values that represent the attributes attached to individual records suchas a particular weight of a person or an address of an individual
In many semantic networks a distinction is made between generic concepts
that represent abstractions or classes of events, from particular instances of
events. A generic statement such as “physical objects carry a weight” would
then be treated differently than a specific instance such as “Joe Smith weighs
150 pounds.”
Among the operations that must be defined for semantic nets are the basic
search functions that relate individual instances to characterizations on the ge­neric level. Node-creating operations can add information to a network. N et­work transformation rules alter the network in accordance with newly available
information, or combine individual events, concepts, and characteristics intosequences of events, or scenarios. The network transformations and exten-

N A T U R A L

L A N G U A G E

291

P R O C E S S IN G

(a)

(b)

(c)

(d)

Figure 7-15
h u m a np liesT yp icals p e c ie s ."

500

(b)

rela tio n sh ip s

in clu d ed

“ P ete r

so n

is t h eins e m a n tic

of J a n e .”

(c)

“ A L

n ets,
26

is a

(a)

“ J o h n

flig h t.”

is a
(d)

m e m b e r“ S u p p lie ro f th exs u p ­

m u ffle rs.”

sions may then serve a role in content representation similar to that previously
mentioned for frames, scripts, or schemes.
The basic problem with the current perceptions of knowledge representa­tion is that they lack uniformity. In other words, no accepted theory of knowl­edge representation exists. Many of the structures appear to be produced by ad
hoc definitions. Rules used to manipulate the structures are sometimes uncer­
tain and inadequately motivated. The structures are thus hard to extend to new
discourse areas or to altered processing environments. Since an adequate the­ory of knowledge representation is essential for question-answering purposes,
it is not surprising that the question-answering problem still lacks a general so­lution.
B

Question-Answering Environment

From what has already been said it should be clear that a number of quite so­phisticated processing steps are required in order to produce direct answers toquestions. At the least, it is necessary to thoroughly comprehend the subject
area under discussion. In addition the context surrounding the question-an­
swering interplay must be understood. Finally, a complete language analysis

C H A P T E R

292

7

system capable of transforming user-formulated queries into answers to ques­
tions must be available.
Most existing question-answering systems perform tasks of substantial so­phistication in a restricted semantic environment. Typically, a microworld ischosen in which only a small number of entities and a small number of relations
are recognized. This automatically implies that the dictionaries which specify
the syntactic and semantic properties of the concepts are of limited size, andthat the syntactic and semantic patterns that occur (or that are allowed tooccur) are also restricted to those of a well-defined domain of discourse. Alter­
natively, a larger area of discourse may be tolerated, or the dependence of thesyntactic and semantic systems on the discourse area may be less rigid, pro­vided that the resulting ambiguities can be resolved externally, possibly by in­teraction with the user during the course of the question-answering process[48],
In many systems the more difficult problems in language analysis are disre­garded. The system may not, for example, include methods for the interpreta­tion of conjunctions (and, or, but, etc.), the proper resolution of quantification(all, every, each, some, etc.), the handling of anaphoric expressions (where
pronouns are used to refer to antecedents in the text that may be ambiguous),
the processing of ellipses (where parts of the text are omitted because the in­tended meaning is clear from the context), and the interpretation of polyseman­tic words, such as “ base,” whose meaning must be clarified by the context.
Typically, a special-purpose environment is chosen where many of theaforementioned difficulties can be bypassed. Examples are the use of special
kinds of texts such as pathology data and medical diagnostic summaries [49—52] or of formatted data structures such as occur in data base management [5359]. In either case, the conversion of an information request into a formalizedstatement of user needs may be simpler to carry out than in totally unrestrictedquestion-answering environments.
The language analysis features incorporated into some existing question­
answering systems are described in the remainder of this chapter.
*C

Linguistic Features in Question Answering

One of the earliest operational question-answering systems was LSNLIS, de­signed to answer questions about chemicals and rock samples brought backfrom the moon by the astronauts [53-54]. Like other existing question-an­
swering systems, the LSNLIS system is characterized by a discrete knowledge
area and by circumscribed user interests. The system is modular in that thesyntactic component is separated from the semantic interpretation, and that inturn is distinct from the data base retrieval component, as seen in Fig. 7-16.
The user queries are first subjected to a standard syntactic analysis using
an ATN grammar. The semantic rules are tightly bound to the subject matterand are designed to produce formal representations of the meaning of thequeries. These formal representations are then compared with the stored dataN A T U R A L

L A N G U A G E

Figure 7 - 1 6

B a s ic

P R O C E S S IN Go p e ra tio n s

o f th e

293

L S N L IS

syste m .

base consisting of information about the composition of the various rock sam­ples found on the moon, the amount of material found of each type of mineral,the location where each sample was found, and so on. Eventually, appropriate
answers are extracted from the data base.
The semantic interpretation rules constitute possibly the most interesting
part of the system. Two types of information are used as input, consisting firstof portions of the syntactic phrase markers produced by the syntactic analysis,
and second of certain semantic features attached to the terminal nodes of thesyntactic trees (that is, semantic classification data for some of the words in thequery texts).
Consider, as an example, the semantic interpretation rule “ author of” pre­sented in detail in Fig. 7-17. The input consists of two syntax tree excerpts
identified, respectively, as S:NP-V and S:V-NP, representing the usual subject-(S:NP-V ((1) PERSON))(S:V-NP ((2) DOCUMENT) ((1) EQU WRITE))
T H E N (1) NP-V AUTHOR OF (2) V-NP
AND

(0
Figure 7-17

S e m a n tic(b) V e r b - o b j e c t t r e e —in terp retatio n

S :V -N P .

in t h e(c) S e m a n t ic

L S N L IS
ru lesyste m ,“ a u th o r o f."(a)

S u b je c t-v e rb

tr e e —S:N P -V .

294

C H A P T E R

7

verb and verb-object components. Assuming that the dictionary processing re­veals that the word attached to node (1) of the subject-verb tree is a member ofthe class of “persons,” that is, an animate human being, while nodes (1) and (2)of the verb-object tree correspond, respectively, to some form of the word
“write” and to a member of the class of “documents,” the conclusion is that
node (1) of the NP-V tree is the “author of” node (2) of the V-NP tree. The ruleof Fig. 7-17 then makes it possible to answer questions such as “who wrote
document x?” or “list the authors writing documents that concern rock sam­ples.”
Many of the existing question-answering systems are based on an organi­zation similar to LSNLIS in the sense that the syntactic information produced
by an ATN analysis is used with semantic information attached to the nodes ofthe syntactic tree (for example, information about the “cases” of the concepts
attached to certain nodes) to derive the semantic interpretations of the user
queries. When the queries to be handled by the system are tightly circum­
scribed and the discourse area is well defined, the number of different syntax
trees and the variety of the needed semantic interpretation rules often proves
sufficiently small to permit the construction of practical question-answeringsystems.
Because of the restricted discourse areas, many of the semantic ambigui­
ties arising in the language-at-large are effectively eliminated in the practicalquestion-answering environment. Thus the word “ sample” in the LSNLIS
context may safely be assumed to refer to a lunar sample without further anal­
ysis. Nevertheless, a substantial amount of effort can be spent to adapt thequestion-answering environment to the sometimes sloppy habits of the users.
Thus, some systems include routines for spelling correction, ellipsis substitu­
tion, and the resolution of pronoun reference [55-57], Ellipsis in the question­
answering context normally implies that the user proposes a series of questions
without repeating all components. The user might state: “identify all samples inwhich glass was found”- “what about chromite?” and the system would inter­
pret the second part as “identify all samples in which chromite was found.”Pronoun reference is normally resolved by looking for a likely referent in thepreceding context. Thus “identify the composition of all samples containing
glass— list their identification numbers” would be interpreted as “list the iden­tification numbers of all samples containing glass.”
A substantial amount of work has also gone into the perfection of the dia­logue between system and user during the question-answering process. In somesystems a clarifying dialogue is in fact initiated with the user when an ambiguity
arises. The hope is that the user will resolve the ambiguity by letting the systemknow which of several alternatives may be correct. The same strategy can beused to get the user to certify the correctness of a final interpretation of thequery by the system. If the user returns a “yes,” the system proceeds to theretrieval phase; a “ no,” on the other hand, would mean that the user’s interest
was misinterpreted. The user would then submit a new formulation of the query[57-59].

NATURAL LANGUAGE PROCESSING

295

Several question-answering systems utilize a syntactic analysis component
that is not based on the ATN formalism. The REQUEST system, for example,
is based on a transformational grammar [27], and the LSP project uses a “ string
analysis” system [50—52]. The latter is noteworthy because its somewhat form alizedinput, consisting ofreports on medical test results or medical diagnos­
tic summaries, makes it possible to reduce the sentences of natural language
text to a tabular format which serves as a basis for the retrieval component.
The system includes
1 ' A syntactic analysis component
2 A system of transformations to regularize the syntactic structure ofeach sentence
3 A reduction of the text to tabular format
4 A retrieval component that uses the entries in the columns of the tables
to answer user queries.
A typical tabular format for an excerpt of a diagnostic report is shown in
Table 7-4. Such a table might not be easily generated for general texts that do
not exhibit the kind of stereotyping and uniformity of language that apparently
occurs in some scientific disciplines.
In several question-answering systems, the linguistic processing is not astightly bound to the domain of discourse as expected. Inevitably, a substantial
amount of ambiguity must then be accepted, because restrictive semantic rules
are no longer included in the process. The ROBOT system uses a relatively
general system of linguistic processing, initially based on an ATN grammar[60]. The tight semantic interpretation rules are then replaced by an interesting
verification system that uses the stored data base itself to help in the disambi­
guation of concepts that require elaboration.
Specifically, given a query such as ‘‘list the names of all Chicago secre­
taries,” the system will search the data base to determine .whether “ Chicago”
might be an attribute of secretary. When “ Chicago” is discovered as a compo­
nent of the address of some secretaries, the query is reinterpreted to mean “ list
the names of all secretaries located in Chicago.” A request for “ green F ords,”
where “ green” is listed both as a color and as the name of a person, and Ford
identifies the name of a person or alternatively an automobile manufacturer, iseventually interpreted correctly because the data base contains entries only forrecords where car manufacturer equals Ford, and car color equals green,whereas no records exist in the data base for the other three possible interpreta­
tions.
An alternative to using the data base for semantic verification consists ofbuilding an elaborate knowledge component into the question-answering sys­tem. This knowledge system in the form of scripts or frames can then be used
not only for query interpretation but also for the generation of answers to ques­
tions [61,62]. The answer generation problem in unrestricted question-an­
swering systems presents many unresolved problems. The obvious answer to a

0)
o
c -m

co
© c a>©O* - Q,
a)
0)
O)
oc
C
O

T3
C

CO
a
D

T3

0

O
5
<o

CO

«

35

©
o
c ^ —
O) .2 ©
(0
5

©
.c
c
(0
Q.
O)
0)

c
o>

c
co

(75
"O
d)
c

To
Q.

a

■oo t(0

O)
©

€ £
« c

C0

ffl &

E

o

o
c

CD
sz

>

5

H -

a 0

«
a

E
o
o

>
k_
CO

E
E

3
CD

O
'3
(A

_ (0
€ £

0)
a>
CO

■©D

4) *0
> ©

© k-

co O

E

$ $

O ■D
_ a)

.2 3
©
© ©

tj 5

o>
£
co o
c

a

O)
CO

To X5
o
5. CO
>i E
a>
c
co

co a)

E °

CO
Q_

o

u.
■D
CO
■*- to

e
*
©

(0 n

296

co
5

C/)
©
O
C

O)

T
3
C
©

NATURAL LANGUAGE PROCESSING

297

question is almost never adequate— for example, a simple yes/no answer to auser query will be found confining in most instances. Instead users look for an­swers that take into account the focus of the questions and offer appropriate
elaborations and rationalizations. The time is not yet at hand when knowledge
encoded in frames or scripts can be used efficiently for the interpretation ofqueries and the generation of system responses in unrestricted automatic ques­tion-answering systems [63].
6SUMMARY

It has become evident in recent years that an unrestricted automatic natural
language information system must necessarily incorporate a complete language
understanding system. The latter in turn should be based on an acceptable the­ory of language, and on prestored knowledge covering the area of discourse
under consideration, the general world knowledge normally assumed, and thepsychological context of a given interaction in question answering.
Since these basic cornerstones of a full language processing system are notclose to being under control, the choice on the part of practitioners interested in
making use of language processing tools is twofold. On the one hand, an at­
tempt can be made to use sophisticated linguistic tools in a restricted discourse
area where the semantic difficulties can be resolved by the context and much of
the ambiguity is automatically absent. This is the path followed by researchers
who design question-answering systems in restricted topic environments. On
the other hand, some of the language processing tools that appear to be wellunderstood— notably syntactic analysis— could be used to improve the effec­
tiveness of some classes of information systems. The use of syntactic methods
in information retrieval may become attractive before long, especially in auto­
matic indexing applications to control the phrases assigned to documents andqueries for content identification. Syntactic analysis systems could also be use­
ful for incorporation into full-text processing systems— for example, for auto­
matic abstracting and passage retrieval.
Current indications are that more comprehensive linguistic theories may
be needed before sophisticated language processing tools will actually be us­
able in many general-purpose automatic information systems.
REFERENCES[1] T .R . A ddis, M achine Understanding o f Natural Language, International Journal o f
M an-M achine Stu d ies, V ol. 9, N o . 2, M arch 1977, pp. 2 0 7 -2 2 2 .
[2] K . Sparck Jones and M . K ay, L inguistics and Information S cien ce, A cadem ic
Press, N e w Y ork, 1973.
[3] C .A . M ontgom ery, L inguistics and Information S cien ce, Journal o f the A S IS , V ol.
23, N o . 3, M a y -J u n e 1972, pp. 1 95-219.
[4] K . Sparck Jones and M . K ay, L inguistics and Information S c ie n c e — A Postscript,
in Natural Language in Information S cien ce, D .E . W alker, H . Karlgren and M.
K ay, editors, F ID Publication 551, Skriptor, Stockholm , 1977, pp. 183-192.

298

CHAPTER 7[5] F .J. D am eraii, A utom ated Language P rocessing, in A nnual R ev iew o f Information
S cien ce and T ech n ology, V ol. 11, M .E . W illiam s, editor, A m erican S ociety for In­
formation S cien ce, W ashington, D C ., 1976, pp. 107-161.
[6] G. Silva and C .A . M ontgom ery, K n ow led ge R epresentation for A utom ated U nder­
standing o f Natural Language D isco u rse, Com puters and the H um anities, V ol. 11,
N o . 4, J u ly -A u g u st 1977, pp. 2 2 3 -2 3 4 .
[7] R .C . Schank, M . L eb ow itz, and L. Birnbaum , A n Integrated U nderstander, A m er­
ican Journal o f Com putational L inguistics, V ol. 6, N o . 1, January-M arch 1980, pp.
13-30.
[8] N . Sager, C om putational L inguistics, in Natural Language in Information S cien ce,
D .E . W alker, H . Karlgren, and M. K ay, editors, FID Publication 551, Skriptor,
Stockholm , 1977, pp. .75-100.
[9] A .G . Oettinger, A utom atic Language Translation, Harvard U n iversity P ress, Cam ­bridge, M assachusetts!; 1960.
[10] Y . Bar H illel, Language and Inform ation, A d dison -W esley Publishing C om pany,
R eading, M assach u setts, 1964.
[11] A utom atic Language P rocessing A d visory C om m ittee, Language and M achines,
N ational A cadem y o f S cien ces, Publication 1416, W ashington, D C ., 1966.
[12] D .E . Rumelhart, Introduction to Hum an Information P rocessin g, John W iley andSon s, N e w Y ork, 1977.
[13] J.J. K atz and J .A . Fodor, The Structure o f Sem antic T h eory, Language, V ol. 39,
N o. 2. 196.3, pp. 170-210.
[14] C.J. Fillm ore, T he C ase for C ase, in U n iv e r s a l in Linguistic T heory, E. B ach and
R .T . Harris, ed itors, H olt Rinehart and W inston, N e w Y ork, 1968, pp. 1 -8 8 .
[15] D .G . B obrow and T. W inograd, A n O verview o f K R L — A K n ow led ge R epresenta­tion Language, C ognitive S cien ce, V ol. 1, N o . 1, January 1977, pp. 3 -4 6 .
[16] R .C . Schank, C onceptual D ep en d en cy T heory, in C onceptual Information Pro­
cessin g, Chapter 12., N orth H olland Publishing C om pany, A m sterdam , 1975, pp.
22 -8 2 .',■"3[17] N .V . Findler, editor, A ssociative N etw o rk s— R epresentation and U se o f K n ow l­edge by C om puters, A cadem ic P ress, N e w Y ork, 1979.
[18] M. M insky, A Fram ework for R epresenting K n ow led ge, in T he P sych ology o fComputer V isio n , P. W inston, editor, M cGraw-Hill B o o k C om pany, N e w Y ork,
1975, pp. 2 1 1 -2 7 7 .
[19] R .C . Schank and R .P. A b elso n , Scripts, Plans, G oals and U nderstanding,
Law rence Erlbaum A sso cia tes, H illsd ale, N e w Jersey, 1977.
[20] J.C. Gardin, On the R elation b etw een Q uestion-A nsw ering S ystem s and Various
T heoretical A pproaches to the A n alysis o f T ext, in T he A n alysis o f M eaning, M .
M acCafferty and K . Gray, editors, A slib , L ondon, 1979, pp. 2 0 6 -2 2 0 .
[21] S .E . R obertson, .B etw een A b ou tn ess and M eaning, in T he A n alysis o f M eaning, M.
M acCafferty and K . Gray, editors, A slib , L ondon, 1979, pp. 2 0 2 -2 0 5 .
[22] K . Sparck J on es, Problem s in the R epresentation o f M eaning in Information R e­trieval, in T he A nalysis o f M eaning, M . M acCafferty and K . Gray, editors, A slib ,L ondon, 1979, pp. 193-201.
[23] N . Sager, Syntactic A nalysis o f Natural L anguage, in A d van ces in Com puters, V ol.
8, A cadem ic P ress, N e w Y ork, 1967, pp. 153-188.
[24] S. K uno and A .G . Oettinger, M ultiple-Path Syntactic A n alyzer, in Information Pro­
cessin g— 62, N orth H olland Publishing C om pany, A m sterdam , 1963, pp. 3 0 6 -3 1 1 .
[25] S. K uno, A utom atic Syntactic A n a ly sis, in Seminar in C om putational L inguistics,

NATURAL LANGUAGE PROCESSING

299

A.W. Pratt, A.H. Roberts, and K. Lewis, editors, Public Health Service Publica­tion 1716, Government Printing Office, Washington, D.C., 1968, pp. 19-41.
[26] N. Chomsky, Aspects of the Theory of Syntax, MIT Press, Cambridge, Massachu­
setts, 1965.
[27] W.J. Plath, REQUEST: A Natural Language Question-Answering System, IBM
Journal of Research and Development, Vol. 20, No. 4, July 1976, pp. 326-335.
[28] R. Grishman, A Survey of Syntactic Analysis Procedures for Natural Language,
American Journal of Computational Linguistics, Vol. 13, No. 5, 1976, Microfiche47.
[29] W.A. Woods, Transition Network Grammars for Natural Language Analysis, Com­
munications of the ACM, Vol. 13, No. 10, October 1970, pp. 591-606.
[30] M. Bates, The Theory and Practice of Augmented Transition Network Grammars,
in Natural Language Communication via Computers, L. Bole, editor, Lecture
Notes in Computer Science, Springer Verlag, Berlin, 1978, pp. 191-260.
[31] J. O’Connor, Retrieval of Answer Sentences and Answer Figures by Text Search­ing, Information Processing and Management, Vol. 11, No. 5/7, 1975, pp. 155—
164.
[32] J. O’Connor, Data Retrieval by Text Searching, Journal of Chemical Information
and Computer Sciences, Vol. 17, 1977, pp. 181-186.
[33] I. Steinacker, Indexing and Automatic Significance Analysis, Journal of the ASIS,
Vol. 25, No. 4, July-August 1974, pp. 237-241.
[34] P.H. Klingbiel, Machine Aided Indexing of Technical Literature, Information Stor­
age and Retrieval, Vol. 9, No. 2, February 1973, pp. 79-84.
[35] P.H. Klingbiel, A Technique for Machine-Aided Indexing, Information Storage andRetrieval, Vol. 9, No. 9, September 1973, pp. 477-494.
[36] P.H. Klingbiel and C.C. Rinker, Evaluation of Machine-Aided Indexing, Informa­tion Processing and Management, Vol. 12, No. 6, 1976, pp. 351-366.
[37] J.M. Carroll, W. Fraser, and G. Gill, Automatic Content Analysis in an On-Line
Environment, Information Processing Letters, Vol. 1, No. 4, June 1972, pp. 134—140.
[38] G. Salton, Automatic Phrase Matching, in Readings in Computational Linguistics,
D.G. Hays, editor, American Elsevier Publishing Company, New York, 1966, pp.
169-188.
[39] G. Salton, The SMART Automatic Document Retrieval System—An Illustration,
Communications of the ACM, Vol. 8, No. 6, June 1965, pp. 391-398.
[40] R.J. Brachman, What’s in a Concept: Structural Foundations for Semantic Net­
works, International Journal of Man-Machine Studies, Vol. 9, No. 2, March 1977,
pp. 127-152.
[41] J.R. Abrial, Data Semantics, in Database Management, J.W. Klimbie and K.I. Kofferman, editors, North Holland Publishing Company, Amsterdam, Holland, 1974,
pp. 1-60.
[42] J.W. Sowa, Conceptual Graphs for a Data Base Interface, IBM Journal of Researchand Development, Vol. 20, No. 4, July 1976, pp. 336-357.
[43] G.G. Hendrix, Encoding Knowledge in Partitioned Networks, Technical Note 164,
Stanford Research Institute, Menlo Park, California, June 1978.
[44] H.J. Schmid and J.R. Swenson, On the Semantics of the Relational Data Model,
ACM SIGMOD Conference Proceedings, Association for Computing Machinery,
New York, 1975, pp. 211-223.
[45] N. Roussopoulos and J. Mylopoulos, Using Semantic Networks for Data Base

300

CHAPTER 7

M anagem ent, Proceedings o f the C onference for Very Large D ata B a ses, A sso cia ­tion for C om puting M achinery, N e w Y ork, 1975, pp. 144.
[46] B .J. G rosz, The R epresentation and U se o f F ocu s in D ialogue U nderstanding, SRI
T echnical N o te 151, Stanford R esearch Institute, M enlo Park, California, July
1977.
[47] N . C ercone, M orphological A n alysis and L exicon D esign for Natural Language
P rocessing, C om puters and the H um anities, V ol. 11, N o . 4, J u ly -A u g u st 1977, pp.
235-258.
[48] T. W inograd, U nderstanding Natural Language, A cadem ic P ress, N e w Y ork, 1972.
[49] G .S. D unham , M .G . Pacak, and A .W . Pratt, A utom atic Indexing o f Pathology
D ata, Journal o f the A S IS , V ol. 29, N o . 2, M arch 1978, pp. 8 1 -9 0 .
[50] N . Sager, Sublanguage Grammars in S cien ce Information P rocessing, Journal o f
the A S IS , V ol. 26, N o . 1, January-February 1975, pp. 10 -1 6 .
[51] R. Grishman and L. Hirschm an, Q uestion A nswering from Natural Language M edi­cal D ata B a ses, Artificial Intelligence, V ol. 11, 1978, pp. 2 5 -4 3 .
[52] N . Sager and R. Grishman, T he R estriction Language for C om puter Grammars o f
Natural Language, C om m unications o f the A C M , V ol. 18, N o . 7, July 1975, pp.
3 9 0 -400.
[53] W .A . W oods and R .M . K aplan, The Lunar S cien ces Natural Language Information
System , R eport N o . 2265, B o lt Beranek and N ew m an , Cambridge, M assach u setts,
Septem ber 1971.
[54] W .A . W oods, R .M . Kaplan, and B. N ash-W ebber, T he Lunar S cien ces Natural
Language Inform ation S ystem , R eport N o . 2378, B olt B eranek and N ew m an, Cam ­bridge, M assach u setts, 1972.
[55] G .G . H endrix, E .D . Sacerdoti, D . Sagalow icz, and J. S locu m , D eveloping a N atu ­ral Language Interface to C om plex D ata, ACM T ransactions on D atabase S ystem s,
V ol. 3, N o . 2, June 1978, pp. 1 05-147.
[56] W .A . Martin, Som e C om m ents on E Q S, A N ear Term Natural Language D ata B ase
Query S ystem , P roceedings ACM 1978 Annual C onference, D ecem ber 1978, pp.
156-164.
[57] D .L . W altz, A n E nglish Language Q uestion A nsw ering S ystem for a Large R ela­tional D ata B a se, Com m unications o f the A CM , V ol. 21, N o . 7, July 1978, pp. 5 2 6 539.
[58] E .F . C odd, R .S . A rnold, J.M . C adiou, C .L . Chang, and N . R o u ssop ou los, R en d ez­
vous: V ersion 1, R eport RJ 2144, IBM R esearch Laboratory, San Jo se, California,
January 1978.
[59] E .F . C odd, S ev en Steps to R en d ezvou s, Report RJ 1333, IBM R esearch Labora­
tory, San J o se, California, January 1974.
[60] L .R . Harris, U ser Oriented D atabase Query with the RO BO T Natural Language
Query Sytem , International Journal o f M an-M achine Studies, V ol. 9, 1977, pp.
6 9 7 -713.
[61] D .G . B obrow , R .M . K aplan, M. K ay, D .A . N orm an, H . T hom pson, and T. W ino­
grad, G U S — A Fram e-D riven D ialog S ystem , Artificial Intelligence, V ol. 8, N o . 2,
April 1977, pp. 155-173.
[62] W . L ehnert, Problem s in Q uestion A nsw ering, Sixth International C onference on
Com putational L inguistics, O ttaw a, Canada, 1976.
[63] B. Shneiderm an, Softw are P sych ology: Hum an F actors in C om puter and Inform a­tion S ystem s, W inthrop Publishers, Cambridge, M assach u setts, 1980.

NATURAL LANGUAGE PROCESSING

301

BIBLIOGRAPHIC REMARKSThe following references can be used to obtain an overview of several linguistic
techniques used in automatic information processing:
L. Bole, editor, Natural Language Communication via Computers, Lecture Notes in
Computer Science, Springer Verlag, Berlin, 1978.
R. Rustin, editor, Natural Language Processing, Courant Computer Science Symposium
No. 8, Algorithmics Press, New York, 1973.

The following references provide a deeper view of various methods cur­rently used for knowledge representation:
D.G. Bobrow and A. Collins, editors, Representation and Understanding, Academic
Press, New York, 1975.
N.V. Findler, editor, Associative Networks— Representation and Use of Knowledge by
Computers, Academic Press, New York, 1979.
R.C. Schank and R.P. Abelson, Scripts, Plans, Goals and Understanding, Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1977.

Problems arising in interfacing linguistic techniques and information re­trieval are covered in the following references:
K. Sparck Jones and M. Kay, Linguistics and Information Science, Academic Press,
New York, 1973.
D.E. Walker, H. Karlgren, and M. Kay, editors, Natural Language in Information Sci­ence, FID Publication 551, Skriptor, Stockholm, 1977.
EXERCISES
7-1 In Chapter 4, four different grammatical interpretations were given for the sentence,“Time flies like an arrow.”a List the various facts of world knowledge that appear to be needed in a language
analysis system capable of recognizing the sample sentence,b Assuming that a context-free grammar is used for recognition purposes, gen­erate a set of semantic rules based on the stored knowledge that are capable ofeliminating the extraneous analyses (leaving only the correct interpretation)
when added to the normal context-free recognition process.
7-2 Explain the similarities and differences between a context-free grammar, a contextsensitive grammar, a transformational grammar, and an ATN grammar. What dothe initials ATN stand for? Explain the function of the concepts represented by theA, T, and N, respectively.
7-3 Consider a TN grammar capable of recognizing character strings consisting of A ’s
and B ’s only. Generate a TN grammar that accepts all input strings exhibiting anequal number of A ’s and B ’s regardless of the ordering of the letters, and rejects allother strings. Thus AABB, ABAB, the null string, etc., would be accepted; how­ever, AAB, ABABC, A, etc., would be rejected.

302

7-4

CHAPTER 7

Consider the following segment of a phrase structure grammar for English:(1)
S - * NP + VP
(2) VP —» V
(3) NP -> DET + ADJ* + N

The asterisk * following ADJ indicates that a variable number of adjectives are ac­
ceptable.
a Draw a transition network corresponding to the three rules,
b Show the individual steps needed to recognize the sentence “The big grayhippo wallows.”
c How can the grammar and network be extended to accept the sentences “Thebig gray hippo wallows mightily” and “The big gray hippo mightily wallows” ?
d Illustrate the recognition of one of the earlier sentences by giving the phrase
markers corresponding to each step of the recognition process.
7-5 Consider the first two paragraphs of the current chapter.
a Choose indexing phrases (noun phrases, prepositional phrases) to represent thecontent of these paragraphs.
b Generate a set of criterion phrases together with the corresponding thesaurus(as in Fig. 7-12) to represent the phrases specified under part a.
c Specify the noun-phrase portion of a context-free grammar capable of recogniz­ing the corresponding phrases in conjunction with the criterion phrase dictio­nary of part b.
d How would you extend the criterion phrase dictionary and the grammar to han­dle the content of the third paragraph of this chapter, in addition to the first two
paragraphs? What does this imply about the ease of extending limited linguistic
recognition systems to wider subject areas?