V iterbi Decoding of Directed Acyclic Transformer for Non-Autoregressive Machine Translation (2022)

Abstract: Non-autoregressive models achieve significant decoding speedup in neural machine translation but lack the ability to capture sequential dependency. Directed Acyclic Transformer (DA-Transformer) was recently proposed to model sequential dependency with a directed acyclic graph. Consequently, it has to apply a sequential decision process at inference time, which harms the global translation accuracy. In this paper, we present a Viterbi decoding framework for DA-Transformer, which guarantees to find the joint optimal solution for the translation and decoding path under any length constraint. Experimental results demonstrate that our approach consistently improves the performance of DA-Transformer while maintaining a similar decoding speedup.

## introduction non-autoregressive translation @xcite models achieve a significant decoding speedup but suffer from performance degradation, which is mainly attributed to the multi-modality problem. multi-modality refers to the scenario where the same source sentence may have multiple translations with a strong cross-correlation between target words. however, non-autoregressive models generally hold the conditional independence assumption on target words, which prevents them from capturing the multimodal target distribution. recently, directed acyclic transformer @xcite was proposed to model sequential dependency with a directed acyclic graph consisting of different decoding paths that enable the model to capture multiple translation modalities. although it has been proven effective, it cannot directly find the most probable translation with the argmax operation. therefore, da-transformer has to apply a se-quential decision process at inference time, which harms the global translation accuracy. in this paper, we propose a viterbi decoding @xcite framework for da-transformer to improve the decoding accuracy. using the markov property of decoding path, we can apply viterbi decoding to find the most probable path, conditioned on which we can generate the translation with argmax decoding. then, we further improve this decoding algorithm to perform a simultaneous search for decoding paths and translations, which guarantees to find the joint optimal solution under any length constraint. after viterbi decoding, we obtain a set of translations with different lengths and rerank them to obtain the final translation. we apply a length penalty term in the reranking process, which prevents the generation of empty translation @xcite and enables us to control the translation length flexibly. experimental results on several machine translation benchmark tasks (wmt14 en↔de, wmt17 zh↔en) show that our approach consistently improves the performance of da-transformer while maintaining a similar decoding speedup. ## methodology this section presents a viterbi decoding framework for da-transformer to improve decoding accuracy. we first develop a basic algorithm to find the optimal decoding path and then improve it to find the joint optimal solution of the translations and decoding paths. finally, we introduce the technique to rerank the viterbi decoding outputs. ## related works most non-autoregressive models can directly find the most probable output with argmax decoding, which is the fastest decoding algorithm. however, models of this type usually suffer from the multimodality problem @xcite , leading to severe performance degradation. a relatively more accurate method is noisy parallel decoding, which requires generating multiple translation candidates and greatly increases the amount of computation. many efforts have been made to address the multi-modality problem, including latent models @xcite @xcite @xcite , alignment-based models @xcite @xcite , and better training objectives @xcite @xcite @xcite . however, these techniques are still not powerful enough, which heavily rely on knowledge distillation @xcite . some researchers seek iterative decoding approaches to improve translation quality. work in this area includes semi-autoregressive decoding @xcite , iterative refinement @xcite , mask-predict decoding @xcite , levenshtein transformer @xcite , multi-thread decoding (ran et al., 2020), imputer @xcite , and rewriting @xcite . although their translations are of better quality, they are criticized for being slow at inference time @xcite . recently, latent alignment models like ctc @xcite and da-transformer @xcite achieved impressive performance and received a lot of attention. beam search is an useful decoding strategy for latent alignment models @xcite @xcite @xcite . it brings considerable improvements but also reduces the decoding speed. viterbi decoding has also been used in nonautoregressive models. in crf-based nat models, viterbi decoding is applied to find the most probable output @xcite . ## conclusion the current decoding strategies of da-transformer need to apply a sequential decision process, which harms the global translation accuracy. in this paper, we propose a viterbi decoding framework for da-transformer to find the joint optimal solution of the translation and decoding path and further demonstrate its effectiveness on multiple benchmarks. argmax y p (y |x) but alternatively finds the joint optimal solution argmax a,y p (a, y |x). however, as we show in section 4.4, outputs with higher joint probability usually also have higher translation probability, suggesting that optimizing the joint probability is helpful. another limitation is that the improvements of our method are smaller in the knowledge distillation setting. however, the main advantage of da-transformer is that it does not heavily rely on knowledge distillation and achieves superior performance on raw data, which makes the impact of this limitation small.