Smoothed word probabilities

Naive Bayes needs P(word | class) for every word, including words the class never used. Compute them with Laplace smoothing.

What to build

A program that computes Laplace-smoothed word probabilities for one class.

Requirements

  • V is the number of different words in all the training messages.
  • For each query word print WORD: P with P = (count of the word in the class + 1) / (number of words in the class + V), with 4 decimal places.

Input

Line 1: t. Then t messages, each a label followed by its words. Then a line with the class. Then a line with the query words.

Output

One line per query word.

Constraints

1 ≤ t ≤ 200; the class has at least one message; words are lower case.

Example

Input:

6
spam win money now
spam free money offer
spam win a free prize
ham meeting at noon
ham project meeting tomorrow
ham lunch at noon tomorrow
spam
free money meeting

Output:

free: 0.1304
money: 0.1304
meeting: 0.0435

Why it works

Adding 1 to every count gives unseen words a small probability instead of 0, and adding V to the total keeps the probabilities of all vocabulary words summing to 1.

Examples

Example 1 · Input
6
spam win money now
spam free money offer
spam win a free prize
ham meeting at noon
ham project meeting tomorrow
ham lunch at noon tomorrow
spam
free money meeting
Expected output
free: 0.1304
money: 0.1304
meeting: 0.0435
Example 2 · Input
2
a x y
b y z
a
y z
Expected output
y: 0.4000
z: 0.2000

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

Hints

Hint 1

Count the words of the chosen class's messages, and the different words across all messages (V).

Hint 2

P(word | class) = (count + 1) / (total words in the class + V).

Solution

Show one correct solution (try it yourself first)
t = int(input())
messages = [input().split() for _ in range(t)]
label = input().strip()
vocabulary = {w for m in messages for w in m[1:]}
words = [w for m in messages if m[0] == label for w in m[1:]]
for word in input().split():
    print(f"{word}: {(words.count(word) + 1) / (len(words) + len(vocabulary)):.4f}")

Lesson: Bayes' rule and Naive Bayes →