greedy decoding limitations

Topics

• greedy decoding

Locally optimal choices may lead to suboptimal overall sequences. Greedy decoding is fast, but if we put aside efficiency for a minute, it might seem more reasonable to search for the most likely sequence, i.e. maximize:

$$\underset{\begin{array}{c}\text{Product over}\\ \text{all timesteps}\end{array}}{\underbrace{\prod _{t=1}^T}}P(\underset{\begin{array}{c}\text{Predicted}\\ \text{output at}\\ \text{time t}\end{array}}{\underbrace{{\hat{y}}_t}}\mid \underset{\begin{array}{c}\text{Previously predicted}\\ \text{outputs up to t-1}\end{array}}{\underbrace{{\hat{y}}_1,\dots ,{\hat{y}}_{t-1}}},\underset{\begin{array}{c}\text{Context}\\ \text{vector}\\ \text{from encoder}\end{array}}{\underbrace{\mathbf{c}}})$$

and not the sequence of (greedily selected) most likely tokens.

Example

• Input: hy het my met 'n tert geslaan
• Target: he hit me with a pie
• Decoding steps: he → he hit → he hit a (locally optimal, but potentially suboptimal)

Thus, greedy approach can lead to irreversible suboptimal choices, as it doesn’t consider future implications of current decisions.

In above case, greedy will pick The nice woman since the probs are 0.5 x 0.4 = 0.2, instead of picking The dog has whose probs will be 0.4 x 0.9 = 0.36 (globally better).

Related