Computational linguistics : a brief introduction

Links & Letters 1, 1994 9-23 Computational linguistics: a brief introduction Anna Espunya i Prat Dpt. de Filologia Anglesa i Gerrnanística Universitat Autbnoma de Barcelona ABSTRACT Cornputationai Linguistics is an interdisciplinary field of study that encornpasses knowledge rnainly from three areas: Linguistics, Computer Science and Logic. This article is an introduction to the anai~sis of language frorn a Computational Linguistics approach, to the first questions linguists face when &ey need to make natural language fit into structures that computers can manipulate. Easy examples illustrate current existing approaches to the morphology, syntax and meaning of language, presenting sorne of the dificulties and challenges faced in this field. A list of basic introductory readings is provided in the last section. 1. Introduction: computers and human language For many of us it would be difficult to think of a world without computers. They are part of our existence at al1 scales: powerful computers in charge of the security and finances of countries, controlling airports, dams, hospitals and city traffic; domestic computers that we use as word processors, home economists, or entertainers. And recently, even as teachers. As they become more popular, companies make them more and more friendly, easier to use. However, communication between us and them is not yet based on our language. Even if it is as simple as clicking the mouse on one command of the menu, much in our interaction with computers needs to be adapted to their possibilities. Making computer systems that understand and speak any human language (also called natural language) is the main goal of Computational Linguistics, an interdisciplinary field of study that encompasses knowledge mainly from three areas: Linguistics, Computer Science and Logic. Computational Linguistics appeared in the late 1950s with the first work in Machine Translation, name given to the translation from one natural language into another performed by 10 Links & Letters 1, 1994 Anna Espunya i Prat the computer without the help of a human translator. Since those pioneering days there has been a steady increase in the quantity, variety and quality of the applications. Apart from machine translation, two of the most important lines of research and development have been man-machine interfaces and information retrieval systems: Man-machine interfaces are programs that allow communication between the computer and its human user. For instance, if you are using a database, you may want to ask questions in English instead of using the command language provided by the database. Information retrieval systems try to respond to the need of finding only the relevant information in large corpora of texts. Given that much of the information people use is still in a natural language form (e.g., books, journals, reports, etc.), every time a specific piece of information is needed, someone has to actually read al1 potential sources. Instead, we may want to ask a program to do the job for us. The system will read, select and retrieve from a natural language text the information we need. This article is not intended as an introduction to concrete Computational Linguistics applications. Neither is it meant to be a critical review of the most recent developments in this field. And finally, it is not intended to contribute to the debate on the possibilities and limitations of computers as real natural language speakers or the more general debate on the philosophy of Artificial Intelligence. Those are topics which occupy the pages of specialized journals, books and presentations in conferences. This article is an introduction to the analysis of language from a Computational Linguistics approach, to the first questions linguists face when they need to formalize a language, to make it fit into structures that computers can manipulate. It is addressed to people with a background in language studies and some familiarity with personal computers, at the user level'. 2. Symbols and languages2 Computers are very general symbol manipulation machines. Symbols are made up of zeroes and ones and they can represent numbers but also more complex objects like words, sentences, syntactic trees, etc. Take, for example, the word "1s". Many computers will represent this word as the sequence of two bytes3 1000100 1 and 1001001 1 corresponding to the letters 1 (137) and S (147) in the ASCII code (American Standard Code for Information Exchange). If you 1. As an entertaining introduction to rhe basic aspects of computers and an "antidote against anxiety produced by computers", 1 would recommend John Shore's The Sachertorte Algorithm and Other Antidotes to Computer Anxiety, 1985, Viking Penguin. There is Spanish translation published by Alianza Editorial (Alianza Universidad collection) 2. This section is based rnainly on section 1.1 in the Introduction of Gazdar and Mellish (1989). 3. A byte is an information unit consisting of eight binary digits or bits. Cornputational Linguistiw: a brief introduction Links & Letters 1, 1994 11 give a computer a list of names and ask it to sort them in alphabeticai order, "in" will precede "six" not because "i" precedes "S" in the alphabet, but because 137 is a smaller number than 147. The point of the previous example is that computers represent linguistic objects in non-linguistic ways. We said before that computers are symbol manipulation machines. This means that, at the lowest level, computers perform very basic operations. Three decades ago, the instructions that programmers gave the computers (the programs) were very much machine oriented, which means that they had to te11 the Computer to add numbers or move information around in the computer's memory. Programmers had to think of the problems in terms of numbers. Fortunately computer science has developed "high level" programming languages that ailow to write more abstract instructions and concentrate on the problem which the program is intended to solve. Arnong the high level programming languages used in Computational Linguistics projects, LISP and PROLOG are the most common4. Sometimes other languages are chosen, mainly to achieve higher speed in the execution of tasks, for instance "C" language and its variations. 3. Computational linguists and natural language Before we start our tour of Computational Linguistics, we should make several observations on its goals compared to the goals of Theoretical Linguistics. The goal of Theoretical (generative) Linguists is to find the simplest theory of grammar that can account for our knowledge of language, and to explain the innate mechanisms that allow people to learn and use human language. They are concerned with language universals (principles of grammar which apply to al1 natural languages) and they focus mainly on grammaticai competence (i.e., why people accept some sentences and reject others). Some particular linguistic theories also take as a fundamental goal to explain language use in ways which are psychologically plausible. The goal of computationai linguists is to write programs that can handle (understand or generate) as much natural language material5 as possible. These programs are good but approximate solutions; they cannot deal with al1 sentences of a natural language, although they deal with the most common and interesting constructions. This fact, which is generally accepted by computa- 4. LISP and PROLOG are very different programrning languages, the basic difference being in the underlying philosophy of how knowledge is stored and put to use and how problems need to be approached. 5. The terrn "Cornputational Linguistics" refers to studies on language independent of its physical realization as sound, which does not rnean that cornputers cannot "hear" or "speak". Machine decoding of spoken material, Le., hearing and identifying sentences as sequences of sounds is the goal of Speech Recognition, a field that combines work in Phoneticsl Phonology and Engineering. Machine production of spoken material ("uttering a rnessage) is the goal of Speech Synthesis, also an interdisciplinary field. 12 Links & Letters 1, 1994 Anna Espunya i Prat tional linguists, would be unacceptable for theoretical linguists, since it is part of their goal to account for al1 grammatical sentences of a language with their theory of grarnmar. Work in Theoretical Linguistics is relevant for Computational Linguistics; al1 generalization efforts (e.g., by reducing a large variety of sentences to a small set of rules and constraints on those rules) made in the former to describe the grammar of a particular natural language, are essential for the latter, especially in the process of sentence analysis. Work in Computational Linguistics is relevant for Theoretical Linguistics. The theory that underlies the more pragmatic work in Computational Linguistics views language understanding and generation as processes of symbol-ma- nipulation in a rule-governed fashion. To the extent that Theoretical Linguistics is interested in al1 aspects of the language capacity (the abstract knowledge of language and how it is used), its work should be testable by systems which computational linguists design (Grishman 1986, Winograd 1983). The task of constructing systems that understand or generate natural language is a complex one. It requires the integration of many kinds of data, linguistic (morpho-syntactic, semantic) and non-linguistic (knowledge of the domain of discourse). It also requires an effective use of al1 data. In this sense, designing and building a natural language application is an engineering task. One general strategy to make construction jobs easier is modularity, (i.e., dividing the problem into smaller subproblems. This notion is not foreign to linguistics. Traditionally, the language capacity is represented and studied as worlung in levels of structure: sounds, words, sentences. Linguists study the phonetics, the phonology, the morphology, the semantics, the syntax of a language and they assume the existente of levels or modules in human competence (e.g., Chomsky's Autonomous Syntax Principle). Even if the modular view is a simplification of the language capacity, it makes natural language systems flexible and easy to expand. Just how much knowledge is used in the understanding or generation process depends on the purpose of the application. For many applications the essential task is analysing sentences, (i.e., determining what sentences mean. Some applications also require an analysis of suprasentential units, such as discourse and dialogue. In this presentation we will concentrate on sentence analysis. 4. Sentence analysis We said before that the goal of sentence analysis is to determine what a sentence means. In computer terms, every input sentence has to be assigned a meaning representation of some kind. Two types of information are combined in a sentence that allow speakers to reach an interpretation of that sentence: its Computational Linguistics: a brief introduction Links & Letters 1, 1994 13 syntactic structure and the lexical meaning ofthe words that compose it. Words usually take special shapes when they occur syntagmatically (i.e., in relation with the other words in the sentence). Thus the morphology ofwords is relevant for syntactic analysis. Once the structure of the sentence is determined, semantics is in charge of accounting for the way words and structures combine to express a meaning. Sections 4.1 and 4.2 try to explain in very simple terms the tasks of the different modules of a sentence analysis system and the language facts such a system has to be ready to deal with, particularly those related to Morphology and Syntax. Section 4.3. introduces several basic issues related to Semantics. 4.1. Morphological analysis Sentences are made up of words. Therefore, an important step in the process of syntactic analysis is looking up the words in the dictionary. The look-up stage is not a trivial one. When words appear in sentences they usually carry inflectional endings. Derivational afixes are also very common and they often change the part of speech of the root they attach to. And we should bear in mind that addition of affixes may involve spelling changes. Let me use some examples from English to illustrate the kind of problems a computational linguist faces when trying to formalize al1 morphological facts of a language6. Consider the conjugation of the English verb. Suppose the sentence we are trying to analyse is: She always stops the joggers. When looking up the word "stops", the result we expect is an analysis like: {stop, verb} + {-S, 3rd person singular, present tense} Our morphological analyser will have to divide the sequence "S t o p s" into two valid morphs, corresponding to the root {stop} and the inflectional ending {-S}, respectively. In order for the morphological analyser to identify the two . morphs, they have to be in the dictionary which is consulted by the program. For now we may assume that both {stop, verb} and {-S, 3rd person singular, present tense} are in the dictionary. It does not seem important whether the items in the dictionary represent morphemes (abstract units) or morphs 6. In fact, English is a simple language as far as its inflectional morphology is concerned. Romance languages, just to mention a well-known family, display complex inflectional systems. Just as an example, consider the Spanish verb "acordar" (to agree). Some of its conjugated forms have root "acord-", with the stress on the inflection, e.g., "acordaremos" (1st. person plural, future tense), and other forms use the root "acuerd-", with the stress on the root, e.g. "acuerdas" (2nd person singular, present tense). The change "o" - "ue" is present in other verbs: "recordar", "volar", "sonar", "rogar", etc. 14 Links & Letters 1, 1994 Anna Espunya i Prat (particular realisations) because the representation of morphemes and the representation of morphs have exactly the same characters. Now let us suppose that the verb is not "stops" but "spies". In this case, the dictionary entries {spy, verb} and {-S, 3rd person singular} may never be identified by the analyser, which is dealing with the sequence "S p i e S". Probably the first solution that comes to mind is to have two entries for rhe verb "spy": {spy, verb} and {spie, verb}, with a tag signalling that they are the same verb, have the same meaning, etc. This may certainly be the only solution if the spelling alternation "y 1 ie" only affected the verb "spy": that is actually how morphological conditioning (e.g, men as the plural of man, deer as the plural of deer) is dealt with. However, since many words (nouns and verbs) show the same spelling change, it may be more eficienr to incorporate the linguistic generalisation al1 roots ending in a consonant + y suffer a spelling change from y to ie before inflections that do not begin with i . Generalisations allow economy in the storage space, which in turn reduces the time required to find items. A possible approach to the problem is to conceive the spelling change as a rule or an instruction to relate input words ending in ie in the appropriate conditions to dictionary items ending in y . Thus the dictionary only needs to include representations of morphemes (e.g., {spy, verb} but not of each concrete realization {spy, verb, non-third-person-singular}, {spie, verb, third-person-sin- gular}. The morphology analysis program identifies the potential morphs in the input word. If a possible spelling change is detected (e.g., ie from y in the sequence 'S p i e" in "S p i e S") , a small sub-program returns the candidate morpheme {spy}, which is then checked in the dictionary. This approach is called two-leve1 morphology7, because there are "surface" forms (those of input words) and "lexical" forms (those in the dictionary). The correspondence between the two levels is achieved through the small sub-programs. 4.2. Analysing syntax: parsers and grammars In logical or mathematical terms, ~rovidin~ a syntactic anal~sis of a sentence is equivalent to finding out whether that sentence belongs to the set of possible sentences of a language, and if it is so, giving a representation of its structure, for instance in the form of a syntactic tree or a bracketed sentences with labels as subscripts. As we know, the number of sentences that are possible in a language is infinite. Fortunately, membership in this infinite set seems to be characterizable through a finite set of rules. Such characterizations of languages are called "grammars". Together with the lexicon (or dictionary), grammars can be considered the knowledge of language. In Computational Linguistics, the process of syntactic analysis is called "parsing". 7. The first implementations of "two-level" morphological analysers were written by Karttunen and his students for English (Karttunen, 1983) based on the work on Finnish by Kimmo Koskenniemi (see Barton et al. 1987 and Karttunen 1983). Cornputational Linguistics: a brief introduction Links & Letters 1, 1994 15 What is required by a computer to parse a sentence of a particular language? First ofall, the computer should have the knowledge of that particular language, (i.e., a grammar and a dictionary). Secondly, the computer should be able to use the knowledge of language. We need a program that takes the sentence as input and finds a combination of grammar rules and words of the dictionary that describe that sentence. Such programs are called "parsers". Parsers make use of grammars. Both may be integrated in different ways, or rather, to various degrees. At one end, there are the parsers which contain instructions equivalent to grammar rules. The separation between grammar and parser is less clear. At the other end, there are systems which keep grammar and parser separated as different modules so that the same parser may be used with grammars of different languages. Another advantage of keeping the parser separated from the grammar is that it saves time and effort to the grammar writer (the person who writes rules that describe the particular language) and the programmer who builds the parser. If a gramatical sentence is not accepted by the parser, the problem could be in either component: the grammar might be wrong, or the parser might not work properly. It is now time to set abstract discussions aside for a moment and see a description of a toy program for the syntactic analysis of language X, a subset of English. The program's components are a small grammar, an even smaller lexicon and the description of the parser. Even though we described morphological analysis, we will obviate this step here. grammar of language X: S+NP VP NP + DET N VP+VtNP VP + Vi This grammar consists of a set of rewriting rules, rules that allow to build phrase structure trees of sentences. Each node has a symbol (syntactic category: S, NP, VP, etc. or word). The symbol on the left hand side of the rule is the mother of the symbols on the right hand side. This is called "immediate constituent approach", and it is just one of the possible approaches to grammar. lexicon of language X: the : DET run : Vi (intransitive verb) spy : Vt (transitive verb) jogger: N girl: N 16 Links & Leners 1, 1994 Anna Espunya i Prat Combining the rules and words of the toy grammar and lexicon (obviating the morphology), sentences like the following will be generated: The girl spies the joggers. The girls run. The jogger runs. The joggers spy the girls. The jogger spies the girls. Once we "know" language X (we have a grammar and a dictionary), we turn to a description in plain English of the sequence of actions performed by one particular parser. The following is one of many possible parsing strategies. Since this is perhaps the most intuitive one, it will be used as example in this little parsing exercise. It is called bottom-up parsing: notice that we start building the tree from the words and the lower branches of the tree before we get to the top symbol. We will present simultaneously the instructions (in plain text) and the example parse (in italics). Our example sentence is: "The girl runs." 1. Read word (from left to right). When al1 words in the sentence have been read, look in the tree-bag (where al1 potential branches found during the parsing process are stored) for a tree whose root is S. If there is one, display it to the user. If not, go to step 4. 1'. '?hen 2. Look it up in the dictionary (this step includes morphological analysis). - If it is there, find its grammatical category. 2'. '?he" is in the dictionary: the : Det. We have ourjrst bit of the phrase structure tree: DET The 3. a. Look in the grammar for a rule whose right hand side starts (from left to right) with the grammatical category of the word. b. Do the following to al1 the symbols of the right hand side of the rule found in step 3 (a). When this step is finished, go back to step 1: i. Read the next word, look it up in the dictionary, and find its grammatical category. ii. If its grammatical category coincides with the following symbol on the right hand side of the rule, repeat step b. 3'. a. The rule NP Det N has Det as its right hand side. We keep it as our current rule. 6. current rule: NP 4 Det N i next word girl . The dictionary has the en? girl: N. We have another potential branch of the tree. ii. N coincides with the following symbol of the right hand side of the rule after Det, i.e., NP + Det N. Since there are no more symbols left in the right hand side of the rule, we keep the rule NP 4 Det N in the tree-bag and we go back to step one. One of thepotential branches is: DES N the girl l. Next word : runs. 2. Dictiona y entry: run : Vi. We have a new bit of the tree. Vi runs 3. a. rule W + Vi. 6. The rule has no other symbols on its right hand side. We keep it in the treebag, Vi runs 4. When al1 words in the sentence have been read, and rules have been found whose right hand sides had the grarnmatical categories of words, the tree-bag has separate rules that still have to be combined. The next action consists in finding a rule in the grammar whose right hand side symbols are left hand side symbols of the rules contained in the tree-bag. Rules in the grammar that match this specification are kept in the tree-bag. The process finishes when a rule is found whose left hand side is the top node (Sentence). Then the syntactic tree is ready to be displayed. 4: Relevant contents of our tree-bag: NP + Det N VP + Vi