Stochastic NLP: POS tagging, n-grams & PCFGs

◈ 4 cards

The Markov approach to language: part-of-speech tagging as HMM decoding with Viterbi, n-gram models, and probabilistic context-free grammars for disambiguation.

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} ∣ 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} ∣ t_{1} \dots t_{i - 1}) \approx p (t_{i} ∣ t_{i - 1})$ — the transition probability;
each word depends only on its own tag: $p (w_{i} ∣ \dots) \approx p (w_{i} ∣ t_{i})$ — the emission probability.

Maximizing the product $\prod p (t_{i} ∣ t_{i - 1}) p (w_{i} ∣ 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} ∣ w_{i - 1})$ , estimated as $count (w_{i - 1}, w_{i}) / 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 (dog ∣ 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 (verb ∣ 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.