Findings of the SIGMORPHON 2021 Shared Task on Unsupervised Morphological Paradigm Clustering (2021)

Abstract: We describe the second SIGMORPHON shared task on unsupervised morphology: the goal of the SIGMORPHON 2021 Shared Task on Unsupervised Morphological Paradigm Clustering is to cluster word types from a raw text corpus into paradigms. To this end, we release corpora for 5 development and 9 test languages, as well as gold partial paradigms for evaluation. We receive 14 submissions from 4 teams that follow different strategies, and the best performing system is based on adaptor grammars. Results vary significantly across languages. However, all systems are outperformed by a supervised lemmatizer, implying that there is still room for improvement.

## introduction in recent years, most research in the area of computational morphology has focused on the application of supervised machine learning methods to word inflection: generating the inflected forms of a word, often a lemma, in order to express certain grammatical properties. for example, a supervised inflection system for spanish might be provided with a lemma disfrutar (english: to enjoy) and morphological features such as indicative, present tense & 1 st person singular, and generate the corresponding inflected form disfruto as output. however, a supervised machine learning setup is quite different from a human first language (l1) acquisition setting. young children must learn to segment a continuous speech signal into discrete words and perform unsupervised classification, decoding, and eventually, inference with incomplete feedback on this noisy input. the task of unsupervised paradigm clustering aims to replicate one of the steps in this process-namely, the grouping of word forms belonging to the same lexeme into inflectional paradigms. in this unsupervised task, a system does not know about lemmas. furthermore, neither does it know (a) the features for which a lemma typically inflects, nor (b) the number of distinct inflected forms which constitute the paradigm. a successful unsupervised paradigm clustering system leverages common patterns in the language's inflectional morphology while simultaneously ignoring regular circumstantial similarities along with derivational patterns. for example, an accurate unsupervised system must recognize that disfrutamos (english: we enjoy) and disfruta (english: he/she/it enjoys) are inflected variants of the same paradigm, but that the orthographically similar disparamos (english: we shoot), belongs to a separate paradigm. likewise, a successful system for english will recognize that walk and walked belong to the same verbal paradigm but walker is a derived form belonging to a distinct nominal paradigm. such fine-grained distinctions are difficult to learn in an unsupervised manner. this paper describes the sigmorphon 2021 shared task on unsupervised morphological paradigm clustering. participants are asked to submit systems which cluster words from the bible into inflectional paradigms. 1 participants are not allowed to use any external resources. four teams submit at least one system for the shared task and all teams also submit a system description paper. the shared task systems can be grouped into two broad categories: similarity-based systems experiment with different combinations of orthographic and embedding-based similarity metrics for word forms combined with clustering methods like k-means or agglomerative clustering. grammarbased methods instead learn grammars or rules from the data and either apply these to clustering directly, or first segment words into stems and affixes and then cluster forms which share a stem into paradigms. our official baseline, described in section 2.3, is based on grouping together word forms sharing a common substring of @xmath0, where k is a hyperparameter. grammar-based systems obtain higher average f1 scores (see section 2.2 for details on evaluation) across the nine test languages than the baseline. the edinburgh system has the best overall performance: it outperforms the baseline by 34.61% f1 and the second best system by 1.84% f1. the rest of the paper is organized as follows: section 2 describes the task of unsupervised morphological paradigm clustering in detail, including the official baseline and all provided datasets. section 3 gives an overview of the participating systems. section 4 describes the official results, and 5 presents an analysis. finally, section 6 contains a discussion of where the task can move in future iterations and concludes the paper. ## task description unsupervised morphological paradigm clustering consists of, given a raw text corpus, grouping words from that corpus into their paradigms without any additional information. recent work in unsupervised morphology has attempted to induce full paradigms from corpora with only a subset of all types. kann et al. (2020) and erdmann et al. (2020) explore initial approaches to this task, which is called unsupervised morphological paradigm completion, but find it to be challenging. building upon the sigmorphon 2020 shared task on unsupervised morphological paradigm completion @xcite , our shared task is focused on a subset of the overall problem: sorting words into paradigms. this can be seen as an initial step to paradigm completion, as unobserved types do not need to be induced, and the inflectional categories of paradigm slots do not need to be considered. ## submitted systems the boulder-perkoff-daniels-palmer team (boulder-pdp; perkoff et al., 2021) participates with four submissions, resulting from experiments with two different systems. both systems apply k-means clustering on vector representations of input words. they differ in the type of vector representations used: either orthographic or semantic representations. semantic skip-gram representations are generated using word2vec @xcite . for the orthographic representations, each word is encoded into a vector of fixed dimensionality equaling the word length |w max | for the longest word w max in the input corpus. they associate each character @xmath1, 1] and assign v i := r if the ith character of the input word w is c. if |w| < |w max |, the remaining entries are assigned to 0. the number of clusters is a hyperparameter of the k-means clustering algorithm. in order to set this hyperparameter, perkoff et al. (2021) experiment with a graph-based method. the word types in the corpus form the nodes of a graph, where the neighborhood of a word w consists of all words sharing a maximal substring with w. the graph is split into highly connected subgraphs (hcs) containing n nodes, where the number of edges that need to be cut in order to split the graph into two disconnected components @xmath2. the number of hcss is then taken to be the cluster number. in practice, however, the graph-clustering step proves to be prohibitively slow and results for test languages are submitted using fixed numbers of clusters of size 500, 1000, 1500 and 1900. in experiments on the dev languages, they find that the orthographic representations outperform the semantic representations for all languages, and thus submit four systems utilizing orthographic representations. the boulder-gerlach-wiemerslage-kann team (boulder-gwk; @xcite submits two systems based on an unsupervised lemmatization system originally proposed by @xcite . their approach is based on agglomerative hierarchical clustering of word types, where the distance between word types is computed as a combination of a string distance metric and the cosine distance of fasttext embeddings @xcite . their choice of fasttext embeddings is due to the limited size of the shared task datasets. two variants of edit distance are compared to quantify string distance: (1) jaro-winkler edit distance @xcite resembles regular edit distance of strings but emphasizes similarity at the start of strings which is likely to bias the system toward languages expressing inflection via suffixation. (2) a weighted variant of edit distance, where costs for insertions, deletions and substitutions are derived from a character-based language model trained on the shared task data. the cu-ubc @xcite team provides systems that built upon the official shared task baseline -given the pseudo-paradigms found by the baseline, they extract inflection rules of multiple types. comparing pairs of words in each paradigm, they learn both continuous and discontinuous character sequences that transform the first word into the second, following work on supervised inflectional morphology, such as @xcite ; @xcite . rules are sorted by frequency to separate genuine inflectional patterns from noise. starting from a random seed word, paradigms are constructed by iteratively applying the most frequent rules. generated paradigms are further tested for paradigm coherence using metrics such as graph degree calculation and fasttext embedding similarity. based on the segmented words from the raw text data, they then determine whether the language uses prefixes or suffixes for inflection. the final stem for words in a predominantly suffixing lan-guage then consists of the prefixes and stem identified by the adaptor grammar. for a predominantly prefixing language, the final stem instead contains all suffixes of the word form. the team notes that this approach is unsuitable for languages which extensively make use of both prefixes and suffixes, such as basque. finally, they group all words which share the same stem into paradigms. however, because sampling from an adaptor grammar is a nondeterministic process -i.e., the system may return multiple possible segmentations for a single word form -they construct preliminary clusters by including all forms which might share a given stem. then they select the cluster that maximizes a score based on frequency of occurrence of the induced segment in all segmentations. ## results and discussion the official results obtained by all submitted systems on the test sets are shown in the edinburgh system performs best overall with an average best-match f1 of 67.96%. in general, grammar-based systems attain the best results, with all of the cu-ubc systems and the edinburgh system outperforming the baseline by at least 23.06% f1. the boulder-gwk and boulder-pdp systems, both of which perform clustering over word representations, approach but do not exceed baseline performance. @xcite found that clustering over word2vec embeddings performs poorly on the development languages, and their scores on the test set reflect clusters found with vectors based purely on orthography. the boulder-gwk systems contain incomplete results, and partial evidence suggests that their clustering method, which combines both fasttext embeddings trained on the provided bible corpora, and edit distance, can indeed outperform the baseline. however, it likely cannot outperform the grammarbased submissions. for comparison, we also evaluate a supervised lemmatizer from the stanza toolkit @xcite . the stanza lemmatizer is a neural network model trained on universal dependencies (ud) treebanks @xcite , which first tags for parts of speech, and then uses these tags to generate lemmas for a given word. because there is no ud corpus in the current version for navajo nor kannada, we do not have scores for those languages. stanza's accuracy on our task is far lower than that reported for lemmatization on ud data. we note, however, that 1) our data is from a different domain, 2) biblical language in particular can differ strongly from contemporary text, and 3) we evaluate on only a partial set of types in the corpus, which could represent a particularly challenging set of paradigms for some languages. the stanza lemmatizer outperforms all systems for all languages, except for german. this is unsurprising as it is a supervised system, though it is interesting that the german score falls short of that of the edinburgh system. overgeneralization/underspecification when acquiring language, children often overgeneralize morphological analogies to new, ungrammatical forms. for example, the past tense of the english verb to know might be expressed as knowed, rather than the irregular knew. the same behavior can also be observed in learning algorithms at some point during the learning process @xcite . this is reflected to some extent in on the other hand, several systems seem to underspecify, indicated by their low recall. a low recall, but high precision indicates that a system does not attribute inflected forms to a paradigm that the form does in fact belong to. this can be caused by suppletion in systems based purely on orthography, for example, generating the paradigm with go and goes, but attributing went to a separate paradigm. underspecification is apparent in the cu-ubc submissions that relied on discontinuous rules (cu-ubc 5, 6, and 7). this is likely because they filtered these systems down to far fewer rules than their prefix/suffix systems, in order to avoid severe overgeneralization that can result from spurious morphemes based on discontinuous substrings. similarly, the boulder-gwk systems both have reasonable precision, but very low recalls. they report that this is due to the fact that they ignore any words with less than a certain frequency in the corpus due to time constraints, thus creating small paradigms and ignoring many words completely. language and typology in general, we find that basque and navajo are the two most difficult test languages. both languages have relatively small figure 3 : singleton paradigm counts for the best performing system on all test languages. languages for which we have more than 100 paradigms on the left, and those for which we have less than 100 paradigms on the right. predicted singleton paradigms are in red and blue, gold singleton paradigms are in grey. figure 4 : the f1 score across paradigm sizes for the best performing system on all test languages. from left to right, the graphs represent the groups of languages in increasing order of how well systems typically performed on them. f1 scores are interpolated for paradigm sizes that do not exist in a given language. corpora, and are typlogically agglutinative -that is, they express inflection via the concatenation of potentially many morpheme segments, which can result in a large number of unique surface forms. both languages thus have relatively high type-token ratios (ttr) -especially navajo, which has the highest ttr, cf. navajo is a predominantly prefixing language -the only one in the development and test setsand basque also inflects using prefixes, though to a lesser extent. the top two performing systems both obtain low scores for navajo. the cu-ubc-2 system considers only suffix rules, which results in it being the lowest performing cu-ubc system on navajo. the edinburgh submission should be able to identify prefixes and consider the suffix to be part of the stem in navajo. however, the large number of types, for a relatively small navajo cor-pus may cause difficulties for their algorithm that builds clusters based on affix frequency. notably, the cu-ubc-7 system, which learns discontinuous rules rather than rules that model strictly concatenative morphology, performs best on navajo by a large margin when compared to the best performing system, which relies on strictly concatenative grammars. it also performs best on basque, though by a smaller margin. another difficulty in navajo morphology is that it exhibits verbal stem alternation for expressing mood, tense, and aspect, which creates challenges for systems that rely on rewrite rules or string similarity, based on continuous substrings. for instance, our evaluation algorithm aligns a singleton predicted paradigm to the gold paradigm in on basque, most systems perform poorly. @xcite , the best performing system overall, obtains a low score for basque, which may be due to their system assuming that a language inflects either via prefixation or suffixation, but not both, as basque does. other systems, however, attain similarly low scores for basque. the next tier of difficulty seems to comprise finnish, kannada, and turkish, on which most sys-tems obtain low scores. all of those languages are suffixing, but also have an agglutinative morphology. the largest paradigm of each of these 3 languages are all in the top 4 largest paradigms in finally, systems obtain the best results for english, followed by spanish, and then bulgarian. these three languages are also strongly suffixing, but typically express inflection with a single morpheme. german appears to be a bit of an outlier, generally exhibiting scores that lie somewhere between the highest scoring languages, and the more difficult agglutinative languages. @xcite hypothesize that this may be due to nonconcatenative morphology from german verbal circumfixes. this hypothesis could explain why the boulder-gwk system performs better on german than other languages: it incorporates semantic information. however, the cu-ubc systems that use discontinuous rules (systems 5, 6, and 7), and thus should better model circumfixation, do not produce higher german scores than the continuous rules, including the suffix-only system. ## analysis: partial paradigm sizes the effect of the size of the gold partial paradigms on f1 score for the best system is illustrated in figure 4 . for basque and navajo, the f1 score tends to drop as paradigm size increases. we see the same trend for finnish, kannada, and german, with a few exceptions, but this trend does not exist for all languages. english resembles something like a bell shape, other than the low scoring outlier for the largest paradigms of size 7. interestingly, spanish and turkish attain both very high and very low scores for larger paradigms. an artifact of a sparse corpus is that many singleton paradigms arise. for theoretically larger paradigms, only a single inflected form might occur in such a small corpus. of course, this also happens naturally for certain word classes. however, nouns, verbs, and occasionally adjectives typically form paradigms comprising several inflected forms. figure 3 demonstrates that the best system tends to overgenerate singleton paradigms. we see this to some extent for all agglutinative languages, which may be due to the high number of typically long, unique forms. this is especially true for navajo, which has a small corpus and extremely high typetoken ratio. on the other hand, for the languages for which the highest scores are obtained, spanish and english, the system does not overgenerate singleton paradigms. of the large number of singleton paradigms predicted for both languages, the vast majority are correct. for other systems not pictured in the figure, singleton paradigms are typically undergenerated for spanish and english. in the case of english, this could be due to words that share a derivational relationship. for example, the word accomplishment might be assigned to the paradigm for the verb accomplish, when, in fact, their relationship is not inflectional. ## conclusion and future shared tasks we presented the sigmorphon 2021 shared task on unsupervised morphological paradigm clustering. submissions roughly fell into two categories: similarity-based methods and grammarbased methods, with the latter proving more successful at the task of clustering inflectional paradigms. the best systems significantly improved over the provided n-gram baseline, roughly doubling the f1 score -mostly through much improved precision. a comparison against a supervised lemmatizer demonstrated that we have not yet reached the ceiling for paradigm clustering: many words are still either incorrectly left in singleton paradigms or incorrectly clustered with circumstantially (and often derivationally) related words. regardless of the ground still to be covered, the submitted results were a successful first step in automatically inducing the morphology of a language without access to expert-annotated data. unsupervised morphological paradigm clustering is only the first step in a morphological learning process that more closely models human l1 acquisition. we envision future tasks expanding on this task to include other important aspects of morphological acquisition. paradigm slot categorization is a natural next step. to correctly categorize paradigm slots, cross-paradigmatic similarities must be considered, for example, the german words liest and schreibt are both 3 rd person singular present indicative inflections of two different verbs. this can occasionally be identified via string similarity, but more often requires syntactic information. syncretism (the collapsing of multiple paradigm slots into a single representation) further complicates the task. a similar subtask involves lemma identification, where a canonical form @xcite ) is identified within the paradigm. likewise, another important task involves filling unrealized slots in paradigms by generating the correct surface form, which can be approached similarly to previous sigmorphon shared tasks on inflection @xcite @xcite @xcite ), but will likely be based on noisy information from the slot categorization -all previous tasks have assumed that the morphosyntactic information provided to an inflector is correct. currently, investigations into the robustness of these systems to noise are sparse. another direction for this task is the expansion to more under-resourced languages. the submitted results demonstrate that the task becomes particularly difficult when the provided raw text is small, but under-documented languages are often the ones most in need of morphological corpora. the jhubc contains bible data for more than 1500 languages, which can potentially be augmented by other raw text corpora because morphology is relatively stable across domains. future tasks may enable the construction of inflectional paradigms in languages that require them to construct further computational tools.