NBS

PUBLICATIONS

U.S. Department

of Commerce

National Bureau

of Standards

NBSIR 83-2687

A1110? 3T0035

AN OVERVIEW OF

COMPUTER-BASED

NATURAL LANGUAGE

PROCESSING

April 1983

Prepared for National Aeronautics and Space

Administration Headquarters

Washington, D.C. 20546

^OS

*

•J 0

'

RATIONAL BimiAU

OF STAWDAAD6

UCRARY

MAY 2 1983

NBSIR 83-2687

0 t

/

AN OVERVIEW OF

COMPUTER-BASED

NATURAL LANGUAGE

PROCESSING

William B. Gevarter*

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Center for Manufacturing Engineering

Industrial Systems Division

Metrology Building, Room A127

Washington, DC 20234

April 1 983

Prepared for: National Aeronautics and Space Administration

Headquarters

Washington, DC 20546

0F x

®<">£AU °*

U.S. DEPARTMENT OF COMMERCE, Malcolm Baldrige, Secretary

NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director

"Research Associate at the National Bureau of Standards Sponsored by NASA Headquarters

AN OVERVIEW OF COMPUTER-BASED

NATURAL LANGUAGE PROCESSING*

Preface

Computer-based Natural Language Processing (NLP) is the

key to enabling humans and their computer-based creations to

interact with machines in natural languages like English and

Japanese (in contrast to formal computer languages). The

doors that such an achievement can open have made this a major

research area in Artificial Intelligence and Computational Linguistics.

Commercial natural languages interfaces to computers have recently

entered the market and the future looks bright for other applications

as well.

This report reviews the basic approaches to such systems,

the techniques utilized, applications, the state-of-the-art

of the technology, issues and research requirements, the major

participants, and finally, future trends and expectations.

It is anticipated that this report will prove useful to

engineering and research managers, potential users, and others

who will be affected by this field as it unfolds.

* This report is part of the NBS/NASA series of overview

reports on Artificial Intelligence and Robotics.
Acknowledgements

I wish to thank the many people and organizations who have

contributed to this report, both in providing information, and

in reviewing the report and suggesting corrections, modifications

and additions. I particularly would like to thank Dr. Brian

Phillips of Texas Instruments, Dr. Ralph Grishman of the NRL

AI Lab, Dr. Barbara Groz of SRI International, Dr. Dara Dannenberg

of Cognitive Systems, Dr. Gary Hendrix of Symantec, and Ms.

Vicki Roy of NBS for their thorough review of the report and

their many helpful suggestions. However, the responsibility

of any remaining errors or inaccuracies must remain with the

author

It is not the intent of the National Bureau of Standards

or NASA to recommend or endorse any of the systems, manufacturers

or organizations named in this report, but simply to attempt

to provide an overview of the NLP field. However, in a growing

field such as NLP, important activities and products may not

have been mentioned. Lack of such mention does not in any

way imply that they are not also worthwhile. The author would

appreciate having any such omissions or oversights called to

his attention so that they can be considered for future reports.
AN OVERVIEW OF COMPUTER-BASED

NATURAL LANGUAGE PROCESSING (NLP)

Table of Contents

Pjfle

A. Introduction 1

B. Applications 4

C. Approach 6

1. Type A: No World Models 6

a. Key Words or Patterns 6

b. Limited Logic Systems. 6

2. Type B: Systems That Use Explicit World Models. 7

3. Type C: Systems That Include Information About the 7

Goals and Beliefs in Intelligent Entities.

D. The Parsing Problem 8

E. Grammars 9

1. Phrase-Structure Grammar - Context Free Grammar 9

2. Transformational Grammars 10

3. Case Grammars 10

4. Semantic Grammars 11

5. Other Grammars 11

F. Semantics and Some Cantankerous Aspects of Language 13

1. Multiple Word Senses. 13

2. Modifier Attachment 13

3. Noun-Noun Modification 14

4. Pronouns 14

5. Ellipsis and Substitution 14

i i i
Page

G . Knowledge Representation 15

1 . Procedur a 1 15

2. Dec 1 ar at i ve 15

a. Logic 15

b. Semantic Networks 15

3. Case Frames 15

4. Conceptual Dependency 16

5. Frames 16

6. Scripts 16

H. Syntactic Parsing 17

1 . Template Matching 17

2. Transition Nets 17

3. Other 17

I. Semantics, Parsing and Understanding 23

J. NLP Systems 25

1 . Kinds 25

2. Research NLP Systems 28

3. Commercial Systems 40

K. State of the Art 48

L. Problems and Issues. 49

1 . How People Use Language 49

2. Linguistics 49

3. Conver sat ion 50

4. Processor Design 51

5. Data Base Interfaces 54

6. Text Understanding 55

i v
Page

M. Research Required 56

1. How People Use Language 56

2.

Linguistics 56

3. Conversation 56

4. Processor Design 57

5. Data Base Interfaces 58

6. Text Understanding 58

N. Principal U.S. Participants in NLP 59

1. Research and Development 59

2. Principal U.S. Government Agencies Funding NLP Research 60

3. Commercial NLP Systems 60

O. Forecast 61

P. Further Sources of Information 65

1. Journals 65

2. Conferences 65

3. Recent Books 65

4. Overviews and Surveys 66

References 67

Glossary 70

v
Li st of Tables

Page

I. Some Applications of Natural Language Processing 5

II. Natural Language Understanding Systems 30

a

SHRDLU 30

b. SOPHIE 31

c . TDUS 32

d. LUNAR 33

e

PLANES/JETS 34

f

ROBOT/INTELLECT 35

g. LADDER 36

h

SAM 37

i . PAM 38

III. Current Research NLP Systems 41

IV. Commercial Natural Language Systems. 46
List of Figures

Page

1. A Transition Network for a Small Subset of English. 18

2a. Example Noun Phrase Decomposition. 20

2b. Parse Tree Representation of the Noun Phrase Surface Structure. 20
... /•
NATURAL LANGUAGE PROCESSING

A. Introduction

One major goal of Artificial Intelligence (AI) research has been to

develop the means to interact with machines in natural language (in

contrast to a computer language). The interaction may be typed,

printed or spoken. The complementary goal has been to understand

how humans communicate. The scientific endeavor aimed at achieving

these goals has been referred to as computational linguistics (or

more broadly as cognitive science), an effort at the intersection

of AI, linguistics, philosophy and psychology.

Human communication in natural language is an activity of the

whole intellect. AI researchers, in trying to formalize what

is required to properly address natural language find themselves

involved in the long term endeavor of having to come to grips

with this whole acitivity. (Formal linguists tend to restrict

themselves to the structure of language.) The current AI approach

is to conceptualize language as a knowledge-based system for

processing communications and to create computer programs to

model that process.

Communications acts can serve many purposes, depending on the

goals, intentions and strategies of the communicator. One goal

of the communication is to change some aspect of the recipient's

mental state. Thus, communication endeavors to add or modify

knowledge, change a mood, elicit a response or establish a new

goal for the recipients.

1
For a computer program to interpret a relatively unrestricted

natural language communication, a great deal of knowledge is

required. Knowledge is needed of:

-the structure of sentences

-the meaning of words

-the morphology of words

-a model of the beliefs of the sender

-the rules of conversation, and

-an extensive shared body of general information about the

wor 1 d

.

This body of knowledge can enable a computer (like a human) to use

expect at i on -dr i ven processing in which knowledge about the usual

properties of known objects, concepts, and what typically happens

in situations, can be used to understand incomplete or ungrammatical

sentences in appropriate contexts.

Thus, Barrow (1979, p. 12) observes:

In current attempts to handle natural language, the need to

use knowledge about the subject matter of the conversation,

and not just grammatical niceties, is recognized--it is

now believed that reliable translation is not possible

without such knowledge. It is essential to find the best

interpretation of what is uttered that is consistent with

all sources of knowledge —lexical, grammatical, semantic

(meaning), topical, and contextual.

2
Arden ( 1 980 , p .463) adds:

In writing a program for understanding languages, one is

faced with all the problems of artificial intelligence,

problems of coping with huge amounts of knowledge, of finding

ways to represent and describe complex cognitive structures,

as well as finding an appropriate structure in a gigantic

space of possibilities. Much of the research in understanding

natural languages is aimed at these problems.

As indicated earlier, natural language communication between

humans is very dependent upon shared knowledge, models of the

world, models of the individuals they are communicating with, and

the purposes or goals of the communication. Because the listener

has certain expectations based on the context and his (or her)

models, it is often the case that only minimal cues are needed

in the communication to activate these models and determine

the meaning.

The next section, B, briefly outlines applications for

natural language processing (NLP) systems. Sections C to I review the technology involved in constructing such systems,

with existing NLP systems being summarized in Section J.

The state of the art, problems and issues, research requirements

and the principle participants in NLP are covered in Sections

K through N. Section 0 provides a forecast of future developments.

A glossary of terms in NLP is provided at the back of this

report. Further sources of information are listed in Section P.

3
B . Applications:

There are many applications for computer-based natural language

understanding systems. Some of these are listed in Table I.

4
Discourse

Speech Understanding

Story Understanding

Information Access

Information Retrieval

Question Answering Systems

Computer-Aided Instruction

Information Acquisition or Transformation

Machine Translation

Document or Text Understanding

Automatic Paraphrasing

Knowledge Compilation

Knowledge Acquisition

Interaction with Intelligent Programs

Expert Systems Interfaces

Decision Support Systems

Explanation Modules For Computer Actions

Interactive Interfaces to Computer Programs

Interacting with Machines

Control of Complex Machines

Language Generation

Document or Text Generation

Speech Output

Writing Aids: e.g., grammar checking

TABLE I Some Applications of Natural Language Processing

5
C. Approach:

Natural Language Processing (NLP) systems utilize both linguistic

knowledge and domain knowledge to interpret the input. As domain

knowledge (knowledge about the subject area of the communication)

is so important to understanding, it is usual to classify the

various systems based on their representation and utilization

of domain knowledge. On this basis, Hendrix and Sacerdoti (1981)

classify systems as Types A, B or C*, with Type A being the simplest,

least capable and correspondingly least costly systems.

1 . Type A; No World Models

a . Key Words or Patterns

The simplest systems utilize ad hoc data structures to

store facts about a limited domain. Input sentences are scanned

by the programs for predeclared key words, or patterns, that

indicate known objects or relationships. Using this approach,

early simple template-based systems, while ignoring the

complexities of language, sometimes were able to achieve

impressive results. Usually, heuristic empirical rules were

used to guide the interpretations.

b . Limited Logic Systems

In limited logic systems, information in their data base was

stored in some formal notation, and language mechanisms were

*0ther system classifications are possible, e.g., those based

on the range of syntactic coverage.

6
utilized to translate the input into the internal form. The

internal form chosen was such as to facilitate performing logical

inferences on information in the data base.

2 . Type B: Systems That Use Explicit World Models

In these systems, knowledge about the domain is explicitly encoded,

usually in frame or network representations (discussed in a later

section) that allow the system to understand input in terms of

context and expectations. Cullinford's work (see Schank and

Ableson, 1977) on SAM (Script Applier Mechanism) is a good example

of this approach.

3 . Type C: Systems that Include Information about the Goals

and Beliefs of Intelligent Entities.

These advanced systems (still in the research stage) attempt

to include in their knowledge base information about the beliefs

and intentions of the participants in the communication. If

the goal of the communication is known, it is much easier to interpret

the message. Schank and Abelson's (1977) work on plans and themes

reflects this approach.

7
D . The Parsing Problem

For more complex systems than those based on key words and pattern

matching, language knowledge is required to interpret the sentences.

The system usually begins by "parsing" the input (processing

an input sentence to produce a more useful representation for

further analysis). This representation is normally a structural

description of the sentence indicating the relationships of

the component parts. To address the parsing problem and to interpret

the result, the computational linguistic community has studied

syntax, semantics, and pragmatics. Syntax is the study of the

structure of phrases and sentences. Semantics is the study of meaning.

Pragmatics is the study of the use of language in context.

8
E. Grammars

Barr and Feigenbaum (1981, p. 229), state, "A grammar of a language

is a scheme for specifying the sentences allowed in the language,

indicating the syntactic rules for combining words into wellformed phrases and clauses." The following grammars are some

of the most important.*

1 . Phrase Structure Grammar - Context Free Grammar

Chomsky (see, e.g., Winograd, 1983) had a major impact on linguistic

research by devising a mathematical approach to language. He

defined a series of grammars based on rules for rewriting sentences

into their component parts. He designated these as, 0,1,2,

or 3, based on the restrictions associated with the rewrite

rules, with 3 being the most restrictive.

Type 2--Context-Free (CF) or Phrase Structure Grammar (PSG)--

has been one of the most useful in natural -language processing.

It has the advantage that all sentence structure derivations

can be represented as a tree and practical parsing algorithms

exist. Though it is a relatively natural grammar, it is unable

to capture all of the sentence constructions found in most natural

languages such as English. Gazder (1981) has recently broadened

the applicability of CF PSG by adding augmentations to handle

situations that do not fit the basic grammar. This generalized

1 1 " ... Charniak and Wilks (1976) provide a good overview of the various

approaches

9
Phrase Structure Grammar is now being developed by Hewlett Packard

( Gawron et al . , 1982 ).

2 . Transformational Grammar

Tennant (1981, p89) observes that "The goal of a language analysis

program is recognizing grammatical sentences and representing

them in a canonical structure (the underlying structure)." A

transformational grammar (Chomsky, 1957) consists of a dictionary,

a phrase structure grammar and a set of transformations. In

analyzing sentences, using a phrase structure grammar, first

a parse tree is produced. This is called the surface structure.

The transformational rules are then applied to the parse tree

to transform it into a canonical form called the deep (or underlying)

structure. As the same thing can be stated in several different

ways, there may be many surface structures that translate into

a single deep structure.

3 . Case Grammar

Case Grammar is a form of Transformational Grammar in which the

deep structure is based on cases - semantically relevant syntactic

relationships. The central idea is that the deep structure of a simple sentence consists of a verb and one or more noun phrases

associated with the verb in a particular relationship. These

semantically relevant relationships are called cases. Fillmore

(1971) proposed the following cases: Agent, Experiencer, Instrument,

Object, Source, Goal, Location, Type and Path.

10
The cases for each verb form an ordered set referred to as a "case

frame" A case frame for the verb "open" would be:

(object (instrument) (agent))

which indicates that open always has an object, but the instrument

or agent can be ommited as indicated by their surrounding

parentheses. Thus the case frame associated with the verb provides

a template which aids in understanding a sentence.

4 . Semantic Grammars

For practical systems in limited domains, it is often more useful,

instead of using conventional syntactic constituents such as noun phrases, verb phrases and prepositions, to use meaningful

semantic components instead. Thus, in place of nouns when dealing

with a naval data base, one might use ships, captains, ports

and cargos. This approach gives direct access to the semantics

of a sentence and substantially simplifies and shortens the

processing. Grammars based on this approach are referred to

as semantic grammars (see, e.g.. Burton, 1976).

5 . Other Grammars

A variety of other, but less prominent, grammars have been devised.

Still others can be expected to be devised in the future. One

example is Montague Grammar (Dowty et al., 1981) which uses

a logical functional representation for the grammar and therefore

is well suited for the parallel-processing logical approach

11
now being pursued by the Japanese (see Nishida and Doshita,

1982) for their future AI work as embodied is their Fifth Generation

Computer research project.

12
F . Semantics and the Cantankerous Aspects of Language

Semantic processing (as it tries to interpret phrases and sentences)

attaches meanings to the words. Unfortunately, English does

not make this as simple as looking up the word in the dictionary,

but provides many difficulties which require context and other

knowledge to resolve.

1 . Multiple Word Senses

Syntactic analysis can resolve whether a word is used as a noun

or a verb, but further analysis is required to select the sense

(meaning) of the noun or verb that is actually used. For example,

"fly" used as a noun may be a winged insect, a fancy fishhook,

a baseball hit high in the air, or several other interpretations

as well. The appropriate sense can be determined by context

(e.g., for "fly" the appropriate domain of interest could be

extermination, fishing or sports), or by matching each noun

sense with the senses of other words in the sentence. This

latter approach was taken by Reiger and Small (1979) using the

(still e mb r ionic) technique of "interacting word experts", and

by Fin in (1980) and McDonald (1982) as the basis for understanding

noun compounds.

2 . Modifier Attachment

Where to attach a prepositional phrase to the parse tree cannot

be determined by syntax alone but requires semantic knowledge.

13
"Put the plant in the box on the table" is an example illustrating

the difficulties that can be encountered with prepositional

phrases

.

3

.

Noun-Noun Modification

Choosing the appropriate relationship when one noun modifies another

depends on semantics. For example, for "apple vendor", one's knowledge

tends to force the interpretation "vendor of apples" rather

than "an apple that is a vendor."

4

.

Pronouns

Pronouns allow a simplified reference to previously used (or

implied) nouns, sets or events. Where feasible, using pragmatics,

pronoun antecedents are usually identified by reference to the

most recent noun phrase having the same context as the pronoun.

5

.

Ellipsis and Substitution

Ellipsis is the phenomenon of not stating explicitly some words in

a sentence, but leaving it to the reader or listener to fill them in.

Substitution is simi lar--using a dummy word in place of the ommitted

words. Employing pragmatics, ellipses and substitutions are

usually resolved by matching the incomplete statement to the

structures of previous recent sentences --fi ndi ng the best partial

match and then filling in the rest from this matching previous

structure

.

14
6. Other Difficulties

In addition to those just mentioned, there are other difficulties,

such as anaphoric references, amb iguous noun groups, adjectivals,

and incorrect language usuage.

6 . Knowledge Representation *

As the AI approach to natural language processing is heavily

knowledge based, it is not surprising that a variety of knowledge

representation (KR) techniques have found their way into the

field. Some of the more important ones are:

1. Procedural Representations -The meanings of words or sentences

being expressed as computer programs that reason about their

meaning

2. Declarative Representations

a. Logic - Representation in First Order Predicate Logic,

for example.

b. Semantic Networks - Representations of concepts and

relationships between concepts as graph structures

consisting of nodes and labeled connecting arcs.

3. Case Frames - (covered earlier)

*More complete presentations on KR can be found in Chapter III

of Barr and Feigenbaum (1981), and in Gevarter (1983).

15
4. Conceptual Dependency - This approach (related to case frames)

is an attempt to provide a representation of all actions in

terms of a small number of semantic primitives into which input

sentences are mapped (see, e.g., Schank and Riesbeck, 1981).

The system relies on 11 primitive physical, instrumental and

mental ACT'S (propel, grasp, speak, attend, P trans, A trans,

etc.), plus several other categories or concept types.

5. Frame - A complex data structure for representing a whole

situtation, complex object or series of events. A frame has

slots for objects and relations appropriate to the situation.

6. Scripts - Frame-like data structures for representing

stereotyped sequences of events to aid in understanding simple

stories

.

16
H. Syntactic Parsing

Parsing assigns structures to sentences. The following types

have been developed over the years for NLP. (Barr and Feigenbaum,

1981 )

.

1. Template Matching : Most of the early (and some current)

NL programs performed parsing by matching their input sentences

against a series of stored templates.

2 . Transition Nets : Phrase structure grammars can be syntactically decomposed using

a set of rewrite rules such as indicated in Figure 1. Observe

that a simple sentence can be rewritten as a Noun Phrase and

a Verb Phrase as indicated by:

S NP VP

The noun phrase can be rewritten by the rule

NP -9- (DET)(ADJ*)N(PP*)

where the parentheses indicate that the item is optional, while

the asterisk indicates that any number of the items may occur.

The items, if they appear in the sentence, must occur in the order

shown. The following example shows how a noun phrase can be

analyzed

NP DET ADJ N P\L

The large satellite in the sky-*. The large satellite in the sky

where PP is a prepositional phrase.

17
GRAMMAR

S NP VP

NP (DET) (ADJ*) N (PP*)

PP PREP NP . VP VTRAN NP

Figure 1. A Transition Networkfor a Small Subset ofEnglish. Each diagram represents a rulefor

finding the corresponding word pattern. Each rule can call on other rules to find neededpatterns.

After Graham (1979, p214.)

18
Thus, the parser examines the first word to see if it corresponds

to its list of determiners (the, a, one, every, etc.) If the first

word is found to be a determiner, the parser notes this and

proceeds on to the next word, otherwise it checks to see if

the first word is an adjective, and so forth. If a preposition

is encountered in the sentence, the parser calls the prepositional

phrase (PP) rule.

A NP transition network is shown as the second diagram in Figure

1, where it starts in the initial state (4) and moves to state

(5) if it finds a determiner or an adjective, or on to state

(6) when a noun is found. The loops for ADJ and PP indicate

that more than one adjective or prepositional phrase can

occur. Note that the PP rule can in turn call a NP rule, resulting

in a nested structure. An example of an analyzed noun phrase

is shown in Figure 2.

As the transition networks analyze a sentence, they can collect

information about the word patterns they recognize and fill

slots in a frame associated with each pattern. Thus, they can identify

noun phrases as singular or plural, whether the nouns refer

to persons and if so their gender, etc., needed to produce

a deep structure. A simple approach to collecting this information

is to attach subroutines to be called for each transition. A

transition network with such subroutines attached is called

an "augmented transition network", or ATN. With ATN's, word

patterns can be recognized. For each word pattern, we can fill

19
NP

** The payload on a tether under the shuttle.

DET N PP

The payload on a tether under the shuttle.

PREP NP

on a tether under the shuttle.

DET N PP

a tether under the shuttle.

PREP NP

under the shuttle.

DET N the shuttle.

Figure 2a. Example Noun Phrase Decomposition

NP

Figure 2b. Parse Tree Representation of the Noun Phrase Surface Structure .

20
slots in a frame. The resulting filled frames provide a basis

for futher processing.

21
3. Other Parsers

Other parsing approaches have been devised, but ATN's remain

the most popular syntactic parsers. ATN's are topdown parsers

in that the parsing is directed by an anticipated sentence structure.

An alternative approach is bottom -up parsing, which examines

the input words along the string from left to right, building

up all possible structures to the left of the current word as

the parser advances. A bottom-up parser could thus build many

partial sentence structures that are never used, but the diversity

could be an advantage in trying to interpret input word strings

that are not clearly delineated sentences or contain ungrammatical

constructions or unknown words. There have been recent attempts

to combine the top-down with the bottom-up approach for NLP

in a similar manner as has been done for Computer Vision (see,

e .g . , Gevarter , 1982 ) .

For a recent overview of parsing approaches see Slocum (1981).

22
I . Semantics, Parsing and Understanding

The role of syntactic parsing is to construct a parse tree or

similar structure of the sentence to indicate the grammatical

use of the words and how they are related to each other. The

role of the semantic processing is to establish the meaning of the

sentence. This requires facing up to all the cantankerous ambiguities discussed earlier.

In natural languages (unlike restricted languages, e.g., semantic

grammars) it is often difficult to parse the sentences and hook

phrases into the proper portion of the parse tree, without some

knowledge of the meaning of the sentence. This is especially

true when the discourse is ungrammatical. Therefore, it has

been suggested (see, e. g. Charniak, 1981) that semantics be

used to help guide the path of the syntactic parser. For that

case, syntax presses ahead as far as it can and then hands off

its results to the semantic portion to resolve the ambiguities.

Woods (1980) has extended ATN grammars for this purpose. Barr

and Feigenbaum (1981, p. 257) indicate that present language

understanding systems are indeed tending toward the use of multiple

sources of knowledge and are intermixing syntactics and semantics.

Charniak (1981) indicates that there have been two main lines

of attack on word sense ambiguity. One is the use of discrimination

nets (Reiger and Small, 1979) that utilize the syntactic parse

23
tree (by observing the grammatical role that the word plays,

such as taking a direct object, etc.) in helping to decide the

word sense. The other approach is based on the frame/script

idea (used, e.g., for story comprehension) that provides a context

and the expected sense of the word (see e.g., Schank and Abelson,

1977) .

Another approach is "preference semantics" (Wilks, 1975) which

is a system of semantic primitives through which the best sense

in context is determined. This system uses a lexicon in which

the various senses of the words are defined in terms of semantic

primitives (grouped into entities, actions, cases, qualifiers,

and type indicators). Representation of a sentence is in terms

of these primitives which are arranged to relate agents, actions

and objects. These have preferential relations to each other.

Wilks approach finds the match that best satisfies these

preferences

.

Charniak indicates that the semantics at the level of the word

sense is not the end of the parsing process, but what is desired

is understanding or comprehension (associated with pragmatics).

Here the use of frames, scripts and more advanced topics such

as plans, goals, and knowledge structures (see, e.g. Schank

and Riesbeck, 1981) play an important role.

24
J . NLP Systems

As indicated below, various NLP systems have been developed

for a variety of functions.

1 . Kinds

a . Question Answering Systems

Question answering natural language systems have perhaps

been the most popular of the NLP research systems. They have

the advantage that they usually utilize a data-base for a limited

domain and that most of the user discourse is limited to questions.

b . Natural Language Interfaces (NLI's)

These systems are designed to provide a painless means

of communicating questions or instructions to a complex computer

program

.

c

.

Computer-Aided Instruction (CAI)

Aren (1980, p. 465) states:

One type of interaction that calls for ability in natural

languages is the interaction needed for effective teaching

machines. Advocates of computer-aided instruction have

embraced numerous schemes for putting the computer to use

directly in the educational process. It has long been

recognized that the ultimate effectiveness of teaching

machines is linked to the amount of intelligence embodied

in the programs. That is, a more intelligent program would

be better able to formulate the questions and presentations

that are most appropriate at a given point in a teaching

dialogue, and it would be better equipped to understand a student's response, even to analyze and model the knowledge

state of the student, in order to tailor the teaching to

his needs. Several researchers have already used the teaching

dialogue as the basis for looking at natural languages

25
and reasoning. For example, the SCHOLAR system of Carbonell

and Collins tutors students in geography, doing complex

reasoning in deciding what to ask and how to respond to

a question. Meanwhile, SOPHIE, teaches electronic circuits

by integrating a natural - 1 anguage component with a specialized

system for simulating circuit behavior. Although these

systems are still too costly for general use, they will

almost certainly be developed further and become practical

in the near future.

d . Discourse

Systems that are designed to understand discourse (extended

dialogue) usually employ pragmatics. Pragmatic analysis requires

a model of the mutual beliefs and knowledge held by the speaker

and listener.

e . Text Understanding

Though Schank (see Schank and Riesbeck, 1981) and others

have addressed themselves to this problem, much more remains

to be done. Techniques for understanding printed text include

scripts and causative approaches.

Arden (1980, pp. 465-466) states:

To understand a text, a system needs not only a knowledge

of the structure of the language but a body of "world

knowledge" about the domain discussed in the text. Thus

a comprehensive, text -underst andi ng system presupposes

an extensive reasoning system, one with a base of commonsense and domain-specific knowledge.

The problem of "understanding a piece of text does, however,

serve as a basic framework for current research in natural

languages. Programs are written which accept text input

and illustrate their understanding of it by answering

questions, giving paraphrases, or simply providing a blowby-blow account of the reasoning that goes on during the

analysis. Generally, the programs operate only on a small

preselected set of texts created or chosen by the author

for exploring a small set of theoretical problems.

26
F. Text Generation:

There are two major aspects of text generation, one is

the determination of the content and textual shape of the message,

the second is transforming it into natural language. There

are two approaches for accomplishing this. The first is indexing

into canned text and combining it as appropriate. The second

is generating the text from basic considerations. One need for

text generation results from the situation in which information

sources need to be combined to form a new message. Unfortunately,

simply adjoining sentences from different contexts usually produces

confusing or misleading text. Another need for text generation

is for explanations of Expert System actions. Text generation

will become particularly important as data bases gradually shift

to true knowledge bases where complex output has to be presented

linguistically. McDonald's thesis (1980) provides, one of the

most sophisticated approaches to text generation.

g . System Building Tools

Recently, computer languages and programs especially

designed to aid in building NLP systems have begun to appear.

An example is OWL developed at MIT as a semantic network knowledge

representation language for use in constructing natural language

question answering systems.

27
2 . Research NLP Systems

Until recently, virtually all of the NLP systems generated were

of a research nature. These NLP systems basically were aimed

at serving five functions:

a. Interfaces to Computer Programs

b. Data Base Retrieval

c. Text Understanding

d. Text Generation

e. Machine Translation

A few of the more prominent systems are briefly reviewed in

this section.

a . Interfaces to Computer Programs

One of the most important early NLP systems, SHRDLU, was a complete

system combining syntactic and semantic processing. This system,

designed as an interface to a research Blocks World simulation,

is described in Table 1 1 a

.

SOPHIE (Table 1 1 b ) , a Computer-Aided Instruction (CAI) system,

made use of a semantic grammar to parse the input and to provide

instruction based on a simulation of a power supply circuit.

TDUS (Table lie) uses a procedural network (which encodes basic

repair operations) to interpret a dialogue with an apprentice

engaged in repair of an electro-mechanical pump.

28
b . Natural Language Interfaces to Large Data Bases

One of the important and prominent research areas for NLP is

intelligent front ends to data base retrieval systems. LUNAR

(Table 1 1 d ) is one of the most often cited early systems. It

utilized a powerful ATN syntactic parser which passed on its

results to a semantic analyzer.

PLANES (Table lie) was a system designed as a front end to

the Navy's database of maintenance and flight records for all

naval aircraft. This semantic-grammar-based system ignores

the sentences's syntax, searching instead for meaningful

semantic constituents by using ATN subnets. These subnets include

PLANETYPE, TIME PERIOD, ACTION, etc.

29
^ T>

8

•«HS'

u o f9 w O u-i 5 TJ 4J S T*

u 3

*

oi oi 3 S3

£ ll

c

O • u X

•*« >1 o« <u 3 iJ t • n ra 5 aj

•r^ u_| .q c w

h W 4J d

<u cn to 3 8 g. s .s g O AJ J) U

P3 w o

‘ “

id

ii Is

0

Li01 u r-l

<0 a. <2

S3 ^ w % C-M

35 ^ S-S S3 W -*H >iWH'O co a> U 3 AJ

0) O (0 U $ u

JJ w 3-3:2 u e a •3 Q •• iu vi n Qj °h>J oi m c

E oi <0 u-i o'® e o

S3oH

sua

fiw

W 0) m-rHo yC C AJ (1) M § OI U 6 <4-1 gj 8

(0 A3c

a>

in2 S'

CL t-4

<1> > n*

d 13 S O H H

•r^8?8C U

TO J* CL

I I

* S 4S "«!'O TJ

*|H I—

I

> C C M

<3 o o

8

’S &no o

c

01 •S&S'o

53 c^i^SfloijCi • u o 51 •h li ai e C u oi i) C a O. 5) m nS £ is M .H 4J jj o C 0) XJ XJ u

-a

• 5fB |3 6

a j s a § 8

"Jr? . 3 3

* § o IIa 6°oi *

in

0i w*m

3

3 gs-g

'S *

s-i

•h a

3

II

,^’iSig-.

0iSS’2g$.t!3o ,3~(Sj03 . *s u

‘ S -S XI ^-S ^ n g 3 g 8.-8 8 8

S JJ 0) «. 4J n him « c

n njiH c o ^

H O O

w u 2 i § 2 ^53 gtfg'g i

-8' 2.

:

w9•H

U4

0) -H u u

•iH fl) fa >

S'

-r-» §

a

mu oiS3

&8^ <D -rH

01 *8 SS U M 01

io cu jy

XJ 3 01 8S

fa O J=

a

^*8

4J O

x -u s

M

oi 'H

01 10 4J

<0 c u -X 8 £

fli!

Ou

cu

>1 d

8

3

01 sc

j t § J2

&H Mg 8

13

Dl 3 ffl

ej

u

S'cN j f|3

fl (0 TJ C r- • U-i rH rH s g ^

£ rH Is.&g

for

noun

phrases

to

redi

the

stilted

nature

of

tl

text

response.
S'

13

xj o

x:0"4J

•Hc

cn

01 -rH -U 01 uO 01

S'S H c

8:8 H^ UJ w o

Si

Si

§g . w 53

XJ ^ UOW« <1) 'O l-i U ^ 0) ou8

53 S

xJ

O

iH -rH

H 3 XJ o u in m u «

rH -H CT1 1° S’ « c §• W 14 XI

It) 01 0) aitg O it) XJ Siu O

1-4

O XJ 8U

o> e

ai -5 U rH S3

H5«)§ S ^ - ssI s

XJ XJ

0) 0) §?§r IS

al

11

•Co • 01 XJ 01 gas s * a S | is i

T3 D> 3 "fo ai 855

It) XJ 2 •• C

13 ^ i C u 3 O a»H u.h

4J 4J S3 53 2

xj c i-i 9

83 ^ § 3 XJ 73 3*g S

jj fd

10 2 <u IB 8 xj s MS

1= s o c

xj xj e

oi

y e

•*4 9 O

33 ^ 4J .!3 w w

XJ

013AO

1-1 &

!>

XJ

01 w ^ CQ

cSg a, S' • U rl ’H H JJ -Q 4J < 8 1 8 • pH M ,25 uw t«w
2o a'S O u-i H ° £ 2

Q.

O g'S ds£ §

4J s s U

U T3 * O^rl 4J (G 1 2^2 8.! a rH -U © 5 5 J S S «5B.

eg

CT» <tJ T3 C U rH

13

u -u § 3 S

toa©

M 4J

at to© rl 4J

S'r

(0 0) -H O)u d> Sl 5 g*S |

in -y aj ca>1 c D W -H

£> 'g in jo S 88 to *338U_l U-I i C o yu

Bo » -U

w 5J -a

w

OT(ua)'

n S§, mS

X ClU'H o <-H

SSii. * - s. !g? y 5 4) . O O u Cg h O 3 . 2 ig*S&6 * HQO-umQuhQ © .x 5 O 3 «JO'-iXO£ei5 >uj Q,ai » © -h 13 8

§3

"S’0

8«u u a a

in a) 4Jc H

©

US r~i

•A

"* 85 8

8^ c ©£ ojn^B U 4J U © 3 C

IH

U U'H

©©

U U-l

©

M

© x:

©

*j

u

u j!

Ul lu1 X -4 fjtj&»

SS'Sft w u * D 8 8 S

fl O'

u

w

O 5 3 -S 2

-* 3 B llf” 3 iJ'Hji , © O (fi 1/1 Jj U -r-l 4J -rH co y c U © -M © T3 rvu II 181!3??S o

<0 • •r4 4J 00

<r» rH if § jj 8 8 c

'•§

os

0) £ S'

,s

g i

as s

K.2 6 ^

1o -iJ 3o 8 -s © s

(0 w1 £o

(N

ro

TAdLE

lie

NATURAL

LANGUAGE

UNDERSTANDING

SYSTEMS

C

CT3

W

U

O

O TJ4J 'n w c

<0

CQU-4 4J < w

(0

OW

fi - 3 « 5 8 . t

ig 8 &

•pH 4J • -H (D 0) . Q —

lH -N G\ 1•H4Ja 4J >, Ma

$83 • C U 4-4 -* 3 u <V u

CQ 8 ^ S Z U1 «3 U

<Q <D 0) *h o .q ^ U -U J

.|.s

a 4-> ft1 U—I W

a> o o co i 5; S g 4J rQ U M2|1f (0 cj cu

Is * S

siS: U ••

§>£j S’ o H (O U UJ (/I

<D • 8 a a. 8 M u m « 8 a 0 h t3 c ur 5 D } -u 35

Q) S'

h &>« % 8

aj

g uj j ig

u 3 u ri 3 CT< 0) (0 <9 4J C 4J 4J

ITJ <3C

O «J Z J h JJ Q

gl!

f-O 3 s (0 01 HI m 4) u u £ u 10 ^ 0> 10 W fli £ i) 5> O *3 C .8

4-1

flj o 8 « 85o q 3 " IW

a?

AJ § ? 0J 8*il ft
L

ir

.53

S

4J • o> ai M Vi c

3 a o

2J 2 2J

„ C <0 „ aj •»-< g.&°.2 8

* * Sffll I

°3

05

•H§ 0)>i

tn

o o
V4-I O

U-l as «

s

•*H u CU

0) u w 2 g-fj

(TJ u

<TJ <D <T3 U. 4J

•fH *—

1

I

s

8

W Q W 1 D " <

o O

a

_ _ 4J fl) ‘M *iH

s-p f-S la 01 § 3 gj T3 E

g> S' W O O' rH W £ u JJ TJ u C aJ (1) nj <3 4) a •’* -a £ m .H S (0 -u il.2§s§|8 D CT> -U .* 43 O <3 .Q

„ 3t5

*8

SS. S&5,

EDi g

fe55

U

n5 >,

fO -Q -rH U

3 W-h ^ 0)

nr* C/5 u u >

c <d 4j ta o o

CO t3 U p „ . -H 10 M 4) ^ < a a w «

X -

-g «j CO

<U 4J ON a <u -t

cd <g ffl • td 3 >i 3 m It h

jj c -w ai « a nj

Z J Q <5

.
.3

a) jj ss

I

m

8!> 3= • a

3*2 5

o

4J 3 35 C 4J ffl (0 o o.'o (0 H <H il hi hi

" c

a-u £

>,3 3 o h m 7J 4J

(U W u c

hi Jj

.25 a

rH >

• s

•H

4J ]2

o) 3 35 S ® o £ H

8 * ^ 1 8 . Da a r-4

h> h> .2*35

hi

S5

fl < a

(0 *H

s|

|1I|.||

d> a> q >h u • a

3 8

”.5

sBu-aS-adti- . 355 h g S 23-2

_ K iu J OO 3 hi Tl

0) OJi-iVhl-H*J u hi <D hi w i to hi a> h C 5} 3 M O W JIHH

<y .C O • <u -h hi jS

<D O *U 3 hi <u >hi &S 8 2 S-cr a

nj .Q cn q<-h -h 5 -h .. . O 6 (3d to cu-^

w

5? * CQ

rro

in

information

about

than,

ROBOT (Table Ilf) uses an ATN syntactic parser followed by a semantic analyzer to produce a formal query language representation

of the input sentence. ROBOT has proved to be very versatile.

LIFER/LADDER (Table Ilg) uses patterns or templates to interpret

sentences. It employs a semantic (pragmatic) grammar, which

greatly simplifies the interpretation. Can handle ellipses and

pronouns

.

c . Text Understanding

SAM (Table 1 1 h ) is a research system that attempts to understand

text about everyday events. Knowledge is encoded in frames

called scripts. SAM uses an English to Conceptual Dependency

parser to produce an internal representation of the story.

PAM (Table 1 1 i ) is one offspring of SAM. PAM understands stories

by determining the goals that are to be achieved in the story.

It then attempts to match actions of the story with methods

that it knows will achieve the goals.

d . Text Generation

Winograd (1983) indicates that the difficult problems in generation

are those concerned with meaning and context rather than syntax.

Thus, until recently, text generation has thus been mostly an outgrowth of portions of other NLP systems.

39
e . Machine Translation:

Though machine translation was the first attempt at NLP, early

failures resulted In little further work being done In this

area until recently.

f . Current Research NLP Systems

Table III lists NLP Systems currently be researched.

3. Commercial Systems:

The commercial systems available today (together with their

approximate price) are listed In Table IV. Several of these

systems are derivatives of the research NLP systems previously

discussed.

40
TABLE

III

CURRENT

RESEARCH

NLP

SYSTEMS

• to

CO

<d Z 0) 0) to

•f— 1 5 • c to

a> co e >» i* T3 0 o»-r- o U z * c u id co k. 0) UJ to id id 3 >>4— 3 •r- P o>»— cr 4- SO* 0 c id co O a) to c

4-» id c a> (/> P* ,rd c •r* e -j id pi

a) <d S

P>O 1 -O O)^!— C P> Z tO 0 5 P O

0 * id CL

<u id c P> id •p- to *— to a. -r 0) Id 0) •r— p a) 0) 0) 0) TJ£ L a> -0 c toe s. “O 0J 4-» 4J L. id co s. C E id a E AC 0 Cl c P> <u 55 f— c 0

<U O 0) 4-» DO 0 id C P> _C 0) •r— a) O C P> »— 5

E id 0 to p»

• 1- *-* 3 • •r— M ai id •M Q. a) r— to P> •r

•d CP • O CD CL-O 3 O OJO

L. 0 Id 3 E P> id d CL

• 1- 0 55 3 r- -M *p- O »— to p> CO CD co 0) U fc. CL 0) 0) tO •f— C 0) > E p* CL CL CO _C >>-C id CO CL < DP UIP r“ 3 id 0 0 O 0

CL

lm >» O or O O

4-» O

C c

0) <E OCLO * a

l— r— id <D a 4- 5 > »p“ 0) c

0

* °l • P*

ide

s to a)

55 »d c *o

P> P> *—

*

id

CO c to

id CL

cnc•p— P>

id

a)

s-0

to 0) L. CO z!

q> id

to -Q CO 3 0 id

L- p> 0 O id P> 4- -0 M _ c

—1 —

J

5 z Z 0

0) -Q

id<D >> Id Cl

r— -L> “C

•0 id (1) c 0 r—

a) s •r- O 0

L- -M c

u0)

i- O <D

> <u <d

- CO l+_ Q. E

> =D L. E CD CD 1 Q) •r- 4-) —i -O 4-> DO tO LlCC >0 DUJM 12

<C DO

LU '

id

t- id _ 5t, i

«d c u

id o>

a. gl toz c

o U *P- L -P ao «j

CO u

o <0 •*- * 0) r- O CL O CL

Q)

tO <D tO p> a> id • to id co * r- 3 Q_

<o o id <c C C P> CO

*o <o <o o Q

Q>3>3 4 CTI"- I— S 3 ^ O -M 0)4- 3

tO CL O id C

CL •»" U tO

>—«5I3

<0 jQ <*- u o

a> jc cue

5 tO id

•*- t- P» O C

CL tO ID J 1^ Z 0) 0) U L QJOQ. r l a) h- Q. Lp- Q.

iO id _J •52 5 jQ <0 -U £ (U <*- O U O

‘is is

P> CL E C P>

JS 0) 3

P> g O •»- a* ki3 i! a> +j * S

§

!§££

42 £2CD -O CL 3 CD <2 o* a>

co »— O id id

Sto

o

§

(-o • Q.4J

I/I

t/> 3

•i- J3O

4-> >»

</> i_ >» <u 00 >

(U 3

I

oo

00

>-00

CL. o UJ Ql

CO 2 < 00

I— UJ

0£

jC CO

00

a

•r* •r—

u c 4-> id -O r— o> C QJ (/> 3 >»

4-> 0J id c oo at a> a»4-i C 4-> E UJ E 4-> 4-» a> c 4J C 0) id a)

id »r» 3 s L. id *f a> E *0 a o oo 4- X 3 >» — r- l- 35 . 33 a) O 4-» 4— w L id

00 c • 4- s « OJ 4->

U *f

C <u 4J j: £ 3 00 o {. x i/i a C 3 -M C Id 4-i O +J *o <u o • id cu o a> fc. c •»- U C CO CT3 W 0) “rSi l> cnu -O 4-i 0) Id C CO ‘O E

4-i l-l CU id C id (/> 5,2 o w N (/i id t/> id r- Id •a >r- • TJ • fO U i/I .3 r— CO 00 00 4-) CL <U "O C 0) CO CO qj x js

•f- 00 OD 0) oo Id 4-i Q) f- /— no I 4-> i. E id X 4> 4- r- CO

4-> •»- 4-i 4J

*J Sa a) 4-> 6 o •— <> 1" o c o

<d *o a> id • *o id a) $. 5,

w 1 * 8 ? x -b C

4-i c u c 3 o

"O QJcn 22 a)a

3>4J o

<u 5 do

a 4-* e co 5

i/i i/i e qj »> .c QJ T3 U -P o id l

0) Qu

C

uO T3 o

(/I

O l/l CT> CD 0) <U <UC 4- o qj o 4-i 1 U. r- i. 4- r— CO a <4- ac U 4-i <U +J u ^ i/i -S

<d

x (.O lucn

L C£<M <0 o a.

f— o o O**- c 3 *f- hX •*“ o C C 1 e u c C U a) id c <d • O 0) >» w u

t- o a. <d .x o jx id -a 4->O *r- >| CO c 4-i r— 4J

O

qj •<— •— id •*—

l/l 3, i0 id •f L. id • C C/I

u +i j: oo

a 4-i •i- jc c d id co a> a> o qj S C IO VI CU «r- oo id OJ lO 4-4 • 4-i U 0) U C V O 0)0) i-

•r- AJ

N 4- 4J

—

NU l/l OO

C L. 4->O

O

N 4-> Id Id C/l <4-

O 1— •r- *f— 3 CO •i- Q. Su rd id 4->

X «f- >»C 3 3 * « o

in 41 fl r—

U CL

C n— OJ o 4» Ur 4-i r— *r- U> CT> o

<u a> •r- 0) 4-> id •1- -o -o

4-i c e

S- l/> 0)

u >> o Id

C

C »- -a E i/l X 10 4-> Q. Si u C T- 5 <U *r» C 4-i «d Id i— C •>“ 3 OJ c ID oo 3 iO 3 QJ H£W^d < (0 no o O o O ° ! o O

a) *o o C u. >> id (U

4->

a 4-> CO -C o CU

4-i

U JZ

*J < id </>

u

u <_> c

OJ < nu «

4-i • Id 00 X Z -a

O 01 5 e

t- <4-C 4- cn 4- <d Q. O t- o to O 1— > id w 1—1 • u • c < = l-l ID O 3 UJ c

OI C7> o c c •r

>r- •r— 4-> •a “O id c c id id to

4-* 4-i c

oo oo id W u w

<u QJ »-

-a •a c c 0) =D c

4-> 4-i jc: X X a

0) <u id H— h- Z

to

4-i 00 x .f- <u ^hr- <U

id > C -f- < 4-i CL

J00 U -r-

•r- S.

4-i

O

id co E <U

a o a 4-i UJ 3 4- a o < O UJ z '—’

co

(U <4-

l/l 4-> L

qj c > >— -o

(O •*- c <o OJ u e o 3 -m

HI

O VIU 4J IS e 'r* <u

cr» (0 • O & V r~ • <J o e c </» tow

a) ia 3 -i- ai-o

>0 qj

OJc

\A0)3 §

cu >— o o io

c/l 01 <*- a> u <o e au« o o

iii-y+Ji*.

U+J-r- q/Sg'ggf

S'"" <5 2 qj l/ll— O 10

<0 I— 3 0) i*e «tc 3 O CJ 4-> ICO f* •<- </• a. cn+J oi io c o o <u n •i- c »— t/l e s or (014- <u

ju .C JS •«- E <o 4-> a. s

>» S’ Z

0)

00

OJc

<d&

•“D

ro
I

o o o o

ft

1/1 £

-J

4-> 0*1 O >* Z 01

0) S £! x, S*j

0) 01 « a,25 UJ?

• I 6^5

uo

(T3 (/> 0) >> -J 01

I

9

,

|
coo

oo

>-

oo

H-l ZCo UJ CSC —I < CO Ltj <C CO

h- UJ

QC

UJ

CSC

CSC

<u

OS (ST 1 P O 03

in L. ITS CO “O 3 c u

t- a +J CO C E O d 3 • 3 O 03 c • d 95 T3 CO o o P • 1- • 4-» as i- co u U (SI C -O r- 3 4-> CO 3 (/I d QJ CO •* O ^ 2 "d

(ST •!— * d <33 Q 4-> e 03 O as a • JZ d

03 U 03 03 >0.0 — -O c > u 5 o) a 03 CO o 3

u CO 03 CJ 03 -C 03 03 03 o 0) o 03 CD CL C 3 CO u as as CL P C P 03 O C P

as

•»- o

<u JC -O •f— »— T3 03 •»- CO L. 03 cd <d (ST 4J as L •»» *C °L i- c JC P 03 o5 P •r» p 03 U 1- 03 £ 03 03 4-f u CL 3 ns • 5

03 CO * CO Q. d u f—

•

a »— d CO uo* 5

o 5

a CO CL at E co CL V- X d -C a.

i/I 0)1/) 0J • C 03 (ST 4-> •p* St x d 03 03 C 0030 CO *rJL3 -s u c 3 it) >t ist « •!— 03 4J CO •r- > •1- X 3 SB 03 Q. C £ o o c 03 •»- P

o 03 cr r- OS 1. B O C CO Cd 03 CO •»- o CL •r- 4-> •»“ r— r—

•

-X -Q »— r- O T- P *3 -Q OS I— a O 4J JC <d 3 4-» as u C >> TD »— P p d 03 3

0) 3 •r— P <j ns cnt- >1 u CO 3 d 3 Q-'I- W f— l. d U 4- d cj u CO O C E

ol o> c > C 3 a — ja •— <u 4-> U >> e d $ Q 3 d O L. n- 03 03 P UJ

lO Q O d CL*0 4J C (U OP CO JD S- c o 1 P P 03 jz -a CO >>

<o o e u (J c O t- JC 4J -o o U«U«« 0.1—

•»- x 03 c d o c X co c C CJ u 3 CO P P p _ CL o co d O 4-> -C 03 u •r .X 03 03 o 03 U O r- 3 CO

0) E P Q. Q. <u -r- +J 10 03 C 4-* 03 r- a »— •r- 4-> C P * *r* 03 d 1 L. d o

T3 -O CO * d 0) •tJ U ns as o •M O C > d 2% 4-> U 8 •r <o P L. P 03 o ^ P

o 03 •r» (/) 03 d d 5ist cc o. j. j; •!- as i- o <J)3 u

C U >» d •r P C 03 Q. C 03 CO c

CJ CO C 03 gj CO O CO c -o P O *r- U *r- d •*- u c JD co C 3 03 6 1ST ITS S- c o e &- CO .X o B c d C U d 3 CO

OJ JC. 0) c P in • u a« CP as Cd O 03 e as is) d 03 CO 03 i- -o d CJ Q. P r— CO 03 P

0) O -C o O <u i— •«- o. OT'r- as o o t- « -C 3 c O i- d (ST ns u C 03 •f— 03 *r- L. (O 03 CL r— d

JC i- o> u • to B co u u as 03 •r“ *r- s_ P d 0) 03 cj .x d P 3 JC

<J d E co (/> +J CO O O O </)(/> l_ cd CO ns U e »— s- o • c P TD •r— *r- 03 CUP •r— P c J. Q-*-> in •>- c c U 4- •i- 4-> CL 3 1 -M 1 CO •f- o P p •— >> j: 03 JC * g,« CO •r* <0 cl as to o*o

as f as — as

<d 03 O d as e c 03 f—

•

« p 3 •— CO 1 P U u CO 2 0) c o d >»jC o o O O 03 i 03 03 •»" I 03 03 u • •r- 4-> *r— CL jd U OSLO OT4-> +s CO • 03 4-» 4-» 4-> as 3 -P d o CO JZ Z 5

U < T3 P P CJ in 3 co CO d •i- TS (U "J •P as 4- 4-> IS) 1ST *i“ a3 L. u a> •r* +j -o £ o S- Q 03 CJ 3 O 03 • P CO C d JJ CO 3 P u >* 03 N cd o CO 3 U 4-> O co d Q 4- E nj d r— • 03 Z — s- •»— d

e o 01 CJ O P c 5 Cf O U 1ST o o •r- p a CO-r- •i” L 03 Q •»- o (O i CO JZ P 03 O 3 U

93 3 o O O <d ns 9 as as a. o r* H cd L. 4- Q. 1ST CO •* co c r— L. C JZ r— d •*— > 03 03 JC u o 4- 0) c S OWr- E O IS) •r JB 03 -9 4-1 s L. O) O 03 o •f CL d 03 d 03 l. O 03 C P

CJ P u CO 3 4-» §

3} c as as j. «sr u -C 4- e 03 _ O d CO CO CO •r- P CL r— *r— o £ >»0) u JZ — P

CO CO CL <C 3 <j d (SI 1ST 1ST <c o. ns at h- O < E < 4J CL ZD T-C ID P 3 d O. JZ 03 h£ > CL P »— 3 o O o o O O o o O o o O

<C o.

QlO r—

• jC cd a.

co

>-CO

CL CO

O P

il

as o

c •»- r- P

*o <0 C L. d <y P C

CO 03 U CD

03 O P C X

=> 03 X *o

<1) C — <0

• fmm P d

03 CL c

CJ 03 o <c c a o d p p • d *

to •»- >, c ^ C CJ c u u o c/> d 03 d O E P CL

• L c P U 03 M o O O CD r— P HH C

• c • CC 03 ID h-. 3 oo z

cj P »“ <0 P CO d C

§

03 "O P C

3 O < O

ld

dI
TABLE

IV

SOME

COMMERCIAL

NATURAL

LANGUAGE

SYSTEMS

S jI 3

- 3

<d U > O 1)

_ 0) Z

S

oo 03

00 03 id

0> -Q

id CM 4-> id

4-> *0

£ 4

(/) C

0)

4-> —

5 S'

0) 0) -C -O

4-» C O 3

C 00

t-H wo

id — X<d

r— » O E

4-

> f—

5- 03 < 3

03 5

*

3

><

(1) 4~> C 03 •2E r— O •— 4- 3 C O M

I i

‘5 g •f- 4_) WO U4Jh 00 -r- wo

03 O >>T3 03 > CO OO

•r- O ^ 0-0

S- OT oo <D

03 O'- -*-* O 4- lO 03 3

-— O OO >—-Q

*oc

03 ^0) x >

00 -r- *—* 4-> —I 3

UJ X

o>c

F" *o

l/l 0)Ul

03 .a

a)cn £803 F- S

|

1. CD * -C

TS§

a>>

03

t/> »— rs4-* -Q

</» >» *

\A 03 H 5

u -a

0)> 0) 0) 0. 00 id

ft

<u8

4- I U C oo 03 03 03 U 4-4

*-> 03 a> os C -C *3

. " »1 q i§4-> s

cn /E co

wo wo c 53 <D >»

on a

i/t id

I oo >>4-

4-4 •*-(» U

oo u x a> u 03 03 cn 4-> •»- u c c • 4- O C •»- *f- </» f— 03 4-> 03

03 Q. 03 03 00 X O S- U

•M 03 <0 . > UJ

£800

03 C

> 03>

4-4 03 r- nr I * o z

z

<oo

Z 00

*-• O'

-J CD

_J 03 a- 03 QC oo o 4-» < "O 1/1 UJ CO C CM >>

Q- OO i/)

2 . a c

03 03 c • OMJfO

•r *f- qp

00 4- O'

a> 4- Q 03 .8 § ^

-fl* O A-» *-» aQ.

c >>.Q

0) S- (t

4-> 03 I—

4-» > -F-

•f- id £23

8N•p84-* 003o

M | U ^ S

“S u

4J O

U 4- • O on “a>»aa 4-> *— Q 3 z cl .?&§

ZD. U

8 a? O Uf- C 03 03 CL4-> >

*5 C >V p «3 c

U E c

Qinoo

03 03 h- >

4-

» 4-> or

JC 03 UJ

CT> > U.

<d o J o 5- 03 KO

4-» O 4- lO OO '— O OO

</» 4-

03 O n—* wo03

03 C > •*-

33

wo cn

<13 C

U) *F- s -Cu4J

• <d O E

oo u • 03 «/1 3 4-» U

CT>4-» 03 C 03 4J

»- Q. U r- (O ^ u

4P 4-» 03 5C5

2

03

03 4-> U 3

03 Q. t §

03 U 4-» I 5 g

4-4 81

00 U

>> o

00 4-

03C

*• <

4-

> C_) 03 ^ •* 5- 03

<d »— Z rd>

>- >»c

c

. 8

< CT» 0O 04

3

ro8wo<d

03 F»

03

8N
oo

oo

>-un

UJo

CDZ

CD t < <

500

jCo

<dO

c.Q.

CL

Id

O 0) 00 4-> C

•r- O Q-r—

o> 3 id C *—

Bk I

S'SrS a

C L- CO

(0 0(0

(/) 31 >> «

C 0) 00 5 IS i

IS .iS

r— X

00 O 4-> C LS (0 aw U CL-r- h fl D

(Vo>

<J id t- 3 4-> O) • id c c IJ3.2

4-> 4-> 3 p- (O <£ (d r—

L- 00 3 C

4-> <d

fd l.

8

CL

S-o

CO

U0» co

0) * 5 ° *o >

r- O

0) s- 3 Du

co>> oo

0)o>

id3

oo c

c o

(d *rC CO

•r- C

id O

e •»-

4-> * id

c\j u

00 o

at a.

f-H U

O

4- u

o

r— C

**

0)>>-M

JQ idc

-o I r* •» O 4-»

«/» f— 8 0)

• o> X i- o id

L. r—

CL

CL O < 4->

£

<dO

1-CL £

a

u

o

<u fo o

-C r- i— >,

*J (O I/I UJ o c —

i/i'p (d a CD C l- CO T3 £ 4J'r

•»- a td 52S«

kui 5 O -C

+J <+- 0)

IO Q C

JC VI +3 O

+j c £

t. jj (— </> o <o a. j-> e «— «/i o

o </i •<- HI f- c "O >—

J-» <0 <v U k « VI

•r- +j o 00 c

VI « 01 # 3 JC • o vi -u vi

ia •<- -o -o QJimi-OL.

vi A or O 3 > > X >

£id

se *5

‘Sid </) c

id

a) u

4-> a) u at

id id

: 3

a) cn

4-> C c id

o

00 >

CL o 4k

CO £

£ai

> •P" JZ •p •p E cn a) 3 a> co •r- <0

•p* u +3 0) t. 00 CO e u WE C *

u 0) •»- C7> 0) S

•p •p CD 5 O IA Q 3 2 Id 3 id a) O 4- im C/> »P E <0 cr u cr E -*-* id 3 O P 5

3 <D 5 4-» E “O >»JC Id jy no e r— p* > p- id *p c O 4J •— -M r- VO 00

ai *— id O i— u t o s- 0) C -p- 0) >101 z < <4- o id CD 5 Q_ CO o 2 S- l/l -H o O o o o

id r— (/) 0) 0) CC CO

id O GO

4-> id

P OJr- L. •p- l- 43 3 a c 3 id L> -O "O <D e <D 04- (d U C 4-> 4-» a? 0 4- CO B s id id e 3

E e a) co 0 •r- o

O U <D u ? >»-a ^ Ldh 3

4- C CO

jj 3) <o U 4-* j-> £.2 £"8

4-> 3 CO L. co cn a> c c a> «m o •*- .e c

oi-2 fl)

C0 c <4- C0

o> U

at aS8

St

*5

<U 4J

fe o

u

"O

a> ia

i/) 3 C

<U _ 0/ _

is y y ia O B C r-

+> O'Jfl i E <3

I IU . O oie

rn -a o

i i 33 •*- in »— y*

i—v X i/i o <u

10 C 3 X Or

i/I V « c

V. C •!- r* O

<U 3 U io i >0 I t- </» i. •>- I cu +J I/I c c

•I- O

s'-S

c Id

•p* V.

a) o -s.

<d id isp" CL

id 0) > u

id <d H <4- i- o a) CO +•>

Z I

4-> X

^ hco

co <d

id p- x •—

a) id »— Q
K. State of the Art

It Is now feasible to use computers to deal with natural language

Input In highly restricted contexts. However, Interacting with

people In a facile manner Is still far off, requiring understanding

of where people are coming from - their knowledge, goals and moods.

In today's computing environment, the only systems that perform

robustly and efficiently are Type A system$--those that do not

use explicit world models, but depend on key word or pattern

matching and/or semantic grammars. In actual working systems,

both understanding and text generation, ATN -like grammars can

be considered the state of the art.

48
L. Problems and Issues

1 . How People Use Language

Many of the issues in natural language understanding

center around the way people use language. Given speech acts

can serve many purposes, depending on the goals, intentions

and strategies of the speaker. Thus, methods for determining

the underlying motivation of a speech act is a major issue.

Another issue is understanding how humans process language -

both in forming output and in interpreting input.

It also appears that knowledge-based inference is essential

to natural language understanding, as language just provides

abreviated cues that must be fleshed out using models and expectations

resident in the receiver. Finally, we do not even have a good

handle on what it means to understand language and what is the

relation between language and perception.

2 . Linguistics

A major issue in NLP is how to disambiguate words to determine

their appropriate sense in the current context. A complementary

problem is dealing with novel language such as metaphors, idioms,

similes and analogies.

Syntactic ambiguity is a common source of trouble in natural

language processing. Where to attach modifying clauses is one

49
problem. However even handling adverbial modifiers has proved

difficult.

Another major issue is pragmatics - the study of language In

context. Arden (1980, p474) notes:

Many of the issues discussed under frame systems are pertinent

to pragmatic Issues. The prototypes stored In a frame

system can Include both the prototypes for the domain being

discussed and those related to the conversational situation.

In a travel -planning system, then, a user responds to the

question, "What time do you want to leave?" with the answer:

"I have to be at a meeting by 11." In planning an appropriate

flight, the system makes asumptlons about the relevance

of the answer to the question.

This aspect of language is one that Is just beginning to

be dealt with In current systems. Although most large

systems in the past had specialized ways of dealing with

a subset of pragmatic problems, there is as yet no theoretical

approach. As people look to interactive systems for teaching

and explanation, however, it seems likely that this will

be the major focus of research in the 1980's.

3 . Conversat ion

In the area of everyday conversation, the real world is

extensive, complex, largely unknown and unknowable. This is

quite different from the closed world of many of the research

NLP systems.

"A major problem for NLP systems is following the dialogue context

and being able to ascertain the references of noun phrases by

taking context into account." (Hendrix and Sacerdoti, 1981, p.

330)

50
Another major problem is understanding the motivation of the

participants in the discourse in order to penetrate their remarks.

As conversational natural -language communication between individuals

is dependent on what the participants know about each other's

knowledge, beliefs, plans, and goals, methods for developing

and incorporating this knowledge into a computer is a major

i ssue

.

4 . Processor Design

"While many specific problems are linguistic,... many important

problems are actually general AI problems of representation

and process organization." (Arden, 1980, p. 409)

A major issue in the design of a NLP system is choosing the

tradeoffs between capability, efficiency and simplicity. Also

at issue are the language constructs to be handled, generality,

processing time and costs. The choice of the overall architecture

of the system and the grammar to be used is a major design decision

for which there are as yet no general criteria.

Though all natural -language processing systems contain some

sort of parser, the practical design of applications of grammar

to NLP has proved difficult. The design of the parser in both

theory and implementation is a complex problem. Also at issue

is the top-down (ATN-like) approach to parsing versus bottomup and combined approaches. In addition, how best to utilize

knowledge sources (phonemic, lexical, syntactic, semantic, etc.)

51
In designing a parser and a system architecture remains a major

Issue

.

A problem with the ATN parser approach, with its heavy dependence

on syntax, Is how can it be adapted to handle ungrammatical Inputs.

Though considerable progress has been made, there Is as yet

no clear solution. INTELLECT (a commercial ATN-based system)

handles ungrammatical constructions by relaxing syntactic constraints.

IBM's Epistle System (Jensen and Heidorn, 1983) use a fitting

procedure to ungrammatical inputs to produce a reasonable approximate

parse. Semantic grammars and expectation-driven systems have

an advantage in overcoming ungrammatical inputs.

Another major Issue is: Is It appropriate to keep the semantic

analysis separate from the syntactic analysis, or should the two

work Interactively? (see Charniak, 1981)

Also, is it necessary in NL translating or understanding to

utilize an intermediate representation, or can the final interpretation be gotten at more directly? If an intermediate representation is to be used, which one is best? What is the appropriate

role of primitive concepts (such as found in case systems or

conceptual dependency) in natural language processing?

How can we make restricted natural language more pal itable to humans?

A major problem is the negative expectations created in the

mind of a naive user, when a system doesn't understand an input

52
sentence. Naive users have difficulty distinguishing between

the limitations in a system's conceptual coverage and the system's

linguistic coverage. A related problem is the system returning

a null answer. This may mislead the user as a answer may be

null for many reasons. Another problem is insuring a sufficiently

rapid response to user inputs.

One common problem with real systems is stonewalling behavior -

the system not responding to what the user is really after (the

user's goal) because the user hasn't suitably worded the input.

Some of the important problems and issues have to do with knowledge

representation

:

-Which knowledge representation is appropriate for a given problem?

-How to represent such things as space, time, events, human

behavior, emotions, physical mechanisms and many processes associated

with novel language?

-How can common sense and plausibility judgement (is this meaning

possible?) be represented?

-How should items in memory be indexed and accessed?

-How should context be represented?

-How should memory be updated?

-How to deal with inconsistencies?

-How can we make the representations more precise?

-How can we make the system learn from experience so as to build

up the necessary large knowledge base needed to deal with the

real world?

53
-How can we build useful Internal representations that correspond

to 3D models, from Information provided by natural language?

NLP usually takes the sentence as the basic unit to be analyzed.

Assigning purpose and meaning to larger units has proved difficult.

The NRL Conceptual Linguistics Workshop (1981) concluded that

"Concept extraction was the most difficult task examined at

the workshop. Success depends on the adequacy of the situationcontext representation and the development of more sophisticated

models of language use."

NLP has always pushed the limits of computer capability. Thus

a current problem is designing special computer architectures

and processors for NLP.

5 . Data Base Interfaces

Hendrix and Sacerdoti (1981, pp 318,350) point out two problems

particularly associated with data base interfaces:

(1)

. The need to understand context throws considerable

doubt on the idea of building natural -language interfaces

to systems with knowledge bases independent of the

language processing system itself.

(2)

. One of the practical problems currently limiting

the use of NLP systems for accessing data bases is

the lack of trained people and good support tools

for creating the knowledge structures needed for each

new data base.

54
6 . Text Understanding

Text understanding systems have encountered problems in achieving

practicality, both in terms of extending the knowledge of the

language and In providing a sufficiently broad base of world

knowledge. The NRL Conceptual Linguistics Workshop (1981)

concluded that "Current systems for extracting information

from military messages use the key word and key phrase methods

which are incapable of providing adequate semantic representation.

In the immediate future, more general methods for concept extraction

probably will work well only in well defined subfields that are

carefully selected and painstakingly modeled."

SRI and the National Library of Medicine have text understanding

systems in the research stage. SRI handcodes logic formulas

that describe the content of a paragraph. Queries are matched

against these paragraph descriptions.

55
M. Research Required

Current research in natural language processing systems includes

machine translation, information retrieval and interactive interfaces to computer systems. Important supporting research topics

are language and text analysis, user modeling, domain modeling,

task modeling, discourse modeling, reasoning and knowledge representation.

Much of the research required (as well as the research now

underway) is centered around addressing the problems and issues

discussed in the following areas:

1 . How People Use Language

The psychological mechanisms underlying human language production

is a fertile field for investigation. Efforts are needed to build

explicit computational models to help explain why human languages

are the way they are and the role they play in human perception.

2 . L i n q u i s i t i c s Further research is needed on methods for disambiguating language

and for the utilization of context in language understanding.

3 . Conversation

Additional work is needed on ways to represent the huge amount of

knowledge needed for Natural Language Understanding (NLU).

56
A great deal of research Is needed to give NLU systems the ability

to understand not only what is actually said, but the underlying

intention as well.

Research is now underway by many groups on explicitly modeling

goals, intentions and planning abilities of people. Investigation

of script and frame-based systems is currently the most active

NLP A I research area.

4 . Processor Design

Architectures, grammars, parsing techniques and internal representations needed for NLP systems remain important research

areas

.

One particularly fertile area is how to best utilize semantics

to guide the path of the syntactic parser. Charniak (1981,

p

1085) indicates that a relatively unexplored area requiring

research is the interaction between the processes of language

comprehension and the form of semantic representation used.

Further work is needed on bringing multiple knowledge sources

(KS's: syntactic, semantic, pragmatic and contextual) to bear

on understanding a natural language utterance, but still keeping

the KS's separate for easy updating and modification. Also

needed is further work in AI problem-solving to cope with the

problem of finding an appropriate structure in the huge space

of possible meanings of a natural language input.

57
Improved NLU techniques are needed to handle complex notions

such as disjunction, quantification, implication, causality

and possibility. Also needed are better methods for handling

"open worlds," where all things needed to understand the world

are not in the system's knowledge base.

Further research Is also necessary to aid with a common source

of trouble In NLP, that is, dealing with syntactic and semantic

ambiguities and how to handle metaphors and idioms.

Finally, the problems of efficiency, speed, portability, etc.,

discussed in the previous chapter, all are in need of better solutions.

5 . Data Base Interfaces

A current research topic is how can data base schemas best be

enriched to support a natural language interface, and what would

be the best logical structure for a particular data base.

Research is also needed on more efficient methods for compiling

a vocabulary for a particular application.

6 . Text Understanding

Seeking general methods of concept extraction remains as one

of the major research areas in text understanding.

/

58
N. Principal U.S. Participants in NLP

1 . Research and Development *

Non-Profit

SRI

MITRE

Universities

Yale U. - Dept of Computer Science

U. of CA, Berkeley - Computer Science Div., Dept of EECS.

Carnegie-Mel Ion U. - Dept of Computer Science.

U. of Illinois, Urbana - Coordinated Science Lab.

Brown U. - Dept of Computer Science

Stanford U. - Computer Science Dept.

U. of Rochester - Computer Science Dept.

U. of Mass, Amherst - Department of Computer and Information Science

SUNY, Stoneybrook, Dept of Computer Science

U. of CA, Irvine, Computer Science Dept.

U of PA - Dept of Computer and Infor. Science

GA Institute of Technology - School of Infor. and Computer Science

USC - Infor. Science Institute.

MIT - A I Lab.

NYU - Computer Science Dept, and Linguistic String Project

U. of Texas at Austin - Dept of Computer Science

Cal . Inst . of Tech

.

Brigham Young U. - Linguistics Dept.

Duke U. - Dept of Computer Science

N Carolina State - Dept, of Computer Science

Oregon State U - Dept of Computer Science

Industrial

BBN

TRW Defense Systems

IBM, Yorktown Heights, N.Y.

Burroughs

Sperry Univac

Systems Development Corp, Santa Monica

Hewlett Packard

Martin Marietta, Denver

Texas Instruments, Dallas

Xerox PARC

Bell Labs

Institute for Scientific Information, Phila., PA

GM Research labs, Warren, MI

Honeywe 1

1

*A review of current research in NLP is given in Kaplan (1982).

59
2 . Principle U.S. Government Agencies Funding NLP Research

ONR (Office of Naval Research)

NSF [National Science Foundation)

DARPA (Defense Advanced Projects Agency)

3 . Commercial NLP Systems

Artificial Intelligence Corp. Waltham, Mass.

Cognitive Systems Inc., New Haven, Conn.

Symantec, Sunnyvale, CA.

Texas Instruments, Dallas, TX

.

Weldner Communications, Inc., Provo, Utah

Savvy Marketing International, Sunnyvale, CA

ALPS, Provo, UT

4. Non-U. S.

U. of Manchester, England

Kyoto U., Japan

Siemens Corp. Germany

U of Strathclyde, Scotland

Centre National de la Recherche Sclent 1 flque . , Paris

U. dl Udine, Italy

U. of Cambridge, England

Philips Res. Labs, The Netherlands

60
0. Forecast

Commercial natural language interfaces (NLI's) to computer programs

and data base management systems are now becoming available.

The imminent advent of NLI's for micro-computers is the precursor

for eventually making it possible for virtually anyone to have

direct access to powerful computational systems.

As the cost of computing has continued to fall, but the cost

of programming hasn't, it has already become cheaper in some

applications to create NLI systems (that utilize subsets of

English) than to train people in formal programming languages.

Computational linguists and workers in related fields are devoting

considerable attention to the problems of NLP systems that understand

the goals and beliefs of the individual communicators. Though

progress has been made, and feasibility has been demonstrated,

more than a decade will be required before useful systems with

these capabilities will become available.

One of the problems, in implementing new installations of NLP

systems, is gathering information about the applicable vocabulary

and the logical structure of the associated data bases. Work

is now underway to develop tools to help automate this task.

Such tools should be available within 5 years.

For text understanding, experimental programs have been developed

that "skim" stylized text such as short disaster stories in

61
newspapers (DeJong, 1982). Despite the practical problems

of sufficient world knowledge and the extension of language

knowledge required, practical tools emerging from these efforts

should be available to provide assistance to humans doing text

understanding within this decade.

The NRL Computational Linguistic Workshop (1981) concluded that

text generation techniques are maturing rapidly and new application

possibilities will appear within the next five years.

The NRL workshop also Indicated that:

Machine aids for human translators appear to have a brighter

prospect for Immediate application than fully automatic

translation; however, the Canadian French -Eng 1 1 sh weather

bulletin project Is a fully automatic system In which only

20% of the translated sentences require minor rewording

before public release. An ambitious common market project

involving machine translation among six European languages

is scheduled to begin shortly. Sixty people will be Involved

in that undertaking which will be one of the largest projects

undertaken in computational linguistics.* The panel was

divided in its forecast on the five year perspective of

machine translation but the majority were very optimistic.

Nippon Telegram and Telephone Corp in Tokyo has a machine translation

AI project underway. An experimental system for translating

from Japanese to English and visa versa is now being demonstrated.

In addition, the recently initiated Japanese Fifth Generation

Computer effort has computer-based natural language understanding

as one of its major goals.

*EUR0TA - A machine translation project sponsored by the European

Common Market - 8 countries, over 15 universities, $24 M over

several years.

62
In summary, natural language interfaces using a limited subset

of English are now becoming available. Hundreds of specialized

systems are already in operation. Major efforts in text understanding and machine translation are underway, and useful (though

limited) systems will be available within the next five years.

Systems that are heavily knowledge-based and handle more complete

sets of English should be available within this decade. However,

systems that can handle unrestricted natural discourse and understand the motivation of the communicators remain a distant goal,

probably requiring more than a decade before useful systems

appear

.

As natural language interfaces coupled to intelligent computer

programs become widespread, major changes in our society are

likely to result. There is a trend now to replace relatively

unskilled white collar and factory work with trained computer

personnel operating computer-based systems. However, with the advent

of friendly interfaces (and eventually even speech understanding

systems and automatic text generation from speech) relatively

unskilled personnel will be able to control complex machines,

operations, and computer programs. As this occurs, even relatively

skilled factory and white collar work may be taken over by these

lesser skilled personnel with their computer aids - the experts

and computer personnel moving on to develop new programs and

applications.

63
The outcome of such a revolution cannot be fully predicted at

this time, other then to suggest that much of the power of the

computer age will become available to everyone, requiring a rethinking of our national goals and life styles.

64
P . Further Sources of Information

1 . Journals

o American Journal of Computational Linguistics - published

by the major society in NLP, the Association for Computational

Linguistics (ACL)

.

o SIGART Newsletter - ACM (Association for Computing Machinery),

o Artificial Intelligence

o Cognitive Science - Cognitive Science Society

o AI Magazine - American Association for AI (AAAI)

o Pattern Analysis and Machine Intelligence - IEEE

o International Journal of Man Machine Interactions

2 . Conferences

o Computational Linguistics (COLING) - held biannually.

Next one is in July 1984 at Stanford University.

o International Joint Conference on AI (IJCAI) - biannual.

Current one in Germany, August 1983.

o ACL Annual Conference.

o AAAI annual conferences.

o ACM conferences.

o IEEE Systems, Man & Cybernetics Annual Conferences.

o Conference on Applied Natural Language Processing.

Sponsored jointly by ACL & NRL - Feb. 1983 in Santa

Monica, CA.

3 . Recent Books

o Winograd, T., Language as a Cognitive Process, Vol I,

Syntax , Reading! Mass : Addison Lesley, 1983.

o Lehnert, W.G. and Ringle, M.H. (eds.). Strategies for Natural

Language Processing , Hillsdale, N.J. Lawrence Erlbaum, 1982.

o Sager, N., Natural Language Information Processing , Reading

Mass: Addison- Wesley, 1981

65
o Tennant, H., Natural Lanquaqe Processinq, New York: Petrocelll.

1981.

o Brady, M., Computational Approaches to Disco urse, Cambridge,

Mass: MIT Press, 1982.

o Joshl, A.K., Weber, B.L. and Sag, I. A. (eds), Elements

of Discourse Understanding , Cambridge: Cambridge University

Press, 1981.

o L. Bole (ed.), Natural Lanquaqe Communication with Computers,

Berlin: Spr i nger - Ver 1 ag , i98i.

o L. Bole (ed.), Data Base Question Answering Systems , Berlin:

Spr i nger-Ver 1 ag , 1982 .

o Schank, R.C. and Riesbeck, C.K., Inside Computer Understanding.

Hillsdale, N.J.: Lawrence Erlbaum, lyai.

4 . Overviews and Surveys

o Barr, A and Feigenbaum, E.A., Chapter IV, "Understanding

Natural Language," The Handbook of Artificial Intelligence,

Vo 1 I , Los Altos, CAl W. Kaufmann 1981, pp 223-322 .

o S.J. Kaplan, "Special Section - Natural Language," SIGART

Newsletter , No. 79, Jan 1982, pp 27-109.

o Charnlak, E., "Six Topics in Search of A Parser: An Overview

of A I Language Research,: I JCAI-81 , pp 1079-1087.

o Waltz, D.L., "The State of the Art in Natural Language

Understanding," In Strategies for Natural Lanquaqe Processing , W.G. Lehnert and M.H. Ringle (eds), Hillsdale, N.J.: Lawrence

Erlbaum, 1982, pp. 3-32.

o Slocum, J., "A Practical Comparison of Parsing Strategies

for Machine Translation and other Natural Language Processing

Purposes," Tech. Report NL-41, Dept of C.S., U. of Texas,

Aug 1981.

o Hendrix, G. G. and Sacerdoti, E. D., "Natural -Language

Processing: The Field in Perspective," Byte , Sept. 1981,

pp 304-352.

66
REFERENCES

o Arden, B.W. (ed), What Can Be Automated ? { COSERS ) , Cambridge,

Mass: MIT Press, Cambridge, 1980.

o Barr, A and Feigenbaum, E.A., Chapter 4, "Understanding

Natural Language," The Handbook of Artificial Intelligence , Los Altos, CA: W. Kaufman, 1981, pp 223-321.

o Barrow, H.G., "Artificial Intelligence: State of the Art,"

Technical Note 198, Menlo Park, CA: SRI International, Oct.

1979.

o Brown, J.S. and Burton, R.R., "Multiple Representations

of Knowledge for Tutorial Reasoning." In Representation of

Learning , D.G. Bobrow and A. Collins ( Eds . ) , New York : Academic

Press, 1975.

o Burton, R.R., "Semantic Grammar: An Engineering Technique

for Constructing Natural Language Understanding Systems," BBN

Report 3453, BBN, Cambridge, Dec. 1976.

’

o Charniak, E. "Six Topics in Search of a Parser: An Overview

of AI Language Research," IJCAI-81, pp 1079-1087

o Charniak, E. and Wilks, Y., Computational Semantics, Amsterdam

North Holland, 1976.

o Chomsky, N., Syntactic Structures, The Haque: Mouton,

1957.

o DeJong, G., "An Overview of the FRUMP System," In

Strategies for Natural Language Processing , W.G. Lehnert and M. H.

Ringle (eds.), Hillsdale, N.J.T Lawrence Erlbaum, 1982, pp 149-176.

o Fillmore, C, "Some Problems for Case Grammar" In R.J. O'Brien

(Ed.), Report of the Twenty-Second Annual Round Table Meeting

on Linguistics and Languages Studies ," Wash, D.C.: Georgetown

U. Press, 1971, pp. 35-56.

o Finin, T. W., "The Semantic Interpretation of Compound

Nominals," Ph.D. Thesis, U. of IL, Urbana, 1980.

o Gawron, J.M. et al., "Processing English with a Generalized

Phrase Structure Grammar," Proc. of the 20th Meeting of ACL , U. of Toronto, Canada, 16-18 June 1982, pp. 74-81.

o Gazdar, G., "Unbounded Dependencies and Coordinate Structure,"

Linguistic Inquiry , 12, 1981, pp. 155-184.

o Gevarter, W.B., An Overview of Computer Vision , NBSIR 82-

2582, National Bureau of Standards, Wash., D.C., September 1982.

67
o Gevarter, W.B., An Overview of Artifical Intelligence and

Robotics, Vol. 1 , NBS (In press ) , 1983

.

o Graham, N., Artificial Intelligence, Blue Ridqe Summit,

PA: TAB Books, 1ST9":

o Hendrix, G. G., Sacerdotl, E. D. Sagalowlcz, D. and Slocum, J.,

"Developing a Natural Language Interface to Complex Data," ACM

Transactions on Database Systems , Vol. 3, No. 2, June 1978.

o Hendrix, G.G. and Sacerdotl, E.D., "Natural -Language Processing:

The Field In Perspective," Byte , Sept 1981, pp. 304-352.

o Jensen, K. and Heldorn, G.E., "The Fitted Parse: 100%

Parsing Capability In a Syntactic Grammar of English," Conf

.

on Applied NLP , Santa Monica, CA, Feb. 1983, pp. 93-98.

o Kaplan, S.J., (Ed.), "Special Sect1on--Natural Language,"

SIGART NEWSLETTER #79, Jan 1982, pp. 27-109.

o McDonald, D.B., "Understanding Noun Compounds," Ph.D Thesis,

Carnegie Mellon U., Pittsburg, 1982.

o McDonald, D.B., "Natural Language Production as a Process

of Decision-Making Under Constraints," Ph.D Thesis, M.I.T.,

Cambridge, 1980.

o Nishida, T. and Doshita, S., "An Application of Montague

Grammar to Eng 1 i sh -Japanese Machine Translation," Proc. of Conf.

on Applied NLP , Santa Monica, Feb. 1983.

o Reiger, C. and Small, S., "Word Expert Parsing," Proc

.

of the Sixth International Joint Conference on Artificial Tnte 1 1 iqence

,

imrw-—723 - 728 . —

o Robinson, A.E., et a 1 . , "Interpreting Natural Language

Utterances in Dialog about Tasks," AI Center TN 210, SRI Inter.,

Menlo Park, CA, 1980.

o Schank, R.C. and Abelson, R.P., Scripts, Plans, Goals and

Understanding , Hillsdale, N.J.: Lawrence Erlbaum, 1977.

o Schank, R.C. and Riesbeck, C.K., Inside Computer Understanding , Hillsdale, N.J.: Lawrence Erlbaum, 19ET!

o Schank, R.C. and Yale AI Project, "SAM - A Story Underst ander ,

Research Rept 43, Dept of Comp Sci, Yale U., 1975.

o Slocum, J., "A Practical Comparison of Parsing Strategies

for Machine Translation and Other Natural Language Purposes,"

Ph.D Thesis, U. of Texas, Austin, 1981.

68
o Tennant, H, Natural Lanquaqe Processinq, New York: Petrocelli,

1981 .

o Waltz, D.L., "Natural Language Access to a Large Data Base,"

In Advance Papers of the International Joint Conference on Artificial

Intel 1 iqence , Cambridge, Mass, MIT, 1975.

o Waltz, D.L. "The State of the Art in Natural Language Understanding," In Strategies for Natural Lanquaqe Processing ., W.G.

Lehnert and M.H. Ringle (eds), Hillsdale, N.J.: Lawrence Erlbaum,

1982, pp. 3-32.

o Webber, B.L. and Finin, T.W., "Tutorial on Natural Language

Interfaces, Part 1 - Basic Theory and Practice," AAAI-82 Conference,

Pittsburg, PA, Aug 17, 1982.

o Wilks, Y., "A Preferential Pattern-Seeking Semantics for

Natural Lanquaqe Processinq," Artifical Intelligence, Vol. 6,

1975, pp. 53-74.

o Winograd, T. Understanding Natural Lanquaqe , New York:

Academic Press, 1972

.

o Winograd, T., Lanquaqe as a Cognitive Process. Vol I: Syntax,

Reading , Mass : Addison-Wesley, 1983.

o Woods, W.A., "Progress in Natural Language Understanding

- An Application to Lunar Geology," In Proc. of the National

Computer Conferences , Montvale, N.J.: AFIPS Press, 1973.

o Woods, W. A., "Cascaded ATN Grammars," Amer. J. of Computational

Linguistics , Vol. 6, No. 1, 1980, pp. 1-12.

o "Applied Computational Linguistics in Perspective," NRL

Workshop at Stanford University, 26-27 June 1981. (Proceedings

in Amer. J. of Comp utational Linguistics , Vol. 8, No. 2,

April-dune 1982, pp 55-83).

69
Glossary

Anaphora ; The repetition of a word or phrase at the beginning

successive statements, questions, etc.

C . A . I

.

: Computer-Aided Instruction

Case : A semantically relevant syntactic relationship.

Case Frame ; An ordered set of cases for each v§rb form.

Case Grammar: A form of Transformational Grammar In which the deep

structure Is based on cases.

Computational Linguistics : The study of processing language with

a computer

Conceptual Dependency (CD): An approach, related to case frames,

1 n wh 1 c h sentences are translated Into basic concepts expressed

In a small set of semantic primitives.

DB : Data Base

DBMS: Data Base Management System.

Deep Structure : The underlying formal canonical syntactic

structure , associated with a sentence, that Indicates the

sense of the verbs and Includes subjects and objects that

may be Implied but are missing from the original sentence.

Discourse : Conversation, or exchange of Ideas.

Domain : Subject area of the communication.

Frame : A data structure for grouping Information on a whole situation,

complex object, or series of events.

Gramma r : A scheme for specifying the sentences allowed in

a language, Indicating the syntactic rules for combining

words Into well-formed phrases and clauses.

Heuristic : Rule of thumb or empirical knowledge used to help

guide a solution.

KB : Knowledge Base

Lex 1 con : A vocabulary or list of words relating to a particular

subject or activity.

Li ngu 1 sties : The scientific study of language.

70
Morphology : The arrangement and interrelationship of morphemes

in words.

Morpheme : The smallest meaningful unit of a language, whether

a word, base or affix.

Network Representation : A data structure consisting of nodes

and labeled connecting arcs.

NL : Natural Language

NLI : Natural Language Interface

NLP : Natural Language Processing.

NLU : Natural Language Understanding

Parse Tree : A tree-like data structure of a sentence, resulting

from syntactic analysis, that shows the grammatical

relationships of the words in the sentence.

Parsing ; Processing an input sentence to produce a more useful

representation

.

Phonemes : The fundamental speech sounds of a language.

Phrase Structure Grammar ; Also referred to as Context Free Grammar.

Type 2 of a series of grammars defined by Chomsky. A Relatively

natural grammar, it has been one of the most useful in naturallanguage processing.

Pragmatics : The study of the use of language context.

Script : A frame-like data structure for representing stereotyped

seguences of events to aid in understanding simple

stories

.

Semantic Grammar : A grammar for a limited domain that, instead

of using conventional syntactic constituents such as noun

phrases, uses meaningful components appropriate to the domain.

Semantics : The study of meaning.

Sense : Meaning.

Surface Structure : A parse tree obtained by appling syntactic

analysis to a sentence.

Syntax : The study of arranging words in phrases and sentences.

71
Temp Tate : A prototype model or structure that can be used for

sentence 1 nterpretat 1 on

.

Tense : A form of a verb that relates It to time.

Transformational Grammar ; A phrase structure grammar that

Incorporates transformational rules to obtain the deep structure

from the surface structure.

72
NBS-1 14A inf v. t -t o U.». DEPT. Of* COMM. 2. Performing Organ. Report NoJ 4. Publication bate

BIBLIOGRAPHIC DATA

SHEET (See Instructions)

1. PUBLICATION OR

REPORT NO.

4. TITLE AND SUBTITLE

AN OVERVIEW OF COMPUTER-BASED NATURAL LANGUAGE PROCESSING

5. AUTHOR(S)

William B. Gevarter

6. PERFORMING ORGANIZATION (If joint or other than NBS, see Instructions)

national bureau of standards

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

,

i

, >. •• I 1;

1 -i t

7. Contract/Grant No.

I. Type of Report & Period Covered

9. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street, City. State. ZIP)

10. SUPPLEMENTARY NOTES

| | Document describes a computer program; SF-185, FIPS Software Summary, is attached.

11. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant

bibliography or literature survey, mention it here)

Computer-based Natural Language processing and understanding is the key to enabling

humans and their creations to interact with machines in natural language (in contrast

to computer language) . The doors that such an achievement can open has made this a major research area in Artificial Intelligence and Computational Linguistics. Commercial natural languages interfaces to computers have recently entered the market and

the future looks bright for other applications as well.

This report reviews the basic approaches to such systems, the techniques utilized,

applications, the state-of-the-art of the technology, issues and research requirements,

the major participants, and finally, future trends and expectations.

It is anticipated that this report will prove useful to engineering and research

managers, potential users, and others who will be affected by this emerging field.

12. KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolon s) artificial intelligence; computational linguistics; computer based;

interfaces; natural language; translation

13. AVAILABILITY

[~X] Uni imited

| | For Official Distribution. Do Not Release to NTIS

I I Order From Superintendent of Documents, U.S. Government Printing Office, Washington, D.C.

20402.

Order From National Technical Information Service (NTIS), Springfield, VA. 22161

14. NO. OF

PRINTED PAGES

15. Price

U SCOMM-DC 6043-P80
I

I

I

:

i