3.4.1 Sequential Transducers and Determinism

Transducers as we have described them may be nondeterministic, in that a given input may translate to many possible output symbols. Thus using general FSTs requires the kinds of search algorithms discussed in Ch. 2, making FSTs quite slow in the general case. This suggests that it would nice to have an algorithm to convert a nondeterministic FST to a deterministic one. But while every non-deterministic FSA is equivalent to some deterministic FSA, not all finite-state transducers can be determined.

Sequential transducers, by contrast, are a subtype of transducers that are deterministic on their input. At any state of a sequential transducer, each given symbol of the input alphabet $ \Sigma $ can label at most one transition out of that state. Fig. 3.10 gives an example of a sequential transducer from Mohri (1997); note that here, unlike the transducer in Fig. 3.8, the transitions out of each state are deterministic based on the state and the input symbol. Sequential transducers can have epsilon symbols in the output string, but not on the input.

Sequential transducers are not necessarily sequential on their output. Mohri's transducer in Fig. 3.10 is not, for example, since two distinct transitions leaving state 0 have the same output (b). Since the inverse of a sequential transducer may thus not be sequential, we always need to specify the direction of the transduction when discussing sequentiality. Formally, the definition of sequential transducers modifies the $ \delta $ and $ \sigma $

functions slightly; $ \delta $ becomes a function from $ Q \times \Sigma^* $ to $ Q $ (rather than to $ 2^Q $), and $ \sigma $ becomes a function from $ Q \times \Sigma^* $ to $ \Delta^* $ (rather than to $ 2^{\Delta^*} $).

One generalization of sequential transducers is the subsequential transducer (Schützenberger, 1977), which generates an additional output string at the final states, concatenating it onto the output produced so far.

What makes sequential and subsequent transducers important is their efficiency; because they are deterministic on input, they can be processed in time proportional to the number of symbols in the input (they are linear in their input length) rather than proportional to some much larger number which is a function of the number of states. Another advantage of subsequent transducers is that there exist efficient algorithms for their determination (Mohri, 1997) and minimization (Mohri, 2000), extending the algorithms for determination and minimization of finite-state automata that we saw in Ch. 2. also an equivalence algorithm.

While both sequential and subsequentă nt transducers are deterministic and efficient, neither of them is able to handle ambiguity, since they transduce each input string to exactly one possible output string. Since ambiguity is a crucial property of natural language, it will be useful to have an extension of subsequentă nt transducers that can deal with ambiguity, but still retain the efficiency and other useful properties of sequential transducers. One such generalization of subsequentă nt transducers is the p-subsequential transducer. A p-subsequential transducer allows for $p(p \geq 1)$ final output strings to be associated with each final state (Mohri, 1996). They can thus handle a finite amount of ambiguity, which is useful for many NLP tasks. Fig. 3.11 shows an example of a 2-subsequential FST.

Mohri (1996, 1997) show a number of tasks whose ambiguity can be limited in this way, including the representation of dictionaries, the compilation of morphological and phonological rules, and local syntactic constraints. For each of these kinds of problems, he and others have shown that they are p-subsequentializable, and thus can be determined and minimized. This class of transducers includes many, although not necessarily all, morphological rules.

3.5 FSTS FOR MORPHOLOGICAL PARSING

Let's now turn to the task of morphological parsing. Given the input cats, for instance, we'd like to output cat +N +Pl, telling us that cat is a plural noun. Given the Spanish input bebo ('I drink'), we'd like to output beber +V +PInd +1P +Sg telling us that bebo is the present indicative first person singular form of the Spanish verb beber, 'to drink'.

In the finite-state morphology paradigm that we will use, we represent a word as a correspondence between a lexical level, which represents a concatenation of morphemes making up a word, and the surface level, which represents the concatenation of letters which make up the actual spelling of the word. Fig. 3.12 shows these two levels for (English) cats.

For finite-state morphology it's convenient to view an FST as having two tapes. The upper or lexical tape, is composed from characters from one alphabet $ \Sigma $. The lower or surface tape, is composed of characters from another alphabet $ \Delta $. In the two-level morphology of Koskenniemi (1983), we allow each arc only to have a single symbol from each alphabet. We can then combine the two symbol alphabets $ \Sigma $ and $ \Delta $ to create a new alphabet, $ \Sigma' $, which makes the relationship to FSAs quite clear. $ \Sigma' $ is a finite alphabet of complex symbols. Each complex symbol is composed of an input-output pair $ i : o $; one symbol $ i $ from the input alphabet $ \Sigma $, and one symbol $ o $ from an output alphabet $ \Delta $, thus $ \Sigma' \subseteq \Sigma \times \Delta $. $ \Sigma $ and $ \Delta $ may each also include the epsilon symbol $ \epsilon $. Thus where an FSA accepts a language stated over a finite alphabet of single symbols, such as the alphabet of our sheep language:

$$ \Sigma=\left\{b,a,!\right\} $$

an FST defined this way accepts a language stated over pairs of symbols, as in:

$$ \Sigma^{\prime}=\left\{a:a,b:b,!!\triangleleft!\right.,a\triangleleft!\left.,a:\epsilon,\epsilon:\right\} $$

In two-level morphology, the pairs of symbols in $ \Sigma' $ are also called feasible pairs. Thus each feasible pair symbol $ a : b $ in the transducer alphabet $ \Sigma' $ expresses how the symbol $ a $ from one tape is mapped to the symbol $ b $ on the other tape. For example $ a : \epsilon $ means that an $ a $ on the upper tape will correspond to nothing on the lower tape. Just as for an FSA, we can write regular expressions in the complex alphabet $ \Sigma' $. Since it's most common for symbols to map to themselves, in two-level morphology we call pairs like $ a : a $ default pairs, and just refer to them by the single letter $ a $.

We are now ready to build an FST morphological parser out of our earlier morpho-tactic FSAs and lexica by adding an extra “lexical” tape and the appropriate morphological features. Fig. 3.13 shows an augmentation of Fig. 3.3 with the nominal morphological features (+Sg and +Pl) that correspond to each morpheme. The symbol ^ indicates a morpheme boundary, while the symbol # indicates a word boundary. The morphological features map to the empty string $ \epsilon $ or the boundary symbols since there is no segment corresponding to them on the output tape.

In order to use Fig. 3.13 as a morphological noun parser, it needs to be expanded with all the individual regular and irregular noun stems, replacing the labels reg-noun etc. In order to do this we need to update the lexicon for this transducer, so that irregular plurals like geese will parse into the correct stem goose +N +Pl. We do this by allowing the lexicon to also have two levels. Since surface geese maps to lexical goose, the new lexical entry will be “g:g o:e o:e s:s e:e”. Regular forms are simpler; the two-level entry for fox will now be “f:f o:o x:x”, but by relying on the orthographic convention that f stands for f:f and so on, we can simply refer to it as fox and the form for geese as “g o:e o:e s e”. Thus the lexicon will look only slightly more complex:

The resulting transducer, shown in Fig. 3.14, will map plural nouns into the stem plus the morphological marker +Pl, and singular nouns into the stem plus the morphological marker +Sg. Thus a surface cats will map to cat +N +Pl. This can be viewed in feasible-pair format as follows:

$$ \begin{array}{l}c:c\ a:a\ t:t\ +N:\epsilon\ +P1:\wedge s\#\end{array} $$

Since the output symbols include the morpheme and word boundary markers $ ^{\wedge} $ and #, the lower labels Fig. 3.14 do not correspond exactly to the surface level. Hence we refer to tapes with these morpheme boundary markers in Fig. 3.15 as intermediate tapes; the next section will show how the boundary marker is removed.

3.6 TRANSDUCERS AND ORTHOGRAPHIC RULES

The method described in the previous section will successfully recognize words like aardvarks and mice. But just concatenating the morphemes won't work for cases where there is a spelling change; it would incorrectly reject an input like foxes and accept an input like foxes. We need to deal with the fact that English often requires spelling changes at morpheme boundaries by introducing spelling rules (or orthographic rules). This section introduces a number of notations for writing such rules and shows how to implement the rules as transducers. In general, the ability to implement rules as a transducer turns out to be useful throughout speech and language processing. Here's some spelling rules:

We can think of these spelling changes as taking as input a simple concatenation of morphemes (the “intermediate output” of the lexical transducer in Fig. 3.14) and producing as output a slightly-modified (correctly-spelled) concatenation of morphemes. Fig. 3.16 shows in schematic form the three levels we are talking about: lexical, intermediate, and surface. So for example we could write an E-insertion rule that performs the mapping from the intermediate to surface levels shown in Fig. 3.16. Such a rule

might say something like “insert an e on the surface tape just when the lexical tape has a morpheme ending in x (or z, etc) and the next morpheme is -s”. Here’s a formalization of the rule:

$$ \epsilon \longrightarrow \mathrm{e} / \left\{ \begin{array}{l} x \\ s \\ z \end{array} \right\} \xrightarrow{\quad} \mathrm{s} \# $$

This is the rule notation of Chomsky and Halle (1968); a rule of the form $ a \to b/c \_\_\_ d $ means “rewrite $ a $ as $ b $ when it occurs between $ c $ and $ d $”. Since the symbol $ \epsilon $ means an empty transition, replacing it means inserting something. Recall that the symbol $ \hat{} $ indicates a morpheme boundary. These boundaries are deleted by including the symbol $ \hat{} $: $ \epsilon $ in the default pairs for the transducer; thus morpheme boundary markers are deleted on the surface level by default. The $ \# $ symbol is a special symbol that marks a word boundary. Thus (3.4) means “insert an $ e $ after a morpheme-final $ x $, $ s $, or $ z $, and before the morpheme $ s $”. Fig. 3.17 shows an automaton that corresponds to this rule.

The idea in building a transducer for a particular rule is to express only the constraints necessary for that rule, allowing any other string of symbols to pass through

unchanged. This rule is used to ensure that we can only see the $ \epsilon:e $ pair if we are in the proper context. So state $ q_0 $, which models having seen only default pairs unrelated to the rule, is an accepting state, as is $ q_1 $, which models having seen a $ z $, s, or x. $ q_2 $ models having seen the morpheme boundary after the $ z $, s, or x, and again is an accepting state. State $ q_3 $ models having just seen the E-insertion; it is not an accepting state, since the insertion is only allowed if it is followed by the s morpheme and then the end-of-word symbol \#.

The other symbol is used in Fig. 3.17 to safely pass through any parts of words that don't play a role in the E-insertion rule. other means “any feasible pair that is not in this transducer”. So for example when leaving state $ q_0 $, we go to $ q_1 $ on the z, s, or x symbols, rather than following the other arc and staying in $ q_0 $. The semantics of other depends on what symbols are on other arcs; since # is mentioned on some arcs, it is (by definition) not included in other, and thus, for example, is explicitly mentioned on the arc from $ q_2 $ to $ q_0 $.

A transducer needs to correctly reject a string that applies the rule when it shouldn't. One possible bad string would have the correct environment for the E-insertion, but have no insertion. State $ q_5 $ is used to ensure that the $ e $ is always inserted whenever the environment is appropriate; the transducer reaches $ q_5 $ only when it has seen an $ s $ after an appropriate morpheme boundary. If the machine is in state $ q_5 $ and the next symbol is $ \# $, the machine rejects the string (because there is no legal transition on $ # $ from $ q_5 $). Fig. 3.18 shows the transition table for the rule which makes the illegal transitions explicit with the “_” symbol.

The next section will show a trace of this E-insertion transducer running on a sample input string.

3.7 COMBINING FST LEXICON AND RULES

We are now ready to combine our lexicon and rule transducers for parsing and generating. Fig. 3.19 shows the architecture of a two-level morphology system, whether used for parsing or generating. The lexicon transducer maps between the lexical level, with its stems and morphological features, and an intermediate level that represents a simple concatenation of morphemes. Then a host of transducers, each representing a single spelling rule constraint, all run in parallel so as to map between this intermediate level and the surface level. Putting all the spelling rules in parallel is a design choice; we could also have chosen to run all the spelling rules in series (as a long cascade), if we slightly changed each rule.

The architecture in Fig. 3.19 is a two-level cascade of transducers. Cascading two automata means running them in series with the output of the first feeding the input to the second. Cascades can be of arbitrary depth, and each level might be built out of

many individual transducers. The cascade in Fig. 3.19 has two transducers in series: the transducer mapping from the lexical to the intermediate levels, and the collection of parallel transducers mapping from the intermediate to the surface level. The cascade can be run top-down to generate a string, or bottom-up to parse it; Fig. 3.20 shows a trace of the system accepting the mapping from $ f_ox + N + PL $ to foxes.

The power of finite-state transducers is that the exact same cascade with the same state sequences is used when the machine is generating the surface tape from the lexical tape, or when it is parsing the lexical tape from the surface tape. For example, for generation, imagine leaving the Intermediate and Surface tapes blank. Now if we run the lexicon transducer, given $ f_ox + N + PL $, it will produce $ f_ox^s $# on the Intermediate tape via the same states that it accepted the Lexical and Intermediate tapes in our earlier example. If we then allow all possible orthographic transducers to run in parallel, we will produce the same surface tape.

Parsing can be slightly more complicated than generation, because of the problem of ambiguity. For example, foxes can also be a verb (albeit a rare one, meaning “to baffle or confuse”), and hence the lexical parse for foxes could be Fox +V +3SG as well as Fox +N +PL. How are we to know which one is the proper parse? In fact, for ambiguous cases of this sort, the transducer is not capable of deciding. Disambiguating will require some external evidence such as the surrounding words. Thus foxes is likely to be a noun in the sequence I saw two foxes yesterday, but a verb in the sequence That trickster foxes me every time!. We will discuss such disambiguation algorithms in Ch. 5 and Ch. 20. Barring such external evidence, the best our transducer can do is just enumerate the possible choices; so we can transduce fox^s# into both Fox +V +3SG and Fox +N +PL.

There is a kind of ambiguity that we need to handle: local ambiguity that occurs during the process of parsing. For example, imagine parsing the input verb assess. After seeing ass, our E-insertion transducer may propose that the e that follows is

inserted by the spelling rule (for example, as far as the transducer is concerned, we might have been parsing the word asses). It is not until we don't see the # after asses, but rather run into another s, that we realize we have gone down an incorrect path.

Because of this non-determinism, FST-parsing algorithms need to incorporate some sort of search algorithm. Exercise 3.7 asks the reader to modify the algorithm for non-deterministic FSA recognition in Fig. ?? in Ch. 2 to do FST parsing.

Note that many possible spurious segmentations of the input, such as parsing assess as ^a^s^ses^s will be ruled out since no entry in the lexicon will match this string.

INTERSECTION

Running a cascade, particularly one with many levels, can be unwieldy. Luckily, we've already seen how to compose a cascade of transducers in series into a single more complex transducer. Transducers in parallel can be combined by automaton intersection. The automaton intersection algorithm just takes the Cartesian product of the states, i.e., for each state $ q_i $ in machine 1 and state $ q_j $ in machine 2, we create a new state $ q_{ij} $. Then for any input symbol $ a $, if machine 1 would transition to state $ q_n $ and machine 2 would transition to state $ q_{m} $, we transition to state $ q_{nm} $. Fig. 3.21 sketches how this intersection ( $ \wedge $) and composition ( $ \circ $) process might be carried out.

Since there are a number of rule→FST compilers, it is almost never necessary in practice to write an FST by hand. Kaplan and Kay (1994) give the mathematics that define the mapping from rules to two-level relations, and Antworth (1990) gives details of the algorithms for rule compilation. Mohri (1997) gives algorithms for transducer minimization and determination.

3.8 LEXICON-FREE FSTS: THE PORTER STEMMER

While building a transducer from a lexicon plus rules is the standard algorithm for morphological parsing, there are simpler algorithms that don't require the large on-line lexicon demanded by this algorithm. These are used especially in Information Retrieval (IR) tasks like web search (Ch. 23), in which a query such as a Boolean combination of relevant keywords or phrases, e.g., (marsupial OR kangaroo OR koala) returns documents that have these words in them. Since a document with the word marsupials

might not match the keyword marsupial, some IR systems first run a stemmer on the query and document words. Morphological information in IR is thus only used to determine that two words have the same stem; the suffixes are thrown away.

One of the most widely used such stemming algorithms is the simple and efficient Porter (1980) algorithm, which is based on a series of simple cascaded rewrite rules. Since cascaded rewrite rules are just the sort of thing that could be easily implemented as an FST, we think of the Porter algorithm as a lexicon-free FST stemmer (this idea will be developed further in the exercises (Exercise 3.6). The algorithm contains rules like these:

$$ \mathrm{ATIONAL}\rightarrow\mathrm{ATE}\ (\mathrm{e.g.},\mathrm{relational}\rightarrow\mathrm{relate}) $$

$$ ING\rightarrow\epsilon if stem contains vowel(e.g.,motoring\rightarrow motor) $$

See Porter (1980) or Martin Porter's official homepage for the Porter stemmer for more details.

Krovetz (1993) showed that stemming tends to somewhat improve the performance of information retrieval, especially with smaller documents (the larger the document, the higher the chance the keyword will occur in the exact form used in the query). Nonetheless, not all IR engines use stemming, partly because of stemmer errors such as these noted by Krovetz:

3.9 WORD AND SENTENCE TOKENIZATION

We have focused so far in this chapter on a problem of segmentation: how words can be segmented into morphemes. We turn now to a brief discussion of the very related problem of segmenting running text into words and sentences. This task is called tokenization.

Word tokenization may seem very simple in a language like English that separates words via a special ‘space’ character. As we will see below, not every language does this (Chinese, Japanese, and Thai, for example, do not). But a closer examination will make it clear that whitespace is not sufficient by itself. Consider the following sentences from a Wall Street Journal and New York Times article, respectively:

Mr. Sherwood said reaction to Sea Containers' proposal has been "very positive." In New York Stock Exchange composite trading yesterday, Sea Containers closed at $62.625, up 62.5 cents.

''I said, 'what're you? Crazy?' '' said Sadowsky. ''I can't afford to do that.'''

Segmenting purely on white-space would produce words like these:

cents.

said,

Crazy?

positive."

We could address these errors by treating punctuation, in addition to whitespace, as a word boundary. But punctuation often occurs word internally, in examples like m.p.h., Ph.D., AT&T, cap'n, 01/02/06, and google.com. Similarly, assuming that we want 62.5 to be a word, we'll need to avoid segmenting every period, since that will segment this into 62 and 5. Number expressions introduce other complications as well; while commas normally appear at word boundaries, commas are used inside numbers in English, every three digits: 555,500.50. Languages differ on punctuation styles for numbers; many continental European languages like Spanish, French, and German, by contrast, uses a comma to mark the decimal point, and spaces (or sometimes periods) where English puts commas: 555 500.50.

Another useful task a tokenizer can do for us is to expand clitic contractions that are marked by apostrophes, for example converting what're above to the two tokens what are, and we're to we are. This task is complicated by the fact that apostrophes are quite ambiguous, since they are also used as genitive markers (as in the book's over or in Containers' above) or as quotative markers (as in 'what're you? Crazy?' above). Such contractions occur in other alphabetic languages, including articles and pronouns in French (j'ai, l'homme). While these contractions tend to be clitics, not all clitics are marked this way with contraction. In general, then, segmenting and expanding clitics can be done as part of the process of morphological parsing presented earlier in the chapter.

Depending on the application, tokenization algorithms may also tokenize multi-word expressions like New York or rock 'n' roll, which requires a multiword expression dictionary of some sort. This makes tokenization intimately tied up with the task of detecting names, dates, and organizations, which is called named entity detection and will be discussed in Ch. 22.

In addition to word segmentation, sentence segmentation is a crucial first step in text processing. Segmenting a text into sentences is generally based on punctuation. This is because certain kinds of punctuation (periods, question marks, exclamation points) tend to mark sentence boundaries. Question marks and exclamation points are relatively unambiguous markers of sentence boundaries. Periods, on the other hand, are more ambiguous. The period character ‘.’ is ambiguous between a sentence boundary marker and a marker of abbreviations like Mr. or Inc. The previous sentence that you just read showed an even more complex case of this ambiguity, in which the final period of Inc. marked both an abbreviation and the sentence boundary marker. For this reason, sentence tokenization and word tokenization tend to be addressed jointly.

In general, sentence tokenization methods work by building a binary classifier (based on a sequence of rules, or on machine learning) which decides if a period is part of the word or is a sentence boundary marker. In making this decision, it helps to know if the period is attached to a commonly used abbreviation; thus an abbreviation dictionary is useful.

State-of-the-art methods for sentence tokenization are based on machine learning and will be introduced in later chapters. But a useful first step can still be taken via a sequence of regular expressions. We introduce here the first part; a word tokenization algorithm. Fig. 3.22 gives a simple Perl word tokenization algorithm based on Grefenstette (1999). The algorithm is quite minimal, designed mainly to clarify many of the segmentation issues we discussed in previous paragraphs.

The algorithm consists of a sequence of regular expression substitution rules. The first rule separates unambiguous punctuation like question marks and parentheses. The next rule segments commas unless they are inside numbers. We then disambiguate apostrophes and pull off word-final clitics. Finally, we deal with periods, using a (toy) abbreviation dictionary and some heuristics for detecting other abbreviations.

#!/usr/bin/perl

$letternumber = "[A-Za-z0-9]";

$notletter = "[^A-Za-z0-9]";

$alwayssep = "[\\?!(\)(\";/\\\]";

$clitic = "('|:|-|'S'D'M'LL'RE'VE|N'T's'd'm'll're've've|n't");

$abbr={Co.}= 1; $abbr{"Dr."} = 1; $abbr{"Jan."} = 1; $abbr{"Feb."} = 1;

while ($line = <>) { # read the next line from standard input

# put whitespace around unambiguous separators

$line = "s/s/alwayssep / $& /g;

# put whitespace around commas that aren't inside numbers

$line = "s/([^0-9]),/$1, /g;

$line = "s/({^0-9}) / , $1/g;

# distinguish singlequotes from apostrophes by

# segmenting off single quotes not preceded by letter

$line = "s/^{\& /g;

$line = "s/($notletter)/$1' /g;

# segment off unambiguous word-final clitics and punctuation

$line = "s/$clitic$/ $&/g;

$line = "s/$clitic($notletter) / $1 $2/g;

now deal with periods. For each possible word

@possiblewords=split(/\s+/,$line);

foreach $word @possiblewords) {

# if it ends in a period,

if (($word = / $letternumber/.)

&& !($abbr($word)) # and isn't on the abbreviation list

# and isn't a sequence of letters and periods (U.S.)

# and doesn't resemble an abbreviation (no vowels: Inc.)

&&!($word =

^([A-Za-z]).([A-Za-z]).+|[A-Z][bcdfghj-nptvxz]+.)$/)) {

# then segment off the period

$word = "s/.\$/ /.:/

}

# expand clitics

$word = "s/ve/have/;

$word = "s/m/am/;

print $word," "

}

print "n";

}

The fact that a simple tokenizer can be built with such simple regular expression patterns suggests that tokenizers like the one in Fig. 3.22 can be easily implemented in FSTs. This is indeed the case, and (Karttunen et al., 1996) and (Beesley and Karttunen, 2003) give descriptions of such FST-based tokenizers.