How NLP is done: approaches and linguistic knowledge

In 1966 Joseph Weizenbaum's ELIZA could take "I need some help" and answer "WHAT WOULD IT MEAN TO YOU IF YOU GOT SOME HELP". Jurafsky and Martin describe it as "a surprisingly simple program that uses pattern matching on words to recognize phrases like 'I need X' and change the words into suitable outputs", working "by having a series or cascade of regex substitutions". Every one of those rules was typed by a person. A modern translation system, by contrast, was shown millions of sentence pairs and nobody wrote a rule for any of them.

Those two systems mark the ends of one axis, and the four approaches on slide 15 are points along it. What separates them is not the task and not the programming language. It is the answer to a single question: what does a human write, and what does the data supply?

Rule-based: the human writes everything

In rule-based NLP the knowledge of language lives in artefacts a person authored: a grammar, a lexicon, a set of regular expressions, a finite-state machine. The Georgetown-IBM demonstration of 7 January 1954, the first public machine translation, was in Hutchins's account "a small-scale experiment of just 250 words and six 'grammar' rules". ELIZA came twelve years later, and Jurafsky and Martin date the whole symbolic era "roughly from 1965 til the early 1990s".

The strengths follow from authorship. A rule is precise, you can read it, you can explain any output by pointing at the rule that produced it, and nothing has to be trained. Rule-based tokenizers are, in Jurafsky and Martin's words, "deterministic algorithms based on regular expressions compiled into efficient finite state automata", which is why they are fast. The weakness follows from the same fact: language keeps producing phenomena nobody wrote a rule for, and every one of them costs another rule, which may conflict with the rules already there.

Classical machine learning: the human writes the features, the data sets the weights

Machine learning based NLP moves the boundary. A person still decides what the model looks at, but the data decides how much each observation matters. For a part-of-speech tagger the designer might say "look at the word, its suffix, its capitalisation, and the previous tag". Jurafsky and Martin describe the arrangement exactly: "Although the idea of what features to use is done by the system designer by hand, the specific features are automatically populated by using feature templates", so a word-shape feature maps DC10-30 to XXdd-dd without anyone listing every flight number. A Classifier such as naive Bayes or logistic regression, or a sequence model such as a hidden Markov model or a conditional random field (Lafferty, McCallum and Pereira, 2001), then learns the weights from labelled examples.

The era began, by Jurafsky and Martin's account, with Jelinek's IBM speech group between 1975 and 1985, and "by the late 1980s statistical methods had begun to spread from speech researchers to NLP researchers working on text"; they date this "long revival of empiricism" as lasting until 2017. The strength is robustness: a probabilistic model degrades gracefully on input no rule anticipated. The price is twofold. Someone must label the training data, and someone must engineer the features, which is where the linguistic knowledge of the designer now goes.

End-to-end deep learning: the data supplies the representations too

End-to-end NLP using deep learning removes feature engineering. The model reads raw text (or audio) and learns its own intermediate representations on the way to the output. Sutskever, Vinyals and Le (2014) translated by using "a multilayered Long Short-Term Memory (LSTM) to map the input sequence to a vector of a fixed dimensionality, and then another deep LSTM to decode the target sequence". Vaswani and colleagues (2017) then proposed "a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely". Jurafsky and Martin note that the transformer, "invented for machine translation, quickly became a general-purpose neural architecture", and mark prompting in 2019 as the next inflection point. Speech went the same way: modern recognisers are encoder-decoder models with no hand-built pronunciation pipeline in front.

What the designer still writes is the architecture and the training objective. Everything else, including whatever the model knows about morphology or syntax, arrives from data. That gives the best accuracy and one model for many tasks, at the cost of very large data sets and compute, and of a system nobody can read. Jurafsky and Martin treat interpretability as an open research field for exactly this reason.

Hybrid: rules around a learned core

The Hybrid approach is what most production systems actually are. The pattern is a learned model in the middle with rules on either side: rules for normalisation before the model, and rules for constraints, safety checks or formatting after it. The clearest example is hiding inside the largest models. The GPT-2 tokenizer first runs a hand-written regular expression, which Jurafsky and Martin show as "the GPT-2 pre-tokenizer regular expression, used to split (roughly) on whitespace before running the BPE algorithm", and only then applies byte-pair encoding merges learned from data (Sennrich, Haddow and Birch, 2016). Rule first, learning second, in the front door of a language model.

Take one paragraph: "Dr. Ahmad's students are running experiments. The pipeline costs 3.14 dollars per run. It works!" To a machine this is a string of characters. Before any approach from the last concept can be applied, that string has to be cut into units the approach can work on, and slide 16 names the cuts: paragraphs to sentences, sentences to words, words to their morphology.

Step through the paragraph below before reading on. Watch which periods survive as sentence boundaries, where the apostrophe goes, and what happens to are under each normaliser.

Paragraphs to sentences: the period is ambiguous

Sentence boundary disambiguation looks easy because sentences end in punctuation. Jurafsky and Martin explain why it is not: "Question marks and exclamation points are relatively unambiguous markers", but "the period character '.', on the other hand, is ambiguous between a sentence boundary marker and a marker of abbreviations like Dr. or Inc.". Our paragraph has two periods that are not boundaries: the one in Dr. and the decimal point in 3.14. The stepper's second example adds the harder case, Inc., where one period closes the abbreviation and ends the sentence at the same time. Jurafsky and Martin use that case to argue that "sentence tokenization and word tokenization can be addressed jointly": the decision about the period is one decision, not two.

Practical splitters decide with an abbreviation dictionary, which "can be hand-built or machine-learned" (Kiss and Strunk, 2006, is the standard unsupervised method, and the NLTK Punkt tokenizer in the stepper implements it). Notice which approach that is: a rule, backed by a list that a person or a corpus supplies. The last concept's axis is already in play at the first step.

Sentences to words: tokenization is not splitting on spaces

Tokenization turns a sentence into tokens, and the trouble starts with the apostrophe. Jurafsky and Martin point out that "I'm is one word, grammatically it functions as two words". The 's in Ahmad's is a clitic, in their definition "a morpheme that acts syntactically like a word but is reduced in form and attached ... to another word" (a morpheme being the smallest meaningful piece of a word, defined properly below), and the Penn Treebank convention therefore splits it off, giving Ahmad and 's as two tokens. The same convention separates doesn't into does and n't, keeps hyphenated words such as San Francisco-based together, and makes every punctuation mark its own token, which is why the first sentence yields eight tokens, not six words.

The choices are language-specific. Arabic attaches the preposition b (by, with) and the conjunction w (and) to the following word, so a tokenizer for Arabic must decide whether to detach them. Chinese, Japanese and Thai, in Jurafsky and Martin's words, "simply don't have orthographic words at all": Chinese words average "roughly between 1.5 and 1.9 characters long" and a sentence such as 姚明进入总决赛 can be segmented as three words, five words or seven characters. Numbers differ too, 555,500.50 in one convention and 555 500,50 in another. This is Segmentation in its most basic form, and part 4 returns to it as a source of difficulty.

Words to morphology: chop, or look up

A word is built from morphemes, which Jurafsky and Martin define as minimal meaning-bearing units: cats is the morpheme cat plus the morpheme -s. Morphology is the level that knows this, and slide 16 lists two ways to use it. Stemming, in Manning, Raghavan and Schütze's definition, is "a crude heuristic process that chops off the ends of words in the hope of achieving this goal correctly most of the time". Lemmatization means "doing things properly with the use of a vocabulary and morphological analysis of words, normally aiming to remove inflectional endings only" and returning the lemma, the dictionary form.

The difference is visible in the stepper. Porter's 1980 algorithm, "the most common algorithm for stemming English", turns experiments into experi and are into ar: neither is a word, and the stemmer does not care, because it never consults a dictionary. The WordNet lemmatizer turns are into be. No suffix rule can do that; Manning and colleagues give exactly this case, "am, are, is" to be, as the reason lemmatization needs a vocabulary. It also needs the part of speech: running as a verb lemmatizes to run, but as a noun ("the running of the race") it stays running. The Porter stemmer gives run either way, and on that verb the two methods happen to agree.

Extend the running example by one sentence: "Dr. Ahmad's students are running experiments. They will publish them tomorrow." Say it aloud, and something has to know that the sound wave you produced for running counts as that word and not runny. Write it down, and something has to know that they means the students and them means the experiments. Between those two ends lie the levels of linguistic knowledge, and slide 17 draws them twice: as concentric rings and as a stack with two roots.

Walking one sentence up the rings

Phonetics is, in Jurafsky and Martin's definition, "the study of the speech sounds used in the languages of the world, how they are produced in the human vocal tract, how they are realized acoustically, and how they can be digitized and processed". Its unit is the phone, the actual speech sound; the rings figure labels it "speech sounds", which is correct. A casual runnin' ends in a different phone from a careful running, and a recogniser must still hear one word: that variation is phonetics. Phonology abstracts over that variation to phonemes, the sound units that make one word different from another: running and runny differ by phonemes, however each is pronounced. Jurafsky and Martin put both under one heading in their list, "Phonetics and Phonology: knowledge about linguistic sounds", and note that speech recognition and synthesis need them to know "how words are pronounced in terms of sequences of sounds and how each of these sounds is realized acoustically".

On the text side the same role is played by Orthography, the writing system: the letters r-u-n-n-i-n-g, the fact that Arabic is written right to left with letters that change shape by position, the choice of Unicode code points. Both branches feed Morphology, which was the last concept: run plus -ing, student plus -s, Ahmad plus 's. Jurafsky and Martin's example is that "recognizing that doors is plural" requires morphology.

Above morphology sits the lexical level, which slide 16 calls "lexemes". A Lexeme is a vocabulary item with its senses: run as move fast, as operate, as manage. This is the level where Word sense disambiguation lives, the same task that slide 9 needed to read "heavy" as mass. Syntax is "knowledge of the structural relationships between words": the noun phrase "Dr. Ahmad's students" is the subject of "are running", and Parsing is the task that recovers such structure. Semantics is "knowledge of meaning", here the literal proposition that some students conduct experiments.

The last two levels leave the sentence (the rings stop at pragmatics; only the stack adds discourse above it). Pragmatics is "knowledge of the relationship of meaning to the goals and intentions of the speaker": "tomorrow" names a different day depending on when the sentence was written, which is exactly what the calendar extraction of slide 12 had to resolve. Discourse is "knowledge about linguistic units larger than a single utterance": deciding that they and them refer back to the students and the experiments is coreference resolution, the standard discourse task. Jurafsky and Martin close the list with the sentence that opens the next part: "most tasks in speech and language processing can be viewed as resolving ambiguity at one of these levels".

Two figures, three omissions

The rings and the stack on slide 17 disagree in three small ways, and each is worth knowing because they are the kind of thing an exam question probes. The rings have no lexical ring: they go straight from morphology (words) to syntax (phrases and sentences), while the stack has "lexemes" between them. The rings have no orthography: they start from phonetics as if all input were speech, while the stack shows the text branch explicitly. The rings also stop at pragmatics, labelled "meaning in context of discourse", while the stack puts a separate discourse level on top. Read the stack as the complete list and the rings as the speech-first view.

The lecture opens its next question, why NLP is difficult, with a picture rather than a list: a baby in a pinstriped suit sitting beside a laptop, labelled "Predisposed for acquiring language" and "Not so!". The joke carries the most important idea in the part. Jurafsky and Martin cite estimates that young adult speakers of American English know between 30,000 and 100,000 words, and conclude that children must learn "about 7 to 10 words a day, every single day" to reach that level by age 20 (the full range alone implies roughly 4 to 14 a day), most of them picked up "as a by-product of reading" with nobody teaching each one. The laptop knows nothing until someone types rules or feeds it data.

The claim on the slide is the nativist position in psycholinguistics. Its classic argument is the poverty of the stimulus: in the Stanford Encyclopedia's summary, "there are aspects of developed linguistic competence which cannot be explained with respect to the evidence available to the language learning child", so something must be built in. The debate about how much is built in remains open; the same entry notes that modern empiricists no longer defend a blank slate but "complex, innately structured minds and learning systems" while denying that any of them are specific to language. For this course you do not need to settle that. You need the part of the slide that nobody disputes: whatever a child brings to the task, a machine brings none of it.

Now put the two previous concepts side by side. The rings list the Knowledge of language that any language processor must have, from phonetics to discourse. The four approaches list the only two ways that knowledge can get into a machine: a person writes it down (rule-based), or a model extracts it from data (machine learning and Deep learning). There is no third route. Every ring, for every language the system must handle, has to be filled through one of those two arrows. That is why NLP is difficult, which part 4 takes up, and why slide 24 lists the disciplines and tools needed to do the filling.

The learned route is now the dominant one, and Jurafsky and Martin describe how far it reaches: large language models "learn this knowledge of language, knowledge of concepts, and knowledge of the world simply by being taught to predict the next word", an idea that goes back to the distributional hypothesis of the 1950s. Note what the learner is given: text, and only text. A child gets speech embedded in a situation, with gestures, objects and corrections. Jurafsky and Martin add that "grounding from real-world interaction or other modalities like vision can help build even more powerful models, but even text alone is remarkably useful".