Beam Search

As discussed, the aim of machine translation is to translate from one language (say French) to another language (say English) using a many-to-many encoder-decoder RNN.

The translated sentence is outputted word by word.

We must find the most probable translation.

The Beam Search algorithm helps us do so. It has a parameter called the beam width (say b).

First, the algorithm chooses b possible words as the first word of the translated sentence. Then, for each of these words, the next most probable word is chosen, and so on. (If b=1, it is a greedy approach, since it will choose a single most probable word at each step, but this may not be accurate/efficient). So, using larger b values will lead to a more accurate translation, however it will also be more computationally intensive.

Also, note that unlike exact search algorithms, such as the Breadth-First Search (BFS) or Depth-First Search (DFS), the Beam Search algorithm is an approximate search model, and doesn’t always find the exact maximum. Thus, it doesn’t always output the most likely sentence.

Optimizing Beam Search - Length Normalization

This is one way to optimize the Beam Search algorithm.

Since Beam Search internally computes a product of several probabilities, the result will be a very small number that is difficult for a computer to store accurately. So, instead of maximizing this product, we take the log instead. This results in a more numerically-stable algorithm, less prone to rounding errors.

Another unintended effect of the product is that it gets smaller for longer sentences since there will be more probabilities to multiply, thereby causing the algorithm to prefer shorter sentences. This may, however, not be accurate. So, we normalize the log of the product by the number of words in the output sentence, say n (in practice we normalize with $n^{0.7}$)

Error Analysis in Beam Search

Say the actual translation is y_actual, but Beam Search resulted in y_predicted. (x is the input sentence).

If P(y_actual | x) > P(y_predicted | x), then Beam Search is at fault because it failed to output the sentence with the maximum probability. In such a case, increasing the beam width may help.

If P(y_actual | x) <= P(y_predicted | x), then the RNN is at fault because it wrongly predicted the probabilities. In such a case, it may help to get more training data, use regularization, try a different network architecture etc.