Word alignment, which aims to align translationally equivalent words between source and target sentences, plays an important role in many natural language processing tasks. Current unsupervised neural alignment methods focus on inducing alignments from neural machine translation models, which does not leverage the full context in the target sequence. In this paper, we propose MASK-ALIGN , a self-supervised word alignment model that takes advantage of the full context on the target side. Our model parallelly masks out each target token and predicts it conditioned on both source and the remaining target tokens. This two-step process is based on the assumption that the source token contributing most to recovering the masked target token should be aligned. We also introduce an attention variant called leaky attention , which alleviates the problem of high cross-attention weights on specific tokens such as periods. Experiments on four language pairs show that our model outperforms previous unsupervised neural aligners and obtains new state-of-the-art results. 1 1 Introduction Word alignment is an important task of finding the correspondence between words in a sentence pair (Brown et al., 1993) and used to be a key component of statistical machine translation (SMT) (Koehn et al., 2003; Dyer et al., 2013). Although word alignment is no longer explicitly modeled in neural machine translation (NMT) (Bahdanau et al., 2015; Vaswani et al., 2017), it is often leveraged to analyze NMT models (Tu et al., 2016; Ding et al., 2017). Word alignment is also used in many other scenarios such as imposing lexical constraints on the decoding process (Arthur et al., 2016; Hasler  Corresponding author 1 Code can be found at https://github.com/THUNLP-MT/ Mask-Align. Induced alignment link: Tokio Tokyo et al., 2018), improving automatic post-editing (Pal et al., 2017) , and providing guidance for translators in computer-aided translation (Dagan et al., 1993). Compared with statistical methods, neural methods can learn representations end-to-end from raw data and have been successfully applied to supervised word alignment (Yang et al., 2013; Tamura et al., 2014). For unsupervised word alignment, however, previous neural methods fail to significantly exceed their statistical counterparts such as FAST-ALIGN (Dyer et al., 2013) and GIZA++ (Och and Ney, 2003). Recently, there is a surge of interest in NMT-based alignment methods which take alignments as a by-product of NMT systems (Li et al., 2019; Garg et al., 2019; Zenkel et al., 2019, 2020; Chen et al., 2020). Using attention weights or feature importance measures to induce alignments for to-be-predicted target tokens, these methods outperform unsupervised statistical aligners like GIZA++ on a variety of language pairs. Although NMT-based unsupervised aligners have proven to be effective, they suffer from two major limitations. First, due to the autoregressive w 1 + p 1 w 2 + p 2 w 4 + p 4 EncoderLayer w 3 + p 3 h1 h 2 h 4 h 3 w 1 +p 1 p 1 w 2 +p 2 p 2 w 3 +p 3 p 3 w 4 +p 4 p 4 t 4 t 3 Static-KV Attention Leaky Attention Feed Forward  L L  (cid:72)(cid:76)(cid:81) (cid:75)(cid:88)(cid:81)(cid:71) (cid:85)(cid:68)(cid:81)(cid:81)(cid:87)(cid:72) (cid:90)(cid:72)(cid:74) (cid:68) (cid:71)(cid:82)(cid:74) (cid:85)(cid:88)(cid:81)(cid:86) (cid:68)(cid:90)(cid:68)(cid:92) (cid:68) t 1 t 2 t 1 t 2 t 3 t 4 h 1 h 2 h 3 h 4 Linear & Softmax (cid:71)(cid:82)(cid:74) (cid:85)(cid:88)(cid:81)(cid:86) (cid:68)(cid:90)(cid:68)(cid:92) Attention Weights Alignment (cid:68) (cid:71)(cid:82)(cid:74) (cid:85)(cid:88)(cid:81)(cid:86) (cid:68)(cid:90)(cid:68)(cid:92) (cid:72)(cid:76)(cid:81) (cid:75)(cid:88)(cid:81)(cid:71) (cid:85)(cid:68)(cid:81)(cid:81)(cid:87)(cid:72) (cid:90)(cid:72)(cid:74) Figure 2: The architecture of MASK-ALIGN . property of NMT systems (Sutskever et al., 2014), they only leverage part of the target context. This inevitably brings noisy alignments when the prediction is ambiguous. Consider the target sentence in Figure 1. When predicting Tokyo, an NMT system may generate 1968 because future context is not observed, leading to a wrong alignment link (1968, Tokyo). Second, they have to incorporate an additional guided alignment loss (Chen et al., 2016) to outperform GIZA++. This loss requires pseudo alignments of the full training data to guide the training of the model. Although these pseudo alignments can be utilized to partially alleviate the problem of ignoring future context, they are computationally expensive to obtain. In this paper, we propose a self-supervised model specifically designed for the word alignment task, namely MASK-ALIGN . Our model parallelly masks out each target token and recovers it conditioned on the source and other target tokens. Figure 1 shows an example where the target token Tokyo is masked out and re-predicted. Intuitively, as all source tokens except Tokio can find their counterparts on the target side, Tokio should be aligned to the masked token. Based on this intuition, we assume that the source token contributing most to recovering a masked target token should be aligned to that target token. Compared with NMT-based methods, MASK-ALIGN is able to take full advantage of bidirectional context on the target side and hopefully achieves higher alignment quality. We also introduce an attention variant called leaky attention to reduce the high attention weights on specific tokens such as periods. By encouraging agreement between two directional models both for training and inference, our method consistently outperforms the state-of-the-art on four language pairs without using guided alignment loss. Figure 2 shows the architecture of our model. The model predicts each target token conditioned on the source and other target tokens and generates alignments from the attention weights between source and target (Section 2.1). Specifically, our approach introduces two attention variants, static-KV attention and leaky attention , to efficiently obtain attention weights for word alignment. To better utilize attention weights from two directions, we encourage agreement between two unidirectional models during both training (Section 2.2) and inference (Section 2.3). Conventional unsupervised neural aligners are based on NMT models (Peter et al., 2017; Garg et al., 2019). Given a source sentence x = x 1 , . . . , x J and a target sentence y = y 1 , . . . , y I , NMT models the probability of the target sentence conditioned on the source sentence: P ( y | x ;  ) = I (cid:89) i =1 P ( y i | y <i , x ;  ) (1) where y <i is a partial translation. One problem of this type of approaches is that they fail to exploit the future context on the target side, which is probably helpful for word alignment. y i conditioned on the source sentence x and the remaining target tokens y \ y i : This equals to masking out each y i and then recovering it. We build our model on top of Transformer (Vaswani et al., 2017) which is the state-of-the-art sequence-to-sequence architecture. Next, we will discuss in detail the implementation of our model. As self-attention is fully-connected, directly computing (cid:81) Ii =1 P ( y i | y \ y i , x ;  ) with a vanilla Transformer requires I separate forward passes, in each of which only one target token is masked out and predicted. This is costly and time-consuming. Therefore, how to parallelly mask out and predict all target tokens in a single pass is important. To do so, a major challenge is to avoid the representation of a masked token getting involved in the prediction process of itself. Inspired by Kasai et al. (2020), we modify the self-attention in the Transformer decoder to perform the forward passes concurrently. Given the word embedding w i and position embedding p i for target token y i , we first separate the query inputs q i from key k i and value inputs v i to prevent the to-be-predicted token itself from participating in the prediction: q i = p i WQ (3) k i = ( w i + p i ) WK (4) v i = ( w i + p i ) WV (5) where WQ , WK and WV are parameter matrices. The hidden representation h i for y i is computed by attending to keys and values, K (cid:54) = i and V (cid:54) = i , that correspond to the remaining tokens y \ y i : h i = Attention( q i , K (cid:54) = i , V (cid:54) = i ) (6) K (cid:54) = i = Concat( { k m | m (cid:54) = i } ) (7) V (cid:54) = i = Concat( { v m | m (cid:54) = i } ) (8) In this way, we ensure that h i is isolated from the word embedding w i in a single decoder layer. However, there exists a problem of information leakage if we update the key and value inputs for each position across decoder layers since they will contain the representation of each position from previous layers. Therefore, we keep the key and value inputs unchanged and only update the query inputs I was born in in 1968 Ich wurde 1968 in Tokio geboren Tokyo . where q li and h li denote the query inputs and hidden states for y i in the l -th layer, respectively. h 0 i is initialized with p i . We name this variant of attention the static-KV attention . By static-KV, we mean the keys and values are unchanged across different layers in our approach. Our model replaces all self-attention in the decoder with static-KV attention. Extracting alignments from vanilla cross-attention often suffers from the high attention weights on some specific source tokens such as periods, [EOS], or other high frequency tokens (see Figure 3). This is similar to the garbage collectors effect (Moore, 2004) in statistical aligners, where a source token is aligned to too many target tokens. Hereinafter, we will refer to these tokens as collectors . As a result of such effect, many target tokens (e.g., the 0.5 0.5 not true falsch 1.0 1.0 not true falsch not true falsch 0.4 0.4 0.2 [NULL] 0.2 0.4 not true falsch 0.8 0.6 [NULL] leaky attention vanilla attention Figure 4: An illustrative example of the attention weights from two directional models using vanilla and leaky attention. Leaky attention provides a leak position [NULL] to collect extra attention weights. two ins in Figure 3) will be incorrectly aligned to the collectors according to the attention weights. This phenomenon has been studied in previous works (Clark et al., 2019; Kobayashi et al., 2020). Kobayashi et al. (2020) show that the norms of the value vectors for the collectors are usually small, making their influence on attention outputs actually limited. We conjecture that this phenomenon is due to the incapability of NMT-based aligners to deal with tokens that have no counterparts on the other side because there is no empty (NULL) token that is widely used in statistical aligners (Brown et al., 1993; Och and Ney, 2003). We propose to explicitly model the NULL token with an attention variant, namely leaky attention . As shown in Figure 4, when calculating cross-attention weights, leaky attention provides an extra leak position in addition to the encoder outputs. Acting as the NULL token, this leak position is expected to address the biased attention weight problem. To be specific, we parameterize the key and value vectors as k NULL and v NULL for the leak position in the cross-attention, and concatenate them with the transformed vectors of the encoder outputs. The attention output z i is computed as follows: z i = Attention( h Li WQ , K , V ) (11) K = Concat( k NULL , H enc WK ) (12) V = Concat( v NULL , H enc WV ) (13) where H enc denotes encoder outputs. 2 A similar attention implementation can be found in https://github.com/pytorch/fairseq/blob/master/fairseq/ modules/multihead attention.py. deviation to initialize k NULL and v NULL to ensure that their initial norms are rather small. When extracting alignments, we only consider the attention matrix without the leak position. Note that leaky attention is different from adding a special token in the source sequence, which will share the same high attention weights with the existing collector instead of calibrating it (Vig and Be-linkov, 2019). Our parameterized method is more flexible than Leaky-Softmax (Sabour et al., 2017) which adds an extra dimension with the value of zero to the routing logits. In Section 2.2, we will show that leaky attention is also helpful for applying agreement-based training on two directional models. We remove the cross-attention in all but the last decoder layer. This makes the interaction between the source and target restricted in the last layer. Our experiments demonstrate that this modifica-tion improves alignment results with fewer model parameters. To better utilize the attention weights from two directions, we apply an agreement loss in the training process to improve the symmetry of our model, which has proven effective in statistical alignment models (Liang et al., 2006; Liu et al., 2015). Given a parallel sentence pair (cid:104) x , y (cid:105) , we can obtain the attention weights from two different directions, denoted as W x  y and W y  x . As alignment is bijective, W x  y is supposed to be equal to the transpose of W y  x . We encourage this kind of symmetry through an agreement loss: L a = MSE (cid:16) W x  y , W (cid:62) y  x (cid:17) (14) where MSE represents the mean squared error. For vanilla attention, L a is hardly small because of the normalization constraint. As shown in Figure 4, due to the use of softmax activation, the minimal value of L a is 0 . 25 for vanilla attention. Using leaky attention, our approach can achieve a lower agreement loss ( L a = 0.1) by adjusting the weights on the leak position. However, our model may converge to a degenerate case of zero agreement loss where attention weights are all zero except for the leak position. We circumvent this case by introducing an entropy loss on the attention weights: L e, x  y =  1 II (cid:88) i =1 J (cid:88) j =1  W ij x  y log  W ij (15)  W ij x  y = W ij x  y +  (cid:80) j ( W ij x  y +  ) (16) where  W ij x  y is the renormalized attention weights and  is a smoothing hyperparamter. Similarly, we have L e, y  x for the inverse direction. We jointly train two directional models using the following loss: L = L x  y + L y  x +  L a +  ( L e, x  y + L e, y  x ) (17) where L x  y and L y  x are NLL losses,  and  are hyperparameters. When extracting alignments, we compute an alignment score S ij for y i and x j as the harmonic mean of attention weights W ij x  y and W ji y  x from two directional models: S ij = 2 W ij x  y W ji y  x W ij x  y + W ji y  x We use the harmonic mean because we assume a large S ij requires both W ij x  y and W ji y  x to be large. Word alignments can be induced from the alignment score matrix as follows: A ij = (cid:26) 1 if S ij   0 otherwise (19) where  is a threshold. We conducted our experiments on four public datasets: German-English (De-En), English-French (En-Fr), Romanian-English (Ro-En) and Chinese-English (Zh-En). The Chinese-English training set is from the LDC corpus that consists of 1.2M sentence pairs. For validation and testing, we used the Chinese-English alignment dataset from Liu et al. (2005) 3 , which contains 450 sentence pairs for validation and 450 for testing. For other three language pairs, we followed the experimental setup in 3 http://nlp.csai.tsinghua.edu.cn/  ly/systems/ TsinghuaAligner/TsinghuaAligner.html (Zenkel et al., 2019, 2020) and used the preprocessing scripts from Zenkel et al. (2019) 4 . Following Ding et al. (2019), we take the last 1000 sentences of the training data for these three datasets as validation sets. We used a joint source and target Byte Pair Encoding (BPE) (Sennrich et al., 2016) with 40k merge operations. During training, we filtered out sentences with the length of 1 to ensure the validity of the masking process. We implemented our model based on the Transformer architecture (Vaswani et al., 2017). The encoder consists of 6 standard Transformer encoder layers. The decoder is composed of 6 layers, each of which contains static-KV attention while only the last layer is equipped with leaky attention. We set the embedding size to 512, the hidden size to 1024, and attention heads to 4. The input and output embeddings are shared for the decoder. We trained the models with a batch size of 36K tokens. We used early stopping based on the prediction accuracy on the validation sets. We tuned the hyperparameters via grid search on the Chinese-English validation set as it contains gold word alignments. In all of our experiments, we set  = 0 . 05 (Eq. (16)),  = 5 ,  = 1 (Eq. (17)) and  = 0 . 2 (Eq. (19)). The evaluation metric is Alignment Error Rate (AER) (Och and Ney, 2000). We introduce the following unsupervised neural baselines besides two statistical baselines FASTALIGN and GIZA++: NAIVE-ATT (Garg et al., 2019): a method that induces alignments from cross-attention weights of the best (usually penultimate) decoder layer in a vanilla Tranformer. NAIVE-ATT-LAST : same as NAIVE-ATT except that only the last decoder layer performs cross-attention. ADDSGD (Zenkel et al., 2019): a method that adds an extra alignment layer to repredict the to-be-aligned target token. MTL-FULLC (Garg et al., 2019): a method that supervises an attention head with symmetrized NAIVE-ATT alignments in a multitask learning framework. 4 https://github.com/lilt/alignment-scripts Method Guided De-En En-Fr Ro-En Zh-En FAST-ALIGN (Dyer et al., 2013) N 25.7 12.1 31.8 -GIZA++ (Och and Ney, 2003) N 17.8 6.1 26.0 18.5 NAIVE-ATT (Garg et al., 2019) N 31.9 18.5 32.9 28.9 NAIVE-ATT-LASTN 28.4 17.7 32.4 26.4 ADDSGD (Zenkel et al., 2019) N 21.2 10.0 27.6 MTL-FULLC (Garg et al., 2019) N 20.2 7.7 26.0 BAO (Zenkel et al., 2020) N 17.9 8.4 24.1 SHIFT-ATT (Chen et al., 2020) N 17.9 6.6 23.9 20.2 MTL-FULLC-GZ (Garg et al., 2019) Y 16.0 4.6 23.1 -BAO-GUIDED (Zenkel et al., 2020) Y 16.3 5.0 23.4 SHIFT-AET (Chen et al., 2020) Y 15.4 4.7 21.2 17.2 MASK-ALIGNN 14.4 4.4 19.5 13.8 Table 1: Alignment Error Rate (AER) scores on four datasets for different alignment methods. BAO (Zenkel et al., 2020): an improved version of ADDSGD that extracts alignments with Bidirectional Attention Optimization. SHIFT-ATT (Chen et al., 2020): a method that induces alignments when the to-be-aligned tatget token is the decoder input instead of the output. We also included three additional baselines with guided training: (1) MTL-FULLC-GZ (Garg et al., 2019) which replaces the alignment labels in MTLFULLC with GIZA++ results, (2) BAO-GUIDED (Zenkel et al., 2020) which uses alignments from BAO for guided alignment training, (3) SHIFTAET (Chen et al., 2020) which trains an additional alignment module with supervision from symmetrized SHIFT-ATT alignments. Table 1 shows the results on four datasets. Our approach significantly outperforms all statistical and neural baselines. Specifically, it improves over GIZA++ by 1.7-6.5 AER points across different language pairs without using any guided alignment loss, making it a good substitute to this commonly used statistical alignment tool. Compared to SHIFTATT , the best neural methods without guided training, our approach achieves a gain of 2.2-6.4 AER points with fewer parameters (as we remove some cross-attention sublayers in the decoder). stantial improvements over all methods. For example, on the Romanian-English dataset, it improves over SHIFT-AET by 1.7 AER points. Recall that our method is fully end-to-end, which does not require a time-consuming process of obtaining pseudo alignments for full training data. Table 2 shows the ablation results on the German-English dataset. As we can see, masked modeling seems to play a critical role since removing it will deteriorate the performance by at least 9.0 AER. We also find that leaky attention and agreement-based training and inference are both important. Removing any of them will significantly diminish human rights throughout the world in 1995 1996 MR i n de r w e l t 1995 \ 1996 Figure 5 shows the attention weights from vanilla and leaky attention and Table 3 presents the norms of the transformed value vectors of each source token for two types of attention. For vanilla attention, we can see large weights on the high frequency token der and the small norm of its transformed value vector. As a result, the target token in will be wrongly aligned to der. While for leaky attention, we observe a similar phenomenon on the leak position  [NULL] , and in will not be aligned to any source tokens since the weights on all source tokens are small. This example shows leaky attention can effectively prevent the collector phenomenon. Removing End Punctuation To further investigate the performance of leaky attention, we tested an extraction method that excludes the attention weights on the end punctuation of a source sentence. The reason behind this is that when the source sentence contains the end punctuation, it will act as the collector in most cases. Therefore removing it will Method w/ punc. alleviate the effect of collectors to a certain extent. Table 4 shows the comparison results. For vanilla attention, removing end punctuation obtains a gain of 7.7 AER points. For leaky attention, however, such extraction method brings no improvement on alignment quality. This suggests that leaky attention can effectively alleviate the problem of collectors. Case Study Figure 6 shows the attention weights from four different models for the example in Figure 1. As we have discussed in Section 1, in this example, NMT-based methods might fail to resolve ambiguity when predicting the target token tokyo. From the attention weight matrices, we can see that NMT-based methods (Figures 6(b) and 6(c)) indeed put high weights wrongly on 1968 in the source sentence. As for MASK-ALIGN , we can see i was born in tokyo in 1968 . that the attention weights are highly consistent with the gold alignment, showing that our method can generate sparse and accurate attention weights. Prediction and Alignment We analyzed the relevance between the correctness of word-level prediction and alignment. We regard a word as correctly predicted if any of its subwords are correct and as correctly aligned if one of its possible alignment is matched. Figure 7 shows the results. We divide target tokens into four categories: 1. cPcA: correct prediction & correct alignment; 2. wPcA: wrong prediction & correct alignment; 3. cPwA: correct prediction & wrong alignment; 4. wPwA: wrong prediction & wrong alignment. Compared with other methods, MASK-ALIGN significantly reduces the alignment errors caused by wrong predictions (wPwA). In addition, the number of the tokens with correct prediction but wrong alignment (cPwA) maintains at a low level, indicating that our model does not degenerate into a target masked language model despite the use of bidirectional target context. Our work is closely related to unsupervised neural word alignment. While early unsupervised neural aligners (Tamura et al., 2014; Alkhouli et al., 2016; Peter et al., 2017) failed to outperform their statistical counterparts such as FAST-ALIGN (Dyer et al., 2013) and GIZA++ (Och and Ney, 2003), recent studies have made significant progress by inducing alignments from NMT models (Garg et al., 2019; Zenkel et al., 2019, 2020; Chen et al., 2020). Our work differs from prior studies in that we design a novel self-supervised model that is capable of utilizing more target context than NMT-based models to generate high quality alignments without using guided training. Our work is also inspired by the success of conditional masked language models (CMLMs) (Ghazvininejad et al., 2019), which have been applied to non-autoregressive machine translation. The CMLM can leverage both previous and future context on the target side for sequence-to-sequence tasks with the masking mechanism. Kasai et al. (2020) extend it with a disentangled context Transformer that predicts every target token conditioned on arbitrary context. By taking the characteristics of word alignment into consideration, we propose to use static-KV attention to achieve masking and aligning in parallel. To the best of our knowledge, this is the first work that incorporates a CMLM into alignment models. We have presented a self-supervised neural alignment model MASK-ALIGN . Our model parallelly masks out and predicts each target token. We propose static-KV attention and leaky attention to achieve parallel computation and address the garbage collectors problem, respectively. Experiments show that MASK-ALIGN achieves new state-of-the-art results without using the guided alignment loss. In the future, we plan to extend our method to directly generate symmetrized alignments without leveraging the agreement between two unidirectional models. This work was supported by the National Key R&D Program of China (No. 2017YFB0202204), National Natural Science Foundation of China (No.61925601, No. 61772302) and Huawei Noah's Ark Lab. We thank all anonymous reviewers for their valuable comments and suggestions on this work.
abstain abstain objective method abstain abstain objective abstain abstain other abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain objective abstain abstain abstain objective abstain method result method abstain method method abstain other abstain abstain abstain method method abstain abstain abstain abstain method other method method method abstain abstain abstain abstain method abstain abstain abstain other abstain abstain method abstain abstain abstain method abstain other abstain method abstain method abstain method abstain abstain method method abstain method abstain abstain abstain method method method method method method abstain method abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain result abstain result abstain result abstain abstain result abstain result result abstain abstain result abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain result result abstain abstain result result abstain abstain abstain abstain abstain abstain abstain other objective method other other objective objective method method objective abstain objective other other