Non-Autoregressive Machine Translation as Constrained HMM (2024)

Abstract: In non-autoregressive translation (NAT), directed acyclic Transformers (DAT) have demonstrated their ability to achieve comparable performance to the autoregressive Transformers.In this paper, we first show that DAT is essentially a fully connected left-to-right Hidden Markov Model (HMM), with the source and target sequences being observations and the token positions being latent states.Even though generative models like HMM do not suffer from label bias in traditional task settings (e.g., sequence labeling), we argue here that the left-to-right HMM in NAT may still encounter this issue due to the missing observations at the inference stage.To combat label bias, we propose two constrained HMMs: 1) Adaptive Window HMM, which explicitly balances the number of outgoing transitions at different states; 2) Bi-directional HMM, i.e., a combination of left-to-right and right-to-left HMMs, whose uni-directional components can implicitly regularize each other’s biases via shared parameters.Experimental results on WMT’14 EnDe and WMT’17 ZhEn demonstrate that our methods can achieve better or comparable performance to the original DAT using various decoding methods.We also demonstrate that our methods effectively reduce the impact of label bias.

## introduction autoregressive (ar) models @xcite have played a major role in various text generation tasks such as machine translation @xcite and text summarization @xcite . despite being powerful, ar models still have some drawbacks: 1) slow inference speed due to the sequential generation property; 2) label bias @xcite @xcite due to the local normalization (e.g., softmax operation over the ## the missing observation and label bias in this section, we argue that dat is essentially a fully connected left-to-right hmm, and it can still suffer from the label bias problem at the inference stage due to the missing observation y . dat as a fully connected left-to-right hmm if we compare the training objective eq.1 of dat to an hmm model, (x, y ) can be seen as the observations and the positions a @xmath0, l -1] as latent states in hmm, respectively. specifically, p (y i |a i , x) is the emission score, and p (a i |a i-1 , x) is the transition score, both of which are parameterized by a transformer network. a normal hmm would allow transitions between any two states, while dat only allows transitions from small positions to large positions (p (a i hence, it is essentially a fully connected left-to-right hmm or bakis hmm @xcite (see fig. 1a ). however, there are some special properties when applying hmm to the translation task as opposed to common structured prediction problems such as sequence labeling. first, the observations are composed of two parts, i.e., source sentence x and target sentence y , and x is always available whereas y is unavailable during inference. in sequence labeling, however, the observations only consist of x (i.e., the text sequences to be labeled) and they are always given. second, the decoding problem in machine translation is @xmath1, a|x) whereas in sequence labeling it is @xmath2. that is, we are interested in the missing "observation" y instead of the latent states a. label bias the label bias problem refers to that when applying decoding algorithms that involve the comparison between cumulative scores (e.g., log probabilities) to a locally normalized discriminative model (e.g., maximum entropy markov model, @xcite , the states with less outgoing transitions (or low-entropy transition probability distribution) will be preferred over those with more due to the local normalization or "conservation of score mass" @xcite @xcite . take the transitions p (a|x) = i p (a i |a i-1 , x) (eq. 1) for example, which alone can be regarded as a locally normalized discriminative model. if each 0 1/5 1/5 1/5 1/5 1/5 0 0 1/4 1/4 1/4 1/4 p (a i |a i-1 , x) follows a uniform distribution, then viterbi decoding will pick the path that contains states with fewer outgoing transitions. we give a toy example in figure 3a where the viterbi decoding result of p (a|x) yields the green path with a probability 1/5 rather than the red path with a probability 1/20. the green path (0, 4, 5) is preferred over the red path (0, 1, 5) since a 1 = 4 has only one outgoing transition while a 1 = 1 has 4 outgoing transitions. in real scenarios, if the model is always biased to choose similar paths for different x (i.e., being biased to put the tokens towards the end positions), the front positions can be wasted and the model's expressive power can be "under-utilized". in hmm, however, we still have an emission term p (y i |a i , x), which can freely "amplify" or "dampen" the influence of p (a i |a i-1 , x) based on the given observation y i @xcite . that is, p (y i |a i , x) is able to upweight or downweight p (a i |a i-1 , x). in the toy example, if we consider the emission term p (y 1 |a 1 = 4, x) together with p (a 1 = 4|a 0 = 0, x), the probability of choosing green path will be p (y 1 |a 1 = 4, x)/5, and for the red path it is p (y 1 |a 1 = 1, x)/20 (we ignore p (y 0 |a 0 = 0, x) and p (y 2 |a 2 = 5, x) since they are the same for both paths). thus, there is still a chance that p (y unfortunately, ground truth y i is only provided during the training stage, not during the inference stage, and thus we do not know the ground truth emission score p (y i |a i , x). we can only esti- ## approach adaptive window hmm (aw-hmm) we notice that one of the causes of label bias is that the number of the outgoing transitions (outdegree) is imbalanced at different positions (see figure 1a , figure 3a ). at position 0, the number of possible outgoing transitions is l -1, whereas this number decreases to 1 at position l -2. to reduce this imbalance, we set the maximal number of outgoing transitions to be: for example, we have l ′ = 3 in figure 1b and 3b, and positions 0, 1, 2 can all observe l ′ = 3 future positions, respectively. in figure 3b , it can be seen that now the probability difference between the green and red paths has been narrowed from 3/20 = 1/5-1/20 down to 1/18 = 1/6-1/9. at first glance, we can choose a small β to deal with label bias more effectively, but a small β will lead to a small set γ, which impairs the model's expressiveness. therefore, we need to make a trade-off here (as we will see in section ??). note that the decoding algorithms of aw-hmm stay the same as dat. bi-directional hmm instead of only modeling a left-to-right hmm (l2r), we consider both left-toright and right-to-left hmm (r2l) simultaneously (see figure 1c and 3c ). the original objective function can be written as: eq. 3) to model p ( -→ a |x) and p ( ← -a |x) but allow them to share transformer backbone and emission parameters (see eq. 2). α is a hyperparameter that adjusts the weight of the two hmms. obviously, p ( -→ a |x) and p ( ← -a |x) would have opposite biases. in figure 3c , the l2r hmm favors the path [0, 4, 5] while the r2l hmm favors [0, 1, 5]. however, the shared parameters, namely the transformer backbone and the emission scores e, force them to regularize each other during training and thus reduce their own biases implicitly. we can observe in figure 3c that the green and red paths have equal probability now. during inference, we apply the same decoding strategy to the l2r and r2l hmms, obtaining two translations together with their scores (i.e., probabilities). then we only keep the translation with higher scores. both aw-hmm and bi-hmm can alleviate the label bias problem, by imposing an inductive bias that tokens should be distributed evenly across all positions, making full use of the model's expressive power. glancing training dat adopts the glancing strategy for training @xcite , which dynamically determines the number of ground truth tokens y t to be kept in the decoder input for each training instance x based on current translation accuracy. for aw-hmm, the glancing strategy stays the same. as for bi-hmm, we randomly choose the l2r or r2l model for glancing. model our implementation is based on dat. 4 the backbone of the model is a standard transformer, except that we remove the causal mask in decoder self-attention. the up-scale factor λ is set to 8, following dat @xcite . the adaptive window factor β = 4 in our experiments is finetuned on the validation set of wmt'14 en-de. in bi-hmm, the l2r/r2l weight α is set to 0.5 (see appendix 6.1). we train all the models including autoregressive transformer @xcite for 300k steps with a batch size of 64k tokens. other training details can be found in appendix a. we also select the best 5 checkpoints according to the bleu score on the validation set and average them before testing. after training, we apply greedy, lookahead, beam search @xcite , and viterbi @xcite to dat and our models. evaluation in this study, we adhere to the reporting conventions established by prior research to ensure comparability and consistency in evaluating translation quality. specifically, we report tokenized bleu score @xcite for @xcite , we also report bleurt @xcite for the main baseline, dat in ## conclusion in this paper, we argue that directed acyclic transformer @xcite is essentially a left-toright hmm, with the source and target sequences x, y being observations and the token positions a being latent states. furthermore, this left-to-right may suffer from the label bias issue due to the unavailability of the target observations y during inference, which could under-utilize the model's expressive power. therefore, we propose adaptive window hmm (aw-hmm) and bi-directional hmm (bi-hmm) to combat label bias. the experimental results on wmt'14 en↔de and wmt'17 en↔zh show the effectiveness of our methods and we also quantitatively show that our method indeed mitigates the influence of label bias.