Computational linguistics distinguishes itself by trying to model the human faculty of language as a computational process: to implement on a computer machine a program that exhibits intelligent behavior by possessing an apparent ability to "understand" language as used by the human speaker. Computational linguistics' scope of inquiry is immediately broadened by the inescapable conclusion that by whatever definition of the human linguistic faculty used, recourse must be made to other deeper cognitive processes. Topics that come immediately to mind such as memory organization, learning, inferencing and remembering must all be accounted for by the computer-based model. With such an array of issues to handle, it is little surprise that many more questions than answers have arisen in the course of the development of NL research in the last two decades.
However, the higher linguistic levels such as semantics, and the more mentally oriented processes such as memory organization, have proven to be more problematic and have traditionally been excluded from the realm of linguistics. One of the maor reasons for controversies among the various schools studying language is the lack of a common definition of the human language faculty. In the often bewildering array of approaches to the study of language, each school has seen fit to draw its own boundaries around language. To the phonoligists, language is essentially a series of distinct sounds (phonemes) produced by the human vocal chords; to the Chomskyan, language is an abstract formal mechanism analyzing grammatacality; to the sociologist or anthropologist, language is a communicative process in a social setting; to the philosopher, it is the examination of theories of meaning.
The goal of computational linguistics is the mapping of the linear surface
structure of a sentence into a representation of its underlying meaning.
But how this process is to be modeled is still a very open question,
the main points fo disgreement centering on the precise relationship between
the syntactic and semantic aspects of the language comprehension process.
except for a few basic notions, such as the analogy between mental processes
computational processes, there is a wide divergence of opinion as to what
ar the proper mthods needed to analyze sentences, and on what level their
meaning should be represented.
One important theme that underlies much of the difference in computational
linguistics is the relationship between language and thought.
Some researchers, such as Schank, question if it is even useful to make
this distinction.
The journey from utterance to understanding is a long an tortuous one,
traversing several physical and mental processes that interact in complex
and largely unknown ways.
No school has yet satisfactorily explained this process in full.
2 Approaches to Natural Language Processing
2.1 Subparadigms of Computational Linguistics
It is important to realize that neither side claims that syntax and semantics is unnecessary; rather, the contrtoversy centers on the precise bandwidth of the communication channel between these two knowledge sources. The nature of the controversy could be better seen as revolving around the semi-autonomy of syntax rather than the autonomy of syntax. A number of other differences arise from this elementary distinction: the nature fo the control mechanism used to implement the parse, and the type of structures used to encode logical relations. Syntax-oriented researchers have spent most of their energy on extending the Augmented Transition Network (ATN) model to handle complex syntactic constructs, while adherents of the integrated approach concentrate on more cognitive issues such as memory organization.
Schematically, four different possible types of NL systems can be identified (Sowa, 1984, Schank, 1984):
The nearly decomposable model also contains independent modules devoted to syntax and semantics, but, here the syntax modul frequently invokes to aid it in disambiguation phrases. Syntax can be seen as issuing subroutine calls to semantics, but control still remains with syntax. When the syntactic phase has finished, processing passes on to semantics. An example of such as system is the semantic grammars often used by ATN-based parsers (Hendrix, 1978, Waltz 1978).
The coroutine mechanism can be viewed as a variation of the second type. Again, autonomous syntactic and semantic units exists, but they exhibit a much closer degree of cooperation. Control does not exclusively lie with syntax but is shared jointly with semantics. When syntax encounters a problem it will pass contol to semantics, which, in turn, returns contol to syntax when it (semantics) can proceed no further. Winorad's SHRDLU system (Winograd, 1972) can be seen as an example of this class of system.
In all three versions described above the main difference has centered on the best way to build syntaqctic structures. What is at issue here is not the validity of an autonomous level of syntactic representation; rather, the manner in which extra-syntactic knowledge is utilized along with syntactic information in generating syntacitc structures. Although syntactic and semantic rules operate with varying degrees of cooperation, the problem they are working on is syntactic representations.
The integrated approach deos not subscribe to this assumption and advocates a close coupling of syntactic and semantic information in all stages of the comprehension process. Syntactic structures are not regarded as necessary, and the parsing process maps a sentence directly into its semantic constituents. Integrated parsing is examine in depth in chapter 3.
However, computational linguistics's main concern is not in describing linguistic capabilities as an abstract formal mecahnism, but in developing a framework to represent meaning, the real-world objects and concepts that a sentence connotes. The derivation of phrase structures is not the primary objective as in transformational linguistics, but, if used, is merely a means to the end of decoding the meaning underlying a sentence. This broadening of the scope of inquiry to semantics and the organization of knowledge presents computational linguistics with a task that necessitates cooperation with other fields studying the human mind such as philosophy and psychology.
Although transformational grammar influenced much of the early work in NL understanding, its direct utility proved limited since it is primarily concerned with transformations from syntactic deep level structures to surface structures, and NL researches' goal is the reverse, mapping surface structures into syntactic and semantic structures. It is this distinction between performance and competence that puts transformational grammar at odds with computational linguistics. In disregarding questions of process, transformational grammar effectively isolates itself from real-world issues of human language understanding. Computational linguistics' main concern is performance, and implementationl models are an integral pars of its methodology.
People who apply for marriage licenses wearing shorts of pedal pushers will be denied licenses
results in forty possible parse trees (Sowa, 1984).
The principle type of ambiguity that causes most grief is word class ambiguity, where a word can belong to several different grammatical categories. For example, the word duck can be either a verb as in I would duck if I saw a ball coming, or a noun when describing the type of bird that swims in a pond. Without recourse to some discourse context, two parse trees are equally valid for the sentence I saw her duck.
Structural ambiguity arises when several alternative syntacic structures can be derived from a string of words whose word classes are unambiguous. In the phrase old men and women it is not clear whether both the men and women are odl, or if only the men are old. Again, context can help out but this problem is not as easily solved as word class ambiguity.
Lexical ambiguity, or word sense ambiguity, is when a word of a given class can have several different meanings. The phrase he cannot bear kids has two lexically ambiguous words, bear meaning tolerate as in he cannot bear loud noises, or meaning to give birth to as in a woman can bear children. The other ambiguousword is kid, signifying a human child or baby goat. This type of ambuguity is outside the scope of syntax analyzers, but is often amenable to semantic resolution based on discourse context. Of course, real problem arise when these ambuguities occur simultaneously in a senctence as in she was sick and he took her flowers. Here, took is lexcially ambiguous, meaning either to give or to take away, and her is word class ambiguous, its part-of-speech being either a personal pronoun or a possessive pronoun.
Modifier (prepositional phrase) attachment is another issue that cannot be decided solely upon syntactic grounds. In a sentence there will often be many noun phrases a given phrase can refer to, and usually only one will be semantically plausible. For instance, in the phrase I went to the park with a girl, the modifier with a girl can either be attached to the park or I, although the latter is the usual interpretation.
Ambiguity can be also classified along another dimension scope (Ritchie, 1984). ALl different classes of ambiguity enumerated above pertain to global ambiguity. Local ambiguity is when words are ambiguous in the course of parsing a sentence, but are not ambiguous once the whole sentence has been processed. For instance, if the parse encounters the words plastic covers they are locally ambiguous in two ways: plastic can be a noun and covers a verb as in the plastic covers the table, or plastic can be an adjective and covers aa noun as in the plastic covers protect the table. Until the parse has reached the fourth word in the sentence, it has no way of correctly assigning a category for either word.
The current phase of NL research was ushered in by two events: Woods' concise formulation of the Augmented Transition Network (ATN) model (Woods, 1970, 1973) which provided researchers with a practical and versatile formalism within which to pursue syntactic analysis, and Winograd's SHRDLU sustem (Winograd, 1972) which demonstrated that combining syntactic parsing with procedural semantics could produce behavior approximating human unerstanding. However, SHRDLU's methods proved to be too domain specific, too tied to the block world, to be generalizable. Winograd's experiment demonstrated that a more complete understanding of the role that world knowledge plays in the language comprehension process was necessary. On the other hand, Woods' project turned out to be a more fruitful enterprise although it was also confronted by the challenge of semantic and world knowledge. A variety of hybrid systems have since been developted along ATN lines, and, in fact, ost commercial NL front-ends are based on this model.
Because natural language is inherently ambiguous, ATNs are non-deterministic machines since there can be several arcs leaving any given state, and the decision as to which one to follow is arbitrary. An ATN describes what the acceptable patterns are but not how these patterns are to be recognized. An ATN is a top-down parser, pursuing a breadth-first searcg through the network. When an incorrect path is chosen by the interpreter, i.e. no more legal transitions can be undertaken, the system will back up to the most recent node that still has an untried arc. From this choicepoint an arc will be selected and pursued until the final halt state is reached, signifying a succesful parse.
In the aforementioned ambiguous example plastic covers protect the table, when confronted with the word plastic, an ATN parser has to hypothesize either a noun or adjective, and if it chooses the wrong part-of-speech for plastic it will have to backup to this word and try another word class. In the course of even a short normal sentence, an ATN can be forced to backup a large number of times even though the sentence is not globally ambiguous. In the case of global ambiguity, either the system outputs the first alternative it parses, or it generates all possible parses and hands over the dilemma to the semantic component.
The key drawback to this approach is the ambuguity of so many words and the non-deterministic strategy used to overcome this problem. Herein lies the Achilles heel of the ATN approach: the combinatorial explosion of candidate paths. In principle, this can be solve by backtracking or parallel pursuit of all legitimate path. But either alternative results in an unacceptable number of paths unless elaborate scheduling strategies are devised for ordering choicepoints. Nevertheless, this still does not alter the fact that the basic method remains guess and if wrong, back up.
The major inefficiency with backtracking lies in the resotration of prior states, i.e. the saving of structures and deleting of already built structures. A partial solution to this problem consists of maintaining a chart, which is a record of existing constituents that do not have to be recreated when backtracking (Kay, 1973, Thompson, 1984).
It is important to point out that the type of ambiguity that has been discussed above is local ambiguity. An ATN may have to backtrack a large number of times due to locally ambiguous words, even though the sentence has only one legitimate parse. Global ambiguity presents another type of problem that in a strict sense falls outside the framework of the ATN model. This type of ambiguity results in there being several valid paths through the network for a given sentence, and the decision of which one to retain cannot be decided upon strictly syntactic grounds. A well known example of a globally ambiguous sentence is time flies like an arrow which has at least three parse trees.
The simplest solution is to generate all these representations, and then pass on the problem to the semantic mopdule to pick the mist desirable one. But this presents serious computational problems as well as not accurately reflecting human parsing techniques. The more common used strategy is to embed semantic checks inside the syntactic module in order to prune undesirable paths early in the parsing process. This method, often called a semantic grammar, has arc tests not only for parts of speech, i.e. syntactic categories, but also test for elements of the semantic domain. For instance, if the database pertained to auto repair tools, tests would be for wrench and screwdriver, and not only for noun and verb. Moreover, the ATN model, as well as other parsers within the syntactic paradigm, do not address the process of mapping the parse trees into semantic structures.
The parsing process can be divided into two phases:
Constituents:
Integrate parsing is based upon the premise that semantic and syntactic
knowledge have to be used concurrently in language analysis, and that a
separate and distinct syntactic stage is not necessary (Riesbeck, 1975).
The parse should use all information at its disposal, both linguistic
and non-linguistic, as early as possible in the parsing process and not
limit itself to one arbitrarily defined class of knowledge such as syntax.
Psychological evidence indicates that people do not first interpret a
sentence syntactically and then semantically, but rather, they use all
available information to extract the final meaning.
Since people have little trouble understanding incomplete or incorrectly
formed sentences, a parse that relies solely on syntactically
well-formed sentences leaves unaccounted a wide range of human
language performance.
XX
While the user does not exit do
Begin
Read a sentence
Replace all the synonyms in sentence
While a word still exists in the input sentence do
Begin
Get a word from the sentence
Get the word's requests from the Word Dictionary
Call procedure activate-requests with these requests
For all requests on the Rlist do
If a request is fired then
For all action in the Then part of the request
Begin
If the action will add a concept to the Clist then
Begin
Get the default requests associated with the concept
Call procedure activate-requests with these requests
Add the concept to the Clist
End_if
Else
Execute the action
End_for
End
End