Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 49 ยท Computational Linguistics

Chapter review: Computational linguistics

Review corpora, Zipf's law, n-gram models, perplexity, tagging and CKY parsing with a one-picture summary, a recap table and a ten-question quiz.

This chapter followed a single thread: how to turn the rich, messy structure of language into something a computer can count, predict and analyse. You counted words, saw that a few dominate, built models that predict the next word, labelled words and parsed sentences. Here is the whole chapter on one page.

Four cards: corpus, n-grams, tagging and parsing, with a loop arrow labelled evaluate on held-out text
The chapter in one picture: count, predict, label, parse, and always test on text the model has not seen.

The chapter in one table

Topic Core idea Key numbers or names
Corpus A structured sample of language Brown Corpus (1 million words), Penn Treebank
Tokens and types Occurrences versus distinct forms type-token ratio falls as text grows
Zipf's law frequency โ‰ˆ C / rank log-log slope near โˆ’1; Mandelbrot refinement
Sparse data Most sequences are never seen hapax legomena; need for smoothing
n-gram model Predict the next word from the last n โˆ’ 1 chain rule, Markov assumption
Smoothing Give unseen events some probability add-one, backoff, Kneser-Ney
Perplexity Average branching, lower is better exp(โˆ’mean log P)
POS tagging Label each word in context most-frequent-tag baseline about 90 percent
HMM and Viterbi Best tag path by dynamic programming transition and emission probabilities
CKY Chart of spans, cubic time CNF grammars; S in the whole-span cell
Evaluation Test on held-out data accuracy, perplexity

Questions to carry forward

  • Does fluency equal understanding? ELIZA looked clever with a few patterns; modern language models are far more capable, and researchers disagree about what that shows.
  • What do models inherit from data? Biases and gaps in a corpus appear in the model.
  • Where does linguistic knowledge still matter? In designing annotation schemes, testing models on hard constructions (agreement across long distance, scope, ambiguity) and explaining errors.

Try it

The first demo computes perplexity from a list of probabilities a model assigned to each next word. It shows how a more confident model scores lower.

JS Perplexity calculator

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

No output.

The second demo runs a tiny end-to-end check: tokenize, look up categories, and ask a CKY recognizer whether each sentence is accepted by a small grammar.

Python From text to accepted parse

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 ยท 10 questions

of 10 answered You scored / 10 ยท perfect!

  1. 1. Which pair best describes the sentence the cat saw the dog?

    The is repeated, so there are four distinct types and five tokens.
  2. 2. On log-log axes, Zipf's law looks like:

    Slope near minus one.
  3. 3. What is the main reason for smoothing?

    Because of the long tail, many valid n-grams are missing from training data.
  4. 4. A model that assigns probability 0.1 to each next word has perplexity:

    It is torn between ten equally likely choices at each step.
  5. 5. Which limitation of n-gram models is illustrated by long-distance subject-verb agreement?

    The agreeing word may lie outside the n-gram window.
  6. 6. What does the Viterbi algorithm use to avoid trying every tag sequence?

    It keeps only the best path ending in each tag at each position.
  7. 7. A CKY parse succeeds when:

    The start symbol must cover the entire input.
  8. 8. What is the time complexity of CKY in sentence length n?

    Three nested loops over start, end and split point.
  9. 9. Why must models be evaluated on held-out data?

    Performance on training text overestimates real ability.
  10. 10. What did the typing-monkey argument imply about Zipf's law?

    Random processes can produce the same shape.

Summary

  • Corpora give counts; Zipf's law shapes everything built on them.
  • n-gram models predict from local context and need smoothing; perplexity compares them.
  • Tagging and parsing recover categories and structure with dynamic programming.
  • Always evaluate on held-out data, and remember that models inherit the limits of their data.

Next: Project: a language identifier