Machine Translation

13.4 Decoding: beam search

1. What is the problem with greedy decoding for MT, illustrated by a search tree?
   A locally most probable token may lead to a worse sequence: if “yes” (0.5) beats “ok” (0.4) at step 1, greedy picks yes, even if “ok ok” has the highest total probability.

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, pp. 286–287
2. Why can’t dynamic programming (Viterbi) or exhaustive search be used for MT decoding?
   Generation has long-distance dependencies between output decisions, so dynamic programming doesn’t apply, and exhaustive search over all \(V^T\) sentences is far too slow.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, p. 287
3. What is beam search?
   A heuristic search keeping the \(k\) best hypotheses (partial translations with their probabilities) at each step: extend each with every vocabulary token, score the \(k \times V\) candidates, and prune back to the best \(k\). \(k\) is the beam width.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, p. 287
4. When does beam search stop, and what does it return?
   When a hypothesis generates EOS it is complete and removed from the frontier, and the beam shrinks by one; search continues until the beam is empty, returning \(k\) complete hypotheses.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, p. 288
5. How are beam search hypotheses scored?
   By the log probability of the sequence, built incrementally with the chain rule: \(\text{score}(y) = \sum_{i=1}^{t}\log P(y_i \mid y_1, \ldots, y_{i-1}, x)\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, p. 288
6. Why is length normalization needed in beam search, and how is it done?
   Language models give longer strings lower probabilities, so completed hypotheses of different lengths would favor short outputs. Divide the log probability by the number of words: \(\frac{1}{t}\log P(y \mid x)\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, p. 289
7. What beam widths are typical in MT?
   Between 5 and 10.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, p. 289
8. What is minimum Bayes risk (MBR) decoding?
   Instead of the most probable translation, choose the one likely to have the least error: from a set of candidate translations \(Y\) (e.g. 32–64 samples), pick the candidate most similar to all the others, \(\hat{y} = \arg\max_{y \in Y}\sum_{c \in Y}\text{util}(y, c)\), with a utility like chrF, BLEU or BERTScore.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, pp. 289–290
9. Where else has MBR decoding been used?
   Widely in speech recognition before MT, and in other generation tasks such as summarization, dialogue and image captioning.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 13, §13.4, p. 291