NLP: Priors and word likelihoods

Compute the two ingredients of Naive Bayes from labelled examples.

What to build

A program that prints each class's prior and the smoothed likelihood of one word.

Requirements

  • Each training line is label: text. Lowercase the text and split it on whitespace.
  • prior = documents in the class ÷ all documents. likelihood = (times the word occurs in the class + 1) ÷ (word tokens in the class + V), where V is the number of distinct words in all training texts.
  • Print label prior P likelihood L for each class in alphabetical order, with four decimal places. The query word is lowercased too.

Input

Line 1: n. Then n training lines. Last line: the word.

Output

One line per class.

Constraints

n ≤ 500.

Example

Input:

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

Output:

ham prior 0.5000 likelihood 0.0455
spam prior 0.5000 likelihood 0.1429

Why it works

The prior is how common a class is before reading the text, and the smoothed likelihood is how typical the word is of the class, never exactly zero; these are the only numbers the classifier needs.

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
now
Expected output
ham prior 0.5000 likelihood 0.0455
spam prior 0.5000 likelihood 0.1429
Example 2 · Input
3
pos: good good fun
neg: bad
pos: fun
Good
Expected output
neg prior 0.3333 likelihood 0.2500
pos prior 0.6667 likelihood 0.4286

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

Hints

Hint 1

Split each training line once at the first colon: `label, text = line.split(":", 1)`.

Hint 2

V is the number of distinct words in all the training texts; likelihood = (count of the word in the class + 1) / (words in the class + V).

Solution

Show one correct solution (try it yourself first)
n = int(input())
docs, counts, totals, vocab = {}, {}, {}, []
for _ in range(n):
    label, text = input().split(":", 1)
    label = label.strip()
    words = text.lower().split()
    docs[label] = docs.get(label, 0) + 1
    counts.setdefault(label, {})
    totals[label] = totals.get(label, 0) + len(words)
    for w in words:
        counts[label][w] = counts[label].get(w, 0) + 1
        if w not in vocab:
            vocab.append(w)
word = input().strip().lower()
for label in sorted(docs):
    prior = docs[label] / n
    like = (counts[label].get(word, 0) + 1) / (totals[label] + len(vocab))
    print(f"{label} prior {prior:.4f} likelihood {like:.4f}")

Lesson: Naive Bayes text classification →