Fuzzy Alignments in Directed Acyclic Graph for Non-Autoregressive Machine Translation
Authors: Zhengrui Ma
Chenze Shao
Shangtong Gui
Min Zhang
Yang Feng
Venue: ICLR 2023 poster (2023)
Keywords: Machine translation
Non-autoregressive generation
Fuzzy alignment

Abstract: Non-autoregressive translation (NAT) reduces the decoding latency but suffers from performance degradation due to the multi-modality problem. Recently, the structure of directed acyclic graph has achieved great success in NAT, which tackles the multi-modality problem by introducing dependency between vertices. However, training it with negative log-likelihood loss implicitly requires a strict alignment between reference tokens and vertices, weakening its ability to handle multiple translation modalities. In this paper, we hold the view that all paths in the graph are fuzzily aligned with the reference sentence. We do not require the exact alignment but train the model to maximize a fuzzy alignment score between the graph and reference, which takes captured translations in all modalities into account. Extensive experiments on major WMT benchmarks show that our method substantially improves translation performance and increases prediction confidence, setting a new state of the art for NAT on the raw training data.

Published as a conference paper at ICLR 2023
FUZZY ALIGNMENTS IN DIRECTED ACYCLIC GRAPH FOR NON-AUUOREGRRSSIVE MACHINE TRANSLATION
Zhengrui Ma Chenze S
Shangtong Gui Min Zhang' & Yang Feng!
Key Laboratory of Intelligent Information Processing Institute of Computing Technology, Chinese Academy of Sciences
2 University of Chinese Academy of Sciences
3 Harbin Institute of Technology, Shenzhen
ABSTRACT
Non-autoregressive translation (NAT) reduces the decoding latency but suffers from performance degradation due to the multi-modality problem. Recently, the structure of directed acyclic graph has achieved great success in NAT, which tackles the multi-modality problem by introducing dependency between vertices. However, training with negative log-likelihood loss implicitly requires strict alignment between reference tokens and vertices, weakening its ability to han- dle multiple translation modalities. In this paper, we hold the view that all paths in the graph are fuzzily aligned with the reference sentence. We do not require the exact alignment but train the model to maximize a fuzzy alignment score be- tween the graph and reference, which takes captured translations in all modalities into account. Extensive experiments on major WMT benchmarks show that our method substantially improves translation performance and increases prediction confidence, setting a new state of the art for NAT on the raw training data.' !
INTRODUCTION
Non-autoreerresivee translation (NAT) (Gu et al., 2018) reduces the decoding latency by generating all target tokens parallel. Compared with the autoregressive counterpart (Vaswani et al., 2017), NAT often suffers from performance degradation due to the severe multi-modality problem (Gu et al., 2018), which refers to the fact that one source sentence may have multiple translations in the target language. NAT models are usually trained with the cross-entropy loss, which strictly aligns model prediction with target tokens. The strict alignment does not allow multi-modality such as position shifts and word reorderings, so proper translations likely be wrongly penalized. The inaccurate training signal makes NAT tend to generate mixture of different translations rather than a consistent translation, which typically contains many repeated tokens in generated results.
Many efforts have been devoted to addressing the above problem (Libovický & Helcl, 2018; Shao al., 2020: Ghazvininejad et al., 2020a; Du et al., 2021; Huang et al., 2022c). Among them, Di- rected Acyclic Transformer ODA-Transforeet (Huang et al., 2022c) introduces a directed acyclic graph (DAG) on top of the NAT decoder, where decoder hidden states are organized as a graph rather than sequence. By modeling the dependency between vertices, DAG is able to capture multiple translation modalities simultaneously by assigning tokens in different translations to dis- tinct vertices. In this way, DA-rransformer does not heavily rely on knowledge distillation (KD) (Kim & Rush, 2016; Zhou et al., 2020) to reduce training data modalities and can achieve superior performance on raw data.
Despite the success of DA- Traansssforerr training it with negative log- log-likelihood (NLL) loss, which marginalizes out the path from the joint distribution of DAG path and reference, is sub-optimal in the scenario of NAT. It implicitly introduces a striet monotonic alignment between reference tokens and vertices on all paths. Although DAG enables the model to capture different translations in different
*Corresponding author: Yang Feng. Contact: (mazhergru b,,, shaochenzel B2, gu shangtong211 s,
F ct ac...... en; zhangmi n2021 wt..ieitttt..................... edu.cn. Source code: https: / huub. htw. c p/PA-DAT.

---

Published as a conference paper at ICLR 2023
transition paths, only paths that aligned verbatim with reference with large probability will be well calibrated by NLL (See Section 2.3 for detailed analysis). It weakens DAG's ability to handle data multi-modality, making the model less confident in generating outputs and requiring large graph size to achieve satisfying performance.
In this paper, extend the verbatim alignment between reference and DAG path fuzzy align- ment, aiming to better handle the multi-modalle problem. Specifically, we do not require the exact alignment but hold the view that all paths in DAG are fuzzily aligned with the reference sentence. To indicate the quality of alignment, an alignment score is assigned to each DAG path based on the expectation n- n-gram overlapping. We further define an alignment score between the whole DAG and reference as the expected alignment score of all its paths. The model is trained to maximize the alignment score, which takes captured translations in all modalities into account.
Experiments on major WMT benchmarks show that our method substantially improves the transla- tion quality of DA- Transformer. It achieves comparable performance the autoregressive Trans- former without the help of knowledge distillation and beam search decoding, setting new state of the art for NAT on the raw training data.
BACKGROUND
2.1
NON-AUTOREGRESSIVE MACHINE TRANSLATION
Non-autoregressive translation (Gu et al., 2018) is proposed to reduce the decoding latency. It aban- dons the assumption of autoregressive dependency between output tokens and generates all tokens simultaneously. Given a source sentence æ {I1,..., EN NAT factorizes the joint probability of target tokens y {y1 }Mr} as.
M
Po(y)æ) = II Po Po
(1)
where 0 is the model parameter and (o (x) denotes the translation probability of yi at position i.
In vanilla NAT, the decoder length is set to reference length during the training and determined by a trainable length predictor during the inference. Standard NAT model is trained with the cross- entropy loss, which strictly requires the generation of word y: at position i:
LCE =
Σ log (o).
2.2 DIRECTED ACYCLIC TRANSFORMER
Vanilla NAT model suffers two major drawbacks, including inflexible length prediction and disabil- ity to handle multi-modality. BA-rransformer (Huang et al., 2022c) addresses these problems by stacking a directed acyclic graph on the top of NAT decoder, where hidden states and transitions between states represent vertices and edges in DAG.
Formally, given a bilingual pair æ {II,..., IN} and = (y,,..,, ya.,,,ar, DA-Trans TraTransfrrmer sets the decoder length L N and models the translation probability by marginalizing out paths in DAG:
Po())z)
Σ Polyla, ( Polal))) a
(3)
where a = {ai.... am} is a path represented by a sequence vertex indexes with the bound 1 (1 ... aM L and T, contains all paths with the same length the target sentence y. (a(az) and Po(yla, a, .)) indicate the probability of path a and the probability of target sentence y conditioned on path respectively. DAG factorizes the path probability Pe (a(æz) based on the Markov hypothesis:
M-1
M-1
Po(a)x)= II 1=1
Polas+1aa;. x) = II Ea
(4)
2

---

Published as a conference paper at ICLR 2023
where E R is a row-normalized transition matrix. Due to the unidirectional inherence of DAG, the lower triangular part E are masked to zeros. Once path a is determined, token yi can be generated conditioned on the decoder hidden state with index a;:
Polyla, x) II Po (ollaa,, i=1
DA-Transformer is trained to minimize the negative log- ligllikelioood loss via dynamic programming:
C = log Po(y)x) = log Σ Polyla,
(6)
acTy
The structure of DAG helps NAT model token dependency through transition probability between vertices while almost zero overhead of sequential operation is paid in decoding.
2.3 MULTI-MODALITY IN DAG
DA- Transformer alleviates the multi-modality problem by arranging tokens in different translations to distinct vertices, and the learned vertex transition probability prevents them from co-occurring in the same DAG path. Despite DAG's ability to capture different translations simultaneously, only paths that aligned verbatim with reference with large probability will be well calibrated by the NLL loss. can be demonstrated by inspecting the gradients:"
① C- 00
Σ Po x) 00 La.
aet,
where La -og (o alx). Equation 7 shows that NLL loss will assign paths with smaller posterior probability smaller gradient weights, making paths corresponding to translations other modalities poorly calibrated. Considering that only one reference is provided in major translation benchmarks, training DAG with the NLL loss inevitably hurts its potential to handle translation multi-modality.
3 METHODOLOGY
In this section, we extend the verbatim alignment between reference and DAG path to an n-gram- based fuzzy alignment. In Section 3.1 and 3.2, we explore a metric to calibrate DAG under fuzzy alignment. We develop an efficient algorithm to calculate the alignment score in Section 3.3, and introduce a training strategy with fuzzy alignment in Section 3.4.
3.1 FUZZY ALIGNMENT
We do not require the exact alignment but hold the view that all paths in DAG are fuzzily aligned with the reference sentence to some extent. order to allow multi-modality such as position shifts and word reorderings, overlapping, which is a widely used factor in machine translation evaluation (Papineni et al., 2002).
measure the quality of fuzzy alignment by the order-agnostic n-gram
Given target sentence y (yI,..., HM} } and integer repeating n-grams as (y) the elements which are mutually exclusive. For any n-gram g e Gn (y), the number of its appearances by clipped n n-gram precision of model output y against reference y:
1, denote the set of all its non-
is denoted as Cg (3). We measure the alignment quality
Σ Pr (n'. y) (v)
min(C (Cn(C())) Cg())
(eG.,(rr)
Considering that the DAG path composed of consecutive vertices, and each vertex represents word distribution rather than a concrete word, we assign an alignment score to each DAG path with the expected n-gram precision:
Pn (0, a, E Ey (pn (o(V''y)
We leave the derivation in Appendix A.
3

---

Published as a conference paper at ICLR 2023
3.2 ESTIMATING FUZZY ALIGNMENT IN DAG
Directed acyclic graph simultaneously retains multiple translations in different paths, motivating us measure the alignment between generated graph and reference sentence by the averaged alignment score of all its possible transition paths:
Pr (f, y) (a .²) [Pn a. y)]
(10)
However, the search spaces for translations and paths both exponentially large, making Equa- tion 10 intractable. Alternatively, we turn to calculate the ratio of the clipped expected count of n- n-gram matching to expected number of n-grams, which can be considered as an approximation of Pa (0, y):
Σ
min (Co (C,()))),,
(0, y) = gEG,. (M)
(11)
Ey
E Cg(y')] gEGn(ar)
Though p', (9, y) much simplified, the direct calculation will still suffer from exponential time complexity due the intractable expectation terms in it. In the following section, will focus developing an efficient algorithm to calculate Eny (Cg (1y) and Ey Σ Cg(v')).
gEG,(y))
3.3 EFFICIENT CALCULATION OF FUZZY ALIGNMENT
Fortunately, the Markov property of DAG makes it possible simplify the calculation of Equa- tion 11. We first consider an n-vertex subpath UI, Un which is bounded by 1 S U1, Un S L. An indicator function 1 (U),,... bn E a) introduced to indicate whether Uı,..., Uy is a part of path a. Then we can define the passing probability of subpath by enumerating all possible paths a:
P(I(VI....,,.. [x)l=) = Σ Po(a Un Ea).
(12)
With the definition of passing probability, can transform the sum operations in Equation 11 from enumerating all translations to enumerating all the n-vertex subpaths, which significantly narrows the search space. We directly give the following theorem and refer readers to Appendix B for detailed derivation:
E Σ
Ca(y')= = Σ P(I 2n))
(13)
gEG.(V))
10
Σ P( un) II Po
(14)
where (g denotes the probability that vertex with index generates the i-th token in n-gram g. By narrowing the search space, we can find that those expected counts are actually the sum and weighted sum of passing probabilities of n-vertex subpaths. It is worth noting that the n-vertex subpath Vi..... in forms a Markov chain, leading us to factorize the passing probability into the product of transitions. We reuse the transition matrix E introduced in Section 2.2 for notation, where E,,,oy is the transition probability from v/ to uy. The passing probability of an n-vertex subpath can be formulated as:
P(I(VI,..,,,) = ((1(e))lz)
Il 1=1
E E
(15)
where (()()))) denotes the passing probability of vertex with index v. For any 1 S v < I, P(1(v) x)) can be calculated efficiently via dynamic programming:
((1())=)
Σ V'CU
(16)
Note that there is need to require = < L. In fact, the upper triangular transition matrix only considers paths with monotonie order and sets the prohahility of others
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Calculation of (C,((())))))) and By gEg C3(y')l
Input: Transition matrix E, Token probability matrix G, Graph size L, r--gram order N. Output: Expected counts Ey (Co (y') and By (Eger,,('' Co(y
1: 4-1
2: for i 2 do
3: Pi Σ E,
3=1
p (pI.P2,.., PL]"
5: c(2) + c
t p" GI.
for 21o do
7:
c(ll () E
8:
el0 + (- G.;
9: (y)()(())]
t |e Ey I Egeaniv" Co(y')l < ||
10: return
and EV (rg Co(v')).
with the boundary condition that the passing probability of the first vertex in the directed graph equal to 1. For convenience, we introduce passing probability vector p E IR,, where P. (v) x). Equation 15 reminds us that the sum of n-vertex passing probabilities is actually the sum of (n-1) transition probabilities in Markov chain with initial probability p and transition matrix E. On the basis of Equation 13, we have:
n-1 Eyl E Co(y') = Σ ((1(e))(z II Eu.. 1|p" "1pp.E"-111 gEG.(V))
E1-
(17)
UI....
By rearranging the order of products, Equation 14 a similar way. We introduce G E T with the ith row of G representing the token probability of gi each vertex, i.e., G. Po (v). Then we can obtain:
handle the weighted sum of passing probabilities in
Σ P(I(v))(z)
E B II Pa(g)l))
(18)
Σ ((I(v))())Pal
(()) Emaon Po Po Po(g
21 Pe
=Ipp" G1.
E G2.
E G.,lhh:
where denotes position-wii wise product, and G. should be broadcast when i 1. We refer readers to Appendix C for detailed derivation.
Based on the discussion above, we finally avoid the exponential time complexity in calculating p', (8, y). Instead, it can be implemented with On + L) parallel operations, making the proposed fuzzy alignment objective practical for the training. We summarize the calculation process in Algo- rithm 1.
3.4 TRAINING STRATEGY
We have found way to train DA- DA-Transformer to maximize the fuzzy alignment score p', (0, y) efficiently. However, it may bias the model favor short translations. To this end, we adopt the idea of brief penalty (Papineni et al., 2002) for regularization. Specifically, we define the brief penalty of DAG based the ratio of reference length to the expected translation length:
T
BP min (exp (1
). Ey [Ty,
(19)
where T, denotes the length of reference y. As the expected translation length is equal to the expected number of 1-grams outputs, it is convenient to calculate [Tyr] efficiently with the help of Equation 17. Finally, we train the model with the following loss:
L -B P', (0,
(20)

---

Published as a conference paper at ICLR 2023
We first pretrain DA- DA-Transformer with the NLLloss to obtain good initialization, and then finetune the model with our fuzzy alignment objective.
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Datasets We conduct experiments on two major benchmarks that widely used in previous stud- ies: WMT14 English+>German (EN++DE, 4M) and WMT17 Chineses+English (ZH++EN, 20M).* We apply BPE (Sennrich al., 2016) learn a joint subword vocabulary for EN++DE and separate vocabularies for ZH+EN on the tokenized data. For fair comparison, we evaluate our method with SacreBLEU (Post, 2018) for WMT EN-ZH task and tokenized BLEU (Papineni et al., 2002) for other benchmarks. Considering BLEU may be biased, we also measure the translation quality with learned metrics in Appendix F. The decoding speedup is measured with batch size of 1.
Implementation Details We adopt Transformer-bat (Vaswani et al., 2017) as our autoregressive baseline. For the architecture of our model, we strictly follow the settings of DA- -ra-rrasforrmer where we set the decoder length to 8 times the source length (A = 8) and use graph positional embeddings as decoder inputs unless otherwise specified. During both pretraining and finetuning, we set dropout rate to 0.1, weight decay to 0.01, and no label smoothing is applied. In pretraining, all models are trained for 300k updates with a batch size of 64k tokens. The learning rate warms up to 10-4 within 10k steps. In finetuning, we use the batch of 256k tokens to stabilize the gradients and train models for 5k updates. The learning rate warms up to 2- 10 within 500 steps. We evaluate BLEU scores on the validation set and average the best 5 checkpoints for the final model. We implement our models with open-source toolkit fai rseq (Ott et al., 2019). All the experiments are conducted on GeForce RTX 3090 GPUs.
Glancing Glancing (Qian et al., 2021a) is a promising strategy to alleviate data multi-modality while training. We apply the same glancing strategy as Huang et al. (2022c), which assigns target tokens to appropriate vertices based on the most probable path: à = arg max Po (a) xx y). In the pretraining, we linearly anneal the unmasking ratio 7 from 0.5 to 0.1. In the finetuning, we fix 0.1.
Decoding We apply beam search with beam size of 5 for autoregressive baseline and argmax decoding for vanilla NAT. Following Huang et al. (2022c), we find the translation of DAG with Greedy and Lookahead decoding. The former only searches the path greedily and then collects the most probable token from each vertex sequentially:
arg max Po(aala,.1. 2), V1 = arg max Po (vvla,,,))) x)..
(21)
a,
And the latter jointly searches the path and tokens in greedy way:
a " = arg max Po (o(a
(22)
We also adopt Joint-Viterbi decoding (Shao et al., 2022a) to find the global joint optimum of trans- lation and path under pre-defined length constraint, then rerank those candidates by length normal- ization.
4.2 PRELIMINARY EXPERIMENT: EFFECTS OF n
We first study the effects of n-gram order on our fuzzy alignment objective. In this experiment, we set the decoder length to 4 times the source length (A = 4) and apply Lookahead decoding to generate outputs. We compare different settings of n and report BLEU scores and BERTScores on the raw WMT14 EN-DE dataset in Table 1.
As shown in Table the performance of our fuzzy alignment objective differs as n varies. We find that using a larger is helpful for DAG to generate better translations. Specifically, it improves the DA- TM-Trrnsformer baseline by 0.82 BLEU and 1.11 BERTScore when n 2 and by 0.65 BLEU and
NNwstest20133 as the validation set and newstesr2014 as the test set for EN++DE; devtest2017 as vali- dation set and newstesr2017 as the test set for Z.H+ENN. h-w..oo....ppptttoohheeeeeeoooo.
SacreBI.Fr EU signature: www.kcass.miiee-murrff...

---

Published as a conference paper at ICLR 2023
Table I: Effects of fuzzy alignment objective WMT14 EN-DE. Decoder length is set to 4 times source length (A 4).
BLEU
BERTScore
DA-Trame Transformer
26.16
60.57
+ 1-rgrm
25.71
60.69
+2 +2-gram
26.98
61.68
+3 +3-gram
26.81
61.56
Table 2: BLBU scores on raw WMT14 EN++ and WMT17 ZHe>EN dataset. Results of baselines are quoted from Huang al. (2022c). indicatess the results from our re-implementation. * and **
indicate the improvement over DA- TA-Transformer is statistically significant 0.05 and 0.01, respectively).
WMT14
WMT17
Model
Iter.
Speedup
EN-DE
DE-EN
ZH-EN
EN-ZH
Transformer (Vaswani et al., 2017)
N
1.0x
27.6
31.4
23.7
34.3
Transformer'
N
1.0x
27.54
31.55
24.23
35.19
CMLM (Ghazvininejad al.,
10
2.2x
24.61
29.40
SMART (Ghazvininejad al., 20206)
2.2x
25.10
29.58
DisCo (Kasai et al., 2020)
R34
3.5x
25.64
Imputer (Saharia et al., 2020)
8
2.7x
25.0
CMLMC (Nuang al., 2022d)
10
1.7x
26.40
30.92
Vanilla-NAT (Gu al., 2018)
15.3x
11.79
16.27
8.69
18.92
CTC (Libovicky Helel, 2018)
14.6x
18.42
23.65
12.23
26.84
AXE (Ghovvnninejad al., 2020s)
14.2x
20.40
24.90
GLAT (Qian et at., 2021a)
15.3x
19.42
26.51
18.88
29.79
OaXE (Du et al., 2021)
14.2x
22.4
26.8
CTC GLAT (Qian et 2021b)
14.6x
25.02
29.14
19.92
30.65
CTC DSLP (Huang al,, 2022n)
14.0x
24.81
28.33
DA-Trane Transformmr
Greedy
14.2x
26.08
30.48
22.66
33.27
(Huang 2022c)
Lookahead
14.0x
26.57
30.68
22.82
33.83
Greedy
14.2x
26.07
30.69
22.35
33.58
Trrraasforrmrr
Lookahead
14.0x
26.56
30.81
22.65
33.62
Joint Viterbi
13.2x
26.89
31.09
23.17
33.25
Greedy
14.2x
27.49**
31.36**
23.78**
33,97*
FA-DAT
Lookahead
14.0x
27.53*
31.37**
23.81
34.02*
+
Joint Viterbi
13.2x
27.47**
31.44*
24.22
34,49**
0.99 BERTScore when n = We speculate the reason for performance degradation with n is that the 1-gram alignment objective thoroughly breaks the order dependency among tokens in sentence, which will encourage the model to output bag-of-words instead of fluent sentence. is also noteworthy that 2-gram alignment performs better than 3-gram. We attribute the reason the Markov property of DAG, which only models the dependency between adjacent tokens, thus making the 2-gram alignment more appropriate. In the following experiments, we will apply 2 the default setting and name it as FUZZY-ALIGNED DIRECTED ACYCLIC TRANSFORMER (FA-DAT).
4.3 MAIN RESULTS
We compare our FA-DAT with the autoregressive baseline and previous NAT approaches in Table 2. FA-DAT consistently improves the translation quality of DA-Transformer by large margin under all decoding strategies. Notably, it achieves comparable performance with the autoregressive baseline without knowledge distillation and beam search decoding. With Joint-Viterbi decoding, the average gap between autoregressive model and FA-DAT on raw data is further reduced to 0.09 BLEU on EN and 0.35 BLEU ZH++EN while FA-DAT maintains 13.2 times decoding speedup.

---

Published as a conference paper at ICLR 2023
taken probability
0.6
0.6
0.4
0.4
0.0
0.4
0.6
0.0
0.2
0.6
0.6
6.8
1.0
passing probability
passing probabliity
Vertex distribution of FA-DAT
(b) Vertex distribution DA-rransformer
Figure I: The distribution of vertices' passing probabilities and max token probabilities on test set of WMT14 EN-DE. Passing probability and max token probability refer to the probability of a vertex appearing sampled path and the probability of its most probable token respectively. Darker area indicates dense distribution of vertices. Marginal distributions are given on the top and right.
Table 3: Statistics of translations on raw WMT14 EN-DE dataset.
log (a(a)))
log Po (y a)
log (o(y)ar)
+Geedd Lookahead
10.27
4.51
11.47
DA-Transformer
10.49
3.84
11.06
Joint Viterbi
9.60
3.32
10.50
Greedy
2.99
1.03
2.03
FA-DAT
Lookahead
3.00
1.00
2.02
+Joint- Vittrbi
3.17
0.98
1.86
4.4 ANALYSIS AND DISCUSSION
Generation Confidence We note that the performance of Greedy decoding is on par with that of Looka- head decoding in FA-DAT while left far behind in DA- Transformer Table To conduct the analysis, we collect the probability of generated path (P)(a))) and generated translation given path (Po (a, æ)) on test set and further calculate the marginal probability of generated translation (Po x) via dynamic program- ming. Statistics are shown in Table 3. We observe log Payya,, æ) is extremely low in FA-DAT, sug- gesting that every vertex DAG is assigned with concrete token with high confidence, making Greedy decoding perform similarly Lookahead decoding. Compared with DA- DA-Transformer, path searched in FA- DAT has a larger probability and the model is more confident about its output translation under all decod- ing strategies. We owe FA-DAT's ability to well calibrate vertices in different modalities. It can be ver- ified by checking the distribution of vertices' passing probabilities and max token probabilities in Figure 1. Vertices of FA-DAT have passing probabilities either close to or to and token probabilities all close to 1. It demonstrates the fuzzy alignment objective's 's ability reduce model perplexity and improve generation confidence.
Effects of X
Das Melrandteees
27.53
28.55
26.0
26:16
26.03
25.5
25.45
25.0
Size Factor
Figure 2: Effects of À on raw WMT14 EN- DE. Decoder length set to times source length.
Effects of Graph Size We further study how the size of the graph affects our method. We vary the graph size hyperparameter X from 2 8 and measure the translation quality of the proposed
8

---

Published as a conference paper at ICLR 2023
FA-DAT and DA-Transfomeer baseline with Lookahead decoding on WMTI4EN-DE. As shown in Figure 2, FA-DAT consistently outperforms DA- Transfooorr by 0.96 BLEU on average across all settings of graph size. Notably, FA-DAT does not necessarily require large graph size to perform competitively. It makes use of vertices in DAG more efficiently, realizing comparable performance with À = 3 to DA-Transformer with À (26.47 vs 26.55). We attribute the success that fuzzy alignment considers all translation modalities during training. Vertices corresponding to tokens in different modalities are all incorporated in the backward flow with non-negligible gradients. Oppo- sitely, NLL loss only trains paths that are strictly aligned with the reference. As shown in Figure 1, most vertices' token probabilities are close in FA-DAT while are scattered in DA-Transformer. suggests all the vertices in DAG are well calibrated with the fuzzy alignment objective. Since model complexity is quadratic to graph size, massive overhead will introduced with larger graph size. FA-DAT achieves a better trade-off between graph size and translation quality, making the structure of DAG more appealing in practical application.
5 RELATED WORK
Gu et al. (2018) first proposes non-autoregreesive translation to reduce the decoding latency. Com- pared with the autoregressive counterpart, NAT suffers from the performance degradation due to the multi-modality problem and heavily relies on knowledge distilled from autoregressive teacher (Kim & Rush, 2016; Zhou et al., 2020; Tu et al., 2020; Ding al., 2021; Shao et al., 2022b). The multi-modality problem in training data has been analyzed comprehensively in the view of lexical choice (Ding al., 2021), syntactic structure (Zhang et al., 2022) and information theory (Huang et al., 2022b). To mitigate the performance gap, some researchers introduce semi-autoregressive decoding (Wang et al., 2018; Ran et al., 2020: Ghazvininejad iterative decoding mechanisms to refine NAT outputs (Lee et al., 2018; Ghazvininejad et al., 2019; Gu et al., 2019; Kasai al., 2020; Saharia al., 2020; Huang et al., 2022d). However, these ap- proaches inevitably weaken the advantage of fast inference (Kasai et al., 2021). To this end, some researchers focus on improving the training procedure
al., 2020b; Wang et al., 2021) or
fully NAT models. Qian et al. (2021a) introduces glancing training to NAT, which helps the model to calibrate outputs by feeding partial targets. Huang et al. (2022a) further applies a similar idea to middle layers with deep supervision. In another direction, researchers are looking for flexible training objectives that alleviate strict position- wise alignment required by the naive NLL loss. Libovický & Helel (2018) proposes latent alignment model with CTC loss (Graves al., 2006) and Shao & Feng (2022) further explores non-monotonic alignments under CTC loss. Wang et al. (2019) introduces two auxiliary regularization terms to improve the quality of decoder hidden representations. Shao al. (2020; 2021) 1) introduce sequence- level training objectives with reinforcement learning and bag-of-ngrams difference. Ghazvininejad al. (2020a) trains NAT model with the best monotonic alignment found by dynamic program- ming and Du et al. (2021) further extends it to order-agnostic cross-entropy loss. Recently, Huang et al. (2022c) introduces Franransformer, which alleviates multi-modality problem by modeling dependency among vertices in directed acyclic graph. Despite the success of DA-Transforme it still implicitly requires monotonic one-to-one alignment between target tokens and vertices in the training. which weakens its ability to handle multi-modalit
6 CONCLUSION
In this paper, we introduce fuzzy alignment objective between the directed acyclic graph and reference sentence based on n-gram matching. Our proposed objective can better handle predictions with position shift, word reordering, or length variation, which are critical sources of translation molti-modality. Experiments demonstrate that our method facilitates training of DA-Trame Transformer, achieves comparable performance to autoregressive baseline with fully parallel decoding, and sets new state of the art for NAT on the raw training data.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Liang Ding, Longyue Wang, Xuebo Liu, Derek F. Wong, Dacheng Tao, and Zhaopeng Tu. Under- standing and improving lexical choice in non-autoregressive translation. In International Confer- ence on Learning Representations, 2021. URL https: /ttps/////ppeeeei...///o net mwt/forumm forum? - 2IFeSBIX9C.
Cunxiao Du, Zhaopeng Tu, and Jing Jiang. Order-agnostic cross entropy for non-autoregressive ma- chine translation. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2849-2859, PMLR, 18-24 Jul 2021. URL https: pettps://proceeeeee http///ppoceeeccceeeeeee/c/ss.st www.ppess.v......m..m....
du21c. html.
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predict: Parallel decoding of conditional masked language models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Confer- ence on Natural Language Processing (EMNLP-IJCNLP) pp. 6112-6123 Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10. 10.18653/11/DI1-16333 URL htttsss/aallantholoyy.oooo
Marjan Ghazvininejad, Vladimir Karpukhin, Luke Zettlemoyer, and Omer Levy. Aligned cross entropy for non-autoregressive machine translation. In International Conference on Machine Learning, pp. 3515-3523. PMLR, 2020a.
Marjan Ghazvininejad, Omer Levy, and Luke Zettlemoyer. Semi-autoregrrssivve training improves mask-predict decoding. CoRR, abs/2001.0878. 2020b. URL https: org/ abs/ 2001 087008 5.
Alex Graves, Santiago Fernández, Faustino Gomez, and Jürren Schmidhuber. Connectionist tempo- ral classification: Labelling unsegmented sequence data with recurrent neural networks. In Pro- ceedings of the 23rd International Conference on Machine Learning, ICML '06, pp. 369-376, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 10.1 143844. 143891. URL. https: //oii www.oo.g//.............o
1151/111444444444888 43891.
Jiatao Gu and Xiang Kong. Fully non-autoregressive neural machine translation: Tricks of the trade. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pp. 120-133, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/ 2021 .indinngs-all.1111 URL https: h/al://///laaaaaaoooooorooo org/2021 findings acl. .11.
Jiatao Gu, James Bradbury, Caiming Xiong, Victor Li, and Richard Socher. Non-autoregressive
neural machine translation. In International Conference on Learning Representations, 2018. URL
https: htttps://openzevieer net. forum?
Jiatao Gu, Changhan Wang, and Junbo Zhao Levenshtein transformer. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Gameet (eds.), Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, wtw.eeeedddinn....ii...e cc/ccc///aaaa /ptppaapr//////// fb4 4b47 90b4 66 Abstract htttl...c.tt.......
Canada, pp. 11179-11189, 2019. URL https: 201 9 hww.9//hhhhheeeee
Chenyang Huang, Hao Zhou, Osmar R. Zaïane, Lili Mou, and Lei Li. Non-autoregressive translation with layer-wise prediction and deep supervision. In Thirty-Sixii -ixih AAAI Conference on Artificial Intelligence, AAAI 2022, Fhirth-Fourth Conference Innovative Applications of Artificial Intel- ligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 March 2022, pp. 10776-10784. AAAI Press, 2022a. URL https:://///
/ index. php htt.////aattteeveeeeeeeeeeeeeeee
Fei Huang, Tianhua Tao, Hao Zhou, Lei Li, and Minlie Huang. On the learning of non-autoregressive transformers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning. ICML 2022, 17- 23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 9356-9376 PMLR, 2022b. URL https: / /pppceeeiinggssscee mlr. press/ v1 62, 62/hhangg22 html.
10

---

Published as a conference paper at ICLR 2023
Fei Huang, Hao Zhou, Yang Liu, Hang Li, and Minlie Huang. Directed acyclic transformer for non- autoregressive machine translation. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference Machine Learning, 1C21, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 9410-9440 9428.9428. PMLR, 2022c. URL https: pestpps:/prrceeddiiee /ttp///ooeeeeeeeee ngs mmlr. press/vl 62166//6 huang22m..mmmmmm html.
Xiao Shi Huang, Felipe Perez, and Maksims Volkovs. Improving non-autoregressive translation models without distillation. In International Conference on Learning Representations, 2022d.
URL https: https////ppeeeiiiieeeee net. http://eee//etueee/eeeeeee id I2HW58KHHB8
Jungo Kasai, James Cross, Marjan Ghazvininejad, and Jiatao Gu. Non- Non-autoregressive machine translation with disentangled context transformer. In Proceedings of the 37th International Conference on Machine Learning, ICML. 2020, 13-18 July 2020, Viriual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3145-5155. PMIRR 2020. URL http: / /ppoceedings ml press/ / vv 1 9 kasai2Ca, html.
Jungo Kasai, Nikolaos Pappas. Hao Peng, James Cross, and Noah A. Smith. Deep encoder, shal- low decoder: Reevaluating non-autoregressive machine translation. 9th International Confer- ence on Learning Representattions, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenRe- view.net, 2021. URL https:t///// http://pppeeeeeeeeeeeeeeeee net
Yoon Kim and Alexander M. Rush. Sequence-level knowledge distillation. In Jian Su, Xavier Carreras, and Kevin Duh (eds.). Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016, pp. 1317- 1327. The Association for Computational Linguistics, 2016. doi: 10. 10.18653/v1/d16- 139. URL htttps://do http://bbb..rgg/...88///////////
6133
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic non-autoreggessive neural se- quence modeling by iterative refinement. In Proceedings of the 2018 Conference Empir- ical Methods in Natural Language Processing, pp. 1173-1182, Brussels, Belgium, October- November 2018. Association for Computational Linguistics. doi: 10.18653/v1/D18- 1149. URL https: /ttp:://wwwwwee ac web org hwtp:/www.w..hooooggggo/o//////e /
Jindrich Libovický and Jindřich Helel. End-to-end non-autoregressive neural machine translation with connectionist temporal classification. In Proceedings of the 2018 Conference on Empir- ical Methods in Natural Language Processing, pp. 3016-3021, Brussels, Belgium, October- November 2018. Association for Computational Linguistics. doi: 10.18653/11/D11-1333. 1336. URL. http:///aaaaannhooo...ooo
1336.
Nathan Ng. Kyra Yee, Alexei Baevski, Myle Out, Michael Auli, and Sergey Edunov. Facebook fair's WMT19 news translation task submission. In Ondrej Bojar, Rajen Chatterjee, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno- Yepes, Philipp Koehn, André Martins, Christof Monz, Matteo Negri, Aurélie Névéol, Mariana I.. Neves, Matt Post, Marco Turchi, and Karin Verspoor (eds.), Proceedings of the Fourth Conference on Machine Translation, WMT 2019, Florence, Italy, August 1-2, 2019 Volume 2: Shared Task Papers, Day pp. 314-319, Association for Computational Linguisties, 2019. doi: 10.18653/v1/ w19-5333. URL https: /ooi
10 1w..1..155/.1//e// 53333
Myle Ott, Sergey Edunov, Alexci Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fastt extensible toolkit for sequence modeling. In Waleed Am- mar, Annie Louis, and Nasrin Mostafazadeh (eds.). Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-IILT 2019, Minneupolis, MN, USA, June 2-7, 2019, Demonstrations, pp. 48-53. Association for Computational Linguisties, 2019. doi: 10. 10.18653/v11n11-4400 URL https: //tp::://ddi... http:/oo..oogg//// www.oooggo....oo......ooooo 18w.11...111///1 11/119-4009....
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: method for automatic
evaluation of machine translation. In Proceedings of the 40th Anmual Meeting of the Associa- tion for Computational Linguistics, pp. 311-318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics. doi: 1031155/073083..073333. URL https: / //aclanthology htwp:hh/oooo...ooo0/00011000
11

---

Published as a conference paper at ICLR 2023
Matt Post. A call for clarity in reporting BLEU scores. In Ondrej Bojar, Rajen Chatterjee, Chris- tian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno- Yepes, Philipp Koehn, Christof Monz, Matteo Negri, Aurélie Névéol, Mariana L. Neves, Matt Post, Lucia Specia, Marco Turchi, and Karin Verspoor (eds.), Proceedings of the Third Con- ference on Machine Translation: Research Pupers, WMT 2018, Belgium, Brussels, October 31 November 1, 2018, pp. 186-191. Association for Computational Linguistics, 2018. doi: 10.18653/v1/w18-2
URL https: /tw.///.iiio//////////../ owg/oogg///oooo 18653/861vvv httllvlwwlll11/ ww18-6319
Amy Pu, Hyung Won Chung, Ankur P Parikh, Sebastian Gehrmann, and Thibault Sellam. Learning compact metrics for mt. In Proceedings of EMNLP, 2021.
Lihua Qian, Hao Zhou, Yu Bao. Mingxuan Wang. Lin Qiu, Weinan Zhang, Yong Yu, and Lei Li. Glancing transformer for non-autoregressive neural machine translation. Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pp. 2903, On- line, August 2021a. la. Association for Computational Linguisties. doi: 10. 120.l////00....lloooo. 155. URL ht htt///aaaaantlooooo/ee org 2021 acl-long. 155.
Lihua Qian, Yi Zhou, Zaixiang Zheng, Yaoming Zhu, Zehui Lin, Jiangtao Feng, Shanbo Cheng, Lei Li, Mingxuan Wang, and Hao Zhou. The voletrans GLAT system: Non-autoregressive translation meets WMT21. In Proceedings of the Sixth Conference on Machine Translation, pp. 187-196, Online, November 2021b. Association for Computational Linguistics. URL ht https: http///aaaaaahllla/o//e/ org/202//22 2021. wmt-1.17.
Qiu Ran, Yankai Lin, Peng Li, and Jie Zhou. Learning recover from multi multi-modality errors for non-autoregressive neural machine translation. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 3059-3069, Online, July 2020. Association for Computational Linguistics. doi: 10. 10.18653/w12220, main. URL https:// mac.cmmmai...mm 277.
aclweb. org/ anthology/2028
Chitwan Saharia, William Chan, Saurabh Saxena, and Mohammad Norouzi. Non-autoregressive machine translation with latent aligmments. In Proceedings of the 2020 Conference on Empir- ical Methods Natural Language Processing (EMNLP), pp. 1098-1100 Online, November URL
2020. Association for Computational Linguistics. doi: 10. 10.18653/v 12200//mmm.m..mmmma..... https: http://aaaaaaalaaacc org/2020 emnly-maemmmm ma in. 83.
Thibault Sellam, Dipanjan Das, and Ankur P Parikh. Bleurt: Learning robust metrics for text gener- ation. In Proceedings of ACL, 2020.
Rico Sennrich, Barry Haddow. and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Anmual Meeting of the Association for Com- putational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume I: Long Pa- pers. The Association for Computer Linguistics, 2016. doi: 10.18653/w1pp1--1162. URL
https: //oi. www.ooo..o....oooo.ooooooo.o...o 10t.../663vvlle (18653/11/16611111
Chenze Shao and Yang Feng. Non-monotonic latent alignments for CTC-based non-autoregressive machine translation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:// http://wwwwnttorummmmmeeeae (tt.r//oorrm111d0ooaPPPaa1.1
Chenze Shao, Jinchao Zhang, Yang Feng, Fandong Meng, and Jie Zhou. Minimizing the bag-of- ngrams difference for non-autoregressive neural machine translation. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Ad- vances Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 198- 205. AAAI Press, 2020. URL hwt.hhttp//omm //tp://///////////// wtw.oooa.aaa.rrrrrooooooooo wnniiniexx.. wttplee.ppp//.///atiiiii Bilew// 55311.
Chenze Shao, Yang Feng, Jinchao Zhang, Fandong Meng, and Jie Zhou. Sequence-Level Training for Non-Autoregreessvve Neural Machine Translation. Computational Linguistics, pp. 1-35, 10 2021. ISSN 0891-2017. doi: 10.1162/coli a 00421. URL https: //tp///c////////////../ .or. /00./11...0 1162/ col 00421.
12

---

Published as a conference paper at ICLR 2023
Chenze Shao, Zhengrui Ma, and Yang Feng. non-autoregressive machine translation, In Findings of the Association for Computational Lin- guistics: EMNLP 2022, pp. 4390-4397, Abu Dhabi, United Arab Emirates, December 2022a. Association for Computational Linguistics. URL https: : / / antho org/2022. findings-emnil 322.
Viterbi decoding of directed acyelic transformer for
Chenze Shao, Xuanfu Wu, and Yang Feng. One reference reference selection for non-autoregressive translation. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 3779-3791, Seattle, United States, July 2022b. Association for Computational Linguistics. doi: 10. 18653866/v /2wp//22222aaaaii..... 2022. www.haalnannn. m.i.mmai.......
enough: Diverse distillation with
URL https: http::t//caaaathaaaaae http///aaaanntoooooooooooo org/
Lifu Tu, Richard Yuanzhe Pang. Sam Wiseman, and Kevin Gimpel. ENGINE: Energy-based in- ference networks for non-autoregressive machine translation. In Proceedings of the 58th An- mual Meeting of the Association for Computational Linguistics, pp. 2819-2826, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/v 1015///112020..oo acl-main.251 URL attps://aclanthonn
org/2020000 acl200acc--- meel-mman..555 251.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998 6008, 2017. URL https: http:///ppcceeeeg....eee / neurips........................e wwtpccppppppeaeeeee ppaper/2017/// 2017/hashh/// 3f 7 fbdd03c3 c oa Abst html.
Chunqi Wang, Ji Zhang, and Haiqing Chen. Semi-autoregressive neural machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 479-488, Brussels, Belgium, Kttober-November 2018. Association for Computational Lin- ogy/ guistics. doi: 10.18653/v1/D18-1000 URL https::/p/// /wwwww... www.wwaclla acl www.ww.ww.................... D1 D18-1044.
Qiang Wang, Heng Yu, Shaohui Kuang, and Weihua Luo. Hebrid-regressive neural machine trans- lation, 2021. URL https: httptt/////peeeeeveee... net wwweereeiie.nnee/orrrneere
piet7m. Yiren Wang, Fei Tian, Di He, Tao Qin, ChengXiang Zhai, and Tie-Yan Liu. Non-autoreerressiv machine translation with auxiliary regularization. In The Thirty-Third AAAI Conference Artifi- cial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, 2019, pp. 5377-5384. AAAI Press, 2019. doi: 10. 10.1609/aai..v3330 333.....30111337177777333 URL https: /oii org 100 1699 aaai. v33101. 33C15377.
Kexun Zhang, Rui Wang, Xu Tan, Junliang Guo. Yi Ren, Tao Qin, and Tie-Yan Liu. A study of syntactic multi-modality in non-autoregressive machine translation. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguis- tics: Human Language Technologies, pp. 1747-1757, Seattle, United States, July 2022. Asso- ciation for Computational Linguistics. doi: 10.
URL https:
/ //aclanthologg org naacl ma i 126.
Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi Bertscore: Eval- uating text generation with BERT. In 8th International Conference on Learning Representa- fions, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URI. httts:://ppereet
net http:///g..gaeeeeee.eeeeeeeeaaes
Chunting Zhou, Jiatao Gu, and Graham Neubig. Understanding knowledge distillation in non- autoregressive machine translation. In International Conference Learning Representations, 2020. URL https: 2 http://////pp/eeeeeeeee net. forett/orrmmmmmooo wtt.::/wwww...aooo////aa.a......
13

---

Published as a conference paper at ICLR 2023
A
PROOF OF EQUATION 7
We can inspect the NLL gradients from different translation paths in the graph by applying the chain rule:
θ (- log (o(y)a)) C
08
08
Po x) 00 Po(y)))
Po(y.alx))
Po(y)æ) 00
TeT
0
(23)
Po Polyaala)
Polyla)
30
aET
Poly, al))
1
Po
Po(y)ar)
Po a) 00
oET,
Σ aET
Po(aly: y. x.
log Po alx))
00
Note that log Peyy. alx) is the loss of one specific translation path. NLL implicitly assigns each path its posterior probability Po (aly, æ) the weight during training, making paths corresponding to translations in other modalities poorly calibrated.
B PROOF OF EQUATION 13 AND EQUATION 14
We denote the length of arbitrary translation y' and that of path a as Ty and Ta respectively. Note that the averaged length of generated translations should be the same the averaged length of DAG paths:
Σ V
Poly'(a)T
Σ
Po(ala)Ta
(24)
Then have:
Eyl
Σ gEGn(1/)
Co(3')) = Σ Po(v'lz)) Σ Co(y')
gEG..(y))
Σ Poly'Iz)) +
Σ Po(alæ) - n
(25)
Σ Po(al Σ I(U Un aa)
Σ U,)lz)
Un
We can handle (y-lC in similar way. When particular path a is given, it is convenient to calculate the averaged appearance of n-gram g through sliding a window of size on token distributions along the path (Shao et al., 2020):
T--n+1 n
Eyja (C
Σ x0
Σ
Il Po (1
(26)
14

---

Published as a conference paper at ICLR 2023
Then apply the indicator function 1(11, ... U/ a) to transform the enumerating space from the space of n adjacent vertices in path a to the space of arbitrary n vertices graph:
Ey (Cg() = >
Po Ba (C)()
Ia-n+1
Po(a)z
Σ
Il
Po(yylaitz-))
J=1
Σ Po(alæ)
Σ
1(V E a II Po(g)lus)
j=1
(27)
Σ Mires Usa
Σ
Po(ala)) Un aa) II (g
a Polalz)1(1),... on e a) II Po
Σ
Σ
j=1
P(I vn)) II Po(g)
==1
We can find Byy (Cg (v/)) actually a weighted sum of passing probabilities of n-vertex subpaths.
C PROOF EQUATION 18
On the basis of Equation 14 and Equation 15, we first rewrite it as:
n-
n
Σ ((1(0))a=)
II
E E Il Po(g)uu)
(28)
We can construct similar form to Equation 17 by commutating and associating terms in the product:
R-1
n E II Polg)
Ey (Cg(t))
Σ P(I(V)) x)
E
F=1
(29)
Σ ([(1(r)))))PA(()lu))))
E Po [1441]]
Equation 29 indicates that the weighted sum of passing probability shares the same form with the sum of (n 1)-hop transition probabilities of Markov chain with unnormalized initial probability and step-variant transition matrix. The initial probability and the ith step transition probability are given as:
(())))=) ((
(30)
E.G. = Po.
With passing probability vector p and token probability matrix introduced in Section 3.3, equa- tions above can be expressed in matrix form:
6"' p" 3 G1.- D EO G.+1.
(31)
where G,+1, should be broadcast to the size of E. Then we can obtain the expression of Equation 29 in matrix form based on the formula of the sum of transition probabilities in Markov chain:
n-1
[C = 1T
II
D
(32)
= (p c G..) (E 3 G2.) .....
E 3 G..
Considering G is broadcast across rows, removing parentheses in Equation 32 will not change the results:
Ey [C'('')] ||p @ G1, E G2. E Gnall
(33)
15

---

Published as a conference paper at ICLR 2023
D ANALYSIS OF HANDLING MULTI-MODALITY
Generation Fluency We argue that FA-DAT improves NAT performance by better capturing multi- modality with the fuzzy alignment objective. It helps the model avoid generating mixture of different translations. To demonstrate that, we measure the fluency of outputs from different models. The perplexity (PPL) score calculated by a pretrained language model (Ng al., 2019) with context window size 128. Lookahead decoding is applied to DA-Transformer and FA-DAT.
Table 4: Perplexity scores on raw WMT14 EN-DE dataset.
Vanilla-NAT
DA-Transformer
FA-DAT
AT
Reference
PPL
1909.9
495.8
468.6
411.7
395.8
As shown in Table 4, autoregressive translation (AT) model achieves comparable fluency with gold reference while vanilla-NAT suffers a significant drop due to the disability to handle multi-modality. DA-Trame DA-Transformer improves NAT fluency by large margin and proposed FA-DAT further reduces the fluency gap between AT and NAT.
Sequence Length As longer sentences tend to have more complex grammatical structures, multi- modality usually occurs in their translation distribution. Motivated by this, we also investigate model performance for sequences of different lengths. We split the test set of WMT14 EN-DE into different buckets based on reference length and report the translation quality of each bucket in Table
Table 5: BLEU scores of different length buckets on raw WMT14 EN-DE dataset.
DA-Transformer
FA-DAT
L < 20
24.81
25.81
20 < I < 40
26.96
27.89
40 < I < 60
27.33
27.39
L
22.81
25.54
We find that FA-DAT improves the translation quality of all length buckets, especially for L. 2 60, where the gain is 2.73 BLEU. We argue that both word reordering and position shift issues are more common in long sentences due the syntactic multi-modalities, where the model trained by NLL loss will get confused. As shown in Table 5, NLL-trained DA-Transformer suffers a steep performance drop by around 4 BLEU when translating the bucket longest sentences. In contrast, FA-DAT shows a much better ability to deal with long sentences, which demonstrates its effective- ness in handling multi-modality.
E RESULTS ON DISTILLED DATASET
Though FA-DA PA-DAT is proposed to deal with the multi-modall problem which is severe on raw training data, also conduct experiments to evaluate the performance of FA-DAT distilled data, where the data distribution is much simplified. Following Gu et al. (2018), we use Transformer-base as the teacher model generate the distilled dataset. We apply Lookahead decoding both DA- Transformer and FA-DAT and report the results in Table 6.
We find that FA-DAT consistently outperforms DA-Transformer on both settings of training data. However, the improvement on the distilled dataset is relatively marginal. We attribute it to that multi-modality in distilled data is already alleviated due the simplification by the autoregressive teacher. Interestingly. we note that FA-DAT performs better on raw training data by margin of 0.36 BLEU, which shows a distinct feature in contrast to NAT models in the literature. We argue that traditional sequence-level KD limits the performance of NAT model by imposing an upper
phttps://gg tww.. Faceboo resea rsse/ttree/mg /exampl leeelaggage model
16

---

Published as a conference paper at ICLR 2023
Table 6: BLEU scores on raw and distilled WMT14 EN-DE dataset.
DA Transformer
FA-DAT
Raw Distilled
26.56
27.53
26.94
27.17
bound (AT's performance). It demonstrates that NAT model endowed with the ability to handle data multi-modality can benefit more from training on authentic data, showing the potential of further developing stronger NAT models.
F MEASURE TRANSLATION QUALITY WITH LEARNED METRICS
Considering fuzzy alignment objective is a natural fit with n-gram matching- evaluation met- rics, we additionally measure the translation quality with learned metries: BERTScore (Zhang et al., 2020)² and BLEURT (Sellam et al., 2020), which have been demonstrated to correlate well with human judgments. For BLEURT, we use the currently recommended checkpoint BLEURT-20* (Pu et al., 2021) to generate scores. The results are reported in Table 7 and 8.
Table 7: BERTScores on raw WMT14 EN+DD and WMT17 ZH++EN dataset.
EN-DE
DE-EN
ZH-EN
EN-ZH
+reedd
60.86
66.91
56.70
61.64
DA DA-rnassformrr
Lookahead
60.89
67.00
56.97
61.62
Joint- Joint-Viterbi
60.94
67.12
56.63
60.75
+Greddy
62.16
67.48
58.50
62.80
FA-DAT
Lookahead
62.18
67.50
58.51
62.66
JJint- Viterbi
62.17
67.49
58.12
62.53
Table BLEURT scores on raw WMT14 EN+DD and WMT17 ZH+EEN dataset.
EN-DE
DE-EN
ZH-EN
EN-ZH
+Greedy
61.63
68.06
62.14
59.52
DA-Transformer
Lookahead
61.13
68.02
61.87
58,95
Joint Viterbi
61.34
68.13
61.39
58.62
Greedy
64.26
68.14
62.72
60.10
FA-DAT
Lookahead
64.29
68.14
62.70
60.00
Vittt-iitrbi
64.26
68.32
62.44
59.94
As shown in Table 7 and 8, FA-DAT improves both BERTScore and BLEURT scores on all four translation tasks, which consistent with the results BLEU in Table 2. Interestingly, we find Nitt--Viterbi decoding does not show its superiority compared to other decoding approaches, as opposed to the results measured by BLEU Table 2. Moreover, BLEURT tends to prefer transla- tions generated by Greedy decoding, especially for the generation of DA-Transformer. We leave the discussion of those findings in future work.
G QUALITY-LATENCY TRADE-OFF UNDER BATCH DECODING
Gu Kong (2021) has pointed out that the speed advantage of non-autoregressive model shrinks when the size of the decoding batch gets larger. As both DA-Transformer and proposed FA-DAT
"tt t/tptsttt///.././//////ppp com/Ti giggrrbrrrrtt score netpss: /// thub. com/
coo. goog reseerceeechhheeeeeee
17

---

Published as a conference paper at ICLR 2023
obtain the best translation performance at the cost of high upsampling ratio (A 8), the extra overhead computation and memory can make the speedup degradation worse. To have a better understanding of the problem, compare the speed-quality tradeoffs under different settings of upsampling ratio and decoding batch size. The results are plotted in Figure 3.
Speed-quality Tradeoff
27.6
27.4
27.0
BLEU
26.8
26.6
26.4
AT
FA-DAT (AmR)
FA-DAT (A+4)
DAT (A=
26.0
2
10
Relative Speedup
Figure 3: Relative speedup ratio (X-axis) and BLEU score (y-axis) against different settings of batch
decoding size (8: 16: 32:
64:
It is consistent with previous findings that the speedup drops under a large batch setting. Moreover, the degradation becomes even worse with a larger upsampling ratio. As shown in Figure 3, the relative speedup ratio is reduced to around 2 under decoding batch size 64 with 8 times upsampling model. We attribute this problem to the intrinsic property of the directed acyclic graph, which requires large number of redundant vertices model the translation multimodality. However, we find proposed FA-DAT is beneficial to relieve the problem. 4x upsampled FA-DAT achieves a better quality than 8x upsampled DA-Transformer by around 0.5 BLEU with significantly shorter decoding latency. We argue that fuzzy alignment is capable of well-calibrating all the vertices in the graph (as analyzed Section 4.4), which uses upsampled vertices more efficiently and reduces redundancy.
H EFFECTS OF PRETRAINING
We further investigate the effects of NLL pretraining in this section.
Effects of NLL Pretraining
27.26
27
28.84
26.06
26
25
24.55
24
23
22
19:32
10k
50k
100k
200k
Pretrain Steps
Figure 4: BLEU scores of FA-DAT and NLL-pretrained models under different settings of pretrain- ing step. No checkpoint averaging trick is applied for both pretrained model and FA-DAT.
18

---

Published as a conference paper at ICLR 2023
As discussed in Section 3.4, initialize FA-DAT with NLL-trained DA- Transforrrr In this exper- iment, we train FA-DAT from models with different settings of the pretraining step. BLEU scores of FA-DAT and NLL-pretrained models under different settings are plotted in Figure 4.
We find that fuzzy alignment training can boost the performance of NLL-pretrained model under all circumstances. Moreover, initializing FA-DAT with a well-NLLL-peerrinned model can further improve the translation quality. We argue that P-gram-based fuzzy alignment objective models word reordering the cost of ignoring higher (i.e., > n) order dependency. However, such ignored information modeled when trained with NLL loss due to its verbatim alignment property, which makes NLL pretraining complementary and essential fuzzy alignment training.
19


Reviews:
[{"review_id": "wV-p9HkFuk", "reviewer": "Reviewer_zAdY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work improves the DA-Transformer with an N-gram based fuzzy alignment loss for non-autoregressive machine translation. Instead of enforcing strict monotonic alignment and NLL loss in the original DA-Transformer, the proposed method adopts a fuzzy loss similar to N-gram precision in the calculation of BLEU. With evaluations on standard MT datasets, the proposed method is shown to obtain impressive results using raw (non-distilled) training data, bringing improvements over the DA-Transformer and almost closing the gaps to auto-regressive models.", "summary_of_the_review": "Overall I think this paper did a relatively good job on providing an effective algorithm for calculating expected n-grams and pushing the raw-training results close to the auto-regressive ones. My main concern is the evaluation of decoding efficiency, where the large decoder length might have an undesired effect when using batched decoding.", "strength_and_weaknesses": "Strength:\n\nThe work provides an effective way to calculate expected n-gram counts for the DAG-based decoder.\n\nThe results seem impressive, with clear improvements over the baselines and the final FA-DAT models almost close the gaps to auto-regressive ones using raw data.\n\nWeakness:\n\nOne concern is that the proposed model needs to use a relatively large lambda (decoder length) to obtain good enough results. This might not be a problem when performing single-instance decoding, while this brings extra operations and might more obviously affect batched decoding. \n\nThe proposed method seems a natural fit to evaluating using BLEU, but it is unclear with other MT evaluation metrics. (I’m not sure whether BERTScore is a good metric for MT evaluation). \n\nSome more analyses and ablations might be needed, for example, on the effects of the initialization from NLL-trained DA-Transformer, the adaptation of the brief penalty.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "T2TLDm8YoA", "reviewer": "Reviewer_5ZNc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "To alleviate the problem of multi-modality, the paper introduces a training objective that could consider multiple translations in the directed acyclic graph. The method is based on a fuzzy alignment between reference and the directed acyclic graph based on n-gram matching.  Authors explore an alignment score to measure the fuzzy alignment, where an efficient algorithm in linear complexity is developed to cope with the exponential search space.  Experiments on major WMT benchmarks validate the proposed approach.", "summary_of_the_review": "I'd like to see this paper accepted, although some more analysis or experiments may be needed.", "strength_and_weaknesses": "Reasons to accept:\n- the intuition is clear and the solution is straightforward \n- a novel algorithm with linear complexity is proposed to calculate alignment scores, making it viable to exploit exponential search space. \n- the proposed method does not involve knowledge distillation, which is worth noting for NAT. The proposed method keeps the decoding speedup, demonstrating the potential of NAT trained by only raw data. \n\nReasons to reject:\n- it is not clear for how many sentences in the training data suffers from the multi-modality problem. It is not clear whether there are sentences that are more different from the reference, so that the fuzzy alignment does not work at all. It will help if such analysis is provided.\n\n- brief penalty is introduced to prevent the favor for shorter translations. however, it may bring an additional parameter to tune, and make the method less generalize to different datasets or translation distributions. There is no discussion for this issue.\n\n- The experiment section could be improved. This paper proposes the fuzzy alignment for the multi-modality issue, but there are no corresponding experiments for this claim. \n\n\n\nSuggestions:\n\nThe derivation from eq 6 to eq 7 should be presented clearly (in the main body or in an appendix).\n\nWould authors provide more evidence that your approach does improve the DAT's ability for multi-modality? E.g., can FA-DAT cater for the position shifts and word reorderings issues than baselines? \n\nA few examples may also be helpful for demonstrating the effect of the proposed method.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JgmLvTwEEAE", "reviewer": "Reviewer_Qie9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new training method for DAT (SOTA NAT model). The authors hold the view that all paths in the graph are fuzzily aligned with the reference sentence. Hence, they train the model to maximize a fuzzy alignment score between the graph and reference. The proposed method is interesting, and the improvement of performance for DAT is exciting. ", "summary_of_the_review": "The performance of the proposed method is exciting, and the experimental content is complete, but the proposed method is innovative.", "strength_and_weaknesses": "strengths:\n1. The final performance of FA-DAT is exciting.\n2. It is interesting to train NAT models with fuzzy alignment of n-grams, which relaxes the order constraints of n-grams.\n\nweaknesses:\n1. The new training method for DAT is too similar to the proposed training method in [1].\n\n[1] Chenze Shao, Yang Feng. Non-Monotonic Latent Alignments for CTC-Based Non-Autoregressive Machine Translation, NeurIPS 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster