Paradigm Clustering with Weighted Edit Distance (2021)

Abstract: This paper describes our system for the SIGMORPHON 2021 Shared Task on Unsupervised Morphological Paradigm Clustering, which asks participants to group inflected forms together according their underlying lemma without the aid of annotated training data. We employ agglomerative clustering to group word forms together using a metric that combines an orthographic distance and a semantic distance from word embeddings. We experiment with two variations of an edit distance-based model for quantifying orthographic distance, but, due to time constraints, our system does not improve over the shared task’s baseline system.

## introduction most of the world's languages express grammatical properties, such as tense or case, via small changes to a word's surface form. this process is called morphological inflection, and the canonical form of a word is known as its lemma. a search of the wals database of linguistic typology shows that 80% of the database's languages mark verb tense and 65% mark grammatical case through morphology @xcite . the english lemma do, for instance, has an inflected form did that expresses past tense. though english verbs inflect to express tense, there are generally only 4 to 5 surface variations for a given english lemma. in contrast, a russian verb can have up to 30 morphological inflections per lemma, and other languagessuch as basque -have hundreds of forms per lemma, cf. inflected forms are systematically related to each other: in english, most noun plurals are basque lemma: egin begi begiate begidate begie begiete begigu begigute begik begin beginate begio begiote begit begite begitza ... ... ... zenegizkigukeen zenegizkigukete zenegizkiguketen zenegizkigun zenegizkigute zenegizkiguten zenegizkio zenegizkioke zenegizkiokeen zenegizkiokete zenegizkioketen zenegizkion zenegizkiote zenegizkioten zenegizkit in this work, we address the sigmor-phon 2021 shared task on unsupervised morphological paradigm clustering ("task 2") @xcite . the goal of this shared task is to group words encountered in naturally occurring text into morphological paradigms. unsupervised paradigm clustering can be helpful for state-of-the-art natural language processing (nlp) systems, which typically require large amounts of training data. the ability to group words together into paradigms is a useful first step for training a system to induce full paradigms from a limited number of examples, a task known as (supervised) morphological paradigm completion. building paradigms can help an nlp system to induce representations for rare words or to generate words that have not been observed in a given corpus. lastly, unsupervised systems have the advantage of not needing annotated data, which can be costly in terms of time and money, or, in the case of extinct or endangered languages, entirely impossible. since 2016, the association for computational linguistics' special interest group on computational morphology and phonology (sigmorphon) has created shared tasks to help spur the development of state-of-the-art systems to explicitly handle morphological processes in a language. these tasks have involved morphological inflection @xcite , lemmatization @xcite , as well as other, related tasks. sig-morphon has increased the level of difficulty of the shared tasks, largely along two dimensions. the first dimension is the amount of data available for models to learn, reflecting the difficulties of analyzing low-resource languages. the second dimension is the amount of structure provided in the input data. initially, sigmorphon shared tasks provided predefined tables of lemmas, morphological tags, and inflected forms. for the sigmorphon 2021 shared task on unsupervised morphological paradigm clustering, only raw text is provided as input. we propose a system that combines orthographic and semantic similarity measures to cluster surface forms found in raw text. we experiment with a character-level language model for weighing substring differences between words. due to time constraints we are only able to cluster over a subset of each languages' vocabulary. despite of this, our system's performance is comparable to the baseline. ## related work unsupervised morphology has attracted a great deal of interest historically, including a large body of work focused on segmentation @xcite @xcite . recently, the task of unsupervised morphologi-cal paradigm completion has been proposed @xcite @xcite , wherein the goal is to induce full paradigms from raw text corpora. in this year's sigmorphon shared task, we are asked to only address part of the unsupervised paradigm completion task: paradigm clustering. intuitively, the task of segmentation is related to paradigm clustering, but the outputs are different. @xcite produces morphological signatures, which are similar to approximate paradigms, based on an algorithm that uses minimum description length. however, this type of algorithm relies heavily on purely orthographic features of the vocabulary. @xcite hypothesize that approximating semantic information can help differentiate between hypothesized morphemes, revealing those that are productive. they propose an algorithm that combines orthography, semantics, and syntactic distributions to induce morphological relationships. they used semantic relatedness, quantified by latent semantic analysis, combined with the frequencies of affixes and syntactic context @xcite . more recently, @xcite have used skipgram word embeddings @xcite to find meaningful morphemes based on analogies: regularities exhibited by embedding spaces allow for inferences of certain types (e.g., king is to man what queen is to woman). hypothesizing that these regularities also hold for morphological relations, they represent morphemes by vector differences between semantically similar forms, e.g., the vector for the suffix -→ s may be represented by the difference between --→ cats and -→ cat. drawing upon these intuitions, we follow @xcite , which combines semantic distance using fasttext embeddings @xcite with an orthographic distance between word pairs. words are then clustered into paradigms using agglomerative clustering. data as the raw text data for this task, jhu bible corpora @xcite are provided by the organizers. this is the only data that systems can use. the organizers further provide development and test sets consisting of gold clusters for a subset of words in the bible corpora. each cluster is a list of words representing π k σ for π @xmath0, respectively, and π dev , π test π. the partial morphological paradigms in π dev and π test are taken from the unimorph database @xcite . development sets are only available for the development languages, while test sets are only provided for the test languages. all test sets are hidden from the participants until the conclusion of the shared task. languages the development languages featured in the shared task are maltese, persian, portuguese, russian, and swedish. the test languages are basque, bulgarian, english, finnish, german, kannada, navajo, spanish, and turkish. ## system descriptions we submit two systems based on @xcite . the first, referred to below as jw-based clustering, follows their work very closely. the second, lm-based clustering, contains the same main components, but approximates orthographic distances with the help of a language model. ## conclusion we present two systems for the sigmor-phon 2021 shared task on unsupervised morphological paradigm clustering. both of our systems perform slighly worse than the official baseline. however, we also show that this is due to our official submissions only making predictions for a subset of the corpus' vocabulary, due to time constraints and that at least one of our systems improves strongly if the time constraints are removed.