ParaMor, our unsupervised morphology induction system performed well at Morpho Challenge 2008. When ParaMor's morphological analyses, which specialize at identifying inflectional morphology, are added to the analyses from the general purpose unsupervised morphology induction system, Morfessor, the combined system identifies the morphemes of all five Challenge languages at recall scores higher than those of any other system which competed in Morpho Challenge. In Turkish, for example, the recall of the ParaMor-Morfessor system, at 52.1%, is twice that of the next highest system that participated. These strong recall scores lead to F1 values for morpheme identification as high as or higher than those of any competing system for all the competition languages but English. Of the three language tracks of the task-based information retrieval (IR) evaluation of Morpho Challenge, the combined ParaMor-Morfessor system placed first at average precision in the English and German tracks. And in the German and Finnish tracks of the IR task, the ParaMor-Morfessor system outperformed the hand-built stemming package, Snowball.
Experimentation
This paper describes the performance of the unsupervised morphology induction algorithm ParaMor in Morpho Challenge 2008. Morpho Challenge is a series of peer-operated competitions for algorithms designed to discover the morphological structure of individual natural languages in an unsupervised fashion. Two major considerations motivate our work on unsupervised morphology induction. First, and primarily, we are interested in developing methods to quickly bring a morphology analysis system online for a new language. Of the nearly 7000 languages in the world, only a few dozen have working computational morphological analysis systems. Unsupervised morphology induction promises to significantly decrease the time and expertise needed to build a morphology system for the many remaining languages. Second, we are interested in this problem from a theoretical standpoint: We would like to know how much of the morphology of a language it is possible to learn from nothing but raw text. Although we do not claim that our unsupervised morphology induction algorithm mimics how a human learns morphology, we hope that our work can place constraints on the range of strategies that humans might use.
A considerable number of researchers have worked on the problem of unsupervised morphology induction.
Here, we summarize and categorize a few approaches that are most related to or that have significantly
influenced our system. The approaches we summarize fall into one or more of four categories. The first category
comprises systems which examine word-internal character transitions for probabilistic evidence of a morpheme
boundary. Probably the first work to look at unsupervised morphology induction,
The fourth and final category of unsupervised morphology induction system discussed here are systems
which purposefully model the paradigmatic structure of morphology. A morphological paradigm is a mutually
substitutable set of morphological operations. In particular, conjugation and declension tables, as commonly
found in language text books, are paradigms. Systems that appeal to the paradigmatic structure of morphology
include
The remainder of this paper is organized as follows: Section 2 provides a brief overview of our unsupervised
morphology induction algorithm, ParaMor, taking particular note of the pieces of the ParaMor algorithm which
have changed since the Morpho Challenge 2007 competition. A more full description of the ParaMor algorithm
has been published in the series of papers
An unsupervised morphology induction algorithm, such as ParaMor, discovers the morphology of a language from nothing more than raw text. The ParaMor algorithm takes as input a text and reduces the text to a list of unique word types. A priori ParaMor does not know where the morpheme boundaries fall in any given surface form, and so ParaMor proposes, for each word, a separate analysis that hypothesizes a morpheme boundary at each character boundary of that word. Whenever two or more corpus types end in the same word-final string, ParaMor constructs a paradigm seed. This paradigm seed contains the word-final string together with all wordinitial strings which allow the word-final string to attach.
The ParaMor algorithm then proceeds in two main stages. In the first stage, ParaMor searches for sets of
word-final strings which likely represent the suffixes of a paradigm. In the second stage, ParaMor segments
word forms exactly where the discovered paradigms suggest a morpheme boundary. The paradigm discovery
stage consists of three steps. The first step is a recall centric search that greedily expands ParaMor’s paradigm
seeds into full candidate paradigms by successively adding additional suffixes. Each of ParaMor’s candidate
paradigms consists of a set of word-final strings, or candidate suffixes, together with all the word-initial strings,
candidate stems, which occurred in separate words with each suffix in the candidate paradigm. The second step
of paradigm discovery is to cluster initially selected candidate paradigms which likely model the same
underlying paradigm of a language. The clustering step merges candidate paradigms which share a large fraction
of their suffixes and stems. The third step in ParaMor’s paradigm discovery phase applies a series of filters to
weed out paradigm candidates which likely do not model true paradigms of a language. The paradigm filters
consider a range of criteria when deciding to keep or discard a candidate paradigm. These criteria include: the
number of suffixes and stems in the candidate, the length of the suffixes and stems in the candidate, and the
character transition probabilities that surround the morpheme boundary that the paradigm candidate
hypothesizes, in the style of
ParaMor’s word-to-morpheme segmentation stage looks for paradigmatic evidence of a morpheme boundary.
Specifically, ParaMor matches each word-final string of each word type against the suffixes in each discovered
paradigm. Whenever a word-final string is identical to a suffix in a discovered paradigm, ParaMor looks for
evidence that the word belongs to that particular paradigm. If a word belongs to a paradigm, then the stem of that
word will likely form valid surface forms with other suffixes from that paradigm. Hence, whenever a word-final
string matches a suffix of a discovered paradigm, ParaMor substitutes, one at a time, the other suffixes of that
discovered paradigm. If at least one of the substituted forms occurred as a word type in the corpus, then ParaMor
segments the original word form at the boundary of the matched word-final string.
Morpho Challenge 2008 is the second Morpho Challenge competition in which ParaMor has taken part. In
Morpho Challenge 2007, ParaMor participated in the English and German competitions. This year, ParaMor
again analyzed English and German morphology, but also participated in the Finnish, Turkish, and Arabic tracks.
Three major additions and adaptations to the ParaMor algorithm made participation in these morphologically
more challenging language tracks practical. These three adaptations are described in detail in
The first adaptation restricts the set of word types which participate in ParaMor’s paradigm discovery phase.
Because, combinatorially, there are fewer possible short strings, words that consist of just a few characters are
more likely to suggest spurious morphological relationships with other short types that occur in any particular
corpus. Hence, the first adaptation excludes short types from the paradigm induction vocabulary. Since the
morphological paradigms that ParaMor seeks to uncover describe large sets of word types, ParaMor can rely on
the remaining longer types to identify paradigms. Other unsupervised morphology induction systems, including
the Linguistica system
The second adaptation borrows ideas originally due to
The final adaptation to the ParaMor system from the 2007 Challenge acknowledges the agglutinative structure of natural language morphology: Many natural languages, including Turkish and Finnish, form surface words from several morphemes in sequence. Any individual candidate paradigm that ParaMor constructs during the paradigm identification phase can propose at most a single morpheme boundary in any particular word. Our third adaptation straightforwardly merges the separate morpheme boundaries that are proposed by distinct candidate paradigms into a single combined morphological segmentation that contains multiple morpheme boundaries.
As described earlier, the unsupervised morphology induction system ParaMor is designed to identify morphological paradigms: sets of mutually substitutable morphological operations. In particular, ParaMor looks for sets of mutually substitutable suffixes. Paradigms are the structure of inflectional morphology. In inflectional morphology any given lexeme adheres to a paradigm forms a separate surface form with each member of the paradigm. But the Morpho Challenge specifically evaluates morphology analysis systems on both inflectional and derivational morphology. Derivational morphology is much more idiosyncratic: any particular stem may or may not form a new word with any particular derivational suffix.
To more practically compete in Morpho Challenge we add to ParaMor’s morphological analyses the
morphological analyses suggested by the unsupervised morphology induction system Morfessor
Morpho Challenge 2008 evaluated unsupervised morphology induction systems in two ways
The linguistic evaluation of Morpho Challenge 2007 used the same evaluation methodology as the 2008 challenge; and moreover, The 2007 challenge scored systems over the same corpora and against the same answer key as the more recent 2008 competition.
Of the six systems which competed in the 2008 challenge that appear in Table 1, three are systems we, Monson et al., submitted, while three are systems submitted by others. The three systems which we entered in Morpho Challenge 2008 are:
The ParaMor algorithm has several free parameters that control the paradigm discovery phase. These parameters were set to values that produced reasonable Spanish paradigms. The parameters were then frozen before running the Morpho Challenge experiments. The six systems in Table 1 which were prepared by others are the systems with the top performance in the linguistic evaluation of Morpho Challenge 2007/2008. The system labeled Morfessor MAP is the same Morfessor algorithm as the Morfessor system which we submitted but with a different parameter setting. A change in parameter setting can sometimes result in quite different performance for Morfessor, c.f. Finnish. The remaining five systems found in Table 1 bear the names of their principle authors.
Although ParaMor alone performs respectably, it is when ParaMor’s analyses are combined with Morfessor’s that ParaMor shines. In all languages but English, the combined ParaMor-Morfessor system achieves the highest F1 of any system which competed in the 2007 or 2008 Challenges. In general, the ParaMor-Morfessor system attains this higher F1 by balancing precision and recall. Where the other unsupervised morphology induction systems of Table 1 tend to be cautious, only proposing morphemes when they have high confidence, the ParaMor-Morfessor system is more willing to guess at morphemes which may be incorrect. The more cautious high-confidence strategy results in higher precision but lower recall. In contrast ParaMor’s strategy lowers precision but increases recall, balancing the two, and, overall, raising F1.
The language ParaMor performs most poorly at is Arabic. New to Morpho Challenge in 2008, Arabic’s morphology is distinctly different from that of the other four languages in the challenge. Arabic morphology differs most notably in possessing templatic morphology, where a consonantal root is interleaved with vowels to produce specific surface forms. Equally important, from ParaMor’s perspective, is that Arabic is the only language in Morpho Challenge with significant prefixation. Arabic verbal morphology includes inflectional prefixes. In addition, Arabic orthography attaches a number of common determiners and prepositions directly onto the written form of the following word. These attached function words act as prepositions in text. In general, all the systems which competed in Arabic identified less than a third of the morphemes of Arabic. In particular, as ParaMor is limited to looking for suffixes, both the templatic morphology and the prefixational morphology lower ParaMor’s morpheme recall. In the near term, since prefixes are the mirror image of suffixes, a simple augmentation could allow ParaMor to analyze prefixation. The ability to identify prefixes would not only improve morpheme recall in Arabic, but help identify German verbal prefixes, and English derivational prefixes as well. Interestingly, when ParaMor’s Arabic analyses are presented in combination with Morfessor’s the increase in recall between the two systems is practically additive: implying very little overlap between the morphemes which the two systems identify. When recall scores are depressed across the board, any increase in recall implies an increase in F1. And indeed, the ParaMor-Morfessor system receives the highest F1 of any system which analyzed Arabic morphology.
Tables 2 and 3 contain the results of the task-based information retrieval evaluation of Morpho Challenge 2008. The IR evaluation only covered three languages: English, German, and Finnish. These same three IR tracks also appeared in Morpho Challenge 2007 with the same evaluation set as for the 2008 challenge, making results from both years comparable. Table 2 contains the average precision IR scores for the eight best performing systems from the 2007 and 2008 challenges; while Table 3 contains average precision scores for four baseline metrics used in Morpho Challenge 2008, namely: 1. 2. 3.
Snowball (Porter) - where all words in each document and query are stemmed using the Snowball package of language stemmers. In the case of English, the Snowball stemmer is the Porter stemmer; Answer Key - where document and query words are replaced with their morphological analyses from the answer keys that were used in the linguistic evaluation of Morpho Challenge. The answer keys used in the linguistic evaluations contain only a subset of full set of types found in the IR evaluation; and Two-Level - where all words are replaced with the morphological analysis provided by a hand-built rulebased morphological analysis system. No hand-built morphological analysis system was evaluated for German.
In the IR evaluation of Morpho Challenge 2008 the combined ParaMor-Morfessor system placed first in English and German, and fourth in Finnish. The IR evaluation is a black-box experiment, and so it is not completely clear why the ParaMor-Morfessor system fared worse in the Finnish track. The most likely explanation is that replacing each word in each document and query with both the ParaMor and the Morfessor analyses is inappropriate for a language with complex morphology such as Finnish. It is unfortunate that Morpho Challenge did not evaluate an IR experiment for the morphologically complex Turkish and Arabic. It would be particularly interesting to see ParaMor’s IR performance on Turkish, which, like Finnish, is agglutinative.
In comparison to the baseline algorithms of Table 3, all the unsupervised morphology induction systems of Table 2, including the two systems which incorporate ParaMor, perform well. Most notably, in all languages, all 2008 2007
Finnish 39.9 47.3 of the unsupervised morphology induction systems of Table 2 improve on the average precision scores when no morphological analysis is performed. The best performing unsupervised systems, including ParaMor, also outperform the baseline Answer Key scenario: demonstrating that imperfect morphological analysis can trump partial analysis. ParaMor and the other unsupervised system face stiffer competition in the two hand-built morphological baselines that have some generalization capacity, Snowball (Porter) and Two-Level. The Porter stemmer has the best average precision of any method against English; but unsupervised systems, ParaMor among them, outperform the Snowball rule-based stemmers for both German and Finnish. And finally, the handbuilt two-level morphological analyzer performs best of any method on Finnish; and nearly as good as the best unsupervised system on English. 4
The premise that the paradigmatic structure of morphology can be leveraged toward unsupervised morphology induction is clearly justified by the state-of-the-art performance of the ParaMor algorithm in Morpho Challenge 2008. In addition, the improved performance that results from joining the morphological analyses of the ParaMor and Morfessor systems demonstrates that current unsupervised morphology algorithms are highly complementary, and have much to gain from uniting their unique strengths.
While we are pleased with ParaMor’s performance in Morpho Challenge 2008, we also see significant room
for improvement on ParaMor’s morphology induction algorithms. A careful examination of the paradigms which
ParaMor produces over Spanish data identifies two major error classes. The first class of erroneous candidate
paradigm results from inadequate clustering of initially selected candidate paradigms. We would like to more
tightly integrate the search and clustering phases of ParaMor to enable more complete clustering of the initially
selected partial paradigms. The second major class of erroneous paradigm is a consequence of
morphophonology. Specifically, a stem or a suffix may appear in different surface forms conditioned on the
morphemes with which it occurs. To conflate the varied surface forms of a single underlying morpheme we
believe we will need to look at evidence outside the word as
The research described in this paper was supported by NSF grants IIS-0121631 (AVENUE) and IIS-0534217 (LETRAS), with supplemental funding from NSF’s Office of Polar Programs and Office of International Science and Education.