Wiki
Core13 min read

Tagging, parsing and Naive Bayes

Sequence labelling with hidden Markov models, the Naive Bayes classifier, and the precision/recall confusion matrix used to evaluate both.

Knowing the words of a sentence is only the beginning. Grammar lives in the labels attached to them — noun, verb, adjective — and in the tree of phrases those labels form. A parser that knows book is a verb in "they book a room" and a noun in "read the book" unlocks search, translation, question answering and a hundred downstream tasks.

This is sequence labelling: the label of one word depends on the word, but also on the labels around it. The classical tool is the hidden Markov model, and the classifier at its heart — Naive Bayes — is one of the most reusable ideas in machine learning.

Classification with a confusion matrix

Every tagger is a classifier being graded. Gold tag on one axis, predicted tag on the other, and the counts tell you exactly how it fails: which distinctions it confuses, and whether it is over- or under-predicting a tag. Precision, recall and F1 are just summaries of which axis you care about.

The widget runs two toy taggers over a labelled test set and rebuilds the confusion matrix, precision, recall and macro-F1 for each.

Gold tag down the rows, predicted tag across the columns. Switch taggers and watch the off-diagonal cells, and macro-F1, move.

macro-F1 = 0.564
gold ↓ / pred →NOUNVERBADJADVADPDET
NOUN700000
VERB400000
ADJ500000
ADV100200
ADP000040
DET000001

Hover a cell to see which test words fell into it.

NOUN

P 0.41 · R 1.00 · F1 0.58

VERB

P 0.00 · R 0.00 · F1 0.00

ADJ

P 0.00 · R 0.00 · F1 0.00

ADV

P 1.00 · R 0.67 · F1 0.80

ADP

P 1.00 · R 1.00 · F1 1.00

DET

P 1.00 · R 1.00 · F1 1.00

Real evaluation arithmetic on a hand-labelled toy test set. The “memorised” tagger is the degenerate case of a Naive Bayes tagger with no smoothing; the rule tagger is the kind of baseline a learned HMM or CRF must beat.

Naive Bayes, the generative classifier

For a document or a word with observed features x1,…,xnx_1, \dots, x_n and a class cc, Bayes' rule gives

P(c∣x1,…,xn)∝P(c)∏i=1nP(xi∣c).P(c \mid x_1, \dots, x_n) \propto P(c) \prod_{i=1}^{n} P(x_i \mid c).

The "naive" step assumes the features are conditionally independent given the class. That assumption is usually false, yet the resulting classifier is fast, needs little data, and remains remarkably competitive on text. In a unigram tagger the feature is just the word identity and P(c∣w)∝P(c) P(w∣c)P(c \mid w) \propto P(c)\, P(w \mid c); with no smoothing it simply memorises the most frequent tag per word, which is exactly the first tagger in the widget.

Hidden Markov models and Viterbi

A tagger should use context, not just the word. An HMM models the label sequence as a Markov chain and emits words from labels:

P(c1:m,w1:m)=∏i=1mP(ci∣ci−1) P(wi∣ci),P(c_{1:m}, w_{1:m}) = \prod_{i=1}^{m} P(c_i \mid c_{i-1})\, P(w_i \mid c_i),

with transition probabilities P(ci∣ci−1)P(c_i \mid c_{i-1}) and emission probabilities P(wi∣ci)P(w_i \mid c_i). Decoding the best label sequence is dynamic programming: the Viterbi algorithm fills a trellis of best scores ending in each tag and back-pointers a path. It is O(m ∣T∣2)O(m\,|T|^2) — linear in sentence length.

Parsing in one paragraph

Tagging produces a flat label per word. Parsing produces structure: a context-free grammar rewrites non-terminals into sequences of symbols and a chart parser (CKY) fills a table of spans to recover the tree. Constituency trees group words into phrases; dependency trees link heads to dependents. Both are sequence-structure problems with the same dynamic-programming flavour as Viterbi, now over spans rather than positions.

Evaluation you must quote

For a tag tt: precision=TP/(TP+FP)\text{precision} = TP/(TP+FP), recall=TP/(TP+FN)\text{recall} = TP/(TP+FN), F1=2PR/(P+R)F_1 = 2PR/(P+R). Averaging F1F_1 over tags gives macro-F1, which weights rare tags equally; micro-averaging weights them by frequency. Quoting the wrong average is one of the most common ways a result looks better than it is.

Accuracy hides class imbalance

If 90% of tokens are nouns, a tagger that always predicts NOUN scores 90% accuracy and is useless. The confusion matrix and macro-F1 expose that immediately; always report per-class numbers, never a single accuracy figure, on imbalanced label sets.

Illustrative vs real

Both taggers in the widget are tiny: a memorised unigram model and a suffix/closed-class rule baseline over about twenty tags' worth of toy data. Real taggers use trigram HMMs with suffix-based unknown-word models, or neural BiLSTM/Transformer taggers with CRF decoding, evaluated on the Penn Treebank. The confusion matrix, precision/recall/F1 arithmetic and the HMM factorisation are exactly those used in practice.

Check yourself

Eduspheria wiki · Applied AI, Classical NLP

0 / 5 answered

  1. 1A tagger predicts VERB 20 times, of which 16 are correct, and there are 4 gold VERB tokens it missed. What is recall for VERB?
    Numeric answer
  2. 2What makes Naive Bayes 'naive'?
    Multiple choice
  3. 3Which dynamic-programming algorithm decodes the most probable hidden state sequence in an HMM?
    Short answer
  4. 4With 90% of tokens labelled NOUN, a tagger predicting NOUN for every token achieves high accuracy but low macro-F1.
    True / false
  5. 5Precision = 0.6 and recall = 0.4. What is F1?
    Numeric answer

From the exam paper

Modeled on NITJ AI-502, End-Sem May 2025

0 / 5 answered

  1. 1A spam classifier has P(Spam) = 0.4, P(Ham) = 0.6, P(Buy | Spam) = 0.8 and P(Buy | Ham) = 0.2. What is the unnormalized score P(Spam)·P(Buy | Spam)?
    Numeric answer
  2. 2For the same classifier, what is the unnormalized score P(Ham)·P(Buy | Ham)?
    Numeric answer
  3. 3An email contains the word 'Buy'. What is the posterior P(Spam | Buy)? Give three decimal places.
    Numeric answer
  4. 4How should the email that contains the word 'Buy' be classified?
    Multiple choice
  5. 5Because the denominator P(Buy) is shared by both classes, it never changes which class has the larger posterior.
    True / false

Where next: video analytics — where the input is a stream of frames and motion itself becomes the signal.