This paper investigates a novel approach to unsupervised morphology induction relying on community detection in networks. In a rst step, morphological transformation rules are automatically acquired based on graphical similarities between words. These rules encode substring substitutions for transforming one word form into another. The transformation rules are then applied to the construction of a lexical network. The nodes of the network stand for words while edges represent transformation rules. In the next step, a clustering algorithm is applied to the network to detect families of morphologically related words. Finally, morpheme analyses are produced based on the transformation rules and the word families obtained after clustering. While still in its preliminary development stages, this method obtains encouraging results at Morpho Challenge 2009, which demonstrate the viability of the approach.
http://www.ukp.tu-darmstadt.de Unsupervised morphology induction, which is the goal of the Morpho Challenge competition series, consists in automatically discovering a word's morphemes using only minimal resources such as a list of the words in the target language and a text corpus. Ideally, unsupervised algorithms should be able to learn the morphology of a large variety of languages; for Morpho Challenge 2009, the target languages were English, Finnish, German, Turkish and Arabic.
For our participation at Morpho Challenge 2009 we developed a novel method for
unsupervised morphology induction called MorphoNet. MorphoNet relies on a network representation of
morphological relations between words, where nodes correspond to whole word forms and edges
encode morphological relatedness. Networks have been successfully used in recent years to
represent linguistic phenomena for tasks such as word clustering [
Though in its very early development stages, the approach yields promising results at Morpho
Challenge 2009 when compared to standard baselines such as the Morfessor algorithms [
The article is structured as follows. In the next section, we report related work. Next, we describe our method for building lexical networks. In Section 4, we explain how word families can be discovered based on the network structure, while in Section 5 we detail our approach for obtaining morpheme analyses. Evaluation results are given in Section 6. 2
Morphological analysis is useful for many applications like speech recognition and synthesis, automatic translation or information retrieval. However, all these applications of morphology necessitate morphological resources which are not available for all languages, or, when available, are often incomplete. Much research has therefore been devoted to the unsupervised acquisition of morphological knowledge.
Methods for the unsupervised acquisition of morphological knowledge can be classi ed
according to the intended result: (i) identi cation of morphologically related words (clustering ), (ii)
splitting of words into morphs (segmentation), and (iii) identi cation of morphemes (analysis ).
Morpheme analysis is the goal of the latest Morpho Challenge competitions, while for some
applications, such as information retrieval, it is often su cient to retrieve morphologically related
words without proceeding to a full analysis. The identi cation of morphologically related words
has been attempted by unsupervised methods [
Segmentation is certainly the method which has gathered the largest amount of interest in the
NLP research community [
1We refer the reader to Arono and Fudeman [
Unsupervised methods rely on many properties for morphology induction, which are too
numerous to be listed here. The most obvious cue is usually graphical relatedness : two words which
share a long enough common substring are likely to be morphologically related. Graphical
relatedness can be estimated by measures of orthographic distance [
A network can be mathematically represented as a graph. Formally, a graph G is a pair (V; E), where V is a set of vertices (nodes) and E V V is a set of edges (lines, links). The main advantage of graphs is that they make it possible to take into account multiple dependencies across elements, so that the whole network plays an important role on the results obtained for a single element.
The lexical networks built by our method consist of word nodes linked by edges which encode
morphological relations. Similar lexical networks have been previously described by Hathout [
The rst step in our method consists in acquiring a set of morphological transformation rules. Morphological transformation rules make it possible to transform one word into another by performing substring substitutions. We represent a rule R with the following notation: pattern ! repl, where pattern is a regular expression and repl is the replacement with backreferences to capturing groups in the pattern. For instance, the rule ^(.+)ly$ ! n1 applies to the word totally to produce the word total.
Transformation rules are related to, though more general than, the notion of a x pairs used
in many methods for the unsupervised acquisition of morphological knowledge, under di erent
names: patterns [
The main advantage of transformation rules over pre x or su x pairs is that they are not limited to concatenative processes, which is especially useful for languages such as Arabic, e.g. when inducing rules for word pairs such as kataba (he wrote) and kutiba (it was written).
These rules are acquired using a subset L of the wordlist W provided for each language. In our experiments, we used the 10,000 most frequent words whose length exceeds the average word (type) length.2 The method used to acquire the rules is described in detail in Algorithm 1.
For each word w in the list L we retrieve graphically similar words (Line 5, get close matches) using a gestalt approach to fuzzy pattern matching based on the Ratcli -Obershelp algorithm.3 For example, given the target word democratic, the following close matches are obtained: undemocratic, democratically, democrats, democrat's, anti-democratic. We then obtain rules (Line 7, get rule from word pair) by comparing the target word with all its close matches and identifying the matching subsequences;4 for instance given the word democratic and its close match undemocratic, we obtain the following rule: ^un(.+)$ ! n1.
We have kept all rules which occur at least twice in the training data.5 Moreover, no attempt is made to distinguish between in ection and derivation.
2Except for Arabic, where there are only 9,641 word forms which are longer than the average word length in the vowelized version and 6,707 in the non-vowelized version.
3We used the implementation provided by the Python di ib module with the cuto argument set to 0.8. 4Matching subsequences are identi ed by the get matching blocks Python method.
5For Arabic, we even kept all rules given the small size of the input word list.
Algorithm 1 Procedure for the acquisition of morphological transformation rules, given an input list of words L.
1: rules ; 2: n len(L) 3: for i = 1 to n do 4: w L[i] 5: matches get close matches(w; L[i + 1 : n]) 6: for w2 in matches do 7: r get rule from word pair(w; w2) 8: add r to rules 9: end for 10: end for 11: return rules Once transformation rules have been acquired, they are used to build a lexical network represented as a graph. Nodes in the graph represent words from the input word list W . Two words w1 and w2 are connected by an edge if there exists a transformation rule R such that R(w1) = w2. The graph obtained using this method is directed based on the direction of the rules applied. Figure 1 displays an example lexical network. 4
The graphs we obtain usually contain one large connected component, along with smaller connected components. Extracting connected components is thus not reliable enough to identify word families, i.e. groups of words which are related both semantically and orthographically. For instance, the lexical network depicted in Figure 1 contains one large connected component, which clearly consists of two di erent word families. The induction of word families can be formulated as a classical problem of community detection in graphs, and thus be solved by clustering algorithms.
Communities correspond to groups of tightly-knit nodes characterised by a high intra-group
density and a lower inter-group density [
insultingly insulating
insulators insulator insulated
insulates insulate insulation
insulted insulting insults insult
The method proposed by Newman relies on the modularity function Q which measures the quality of a division of a graph into communities. The advantages of this method are that it is not necessary to know the number of communities beforehand and it needs no ne parameter tuning. Modularity compares the number of edges within communities to the number of expected edges: Q =
X(eii i (X eij )2) j where eii is the fraction of the edges in the network that connect nodes within community i, eij is one-half of the fraction of edges in the network that connect nodes in community i to those in community j and Pj eij is the fraction of edges connected to nodes in community i.
A good division corresponds to more edges within communities than would be expected by random chance, that is to say a positive modularity value Q. Modularity is high when there are many edges within communities and few between them. Figure 2 illustrates the results of Newman's algorithm on the lexical network of Figure 1: in this case, two communities are identi ed.
The main di culty lies in nding the division which yields the best value for Q. It is of
course infeasible to test each possible division of the network. Newman [
Our experiments with the Newman Clustering algorithm have nevertheless shown that it tends to detect bigger communities than wanted, thus decreasing the precision. We have therefore added an additional constraint on possible joins by measuring the density of edges across communities (cross-community edge density ).
Cross-community edge density between communities A and B is de ned as follows: number of edges(A; B)
DAB = jAj jBj where number of edges(A; B) is the number of edges linking nodes in community A to nodes in community B, and j j and jBj are the number of nodes in community A and B, respectively.
A
The minimum cross-community edge density is xed by a parameter d whose value ranges from 0 to 1.
After performing clustering, morpheme analyses are obtained based on the word families identi ed and the transformation rule edges linking words which belong to the same family. First, a representative word is identi ed for each word family: this is the shortest word in the family; in case of a tie, the most frequent among the shortest words is chosen. The full morpheme analysis for a word form w consists of its family representative and a string representation of the transformation rules that apply to w. The method is detailed in Algorithm 2.
Algorithm 2 Procedure for obtaining the morpheme analyses, given a word family C and the lexical network G.
1: analyses[ ] ; 2: subg get subgraph(G; C) 3: for edge (w1; w2; rule) in subg do 4: analyses[w1] analyses[w1] [ to plain string(rule:pattern) 5: analyses[w2] analyses[w2] [ to plain string(rule:repl) 6: end for 7: rep get family representative(C) 8: for word w in word family C do 9: analyses[w] analyses[w] [ rep 10: end for 11: return analyses absorbers absorbing absorber absorbes re-absorbing absorbingly absorb absorbs reabsorb // absorbable non-absorbable absorbables // super-absorbent super-absorbency superabsorbent // aborbed unabsorbed self-absorbed absorbed well-absorbed non-absorbed // high-absorbency absorbent absorbant absorbency absorbents absorbencies well-documented undocumented documented document's // documents documents' documentation documention document-based documenting document // documentarian documentary's documentary documentaries friendship's friendship friendships // friend's friendly's ends friendy friends friendlier friendly rends end friends' friend unfriendly friendlies emigrants emigrants' emigrant emigrant's // emigrators emgrated emigrates emigrated emigrations emigration emigratiion emigrate emigrating // migrated outmigration outmigration migration migrates migratory migrations transmigration non-migratory migrating sparkler sparkling sparkles sparkled sparklers non-sparkling sparkle sparklingly
Example Consider for instance the communities represented in Figure 2. The representative for the word family finsulted ;insulting ;insult ;insults ;insultingly g is insult since it is the shortest word. The complete analyses for the words are the following: insultingly insulting insulted insults insult insult ly ingly insult ing insult ed insult s insult Two transformation rules apply to the word insultingly : ^(.+)ly$ ! n1 and ^(.+)ingly$ ! n1, which are represented in the nal analysis as ly ingly. 6
In this section, we report the results obtained by MorphoNet at Morpho Challenge 2009 competitions 1 (linguistic evaluation) and 2 (information retrieval). For all languages, the value of parameter d (cross-community edge density) was empirically set to 0.1 for community detection. 6.1
P
R
F
Except for Arabic, where no results have been provided for Morfessor CatMAP, MorphoNet obtains intermediate results between both Morfessor systems. In Finnish, German and Turkish, MorphoNet performs better than Morfessor baseline, but worse than Morfessor CatMAP. In English, MorphoNet performs better than Morfessor CatMAP and worse than Morfessor baseline.
The results show that MorphoNet consistently obtains better precision than recall, especially in Arabic. The method relies on a list of transformation rules which are automatically acquired. It is therefore likely that some important rules are missing, leading to low recall. This problem might be solved by performing multiple iterations of rule induction and clustering or by applying rules in a cascaded manner, so that one rule applies to the output of another rule.
Moreover, the procedure for obtaining morpheme analyses is still very coarse and could easily be improved by detecting composite morphemes. For instance, ingly could be decomposed into ing and ly.
Finally, transformation rules could be weighted by their frequency to improve clustering. 6.2
MorphoNet improves the IR results over unanalysed words for English and Finnish, but not for German. While it is di cult to come up with a clear explanation, this might be due to the compounding nature of German. Indeed, the MorphoNet system does not directly cope with compounding for the time being, which might be detrimental to the IR task.
We have described a novel linguistically motivated approach to unsupervised morpheme analysis relying on a network representation of morphological relations between words. Due to the underlying network representation, it is possible to use community detection and ranking methods devised for other kinds of data. This approach is still in its very early stage, yet the results obtained at Morpho Challenge 2009 demonstrate that it yields very promising results and thus deserves further investigation.
The method described in this paper can be considered as a baseline for network-based morphology induction. It leaves lots of room for improvement. A rst objective would be to obtain a better recall for morpheme analysis. This necessitates to provide a better mechanism for the acquisition of transformation rules. It should be possible to perform multiple iterations of the rule induction and clustering cycle or to apply rules in a cascaded manner. This is especially needed for languages which are morphologically more complex than English such as Turkish or Finnish. Also, we have not weighted the edges in the graph, which could be useful to improve clustering.
The clustering method performs hard-clustering: each word belongs to only one family. This is especially detrimental for languages like German, for which it would be desirable to allow multiple family membership in order to take compounding into account. In the future, we would therefore like to better address compounding.
Graphs also open up the way for a new form of modelisation of morphology enabling the analysis of crucial morphological properties. Node properties in the graph could be used to rank nodes and detect base words in families, using algorithms such as PageRank. Moreover, edge properties could be employed to di erentiate between di erent forms of morphological processes such as in ection and derivation. We will consider these posibilities in our future work. [8] Mathias Creutz and Krista Lagus. Inducing the Morphological Lexicon of a Natural Language from Unannotated Text. In Proceedings of the International and Interdisciplinary Conference on Adaptive Knowledge Representation and Reasoning (AKRR'05), 2005. [9] Sajib Dasgupta and Vincent Ng. High-Performance, Language-Independent Morphological Segmentation. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics (HLT-NAACL 2007), pages 155{163, 2007.