NLP: Train and apply Naive Bayes

Train a multinomial Naive Bayes classifier and label new messages.

What to build

A program that trains Naive Bayes with add-one smoothing and classifies messages.

Requirements

  • Training lines are label: text; lowercase and split on whitespace. V is the number of distinct training words.
  • For a message, ignore words that never occurred in training. A class's score is ln(prior) plus the sum over the remaining words (repeats included) of ln((count of the word in the class + 1) ÷ (word tokens in the class + V)).
  • For each message print the best label, then each label's score as label=S with three decimal places, labels in alphabetical order. On a tie, choose the alphabetically first label.

Input

Line 1: n. Then n training lines. Then m and m messages.

Output

m lines.

Constraints

n ≤ 500; m ≤ 100.

Example

Input:

4
spam: win money now
spam: win a free prize now
ham: meeting at noon
ham: lunch at noon with the team
2
free lunch now
lunch at noon

Output:

spam ham=-9.273 spam=-8.035
ham ham=-7.076 spam=-9.827

Why it works

Adding log probabilities is the same as multiplying the prior by each word's likelihood, so the highest score is the class that makes the message most probable, and smoothing keeps every class possible.

Examples

Example 1 · Input
4
spam: win money now
spam: win a free prize now
ham: meeting at noon
ham: lunch at noon with the team
2
free lunch now
lunch at noon
Expected output
spam ham=-9.273 spam=-8.035
ham ham=-7.076 spam=-9.827
Example 2 · Input
3
pos: good fun
neg: bad boring
pos: great
2
good movie
boring
Expected output
pos neg=-3.045 pos=-1.792
neg neg=-2.351 pos=-2.485

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

Hints

Hint 1

score = `math.log(prior)` plus, for each known word of the message, `math.log((count + 1) / (class words + V))`.

Hint 2

`max(labels, key=lambda c: scores[c])` with labels in alphabetical order returns the alphabetically first label on a tie.

Solution

Show one correct solution (try it yourself first)
import math

n = int(input())
docs, counts, totals, vocab = {}, {}, {}, []
for _ in range(n):
    label, text = input().split(":", 1)
    label = label.strip()
    docs[label] = docs.get(label, 0) + 1
    counts.setdefault(label, {})
    totals.setdefault(label, 0)
    for w in text.lower().split():
        counts[label][w] = counts[label].get(w, 0) + 1
        totals[label] += 1
        if w not in vocab:
            vocab.append(w)
labels = sorted(docs)
for _ in range(int(input())):
    words = [w for w in input().lower().split() if w in vocab]
    scores = {}
    for label in labels:
        s = math.log(docs[label] / n)
        for w in words:
            s += math.log((counts[label].get(w, 0) + 1) / (totals[label] + len(vocab)))
        scores[label] = s
    best = max(labels, key=lambda c: scores[c])
    print(best, " ".join(f"{c}={scores[c]:.3f}" for c in labels))

Lesson: Naive Bayes text classification →