Send us a comment. \"../Text/ch01ai.txt
As subsequent chapters in this book make plain, linguistic objects are structured objects. But they do not make their structures manifest. A grasp of the meaning of a sentence depends crucially on an ability, which is likely to be unconscious for a native speaker of the language in question, to recover its structure. A computational device that infers structure from grammatical strings of words is known as a parser, and much of the history of NLP over the last 20 years has been occupied with the design of parsers.
A modern parser can be thought of as a device that takes a grammar and a string of words, and gives either a grammatical structure imposed on that string of words, if the string of words is grammatical with respect to the grammar, or nothing, if it is not. Conceptually, the parser and the grammar are quite distinct kinds of things: a grammar is simply an abstract definition of a set of well-formed structured objects, whereas a parser is an algorithm - that is, a precise set of instructions - for arriving at such objects.
Whereas in early parsers the grammars employed were inextricably interwoven with the computer programs implementing the parsing algorithm, the trend towards declarative, as opposed to procedural, formalisms has led many modern computational linguists to separate clearly these two components. In spite of the fact that the grammar and the parsing algorithm are best seen as semi-independent components, the manner in which grammars are represented still plays a significant role in an overall parsing system, however.
Recursive transition networks (RTNs) are one way of specifying grammars.
An RTN consists of a collection of networks, each of which is labelled with the name of some syntactic category, or 'part of speech' in traditional parlance. The networks themselves consist of a collection of 'states'
connected by directional 'arcs'
labelled with the names of syntactic categories. Each network has, in addition, an indication of its initial and final states (see Chapter 3 for a detailed discussion). The RTN can be interpreted as a collection of maps that permit us to find our way through the grammatical expressions of the language.
To determine whether a given string of words is grammatical according to an RTN, it is necessary to find a route through the relevant maps, starting at initial states and ending up at final states. At each stage, progress can only be made by following the arcs in the network, whose labels tell which categories the successive words in the string must belong to. Only if all these conditions can be met has a successful path been found.
The RTN formalism used to appeal to NLP researchers precisely because of the naturally procedural interpretation suggested by it. In the 1980s, computational linguists shifted from procedural grammar representations to declarative ones (see Chapter 4 for examples). In part, this reflected analogous moves within linguistics itself, but it is also a consequence of the trends within AI and computer science discussed in the Section 1.1.
RTNs themselves have been overshadowed in NLP by an elaborated version of the formalism known as the augmented transition network (ATN). An ATN is simply an RTN that has been equipped with a memory and the ability to augment arcs with actions and conditions that make reference to that memory (see Chapter 3 for a detailed discussion of RTNs and ATNs). ATN-based parsers were probably the most common kind of parser employed by computational linguists in the 1970s, but they have begun to fall out of favour in recent years. This is largely because the augmentations destroy the declarative nature of the formalism and because a parser using an ATN is limited in the search strategies it can employ (see Chapter 5 for a comprehensive account of the relation between parsing and search).
A much larger range of search strategies become practical once a data structure known as a chart is adopted for parsing, and chart parsers have now become one of the basic tools of modern NLP. A chart is basically a data structure in which the parser records its successful attempts to parse subconstituents of the string of words.
Once the parser has recorded the presence of a constituent in one part of the string, it never needs to look for the same kind of constituent there again. This represents a significant improvement on the backtracking algorithms used in most ATN systems. The ability of the chart to record, in addition, the current goals of the parser leads to the possibility of implementing very sophisticated algorithms (see Chapter 6 for a detailed discussion of chart-based parsers).
Prolog is an inherently declarative language and so it is not surprising that one of the first of the new breed of declarative grammar formalisms emerged from that language. Definite Clause Grammars (DCG's) were developed from ideas of Colmerauer and have been quite widely used within the Prolog community. A DCG is essentially a phrase structure grammar (see Chapter 4) annotated with Prolog variables which maps straightforwardly into ordinary Prolog code. This total compatibility with Prolog is the major attraction of DCG's. Even though they look like grammars, and are in fact grammars, they can be used as parsers directly, given the way that Prolog works. REMOVED IN LIGHT OF REVIEWER COMMENT: However, using them in this way can prove inefficient since Prolog does not, by itself, employ any analogue of the well-formed substring table or chart discussed in the preceding section. The DCG formalism is provably powerful enough to describe languages (both natural and artificial) of arbitrary complexity. It is not, however, especially well-adapted for providing elegant accounts of some of the complexities that show up in natural languages (e.g., the unbounded dependency type of construction discussed in Chapter 4), although this has been ameliorated in some subsequent extensions of the formalism.
Ambiguity is arguably the single most important problem in NLP (see Chapter 5). Natural languages are riddled with ambiguities at every level of description, from the phonetic to the sociological, and in this respect they differ radically from formal languages, such as the propositional calculus or Prolog. Yet, as users of natural languages, we are blithely unaware of this pervasive ambiguity - it only comes to our attention in the guise of such linguistically marginal phenomena as puns, misunderstandings and contested libel suits.
Consider the possible readings
of the sentence:
Flying planes made her duck.
One reading is distinctly improbable: it requires us to imagine a female person intermittently lowering her head to avoid a projectile whenever she is engaged in the activity of flying an airplane. Two other readings are semantically quite bizarre: they involve aquatic birds being constructed in improbable ways. So, only one reading remains; namely, that in which she ducks to avoid airplanes that are flying overhead. We will examine later some of the semantic mechanisms used by computational linguists to tackle the problem of ambiguity. This example is a globally ambiguous sentence; that is, the entire string of words has more than one structure associated with it. Much of the ambiguity problem in NLP arises, however, from local ambiguities; that is, ambiguities that exist only in some subpart of the whole. Consider the following example:
The company that bought Scicon sold V.I.M.
This sentence is not globally ambiguous and it says nothing at all about whether or not Scicon sold V.I.M. But if you restrict your attention simply to the last three words, then you might well hypothesize the existence of a sentential subconstituent made up of 'Scicon sold V.I.M'. This is a local ambiguity, and such local ambiguities can sidetrack natural language parsers into many time-wasting investigations of possibilities that do not work out in the end. Marcus initiated a line of research into so-called deterministic parsers, which are parsers that are not fooled into pointless activity by local ambiguities of this kind (see Chapter 5 for some further discussion). The human parser seems to be adept at overcoming most, but not all, cases of local ambiguity. Work on deterministic parsers seeks to explain why garden path sentences such as (1) cause such perceptual problems, whereas sentences like (2) do not:
(1) The metal blocks the tube supports disintegrated. (2) The metal block the tube supports disintegrated.
The issue is further discussed in Chapter 5.
Send us a comment.