This paper presents the evaluation of Morpho Challenge Competition 2 (information retrieval). The Competition 1 (linguistic gold standard) is described in a companion paper. In Morpho Challenge 2007, the objective was to design statistical machine learning algorithms that discover which morphemes (smallest individually meaningful units of language) words consist of. Ideally, these are basic vocabulary units suitable for different tasks, such as text understanding, machine translation, information retrieval, and statistical language modeling In this paper the morpheme analysis submitted by the Challenge participants were evaluated by performing information retrieval (IR) experiments, where the words in the documents and queries were replaced by their proposed morpheme representations and the search was based on morphemes instead of words. The IR evaluations were provided for three languages: Finnish, German, and English and the participants were encouraged to apply their algorithm to all of them. The challenge organizers performed the IR experiments using the queries, texts, and relevance judgments available in CLEF forum and morpheme analysis methods submitted by the challenge participants. The results show that the morpheme analysis has a significant effect in IR performance in all languages, and that the performance of the best unsupervised methods can be superior to the supervised reference methods. The challenge was part of the EU Network of Excellence PASCAL Challenge Program and organized in collaboration with CLEF.
becoming increasingly important, because language technology methods need to be quickly and as automatically as possible extended to new languages that have limited previous resources. That is why learning the morpheme analysis directly from large text corpora using unsupervised machine learning algorithms is such an attractive approach and a very relevant research topic today.
Morpho Challenge 2007 is a follow-up to our previous Morpho Challenge 2005 (Unsupervised
Segmentation of Words into Morphemes) [
In Morpho Challenge 2007 a more general focus was chosen to not only to segment words into smaller units, but also to perform morpheme analysis of the word forms in the data. For instance, the English words ”boot, boots, foot, feet” might obtain the analyses ”boot, boot + plural, foot, foot + plural”, respectively. In linguistics, the concept of morpheme does not necessarily directly correspond to a particular word segment but to an abstract class. For some languages there exist carefully constructed linguistic tools for this kind of analysis, although not for many, but using statistical machine learning methods we may still discover interesting alternatives that may rival even the most careful linguistically designed morphologies.
The problem of learning the morphemes directly from large text corpora using an
unsupervised machine learning algorithm is clearly a difficult one. First the words should be somehow
segmented into meaningful parts, and then these parts should be clustered in the abstract classes
of morphemes that would be useful for modeling. It is also challenging to learn to generalize
the analysis to rare words, because even the largest text corpora are very sparse, a significant
portion of the words may occur only once. Many important words, for example proper names
and their inflections or some forms of long compound words, may also not exist in the training
material at all, and their analysis is often even more challenging. However, benefits for successful
morpheme analysis, in addition to obtaining a set of basic vocabulary units for modeling, can be
seen for many important tasks in language technology. The additional information included in
the units can provide support for building more sophisticated language models, for example, in
speech recognition [
The evaluation of the unsupervised morpheme analysis was in this challenge solved by
developing two complementary evaluations, one including a comparison to linguistic morpheme analysis
gold standard, and another including a practical real-world application where morpheme analysis
might be used. This paper presents how the application-oriented evaluation called Competition 2
was performed and the companion paper [
The same IR tasks that were attempted using the Morpho Challenge participants’ morpheme
analysis, were also tested by a number of reference methods to see how the unsupervised
morpheme analysis performed in comparison to them. These references included the organizers’ public
Morfessor Categories-Map [
The Morpho Challenge 2007 task was to return the unsupervised morpheme analysis of every
word form contained in a long word list supplied by the organizers for each test language [
The data sets for testing the IR performance in each test language consisted of news paper articles as the source documents, test queries and the binary relevance judgments regarding to the queries. The organizers performed the IR experiments based on the morpheme analyses submitted by the participants, so it was not necessary for the participants to get these data sets. However, all the data was available for registered participants in the Cross-Language Evaluation Forum (CLEF)1.
The source documents were news articles collected from different news papers selected as follows: • In Finnish: 55K documents from short articles in Aamulehti 1994-95, 50 test queries on specific news topics and 23K binary relevance assessments (CLEF 2004) • In English: 170K documents from short articles in Los Angeles Times 1994 and Glasgow Herald 1995, 50 test queries on specific news topics and 20K binary relevance assessments (CLEF 2005). • In German: 300K documents from short articles in Frankfurter Rundschau 1994, Der Spiegel 1994-95 and SDA German 1994-95, 60 test queries with 23K binary relevance assessments (CLEF 2003).
When performing the indexing and retrieval experiments for Competition 2, it turned out
that the test data contained quite many new words in addition to those that were provided as
training data for the Competition 1 [
By the deadline in May, 2007, 6 research groups had submitted the segmentation results obtained by their algorithms. A total of 12 different algorithms were submitted, 8 of them ran experiments on all four test languages. All the submitted algorithms are listed in Table 1. In general, the submissions were all interesting and relevant and all of them met the exact specifications given and were able to get properly evaluated. In addition to the competitors’ 12 morpheme analysis algorithms, we evaluated a number of reference methods described in Section 5.
The outputs of the submitted algorithms are analyzed closer in [
To study and understand how the different morpheme analysis performed in the IR tasks, we attempted the same tasks with different reference methods. This also revealed us whether the unsupervised morpheme analysis (or even a supervised one) could really be useful in the IR tasks compared to simple word based indexing.
1. Morfessor Categories-Map: The same Morfessor Categories-Map (or here just “Morfessor
MAP”, for short) as described in Competition 1 [
In this evaluation, the organizers applied the analyses provided by the participants in information retrieval experiments. The words in the queries and source documents were replaced by the corresponding morpheme analyses provided by the participants, and the search was then based on morphemes instead of words. Any word that did not have a morpheme analysis was left un-replaced.
The evaluation was performed using a state-of-the-art retrieval method (the latest version of
the freely available LEMUR toolkit2). We utilized two standard retrieval method: Tfidf and Okapi
term weighting. The Tfidf implementation in LEMUR applies term frequency weights for both
query and document based on the BM25 weighting and the Euclidean dot-product as similarity
measure. Okapi in LEMUR is an implementation of the BM25 retrieval function as described in
[
The evaluation criterion was Uninterpolated Average Precision There were several different categories and the winner with the highest Average Precision was selected separately for each language and each category: 1. All morpheme analyses from the training data are used as index terms “withoutnew” vs. additionally using also the morpheme analyses for new words that existed in the IR data but not in the training data “withnew”. 2. Tfidf term weighting was utilized for all index terms without any stoplists vs. Okapi term weighting for all index terms excluding an automatic stoplist constructed for each run separately and consisting of the most common terms (frequency threshold was 75,000 for Finnish and 150,000 for German and English). The stoplist was developed for the Okapi weighting, because otherwise Okapi weights were not suitable for the indexes that had many very common terms.
The results of the information retrieval evaluations are shown in Tables 2 – 4. In the Finnish
task, the highest average precision was obtained by the “Bernhard 2” algorithm, which was also
won the Competition 1 [
The “Bernhard 1” algorithm obtained the highest average precision 0.47 for the German task using the new words, Okapi and stoplist. The same algorithm won also the categories for using Tfidf without stoplist with and without new words, but in using Okapi and stoplist without the new words the winner was the “Bernhard 2”. However, the difference between “Bernhard 1” and “Bernhard 2” was very small in all categories.
For English, the highest average precision was obtained by the “Bernhard 2” algorithm, which
was also won the Competition 1 [
As expected, the “grammatical” reference method based on linguistic Gold Standard morpheme
analysis [
For the “Morfessor” references it is interesting to note that they always performed better than
the “grammatical”, which seems to suggest that the coverage of the analysis (“Morfessor” does not
have any out-of-vocabulary words) is more important for IR than the grammatical correctness. The
reason for “Morfessor Baseline” being almost always better than the more sophisticated “Morfessor
Categories-MAP” is not clear, and also the hybrid “Tepper” improvement for Morfessor does not
seem to affect the IR results. In general, the old “Morfessor Baseline” seems to provide a very
good baseline in all tested languages also for the IR tasks as it did for the language modeling and
speech recognition in [
The comparison of the results in the Tfidf and Okapi categories show that the Okapi with stoplist performed significantly better for all languages. We also run Tfidf with stoplist (the results not included here) which achieved results that were better than the plain Tfidf and only slightly inferior to Okapi with stoplist. However, we decided to rather report the original Tfidf, since we wanted to show what is the performance and the relative ranking of the methods without the stoplist.
When comparing the results in the “withnew” and “withoutnew” categories, we see that with stoplist (and Okapi) the addition of the analysis of the new words helps in Finnish, but in German and in English it does not seem to affect the results. Probably this just indicates that in Finnish the vocabulary explosion is more severe and the new corpus introduced a significant amount of important new words. In general, the new words can be analyzed in two different ways: either use the trained analyzer method as such, or train it first with the new words. In this evaluation both ways were actually possible for the participants, and many of them probably already applied the second one.
The Porter stemming that is a standard word preprocessing tool in IR remained unbeaten (by a narrow margin) in our evaluations in English, but in German and especially in Finnish, the unsupervised morpheme analysis methods clearly dominated the evaluation. There might exist better stemming algorithms for those languages, but because of the more complex morphology, their development might not be an easy task.
As future work in this field it should be relatively straight-forward to evaluate the unsupervised morpheme analysis in several other interesting languages, because it is not bounded to only those languages where rule-based grammatical analysis can be performed. It would also be interesting to try to combine the rival analysis to produce something better. 9
The objective of Morpho Challenge 2007 was to design a statistical machine learning algorithm that discovers which morphemes (smallest individually meaningful units of language) words consist of. Ideally, these are basic vocabulary units suitable for different tasks, such as text understanding, machine translation, information retrieval, and statistical language modeling. The current challenge was a successful follow-up to our previous Morpho Challenge 2005 (Unsupervised Segmentation of Words into Morphemes). This time the task was more general in that instead of looking for an explicit segmentation of words, the focus was in the morpheme analysis of the word forms in the data.
The scientific goals of this challenge were to learn of the phenomena underlying word construction in natural languages, to discover approaches suitable for a wide range of languages and to advance machine learning methodology. The analysis and evaluation of the submitted machine learning algorithm for unsupervised morpheme analysis showed that these goals were quite nicely met. There were several novel unsupervised methods that achieved good results in several test languages, both with respect to finding meaningful morphemes and useful units for information retrieval. The IR results also revealed that the morpheme analysis has a significant effect in IR performance in all languages, and that the performance of the best unsupervised methods can be superior to the supervised reference methods.
12 different segmentation algorithms from 6 research groups were submitted and evaluated. The IR evaluations included 3 different languages: Finnish, German and English. The algorithms and results were presented in Morpho Challenge Workshop, arranged in connection with other CLEF 2007 Workshop, September 19-21, 2007. Morpho Challenge 2007 was part of the EU Network of Excellence PASCAL Challenge Program and organized in collaboration with CLEF.
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. Especially, we would like to thank Carol Peters from CLEF for helping us to get Morpho Challenge in CLEF 2007 and organize a great workshop there. We thank also Krista Lagus for comments of the manuscript. 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.