Stochastic NLP: POS tagging, n-grams & PCFGs

Counting instead of hand-coding

Hand-built grammars and knowledge bases hit the knowledge-acquisition bottleneck: there is too much language to encode by hand. The stochastic alternative *learns* the regularities from a corpus by counting, and it works astonishingly well for the scale-limited tasks where deep understanding is not required.

Part-of-speech tagging as HMM decoding

The POS tagging problem: given a word sequence $w_1\dots w_n$, find the tag sequence $t_1\dots t_n$ that maximizes $p(t_1\dots t_n \mid w_1\dots w_n)$. The exact joint probability is intractable (exponential in sentence length), so we make the first-order Markov approximation, two assumptions:

- each tag depends only on the previous tag: $p(t_i \mid t_1\dots t_{i-1}) \approx p(t_i \mid t_{i-1})$ — the transition probability; - each word depends only on its own tag: $p(w_i \mid \dots) \approx p(w_i \mid t_i)$ — the emission probability.

Maximizing the product $\prod p(t_i \mid t_{i-1})\,p(w_i \mid t_i)$ is exactly a Hidden Markov Model decoding problem: hidden states = true tags, observations = words. The Viterbi algorithm finds the most-probable hidden path in $O(t^2 s)$ time ($t$ tags, $s$ sentence length). Both probability tables are estimated by counting in a hand-tagged training corpus — and this simple bigram model reaches about 97% accuracy, near human level.

n-grams and the bigram model

The transition table above is a bigram model: the probability of the next item given the one before it, $p(w_i \mid w_{i-1})$, estimated as $\text{count}(w_{i-1}, w_i) / \text{count}(w_{i-1})$. Trigrams condition on the previous *two*; in general an n-gram conditions on the previous $n-1$. The same machinery predicts the next word, scores a sentence's fluency, or — as transition probabilities — drives the tagger.

Worked example — a bigram next-word predictor

The exercise below builds bigram counts from a tiny corpus and predicts the most likely word after the. In the corpus, the is followed by dog twice and by cat and bird once each (4 occurrences), so $p(\text{dog} \mid \text{the}) = 2/4 = 0.5$, and the model prints after 'the' -> 'dog' (p=0.5). That is the entire idea of a statistical language model in one line of arithmetic.

PCFGs — probabilities on grammar rules

A probabilistic context-free grammar (PCFG) attaches a probability to each rule; a parse's probability is the product of the rule probabilities used, so an ambiguous sentence is disambiguated by choosing the highest-probability parse. A lexicalized PCFG adds word-level affinities — e.g. $p(\text{verb} \mid \text{subject noun})$, capturing that dogs are more likely to *bite* than to *like* — resolving attachments that structural probabilities alone cannot ("print the file on the printer"). PCFGs connect straight back to Chapter 13's stochastic methods: they can be learned with EM and decoded with dynamic programming analogous to Viterbi.