Frugal Paradigm Completion (2020)

Abstract: Lexica distinguishing all morphologically related forms of each lexeme are crucial to many language technologies, yet building them is expensive. We propose a frugal paradigm completion approach that predicts all related forms in a morphological paradigm from as few manually provided forms as possible. It induces typological information during training which it uses to determine the best sources at test time. We evaluate our language-agnostic approach on 7 diverse languages. Compared to popular alternative approaches, ours reduces manual labor by 16-63% and is the most robust to typological variation.

## introduction from syntactic parsing @xcite to text-to-speech @xcite , many linguistic technologies rely on accurate lexica decorated with morphological information. yet, building such lexica requires much human effort @xcite @xcite @xcite . we present a language-agnostic method for minimizing the manual labor required to add new paradigms to an existing lexicon. formally, let each lexicon entry, or realization, be a triple (p, c, f ). p marks membership in some paradigm p of morphologically related words, c defines a cell in p as a bundle of morphosyntactic features, and f is the form realizing c in p. hence, paradigm sing can be expressed (in the unimorph schema @xcite ) as a set of realizations: {(sing, nfin, sing), (sing, 3.sg.pres, sings), . . . }. for each paradigm to be added to the lexicon, e.g., fly, we aim to select as few sources as pos-sible to be manually realized, e.g., {(fly, nfin, fly), (fly, pst, flew)} such that the forms realizing the remaining cells can be predicted, i.e., flies, flying, flown. here, sources are manually provided realizations. targets are realizations whose forms must be predicted from sources. our work differs from traditional paradigm completion @xcite in that sources are not given blindly, but the system must strategically select which sources it wants to be given at test time. paradigm completion from one source is typically non-deterministic due to multiple inflection classes realizing different exponents in some cells, e.g., suffixing +ed generates the past tense for walk, but not for sing or fly which are members of different classes. hence, many works discuss paradigm completion in the context of (implicit) inflection class disambiguation @xcite @xcite . @xcite propose three approaches to select the fewest sources required to deterministically identify class. yet, neural sequence models can often complete paradigms accurately from less sources without fully disambiguating inflection class @xcite @xcite . @xcite for an overview of the application of neural sequence models to morphological theory. we propose frugal paradigm completion (fpc), inspired by work on inflection class disambiguation and neural sequence modeling. we train a source selection agent (ssa) to induce typological knowledge regarding the distribution of complexity in paradigms and use this to request informative source cells to be realized by an oracle. sources are fed to a predictor to generate target forms. for each paradigm, ssa iteratively requests sources until the oracle confirms all cells have been realized correctly. we introduce a novel metric, auto-rate, to quantify the manual labour (performed by the oracle) needed to complete each paradigm. using this metric, we demonstrate that fpc reduces labor by 63% over predicting targets from lemmata, and 47% over predicting them from the smallest set of sources that fully disambiguates inflection class. we propose a new typology for discussing the organization of complexity in paradigms which helps explain why strategies perform better or worse on certain languages while fpc, being sensitive to typological variation, performs robustly. after discussing related paradigm completion approaches in section 2, we describe fpc in section 3. section 4 covers all data and experimental set up details. we discuss results in section 5 and analyze fpc's behavior in section 6. ## paradigm completion approaches here we discuss several paradigm completion approaches related to fpc. ## frugal paradigm completion this section describes the interactions of the three fpc components. as illustrated in figure 1 , the predictor takes a source cell and its realizing form as input, e.g., 3.sg.pres: sings, or cell 2: form 2 in the figure. the predictor is composed of as many sub-predictors as there are cells in the paradigm, each of which is trained to predict the entire paradigm from one source cell's realization. cell 2 in the paradigm is grayed out in the figure, as this was provided as input so it does not have to be predicted. the predicted paradigm is evaluated by the oracle. if there are no errors, we are done. otherwise, based on previous sources, ssa chooses a new cell to be realized by the oracle and gives it to the predictor as the next source. because cell 3 is chosen in the figure, sub-predictor 3 will be used to predict the paradigm going forward, and cells 2 and 3 will both be grayed out. the process continues like this until all cells have been correctly predicted by at least one sub-predictor. crucially, during inference, each test paradigm is empty, i.e., no realization has been seen during training and no source is available to inflect from a-priori. our setup aims to minimize the number of sources which the ssa must request from the oracle (typically a human in the loop at inference time) to predict the remaining paradigm slots correctly. ## experimental details we evaluate 4 paradigm completion approaches on 7 languages. here we discuss implementation, data and evaluation details. ## results and discussion as shown in ## analysis here, we discuss patterns relating ssa's first and second sources chosen (figures 3a-b and 4a-b ) to the inter-predictability of cells represented by heat maps (3c and 4c). maps display the average accuracies with which each target (column) can be predicted from each source (row). we analyze specific ssa choices and predictor errors in arabic and latin. the maps (for all languages, see the appendix) suggest complexity can be distributed within paradigms in systematically distinct ways. @xcite propose integrative (i-) complexity, using average conditional entropy to describe paradigmatic organization, but this has been criticized for obscuring differences in the predictability of sub-paradigm regions @xcite . to remedy this, we propose a typology for measuring the extent to which i-complexity is realized via different organizational strategies, which is useful for discussing source selection strategies. our typology describes paradigms in terms of mutual predictability, the correlation of a map and its transpose, and entropy predictiveness, the negative correlation of cells' average predictiveness (see equation 1) and average predictability, defined here in comparable terms as: intuitively, a paradigm is mutually predictable if the fact that cell a predicts cell b means that b is likely to predict a. such paradigms often feature regions of mutually predictable cells (as in 3c), such that an optimal strategy avoids picking multiple sources from one region. for entropy predictive paradigms, if a is generally more difficult to predict than b, a is likely to be a better predictor of the remaining cells (following the information theoretic logic that surprisal is informative @xcite ). for such paradigms, the optimal strategy selects the source which would have been the most difficult target to predict. unlike sims (2020)'s graph-theoretic typology for describing inflection class structure, our typology is a two-dimensional description of how the optimal paradigm completion strategy is affected by underlying class structure. in this sense, our typology is complementary to hers and future work might investigate the relationship between traits in her typology and mutual predictability or entropy predictiveness. furthermore, our typology might be updated to consider the impact of type frequency @xcite in a framework where distributional data is available. figure 5 demonstrates that cross-linguistic variation is vast with respect to our typology, as some languages even exhibit negative entropy predictiveness or mutual predictability. this partly explains why non-fpc approaches perform erratically: if paradigmatic organization varies by language, source selection strategies must be able to adapt to the data. ## conclusion we presented frugal paradigm completion, which reduces the manual labor required to expand a morphological lexicon by 16-63% over competitive approaches across 7 languages. we demonstrated that typologically distinct morphological systems require unique treatment and benefit from our ssa, that learns its strategy from data. we found that inducing this strategy is not as challenging as previously suggested @xcite . thus, ssa might be replaced with a less costly architecture while our model might be improved by conditioning on semantics and jointly decoding from a variable number of sources.