Fine-tune a bigram model

Fine-tuning keeps what a model learned and adds the new data, here counted with a weight.

What to build

A program that builds a bigram model from a pretraining text, adds a fine-tuning text, and shows the next-word predictions before and after.

Requirements

  • Count each pair of neighbouring words in the pretraining text once. Count each pair in the fine-tuning text w times, in the same table.
  • Print base: and tuned: with up to three next words after the query word as WORD P, separated by , , P to two decimal places.
  • Print none if the query word has no next word in that model.

Input

Line 1: the pretraining text. Line 2: the fine-tuning text. Line 3: the weight w. Line 4: the query word.

Output

Two lines.

Constraints

Texts of 2 to 200 words. 1 ≤ w ≤ 10.

Example

Input:

the cat sat . the dog ran . the cat ran .
the order is late . the order is lost .
2
the

Output:

base: cat 0.67, dog 0.33
tuned: order 0.57, cat 0.29, dog 0.14

Why it works

The tuned model has all the old counts plus the new ones, so the new text pulls probability towards its own words without erasing what the base model knew.

Examples

Example 1 · Input
the cat sat . the dog ran . the cat ran .
the order is late . the order is lost .
2
the
Expected output
base: cat 0.67, dog 0.33
tuned: order 0.57, cat 0.29, dog 0.14
Example 2 · Input
the cat sat . the dog ran . the cat ran .
the order is late . the order is lost .
2
order
Expected output
base: none
tuned: is 1.00

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

Hints

Hint 1

Count the pretraining text with weight 1 first, then add the fine-tuning counts multiplied by the weight into the same table.

Hint 2

Show the three most likely next words, sorted by count (highest first) and then alphabetically, with their probability to two decimal places.

Solution

Show one correct solution (try it yourself first)
pre = input().split()
fine = input().split()
w = int(input())
word = input()


def counts(words, weight, table):
    for a, b in zip(words, words[1:]):
        table.setdefault(a, {})
        table[a][b] = table[a].get(b, 0) + weight
    return table


def top(table, word):
    after = table.get(word)
    if not after:
        return "none"
    total = sum(after.values())
    ranked = sorted(after.items(), key=lambda kv: (-kv[1], kv[0]))[:3]
    return ", ".join(f"{x} {c / total:.2f}" for x, c in ranked)


base = counts(pre, 1, {})
tuned = counts(fine, w, counts(pre, 1, {}))
print("base:", top(base, word))
print("tuned:", top(tuned, word))

Lesson: Fine-tuning and alignment →