Searching for Search Errors in Neural Morphological Inflection (2021)

Abstract: Neural sequence-to-sequence models are currently the predominant choice for language generation tasks. Yet, on word-level tasks, exact inference of these models reveals the empty string is often the global optimum. Prior works have speculated this phenomenon is a result of the inadequacy of neural models for language generation. However, in the case of morphological inflection, we find that the empty string is almost never the most probable solution under the model. Further, greedy search often finds the global optimum. These observations suggest that the poor calibration of many neural models may stem from characteristics of a specific subset of tasks rather than general ill-suitedness of such models for language generation.

## introduction neural sequence-to-sequence models are omnipresent in the field of natural language processing due to their impressive performance. they hold state of the art on a myriad of tasks, e.g., neural machine translation (nmt; @xcite and abstractive summarization (as; @xcite . yet, an undesirable property of these models has been repeatedly observed in word-level tasks: when using beam search as the decoding strategy, increasing the beam width beyond a size of @xmath0. further, in the context of nmt, it has been shown that the empty string is frequently the most-probable solution under the model @xcite . some suggest this is a manifestation of the general inadequacy of neural models for language generation tasks @xcite @xcite ; in this work, we find evidence demonstrating otherwise. sequence-to-sequence transducers for characterlevel tasks often follow the architectures of their word-level counterparts @xcite , and have likewise achieved state-of-the-art performance on e.g., morphological inflection generation @xcite and grapheme-to-phoneme conversion @xcite . given prior findings, we might expect to see the same degenerate behavior in these models-however, we do not. we run a series of experiments on morphological inflection (mi) generators to explore whether neural transducers for this task are similarly poorly calibrated, i.e. are far from the true distribution p(y | x). we evaluate the performance of two character-level sequenceto-sequence transducers using different decoding strategies; our results, previewed in tab. 1, show that evaluation metrics do not degrade with larger beam sizes as in nmt or as. additionally, only in extreme circumstances, e.g., low-resource settings with less than 100 training samples, is the empty string ever the global optimum under the model. our findings directly refute the claim that neural architectures are inherently inadequate for modeling language generation tasks. instead, our results admit two potential causes of the degenerate behavior observed in tasks such as nmt and as: (1) lack of a deterministic mapping between input and output and (2) a (perhaps irreparable) discrepancy between sample complexity and training resources. our results alone are not sufficient to accept or reject either hypothesis, and thus we leave these as future research directions. ## neural transducers sequence-to-sequence transduction is the transformation of an input sequence into an output sequence. tasks involving this type of transformation are often framed probabilistically, i.e., we model the probability of mapping one sequence to another. on many tasks of this nature, neural sequence-tosequence models @xcite hold state of the art. formally, a neural sequence-to-sequence model defines a probability distribution p θ (y | x) parameterized by a neural network with a set of learned weights θ for an input sequence @xmath1, x 2 , . . . and output sequence @xmath2, y 2 , . . . . morphological inflection and nmt are two such tasks, wherein our outputs are both strings. neural sequence-to-sequence models are typically locally normalized, i.e. p θ factorizes as follows: given a vocabulary v, each conditional p θ is a distribution over v ∪ {eos} and y 0 := bos. we consider p θ (y | x) to be well-calibrated if its probability estimates are representative of the true likelihood that a solution y is correct. ## decoding in the case of probabilistic models, the decoding problem is the search for the most-probable sequence among valid sequences v * under the model p θ : this problem is also known as maximum-aposteriori (map) inference. decoding is often performed with a heuristic search method such as greedy or beam search @xcite , since performing exact search can be computationally expensive, if not impossible. 2 while for a deterministic task, greedy search is optimal under a bayes optimal model, 3 most text generation tasks benefit from using beam search. however, text quality almost invariably decreases for beam sizes larger than @xmath3. this phenomenon is sometimes referred to as the beam search curse, and has been investigated in detail by a number of scholarly works @xcite @xcite @xcite . exact decoding can be seen as the case of beam search where the beam size is effectively stretched to infinity. 4 by considering the complete search space, it finds the globally best solution under the model p θ . while, as previously mentioned, exact search can be computationally expensive, we can employ efficient search strategies due to some properties of p θ . specifically, from eq. ( 1 ), we can see that the scoring function for sequences y is monotonically decreasing in t. we can therefore find the provably optimal solution with dijkstra's algorithm @xcite , which terminates and returns the global optimum the first time it encounters an eos. additionally, to prevent a large memory footprint, we can lower-bound the search using any complete hypothesis, e.g., the empty string or a solution found by beam search @xcite . that is, we can prematurely stop exploring solutions whose scores become less than these hypotheses at any point in time. although exact search is an exponential-time method in this setting, we see that, in practice, it terminates quickly due to the peakiness of p θ (see app. a). while the effects of exact decoding and beam search decoding with large beam widths have been explored for a number of word-level tasks @xcite @xcite , to the best of our knowledge, they have not yet been explored for any character-level sequence-to-sequence tasks. ## experiments we run a series of experiments using different decoding strategies to generate predictions from morphological inflection generators. we report results for two near-state-of-the-art models: a multilingual transformer @xcite and a (neuralized) hidden markov model (hmm; @xcite . for reproducibility, we mimic their pro4 this interpretation is useful when comparing with beam search with increasing beam widths. data. we use the data provided by the sigmor-phon 2020 shared task @xcite , which features lemmas, inflections, and corresponding msds in the unimorph schema @xcite in 90 languages in total. the set of languages is typologically diverse (spanning 18 language families) and contains both high-and low-resource examples, providing a spectrum over which we can evaluate model performance. the full dataset statistics can be found on the task homepage. 6 when reporting results, we consider languages @xmath4, respectively. decoding strategies. we decode morphological inflection generators using exact search and beam search for a range of beam widths. we use the sgnmt library for decoding @xcite albeit adding dijkstra's algorithm. ## discussion our findings admit two potential hypotheses for poor calibration of neural models in certain language generation tasks, a phenomenon we do not observe in morphological inflection. first, the tasks in which we observe this property are ones that lack a deterministic mapping, i.e. tasks for which there may be more than one correct solution for any given input. as a consequence, probability mass may be spread over an arbitrarily large number of hypotheses @xcite . in contrast, the task of from this example, we can conjecture that lack of sufficient training data may manifest itself as the (relatively) high probability of the empty string or the (relatively) low probability of the optimum. we can extrapolate to models for nmt and other word-level tasks, for which we frequently see the above phenomenon. specifically, our experiments suggest that when neural language generators frequently place high probability on the empty string, there may be a discrepancy between the available training resources and the number of samples needed to successfully learn the target function. while this at first seems an easy problem to fix, we expect the number of resources needed in tasks such as nmt and as is much larger than that for mi if not due to the size of the output space alone; perhaps so large that they are essentially unattainable. under this explanation, for certain tasks, there may not be a straightforward fix to the degenerate behavior observed in some neural language generators. ## conclusion in this work, we investigate whether the poor calibration often seen in sequence-to-sequence models for word-level tasks also occurs in models for morphological inflection. we find that character-level models for morphological inflection are generally well-calibrated, i.e. the probability of the globally best solution is almost invariably much higher than that of the empty string. this suggests the degenerate behavior observed in neural models for certain word-level tasks is not due to the inherent incompatibility of neural models for language generation. rather, we find evidence that poor calibration may be linked to specific characteristics of a subset of these task, and suggest directions for future exploration of this phenomenon.