The goal of Morpho Challenge 2008 was to find and evaluate unsupervised algorithms that provide morpheme analyses for words in different languages. Especially in morphologically complex languages, such as Finnish, Turkish and Arabic, morpheme analysis is important for lexical modeling of words in speech recognition, information retrieval and machine translation. The evaluation in Morpho Challenge competitions consisted of both a linguistic and an application oriented performance analysis. This paper describes an evaluation where the competition entries were compared to a linguistic morpheme analysis gold standard. Because the morpheme labels in an unsupervised analysis can be arbitrary, the evaluation is based on matching the morpheme-sharing words between the proposed and the gold standard analyses. In addition to Finnish, Turkish, German and English evaluations performed in Morpho Challenge 2007, the competition this year had an additional evaluation in Arabic. The results in 2008 show that although the level of precision and recall varies substantially between the tasks in different languages, the best methods seem to manage all the tested languages quite well. The Morpho Challenge was part of the EU Network of Excellence PASCAL Challenge Program and organized in collaboration with CLEF.
The topic of the Morpho Challenge 2008 competition is to evaluate proposed unsupervised
machine learning algorithms in the task of morpheme analysis for words in different languages. The
Morpho Challenge evaluation consisted of both a linguistic and an application oriented
performance analysis. The linguistic evaluation described in this paper, Competition 1, is based on a
comparison of the suggested morpheme analysis to a linguistic morpheme analysis gold standard.
The practical application oriented evaluation described in the companion paper [
The Morpho Challenge 2008 tasks and training corpora were the same as in our previous
Morpho Challenge 2007 [
Especially in morphologically complex languages, such as Finnish, Turkish and Arabic, the
morpheme analysis is important for lexical modeling of words in speech recognition [
The scientific objectives of the Morpho Challenge competitions are: to learn about the word construction in natural languages, to advance machine learning methodology, and to discover approaches that are suitable for many languages. The portability to different languages is very important, because the language technology often needs to be quickly extended to various new languages for which there are limited amount of resources available. Unsupervised learning is then the most attractive approach for data analysis, because the majority of the available data is unannotated and human annotation work is expensive. 2
The task in the Morpho Challenge 2008 was to return the given list of words in each language extended by the morpheme analysis of each word form. The morpheme analyses should be obtained by an unsupervised learning algorithm that would preferably be as language independent as possible. In each language, the participants were pointed to a training corpus in which all the words occur (in a sentence), so that the algorithms may also utilize information about the word context. The tasks were the same as in the Morpho Challenge 2007 last year with the addition of one new language, Arabic.
The training corpora were the same as in the Morpho Challenge 2007, except for Arabic: 3 million sentences for English, Finnish and German, and 1 million sentences for Turkish in plain unannotated text files that were all downloadable from the Wortschatz collection1 at the University of Leipzig (Germany). The corpora were specially preprocessed for the Morpho Challenge (tokenized, lower-cased, some conversion of character encodings).
The Arabic text data (135K sentences with 3.9M words) is the same as used by Habash and
Sadat [
The exact syntax of the word lists and the required output lists with the suggested morpheme
analyses were explained previously in [
In Competition 1 the proposed unsupervised morpheme analyses were compared to the correct grammatical morpheme analyses called here the linguistic gold standard. The gold standard morpheme analyses were prepared in exactly the same format as the result file the participants were asked to submit, alternative analyses separated by commas. See Table 1 for examples.
The gold standard reference analyses were the same as in the Morpho Challenge 2007 [
In the word lists described in the previous section, the gold standard analyses were available for 650,169 (Finnish), 214,818 (Turkish), 125,641 (German), 63,225 (English), and 141,876 (Arabic) word types. 3.2
As baseline results for unsupervised morpheme analysis, the organizers provided morpheme
analysis by a publicly available unsupervised algorithm called “Morfessor Categories-MAP” developed
at Helsinki University of Technology [
By the submission DL at the end of June, 2008, four research groups had submitted nine different algorithms which were then evaluated by the organizers. After the DL, more submissions were received from another author (Goodman), which were evaluated separately outside the Competition 1. One group (Can) decided not to submit the final wordlists that could be evaluated and one (McNamee) wanted only to participate in Competition 2. Thus, the final amount of evaluated algorithms was nine: six in Competition 1, one outside the competition, and two reference results by Morfessor. The algorithm submissions and their authors are listed in Table 2.
Some characteristics of morpheme analyses proposed by the unsupervised algorithms together with the gold standard analyses are briefly presented in Tables 3 and 4. The statistics of each submission include the average amount of alternative analyses per word, the average amount of morphemes per analysis, and the total amount of morpheme types. The “Allomorfessor” is an extension to the “Morfessor Baseline” that attempts to discover common baseforms for the different surface forms that are likely to represent the same morpheme. The “ParaMor” is another algorithm for segmenting words into morphemes which, after improvements from the previous Morpho Challenge, was submitted also as a combination with the publicly available “Morfessor CATMAP”. The “Zeman 1” is a resubmission from the previous Morpho Challenge which, after attempts to include a new treatment of prefix, was submitted as the “Zeman 3”. It is interesting to note that this year all the algorithms resulted in a very large lexicon, usually much larger than the reference methods did. 5
The evaluation of Competition 1 in Morpho Challenge 2008 was similar as in Morpho Challenge
2007 except that there was one new language, Arabic. The full description of the method to
compare the submitted unsupervised morpheme analyses were to the linguistic gold standard
analyses is in [
Because the morpheme analysis candidates are achieved by unsupervised learning, the morpheme labels can be arbitrary and different from the ones designed by linguists. The basis of the evaluation is, thus, to compare whether any two word forms that contain the same morpheme according to the participants’ algorithm also has a morpheme in common according to the gold standard and vice versa. In practice, the evaluation is performed by randomly sampling a large number of morpheme sharing word pairs from the compared analyses. Then the precision is calculated as the proportion of morpheme sharing word pairs in the participant’s sample that really has
Example word: popUlerliGini #a popUler liGini 1 popUlerl +i +G +in +i 1 pop/STM +U/SUF +ler/SUF +liGini/SUF 1 pop/STM +U/SUF +ler/SUF +liGini/SUF, popUlerl +i +G +in +i 2 popUlerliGin i, popUlerliGi ni 3.24 popU lerliGi ni, popU lerliGin i, popU lerliGini, popUlerliGi ni, popUlerliGin i 1.14 popUler liGini 1 pop +U +ler +liGini 1 popUler +DER lHg +POS2S +ACC, popUler +DER lHg +POS3 +ACC3 1.99 Example word: AlmtHdp AlmtHd +p +Al/PRE mtHd/STM +p/SUF +Al/PRE mtHd/STM +p/SUF, AlmtHd +p AlmtHdp, AlmtHd p, AlmtH dp AlmtHdp Al mtHdp Al/PRE mtHd/STM p/SUF mut aHidap POS:PN Al+ +SG, mut aHid POS:AJ Al+ +SG #a 1 1 2 2.24 1.23 1 1
Example word: baby-sitters baby- sitters bab +y, sitt +er +s +baby-/PRE sitter/STM +s/SUF +baby-/PRE sitter/STM +s/SUF, bab +y, sitt +er +s baby-sitter s, baby-sitt ers baby-sitt ers, baby-sitter s baby- sitters baby - sitters baby N sit V er s +PL
The results of the linguistic evaluation are presented in Tables 5 and 6. The tasks in Competition 1 were the same as in Morpho Challenge 2007, so it is possible to directly compare the improvements made over the previous algorithms. However, direct comparisons between the evaluation measures in different languages are not valid, because the corpora and gold standards are different. In all tasks except the English one, improvements were made in 2008 and the best obtained F-measure was now higher. As clearly seen in Tables 5 and 6, this is mainly due to the improved version of “Monson paramor+morfessor” that dominated all tasks. The difference is especially clear in the recall statistics where the performance of the “Monson paramor+morfessor” is superior. Behind Monson’s algorithms, the “Zeman 1” that is a re-submission from last year, was better than the rest of the algorithms, which all suffered from a very low recall. It is worth noting that the “Kohonen allomorfessor” algorithm achieved clearly the highest precision of all algorithms in all tasks, but due to the low recall, or undersegmentation, it got rather low F-measure values.
From the Competition 1 in Morpho Challenge 2007 [
The Morpho Challenge 2008 was a successful follow-up to our previous Morpho Challenges 2005 and 2007. Since the main tasks were unchanged, the participants of the previous challenges were able to track improvements of their algorithms. It also gave a possibility for the new participants and those who missed the previous deadlines to try more established benchmark tasks. This year the evaluation was performed also in Arabic, and despite the relatively small wordlist and the disability to distribute a relevant text corpus, this task was again successful in finding significant differences between the submitted algorithms.
The significance of the differences in F-measure was analyzed for all algorithm pairs in all tasks using the t-test. The analysis was performed by splitting the data into several partitions and comparing the results in each independent partition separately. The results of the tests show that all differences were statistically significant, except “Zeman 1” vs “Morfessor catmap” in the English task.
As already noted in the previous section, the ranking of the algorithms would have been very different, if only the precision measure was utilized. Some of the methods, especially “Kohonen allomorfessor” undersegmented the word forms heavily, which produced high precision but low recall. However, because it is difficult to estimate the relative weight of precision against recall in different applications, it remains for the application based evaluations in different tasks to show which algorithms are most useful. Many of the grammatical morphemes (such as +PL and +PAST in Table 1) are very common and may not be very relevant in IR, for example, compared to recognizing the right stem.
We thank all the participants for their submissions and enthusiasm. We owe great thanks as well to the organizers of the PASCAL Challenge Program and CLEF who helped us organize this challenge and the challenge workshop. We are most grateful to the University of Leipzig for making the training data resources available to the Challenge, and in particular we thank Stefan Bordag for his kind assistance. We are indebted to Ebru Arisoy for making the Turkish gold standard available to us. We are most grateful to the Nizar Habash from the University of Columbia for his kind assistance and making the Arabic word frequency list and reference analyses available to the Challenge. Our work was supported by the Academy of Finland in the projects Adaptive Informatics and New adaptive and learning methods in speech recognition. This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778. This publication only reflects the authors’ views. We acknowledge that access rights to data and other materials are restricted due to other commitments.