Lab 2_hmm_pos_tagger

ipynb48 kBPython · 19 cellsIn TP 2: HMM POS tagger

🏷️ Assignment: Building a POS Tagger from Scratch using Hidden Markov Models


Objectives

In this assignment you will:

  1. Learn an HMM from a labeled corpus (compute π, A, B matrices)
  2. Decode new sentences using the Viterbi algorithm
  3. Evaluate your tagger against NLTK's built-in HMM tagger

Background

A first-order HMM for POS tagging is defined by three components:

Component Symbol Definition
Prior probabilities π(t) Probability that tag t starts a sentence
Transition matrix A[t₁ → t₂] Probability of tag t₂ following tag t₁
Emission matrix B[t → w] Probability of word w being emitted by tag t

All probabilities are estimated by Maximum Likelihood Estimation (MLE):

π(t)=count(t starts sentence)total sentences\pi(t) = \frac{\text{count}(t \text{ starts sentence})}{\text{total sentences}}

A[ti→tj]=count(ti,tj)count(ti as non-final tag)A[t_i \to t_j] = \frac{\text{count}(t_i, t_j)}{\text{count}(t_i \text{ as non-final tag})}

B[t→w]=count(w,t)count(t)B[t \to w] = \frac{\text{count}(w, t)}{\text{count}(t)}


Structure

Section Task Who implements?
1. Corpus Hardcoded labeled sentences ✅ Provided
2. Exploration Inspect the data ✅ Provided
3. HMM Learning Compute π, A, B 🔧 You implement
4. Viterbi Decoder Find best tag sequence 🔧 You implement
5. Evaluation Token-level accuracy ✅ Provided
6. NLTK Comparison Train NLTK HMM & compare ✅ Provided

Section 1 — Corpus

The corpus below contains the first 10 sentences of the Penn Treebank (Wall Street Journal section), with gold-standard POS tags. Each sentence is a list of (word, tag) tuples.

Note: Tags follow the Penn Treebank tagset. Common ones you'll see: NNP (proper noun), NN (noun), VBN (verb past participle), IN (preposition), DT (determiner), JJ (adjective), etc.

In [29]
# ============================================================
#  CORPUS — First 10 sentences of the Penn Treebank (WSJ)
#  Source: Marcus et al. (1993). Each entry: (word, POS_tag)
# ============================================================

CORPUS = [
    # Sentence 1
    [
        ("Pierre", "NNP"),
        ("Vinken", "NNP"),
        (",", ","),
        ("61", "CD"),
        ("years", "NNS"),
        ("old", "JJ"),
        (",", ","),
        ("will", "MD"),
        ("join", "VB"),
        ("the", "DT"),
        ("board", "NN"),
        ("as", "IN"),
        ("a", "DT"),
        ("nonexecutive", "JJ"),
        ("director", "NN"),
        ("Nov.", "NNP"),
        ("29", "CD"),
        (".", "."),
    ],
    # Sentence 2
    [
        ("Mr.", "NNP"),
        ("Vinken", "NNP"),
        ("is", "VBZ"),
        ("chairman", "NN"),
        ("of", "IN"),
        ("Elsevier", "NNP"),
        ("N.V.", "NNP"),
        (",", ","),
        ("the", "DT"),
        ("Dutch", "NNP"),
        ("publishing", "VBG"),
        ("group", "NN"),
        (".", "."),
    ],
    # Sentence 3
    [
        ("Rudolph", "NNP"),
        ("Agnew", "NNP"),
        (",", ","),
        ("55", "CD"),
        ("years", "NNS"),
        ("old", "JJ"),
        ("and", "CC"),
        ("former", "JJ"),
        ("chairman", "NN"),
        ("of", "IN"),
        ("Consolidated", "NNP"),
        ("Gold", "NNP"),
        ("Fields", "NNP"),
        ("PLC", "NNP"),
        (",", ","),
        ("was", "VBD"),
        ("named", "VBN"),
        ("*-1", "*-1"),
        ("a", "DT"),
        ("nonexecutive", "JJ"),
        ("director", "NN"),
        ("of", "IN"),
        ("*", "*"),
        ("a", "DT"),
        ("British", "JJ"),
        ("...", ":"),
        ("company", "NN"),
        (".", "."),
    ],
    # Sentence 4
    [
        ("A", "DT"),
        ("form", "NN"),
        ("of", "IN"),
        ("asbestos", "NN"),
        ("once", "RB"),
        ("used", "VBN"),
        ("*", "*"),
        ("to", "TO"),
        ("make", "VB"),
        ("Kent", "NNP"),
        ("cigarettes", "NNS"),
        ("has", "VBZ"),
        ("resurf", "VBN"),
        ("*", "*"),
        ("in", "IN"),
        ("a", "DT"),
        ("class-action", "JJ"),
        ("suit", "NN"),
        ("brought", "VBN"),
        ("*", "*"),
        ("against", "IN"),
        ("the", "DT"),
        ("Manville", "NNP"),
        ("Corp.", "NNP"),
        (".", "."),
    ],
    # Sentence 5
    [
        ("Lorillard", "NNP"),
        ("Inc.", "NNP"),
        (",", ","),
        ("the", "DT"),
        ("manufacturer", "NN"),
        ("of", "IN"),
        ("Kent", "NNP"),
        ("cigarettes", "NNS"),
        (",", ","),
        ("must", "MD"),
        ("pay", "VB"),
        ("$", "$"),
        ("6", "CD"),
        ("million", "CD"),
        ("to", "TO"),
        ("settle", "VB"),
        ("a", "DT"),
        ("class", "NN"),
        ("-", "HYPH"),
        ("action", "NN"),
        ("suit", "NN"),
        ("brought", "VBN"),
        ("*", "*"),
        ("against", "IN"),
        ("it", "PRP"),
        ("by", "IN"),
        ("*-2", "*-2"),
        ("smokers", "NNS"),
        ("who", "WP"),
        ("use", "VBP"),
        ("Kent", "NNP"),
        ("cigarettes", "NNS"),
        (".", "."),
    ],
    # Sentence 6
    [
        ("Attorneys", "NNS"),
        ("have", "VBP"),
        ("also", "RB"),
        ("been", "VBN"),
        ("told", "VBN"),
        ("*-1", "*-1"),
        ("to", "TO"),
        ("consider", "VB"),
        ("*", "*"),
        ("consolidating", "VBG"),
        ("the", "DT"),
        ("suits", "NNS"),
        ("filed", "VBN"),
        ("*", "*"),
        ("in", "IN"),
        ("other", "JJ"),
        ("courts", "NNS"),
        (".", "."),
    ],
    # Sentence 7
    [
        ("That", "DT"),
        ("request", "NN"),
        (",", ","),
        ("sent", "VBD"),
        ("*", "*"),
        ("to", "TO"),
        ("about", "IN"),
        ("200", "CD"),
        ("law", "NN"),
        ("firms", "NNS"),
        (",", ","),
        ("also", "RB"),
        ("was", "VBD"),
        ("adv", "RB"),
        ("*-1", "*-1"),
        ("to", "TO"),
        ("raise", "VB"),
        ("*", "*"),
        ("the", "DT"),
        ("issue", "NN"),
        ("of", "IN"),
        ("consolidation", "NN"),
        ("in", "IN"),
        ("Houston", "NNP"),
        (",", ","),
        ("where", "WRB"),
        ("the", "DT"),
        ("Manville", "NNP"),
        ("asbestos", "NN"),
        ("cases", "NNS"),
        ("are", "VBP"),
        ("en", "RB"),
        ("route", "NN"),
        (".", "."),
    ],
    # Sentence 8
    [
        ("Texas-based", "JJ"),
        ("Lorillard", "NNP"),
        ("has", "VBZ"),
        ("been", "VBN"),
        ("under", "IN"),
        ("fire", "NN"),
        ("for", "IN"),
        ("its", "PRP$"),
        ("failure", "NN"),
        ("to", "TO"),
        ("warn", "VB"),
        ("smokers", "NNS"),
        ("of", "IN"),
        ("cancer", "NN"),
        ("risks", "NNS"),
        ("from", "IN"),
        ("asbestos", "NN"),
        ("in", "IN"),
        ("the", "DT"),
        ("fibers", "NN"),
        ("used", "VBN"),
        ("*", "*"),
        ("in", "IN"),
        ("Kent", "NNP"),
        ("cigarettes", "NNS"),
        (",", ","),
        ("which", "WDT"),
        ("were", "VBD"),
        ("made", "VBN"),
        ("*-1", "*-1"),
        ("from", "IN"),
        ("1952", "CD"),
        ("to", "TO"),
        ("1956", "CD"),
        (".", "."),
    ],
    # Sentence 9
    [
        ("It", "PRP"),
        ("isn't", "VBZ"),
        ("clear", "JJ"),
        ("*", "*"),
        ("whether", "IN"),
        ("*-2", "*-2"),
        ("asbestos", "NN"),
        ("is", "VBZ"),
        ("now", "RB"),
        ("used", "VBN"),
        ("*-1", "*-1"),
        ("in", "IN"),
        ("Kent", "NNP"),
        ("cigarettes", "NNS"),
        (".", "."),
    ],
    # Sentence 10
    [
        ("A", "DT"),
        ("form", "NN"),
        ("of", "IN"),
        ("asbestos", "NN"),
        ("once", "RB"),
        ("used", "VBN"),
        ("*", "*"),
        ("to", "TO"),
        ("make", "VB"),
        ("Kent", "NNP"),
        ("cigarettes", "NNS"),
        ("has", "VBZ"),
        ("led", "VBN"),
        ("*", "*"),
        ("to", "TO"),
        ("a", "DT"),
        ("class", "NN"),
        ("-", "HYPH"),
        ("action", "NN"),
        ("suit", "NN"),
        ("brought", "VBN"),
        ("*", "*"),
        ("against", "IN"),
        ("the", "DT"),
        ("Manville", "NNP"),
        ("Corp.", "NNP"),
        (".", "."),
    ],
]

print(f"Corpus loaded: {len(CORPUS)} sentences, {sum(len(s) for s in CORPUS)} tokens")
Corpus loaded: 10 sentences, 246 tokens

Section 2 — Corpus Exploration

Before building the model, let's understand the data.

In [30]
from collections import defaultdict, Counter

# --- Extract vocabulary and tag set ---
all_tags = sorted(set(tag for sent in CORPUS for word, tag in sent))
all_words = sorted(set(word for sent in CORPUS for word, _ in sent))

print(f"Vocabulary size : {len(all_words)} unique words")
print(f"Tag set size    : {len(all_tags)} unique tags")
print(f"\nTags: {all_tags}")

# --- Tag frequency ---
tag_freq = Counter(tag for sent in CORPUS for _, tag in sent)
print("\nTop 10 most frequent tags:")
for tag, count in tag_freq.most_common(10):
    print(f"  {tag:8s}: {count}")

# --- Preview first sentence ---
print("\nFirst sentence:")
print("  Words :", [w for w, _ in CORPUS[0]])
print("  Tags  :", [t for _, t in CORPUS[0]])
Vocabulary size : 128 unique words
Tag set size    : 30 unique tags

Tags: ['$', '*', '*-1', '*-2', ',', '.', ':', 'CC', 'CD', 'DT', 'HYPH', 'IN', 'JJ', 'MD', 'NN', 'NNP', 'NNS', 'PRP', 'PRP$', 'RB', 'TO', 'VB', 'VBD', 'VBG', 'VBN', 'VBP', 'VBZ', 'WDT', 'WP', 'WRB']

Top 10 most frequent tags:
  NN      : 31
  NNP     : 29
  IN      : 25
  DT      : 18
  NNS     : 16
  VBN     : 15
  *       : 14
  ,       : 11
  JJ      : 10
  .       : 10

First sentence:
  Words : ['Pierre', 'Vinken', ',', '61', 'years', 'old', ',', 'will', 'join', 'the', 'board', 'as', 'a', 'nonexecutive', 'director', 'Nov.', '29', '.']
  Tags  : ['NNP', 'NNP', ',', 'CD', 'NNS', 'JJ', ',', 'MD', 'VB', 'DT', 'NN', 'IN', 'DT', 'JJ', 'NN', 'NNP', 'CD', '.']

Section 3 — 🔧 HMM Learning (Your implementation)

Implement the three functions below to compute the HMM parameters from the corpus.

Smoothing

To avoid zero probabilities for unseen events (words or transitions not in the training data), apply Laplace (add-1) smoothing:

Asmooth[ti→tj]=count(ti,tj)+1count(ti)+∣Tags∣A_{smooth}[t_i \to t_j] = \frac{\text{count}(t_i, t_j) + 1}{\text{count}(t_i) + |\text{Tags}|}

Bsmooth[t→w]=count(w,t)+1count(t)+∣Vocab∣B_{smooth}[t \to w] = \frac{\text{count}(w, t) + 1}{\text{count}(t) + |\text{Vocab}|}

Why smoothing matters: In Viterbi, multiplying by a zero probability kills any path through that state. Smoothing keeps all paths alive with a small non-zero probability.

In [31]
import math
from collections import defaultdict


def compute_prior(corpus, tags):
    """
    Compute initial state probabilities pi.

    pi[t] = count(sentences starting with tag t) / total sentences

    Parameters
    ----------
    corpus : list of list of (word, tag) tuples
    tags   : sorted list of all unique tags

    Returns
    -------
    pi : dict  {tag -> probability}

    Hint
    ----
    - The starting tag of sentence s is: s[0][1]  (index 0 = first token, index 1 = tag)
    - No smoothing needed here; unseen start tags simply get probability 0.
    """
    pi = {t: 0.0 for t in tags}

    # ── YOUR CODE HERE ──────────────────────────────────────────
    counter = {t: 0 for t in tags}
    total_sentences = len(corpus)
    for sentence in corpus:
        found_tag = sentence[0][1]
        counter[found_tag] += 1

    for t in tags:
        pi[t] = counter[t] / total_sentences

    return pi


def compute_transition(corpus, tags):
    """
    Compute the transition matrix A with Laplace smoothing.

    A[t1][t2] = (count(t1 -> t2) + 1) / (count(t1 as non-final) + |tags|)

    Parameters
    ----------
    corpus : list of list of (word, tag) tuples
    tags   : sorted list of all unique tags

    Returns
    -------
    A : dict of dict  {tag -> {tag -> probability}}
        A[t1][t2] is the probability of t2 following t1.

    Hints
    -----
    - Iterate over consecutive pairs (sent[i], sent[i+1]) in each sentence.
    - A tag at position len(sent)-1 (last position) is NOT a valid source,
      so don't count it in the denominator.
    - After counting, divide each count by (row_total + len(tags)) for smoothing.
    """
    # Raw bigram counts
    trans_count = defaultdict(lambda: defaultdict(int))
    src_count = defaultdict(
        int
    )  # how many times each tag appears as a non-final source

    # ── YOUR CODE HERE ──────────────────────────────────────────

    for sentence in CORPUS:
        for i in range(len(sentence) - 1):
            t1 = sentence[i][1]
            t2 = sentence[i + 1][1]

            trans_count[t1][t2] += 1
            src_count[t1] += 1

    # ────────────────────────────────────────────────────────────

    # Convert counts to smoothed probabilities
    A = {}
    for t1 in tags:
        A[t1] = {}
        denom = src_count[t1] + len(tags)  # Laplace denominator
        for t2 in tags:
            A[t1][t2] = (trans_count[t1][t2] + 1) / denom
    return A


def compute_emission(corpus, tags, vocab):
    """
    Compute the emission matrix B with Laplace smoothing.

    B[t][w] = (count(w tagged as t) + 1) / (count(t) + |vocab|)

    Parameters
    ----------
    corpus : list of list of (word, tag) tuples
    tags   : sorted list of all unique tags
    vocab  : sorted list of all unique words

    Returns
    -------
    B : dict of dict  {tag -> {word -> probability}}
        B[t][w] is the probability of word w being emitted by tag t.

    Hints
    -----
    - Count every (word, tag) pair in the corpus.
    - Also count total occurrences of each tag (tag_count[t]).
    - The smoothed probability for an UNSEEN word w' under tag t is: 1 / (tag_count[t] + |vocab|)
    """
    emit_count = defaultdict(lambda: defaultdict(int))
    tag_count = defaultdict(int)

    # ── YOUR CODE HERE ──────────────────────────────────────────
    for sentence in CORPUS:
        for word, tag in sentence:
            emit_count[tag][word] += 1
            tag_count[tag] += 1

    # ────────────────────────────────────────────────────────────

    # Convert counts to smoothed probabilities
    B = {}
    for t in tags:
        B[t] = {}
        denom = tag_count[t] + len(vocab)  # Laplace denominator
        for w in vocab:
            B[t][w] = (emit_count[t][w] + 1) / denom
    return B
In [32]
# ── Train the HMM ──────────────────────────────────────────────────────────
pi = compute_prior(CORPUS, all_tags)
A = compute_transition(CORPUS, all_tags)
B = compute_emission(CORPUS, all_tags, all_words)

# ── Sanity checks ──────────────────────────────────────────────────────────
print("=== Sanity Checks ===")

# 1. pi sums to 1
print(f"Sum of pi            : {sum(pi.values()):.4f}  (expected: 1.0)")

# 2. Each row of A sums to 1
row_sums = {t: sum(A[t].values()) for t in all_tags}
all_ok = all(abs(s - 1.0) < 1e-9 for s in row_sums.values())
print(
    f"A rows sum to 1      : {all_ok}   (sample NNP row: {sum(A['NNP'].values()):.4f})"
)

# 3. Each row of B sums to 1
b_row_sums = {t: sum(B[t].values()) for t in all_tags}
all_ok_b = all(abs(s - 1.0) < 1e-9 for s in b_row_sums.values())
print(
    f"B rows sum to 1      : {all_ok_b}   (sample NN row: {sum(B['NN'].values()):.4f})"
)

# 4. Spot-check specific values
print("\n=== Spot-check Expected Values ===")
print(f"pi['NNP']            : {pi['NNP']:.4f}  (expected: 0.4000)")
print(f"pi['DT']             : {pi['DT']:.4f}  (expected: 0.3000)")
print(f"pi['VBZ']            : {pi['VBZ']:.4f}  (expected: 0.0000)")
print(f"A['DT']['NN'] (raw)  : ~0.50  (unsmoothed count: 9/18)")
print(f"A['DT']['NN'] (smooth): {A['DT']['NN']:.4f}")
print(f"A['NNP']['NNP'](smth): {A['NNP']['NNP']:.4f}")
=== Sanity Checks ===
Sum of pi            : 1.0000  (expected: 1.0)
A rows sum to 1      : True   (sample NNP row: 1.0000)
B rows sum to 1      : True   (sample NN row: 1.0000)

=== Spot-check Expected Values ===
pi['NNP']            : 0.4000  (expected: 0.4000)
pi['DT']             : 0.3000  (expected: 0.3000)
pi['VBZ']            : 0.0000  (expected: 0.0000)
A['DT']['NN'] (raw)  : ~0.50  (unsmoothed count: 9/18)
A['DT']['NN'] (smooth): 0.2083
A['NNP']['NNP'](smth): 0.1864

Section 4 — 🔧 Viterbi Decoder (Your implementation)

The Viterbi algorithm finds the most probable tag sequence for an observed word sequence.

It fills a trellis of size |states| × |observations|:

δ(s,1)=π(s)×B[s→o1]\delta(s, 1) = \pi(s) \times B[s \to o_1]

δ(s,t)=max⁡s′[δ(s′,t−1)×A[s′→s]]×B[s→ot]\delta(s, t) = \max_{s'} \left[ \delta(s', t-1) \times A[s' \to s] \right] \times B[s \to o_t]

ψ(s,t)=argmax⁡s′[δ(s′,t−1)×A[s′→s]]\psi(s, t) = \operatorname{argmax}_{s'} \left[ \delta(s', t-1) \times A[s' \to s] \right]

The best tag sequence is recovered by backtracking from the final state with the highest δ.

⚠️ Numerical Underflow

Multiplying many small probabilities causes floating-point underflow (values become 0). Use log probabilities instead:

log⁡δ(s,t)=max⁡s′[log⁡δ(s′,t−1)+log⁡A[s′→s]]+log⁡B[s→ot]\log \delta(s, t) = \max_{s'} \left[ \log \delta(s', t-1) + \log A[s' \to s] \right] + \log B[s \to o_t]

Replace every multiplication with addition and every max-product with max-sum.

In [33]
import math

LOG_ZERO = float("-inf")  # represents log(0)


def safe_log(x):
    """Return log(x), or LOG_ZERO if x <= 0."""
    return math.log(x) if x > 0 else LOG_ZERO


def viterbi(words, tags, pi, A, B):
    """
    Viterbi algorithm — returns the most likely POS tag sequence.

    Parameters
    ----------
    words : list of str   — the observed word sequence
    tags  : list of str   — all possible POS tags
    pi    : dict          — prior probabilities  {tag -> prob}
    A     : dict of dict  — transition matrix    {tag -> {tag -> prob}}
    B     : dict of dict  — emission matrix      {tag -> {word -> prob}}

    Returns
    -------
    best_path : list of str  — predicted tag for each word

    Hints
    -----
    - Use two tables of size len(tags) x len(words):
        delta[t][i]  : best log-probability of reaching tag t at position i
        psi[t][i]    : index of the best previous tag that led to (t, i)

    - Initialization (i = 0):
        delta[t][0] = safe_log(pi[t]) + safe_log(B[t].get(words[0], 0))
        psi[t][0]   = None

    - Recursion (i > 0), for each tag t:
        For each previous tag t_prev, compute:
            score = delta[t_prev][i-1] + safe_log(A[t_prev][t])
        Take the maximum score and multiply by the emission:
            delta[t][i] = max_score + safe_log(B[t].get(words[i], 0))
            psi[t][i]   = index of t_prev with highest score

    - Termination:
        best_last_tag = tag with highest delta[t][-1]

    - Backtracking:
        Start from best_last_tag and follow psi pointers backwards.
        Reverse the collected path before returning.

    - OOV (out-of-vocabulary) words:
        If words[i] is not in B[t], use the smoothed unseen probability.
        With Laplace smoothing this is already handled if you use:
            B[t].get(words[i], 1 / (tag_count[t] + len(vocab)))
        For simplicity here, a small constant like 1e-6 also works.
    """
    n = len(words)
    T = len(tags)
    tag_index = {t: i for i, t in enumerate(tags)}  # tag -> integer index

    # Trellis tables (T x n)
    delta = [[LOG_ZERO] * n for _ in range(T)]
    psi = [[None] * n for _ in range(T)]

    # ── Initialization ───────────────────────────────────────────
    # ── YOUR CODE HERE ──────────────────────────────────────────
    for t in tags:
        ti = tag_index[t]
        delta[ti][0] = safe_log(pi[t]) + safe_log(B[t].get(words[0], 0))
        psi[ti][0] = None

    # ── Recursion ─────────────────────────────────────────────────
    # ── YOUR CODE HERE ──────────────────────────────────────────
    for i in range(1, n):
        for t in tags:
            ti = tag_index[t]
            best_score = LOG_ZERO
            best_prev_idx = None
            for t_prev in tags:
                tpi = tag_index[t_prev]
                score = delta[tpi][i - 1] + safe_log(A[t_prev].get(t, 0))
                if score > best_score:
                    best_score = score
                    best_prev_idx = tpi
            delta[ti][i] = best_score + safe_log(B[t].get(words[i], 0))
            psi[ti][i] = best_prev_idx

    # ── Termination ───────────────────────────────────────────────
    # ── YOUR CODE HERE ──────────────────────────────────────────
    best_last_idx = max(range(T), key=lambda ti: delta[ti][n - 1])

    # ── Backtracking ──────────────────────────────────────────────
    # ── YOUR CODE HERE ──────────────────────────────────────────
    path = [best_last_idx]
    for i in range(n - 1, 0, -1):
        path.append(psi[path[-1]][i])
    path.reverse()
    best_path = [tags[ti] for ti in path]

    return best_path  # list of tags, same length as words
In [34]
# ── Quick test on Sentence 9 ────────────────────────────────────────────────
test_sent = CORPUS[8]  # 0-indexed: sentence 9
test_words = [w for w, _ in test_sent]
gold_tags = [t for _, t in test_sent]

pred_tags = viterbi(test_words, all_tags, pi, A, B)

print("Sentence 9 decoding:")
print(f"{'Word':<15} {'Gold':>8} {'Predicted':>12} {'Match':>8}")
print("-" * 48)
for w, g, p in zip(test_words, gold_tags, pred_tags):
    match = "✓" if g == p else "✗"
    print(f"{w:<15} {g:>8} {p:>12} {match:>8}")

correct = sum(g == p for g, p in zip(gold_tags, pred_tags))
print(
    f"\nToken accuracy on sentence 9: {correct}/{len(gold_tags)} = {correct/len(gold_tags):.2%}"
)
Sentence 9 decoding:
Word                Gold    Predicted    Match
------------------------------------------------
It                   PRP           DT        ✗
isn't                VBZ           NN        ✗
clear                 JJ          VBN        ✗
*                      *            *        ✓
whether               IN           IN        ✓
*-2                  *-2           DT        ✗
asbestos              NN           NN        ✓
is                   VBZ           IN        ✗
now                   RB           NN        ✗
used                 VBN          VBN        ✓
*-1                  *-1          *-1        ✓
in                    IN           IN        ✓
Kent                 NNP          NNP        ✓
cigarettes           NNS          NNS        ✓
.                      .            .        ✓

Token accuracy on sentence 9: 9/15 = 60.00%

Section 5 — Evaluation

Evaluate your tagger on all 10 training sentences. Since we're training and testing on the same data here (no separate test set due to the small corpus size), this measures training accuracy — how well the HMM memorized the data.

In [35]
def evaluate(corpus, tags, pi, A, B, label="My HMM Tagger"):
    """
    Run Viterbi on every sentence and compute token-level accuracy.
    Returns a dict with per-sentence and overall accuracy.
    """
    total_correct = 0
    total_tokens = 0
    results = []

    for i, sent in enumerate(corpus):
        words = [w for w, _ in sent]
        gold = [t for _, t in sent]
        predicted = viterbi(words, tags, pi, A, B)
        correct = sum(g == p for g, p in zip(gold, predicted))
        results.append(
            {
                "sentence": i + 1,
                "correct": correct,
                "total": len(gold),
                "accuracy": correct / len(gold),
            }
        )
        total_correct += correct
        total_tokens += len(gold)

    overall = total_correct / total_tokens

    print(f"\n{'='*50}")
    print(f"  {label}")
    print(f"{'='*50}")
    print(f"{'Sent':>6} {'Correct':>9} {'Total':>7} {'Accuracy':>10}")
    print("-" * 38)
    for r in results:
        print(
            f"{r['sentence']:>6} {r['correct']:>9} {r['total']:>7} {r['accuracy']:>10.2%}"
        )
    print("-" * 38)
    print(f"{'TOTAL':>6} {total_correct:>9} {total_tokens:>7} {overall:>10.2%}")

    return {
        "per_sentence": results,
        "overall": overall,
        "total_correct": total_correct,
        "total_tokens": total_tokens,
    }


my_results = evaluate(CORPUS, all_tags, pi, A, B, label="My HMM Tagger")
==================================================
  My HMM Tagger
==================================================
  Sent   Correct   Total   Accuracy
--------------------------------------
     1        17      18     94.44%
     2        11      13     84.62%
     3        24      28     85.71%
     4        25      25    100.00%
     5        26      33     78.79%
     6        13      18     72.22%
     7        25      34     73.53%
     8        30      35     85.71%
     9         9      15     60.00%
    10        25      27     92.59%
--------------------------------------
 TOTAL       205     246     83.33%

Section 6 — NLTK HMM Tagger (Comparison)

We now train NLTK's built-in HMM tagger on the same 10 sentences and compare its performance to yours.

In [36]
import nltk
from nltk.tag import hmm as nltk_hmm

# NLTK expects a list of sentences, each sentence being a list of (word, tag) tuples
trainer = nltk_hmm.HiddenMarkovModelTrainer()
nltk_tagger = trainer.train_supervised(CORPUS)

print("NLTK HMM tagger trained successfully.")
NLTK HMM tagger trained successfully.
In [37]
def evaluate_nltk(corpus, nltk_tagger, label="NLTK HMM Tagger"):
    total_correct = 0
    total_tokens = 0
    results = []

    for i, sent in enumerate(corpus):
        words = [w for w, _ in sent]
        gold = [t for _, t in sent]
        predicted = [tag for _, tag in nltk_tagger.tag(words)]
        correct = sum(g == p for g, p in zip(gold, predicted))
        results.append(
            {
                "sentence": i + 1,
                "correct": correct,
                "total": len(gold),
                "accuracy": correct / len(gold),
            }
        )
        total_correct += correct
        total_tokens += len(gold)

    overall = total_correct / total_tokens

    print(f"\n{'='*50}")
    print(f"  {label}")
    print(f"{'='*50}")
    print(f"{'Sent':>6} {'Correct':>9} {'Total':>7} {'Accuracy':>10}")
    print("-" * 38)
    for r in results:
        print(
            f"{r['sentence']:>6} {r['correct']:>9} {r['total']:>7} {r['accuracy']:>10.2%}"
        )
    print("-" * 38)
    print(f"{'TOTAL':>6} {total_correct:>9} {total_tokens:>7} {overall:>10.2%}")

    return {
        "per_sentence": results,
        "overall": overall,
        "total_correct": total_correct,
        "total_tokens": total_tokens,
    }


nltk_results = evaluate_nltk(CORPUS, nltk_tagger, label="NLTK HMM Tagger")
==================================================
  NLTK HMM Tagger
==================================================
  Sent   Correct   Total   Accuracy
--------------------------------------
     1        18      18    100.00%
     2        13      13    100.00%
     3        28      28    100.00%
     4        25      25    100.00%
     5        33      33    100.00%
     6        18      18    100.00%
     7        34      34    100.00%
     8        35      35    100.00%
     9        15      15    100.00%
    10        27      27    100.00%
--------------------------------------
 TOTAL       246     246    100.00%
In [38]
# ── Side-by-side comparison ────────────────────────────────────────────────
print("\n" + "=" * 55)
print("  FINAL COMPARISON")
print("=" * 55)
print(f"  {'Tagger':<25} {'Correct':>9} {'Total':>7} {'Accuracy':>10}")
print("-" * 55)
print(
    f"  {'My HMM Tagger':<25} "
    f"{my_results['total_correct']:>9} "
    f"{my_results['total_tokens']:>7} "
    f"{my_results['overall']:>10.2%}"
)
print(
    f"  {'NLTK HMM Tagger':<25} "
    f"{nltk_results['total_correct']:>9} "
    f"{nltk_results['total_tokens']:>7} "
    f"{nltk_results['overall']:>10.2%}"
)
print("=" * 55)

diff = my_results["overall"] - nltk_results["overall"]
if abs(diff) < 0.01:
    print("\n✅ Your tagger matches NLTK's accuracy closely!")
elif diff > 0:
    print(f"\n🎉 Your tagger outperforms NLTK by {diff:.2%}!")
else:
    print(f"\n📊 NLTK outperforms your tagger by {abs(diff):.2%}.")
    print("   Check your smoothing and probability normalization.")
=======================================================
  FINAL COMPARISON
=======================================================
  Tagger                      Correct   Total   Accuracy
-------------------------------------------------------
  My HMM Tagger                   205     246     83.33%
  NLTK HMM Tagger                 246     246    100.00%
=======================================================

📊 NLTK outperforms your tagger by 16.67%.
   Check your smoothing and probability normalization.

Section 7 — Error Analysis

Let's look at where your tagger makes mistakes and compare with NLTK's decisions.

In [39]
print(
    f"{'Word':<18} {'Gold':>8} {'My Pred':>10} {'NLTK Pred':>12} {'My OK':>7} {'NLTK OK':>9}"
)
print("-" * 70)

for sent in CORPUS:
    words = [w for w, _ in sent]
    gold = [t for _, t in sent]
    my_pred = viterbi(words, all_tags, pi, A, B)
    nltk_pred = [tag for _, tag in nltk_tagger.tag(words)]

    for w, g, m, n in zip(words, gold, my_pred, nltk_pred):
        my_ok = "✓" if g == m else "✗"
        nltk_ok = "✓" if g == n else "✗"
        # Only print mismatches (where at least one tagger is wrong)
        if g != m or g != n:
            print(f"{w:<18} {g:>8} {m:>10} {n:>12} {my_ok:>7} {nltk_ok:>9}")
Word                   Gold    My Pred    NLTK Pred   My OK   NLTK OK
----------------------------------------------------------------------
Nov.                    NNP         IN          NNP       ✗         ✓
Dutch                   NNP         NN          NNP       ✗         ✓
publishing              VBG         IN          VBG       ✗         ✓
and                      CC         NN           CC       ✗         ✓
former                   JJ         IN           JJ       ✗         ✓
British                  JJ         NN           JJ       ✗         ✓
...                       :         IN            :       ✗         ✓
-                      HYPH         IN         HYPH       ✗         ✓
action                   NN         DT           NN       ✗         ✓
it                      PRP         NN          PRP       ✗         ✓
*-2                     *-2        NNP          *-2       ✗         ✓
smokers                 NNS        NNP          NNS       ✗         ✓
who                      WP        NNP           WP       ✗         ✓
use                     VBP        NNP          VBP       ✗         ✓
Attorneys               NNS         DT          NNS       ✗         ✓
have                    VBP         NN          VBP       ✗         ✓
consolidating           VBG         IN          VBG       ✗         ✓
suits                   NNS         NN          NNS       ✗         ✓
other                    JJ        NNP           JJ       ✗         ✓
That                     DT        NNP           DT       ✗         ✓
request                  NN        NNP           NN       ✗         ✓
about                    IN         VB           IN       ✗         ✓
200                      CD         DT           CD       ✗         ✓
adv                      RB        VBN           RB       ✗         ✓
Manville                NNP         JJ          NNP       ✗         ✓
cases                   NNS         IN          NNS       ✗         ✓
are                     VBP         NN          VBP       ✗         ✓
en                       RB         IN           RB       ✗         ✓
Texas-based              JJ        NNP           JJ       ✗         ✓
its                    PRP$         DT         PRP$       ✗         ✓
smokers                 NNS          *          NNS       ✗         ✓
cancer                   NN         DT           NN       ✗         ✓
risks                   NNS         NN          NNS       ✗         ✓
It                      PRP         DT          PRP       ✗         ✓
isn't                   VBZ         NN          VBZ       ✗         ✓
clear                    JJ        VBN           JJ       ✗         ✓
*-2                     *-2         DT          *-2       ✗         ✓
is                      VBZ         IN          VBZ       ✗         ✓
now                      RB         NN           RB       ✗         ✓
-                      HYPH         IN         HYPH       ✗         ✓
action                   NN         DT           NN       ✗         ✓