The Paradigm Discovery Problem (2020)

Abstract: This work treats the paradigm discovery problem (PDP), the task of learning an inflectional morphological system from unannotated sentences. We formalize the PDP and develop evaluation metrics for judging systems. Using currently available resources, we construct datasets for the task. We also devise a heuristic benchmark for the PDP and report empirical results on five diverse languages. Our benchmark system first makes use of word embeddings and string similarity to cluster forms by cell and by paradigm. Then, we bootstrap a neural transducer on top of the clustered data to predict words to realize the empty paradigm slots. An error analysis of our system suggests clustering by cell across different inflection classes is the most pressing challenge for future work.

## introduction in childhood, we induce our native language's morphological system from unannotated input. for instance, we learn that ring and rang belong to the same inflectional paradigm. we also learn that rings and bangs belong to the same cell, i.e., they realize the same morphosyntactic properties 3.sg.pres, but in different paradigms. acquiring such paradigmatic knowledge enables us to produce unseen inflectional variants of new vocabulary items, i.e. to complete morphological paradigms. much work has addressed this task, which @xcite call the paradigm cell filling problem (pcfp), foot_0 but few have discussed inducing paradigmatic knowledge from scratch, which we call the paradigm discovery problem (pdp). 2 as an unsupervised task, the pdp poses challenges for modeling and evaluation and has yet to be attempted in its full form @xcite . however, we contend there is much to be gained from formalizing and studying the pdp. there are insights for cognitive modeling to be won @xcite and intuitions on combating sparse data for language generation @xcite to be accrued. unsupervised language processing also has natural applications in the documentation of endangered languages @xcite where a lot of annotated data is never likely to exist. our formalization of the pdp offers a starting point for future work on unsupervised morphological paradigm completion. our paper presents a concrete formalization of the pdp. then, as a baseline for future work, we introduce a heuristic benchmark system. our benchmark system takes an unannotated text corpus and a lexicon of words from the corpus to be analyzed. it first clusters the lexicon by cell and then by paradigm making use of distributional semantics and string similarity. finally, it uses this clustering as silver-standard supervision to bootstrap a neural transducer @xcite that generates the desired target inflections. that is, the model posits forms to realize unoccupied cell slots in each proposed paradigm. even though our benchmark system models only one part of speech (pos) at a time, our framework extends to the full pdp to support future, more intricate systems. we propose two separate metrics to evaluate both the clustering of attested forms into paradigms and cells and the prediction of unseen inflected forms. our metrics handle non-canonical morphological behavior discussed in theoretical literature @xcite and extend to the full pdp. for three of the five languages we consider, our benchmark system predicts unattested inflections one of its subtasks which @xcite call the paradigm cell finding problem (see §2.2). ## previous work in morphology this section couches our work on the pdp in terms of previous trends in morphological modeling. ## the paradigm discovery problem paradigm discovery is a natural next step in computational morphology, building on related minimally or indirectly supervised works ( §2.2) to bridge the gap between unsupervised traditions ( §2.1) and supervised work on the pcfp ( §2.3). in the pcfp, ## building a benchmark this section presents a benchmark system for proposing a morphologically organized grid given a corpus and lexicon. first, we cluster lexicon forms into cells. then we cluster forms into paradigms given their fixed cell membership. to maintain tractability, clustering assumes a one-to-one mapping of forms to slots. following cell and paradigm clustering, we predict forms to realize empty slots given one of the lexicon forms assigned to a cell in the same paradigm. this allows forms to appear in multiple slots, but does not support overabundance, defectiveness, or multi-word inflections. ## results and discussion as for the pcfp, our benchmark system does well on lexicon expansion accuracy and poorly on the analogy task. while lexicon expansion accuracy (50-86% compared to 72-97% for sup) shows that the benchmark captures meaningful inflectional trends, analogy accuracy demonstrates vast room for improvement in terms of consistently organizing cell-realizations across paradigms. english is the only language where analogy accuracy is within half of sup's upper bound. a major reason for low analogy accuracy is that forms, despite being clustered into paradigms well, get assigned sg pl nom gen dat acc abl nom gen dat acc abl gloss serv-us i o um o i orum is os is "slave.m" serv-a ae ae am a ae arum is as is "slave.f" frat-er ris ri rem re res rum ribus res ribus "brother" to the wrong cell, or the same gold cell gets misaligned across paradigms from different inflection classes. we discuss this phenomenon in more detail below. ## conclusion we present a framework for the paradigm discovery problem, in which words attested in an unannotated corpus are analyzed according to the morphosyntactic property set they realize and the paradigm to which they belong. additionally, unseen inflectional variants of seen forms are to be predicted. we discuss the data required to undertake this task, a benchmark for solving it, and multiple evaluation metrics. we believe our benchmark system represents a reasonable approach to solving the problem based on past work and highlights many directions for improvement, e.g. joint modeling and making better use of distributional semantic information.