Parts-Of-Speech Tagging · Projects

A hidden Markov model treats a sentence as a sequence of hidden states — the part-of-speech tags — that emit the observed words. Tagging recovers the tag sequence most likely to have produced the sentence, and the Viterbi algorithm finds it exactly in time linear in the sentence length.

The model rests on two distributions, both estimated by counting over a tagged corpus: transition probabilities $P (t_{i} ∣ t_{i - 1})$ between adjacent tags, and emission probabilities $P (w_{i} ∣ t_{i})$ of a word given its tag. The HMM class keeps them as two nested maps, states (tag to word to probability) and transitions (tag to following tag to probability), trained by reading paired sentence and tag files — the Brown corpus in brown-train-sentences.txt and brown-train-tags.txt — with a # token marking each sentence start. Under the Markov assumption, the joint probability of a sentence $w_{1 : n}$ and a tag sequence $t_{1 : n}$ factors as

P (w_{1 : n}, t_{1 : n}) = i = 1 \prod n P (t_{i} ∣ t_{i - 1}) P (w_{i} ∣ t_{i}),

and tagging asks for the tag sequence that maximizes it. Enumerating all $∣ T ∣^{n}$ sequences is exponential, so the search is folded into a dynamic program.

The decoder works from a single recurrence. Let $v_{i} (t)$ be the probability of the best tag sequence ending in tag $t$ at position $i$ ; it depends only on the previous column,

v_{i} (t) = P (w_{i} ∣ t) s max v_{i - 1} (s) P (t ∣ s),

so one left-to-right sweep fills an $n \times ∣ T ∣$ table, and back-pointers recover the winning sequence. A greedy tagger that commits to the best tag at each word can be led astray by a locally attractive choice; Viterbi keeps every option open until the whole sentence is scored. Probabilities are accumulated in log space, turning the products into sums and avoiding underflow on long sentences.

Laid out as a grid of positions by tags, the recurrence fills one column from the one before it, and every cell records which predecessor it chose — the back-pointer that lets the winning sequence be traced once the last column is scored:

A Viterbi trellis over four words and three candidate tags. Each cell holds

v_{i} (t)

, the score of the best tag path ending in tag

t

at position

i

; thin edges are the transitions weighed at each step. The accent path is the winner the back-pointers recover, traced right to left from the highest-scoring f/inal cell.

Algorithm:

\textsc{Viterbi}(w_{1:n})

— decode the most likely tag sequence

1
input: a sentence $w_1 \ldots w_n$ , transitions $P(t \mid s)$ , emissions $P(w \mid t)$
2
for each tag $t$ do
3
$v_1(t) \gets P(t \mid \textsc{Start})\, P(w_1 \mid t)$
4
for $i \gets 2$ to $n$ do
5
for each tag $t$ do
6
$v_i(t) \gets P(w_i \mid t)\, \max_{s}\; v_{i-1}(s)\, P(t \mid s)$
7
$\mathrm{back}_i(t) \gets \operatorname{arg\,max}_{s}\; v_{i-1}(s)\, P(t \mid s)$
8
return the sequence traced back from $\operatorname{arg\,max}_{t} v_n(t)$

A word never seen in training has zero emission probability under every tag, which would zero out any path through it. To keep such a word from killing an otherwise good sequence, HMM.viterbi charges a fixed unseenPenalty of $- 100$ in log space for an unseen word, letting the transition structure pick a plausible tag from context alone. Run over held-out data, testFile tags brown-test-sentences.txt and scores its output against brown-test-tags.txt, counting correct against incorrect tags.

References

Project repository
Reference notes: Sequence Labeling: POS and NER
Reference notes: Probabilistic Reasoning over Time

╌╌ END ╌╌