This paper presents a resource-light acquisition of morphological paradigms and lexicon for fusional languages. It builds upon Paramor [10], an unsupervised system, by extending it: (1) to accept a small seed of manually provided word inflections with marked morpheme boundary; (2) to handle basic allomorphic changes acquiring the rules from the seed and/or from previously acquired paradigms. The algorithm has been tested on Czech and Slovene tagged corpora and has shown increased F-measure in comparison with the Paramor baseline.
Morphological analysis is used in many computer
applications ranging from web search to machine translation.
As Hajicˇ [
Modern morphological analysers based on supervised
machine learning and/or hand-written rules achieve very
high accuracy. However, the standard way to create them
for a particular language requires substantial amount of
time, money and linguistic expertise. For example, the
Czech analyzer by [
Various techniques have been suggested to overcome this problem, including unsupervised methods acquiring morphological information from an unannotated corpus. While completely unsupervised systems are scientifically interesting, shedding light on areas such as child language acquisition or general learneability, for many practical applications their precision is still too low. They also completely ignore linguistic knowledge accumulated over several millennia, often failing to discover rules that can be found in basic grammar books.
Lightly-supervised systems aim to improve upon the accuracy of unsupervised system by using a limited amount of resources. One of such systems for fusional languages is described in the paper.
Using a reference grammar, it is relatively easy to
provide information about inflectional endings, possibly
organized into paradigms. In some languages, an analyzer
built on such information would have an acceptable
accuracy (e.g., in English, most words ending in ed are
past/passive verbs, and most words ending in est are superlative
adjectives). However, in many languages, the number of
homonymous endings is simply too high for such system
to be useful. For example, the ending a has about 19
different meanings in Czech [
Thus our goal is to discover inflectional paradigms each with a list of words declining according to it, in other words we discover a list of paradigms and a lexicon. But we do not attempt to assign morphological categories to any of the forms. For example, given an English corpus the program should discover that talk, talks, talking, talked are the forms of the same word, and that work, push, pull, miss,. . . decline according to the same pattern. However, it will not label talked as a past tense and not even as a verb.
This kind of shallow morphological analysis has applications in information retrieval (IR), for example search engines. For the most of the queries, users aren’t interested only in particular word forms they entered but also in their inflected forms. In highly inflectional languages, such as Czech, dealing with morphology in IR is a necessity. Moreover, it can also be used as a basis for a standard morphological analyzer after labeling endings with morphological tags and adding information about closedclass/irregular words.
As the basis of our system, we chose Paramor [
The rest of this paper is organized as follows: First, we discuss related work on unsupervised and semi-supervised learning. Then follows a section about baseline Paramor model. After that, we motivate and describe our extension to it. Finally, we report results of experiments on Czech and Slovene. 2
Perhaps the best known unsupervised morphological
analysers are Goldsmith’s Linguistica [
Goldsmith uses minimum description length
(MDL; [
Unlike Linguistica, Morfessor splits words into
morphemes in a hierarchical fashion. This makes it more
suitable to agglutinative languages, such as Finnish or
Turkish, with a large number of morphemes per word. A
probabilistic model is used to tag each morph as a prefix, suffix
or stem. Kohonen et al. [
The approaches by Yarowsky and Wicentowski [
A system requiring significantly more human
supervision is presented by Oflazer et al. [
Feldman and Hana [
Our approach builds upon Paramor [
Due to data sparsity, not all inflections of a word are found in a corpus. Therefore Paramor does not attempt to reconstruct full paradigms, but instead works with partial paradigms, called schemes. A scheme contains a set of c(andidate)-suffixes and a set of c(andidate)-stems inflecting according to this scheme. The corpus must contain the concatenation of every c-stem with every c-suffix in the same scheme. Thus, a scheme is uniquely defined by its c-suffix set. Several schemes might correspond to a single morphological paradigm, because different stems belonging to the paradigm occur in the corpus in different set of inflections. The algorithm to acquire schemes has several steps: 1. Initialization: It first considers all possible segmentations of forms into candidate stems and endings. 2. Bottom-up Search: It builds schemes by adding endings that share a large number of associated stems. 3. Scheme clustering: Similar schemes (as measured by cosine similarity) are merged. 4. Pruning: Schemes proposing frequent morpheme boundaries not consistent with boundaries proposed by a character entropy measure are discarded.
Paramor works with types and not tokens. Thus it is not using any information about the frequency or context of forms. Below, we describe some of the steps in more detail. 3.1
In this phase, Paramor performs a bottom-up search of the scheme lattice. It starts with schemes containing exactly one c-suffix. For each of them, Paramor ascends the lattice, adding one c-suffix at a time until a stopping criterion is met. C-suffix selected for adding is the one with the biggest c-stem ratio. (Adding a c-suffix to a scheme reduces number of the stems and the suffix reducing it the least is selected. C-stem ratio is ratio between number of stems in the candidate higher-level scheme and the current scheme.) When the highest possible c-stem ratio falls under 0.25, the search stops. It is possible to reach the same scheme from multiple searches. For example, a search starting from the scheme (-s) can continue by adding (-ing) and end by adding (-ed), thus creating a scheme (-s, -ing, -ed). Another search starting from (-ed) can continue by adding (-s) and then by adding (-ing), creating a redundant scheme. Such duplicates are discarded. 3.2
Resulting schemes are then subjected to agglomerative bottom-up clustering to group together schemes which are partially covering the same linguistic paradigm. For example, if the first phase generated schemes (-s, -ing) and (-ing, -ed), the clustering phase should put them in the same scheme cluster. To determine proximity of two scheme clusters, sets of words generated by the clusters are measured by cosine similarity.1 A scheme cluster generates a set of words which is the union of sets generated by the schemes it contains (not a Cartesian product of all stems and suffixes throughout the schemes). In order to be merged, clusters must satisfy some conditions, e.g. for any two suffixes in the cluster, there must be a stem in the cluster which can combine with both of them.
1proximity(X,Y ) = √|X|X∩|Y|Y| | After the clustering phase, there are still too many clusters remaining and pruning is necessary. In the first pruning step, clusters which generate only small number of words are discarded. Then clusters modelling morpheme boundaries inconsistent with letter entropy are dropped. 4 4.1
We have modified the individual steps in Paramor’s pipeline in order to use (1) a manually provided seed of inflected words divided into stems and suffixes; and (2) to take into account basic allomorphy of stems. Figure 1 shows phases of Paramor on the left with dashed boxes representing our alterations.
In the bottom-up search phase and the scheme cluster filtering phase, we use manually provided examples of valid suffixes and their grouping to sub-paradigms to steer Paramor towards creating more adequate schemes and scheme clusters. The data may also contain allomorphic stems, which we use to induce simple stem rewrite rules. Using these rules, some of the allomorphic stems in the corpus can be discovered and used to find more complete schemes.
Note that the Paramor algorithm is based on several heuristics with many parameters whose values were set experimentally. We used the same settings. Moreover, when we applied similar heuristics in our modifications, we used analogical parameter values. 4.2
The manual seed contains a simple list of inflected words with marked morpheme boundary. A simple example in English would be: talk+0, talk+s, talk+ed, talk+ing stop+0, stop+s, stopp+ed, stopp+ing chat+0, chat+s, chatt+ed, chatt+ing
talk, stop/stopp, chat/chatt + 0, s / ed, ing The data are used to enhance Paramor’s accuracy in discovering the correct schemes and scheme clusters in the following way: 1. In the bottom-up search, Paramor starts with singlesuffix schemes. We added a 2-suffix scheme to the starting scheme set for every suffix pair from the manual data belonging to the same inflection. Note that we cannot simply add a scheme containing all the suffixes of the whole paradigm as many of the forms will not be present in the corpus. 2. Scheme clusters containing suffixes similar to some of the manually entered suffix sets are protected from the second phase of the cluster pruning. More precisely, a cluster is protected if at least half of its schemes share at least two suffixes with a particular manual suffix set. 4.3
Many morphemes have several contextually dependent realizations, so-called allomorphs due to phonological/graphemic changes or irregularities. For example, consider the declension of the Czech word matka ‘mother’ in Table 1. It exhibits stem-final consonant change (palatalisation of k to c) triggered by the dative and local singular ending, and epenthesis (insertion of -e-) in the bare stem genitive plural.
Case nom gen dat acc voc loc inst
Singular matk+a matk+y matc+e matk+u matk+o matc+e matk+ou
Plural matk+y matek+0 matk+ám matk+y matk+y matk+ách matk+ami
Paramor ignores allomorphy completely (and so do Linguistica and Morfessor). There are at least two reasons to handle allomorphy. First, linguistically, it makes more sense to analyze winning as win+ing than as winn+ing or win+ning. For many applications, such as information retrieval, it is helpful to know that two morphs are variants of the same morpheme. Second, ignoring allomorphy makes the data appear more complicated and noisier than they actually are. Thus, the process of learning morpheme boundaries or paradigms is harder and less successful.
This latter problem might manifests itself in Paramor’s bottom-up search phase: a linguistically correct suffix triggering a stem change might be discarded, because Paramor would not consider stem allomorphs to be variants of the same stem and c-stem ratio may drop significantly. Further more, incorrect c-suffixes may be selected.
For example, suppose there are 5 English verbs in the corpus: talk, hop, stop, knit, chat, together with their -s (talks, hops, stops, knits, chats) and -ing (talking, hopping, stopping, knitting, chatting) forms. Let’s assume we already have a scheme {0, s} with 5 stems. Unfortunately, a simple ing suffix (without stem-final consonant doubling) combines with one out the 5 stems only, therefore adding ing to the scheme would decrease the number of its stems to 1, leaving only talk in the scheme.
However, for most languages the full specification of
rules constraining allomorphy is not available, or at least
is not precise enough. Therefore, we automatically induce
a limited number of simple rules from the seed examples
and/or from the scheme clusters obtained from the
previous run of algorithm. Such rules both over and
undergenerate, but nevertheless they do improve the accuracy of the
whole system. For languages, where formally specified
allomorphic rules are available, they can be used directly
along the lines of Tepper and Xia [
To obtain a deep stem for a c-stem t, operation of expansion is applied. Expansion works as a breadth-first search using a queue initialised with t and keeping track of the set D of already generated variants. While the queue is not empty, the first member is removed and its variants found by application of all the rules. (Result of applying a rule is non-empty only if the rule is applicable and its right hand side is present in the corpus.) Variants which haven’t been generated so far are added to the back of the queue and to D. When the queue is emptied, D becomes the deep stem associated with t and all other members of D.
Bottom-up search and all the following phases of Paramor algorithm are then using the deep stems instead of the surface ones.
Stem change rule induction from scheme clusters. In addition to deriving allomorphic rules from the manual seed, we also use a heuristic for detecting stem allomorphy in the scheme clusters obtained from the previous run of the algorithm. Stem allomorphy increases the sparsity problem and might prevent Paramor from finding some paradigms. However, if the stem changes are systematic and frequent, Paramor does create the appropriate scheme clusters. However, it considers the changing part of the stem to be a part of suffix.
As an example, consider again the declension of the Czech word matka “mother” in Table 1. Paramor’s scheme cluster with suffixesce, ek, ka, kami, kou, ku, ky, kách, kám has correctly discovered 9 of 10 paradigm’s suffixes,3 but fused together with parts of the stem. Presence of such scheme cluster in the result is a hint that there may be a c/k alteration and epenthesis in the language.
First phase of the algorithm for deciding whether a scheme cluster with a c-suffix set f is interesting in this respect is following: 1. If f contains a c-suffix without a consonant, return false. 2. cc = count of unique initial consonants found in c-suffixes in f . 3. If cc > 2 return false. (Morpheme boundary probably incorrectly shifted to the left.) 4. If cc = 1 and f doesn’t contain any c-suffix starting with a vowel, return false. (No final consonant change, no epenthesis.)
If a scheme cluster passes this test, each of its stems’ subparadigms is examined. Subparadigm for stem s consists of s and fs – all the c-suffixes from f with which s forms 3Except for vocative case singular, which is rarely used. a word in the corpus. For example, let’s have a stem s = mat with fs = {ce, ek, ka, ku, ky}. Now, the morpheme boundary is shifted so that it is immediately to the right from the first consonant of the original c-suffixes. In our example, we get 3 stem variants: matk + a, u, y, matc + e, matek + 0. To reduce falsely detected phonological changes, we check each stem variant’s suffix set whether it contains at least one of the c-suffixes that Paramor has already discovered in other scheme clusters. If the condition holds, rules the with same syntax as the manual data are created. For example, matk / matc / matek + a, u, y / e / 0. All generated rules are gathered in a file and can be used in the same way as the manual seed or just for the induction of phonological rules. 5
We tested our approach on Czech and Slovene lemmatised corpora. For Czech, we used two differently sized subsets of the PDT 1 corpus. The first, marked as cz1, contains 11k types belonging to 6k lemmas. The second, cz2, has 27k types and 13k lemmas and is a superset of cz1. The purpose of having two Czech corpora was to observe the effect of data size on performance of the algorithm. The Slovene corpus si is a subset of the jos100k corpus V2.0 (http://nl.ijs.si/jos/ jos100k-en.html) with 27k types and 15.5k lemmas.
The manual seed consisted of inflections of 18 lemmas for Czech and inflections of 9 lemmas for Slovene. In both cases, examples of nouns, adjectives and verbs were provided. They were obtained from a basic grammar overview. For Czech, we also added information about the only two inflectional prefixes (negative prefix ne and superlative prefix nej). The decision which prefixes to consider inflectional and which not is to a certain degree an arbitrary decision (e.g., it can be argued that ne is a clitic and not a prefix), therefore it makes sense to provide such information manually. (Prefixes were implemented by a special form of stem transformation rules introduced in section 4.3 which create deep stems consisting of a stem with and without given prefix.) 5.1
We evaluated the experiments only on types at least 6 characters long which Paramor uses for learning. That means 8.5k types and 4500 lemmas for cz1, 21k types and 10k lemmas for cz2 and 21k types and 12k lemmas for si.
Since corpora we used do not have morpheme boundaries marked, we could not use the same evaluation method as authors of Paramor and Morfessor – measuring the precision and recall of placing morpheme boundaries. On the other hand, corpora are lemmatised and we can evaluate whether types grouped to paradigms by the algorithm correspond to sets of types belonging to the same lemma.
We use the following terminology in this section: a word group is a set of words returned by our system, a word paradigm is a set of words from the corpus sharing the same lemma. Both word groups and word paradigms are divisions of corpus into disjoint sets of words. An autoseed is a seed generated by the heuristic described in Section 4.3.
Since Paramor only produces schemes and scheme clusters, we need an additional step to obtain word groups. We generated the word groups by bottom-up clustering of words using the paradigm distance which is designed to group together words generated by similar sets of scheme clusters. To compute paradigm distance for two words w1, w2, we find the set of all scheme clusters which generate w1 and compute cosine similarity to the analogical set for w24. In the simplest case, two forms of a lemma will be generated just by one scheme cluster and therefore get distance 1. For a more complicated example, let’s take two Czech words: otrávení “poisoned masc. anim. nom. pl.” and otrávený “poisoned masc. anim. nom. sg.”. The first one was generated by scheme clusters 33 and 41, both with otráv as a stem. The second word was generated by scheme cluster 41 with otráv as a stem and by scheme cluster 45 with otráven as stem. That means that only scheme cluster 41 generates both words and their paradigm distance is √21×2 = 0.5.
Precision and recall of the word groups can be computed in the following way: To compute precision, start with p = 0. For each word group, find a word paradigm with the largest intersection. Add the intersection size to p. Precision = p / total number of words. For computing recall, start with r = 0. For each word paradigm, find a word group with the largest intersection. Add the intersection size to r. Recall = r / total number of words. F1 is the standard balanced F-score. 5.2
Results of the experiments are presented in Tables 2 – 4. We used the following experiment settings: 1. no seed – the baseline, Paramor was run without any seeding 2. man. seed – manual seed was used 3. autoseed – autoseed was used for induction of the stem change rules 4. both seeds – Paramor run with manual seed, stem change rules were induced from manual and autoseed. 5. seed + pref. – manual seed was used together with additional rules for two Czech inflectional prefixes, otherwise same as 2.
4We also have to check whether w1 and w2 have the same stem, so, in fact we are comparing sets of pairs hscheme cluster, c-stemi, to make sure only words sharing c-stems are grouped together. 6. both seeds + pref – manual seed was used together with additional rules for two Czech inflectional prefixes, otherwise same as 4.
Experiment no seed man. seed autoseed both seeds seed + pref. both seeds + pref.
As can be seen from the results, the extra manual information indeed does help the accuracy of clustering words belonging to the same paradigms. What is not shown by the numbers is that more of the morpheme boundaries make linguistic sense because basic stem allomorphy is accounted for. 6
We have shown that providing very little of easily obtainable information can improve the result of a purely unsupervised system. In the near future, we are planning to model a wider range of allomorphic alternations, try larger (but still easy to obtain) seeds and finally test the results on more languages.