## 4 Our Approach
### Attention-Based Encoder-Decoder Network  
The encoder-decoder framework based on RNN architectures such as LSTMs or GRUs is gaining its popularity for neural machine translation [7; 40; 41; 42] as it successfully replaces the statistical machine translation methods. Given an input sentence \(\mathbf{x}=(x_{1},x_{2},\ldots,x_{T_{x}})\), an encoder RNN plays its role as follows:  
\[h_{t}=\text{RNN}(x_{t},h_{t-1})\]  
where \(h_{t}\in\mathbb{R}^{n}\) is a hidden state at time \(t\). After processing the whole input sentence, the encoder generates a fixed-size context vector that represents the sequence as follows:  
\[c=q(h_{1},h_{2},\ldots,h_{T_{x}}),\]For instance, the RNN is an LSTM cell and \(q\) simply returns the last hidden state \(h_{T_{x}}\) in one of the original sequence to sequence papers by [PERSON] et al. [7]. Now, suppose that \(\mathbf{y}=(y_{1},y_{2},\ldots,y_{T_{y}})\) is an output sentence that corresponds to the input sentence \(\mathbf{x}\) in training set. Then, the decoder RNN is trained to predict the next word conditioned on all the previously predicted words and the context vector from the encoder RNN. In other words, the decoder computes a probability of the translation \(\mathbf{y}\) by decomposing the joint probability into the ordered conditional probabilities as follows:  
\[p(\mathbf{y})=\prod_{i=1}^{T_{y}}p(y_{i}|\{y_{1},y_{2},\ldots,y_{i-1}\},c).\]  
Now, our RNN decoder computes each conditional probability as follows:  
\[p(y_{i}|y_{1},y_{2},\ldots,y_{i-1},c)=\text{softmax}(g(s_{i})),\]  
where \(s_{i}\) is the hidden state of decoder RNN at time \(i\) and \(g\) is a linear transformation that outputs a vocabulary-sized vector. Note that the hidden state \(s_{i}\) is computed by  
\[s_{i}=\text{RNN}(y_{i-1},s_{i-1},c),\]  
where \(y_{i-1}\) is the previously predicted word, \(s_{i-1}\) is the last hidden state of decoder RNN, and \(c\) is the context vector computed from encoder RNN. [PERSON] et al. [40] conjectured that the fixed-length context vector \(c\) is a bottleneck in improving the performance of the translation model and proposed to compute the context vector by automatically searching for relevant parts from the hidden states of encoder. Indeed, this \"attention\" mechanism has proven really useful in various tasks including but not limited to machine translation. They proposed a new model that defines each conditional probability at time \(i\) depending on a dynamically computed context vector \(c_{i}\) as follows:  
\[p(y_{i}|y_{1},y_{2},\ldots,y_{i-1},\mathbf{x})=\text{softmax}(g(s_{i})),\]  
where \(s_{i}\) is the hidden state of the decoder RNN at time \(i\) which is computed by  
\[s_{i}=\text{RNN}(y_{i-1},s_{i-1},c_{i}).\]  
The context vector \(c_{i}\) is computed as a weighted sum of the hidden states from encoder:  
\[c_{i}=\sum_{j=1}^{T_{x}}\alpha_{ij}h_{j},\]  
where  
\[\alpha_{ij}=\frac{\exp(\text{score}(s_{i-1},h_{j}))}{\sum_{k=1}^{T_{x}}\exp( \text{score}(s_{i-1},h_{k}))}.\]  
Here, the function \"score\" is called an _alignment function_ that computes how well the two hidden states from the encoder and the decoder, respectively, match. For example, \(\text{score}(s_{i},h_{j})\), where \(s_{i}\) is the hidden state of the encoder at time \(i\) and \(h_{j}\) is the hidden state of the decoder at time \(j\) implies the probability of aligning the part of the input sentence around position \(i\) and the part of the output sentence around position \(j\). [PERSON] attention.Later, [PERSON] et al. [41] examined a novel attention mechanism which is very similar to the attention mechanism by [PERSON] et al. but different in some details. First, only the hidden statesof the top RNN layers in both the encoder and decoder are used instead of using the concatenation of the forward and backward hidden states of the bi-directional encoder and the hidden states of the uni-directional non-stacking decoder. Second, the computation path is simplified by computing the attention matrix after computing the hidden state of the decoder at current time step.