STAT946F17/Decoding with Value Networks for Neural Machine Translation
Introduction
Background Knowledge
- NTM
Neural Machine Translation (NMT), which is based on deep neural networks and provides an end- to-end solution to machine translation, uses an RNN-based encoder-decoder architecture to model the entire translation process. Specifically, an NMT system first reads the source sentence using an encoder to build a "thought" vector, a sequence of numbers that represents the sentence meaning; a decoder, then, processes the "meaning" vector to emit a translation. (Figure 1)[1]
- Sequence-to-Sequence(Seq2Seq) Model
- Two RNNs: an encoder RNN, and a decoder RNN
1) The input is passed though the encoder and it’s final hidden state, the “thought vector” is passed to the decoder as it’s initial hidden state.
2)Decoder given the start of sequence token, <SOS>, and iteratively produces output until it outputs the end of sequence token, <EOS>
- Commonly used in text generation, machine translation, and related problems
- Beam Search
Decoding process:
Problem: Choosing the word with highest score at each time step t is not necessarily going to give you the sentence with the highest probability(Figure 3). Beam search solves this problem (Figure 4). Beam search is a heuristic search algorithm such that at each time step t, it takes the top m proposal and continues decoding with each one of them. In the end, you will get a sentence with the highest probability not in the word level. The algorithm terminates if all sentences are completely generated, i.e., all sentences are ended with the <EOS> token.
value network
Upon the success of NMT with beam search, beam search tends to focus more on short-term reward, which is called myopic bias. At time t, a word $w$ may be appended to the candidates $y_{<t-1} = y_1,...,y_{t}$ if $P(y_{<t}+w|x) > P(y_{<t}+w'|x)$ even if the word $w'$ is the ground truth translation at step t or can offer a better score in future decodings. By applying the concept of value function in Reinforcement Learning (RL), the authors develop a neural network-based prediction model, the value network for NMT, to estimate the long-term reward when appending $w$ to $y_{<t}$ to address the myopic bias.
The value network takes the source sentence and any partial target sequence as input, and outputs a predicted value to estimate the expected total reward (e.g. BLEU[2]) so that select the best candidates in the decoding step is based on both conditional probability of the partial sequence outputted by the NMT model and the estimated long-term reward outputted by the value network.
Contributions
1) Developing a decoding scheme that considers long-term reward while generating words one by one for machine translation.
2) Building another two modules for the value network, a semantic matching module and a context-coverage module. The semantic matching module estimates the similarity between the source and target sentences. The context-coverage module measures the coverage of context used in the encoder-decoder layer obseraving the fact that better translation is generated when using more context in the attention mechanism.
Results of translation experiments demonstrate the effectiveness and robustness of the new decoding mechanism compared to several baseline algorithms.
Neural Machine Translation
NTM systems are implemented with a RNN based encoder-decoder framework, which directly models the probability $P(y|x)$ of a target sentence $y = {y_1,...,y_{T_y}}$ conditioned on the source sentence $x = {x_1,...,x_{T_x}}$, where $T_x$ and $T_y$ are the length of sentence x and y.
The encoder of NMT reads the source sentence x word by word and generates a hidden representation for each word xi: $$ h_i = f(h_{i-1},x_i) $$ where function f is the recurrent unit such as LSTM unit or GRU.
Then the decoder of NMT computes the conditional probability of each target word $y_t$ conditioned on its proceeding words y<t and source sentence: $$ \begin{align*} c_t = q(r_{t-1};h_1,...,h_{T_x})\\ r_t = g(r_{t-1},y_{t-1},c_t)\\ P(y_t|y_{<t},x)\propto exp(y_t;r_t,c_t) \end{align*} $$ where,
$c_t$: weighted contextual information summarizing the source sentence x using some attention mechanism.
$r_t$: decoder RNN hidden representation at step t, computed by an LSTM or GRU
Notations:
- $Θ$: All learned parameters
- $π_{Θ}$: Translation model with parameter $Θ$
- D: training dataset that contains source-target sentence pairs.
The training process aims at seeking the optimal parameters $Θ^*$ using MLE to encode source sentence and decode it into the target sentence. [math]\displaystyle{ Θ^* = \displaystyle\arg\max_{Θ} \prod\limits_{(x,y)∈D}P(y|x;Θ) = \displaystyle\arg\max_{Θ}\prod\limits_{(x,y)∈D}\prod\limits^{T_y}_{t=1}P(y_t|y_{\lt t},x;Θ) }[/math]
Value Network for NMT
Motivation: Beam search has limited ability at predicting a high-quality sentence due to myopic bias. [3][3] introduced scheduled sampling approach, which takes the generated outputs from the model and the golden truth sentence in training to help the model learn from its own errors but cannot avoid the myopic bias of beam search during testing. [4][4] learns a predictor to predict the ranking score of a certain word at step t, and use this score to replace the conditional probability outputted by the NMT model for beam search during testing. Unfortunately, this work still looks only one step forward and cannot address the problem. Thus the authors motivate to estimate the expected performance of any sequence during decoding based on the concept of value function in reinforcement learning.
Value Network Structure
In conventional reinforcement learning, a value function describes how much cumulated reward could be collected from state s by following certain policy π. In NMT, consider $x$ and $y_{<t}$ as the state, $π_{Θ}$ as policy which can generate a word (action) given any state. The value function characterizes the expected translation performance (e.g. BLEU score) when using $π_{Θ}$ to translate $x$ with the previous t-1 words, $y_{<t}$. The value function is defined as:
[math]\displaystyle{ v(x,y_{\lt t}) = \sum\limits_{y'∈Y: y'_{\lt t}=y_{\lt t}}BLEU(y^*(x),y')P(y'|x;Θ) }[/math]
where $y^*(x)$: ground truth translation, $Y$: the space of complete sentence.
Two modules are developed to fully exploit the information in the encoder-decoder framework.
Semantic Matching (SM) Module: at time step, use mean pooling over the decoder RNN hidden states and the over the context states as summarizations of the partial target sequence and the context in source language. Then use a feed-forward network to evaluate semantic information between the source sentence and the target sentence.
i.e.,
$\bar{r_{t}} = \frac{1}{t}\sum\limits^{t}_{l=1}r_l$
$\bar{c_{t}} = \frac{1}{t}\sum\limits^{t}_{l=1}c_l$
$𝜇_{SM} = f_{SM}([bar{r_{t}},bar{c_{t}}])$
References
[1] https://github.com/tensorflow/nmt
[2] https://en.wikipedia.org/wiki/BLEU
[3] S. Bengio, O. Vinyals, N. Jaitly, and N. Shazeer. Scheduled sampling for sequence prediction with recurrent neural networks. In Advances in Neural Information Processing Systems, pages 1171–1179, 2015.
[4] S. Wiseman and A. M. Rush. Sequence-to-sequence learning as beam-search optimization. In EMNLP, 2016.