We describe Allomorfessor, which extends the unsupervised morpheme segmentation method Morfessor to account for the linguistic phenomenon of allomorphy, where one morpheme has several different surface forms. The method discovers common base forms for allomorphs from an unannotated corpus by finding small modifications, called mutations, for them. Using Maximum a Posteriori estimation, the model is able to decide the amount and types of the mutations needed for the particular language. The method is evaluated in Morpho Challenge 2009.
Morphological analysis is crucial to many modern natural language processing applications, especially when dealing with morphologically rich languages. The enormous number of inflected word forms may lead to severe problems with data sparsity and computational efficiency. There are several successful methods for unsupervised segmentation of word forms into smaller, morpheme-like units (see, e.g., [7, 4, 2]). However, the phenomenon of allomorphy limits the quality of morpheme analysis achievable by segmentation alone. Allomorphy is defined in linguistics as when an underlying morpheme-level unit has two or more morph-level surface realizations which only occur in a complementary distribution: only one of the different allomorphs of a given morpheme appear may appear in a certain morpho- and phonotactical context. For example, in Finnish, the singular genitive case is marked with a suffix n, e.g. auto (car) – auton (car’s). Many Finnish nouns undergo a stem change when producing the genitive: kenk¨a (shoe) – keng¨an (shoe’s), pappi (priest) – papin (priest’s), tapa (habit) – tavan (habit’s). A segmentation based approach models changed stems as distinct morphemes.
In Morpho Challenge 2008, we introduced an unsupervised model for morpheme segmentation and allomorphy learning [10]. In [11], some modifications to the model (now referred to as Allomorfessor Alpha) were suggested. In this paper we describe and evaluate the modified Allomorfessor model (referred to as Allomorfessor Baseline). As indicated by the name, the model is an extension to the Morfessor Baseline model by Creutz and Lagus [3].
There are two main problems in literature on the unsupervised learning of allomorphy: finding morphologically related words (e.g. [13, 1]), and learning a morphological analyzer (e.g. [14, 5]). We try to solve the latter, which is more complex and general—as morphologically related words can be determined from the analyses. In contrast to the work by Yarowsky and Wicentowski [14], the framework based on Morfessor allows concatenative morphology, rather than only stemsuffix pairs. In the work by Dasgupta and Ng [5], concatenative morphology is allowed to some extent, but the approach is not as general and cannot find, e.g., suffixes between stems. Another difference is related to what information sources are used for finding the allomorphs. In addition to the orthographic similarity, word frequencies [14] and word contexts [13, 1] have been applied. We currently use only orthographic similarity.
This paper proceeds as follows: Section 2 presents the framework of the model and the learning task, both based on Morfessor. Section 3 describes how Allomorfessor models allomorphy by including new operations, mutations, to the model. Section 4 defines the model probabilities needed by the Maximum a Posteriori estimation. Section 5 describes the applied learning algorithm for the model, and Section 6 how the model can be used to analyze new words. Section 7 includes the initial results for the Morpho Challenge 2009. Finally, Section 8 concludes the paper. 2
(
MMAP = arg max P (M|corpus) = arg max P (M)P (corpus|M)
M M P (M) is the Bayesian prior probability for the model and P (corpus|M) is the likelihood of the training corpus. Compared to Maximum Likelihood estimation, MAP provides a systematic way of balancing the model complexity and accuracy, and thus helps with the problem of overlearning (see, e.g., Chapter 3 in [6]). This MAP formulation can alternatively be formulated using a two-part coding approach of the Minimum Description Length (MDL) principle.
Modeling a corpus with a morphological model is not straightforward. For example, the occurrences of the words in a corpus follow power law distributions (Zipf’s law), any realistic model should abide by that phenomenon. Instead of using an explicit model for the corpus, as in, e.g., [8], we separate word-level model MW and morpheme-level model MM , and estimate only the latter. Word-level model is assumed to be a constant given a word lexicon LW , which contains all the word forms in the corpus. In addition, we divide MM into two parts: morpheme lexicon LM and morpheme grammar GM . The former models word-internal syntax and the latter provides the morphemes that from which the words are constructed. The optimization task is thus: MMAP = arg max P (LW |GM , LM )P (GM )P (LM ).
GM ,LM This is equivalent to the approach used in Morfessor [4], but instead of modeling the original corpus, we are now modeling a lexicon of the words in the corpus.1 3
Our morpheme-level model is Morfessor Baseline extended with operations that can make minor modifications to the surface forms of the morphemes. These operations are called mutations.
1This has been recommended to be done also with Morfessor by setting all the word counts to one. Otherwise, frequent word forms are often undersegmented.
In many cases, the mutations are empty, i.e., they do not affect the surface form. If all of the mutations are empty, the model is equivalent to Morfessor Baseline.
When designing the mutation model for allomorphy we strive to: (
To calculate the smallest mutation of this kind between two arbitrary strings we apply the dynamic programming based algorithm for minimum edit distance (see, e.g., [12]), which can be modified to return also the edit operations needed. We want the optimal sequence of operations not containing insertions, so we set the cost of insertions to be larger than what the other operations may yield for the given string lengths. In this way, we can always find sequences of operations not containing insertions, if such sequences exist, by discarding candidates with too high costs. It is trivial to transform the edit operations into the Allomorfessor mutation format.
To verify the suitability of the approach, we examined how well this kind of mutations are able to find the allomorphic variations in linguistic gold standard segmentations. The tests were performed on English, Finnish and Turkish, based on the gold standards used in Morpho Challenge.2 Statistics were calculated separately for a word lexicon and for a corpus, where the common words had more weight. The results are in Table 2. The first column shows the number of morphs in the data. The second column shows how many of the morphs have allomorphs. The third column shows how many of the allomorphs can be constructed with mutations. We applied similar restrictions to those that were in our model; in practice, variations in affixes and other short morphemes were excluded from the search. Mutations provide reasonable good coverage for English and Finnish. E.g., for English, we can find at most 82% of the real allomorphs in the gold standard segmentation. The percentages for the corpora are lower, as affixes are more common than stems. For Turkish, where most of the allomorphy seems to be in affixes or other short morphemes, only 2% of the cases with allomorphic variants in a corpus can be found using mutations. 4
Next, we give a formal description of the probabilities in Equation 2 for the Allomorfessor Baseline model. Again, the formulation follows the work by Creutz and Lagus [4], especially the Morfessor Baseline model.
2See http://www.cis.hut.fi/morphochallenge2009/datasets.shtml.
First, every word form wj in the word lexicon is represented by a sequence of morphs μjk and mutations δjk
MW nj P (LW |GM , LM ) = Y Y P (μjk)P (δjk|μjk),
j=1 k=1 where nj is the number of morphs in word j. The probabilities of the morphs and the (conditional) probabilities of the mutations are estimated from the observed frequencies. I.e., if there is 10000 morph tokens in the word lexicon, and μjk occurs 200 times, its probablity will be P (μjk) = 200/10000 = 0.02.
The probability of the morph lexicon LM is based on the properties of the morphs: P (LM ) = P (size(LM ) = M )P (properties(μ1) . . . properties(μM ))M ! (4) If a non-informative prior is used for the probability of the lexicon size M , its effect is minimal and it can be neglected. The factor M ! is explained by the fact that there are M ! possible orderings of M items, and the lexicon is the same regardless of the order in which the morphs are discovered.
The properties of the morphs are divided into two parts, usage and form. The usage includes
properties of the morph itself and the properties of its context. Here we include only the frequency
distribution of the morphs. For the probability of the distribution, we use a non-informative,
implicit frequency prior
len(μi)
P (form(μi)) = P (len(μi)) Y P (cij),
j=1
(
The form of a morph is its representation in the model. Forms of the morphs are assumed to be independent. They are represented by a string of characters cij: where cij is the jth character of the morph. The lengths of the morphs are modeled explicitly using an appropriate probability distribution, such as an exponential (geometric) or a gamma distribution.
Grammar GM of the model contains the set of mutations Δ. Similarly to the lexicons,
P (GM ) = P (size(Δ) = Mδ)P (properties(δ1) . . . properties(δMδ ))Mδ!, and properties can be divided into usage and form. Usage features include the frequencies of the mutations and their co-occurrences with the suffix morphs (needed in Equation 3). We apply a condition that each morph has to have at least one co-occurrence with an empty mutation ǫ. In consequence, the count of the empty mutation nǫ is at most N (number of morph tokens) and at least M (number of morph types). Applying the the uniform distribution,
P (freq(ǫ)) =
The other Mδ − 1 mutation types have N − nǫ occurrences in total, as there are as many mutation tokens as there are morph tokens in the data. We apply the same non-informative prior as in Equation 5. Finally, we determine the probability of the co-occurrences of mutations and suffix morphs. For each non-empty mutation δ we divide its occurrences with the M possible morphs. There are freq(δ)+M−1 possibilities, so a non-informative prior for the co-occurrences is
M−1 Note that after the others are determined, the co-occurrences with the empty mutation are: P (co-freqs(Δ, LM )) =
Y 1/ δ∈Δ\ǫ freq(δ) + M − 1
M − 1 For the weights we use P (del) = P (sub) = 0.5, Σ is the alphabet size, and kij tells which instance of the target letter of the operation opij is matched. P (len(δi)) and P (kij ) can be taken from any suitable prior distribution. 5
The model is learned by iteratively improving the model posterior P (M|corpus), processing one
word at a time and selecting the analysis of that word that maximizes the probability, as shown
in Algorithm 1. In the algorithm, Aw is a list and we use + to denote the append operation. The
algorithm considers analyzing the word w (
Since each word has 2(len(w)−1) possible analyses without considering mutations, we search greedily for the best split at any time, reducing the search space to O(len(w)2). When considering mutations, any word w could potentially be the base form for any other word w∗. Thus, a naive algorithm would have time complexity O(N 2), which is unfeasible for large datasets. Therefore, we constrain the candidates in heuristic ways, such as limiting the number of analyses to K per morph and iteration, as can be seen in Algorithm 2. Since finding the baseforms can be done as a range search, it requires O(K log(N )) time, and thus the time complexity for the whole learning algorithm is O(N K log(N )).
while P (M | corpus) increases do
for w ∈ LW in random order do optimize(w,len(w)) end while function optimize(w,n)
Aw ← w + (w1..i, w(i+1)..n) : i ∈ 1, ..., n − 1 + mutated analyses(w, n) Apply the analysis a∗w of the first K elements of Aw that maximizes P (M | corpus) if a∗w involved a split then optimize(w1..i, i); optimize(w(i+1)..n, n − i)
for i ∈ 1, ..., n − 1 do if n >= 4 ∧ len(w(i+1)..n) <= 5 ∧ w(i+1)..n ∈ LM then if n > 6 then difflen ← 4 else difflen ← 3 baseforms ← {v ∈ LW : v1..(n−difflen) = w1..(n−difflen)} Calculate mutations δj between each baseformsj and w(i+1)..n Aw ← Aw + (vj , w(i+1)..n, δj ) : vj ∈ baseforms end if end for return Aw sorted by i and descending len(vj ) 6
After the model has been trained, it can be used to analyze words with a variant of the Viterbi algorithm, which is a dynamic programming algorithm that finds the most probable state sequences for Hidden Markov models [9]. In our case, the observation is the sequence of |W | letters that form the word w, and the hidden states are the morphemes of the word. We need a grid s of length |W | to fill with the best probability values α(si) and paths. Without mutations, the model is 0th order Markov model, and the grid is a one dimensional table. The grid position si indicates that the first i letters are observed. At each time step, we proceed with one letter and insert the probability α(si) = maxj α(sj )P (μji) and path indicator ψ(si) = arg maxj α(sj )P (μji) to the grid. We can come to si from any of the positions sj between s1 and si−1: the letters between j and i form the next morpheme μij . The time complexity is of the algorithm is thus O(|W |2).
The mutations make things a bit more complicated. As they are conditioned on the suffixes, it is easier to run the algorithm from right to left. The grid has to be two dimensional: for each si there can be several states (morphemes) with their own costs and paths. The rule for updating the grid value for si is α(si, μˆij ) =
max max j∈[i+1,|W |] μ∈sj max α(sj , μ)P (δ|μ)P (μˆij ) δ∈Δ (13) where μˆij is a morpheme that produces the letters between i and j when modified by the mutation δ. Only those mutations that are observed before μ need to be tested, otherwise P (δ|μ) = 0. For the morphemes that are not observed before, we use an approximate cost of adding them into the lexicon. The worst case time complexity for the algorithm is O(M Mδ|W |2). In practice, however, the number of morphemes and mutations tested in each position is quite limited. 7
For Morpho Challenge 2009 Competitions 1 and 2 we trained the model with the Competition 1 data, where all words occurring only once were filtered out3, with the exception of Arabic data sets, where the number of words was very low to start with. After training the model, we analyzed all the words in both data sets with the Viterbi algorithm (Section 6). For Competition 3, we used the Europarl data set for training, without any filtering. After training the model, the final analysis was calculated with the Viterbi algorithm. The following parameter settings were used: Morpheme length distribution in Equation 6 was geometric with parameter p = MW /(MW + Mc), where MW is the number of words and Mc the number of characters in the training corpus. The number of candidates considered for each virtual morph was K = 20. For the mutation lengths and kij in Equation 11, we used gamma distribution with scale and shape parameters equal to one, preferring short mutations.
In Table 3, the performance of the Allomorfessor Baseline (the current algorithm) is compared to Allomorfessor Alpha (the algorithm presented in Challenge 2008 [10]) and Morfessor Baseline 3The are plenty of “rubbish”, such as misspelled words and foreign names, in the least frequent words. [3] in the Competition 1 of Morpho Challenge. The improvement over the previous algorithm is remarkable. As indicated by the improved recall measures, the algorithm no longer undersegments. This can also be seen in Figure 1, where the average number of morphemes per word form is shown for the three algorithms.
Compared to Morfessor, the results are roughly at the same level. For English, Allomorfessor has both higher recall and higher precision. For all the other tasks, one is higher and the other is lower. Note that whenever the recall is higher, also the F-measure is higher, as improving the lower measure (in this case, recall) has more effect on the geometric mean of the measures. Figure 1 shows that on average, Morfessor always segments word forms to smaller parts. This usually leads to a higher recall. However, for English, Allomorfessor obtains higher recall while segmenting less than Morfessor, which implies that the majority of the common base forms extracted by Allomorfessor are correct. Also, Allomorfessor achieved the winning F-measure for English in Morpho Challenge 2009.
In Competition 2, the algorithms were applied in an information retrieval system for English, Finnish and German. The results for Allomorfessor and Morfessor Baseline, shown in Table 4, are roughly on the same level. Notably, Allomorfessor is better for Finnish and Morfessor for English in contrast to Competition 1; rigorous error analysis would be needed to find an explanation. Overall, Allomorfessor performed reasonably well in this task, being second in English and Finnish and third in German.
The number of non-empty mutations found by the algorithm (in the final analysis of all the word forms) is shown in Table 5. Generally, mutations are not used as much as linguistic analysis would prefer. One reason is that the model seems to favor storing frequent morphs directly, instead of deriving them using mutations. The method finds, e.g., the morph pretti instead of deriving it as pretty (y|i). Therefore mutations are mostly used for morphs that occur only in few different word forms. When comparing languages, the most striking figures are in the Arabic sets: If the vowels are excluded (as usual in Arabic script), the model finds no useful mutations. However, when the vowels are in the text, the model finds 70 mutations, more than for any other tested 4 3 2 1 language. This nicely demonstrates the method’s ability to adapt to the particular languages and data sets. The fact that Arabic morphology is not concatenative, and thus does not fit well into the Morfessor framework, emphasizes the flexibility of the model.
In Table 6, the mutations found by the algorithm are shown for English and Finnish. As
can be seen, a large part of the mutations correspond to linguistic analysis. The most common
error, especially for Finnish, is having a derived form as the base form. This is because an
unsupervised algorithm has trouble finding the correct base form. However, if the analysed morph
is semantically related to the induced base form, such analyses can be useful in applications. Other
errors include not finding the correct suffix, using a more complex mutation and suffix combination
than necessary, and using a semantically unrelated base form. Mutations are also used commonly
on misspelled word forms.
We have described the Allomorfessor Baseline method for unsupervised morphological analysis.
It attempts to find the morphemes of the input data by segmenting the words into morphs and
finding modifications that can restore allomorphic variations in stems back to their base forms. In
the Morpho Challenge 2009 evaluations, significant improvements were obtained over the previous
version of the method. The results are now close to those of the Morfessor Baseline method. In
comparison to the methods by the other participants, Allomorfessor performed especially well in
the linguistic evaluation for English (the best result in the task), and in the information retrieval
evaluation for English (second), Finnish (second) and German (third).
[4] Mathias Creutz and Krista Lagus. Unsupervised models for morpheme segmentation and
morphology learning. ACM Transactions on Speech and Language Processing, 4(