Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 49 ยท Computational Linguistics

Tagging and parsing

Learn how computers label words with parts of speech, how an HMM tagger uses the Viterbi algorithm, and how the CKY chart parser builds syntax trees step by step.

Two jobs sit at the heart of the classic NLP pipeline. Tagging decides what kind of word each token is. Parsing decides how the words fit together. Both have to cope with ambiguity: flies can be a noun or a verb, and I saw the man with a telescope has two trees. This lesson shows how algorithms solve these problems efficiently, using ideas you have met in the syntax chapter.

A triangular parse chart for the cat sleeps, with determiner, noun, verb phrase, noun phrase and sentence cells
The CKY chart: short spans at the bottom, longer spans above. A sentence is accepted when S covers the whole input.

What you will learn

  • What part-of-speech tags are and how well simple methods work
  • How a hidden Markov model tags a sentence with the Viterbi algorithm
  • How the CKY algorithm fills a chart to parse a sentence
  • Why modern parsers use probabilities and neural networks

Key terms

Part-of-speech (POS) tag: a label such as NOUN, VERB, ADJ for a word in context.

HMM: a hidden Markov model, where tags are hidden states that emit words.

Viterbi algorithm: a dynamic-programming method that finds the most probable tag sequence.

CKY algorithm: a chart-parsing method for grammars in Chomsky normal form.

Treebank: a corpus annotated with syntactic trees.

Part-of-speech tagging

A tagger reads a sentence and outputs one tag per token. The Penn Treebank tag set has about 45 tags (NN singular noun, VBD past-tense verb); the Universal Dependencies project uses 17 coarse tags (NOUN, VERB, ADJ, ADP, DET...) that work across languages. Tagging is hard because many words are ambiguous: book is a noun or a verb, and that can be a determiner, a pronoun or a conjunction.

Even a naive tagger does well. Assigning each word its most frequent tag in training data, and noun for unknown words, reaches roughly 90 percent accuracy on English news text. Careful statistical and neural taggers reach about 97 percent, close to the rate at which human annotators agree. The remaining errors are mostly truly hard cases, such as The old man the boats.

HMM taggers and the Viterbi algorithm

A classic tagger models two things. Transition probabilities say how likely one tag is after another (a determiner is usually followed by a noun). Emission probabilities say how likely a tag is to produce a given word (a NOUN produces time more often than a VERB does). The tagger wants the tag sequence with the highest product of these probabilities.

Trying all sequences is impossible: with 45 tags and 20 words there are 45^20 of them. The Viterbi algorithm avoids that with dynamic programming: for each position and each tag it keeps only the best path that ends there. The cost grows linearly with sentence length and quadratically with the number of tags.

Parsing with a chart

Parsing asks whether a grammar can derive the sentence, and with which tree. Recall the phrase-structure rules from the syntax chapter. A naive parser tries rule after rule and repeats the same work many times. The CKY algorithm (named after Cocke, Kasami and Younger, who each discovered it in the 1960s) avoids this with a chart: a table indexed by spans of the sentence.

It assumes the grammar is in Chomsky normal form (CNF): every rule is either A โ†’ B C (two non-terminals) or A โ†’ word. Any context-free grammar can be converted to CNF. Then:

  1. For each word, record the categories the lexicon gives it (span lengths of 1).
  2. For each longer span, from short to long, try every split point. If the left part has category B and the right part has category C and the grammar has A โ†’ B C, record A for the whole span.
  3. The sentence is accepted if S appears in the cell spanning the whole sentence.

The picture at the top shows the result for the cat sleeps. Cell (0,2) contains NP because NP โ†’ Det N; cell (0,3) contains S because S โ†’ NP VP. If you keep pointers to the pieces that created each entry, you can read off the tree. The algorithm takes time proportional to nยณ for a sentence of n words, and to the size of the grammar. This is much faster than listing every possible tree, even though the number of trees can be exponential: the chart packs them together.

Probabilistic parsing

Real sentences are ambiguous. A probabilistic context-free grammar (PCFG) attaches a probability to each rule, learned by counting in a treebank (for example, how often a VP consists of a verb plus an object). CKY then finds the most probable tree instead of just any tree. Plain PCFGs make poor choices because their rules ignore the actual words, so modern parsers add lexical and contextual information. Today's best parsers use neural networks to score constituents or dependencies, and dependency parsers (such as those trained on Universal Dependencies treebanks) are popular because they work well across languages and are fast.

Common misconceptions

"Tagging is easy because words have fixed categories." Many words change category by context, and 97 percent accuracy still means an error in every few sentences.

"A parser outputs the one correct tree." For ambiguous sentences a parser must choose, using probabilities or learned preferences. Human readers choose using meaning and context.

"Parsing is exponential." Listing all trees may be, but CKY decides grammaticality in cubic time.

Try it

The first demo is a toy HMM tagger with Viterbi decoding. All probabilities are invented for the demonstration and cover only five words. Change the numbers and see how the best tag sequence changes.

Python Viterbi tagging (toy)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Run it and compare the two sentences. In this toy model both receive the same tags, because the model has no word-specific knowledge that fruit flies are insects; real taggers use the whole sentence and far more evidence.

The second demo is a CKY recognizer that fills the chart for the cat sleeps and prints it, then lists the categories found for the whole span. The third part counts the operations the algorithm performs as sentences get longer, which grows with the cube of the length.

Python CKY chart

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 6 questions

of 6 answered You scored / 6 ยท perfect!

  1. 1. What does a part-of-speech tag tell you?

    Tags such as NOUN or VERB are assigned per occurrence.
  2. 2. Roughly how accurate is a tagger that gives each word its most frequent tag?

    A simple baseline is already good, because most words have a dominant tag.
  3. 3. What does the Viterbi algorithm find?

    It uses dynamic programming to avoid trying every sequence.
  4. 4. A grammar in Chomsky normal form has rules of which shapes?

    That restriction lets CKY combine exactly two sub-spans at a time.
  5. 5. In the CKY chart, how does the parser know the sentence is accepted?

    The whole-sentence cell must contain the start symbol.
  6. 6. What does a PCFG add to a plain CFG?

    It lets the parser pick the most probable tree.

Summary

  • Tagging assigns categories in context; simple baselines are strong and statistical models are better.
  • HMM taggers use transition and emission probabilities, with Viterbi finding the best path efficiently.
  • CKY fills a chart of spans in cubic time and packs ambiguity compactly.
  • Modern parsers add probabilities and neural networks, and often use dependency representations.

Next: Chapter review: Computational linguistics