We propose the task of unsupervised morphological paradigm completion . Given only raw text and a lemma list, the task consists of generating the morphological paradigms, i.e., all inflected forms, of the lemmas. From a natural language processing (NLP) perspective, this is a challenging unsupervised task, and high-performing systems have the potential to improve tools for low-resource languages or to assist linguistic annotators. From a cognitive science perspective, this can shed light on how children acquire morphological knowledge. We further introduce a system for the task, which generates morphological paradigms via the following steps: (i) EDIT TREE retrieval, (ii) additional lemma retrieval, (iii) paradigm size discovery, and (iv) inflection generation. We perform an evaluation on 14 typologically diverse languages. Our system outperforms trivial baselines with ease and, for some languages, even obtains a higher accuracy than minimally supervised systems. 1 1 Introduction Morphologically rich languages express syntactic and semantic propertieslike tense or case  of words through inflection, i.e., changes to the surface forms of the words. The set of all inflected forms of a lemma the canonical formis called its paradigm . While English does not manifest a rich inflectional morphology, Polish verbs have around a hundred different forms (Sadowska, 2012), and Archi paradigms, an extreme example, can have over 1.5 million slots (Kibrik, 1977). Morphologically rich languages constitute a challenge for natural language processing (NLP) systems: because each lemma can take on a variety of surface forms, the frequency of each individual inflected word decreases drastically. This yields problems for speech recognition (Creutz 1 Our implementation is available under https://github. et al., 2007), parsing (Seeker and Cetinoglu, 2015), and keyword spotting (Narasimhan et al., 2014), inter alia . For unsupervised machine translation, Guzman et al. (2019) encounter difficulties when translating into the morphologically rich languages Nepalese and Sinhalese. Children acquire morphological knowledge from raw utterances and, in particular, without access to explicit morphological information (Berko, 1958). Do they have an innate capacity that enables them to learn a language's morphology? Or can morphology be learned in an unsupervised fashion? This questionin addition to practical considerations like benefits for the aforementioned NLP tasks has motivated work on unsupervised morphological analyses (Goldsmith, 2001; Creutz, 2003). To the best of our knowledge, no previous work has considered unsupervised morphological generation . 2 However, over the last few years, there has 2 Kann et al. (2017), which performs a zero-shot inflection experiment, uses prior information about paradigm size and related languages and, thus, cannot draw the same conclusions. been a lot of progress on morphological generation tasks with limited amounts of supervision, in particular on morphological inflection (Cotterell et al., 2018) and paradigm completion (Kann and Schutze, 2018), which can potentially be leveraged for unsupervised solutions. Here, we fill the gap between unsupervised morphological analysis and morphological generation with limited training data by proposing the task of unsupervised morphological paradigm completion . That is, we aim to construct and fill inflection tables exclusively from raw text and a lemma list for a known part of speech (POS), in a situation similar to those encountered by field linguists. We further present a system for the task (see Figure 1) which employs state-of-the-art methods common in NLP and computational morphology. It performs the following four steps: (i) EDIT TREE (Chrupaa, 2008) retrieval (  4.1), (ii) additional lemma retrieval (  4.2), (iii) paradigm size discovery using distributional information (  4.3), and (iv) inflection generation (  4.4). To evaluate our approach, we design a metric for unsupervised paradigm completion, best-match accuracy (  5.4), and experiment on 14 languages from 7 families. As we are tackling a novel task with no baselines in the NLP literature, we perform an extensive ablation study to demonstrate the importance of all steps in our pipeline. We further show that our system outperforms trivial baselines and, for some languages, even obtains higher accuracy than a minimally supervised system. Morphological Generation Versions of our task with varying degrees of supervisionthough never totally unsupervisedhave been explored in the past. Yarowsky and Wicentowski (2000) is the previous work most similar to ours. They also assume raw text and a word list as input, but additionally require knowledge of a language's consonants and vowels, as well as canonical suffixes for each part of speech. Dreyer and Eisner (2011) assume access to seed paradigms to discover paradigms in an empirical Bayes framework. Ahlberg et al. (2015) and Hulden et al. (2014) combine information about paradigms and word frequency from corpora to perform semi-supervised paradigm completion. Our work differs from them in that we do not assume any gold paradigms to be given. Durrett and DeNero (2013), Nicolai et al. (2015), and Faruqui et al. (2016) explore a fully supervised approach, learning morphological paradigms from large annotated inflection tables. This framework has evolved into the SIGMORPHON shared tasks on morphological inflection (Cotterell et al., 2016), which have sparked further interest in morphological generation (Kann and Schutze, 2016; Aharoni and Goldberg, 2017; Bergmanis et al., 2017; Makarov et al., 2017; Zhou and Neubig, 2017; Kann and Schutze, 2018). We integrate two systems (Cotterell et al., 2017; Makarov and Clematide, 2018b) produced for SIGMORPHON shared tasks into our framework for unsupervised morphological paradigm completion. Morphological Analysis Most research on unsupervised systems for morphology aims at developing approaches to segment words into their smallest meaning-bearing units, called morphemes (Gold-smith, 2001; Creutz, 2003; Creutz and Lagus, 2007; Snyder and Barzilay, 2008). Unsupervised morphological paradigm completion differs from segmentation in that, besides capturing how morphology is reflected in the word form, it also requires correctly clustering transformations into paradigm slots as well as generating unobserved forms. The model by Xu et al. (2018) recovers something akin to morphological paradigms. However, those paradigms are a means to a segmentation end, and Xu et al. (2018) do not explicitly model information about the paradigm size as required for our task. Other unsupervised approaches to learning morphological analysis and generation rely on projections between word embeddings (Soricut and Och, 2015; Narasimhan et al., 2015); however, these approaches rely on billions of words to train embeddings; at a minimum, Narasimhan et al. (2015) use 129 million word tokens of English Wikipedia. As we will describe later on (  5.1), we, in contrast, are concerned with the setting with mere thousands of sentences. For a detailed survey of unsupervised approaches to problems in morphology, we refer the reader to Hammarstrom and Borin (2011). SIGMORPHON 2020: Unsupervised Morphological Paradigm Completion After multiple shared tasks on morphological inflection starting with Cotterell et al. (2016), in 2020, SIGMORPHON (the ACL special interest group on computational morphology and phonology) is organizing its first shared task on unsupervised morphological paradigm completion. 3 The system presented here is the official shared task baseline system. The first other approach applicable to this shared task has been developed by Erdmann et al. (2020). Their pipeline system is similar in spirit to ours, but the individual components are different, e.g., a transformer model (Vaswani et al., 2017) is used for inflection generation. Given a corpus D = w 1 , . . . , w |D| with a vocabulary V of word types { w i } and a lexicon L = { (cid:96) j } with |L| lemmas belonging to the same part of speech, the task of unsupervised morphological paradigm completion consists of generating the paradigms {  ( (cid:96) ) } (cid:96) L of the entries in the lexicon. Following Matthews and Matthews (1972) and Aronoff (1976), we treat a paradigm as a vector of inflected forms belonging to a lemma (cid:96) . Paradigm completion consists of predicting missing slots in the paradigm  ( (cid:96) ) :  ( (cid:96) ) = (cid:10) f ( (cid:96),(cid:126)t  ) (cid:11)   ( (cid:96) ) , (1) where f :    T    transforms a lemma into an inflected form, 4 (cid:126)t   T is a vector of inflectional features describing paradigm slot  , and ( (cid:96) ) is the set of slots in lemma (cid:96) 's paradigm. Since we only consider lemmas that belong to the same part of speech, we will use  and ( (cid:96) ) interchangeably in the following. Furthermore, we will denote f ( (cid:96),(cid:126)t  ) as f  ( (cid:96) ) for simplicity. On another note, it is not necessary to predict the features (cid:126)t  corresponding to each slot  ; as the exact denotation of features is up to human annotators, they cannot be inferred by unsupervised systems. For our task, it is enough to predict the ordered vector  ( (cid:96) ) of inflected forms. Our system implicitly solves two subtasks: (i) determining the number of paradigm slots; and (ii) generating the inflected form corresponding to each paradigm slot for each lemma. It is organized as a 3 https://sigmorphon.github.io/sharedtasks/ 2020/task2/ 4 We assume a discrete alphabet of symbols  . pipeline consisting of multiple components. Our system is highly modular: individual components can be exchanged easily. In the remainder of this section, we will dedicate each subsection to one component. The first component in our pipeline identifies words in the corpus D which could belong to the paradigm of one of the lemmas in the lexicon L . We call those words paradigm candidates . It then uses the discovered paradigm candidates to identify EDITTREE (Chrupaa, 2008) operations that correspond to valid inflections. Paradigm Candidate Discovery For most paradigms, all participating inflected forms share some characteristicsusually substringswhich humans use to identify the paradigm any given word belongs to. Given a pair ( (cid:96), w ) of a lemma (cid:96) and a word form w , the first step in our pipeline is to determine whether w is a paradigm candidate for lemma (cid:96) . For example, studied is likely to be an inflected form of the English lemma study , while monkey is not. We identify paradigm candidates C (cid:96) of a lemma (cid:96) by computing the longest common substring (LCS) between (cid:96) and w for all words w in the vocabulary V . If the ratio between the LCS's length and the length of (cid:96) is higher than a threshold  P , w is a paradigm candidate for (cid:96) : C (cid:96) = (cid:26) w  V (cid:12)(cid:12)(cid:12)(cid:12) | LCS( (cid:96), w ) | | (cid:96) | >  P (cid:27) . EDIT TREE Discovery Surface form changes, which we denote as  , define a modification of a word's surface form. Our system employs EDIT TREES (Chrupaa, 2008) to represent  . Given two strings x [1 ...n ] and x (cid:48) [1 ...m ] , EDIT TREE ( x [1 ...n ] , x (cid:48) [1 ...m ] ) is constructed by first determining the LCS between x and x (cid:48) . We then recursively model the substrings before and after the LCS. If the length of the LCS is zero, the EDIT TREE consists of the substitution operation of the first string with the second. For example, EDIT TREE ( najtrudniejszy , trudny ) 5 could be visualized as in Figure 2, where Split( i, j ) represents taking the substring x [ i...n  j ] . An EDIT TREE can be applied to new input strings. The EDIT TREE in Figure 2, for example, could be applied to naj apple iejsz s , and the resulting string would be apples . Note that not all EDIT TREES can be applied to all strings. For example, the EDIT TREE in Figure 2 can only be applied to words starting with naj . Our system constructs EDIT TREES from all pairs ( (cid:96), w ) of lemmas (cid:96) and their paradigm candidates w and counts their frequencies: n  = (cid:88) (cid:96) L w  C (cid:96) 1 [ EDIT TREE ( (cid:96), w ) =  ] . It then discards EDIT TREES with frequencies n  below a threshold  FC ( |L| ) , which is a function of the size of the lexicon L : FC ( |L| ) = max { 2 ,  FC  |L|} , where  FC  R is a hyperparameter. The idea is that an EDIT TREE is only valid if it can be applied to multiple given lemmas. EDIT TREES which we observe only once are always considered unreliable. Our system then retains a set of frequent surface form changes  = {  | n    FC ( |L| ) } (5) represented by EDIT TREES . Assuming an one-to-one mapping between surface form changes and paradigm slots (that is, that |  | = |  | and that each  is equivalent to a particular inflection function f  ), we now have a first basic paradigm completion system ( PCS-I ), which operates by applying all suitable EDIT TREES to all lemmas in our lexicon. Complexity and Runtime The time complexity to compute EDIT TREE ( x [1 ...n ] , x (cid:48) [1 ...m ] ) is O (max 3 { n, m } ) . Computing EDIT TREES can trivially be parallelized, and in practice this computation does not take much time. Since we assume a low-resource setting, our lexicon is small (  100 entries). However, the more 5 Polish formlemma pair meaning hardest and hard . lemmas we have, the more confident we can be that the EDIT TREES retrieved by the first component of our system represent valid inflections. An intuitive method to obtain additional lemmas would be to train a lemmatizer and to generate new lemmas from words in our corpus. However, due to the limited size of our initial lemma list, such a lemmatizer would most likely not be reliable. The second component of our system employs another method, which guarantees that additionally retrieved lemmas are valid words: It is based on the intuition that a word w  V is likely to be a lemma if the pseudoinflected forms of w , obtained by applying the EDIT TREES from  4.1, also appear in V . For a word w  V , we say it is a discovered lemma if w /  L and (cid:88)    1 [  ( w )  V ] >  NL ( |  | ) (6) for  NL ( |  | ) = max { 3 ,  NL  |  |} , (7) with  NL  R being a hyperparameter. Similar to Equation 4,  NL depends on the number of discovered EDIT TREES , but is never smaller than 3 . We set this minimum to require evidence for at least two transformations in addition to the identity. We can now bootstrap by iteratively computing additional paradigm candidates and EDIT TREES , and then retrieving more lemmas. We denote the paradigm completion systems resulting from one and two such iterations as PCS-II-A and PCS-II-B , respectively. Since we cannot be fully confident about retrieved lemmas, we associate each additional lemma with a weight  (cid:96) =  it NL , where  NL is a preset hyperparameter and it identifies the iteration in which a lemma is added, i.e., it = 0 for gold lemmas and it = i for lemmas retrieved in the i th iteration. The weights  (cid:96) are used in later components of our system. Until now, we have assumed a one-to-one mapping between paradigm slots and surface form changes. However, different EDIT TREES may indeed represent the same inflection. For example, the past tense inflection of verbs in English involves multiple EDIT TREES , as shown in Figure 3. Thus, the next step is to group surface form changes based on the paradigm slots they realize. Our algorithm for grouping surface form changes is based on two assumptions. First, since EDIT TREES are extracted from ( (cid:96) , w ) pairs, different EDIT TREES belonging to the same paradigm slot cannot be extracted from the same lemma. 6 Thus: Assumption 1 For each lemma, at most one inflected form per paradigm slot can be found in the corpus. Formally, for a multi-to-one mapping from EDITTREES to paradigm slots z :    , we define the EDIT TREE set   of a potential paradigm slot  as   = {  | z (  ) =  } , with (cid:83)    =  . Then, for any lemma (cid:96)  L and proposed paradigm slot    , we have: |{ w  V |  ( (cid:96) ) = w      }|  1 . Our second assumption is a simplification, 7 but helps to reduce the search space during clustering: Formally, we partition  into disjoint subsets:      (cid:48) =    (cid:54) =  (cid:48) . 4.3.3 Paradigm Slot Features and Similarity In addition to Assumptions 1 and 2, we make use of a feature function r (  ) and a score function s ( r (  ) , r (  (cid:48) )) , which measures the similarity between two potential paradigm slots. Our feature function makes the connection between paradigm slots and the instances of inflected forms in the corpus by utilizing the part-of-speech (POS) tags as context information. In our implementation, we employ an unsupervised POS tagger 6 Exceptions to this do exist. However, they are rare enough that we do not expect them to hurt our algorithm. 7 This assumption ignores syncretism. 8 Note that this example is simplified. The system does not need to actually know the tags like PST and V . (cid:95)(cid:50)(cid:55)(cid:50)(cid:96)(cid:50)(cid:77)(cid:43)(cid:50)(cid:98) Figure 4: An example of the distributionally informed feature function with window size 3 for the past tense slot ( PST ). stop  L and f PST ( stop ) = stopped . When the sliding window arrives to this instance of stopped , (cid:126)r PST [ N , V , V ] is increased by 1 . 8 (Stratos et al., 2016) to extract tags for each word in the corpus D . Its values are computed as: (cid:126)r  (cid:104) p j 1 ,...,p j 2 d +1 (cid:105) = (cid:88) w i D 1 (cid:2) w i  V  (14)   p i  d = p j 1       p i + d = p j 2 d +1 (cid:3)  (cid:0)  p j 1 , . . . ,  p j 2 d +1 (cid:1)  P 2 d +1 . This tagger assigns an anchor word , i.e., a pseudo POS tag, to each word w i in the corpus by using an anchor hidden Markov model (HMM) with 8 hidden states. Our feature function counts the tag tuples within a sliding window centered on each instance of inflected forms of a potential paradigm slot. Formally, we denote the set of lemmas that surface form change  is applied to as L  , the set of lemmas that express a potential paradigm slot  as L  , and the corresponding inflected forms as V  : L  = { (cid:96)  L|  ( (cid:96) ) = w  w  V } (10) L  = (cid:91)     L  (11) V  = (cid:91)     {  ( (cid:96) ) } (cid:96) L  . (12) We further refer to the set of available POS tag labels as P = { p 1 , . . . , p 8 } . For a corpus D = w 1 , . . . , w |D| , a window size 2 d +1 , and a potential paradigm slot  , our feature function is defined as: (cid:126)r  = r (  ; D , 2 d + 1) , (13) where (cid:126)r  is a vector with one dimension for each possible tag tuple sequence of length 2d+1. In practice, we initialize (cid:126)r  to the zero vector, and iterate the sliding window over the corpus. When the central word w i  V  , the corresponding value of (cid:126)r  at the POS tuple within the sliding window is incremented by 1 . Figure 4 shows an example in English. We assume that paradigm slots  and  (cid:48) are similar if the words in V  and V  (cid:48) frequently appear in Algorithm 1: Surface Form Change Grouping Result:  , {   }    Initialize  s.t. |  | = |  | and f  i =  i for all  i   ; Initialize   i = {  i } for all  i   ; while  ( ,  (cid:48) ) s . similar contexts, i.e., within similar tag sequences. With the feature function defined above, our system uses cosine similarity as the score function s . We then develop Algorithm 1 to group one-to-one mappings from surface form changes to paradigm slots into many-to-one mappings. The idea is to iteratively merge the most similar slots if this is not violating Assumption 1 until the similarity gets too low. S  (0 , 1) is a threshold parameter. 9 4.4 Generation Now, one paradigm slot can be represented by multiple EDIT TREES . Our system, thus, needs to learn to apply the correct transformation for a combination of lemma and paradigm slot. However, mapping lemmas and paradigm slots to inflected forms corresponds exactly to the morphological inflection task, which has been the subject of multiple shared tasks over the last years (Cotterell et al., 2018). Our morphological inflection models take ( slot , lemma , word ) tuples extracted by the previous components of our system as training data. Formally, they are trained on the training set: (cid:8) ( (cid:126)t  , (cid:96), f  ( (cid:96) )) |     (cid:96)  L   f  ( (cid:96) )  V (cid:9) . 9 This does not result in a functional paradigm completion system, since we still lack a method to decide which surface form change to apply to realize a paradigm slot for a lemma. Affix Editing The baseline system of the CoNLLSIGMORPHON 2017 shared task 10 (Cot-terell et al., 2017) is a simple approach, which is very suitable for low-resource settings. The system breaks each word into PREFIX , STEM , and SUFFIX , and then stores the PREFIX editing rules and the STEM + SUFFIX editing rules. At test time, it applies the longest possible PREFIX and STEM + SUFFIX editing rules to the input lemma. We denote the surface form change grouping in combination with this system as PCS-III-C . Transducer-Based Hard-Attention We further experiment with a transducer-based hard-attention model (Makarov and Clematide, 2018a). Unlike widely used soft-attention sequence-to-sequence models (Bahdanau et al., 2015), which predict the target tokens directly, it predicts edit action sequences to transform the input sequence into outputs, and it disposes of a hard attention mechanism. We denote the surface form change grouping in combination with this system as PCS-III-H . To evaluate our approach in a real-world setting, we restrict our data to resources typically available to a field linguist: a small written corpus (  100k tokens) and a small lexicon. For our corpora, we use the JHU Bible Corpus (McCarthy et al., 2020), which allows future work to build systems in 1600 languages. The Bible is frequently available even in low-resource languages: Ethnologue identifies 3,995 written languages, and the New Testament has been translated into 2,246. The Bible is also highly representative of a language's core vocabulary : Resnik et al. (1999) find high overlap with both the Longman Dictionary of Contemporary English (Summers and Gadsby, 1995) and the Brown Corpus (Francis and Kucera, 1964). Furthermore, the Bible is multi-parallel and, thus, allows for a fair comparison across languages without confounds like domain. For evaluation of our methods only, we additionally obtain ground-truth morphological paradigms from UniMorph (Kirov et al., 2018), which provides paradigms for over 100 languages. From the intersection of languages in the Bible and UniMorph, we select 14 typologically diverse 10 https://github.com/sigmorphon/conll2017/ tree/master/baseline languages from 7 families, each of which display inflectional morphology: Basque ( EUS ), Bulgarian ( BUL ), English ( ENG ), Finnish ( FIN ), German ( DEU ), Kannada ( KAN ), Navajo ( NAV ), Spanish ( SPA ), and Turkish ( TUR ) as test languages, and Maltese ( MLT ), Persian ( FAS ), Portuguese ( POR ), Russian ( RUS ), and Swedish ( SWE ) for development. To create test data for all and development data for our development languages, we sample 100 paradigms for each set from UniMorph, then take their lemmas as our lexicon L . 11 5.2 Baselines and Skylines Lemma Baseline (LB) Our first, trivial baseline predicts inflected forms identical to the lemma for all paradigm slots. We compare to one version of this baseline that has access to the ground-truth paradigm size ( LB-Truth ), and a second version which predicts the paradigm size as the average over the development languages ( LB-Dev ). One/Ten-Shot Inflection Model Our second baseline could be seen as a skyline , since it leverages morphological information our proposed system does not have access to. In particular, we train the baseline system of CoNLLSIGMORPHON 2017 (Cotterell et al., 2017) on one ( CoNLL17-1 ) and ten ( CoNLL17-10 ) paradigms. For this, we randomly sample paradigms from UniMorph, excluding those in our test data. We choose the hyperparameters by grid search over intuitively reasonable ranges, using the development languages. No test language data is seen before final testing. Note also that only the corpus and the lexicon can be accessed by our system, and no ground-truth morphological information (including paradigm size) is given. Our final hyperparameters are  P = 0 . 5 ,  FC = 0 . 05 ,  NL = 0 . 2 ,  NL = 0 . 5 , and  S = 0 . 3 . The window size 2 d +1 for feature extraction is set to 3 . For CoNLL17-1 , we average over the results for 10 different sampled paradigms for each language. Systems for supervised or semi-supervised paradigm completion are commonly being evaluated using word-level accuracy (Dreyer and Eisner, 2011; Cotterell et al., 2017). However, this is not 11 For Basque, Kannada, and Maltese, we only take 20 paradigms for each set, due to limited availability. possible for our task because our system cannot access the gold data paradigm slot descriptions and, thus, does not necessarily produce one word for each ground-truth inflected form. Furthermore, the system outputs pseudo-tags, and the mapping from pseudo-tags to paradigm slots is unknown. Therefore, we propose to use best-match accuracy (BMAcc), the best accuracy among all mappings from pseudo-tags to paradigm slots, for evaluation. Let  = {  i } Ni =1 and  = {   j } Mj =1 be the set of all paradigm slots in the ground truth and the prediction, respectively, with transformation functions f :         {} and  f :        , 12 where f  ( (cid:96) ) =  if the corresponding inflection is missing in the ground truth. 13 We define two types of BMAcc: Macro-averaged BMAcc This is the average per-slot accuracy for the best possible matching of slots. For any  i ,   j , we define g t ( L ,  i ,   j ) as the number of correct guesses (true positives) if   j maps to  i , g a ( L ,  i ) as the number of ground truth inflections for  i , and acc ( L ,  i ,   j ) as the per-slot accuracy: g t ( L ,  i ,   j ) = |{ (cid:96)  L | f  i ( (cid:96) ) =  f  j ( (cid:96) ) (cid:54) = }| g a ( L ,  i ) = |{ (cid:96)  L | f i ( (cid:96) ) (cid:54) = }| , (16) and acc ( L ,  i ,   j ) = g t ( L ,  i ,   j ) g a ( L ,  i ) . Then, we construct a complete bipartite graph with  and  as two sets of vertices and acc ( L ,  i ,   j ) as edge weights. The maximum-weight full matching can be computed efficiently with the algorithm of Karp (1980). With such a matching M = { (  m ,   m ) } min { N,M } m =0 , the macro-averaged BMAcc is defined as: BMAcc-macro ( L ,  ,  ) (18) = (cid:80) (  m ,   m ) M acc ( L ,  m ,   m ) max { N, M } The normalizing factor 1 max { N,M } rewards predicting the correct number of paradigm slots. In the case when acc ( L ,  m ,   m ) = 1 for all (  m ,   m )  M , BMAcc-macro ( L ,  , ) reaches its maximum if and only if N = M . 12 These are equivalent to our definition in  3, since the system does not need to predict the inflectional features. 13 In practice, we merge paradigm slots that are identical for all lemmas in both the predictions and gold standard before evaluating. Micro-averaged BMAcc Our second metric is conceptually closer to word-level accuracy. We start with the same process of bipartite graph matching, but instead use g t ( L ,  i ,   j ) as edge weights. Given the optimal matching M , the micro-averaged BMAcc is defined as: BMAcc-micro ( L ,  , ) = N max { N, M } (cid:80) (  m ,   m ) M g t ( L ,  m ,   m ) (cid:80)  i   g a ( L ,  i ) . Overall Results We present our experimental results in Table 1. The performance of our system varies widely across languages, with best results for ENG ( 74% BMAcc). On average over languages, our final system obtains 18 . 76% / 19 . 06% BMAcc on the test set, as compared to the baseline of 4 . 94% / 5 . 25% and skylines of 18 . 70% / 18 . 70% and 35 . 58% / 35 . 56% . Compared to versions of our system without selected components, our final system performs best on average for both development and test languages. Leaving out step II or step III leads to a reduction in performance. Notably, variants of our system outperform the skyline CoNLL17-1, which has seen one training example and, thus, knows the correct paradigm size in advance, on EUS , BUL , ENG , FIN , KAN , NAV , TUR , MLT , RUS , and SWE . Moreover, it even outperforms CoNLL17-10 on EUS , ENG , and NAV , which shows that unsupervised paradigm completion has promise even in cases where a limited number of training examplesbut not large amounts are available. Differences between Languages We hypothesize that the large differences between languages over 73% between EUS and ENG can be explained in parts by the following reasons: Intuitively, the larger the paradigm, the more difficult the task. If the number of slots is huge, each individual inflection is rare, and it is hard for any unsupervised paradigm completion system to distinguish true inflections (e.g., rise  rises ) from false candidates (e.g., rise  arise ). This could explain the high performance on ENG and the low performance on EUS , FIN , and FAS . Related to the last point, in a limited corpus such as the Bible, some inflected forms might not appear for any lemma, which makes them undetectable for unsupervised paradigm completion systems. For example, a FAS paradigm has 136 slots in UniMorph, but only 46 are observed. 14 Additional statistics can be found in Table 2. Furthermore, Assumption 2 does not hold for all languages. Surface forms can be shared between paradigm slots, as, for instance, in English for he studied and he has studied . Different languages 14 We had to estimate that number based on available data in UniMorph: a slot is considered observed if at least one inflected form for that slot can be found. Pipeline Effects Different combinations of components result in major performance differences. In particular, each step of our system has the potential to introduce errors. This demonstrates a pitfall of pipeline methods also discussed in McCarthy et al. (2020): the quality of individual steps, here, e.g., EDIT TREE discovery and retrieval of additional lemmas, can greatly affect the results of PCS-II and PCS-III. Differences in Components Details of individual components also affect the results. On the one hand, applying more than one iteration of additional lemma retrieval impacts the results only slightly, as those lemmas are assigned very small weights. On the other hand, we see performance differences > 2% between PCS-III-C and PCS-III-H for DEU , MLT , and SWE . Analysis of EDITTREE Quality As it is the first step in our pipeline, the quality of the EDIT TREE discovery strongly affects the performance of later components. For our development languages, we show in Table 2 the percentage of ( (cid:96), w ) pairs for which the system predicts an EDIT TREE  such that  ( (cid:96) ) = w appears in the gold paradigm of (cid:96) . This corresponds to the highest possible performance after PCS-I. FAS has the worst performance ( 12 . 10% ), while the results for SWE are high ( 72 . 91% ). As expected, languages with lower values here also obtain lower final results. Analysis of Syncretism We further hypothesize that syncretism could be a source of errors, due to Assumption 2. Table 2 shows the percentage of words that are the inflected forms corresponding to multiple paradigm slots of the same lemma. We observe that SWE has a low degree of syncretism, and, in fact, our system predicts the correct paradigm size for SWE . A high degree of syncretism, in contrast, might contribute to the low performance on MLT . We proposed unsupervised morphological paradigm completion , a novel morphological generation task. We further developed a system for the task, which performs the following steps: (i) EDIT TREE retrieval, (ii) additional lemma retrieval, (iii) paradigm size discovery, and (iv) inflection generation. Introducing best-match accuracy, a metric for the task, we evaluated our system on a typologically diverse set of 14 languages. Our system obtained promising results for most of our languages and even outperformed a minimally supervised baseline on Basque, English, and Navajo. Further analysis showed the importance of our individual components and detected possible sources of errors, like wrongly identified EDIT TREES early in the pipeline or syncretism. In the future, we will explore the following directions: (i) A difficult challenge for our proposed system is to correctly determine the paradigm size. Since transfer across related languages has shown to be beneficial for morphological tasks (Jin and Kann, 2017; McCarthy et al., 2019; Anastasopoulos and Neubig, 2019, inter alia ), future work could use typologically aware priors to guide the number of paradigm slots based on the relationships between languages. (ii) We plan to explore other methods, like word embeddings, to incorporate context information into our feature function. (iii) We aim at developing better performing string transduction models for the morphological inflection step. By substituting the current transducers in our pipeline, we expect that we will be able to improve the overall performance of our system. We are grateful to the group of SIGMORPHON 2020 shared task organizers as well as Alexander Erdmann for discussions about our proposed task in summer 2019. Special thanks go to Mans Hulden, who was the first to suggest an initial version of the task, and to Jason Eisner, the president of SIGMORPHON. Last but not least, we also thank Clara Vania and the anonymous reviewers for their helpful comments on this work.
objective abstain abstain abstain method abstain abstain abstain abstain method result abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain method abstain abstain objective objective result abstain abstain abstain abstain abstain method objective result objective other other other other objective other other method other other other abstain other objective abstain other other other other abstain method other method abstain abstain method abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain method method method abstain abstain abstain abstain abstain abstain method abstain method abstain method method method abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain method abstain abstain method method abstain abstain method abstain method abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain result other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain other abstain abstain other abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective objective abstain abstain abstain abstain method result result objective objective abstain objective objective result other other other