3.1.5 Agreement

We introduced the plural morpheme above, and noted that plural is marked on both nouns and verbs in English. We say that the subject noun and the main verb in English have to agree in number, meaning that the two must either be both singular or both plural. There are other kinds of agreement processes. For example nouns, adjectives, and sometimes verbs in many languages are marked for gender. A gender is a kind of equivalence class that is used by the language to categorize the nouns; each noun

falls into one class. Many languages (for example Romance languages like French, Spanish, or Italian) have 2 genders, which are referred to as masculine and feminine. Other languages (like most Germanic and Slavic languages) have three (masculine, feminine, neuter). Some languages, for example the Bantu languages of Africa, have as many as 20 genders. When the number of classes is very large, we often refer to them as noun classes instead of genders.

Gender is sometimes marked explicitly on a noun; for example Spanish masculine words often end in -o and feminine words in -a. But in many cases the gender is not marked in the letters or phones of the noun itself. Instead, it is a property of the word that must be stored in a lexicon. We will see an example of this in Fig. 3.2.

3.2 FINITE-STATE MORPHOLOGICAL PARSING

Let's now proceed to the problem of parsing morphology. Our goal will be to take input forms like those in the first and third columns of Fig. 3.2, produce output forms like those in the second and fourth column.

The second column contains the stem of each word as well as assorted morphological features. These features specify additional information about the stem. For example the feature +N means that the word is a noun; +Sg means it is singular, +P1 that it is plural. Morphological features will be referred to again in Ch. 5 and in more detail in Ch. 16; for now, consider +Sg to be a primitive unit that means “singular”. Spanish has some features that don’t occur in English; for example the nouns lugar and pavo are marked +Masc (masculine). Because Spanish nouns agree in gender with adjectives, knowing the gender of a noun will be important for tagging and parsing.

Note that some of the input forms (like caught, goose, canto, or vino) will be ambiguous between different morphological parses. For now, we will consider the goal of morphological parsing merely to list all possible parses. We will return to the task of disambiguating among morphological parses in Ch. 5.

In order to build a morphological parser, we'll need at least the following:

1. lexicon: the list of stems and affixes, together with basic information about them (whether a stem is a Noun stem or a Verb stem, etc.).

2. morphotactics: the model of morpheme ordering that explains which classes of morphemes can follow other classes of morphemes inside a word. For example, the fact that the English plural morpheme follows the noun rather than preceding it is a morphotactic fact.

3. orthographic rules: these spelling rules are used to model the changes that occur in a word, usually when two morphemes combine (e.g., the y $ \rightarrow $ ie spelling rule discussed above that changes city + -s to cities rather than cities).

The next section will discuss how to represent a simple version of the lexicon just for the sub-problem of morphological recognition, including how to use FSAs to model morphotactic knowledge.

In following sections we will then introduce the finite-state transducer (FST) as a way of modeling morphological features in the lexicon, and addressing morphological parsing. Finally, we show how to use FSTs to model orthographic rules.

3.3 BUILDING A FINITE-STATE LEXICON

A lexicon is a repository for words. The simplest possible lexicon would consist of an explicit list of every word of the language (every word, i.e., including abbreviations ("AAA") and proper names ("Jane" or "Beijing")) as follows:

a, AAA, AA, Aachen, aardvark, aardwolf, aba, abaca, aback, ...

Since it will often be inconvenient or impossible, for the various reasons we discussed above, to list every word in the language, computational lexicons are usually structured with a list of each of the stems and affixes of the language together with a representation of the morphotactics that tells us how they can fit together. There are many ways to model morphotactics; one of the most common is the finite-state automaton. A very simple finite-state model for English nominal inflection might look like Fig. 3.3.

The FSA in Fig. 3.3 assumes that the lexicon includes regular nouns (reg-noun) that take the regular -s plural (e.g., cat, dog, fox, aardvark). These are the vast majority of English nouns since for now we will ignore the fact that the plural of words like fox

have an inserted e: foxes. The lexicon also includes irregular noun forms that don't take -s, both singular irreg-sg-noun (goose, mouse) and plural irreg-pl-noun (geese, mice).

This lexicon has three stem classes (reg-verb-stem, irreg-verb-stem, and irreg-past-verb-form), plus four more affix classes (-ed past, -ed participle, -ing participle, and third singular -s):

English derivational morphology is significantly more complex than English inflectional morphology, and so automata for modeling English derivation tend to be quite complex. Some models of English derivation, in fact, are based on the more complex context-free grammars of Ch. 12 (Sproat, 1993).

Consider a relatively simpler case of derivation: the morphotactics of English adjectives. Here are some examples from Antworth (1990):

big, bigger, biggest,

cool, cooler, coolest, coolly

happy, happier, happiest, happily

red, redder, reddest

unhappy, unhappier, unhappiest, unhappy real, unreal, really

clear, clearer, clearest, clearly, unclear, unclearly

An initial hypothesis might be that adjectives can have an optional prefix (un-), an obligatory root (big, cool, etc.) and an optional suffix (-er, -est, or -ly). This might suggest the the FSA in Fig. 3.5.

Alas, while this FSA will recognize all the adjectives in the table above, it will also recognize ungrammatical forms like unbig, unfast, oranger, or smally. We need to set up classes of roots and specify their possible suffixes. Thus adj-root $ _{1} $ would include adjectives that can occur with un- and -ly (clear, happy, and real) while adj-root $ _{2} $ will include adjectives that can't (big, small), and so on.

This gives an idea of the complexity to be expected from English derivation. As a further example, we give in Figure 3.6 another fragment of an FSA for English nominal and verbal derivational morphology, based on Sproat (1993), Bauer (1983), and Porter (1980). This FSA models a number of derivational facts, such as the well known generalization that any verb ending in -ize can be followed by the nominalizing suffix -ation (Bauer, 1983; Sproat, 1993). Thus since there is a word fossilize, we can predict the word fossilization by following states $ q_{0} $, $ q_{1} $, and $ q_{2} $. Similarly, adjectives ending in -al or -able at $ q_{5} $ (equal, formal, realizable) can take the suffix -ity, or sometimes the suffix -ness to state $ q_{6} $ (naturalness, casualness). We leave it as an exercise for the reader (Exercise 3.1) to discover some of the individual exceptions to many of these constraints, and also to give examples of some of the various noun and verb classes.

We can now use these FSAs to solve the problem of morphological recognition; that is, of determining whether an input string of letters makes up a legitimate English word or not. We do this by taking the morphotactic FSAs, and plugging in each “sub-

lexicon" into the FSA. That is, we expand each arc (e.g., the reg-noun-stem arc) with all the morphemes that make up the set of reg-noun-stem. The resulting FSA can then be defined at the level of the individual letter.

Fig. 3.7 shows the noun-recognition FSA produced by expanding the Nominal Inflection FSA of Fig. 3.3 with sample regular and irregular nouns for each class. We can use Fig. 3.7 to recognize strings like aardvarks by simply starting at the initial state, and comparing the input letter by letter with each word on each outgoing arc, and so on, just as we saw in Ch. 2.

3.4 FINITE-STATE TRANSDUCERS

We’ve now seen that FSAs can represent the morphotactic structure of a lexicon, and can be used for word recognition. In this section we introduce the finite-state transducer. The next section will show how transducers can be applied to morphological parsing.

A transducer maps between one representation and another; a finite-state transducer or FST is a type of finite automaton which maps between two sets of symbols. We can visualize an FST as a two-tape automaton which recognizes or generates pairs of strings. Intuitively, we can do this by labeling each arc in the finite-state machine with two symbol strings, one from each tape. Fig. 3.8 shows an example of an FST where each arc is labeled by an input and output string, separated by a colon.

The FST thus has a more general function than an FSA; where an FSA defines a formal language by defining a set of strings, an FST defines a relation between sets of strings. Another way of looking at an FST is as a machine that reads one string and generates another. Here's a summary of this four-fold way of thinking about transducers:

• FST as recognizer: a transducer that takes a pair of strings as input and outputs accept if the string-pair is in the string-pair language, and reject if it is not.

Figure 3.8 A finite-state transducer, modified from Mohri (1997).

• FST as generator: a machine that outputs pairs of strings of the language. Thus the output is a yes or no, and a pair of output strings.

• FST as translator: a machine that reads a string and outputs another string

• FST as set relater: a machine that computes relations between sets.

All of these have applications in speech and language processing. For morphological parsing (and for many other NLP applications), we will apply the FST as translator metaphor, taking as input a string of letters and producing as output a string of morphemes.

Let's begin with a formal definition. An FST can be formally defined with 7 parameters:

Q a finite set of $N$ states $q_{0},q_{1},\ldots,q_{N-1}$

$ \Sigma $ a finite set corresponding to the input alphabet

$ \Delta $ a finite set corresponding to the output alphabet

$ q_0 \in Q $ the start state

$ F \subseteq Q $ the set of final states

$ \delta(q,w) $ the transition function or transition matrix between states; Given a state $ q \in Q $ and a string $ w \in \Sigma^* $, $ \delta(q,w) $ returns a set of new states $ Q' \in Q $. $ \delta $ is thus a function from $ Q \times \Sigma^* $ to $ 2^Q $ (because there are $ 2^Q $ possible subsets of $ Q $). $ \delta $ returns a set of states rather than a single state because a given input may be ambiguous in which state it maps to.

$ \sigma(q,w) $ the output function giving the set of possible output strings for each state and input. Given a state $ q \in Q $ and a string $ w \in \Sigma^* $, $ \sigma(q,w) $ gives a set of output strings, each a string $ o \in \Delta^* $. $ \sigma $ is thus a function from $ Q \times \Sigma^* $ to $ 2^{\Delta^*} $

Where FSAs are isomorphic to regular languages, FSTs are isomorphic to regular relations. Regular relations are sets of pairs of strings, a natural extension of the regular languages, which are sets of strings. Like FSAs and regular languages, FSTs and regular relations are closed under union, although in general they are not closed under difference, complementation and intersection (although some useful subclasses of FSTs are closed under these operations; in general FSTs that are not augmented with the $ \epsilon $ are more likely to have such closure properties). Besides union, FSTs have two additional closure properties that turn out to be extremely useful:

• inversion: The inversion of a transducer $ T(T^{-1}) $ simply switches the input and output labels. Thus if T maps from the input alphabet I to the output alphabet O, $ T^{-1} $ maps from O to I.

composition: If $ T_1 $ is a transducer from $ I_1 $ to $ O_1 $ and $ T_2 $ a transducer from $ O_1 $ to $ O_2 $, then $ T_1 \circ T_2 $ maps from $ I_1 $ to $ O_2 $.

Inversion is useful because it makes it easy to convert a FST-as-parser into an FST-as-generator.

Composition is useful because it allows us to take two transducers that run in series and replace them with one more complex transducer. Composition works as in algebra, applying $ T_1 \circ T_2 $ to an input sequence $ S $ is identical to applying $ T_1 $ to $ S $ and then $ T_2 $ to the result; thus $ T_1 \circ T_2(S) = T_2(T_1(S)) $.

Fig. 3.9, for example, shows the composition of $ [a:b] $ + with $ [b:c] $ + to produce $ [a:c] $ +.

The projection of an FST is the FSA that is produced by extracting only one side of the relation. We can refer to the projection to the left or upper side of the relation as the upper or first projection and the projection to the lower or right side of the relation as the lower or second projection.