Beam search over a bigram model

Greedy decoding commits to one word at a time. Beam search keeps several candidates and can find a more probable sentence.

What to build

A program that runs beam search over a table of next-word probabilities.

Requirements

  • Start with one beam: the start word, probability 1.
  • Repeat L times: extend each beam by each successor of its last word (multiplying the probabilities), drop beams with no successors, and keep the B best by probability (ties: alphabetical order of the whole text).
  • Print the final beams, best first, as TEXT P with P to 4 decimal places; if none survive, print no sequence.

Input

Line 1: m. Then m lines prev next probability. Then a line start B L.

Output

Up to B lines.

Constraints

1 ≤ m ≤ 1000; 1 ≤ B ≤ 10; 1 ≤ L ≤ 10.

Example

Input:

9
the cat 0.5
the dog 0.4
the end 0.1
cat sat 0.3
cat ran 0.3
cat ate 0.4
dog sat 0.9
dog ran 0.1
end . 1.0
the 2 2

Output:

the dog sat 0.3600
the cat ate 0.2000

Why it works

Keeping B candidates lets a sequence that starts with a less likely word survive long enough to show that it leads to a more probable whole, which greedy decoding can never discover.

Examples

Example 1 · Input
9
the cat 0.5
the dog 0.4
the end 0.1
cat sat 0.3
cat ran 0.3
cat ate 0.4
dog sat 0.9
dog ran 0.1
end . 1.0
the 2 2
Expected output
the dog sat 0.3600
the cat ate 0.2000
Example 2 · Input
2
a b 1.0
b c 1.0
a 1 2
Expected output
a b c 1.0000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

A beam is a list of words and its probability; extend every beam with every successor of its last word.

Hint 2

A beam whose last word has no successors is dropped.

Hint 3

Sort candidates by probability (highest first), then by their text, and keep the first B.

Solution

Show one correct solution (try it yourself first)
m = int(input())
following = {}
for _ in range(m):
    a, nxt, p = input().split()
    following.setdefault(a, []).append((nxt, float(p)))
start, b, l = input().split()
beams = [([start], 1.0)]
for _ in range(int(l)):
    candidates = []
    for words, prob in beams:
        for nxt, p in following.get(words[-1], []):
            candidates.append((words + [nxt], prob * p))
    candidates.sort(key=lambda c: (-c[1], " ".join(c[0])))
    beams = candidates[: int(b)]
if not beams:
    print("no sequence")
for words, prob in beams:
    print(f"{' '.join(words)} {prob:.4f}")

Lesson: Decoding: temperature, top-k, top-p and beam search →