Beam Search Decoder
Implement beam search for sequence decoding.
Beam search maintains the top-k (beam width) partial sequences at each step, expanding each with all possible next tokens and keeping only the top-k overall.
Input format:
- Line 1: beam_width max_length
- Line 2: Number of vocabulary tokens V
- Lines 3 to V+2: token probability_given_previous_token (uniform for simplicity)
- Line V+3: Number of transition rules T
- Lines V+4 to V+T+3: prev_token next_token probability
The model uses: P(next | prev) from transition rules. Missing transitions have probability 0. Start token is <s>. End token is </s>. Score = product of probabilities (use log sum).
Output: The top beam_width sequences with their log-probabilities, sorted by score descending. Format: each line is "word1 word2 ... : log_prob"
Example:
2 3 3 a b </s> 4 <s> a 0.6 <s> b 0.4 a </s> 0.7 b </s> 0.8
a : -0.6931 b : -1.1394
Step 1: Expand <s>
- <s> -> a: log(0.6) = -0.5108
- <s> -> b: log(0.4) = -0.9163 Keep top 2: [a (-0.5108), b (-0.9163)]
Step 2: Expand both
- a -> </s>: -0.5108 + log(0.7) = -0.5108 + (-0.3567) = -0.8675. But wait...
Actually with the given probabilities, let me recalculate:
- a -> </s>: log(0.6) + log(0.7) = -0.5108 + (-0.3567) = -0.8675 => "a" (completed)
- b -> </s>: log(0.4) + log(0.8) = -0.9163 + (-0.2231) = -1.1394 => "b" (completed)
Both completed. Sort by score: a : -0.8675 b : -1.1394
Hmm, let me use the exact values from the code.
Constraints:
- Use log probabilities to avoid underflow
- At each step, expand all beams with all possible next tokens
- Keep only top beam_width candidates
- Stop expanding a beam when </s> is generated
- max_length includes </s> but not <s>
- Output completed sequences sorted by log prob (highest first)
- Round log probs to 4 decimal places
Background Knowledge
Machine Translation is a subfield of Natural Language Processing (NLP) that involves translating text from one language to another. One key approach to machine translation is sequence-to-sequence modeling, where the goal is to generate a sequence of tokens (words or characters) in the target language given a sequence of tokens in the source language. Beam search is a heuristic search algorithm used to find the most likely sequence of tokens in the target language.
In the context of sequence-to-sequence modeling, beam search is used to efficiently explore the vast space of possible sequences. The algorithm maintains a set of partial sequences, each with a corresponding score (or probability), and iteratively expands each sequence with all possible next tokens. The beam width determines the number of top-scoring sequences to keep at each step. By using beam search, we can avoid exploring the entire sequence space and focus on the most promising candidates.
The probability model used in this problem is based on transition rules, where the probability of a token given the previous token is defined by a set of rules. The score of a sequence is calculated as the product of the probabilities of each token given the previous token, which can be efficiently computed using log probabilities to avoid underflow issues. The goal is to find the top-scoring sequences with their corresponding log probabilities.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.