Google

In practical decoding algorithms, the search space consists of an exponentially large number of sequences. To prevent the computational load from growing exponentially with sequence length, strategies are used to prune the space. At each decoding step, the set of candidate sequences $$Y_i$$ is formed by applying a pruning function to the full set of expanded hypotheses: $$Y_i = \mathrm{Prune}(Y_{i-1} \times V)$$. The $$\mathrm{Prune}(\cdot)$$ function selectively removes sequences less likely to result in high-quality outcomes. Consequently, the number of sequences under consideration is drastically reduced, ensuring that $$|Y_i| \ll |Y_{i-1}| \cdot |V|$$.

Formula for Pruned Step-wise Expansion of the Hypothesis Set

Based on the provided scenario, what specific modification should be made to the engineer's formula to make the generation process computationally feasible? Explain why this modification solves the problem of the system running out of memory.

Diagnosing a Failing Sequence Generation Algorithm

In a sequence generation task, the set of candidate sequences at step `i-1` contains 3 distinct sequences (i.e., |Y_{i-1}| = 3). The vocabulary size is 1,000 (i.e., |V| = 1,000). The generation process uses the formula `Y_i = Prune(Y_{i-1} × V)`, where the `Prune(·)` function is configured to keep only the 2 most promising sequences.

Based on this information, calculate:
1. The size of the full set of expanded hypotheses (`Y_{i-1} × V`) before pruning.
2. The size of the final set of candidate sequences (`Y_i`) after pruning.

Applying Pruning in Sequence Generation

In a sequence generation process, the set of candidate sequences at step `i`, denoted `Y_i`, is generated from the previous set `Y_{i-1}` and the entire vocabulary `V`. Consider the difference between two methods for generating `Y_i`:

Method A: `Y_i = Y_{i-1} × V`
Method B: `Y_i = Prune(Y_{i-1} × V)`

What is the most significant practical difference in the outcome of using Method B instead of Method A, particularly for generating longer sequences?

Learn Before

Related