## 2 Materials and Methods
### Our Image Captioning Method
#### 2.3.5 Beam Search Strategy  
The LSTM model [13] takes the context vector \(z\) from the attention module and computes the hidden state \(h_{t}\) at each time step \(t\), as follows:  
\[f_{t}=\sigma_{g}(W_{f}z_{t}+U_{f}h_{t-1}+b_{f}) \tag{6}\] \[i_{t}=\sigma_{g}(W_{i}z_{t}+U_{i}h_{t-1}+b_{i})\] (7) \[o_{t}=\sigma_{g}(W_{o}z_{t}+U_{o}h_{t-1}+b_{o})\] (8) \[c_{t}=f_{t}\circ c_{t-1}+i_{t}\circ\sigma_{c}(W_{c}z_{t}+U_{c}h_ {t-1}+b_{c})\] (9) \[h_{t}=o_{t}\circ\sigma_{h}(c_{t}) \tag{10}\]  
where \(f_{t},i_{t},o_{t}\) are forget gate, input gate and output gate, respectively. The forget gate \(f_{t}\) adjusts the information from the previous time step used to compute the new hidden state while input gate \(i_{t}\) adjusts the information from the input vector \(z_{t}\). The output is the processed through the output gate \(o_{t}\) to compute the final hidden state \(h_{t}\). The hidden state is then processed through a classifier to compute the probabilities of all words in the vocabulary set. The generated word is chosen based on the probability of each word. The hidden state \(h_{t}\) is also fed back into the attention modules to compute new context vector \(z_{t}\). The process is repeated until the model generates a special <END> character that mark the end of the sentence. During training, we use the word from ground truth to compute the context vector \(z_{t}\) in order to avoid error from the previous time step. The generated caption is compared with the ground truth to compute the loss function. We train our whole model by minimizing the loss function stochastic gradient descent with momentum. During testing, the ground truth is not accessible. Therefore, the previous generated word is used to compute the context vector \(z\). This could lead to a chain of errors if the previous word is wrongly selected. To avoid this, we apply our modified beam search strategy presented in [17]. Figure 4 shows our beam search strategy. Given probabilities of all words in the vocabulary set, we choose top \(k\) words with the highest probabilities, excluding the special <END> character. Then, each of the \(k\) words is used to generate a new list of probabilities. The new generated probabilities is combined with the probability of their ascendants to compute the scores of the sequences as follows:  
\[score(w)=\log P(w)+\log P(\textit{Ascendants}(w)) \tag{11}\]  
From the scores of the sequences, we choose the next top \(k\) for the next time step. Unlike beam search strategy in some other methods, beside choosing the sequence with the highest score to be  
Figure 4: Our beam search strategy. the final candidate, we apply a heuristic to adjust the result. Choosing the sequence with the highest score may lead to an incomplete sentence because longer sentences get lower scores due to more multiplication. To avoid this, we use the probability of the <END> character to select the final candidate. If the probability of the <END> character is in the top k, we consider that sequence could be a complete sentence. If the current candidate is an incomplete sentence, it is immediately replaced by the new sequence that has high probability of the <END> character. If both are complete sentence, the scores are compared to choose the better candidate. With this heuristic, our model favors complete sentence over incomplete ones. Additional our previous work [17], in this work, we add one more heuristic to favor long sentences over short sentences because longer sentence can describe more details than a shorter one. We apply the formula in [25] to adjust the score at each time step. Concretely, we divide the score with the length normalization score so that the scores of long sentences do not reduce rapidly due to the multiplication of small numbers. The length normalization is computed as follows:  
\[normalize(w)=score(w)/lp(w) \tag{12}\] \[lp(w)=\frac{(5+|w|)^{\gamma}}{(5+1)^{\gamma}} \tag{13}\]  
where \(score(w)\) is the probability of the sequence computed as in Equation (11).