Beam search optimization (Wiseman and Rush, 2016) resolves many issues in neural machine translation. However, this method lacks principled stopping criteria and does not learn how to stop during training, and the model naturally prefers longer hypotheses during the testing time in practice since they use the raw score instead of the probability-based score. We propose a novel ranking method which enables an optimal beam search stopping criteria. We further introduce a structured prediction loss function which penalizes suboptimal finished candidates produced by beam search during training. Experiments of neural machine translation on both synthetic data and real languages (German  English and Chinese  English) demonstrate our proposed methods lead to better length and BLEU score. Sequence-to-sequence (seq2seq) models based on RNNs (Sutskever et al., 2014; Bahdanau et al., 2014), CNNs (Gehring et al., 2017) and self-attention (Vaswani et al., 2017) have achieved great successes in Neural Machine Translation (NMT). The above family of models encode the source sentence and predict the next word in an autoregressive fashion at each decoding time step. The classical cross-entropy training objective of seq2seq models is to maximize the likelihood of each word in the translation reference given the source sentence and all previous words in that reference. This word-level loss ensures efficient and scalable training of seq2seq models. However, this word-level training objective suffers from a few crucial limitations, namely the label bias , the exposure bias , and the loss-evaluation mismatch (Lafferty et al., 2001; Bengio et al.,  Equal contribution BSOBSO This work This work Figure 1: The BLEU score of BSO decreases after beam size 3 as results of increasing length ratio 1 in German  English translation. Our model gets higher BLEU with larger beam. 2015a; Venkatraman et al., 2015). In addition, more importantly, at decoding time, beam search is universally adopted to improve the search quality, while training is fundamentally local and greedy. Several researchers have proposed different approaches to alleviate above problems, such as reinforcement learning-based methods (Ran-zato et al., 2016; Rennie et al., 2017; Zheng et al., 2018b), training with alternative references (Shen et al., 2016; Zheng et al., 2018a). Recently, Wiseman and Rush (2016) attempt to address these issues with a structured training method, Beam Search Optimization (BSO). While BSO outperforms other proposed methods on German-to-English translation, it also brings a different set of problems as partially discussed in (Ma, 2018) which we present with details below. 1 There are two types of length ratios in this paper: (a) target to reference ratio ( | y | / | y  | ), which is used in BLEU, and (b) target to source ratio ( | y | / | x | ). By default, the term length ratio in this paper refers to the former. BSO relies on unnormalized raw scores instead of locally-normalized probabilities to get rid of the label bias problem. However, since the raw score can be either positive or negative, the optimal stopping criteria (Huang et al., 2017) no longer holds, e.g., one extra decoding step would increase the entire unfinished hypothesis's model score when we have positive word score. This leads to two consequences: we do not know when to stop the beam search and it could return overlength translations (Fig. 1) or underlength translations (Fig. 3) in practice. As shown in Fig. 1, the BLEU score of BSO drops significantly when beam size gets larger as a result of overlong translations (as evidenced by length ratios larger than 1). Furthermore, BSO performs poorly (shown in Section 4) on hard translation pairs, e.g., Chinese  English (Zh  En) translation, when the target / source ratio is more diverse (Table 1). To overcome the above issues, we propose to use the sigmoid function instead of the raw score at each time step to rank candidates. In this way, the model still has probability properties to hold optimal stopping criteria without label bias effects. Moreover, we also encourage the model to generate the hypothesis which is more similar to gold reference in length. Compared with length reward-based methods (Huang et al., 2017; Yang et al., 2018), our model does not need to tune the predicted length and per-word reward. Experiments on both synthetic and real language translations (De  En and Zh  En) demonstrate significant improvements in BLEU score over strong baselines and other methods. Here we briefly review the conventional NMT and BSO (Wiseman and Rush, 2016) to set up the notations. For simplicity, we choose to use RNN-based model but our methods can be easily applied to other designs of seq2seq model as well. Regardless of the particular design of different seq2seq models, generally speaking, the decoder always has the following form: p ( y | x ) = (cid:81) | y | t =1 p ( y t | x , y <t ) (1) where x  RN  D represents the D -dimension hidden states from encoder with N words and y <t denotes the gold prefix ( y 1 , ..., y ( t  1) ) before t. The conventional NMT model is locally trained to maximize the above probability. Instead of maximizing each gold word's probability, BSO tries to promote the non-probabilistic scores of gold sequence within a certain beam size b . BSO removes the softmax layer and directly uses the raw score after hidden-to-vocabulary layer, and the non-probabilistic scoring function f x ( y t | y <t ) represents the score of word y t given gold prefix y <t and x . Similarly, f x ( y bt |  y b<t ) is the b th sequence with beam size b at time step t . Then, we have the following loss function to penalize the b th candidate and promote gold sequence: L = | y | (cid:88) t =1 ( y b  t )(1 + f x ( y bt |  y b<t )  f x ( y t | y <t )) + (2) where ( y b  t ) is defined as (1  BLEU ( y b  t , y  t )) which scales the loss according to BLEU score between gold and b th hypothesis in the beam. The notation (  ) + represents a max function between any value and 0 , i.e., z + = max (0 , z ) . When Eq. 1 equals to 0 at time step t , then the gold sequence's score is higher than the last hypothesis in the beam by 1, and a positive number otherwise. Finally, at the end of beam search ( t = | y | ), BSO requires the score of y exceed the score of the highest incorrect hypothesis by 1 . Note that the above non-probabilistic score function f x (  ) is not bounded as probabilistic score in conventional NMT. In practice, when we have positive word score, then the unfinished candidates always get higher model scores with one extra decoding step and the optimal stopping criteria 2 (Huang et al., 2017) is no longer hold. BSO implements a similar shrinking beam strategy which duplicates top unfinished candidate to replace finished hypotheses and terminates the beam search when there are only </eos> in the beam. Non-probabilistic score function works well in parsing and Statical MT where we know when to stop beam search. However, in the NMT scenario, without optimal stopping criteria, we don't know when to stop beam search. As mentioned in Section 2, BSO relies on raw score function to eliminate label bias effects. 2 Beam search stops when the score of the top unfinished hypothesis is lower than any finished hypothesis, or the </eos> is the highest score candidate in the beam. However, without using locally-normalized score does not mean that we should stop using the probabilistic value function. Similar with multi-label classification in (Ma et al., 2017), instead of using locally normalized softmax-based score and non-probabilistic raw scores, we propose to use another form of probabilistic scoring function, sigmoid function, which is defined as follows: g x ( y t | y <t ) = (1 + e w  f x ( y t | y <t ) )  1 (3) where w is a trainable scalar parameter which shifts the return value of f x ( y t | y <t ) into a nonsaturated value region of sigmoid function. Eq. 3 measures the probability of each word independently which is different from locally-normalized softmax function. Similar to the scenario in multi-label classification, g x ( y t | y <t ) only promotes the words which are preferred by gold reference and does not degrade other words. Eq. 3 enables the model to keep the probability nature of scoring function without introducing label bias effects. After the model regain probability-based scoring function, the optimal stopping criteria can be used in testing time decoding. Similar to Eq. 1, testing time decoder multiplies the new word's probabilistic score with prefix's score when there is a new word appends to an unfinished hypothesis. Though the new word's probabilistic score is upper bounded by 1, in practice, the score usually far less than one. As described in (Huang et al., 2017; Yang et al., 2018), decoder always prefers short sentence when we use the probabilistic score function. To overcome the above so-called  beam search curse , we propose to penalize early-stopped hypothesis within the beam during training. The procedure during training is illustrated in Fig. 2. Data Split | x |  ( | x | ) ( | y | | x | )  ( | y | | x | ) # sents Synthetic Train 9.47 5.45 3.0 0.52 5K Valid 9.54 5.42 3.0 0.53 1K Test 9.51 5.49 3.0 0.52 1K De  En Train 17.53 9.93 1.07 0.16 153K Valid 17.55 9.97 1.07 0.16 7K Test  18.89 12.82 1.06 0.16 6.5K Zh  En Train 23.21 13.44 1.30 0.33 1M Valid 29.53 16.62 1.34 0.22 0.6K Test 26.53 15.99 1.4 0.24 0.7K Table 1: Dataset statistics of source sentence length and the ratio between target and source sentences. Different from BSO, to penalize the underlength finished translation hypotheses, we include additional violations when there is an </eos> within the beam before the gold reference finishes and we force the score of that </eos> lower than the b + 1 candidate by a margin. This underlength translation violation is formally defined as follows: L s = | y | (cid:88) t =1 b (cid:88) j =1 1 ( y jt = </eos> )  Q ( y jt ,  y b +1 t ) , Q ( y jt ,  y b +1 t ) = (1 + f x ( y jt |  y j<t )  f x ( y b +1 t |  y b +1 <t )) + (4) where notation 1 is identification function which only equals to 1 when i th candidate in beam  y jt is </eos> , e.g. in Fig. 2. We only have non-zero loss when the model score of underlength translation candidates are greater than the b + 1 candidate by a margin. In this way, we penalize all the short hypotheses during training time. Note that during both training and testing time, the decoder stops beam search when it satisfies the optimal stopping criteria (Huang et al., 2017). Therefore, we do not need to penalize the overlength translations since we have already promoted the gold reference to the top of the beam at time step | y | during training. We showcase the performance comparisons over three different datasets. We implement seq2seq model, BSO and our proposed model based on PyTorch-based OpenNMT (Klein et al., 2017). We use a two-layer bidirectional LSTM as the encoder and a two layer LSTM as the decoder. We train Seq2seq model for 20 epochs to minimize perplexity on the training dataset, with a batch size of 64, word embedding size of 512, the learning rate of 0.1, learning rate decay of 0.5 and dropout rate of 0.2. Following Wiseman and Rush (2016), we then train BSO and our model based on the previous Seq2seq model with the learning rate of 1 3 5 7 9 Beam Size 0 1 2 3 L e n g t h R a t i o Seq2seq BSO This work Figure 3: Length ratio on synthetic test dataset. 0.01 and learning rate decay of 0.75, batch size of 40. Note that our pretrained model is softmax-based, and we only replace the softmax layer with the sigmoid layer for later training for simplicity. The performance will have another boost when our pretrained model is sigmoid-based. We use Adagrad (Duchi et al., 2011) as the optimizer. In Zh  En task, we employ BPE (Sennrich et al., 2015) which reduces the source and target language vocabulary sizes to 18k and 10k. Following BSO, we set the decoding beam size smaller than the training beam size by 1. 4.1 Synthetic Task Table 1 shows the statistics of source sentence length and the ratio between target and source sentences. The synthetic dataset is a simple translation task which generates target sentences from this grammar: { a  x, b  x x, c  x x x, d  x x x x, e  x x x x x } . For example: 1. source sentence [ b c a ] will generate the target sentence [ x x x x x x ] (2 x from b , 3 x from c and 1 x from a ). 2. source sentence [ a, b, c, d, e ] will be translated into [ x x x x x x x x x x x x x x x ] in target side (1 x from a , 2 x from b , 3 x from c , 4 x from d and 5 x from e ). This dataset is designed to evaluate the length prediction ability of different models. Fig. 3 shows the length ratio of different models on the test set. Only our model can predict target sentence length correctly with all beam sizes which shows a better ability to learn target length. The De  En dataset is previously used in BSO and MIXER (Ranzato et al., 2016), which is from IWSLT 2014 machine translation evaluation campaign (Cettolo et al., 2014) 3 . 3 The test set of De  En involves some mismatched source-reference pairs. We have cleaned this test set and report the statistics based on the cleaned version. Table 2 shows the BLEU score and length ratio of different models on dev-set. Similar to seq2seq, our proposed model achieves better BLEU score with larger beam size and outperforms the best BSO b = 4 model with 0.76 BLEU. The ablation study in Table 3 shows that the model produces shorter sentence without scale augment (term ( y b  t ) in Eq. 2) and early stopping loss. The model also performs worse when replacing softmax to sigmoid because of the label bias problem. Fig. 4 shows BLEU score and length ratio of BSO and our models trained with beam size b = 6 with different decoding beam size. Compared with BSO, whose BLEU score degrades dramatically when increasing beam size, our model performs much more stable. Moreover, BSO achieves much better BLEU score with decoding beam b = 3 while trained with b = 6 because of a better Model Original Test Set Cleaned Test Set BLEU Len. length ratio, this is inconsistent with their claim that decoding beam size should smaller than training beam size by 1. Table 4 shows better accuracy of our proposed model than not only published test results of BSO (Wiseman and Rush, 2016), DAD (Bengio et al., 2015b) and MIXER (Ranzato et al., 2016), but also our implemented seq2seq and BSO model. 4.3 Zh  En Translation Model Train Decode BLEU Len. translation dataset. We use the NIST 06 and 08 dataset with 4 references as the validation and test set respectively. Table 1 shows that the characteristic of Zh  En translation is very different from De  En in source length and variance in tar-get/source length ratio. We compare our model with seq2seq, BSO and seq2seq with length reward (Huang et al., 2017) which involves hyper-parameter to solve neural model's tendency for shorter hypotheses (our proposed method does not require tuning of hyper-parameter). Fig. 5 shows that BSO prefers overlength hypotheses in short source sentences and underlength hypotheses when the source sentences are long. This phenomenon degrades the BLEU score in dev-set from Table 5. Our proposed model comparatively achieves better length ratio on almost all source sentence length in dev-set. Our proposed methods are general techniques which also can be applied to the Transformer (Vaswani et al., 2017). As part of our future works, we plan to adapt our techniques to the Transformer to further evaluate our model's performance. There are some scenarios that decoding time beam search is not applicable, such as the simultaneous translation system proposed by Ma et al. (2018) which does not allow for adjusting the committed words, the training time beam search still will be helpful to the greedy decoding performance. We plan to further investigate the performance of testing time greedy decoding with beam search optimization during training. We propose two modifications to BSO to provide better scoring function and under-translation penalties, which improves the accuracy in De-En and Zh-En by 0.8 and 3.7 in BLEU respectively. This work was supported in part by DARPA grant N66001-17-2-4030, and NSF grants IIS-1817231 and IIS-1656051.
abstain abstain objective method objective abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective abstain method method abstain abstain method other abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method other abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain other method other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain objective objective other