Smoothing and Shrinking the Sparse S eq2 S eq Search Space (2021)

Abstract: Current sequence-to-sequence models are trained to minimize cross-entropy and use softmax to compute the locally normalized probabilities over target sequences. While this setup has led to strong results in a variety of tasks, one unsatisfying aspect is its length bias: models give high scores to short, inadequate hypotheses and often make the empty string the argmax—the so-called cat got your tongue problem. Recently proposed entmax-based sparse sequence-to-sequence models present a possible solution, since they can shrink the search space by assigning zero probability to bad hypotheses, but their ability to handle word-level tasks with transformers has never been tested. In this work, we show that entmax-based models effectively solve the cat got your tongue problem, removing a major source of model error for neural machine translation. In addition, we generalize label smoothing, a critical regularization technique, to the broader family of Fenchel-Young losses, which includes both cross-entropy and the entmax losses. Our resulting label-smoothed entmax loss models set a new state of the art on multilingual grapheme-to-phoneme conversion and deliver improvements and better calibration properties on cross-lingual morphological inflection and machine translation for 7 language pairs.

## introduction sequence-to-sequence models (seq2seq: @xcite @xcite have become a powerful and flexible tool for a variety of nlp tasks, including machine translation (mt), morphological inflection (mi; @xcite , and grapheme-to-phoneme conversion (g2p; @xcite . these models often perform well, but they have a bias that favors short hypotheses. this bias is problematic: it has been pointed out as the cause @xcite @xcite of the beam search curse, in which increasing the width of beam search actually decreases performance on neural machine translation (nmt). further illustrating the severity of the problem, @xcite showed that the highest-scoring target sequence in nmt is often the empty string, a phenomenon they dubbed the cat got your tongue problem. these results are undesirable because they show that nmt models' performance depends on the search errors induced by a narrow beam. it would be preferable for models to assign higher scores to good translations than to bad ones, rather than to depend on search errors to make up for model errors. the most common way to alleviate this shortcoming is by altering the decoding objective @xcite @xcite , but this does not address the underlying problem: the model overestimates the probability of implausible hypotheses. other solutions use alternate training strategies @xcite , but it would be preferable not to change the training algorithm. in this paper, we propose a solution based on sparse seq2seq models @xcite , which replace the output softmax @xcite with the entmax transformation. entmax, unlike softmax, can learn locally sparse distributions over the target vocabulary. this allows a sparse model to shrink the search space: that is, it can learn to give inadequate hypotheses zero probability, instead of counting on beam search to prune them. this has already been demonstrated for mi, where the set of possible hypotheses is often small enough to make beam search exact @xcite . we extend this analysis to mt: although exact beam search is not possible for this large vocabulary task, we show that entmax models prune many inadequate hypotheses, effectively solving the cat got your tongue problem. despite this useful result, one drawback of ent-max is that it is not compatible with label smoothing @xcite , a useful regularization technique that is widely used for transformers @xcite . we solve this problem by generalizing label smoothing from the crossentropy loss to the wider class of fenchel-young losses @xcite , which includes the entmax loss as a particular case. we show that combining label smoothing with entmax loss improves results on both character-and word-level tasks while keeping the model sparse. we note that, although label smoothing improves calibration, it also exacerbates the cat got your tongue problem regardless of loss function. to sum up, we make the following contributions: 1 a seq2seq model learns a probability distribution p θ (y | x) over sequences y from a target vocabulary v , conditioned on a source sequence x. this 1 our code is available at https://github.com/ deep-spin/s7 . this factorization implies that the probability of a hypothesis being generated is monotonically nonincreasing in its length, which favors shorter sequences. this phenomenon feeds the beam search curse because short hypotheses foot_0 are pruned from a narrow beam but survive a wider one. the conditional distribution p θ (y i | x, @xmath0, @xmath1, where f θ is parameterized by a neural network, and then applying a transformation π : r |v | → |v | , which maps scores to the probability simplex |v | := {@xmath2: @xmath3, p 1 = 1}. the usual choice for π is softmax @xcite , which returns strictly positive values, ensuring that all @xmath4. coupled with the short sequence bias, this causes significant model error. sparse seq2seq models. in a sparse model, the output softmax is replaced by a transformation π from the entmax family @xcite . like softmax, entmax transformations return a vector in the simplex and are differentiable (almost) everywhere. however, unlike softmax, they are capable of producing sparse probability distributions. concretely, this is done by using the so-called "βexponential function" @xcite in place of the exponential, where β ≥ 0: entmax transformations are sparse for any α > 1, with higher values tending to produce sparser outputs. this sparsity allows a model to assign exactly zero probability to implausible hypotheses. for tasks where there is only one correct target sequence, this often allows the model to concentrate all probability mass into a small set of hypotheses, making search exact @xcite . this is not possible for open-ended tasks like machine translation, but the model is still locally sparse, assigning zero probability to many hypotheses. these hypotheses will never be selected at any beam width. fenchel-young losses. inspired by the softmax generalization above, @xcite provided a tool for constructing a convex loss function. let ω : |v | → r be a strictly convex regularizer which is symmetric, i.e., ω(πp) = ω(p) for any permutation π and any @xmath5. 3 equipped with ω, we can define a regularized prediction function πω : r |v | → |v | , with this form: the name stems from the fenchel-young inequality, which states that the quantity (7) is nonnegative (borwein and lewis, 2010, prop. 3.3.4). when ω is the generalized negative entropy, the loss (7) becomes the kullback-leibler divergence between q and softmax(z) (kl divergence; @xcite , which equals the crossentropy when q is a one-hot vector. more generally, if ω ≡ ω α is the negative tsallis entropy (6), we obtain the α-entmax loss @xcite . fenchel-young losses have nice properties for training neural networks with backpropagation: they are non-negative, convex, and differentiable as long as ω is strictly convex @xcite 2). their gradient is ## fenchel-young label smoothing label smoothing @xcite has become a popular technique for regularizing the output of a neural network. the intuition behind it is that using the gold target labels from the training set can lead to overconfident models. to overcome this, label smoothing redistributes probability mass from the gold label to the other target labels. when the redistribution is uniform, @xcite and @xcite pointed out that this is equivalent (up to scaling and adding a constant) to adding a second term to the loss that computes the kl divergence d kl (u p θ ) between a uniform distribution u and the model distribution p θ . while it might seem appealing to add a similar kl regularizer to a fenchel-young loss, this is not possible when p θ contains zeroes because the kl divergence term becomes infinite. this makes vanilla label smoothing incompatible with sparse models. fortunately, there is a more natural generalization of label smoothing to fenchel-young losses. @xmath6, 1], we define the fenchel-young label smoothing loss as follows: the intuition is the same as in cross-entropy label smoothing: the target one-hot vector is mixed with a uniform distribution. this simple definition leads to the following result, proved in appendix a: proposition 1. the fenchel-young label smoothing loss can be written as the first expression (11) shows that, up to a constant, the smoothed fenchel-young loss equals the original loss plus a linear regularizer (z y * -z). while this regularizer can be positive or negative, we show in appendix a that its sum with the original loss l ω (z, e y * ) is always non-negative -intuitively, if the score z y * is below the average, resulting in negative regularization, the unregularized loss will also be larger, and the two terms balance each other. figure 2 shows the effect of this regularization in the graph of the loss -we see that a correct prediction is linearly penalized with a slope of ; the larger the confidence, the larger the penalty. in particular, when ω is the shannon negentropy, this result shows a simple expression for vanilla label smoothing which, to the best of our knowledge, is novel. the second expression (12) shows that it can also be seen as a form of regularization towards the uniform distribution. when -ω is the shannon entropy, the regularizer becomes a kl divergence and we obtain the interpretation of label smoothing for cross-entropy provided by @xcite and @xcite . therefore, the same interpretation holds for the entire fenchel-young family if the regularization uses the corresponding fenchel-young loss with respect to a uniform. ## experiments we trained seq2seq models for three tasks: multilingual g2p, crosslingual mi, and mt. these tasks present very different challenges. in g2p and mi, character-level vocabularies are small and there is usually only one correct target sequence. the relative simplicity of these tasks is offset by the small quantity of training data and the strict evaluation: the model must produce exactly the right sequence. this tests fenchel-young label smoothing's ability to learn exactly in a low-resource setting. on the other hand, mt is trained with much larger corpora and evaluated with less strict metrics, but uses subword vocabularies with sizes in the tens of thousands and has to manage more ambiguity because sentences typically have many correct translations. in all tasks, we vary two hyperparameters: we trained all models with early stopping for a maximum of 30 epochs for mi, 15 epochs for wmt 2014 @xmath7, and 100 epochs otherwise, keeping the best checkpoint according to a task-specific validation metric: phoneme error rate for g2p, average levenshtein distance for mi, and detokenized bleu score for mt. at test time, we decoded with a beam width of 5. our pytorch code @xcite is based on joeynmt @xcite and the entmax implementation from the entmax package. 4 ## analysis model error. @xcite showed that the bias in favor of short strings is so strong for softmax nmt models that the argmax sequence is usually the empty string. however, they did not consider the impact of sparsity or label smoothing. 8 we show in other inadequate strings. even if a model rules out the empty string, it might assign nonzero probability to other short, inadequate strings. we investigated this with a depth-limited search inspired by @xcite 's exact decoding technique. unfortunately, the algorithm's exponential runtime made it unfeasible to perform the search for all language pairs, and in particular we found it too slow for the dense search space of cross entropy models, even after applying various optimizations. 9 therefore, we show results for en ro entmax loss models in label smoothing and sparsity. @xcite previously showed that rnn models trained with entmax loss become locally very sparse. calibration. this is the degree to which a model's confidence about its predictions (i.e. class probabilities) accurately measure how likely those predictions are to be correct. it has been shown @xcite that label smoothing improves the calibration of seq2seq models. we computed the expected calibration error (ece; naeini et al., 2015) 10 of our mt models and confirmed their findings. our results, in map decoding and the empty string. we showed that sparse distributions suffer less from the cat got your tongue problem than their dense counterparts. this makes sense in light of the finding that exact map decoding works for mi, where probabilities are very peaked even with softmax @xcite . for tasks like mt, this is not the case: eikema and aziz (2020) pointed out that the argmax receives so little mass that it is almost arbitrary, so seeking it with map decoding (which beam search approximates) itself causes many deficiencies of decoding. on the other hand, @xcite showed that beam search has a helpful bias and introduced regularization penalties for map decoding that encode it explicitly. entmax neither directly addresses the faults of map decoding nor compensates for the locality biases of beam search, instead shrinking the gap between beam search and exact decoding. it would be interesting, however, to experiment with these two approaches with entmax in place of softmax. ## conclusion we generalized label smoothing from cross-entropy to the wider class of fenchel-young losses. when combined with the entmax loss, we showed meaningful gains on character and word-level tasks, including a new state of the art on multilingual g2p. in addition, we showed that the ability of entmax to shrink the search space significantly alleviates the cat got your tongue problem in machine translation, while also improving model calibration.