11.5.2 Learning Morphology

We discussed in Ch. 3 the use of finite-state transducers for morphological parsing. In general, these morphological parsers are built by hand and have relatively high accuracy, although there has also been some work on supervised machine learning of morphological parsers (van den Bosch, 1997). Recent work, however, has focused on unsupervised ways to automatically bootstrap morphological structure. The unsupervised (or weakly supervised) learning problem has practical applications, since there are many languages for which a hand-built morphological parser, or a morphological segmented training corpus, does not yet exist. In addition, the learnability of linguistic structure is a much-discussed scientific topic in linguistics; unsupervised morphological learning may help us understand what makes language learning possible.

Approaches to unsupervised morphology induction have employed a wide variety of heuristics or cues to a proper morphological parse. Early approaches were all essentially segmentation-based; given a corpus of words they attempted to segment each word into a stem and an affix using various unsupervised heuristics. For example the earliest work hypothesized morpheme boundaries at the point in a word where there is large uncertainty about the following letters (Harris, 1954, 1988; Hafer and Weiss, 1974). For example, Fig. 11.17 shows a $ \text{trie}^{9} $ which stores the words car, care, cars, cares, cared, etc. Note that there are certain nodes in the tree in Fig. 11.17 that have a wide branching factor (after car and after care). If we think of the task of predicting the next letter giving the path in the tree so far, we can say that these points have

a high conditional entropy; there are many possible continuations. $ ^{10} $ While this is a useful heuristic, it is not sufficient; in this example we would need a way to rule out the morpheme car as well as care being part of the word careful; this requires a complex set of thresholds.

Another class of segmentation-based approaches to morphology induction focuses on globally optimizing a single criterion for the whole grammar, the criterion of minimum description length, or MDL. The MDL principle is widely used in language learning, and we will see it again in grammar induction in Ch. 14. The idea is that we are trying to learn the optimal probabilistic model of some data. Given any proposed model, we can assign a likelihood to the entire data set. We can also use the proposed model to assign a compressed length to this data (with probabilistic models we can use the intuition that the compressed length of the data is related to the entropy, which we can estimate from the log probability). We can also assign a length to the proposed model itself. The MDL principle says to choose the model for which the sum of the data length and the model length is the smallest. The principle is often viewed from a Bayesian perspective; if we are attempting to learn the best model $ \hat{M} $ out of all models M for some data D which has the maximum a posteriori probability $ P(M|D) $, we can use Bayes Rule to express the best model $ \hat{M} $ as:

$$ \hat{M}=argmax_{M}P(M|D)=argmax_{M}\frac{P(D|M)P(M)}{P(D)}=argmax_{M}P(D|M)P(M) $$

Thus the best model is the one which maximizes two terms: the likelihood of the data $ P(D|M) $ and the prior of the model $ P(M) $. The MDL principle can be viewed as saying that the prior term on the model should be related to the length of the model.

MDL approaches to segmentation induction were first proposed by de Marcken (1996) and Brent (1999), as well as Kazakov (1997); let's summarize from a more recent instantiation by Goldsmith (2001). The MDL intuition can be seen from the schematic example in Fig. 11.18 inspired by Goldsmith.

As we see in Fig. 11.18, using morphological structure makes it possible to represent a lexicon with far fewer letters. Of course this example doesn't represent the true complexity of morphological representations, since in reality not every word is combinable with every affix. One way to represent slightly more complexity is to use signatures. A signature is a list of suffixes that can appear with a particular stem. Here are some sample signatures from Goldsmith (2001):

The Goldsmith (2001) version of MDL considers all possible segmentations of every word into a stem and a suffix. It then chooses the set of segmentations for the whole corpus that jointly minimize the compressed length of the corpus and the length of the model. The length of the model is the sum of the lengths of the affixes, the stems, and the signatures. The length of the corpus is computed by using the model to assign a probability to the corpus and using this probably to compute the cross-entropy of the corpus given the model.

While approaches based solely on stem and affix statistics like MDL have been quite successful in morphological learning, they do have a number of limitations. For example Schone and Jurafsky (2000, 2001) noted in an error analysis that MDL sometimes segments valid affixes inappropriately (such as segmenting the word ally to all+y), or fails to segment valid but non-productive affixes (missing the relationship between dirt and dirty). They argued that such problems stemmed from a lack of semantic or syntactic knowledge, and showed how to use relatively simple semantic features to address them. The Schone and Jurafsky (2000) algorithm uses a trie to come up with “pairs of potential morphological variants”, (PPMVs) words which differ only in potential affixes. For each pair, they compute the semantic similarity between the words, using the Latent Semantic Analysis (LSA) algorithm of Ch. 23. LSA is an unsupervised model of word similarity which is induced directly from the distributions of word in context. Schone and Jurafsky (2000) showed that using the semantic similarity alone was at least as good a predictor of morphological structure as MDL. The table below shows the LSA-based similarity between PPMVs; in this example the similarity is high only for words that are morphologically related.

Schone and Jurafsky (2001) extended the algorithm to learn prefixes and circum-fixes, and incorporated other useful features, including syntactic and other effects of neighboring word context (Jacquemin, 1997), and the Levenshtein distance between the PPMVs (Gaussier, 1999).

The algorithms we have mentioned so far have focused on the problem of learning regular morphology. Yarowsky and Wicentowski (2000) focused on the more complex problem of learning irregular morphology. Their idea was to probabilistically align an inflected form (such as English took or Spanish juegan) with each potential stem (such as English take or Spanish jugar). The result of their alignment-based algorithm was a inflection-root mapping, with both an optional stem change and a suffix, as shown in the following table:

| English | Spanish | | | | | | |

| --- | --- | --- | --- | --- | --- | --- | --- |

| root | inflection | stem change | suffix | root | inflection | stem change | suffix |

| take | took | ake $ \rightarrow $ook | + \epsilon | jugar | juega | gar $ \rightarrow $eg | +a |

| take | taking | e $ \rightarrow $ \epsilon | +ing | jugar | jugamos | ar $ \rightarrow $ \epsilon | +amos |

| skip | skipped | \epsilon $ \rightarrow $p | +ed | tener | tienen | ener $ \rightarrow $ien | +en |

The Yarowsky and Wicentowski (2000) algorithm requires somewhat more information than the algorithms for inducing regular morphology. In particular it assumes knowledge of the regular inflectional affixes of the language and a list of open class stems; both are things that might be induced by the MDL or other algorithms mentioned above. Given an inflected form, the Yarowsky and Wicentowski (2000) algorithm uses various knowledge sources to weight the potential stem, including the relative frequency of the inflected form and potential stem, the similarity in lexical context, and the Levenshtein distance between them.