Introduction to natural language processing

Three things you probably did this week. You said "hey Siri, set an alarm for six" and a phone acted on it. A visitor pointed Google Translate's camera at an Arabic menu and read it in English. And Gmail moved a phishing message into spam before you ever saw it. All three are natural language processing, and they are three different jobs: a human talking to a machine, two humans with a machine in the middle, and no conversation at all, just text being handled usefully.

That is exactly how the field defines itself. Slide 4 states it in one sentence: NLP is a branch of artificial intelligence that is concerned with interactions between computers and human language. The purpose clause that follows is the part to memorise, because it lists the three goals in a fixed order: enabling human-machine communication, improving human-human communication, or simply doing useful processing of text or speech. The wording is lifted almost verbatim from the opening of Jurafsky and Martin's textbook, which describes the goal of the field as getting computers to perform useful tasks involving human language, "tasks like enabling human-machine communication, improving human-human communication, or simply doing useful processing of text or speech" (Jurafsky and Martin, 2nd edition, chapter 1).

Notice what the definition does not say. It does not name a technique. It does not say statistics, or neural networks, or grammars. NLP is defined by its problem, human language, and by what it wants to achieve with it. The techniques have moved from hand-written rules to statistical learning to deep neural networks (part 03 walks through that sequence), and the definition has not moved with them. That is why it is worth learning by heart: it will still be true when the current models are obsolete.

The logos, sorted by goal

Slide 2 shows seven companies and says nothing else, so the exercise is to say it for them. Each logo stands for at least one product whose core step is a language step, and each of those products serves one of the three goals. Google Search is the clearest case: in 2019 Google wrote that "Search is about understanding language" and introduced BERT to help it understand one in 10 searches in the U.S. in English better (Google, 2019). Amazon's developer documentation describes the Alexa pipeline as streaming your speech to the cloud, where "the Alexa service handles the speech recognition and natural language processing" (Amazon). Meta's No Language Left Behind project calls machine translation "a key focus of artificial intelligence research today" and covers 200 languages (NLLB Team, 2022). Grammarly says its team of computational linguists and deep learning engineers builds algorithms that learn "the rules and hidden patterns of good writing by analyzing millions of sentences" (Grammarly), which is spelling and grammar correction at industrial scale.

One field, many names

Slide 4 ends by admitting that the field "has many names" and lists three. They are not rival fields. Each stresses a different facet of the same work, and the facet tells you who is speaking. When someone says computational linguistics they are usually facing the linguistics side: language as the object of scientific study, with computation as the method. Its professional society is the ACL, which describes itself as serving people working on computational problems involving human language, "a field often referred to as either computational linguistics or natural language processing (NLP)" (ACL). When someone says speech and language processing they are quoting the title of the Jurafsky and Martin book and reminding you that speech is in scope. When someone says human language technology they are on the engineering side, thinking about systems that ship.

The list keeps growing. The current draft of the third edition says the field "has many names corresponding to its many facets, including natural language processing (NLP), computational linguistics, spoken language processing, speech recognition, or most recently simply language modeling" (Jurafsky and Martin, 3rd edition draft, chapter 1). Note the word "recently": language modeling is the newest label, not a replacement for the field.

Take the spam filter again and ask what you would need to build one. You need to know what counts as a word, that free and FREE!!! are the same word dressed differently, and that "not a scam" flips the meaning of "scam". That is linguistics. You need a classifier, a hash table for the vocabulary, and an algorithm that runs in reasonable time on millions of messages. That is computer science. And you need a way to learn the weights from mail people have reported, and to represent the result as "spam with probability 0.97". That is artificial intelligence.

Slide 5 draws this as a Venn diagram: NLP sits at the intersection of linguistics, computer science (abbreviated Comp. Sci. on the slide) and AI, and the bullet list trails off with an ellipsis. The ellipsis is not decoration. Read against slide 24, which names the fields NLP draws its models, algorithms and theories from as computer science, mathematics and linguistics, the ellipsis stands most plausibly for mathematics (the part of it NLP leans on most is probability and statistics). Jurafsky and Martin go further, listing the foundations of the field as "computer science, linguistics, mathematics, electrical engineering, and psychology" (Jurafsky and Martin, 2nd edition, chapter 1). Electrical engineering enters through the signal processing that speech needs, and psychology through the study of how people actually produce and understand language.

What each parent contributes

The three circles are not interchangeable, and an exam question will often ask you to say what each one brings. Linguistics supplies the object of study and the vocabulary for describing it: the levels of language from sounds through words and sentences to meaning and discourse, the theories of grammar that say which sentences are well formed, and the very idea of ambiguity, which part 04 returns to. Computer science supplies the machinery. Jurafsky and Martin single out "state space search algorithms, such as dynamic programming, and machine learning algorithms, such as classifiers" as the most important (Jurafsky and Martin, 2nd edition, section 1.3). AI supplies learning and knowledge: how to fit a model to data, how to store facts a program can reason over, and the probabilistic stance that, given several possible readings, you should choose the most probable one.

Jurafsky and Martin make the point with the Unix program wc. When it counts bytes and lines it is ordinary data processing. When it counts words it is doing something linguistic, because it needs to know what a word is. The line between data processing and language processing is exactly the linguistics circle: the moment your program relies on knowledge of language, it has crossed into NLP.

Photograph a street sign in Riyadh with your phone. Vision finds the sign in the pixels and reads its letters. NLP translates the words on it. A delivery robot could be told "turn left at that sign" and act on it. And a knowledge base knows that the name on the sign is a real district with a location and a history. One photo has just touched four subfields of artificial intelligence, and most of those steps are now learned from data by a fifth.

Slide 6 lists those five subfields as stacked boxes: natural language processing, knowledge representation and deduction, machine learning, computer vision and robotics. Only one box has a sub-bullet: deep learning is indented under machine learning. The same map appears in the standard AI textbook. Russell and Norvig give knowledge representation its own chapter inside a part called "Knowledge, reasoning, and planning", give machine learning its own part with a deep learning chapter inside it, and group natural language processing, computer vision and robotics under "Communicating, perceiving, and acting" (Russell and Norvig, 4th edition, table of contents). The slide is the textbook's contents page compressed to five lines.

• Natural language processing
• Knowledge representation and deduction (standard phrase: reasoning)
• Machine learning, with deep learning as its sub-area
• Computer vision
• Robotics

Sibling and tool at once

The key point of the slide is why deep learning is indented rather than listed beside the others. Machine learning is a subfield in its own right, but it is also the main method NLP, computer vision and robotics now use, and an increasingly common one in knowledge representation as well. Goodfellow, Bengio and Courville draw this as nested sets: deep learning is a kind of representation learning, which is a kind of machine learning, "which is used for many but not all approaches to AI" (Goodfellow et al., 2016, figure 1.4). The nesting is why the slide indents deep learning, and the "used for" clause is why the AI textbook has both a chapter called Natural Language Processing and one called Deep Learning for Natural Language Processing. It is also why the rest of ICS 582 is mostly machine learning: the problem is language, the method is learning.

The pairings between NLP and its siblings are concrete systems you can name in an exam. With computer vision, image captioning: Vinyals and colleagues describe automatically describing an image as a problem that "connects computer vision and natural language processing" (Vinyals et al., 2014). Optical character recognition is the other direction, a vision task that extracts "printed or handwritten text from images such as posters, street signs, and product labels" and hands it to NLP (Microsoft Learn). With robotics, instruction following: the SayCan system completes "long-horizon, abstract, natural language instructions on a mobile manipulator", with the robot acting as the language model's "hands and eyes" (Ahn et al., 2022). With knowledge representation, question answering over a knowledge graph: Google's Knowledge Graph understands "real-world entities and their relationships to one another: things, not strings", and uses that to tell the Taj Mahal monument from the musician (Google, 2012).

Take the definition of NLP from part 01, paste it into Google Translate, and pick Arabic. In under a second the right pane fills with معالجة اللغة الطبيعية هي فرع من فروع الذكاء الاصطناعي and a Latin transliteration line underneath. Nobody touched that output. The system read 142 characters of English and produced finished Arabic. That is machine translation in its fully automatic mode, and it is the mode most people picture when they hear the words.

Now look at the second screenshot on the same slide, which looks nothing like a consumer product. The source box holds an Arabic news sentence about the Lebanese president being subjected to a fierce campaign in parliament. The translator has typed one word into the translation box, lebanese, and the system has answered with a ranked list of what the next word could be: president, suffered, exposed, president emile, before, presented, offer. The human is still writing the sentence. The machine is predicting where the sentence goes next. This is computer-aided translation, and its existence is the most important fact on the slide: the professional tool keeps the human in charge.

Two modes, and who owns the final text

Jurafsky and Martin list three uses of MT: information access, aiding human translators, and in-the-moment communication. Fully automatic MT serves information access: you want to read a page written in a language you do not know, and a rough but instant translation is worth more than a perfect one next week. Google Translate alone, they note, translates hundreds of billions of words a day between over 100 languages. The second use is aiding human translators. Here the system is not the author. It drafts a translation that a person then fixes, a workflow called post-editing. Interactive systems (Barrachina et al., 2009) go further: they sit inside the editor and predict as the person types, which is what the slide shows.

The interactive kind has a precise description. Barrachina and colleagues put it this way: in each iteration, a prefix of the translation is validated (accepted or amended) by the human and the system computes its best, or n-best, translation suffix to complete that prefix. Read the slide's list with that in mind and it stops being a random menu. The list is an n-best set. "suffered" and "exposed" are two English readings of the same Arabic verb تعرض, and "president" versus "president emile" are two choices about how much of the source to consume in one step. The translator resolves in one click what a fully automatic system would have to gamble on.

Why keep the human at all, when the top screenshot is so good? Because the same paper opens with the plain admission that current MT systems are still not perfect and that in practice their output needs to be edited to correct errors. Which errors matter depends on the text. A gisted news article can survive a wrong verb. A contract, a drug label or a court transcript cannot, and someone must be accountable for the register, the terminology and the liability. The assisted mode is how the field turned an imperfect technology into a productivity tool rather than waiting for a perfect one.

The product numbers, and why they are pipelines

Slide 8 adds two products with feature lists. The Google Translate app page counts how many languages each mode supports, and the Skype Translator blurb promises voice calls in seven languages and adds a line worth remembering: it uses machine learning, so the more you use it, the better it gets. That sentence is the whole of part 03 in miniature. The system is not a fixed set of rules; it is a model that improves with data.

The more durable lesson on the slide is structural. Typing 103 languages is one system: text in, text out. Camera mode is not. To translate the Russian street sign in the photo, the phone must first read the pixels as characters (optical character recognition), then translate the characters, then paint the English back onto the image. Conversation mode is longer still: recognise speech, translate, synthesise speech in the other language. Jurafsky and Martin describe exactly this image-centric case, OCR of the text on a phone camera image used as input to an MT system to translate menus or street signs.

Keep this picture. When part 03 introduces the linguistic pipeline from paragraphs down to morphemes, and when part 04 lists the ways language defeats a system, both are describing links in chains like these. A product that looks like one feature is usually three or four NLP tasks in a row, and the quality the user sees is the product of all of them.

Type how heavy is our planet into a search engine and two very different things can come back. On slide 9 the engine answers with a card: Earth, Mass, 5.972 × 10²⁴ kg, a photograph, and a row of related planets. On slide 10 the same query produces an AI Overview: a paragraph explaining that Earth has a mass of approximately 5.972 × 10²⁴ kilograms, about 13.1 septillion pounds, measured using gravity rather than scales, with a heading on how scientists measure it and two cited sources in a side rail. Both are question answering. They are built on opposite principles.

What the answer box has to get right

The card looks trivial and hides three separate decisions. The slide's own label names two of them: information extraction and word sense disambiguation. Start with the word "heavy". It has several senses: heavy rain, heavy traffic, a heavy heart, a heavy object. Only one of them is a physical quantity a database could store, so the system must choose the sense "has a large mass" before it can look anything up. That choice is word sense disambiguation, and the answer card's label "Mass" is the visible trace of it.

The second decision is about "our planet". No table anywhere has a row called "our planet". The phrase is a string; the answer requires a thing. Google's Knowledge Graph was announced in 2012 under exactly that slogan, things not strings: a model that understands real-world entities and their relationships to one another, so that "Taj Mahal" can mean the monument or the musician. Mapping the mention "our planet" to the entity Earth is entity linking. (The literature calls this entity linking; entity resolution more often means merging duplicate records.) Only once both decisions are made does the third step become a lookup: fetch the mass attribute of the Earth node.

Where did the graph get that number? From text, by information extraction: Jurafsky and Martin define IE as turning the unstructured information embedded in texts into structured data, for example for populating a relational database, and note that knowledge graphs of structured relational knowledge are a useful way for search engines to present information to users. The answer box is therefore the last inch of a long chain: extractors read encyclopedias and fact sheets once, store facts as graph edges, and the search engine reads the edge at query time. The same machinery returns in the email example two concepts from now.

The ratios check out from the slide's own numbers: 6.39 / 59.72 = 0.107, 4.867 / 5.972 = 0.815 and 1898 / 5.972 = 317.8. The Mars row also carries a quiet lesson: the card shows 6.39 × 10²³ kg while NASA's current fact sheet lists 6.4169 × 10²³ kg, about 0.4 percent higher. Nothing in the card is broken. An extracted fact is only as accurate as the source it was extracted from, and that is the answer box's characteristic failure: it can only be as wrong as its stored fact, and it has no way to be more right.

What changes when a language model writes the answer

Slide 10 is the same query on a search page with an AI Mode tab and an AI Overview. Nothing was looked up in a graph and rendered as a card. Instead the engine retrieved documents, handed them to a large language model, and let the model write. Jurafsky and Martin call this retrieval-augmented generation: use information retrieval techniques to retrieve documents, then use a large language model to generate an answer conditioned on those documents. The recipe is three lines. Retrieve the top passages for the query, build a prompt that contains the query and those passages, and call the model.

The screenshot shows every ingredient. The retrieved passages are the two cards in the side rail, an AIP Inside Science article titled "How Much Does Earth Weigh?" and the Wikipedia article on Earth. The generation is the paragraph, which is not a quotation from either page but a new text stitched from both, complete with a unit conversion: 5.972 × 10²⁴ kg times 2.20462 lb/kg is 1.317 × 10²⁵ lb, which is the "13,170,000,000,000,000,000,000,000 lbs" in the overview and the "13 thousand, 170 billion trillion pounds" in the AIP article. The citation chips are the last ingredient, what the textbook calls a knowledge citation that helps the user decide whether to trust the generation.

Look closely at the second chip and you can see the seams. Its snippet reads "Table_title: Earth Table_content: header: | Designations | row: ...", which is not prose at all; the retriever pulled a Wikipedia infobox as a flattened table and the model wrote around it. That is the point of the shift: the classic box extracts one structured fact and shows it, the overview retrieves raw text and composes. The output is more helpful, more explanatory and more flexible, and it introduces a failure that the card never had.

That new failure has a name. Large language models hallucinate, and a hallucination, in Jurafsky and Martin's words, is a response that is not faithful to the facts of the world. They report a study in which, asked questions about the legal domain, large language models hallucinated from 69 to 88 percent of the time, and add the more troubling half: it is not always possible to tell when a model is hallucinating, partly because LLMs are not well calibrated, so they can give a very wrong answer with complete certainty. The card can be stale. The paragraph can be wrong while sounding exactly like the truth, and the citations can point to a page that does not say what the paragraph claims.

Slide 11 shows spelling and grammar correction at work: a Word window with one sentence in it, This is bigger then that ofcourse. Two words are underlined, and the colours are not decoration. ofcourse carries a red squiggle. then carries a blue one, and the context menu under it offers a single replacement, than. Microsoft's documentation spells out the convention: potential spelling errors get a red squiggly line, potential grammatical errors get a blue one. The two colours mark two different problems, and the second is much harder than the first.

Jurafsky and Martin draw the line precisely. Non-word spelling correction is the detection and correction of spelling errors that result in non-words, like graffe for giraffe. Real-word spelling correction is the task of detecting and correcting spelling errors even if they accidentally result in an actual word of English. ofcourse is the first kind: it is not in any dictionary, so the check is a lookup that needs no context whatsoever. then is the second kind. It is a perfectly good English word, in the dictionary, spelled correctly. Nothing about the word itself is wrong. What is wrong is the word in this position, between "bigger" and "that", where English demands the comparative partner "than".

That difference is why the second problem is hard. The textbook says it directly: real-word spelling error detection is a much more difficult task, since any word in the input text could be an error. And it is not a rare case. Studies suggest that between 25 and 40 percent of spelling errors are valid English words. A checker that only consults a dictionary silently passes a quarter to nearly half of all mistakes. To catch them, the system must know what English sentences look like, which is to say it needs alanguage model, a model that assigns higher probability to "bigger than that" than to "bigger then that", or a grammar rule that encodes the same preference by hand.

The noisy channel, in one line

The classical machinery for both kinds is the noisy channel model. Imagine the writer meant some word w and a noisy channel, their fingers, produced x. The corrector wants the intended word that best explains what it sees.

The candidate set V is kept small because the majority of spelling errors consist of a single-letter change, so candidates within one insertion, deletion, substitution or transposition of the typed string (Damerau-Levenshtein distance 1) cover most cases. For a non-word, the language model term just prefers common words. For a real-word error, the channel model works against the correction: in the Mays et al. model the textbook uses, P(x | w) is alpha (about 0.95) when the typed word is the intended one, and only the small remainder 1 - alpha is spread over candidates such as than. The language model term P(w) must therefore outweigh that bias, and it can only do so from context.

This is also the oldest NLP application most people use every day. Jurafsky and Martin note that spelling correctors are ubiquitous in pretty much any software that relies on keyboard input, from word processors to search boxes to phone keyboards, and the same noisy channel idea reappears in speech recognition and machine translation. Real-word correction was also an early case of a language model doing linguistic work that no dictionary could, which is the pattern the whole modern field follows.

An email arrives for Dan Jurafsky, dated January 15, 2012, subject "curriculum meeting". The body is two lines: "Hi Dan, we've now scheduled the curriculum meeting. It will be in Gates 159 tomorrow from 10:00-11:30. -Chris". Beside it sits a grey card that the mail client has filled in by itself: Event, Date, Start, End, Where, and a blue button, Create new Calendar entry. The email is prose. The card is a record. Getting from one to the other is information extraction, and the card is the clearest picture of it in the whole lecture.

The card is an instance of what Jurafsky and Martin call template filling: find documents that invoke a particular script, then fill the slots of the associated template with fillers extracted from the text. The script here is "a meeting is being scheduled", the template has five slots, and the textbook adds the distinction that makes the slide interesting. Slot fillers may consist of text segments extracted directly from the text, or they may consist of concepts that have been inferred from text elements through some additional processing. Sort the five fields by that rule and they split cleanly in two.

Resolving "tomorrow"

The Date field is the one worth slowing down on, because the word "tomorrow" contains no date at all. Jurafsky and Martin call this temporal normalization, the task of mapping a temporal expression to a point in time or to a duration, and they explain why it is possible: most temporal expressions are incomplete and only implicitly anchored, often with respect to the dateline of the article, which they call the document's temporal anchor. The values of expressions such as today, yesterday or tomorrow can all be computed relative to that anchor, and the rule for these two is the simplest one there is. Tomorrow adds a day to the anchor, yesterday subtracts one.

Two threads tie this concept to its neighbours. First, the textbook's own exercise on this chapter asks for exactly the application on the slide: associating temporal expressions connected with events in email with specific calendar entries, which is a sign of how central the example is. Second, the graph that the answer box read from in the previous concept was populated by the same kind of extractor working over encyclopedias instead of inboxes. Search returns documents. Extraction returns fields with normalised values that a program can act on, and the blue button is the program acting.

Slide 13 puts a camera next to a list of the things people talk about when they review it: zoom, affordability, size and weight, flash, ease of use. Under "Size and weight" it collects three remarks: "nice and compact to carry!", "since the camera is small and light, I won't need to carry around those heavy, bulky professional cameras either!", and "the camera feels flimsy, is plastic and very light in weight you have to be very delicate in the handling of this camera". Read the second and third again. Both say the camera is light. Decide below whether each one is praise or complaint, then read on.

The slide title pairs information extraction with sentiment analysis, and that pairing is the lesson. Bing Liu, whose book defined the field, states the principle: an opinion consists of a sentiment (positive or negative) and a target, and an opinion without its target being identified is of limited use. He calls the finer-grained task aspect level analysis, earlier called feature-based opinion mining after Hu and Liu's 2004 work on exactly this kind of camera review, and he formalises an opinion as a tuple of entity, aspect, sentiment, holder and time. Then he adds the line that explains the slide title: that tuple is basically a database schema. Sentiment analysis at this level is an extraction task first. Find the aspect, then judge the polarity of what was said about it.

Now the word "light" can be explained rather than just noticed. In the second review it sits next to "small" and is set against "heavy, bulky professional cameras", so it means easy to carry. In the third it sits next to "flimsy", "plastic" and "delicate", so it means insubstantial. The physical fact is identical. The polarity is a property of the aspect and the context together, not of the word and not of the document. Liu's own camera example makes the mirror image point: "my wife thinks it is too heavy for her" is a negative opinion about weight, and nothing about the word "heavy" on its own tells you that.

Aspects are not always spelled out either. Hu and Liu give the sentence "While light, it will not easily fit in pockets" and point out that the word size does not appear in it, so the system has to infer the aspect before it can score the opinion. Their illustrative summary for a digital camera counts opinions per feature, which is what the grey bars beside the slide's review list are sketching.

1. Find the sentences that express an opinion.
2. Extract the aspect each opinion targets, explicit (flash) or implicit (light, therefore size and weight).
3. Classify the polarity of the opinion about that aspect, using the surrounding words.
4. Aggregate into per-aspect counts, so a reader sees two positive and one negative on size and weight.

The order matters. A whole-document score would average the third review's complaint about build against whatever it praised elsewhere, perhaps affordability, and report a lukewarm three stars that helps nobody. Liu makes the same point with a restaurant: "although the service is not that great, I still love this restaurant" is positive about the restaurant and negative about the service, and a document-level system does not discover what exactly people liked and did not like.

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".

Take four ordinary words, I made her duck, and look for every meaning they can carry. The lecture asks for at least five and leaves the answers to you. Before reading on, try it honestly: how many can you find? Most people stop at two and are surprised that the sentence keeps going.

The five meanings are not the lesson. The lesson is where each one comes from. Jurafsky and Martin use this sentence because every reading is produced by one decision at one linguistic level, and those levels are exactly the ones you met in part 3. That is what makes ambiguity the central problem of the field rather than a party trick.

Work through what flips. The word duck can be a noun (the bird) or a verb (to lower your head), and her can be a dative pronoun (for her) or a possessive (her duck). Both are lexical ambiguities of part of speech. The word make keeps its part of speech but not its meaning: it can mean create or cook, which is a lexical ambiguity of sense, and choosing the right one is Word sense disambiguation. The cause and transform readings are not two further senses of make. They come from the frame the verb takes: the sentence as a whole can be built in three shapes, make with a single object (her duck as one noun phrase), make with two objects (her and duck, one turned into the other), or make with an object and a bare verb (her then duck as an action). That is syntactic ambiguity, a question of syntax rather than of any single word.

One level is still missing, and it only appears when the sentence is spoken. In speech the first word could have been eye and the second could have been maid. Jurafsky and Martin call this an even deeper kind of ambiguity, because it sits below the words themselves, at the level of phonetics. A speech recogniser must settle it before any of the other decisions can even begin. Toggle the cycler to "heard, not read" to see it.

This table is the sentence Jurafsky and Martin build their whole book on: most or all tasks in speech and language processing can be viewed as resolving ambiguity at one of these levels. Part-of-speech tagging decides whether duck is a noun or a verb, word sense disambiguation decides what make means, and probabilistic parsing decides whether her and duck group together. Every one of those tasks has its own chapter later in the course, and each one is answering a question this four-word sentence raises.

If the duck sentence felt contrived, here is one nobody would blink at: I saw the man with a telescope. Who has the telescope? Read it once and you will have decided without noticing. Read it again and the other answer is just as available.

The phrase with a telescope is a prepositional phrase, and a prepositional phrase has to attach to something. Attach it inside the noun phrase, [the man [with a telescope]], and the man has the telescope. Attach it to the verb phrase, [saw [the man] [with a telescope]], and the telescope is the instrument of seeing: I used it. This is prepositional phrase attachment, one of the two common kinds of syntactic ambiguity in English text (the other is coordination ambiguity, as in old men and women), and the point is that both parses are fully grammatical. The grammar licenses both; only context, plausibility or statistics can choose. A third reading hides in the first word: saw can also be the present tense of the verb to saw, so I am cutting the man with a telescope, a lexical ambiguity stacked on top of the syntactic one.

Jurafsky and Martin treat this under structural ambiguity in their parsing chapter: it occurs when the grammar can assign more than one parse to a sentence, and attachment ambiguity is one of the two common forms, the other being coordination ambiguity. Their own example is Groucho Marx's I shot an elephant in my pajamas, where in my pajamas can attach to the shooting or to the elephant. They call ambiguity the most serious problem faced by syntactic parsers, because a grammar big enough to cover real English assigns a naturally occurring sentence not two parses but many, most of them grammatical yet semantically unreasonable. Parsing is therefore never just recognising structure; it is choosing among structures.

Crash blossoms: ambiguity in the wild

Ambiguity is not a classroom invention, and the six headlines stamped "100% REAL" in the lecture prove it: every one really ran in a news outlet. Headlines drop articles, auxiliaries and the copula to save space, which strips away exactly the cues a reader uses to settle part of speech and attachment. The result is a headline that admits an unintended reading, and copy editors have a name for it: a Crash blossom.

The name comes from the first line on the slide. In August 2009 the site Japan Today ran the headline Violinist Linked to JAL Crash Blossoms about Diana Yukawa, whose father died in the 1985 Japan Airlines crash and whose career was flourishing. Editors on the Testy Copy Editors forum read it as a species called crash blossoms and, in the thread that followed, proposed "crash blossom" as the general term for a headline that leads the reader down the garden path. Ben Zimmer picked the story up on Language Log that month and then in his New York Times On Language column in January 2010, which is what made the word stick.

Look at the last column and you will see the same three kinds of ambiguity as the duck sentence, just without the helpful function words. Strikes, blossoms and shooting are part-of-speech flips; holds up, try and cut in half are sense flips; 7 foot doctors is a bracketing flip. Notice also that one choice forces others: once strikes is a verb, idle must be an adjective, and once it is a noun, idle must be a verb. Ambiguities are not independent, which is why parsers resolve them jointly rather than word by word.

Suppose ambiguity were solved. Would language understanding be easy? No, and there are six more reasons, each a different way real text refuses to behave like the tidy sentences of a grammar book. Take them one at a time, and for each one ask which NLP subproblem it defeats, because that subproblem is a research area with its own benchmarks.

Non-standard text

Guys plz d/l the lettr Ive written 2 Jeff Gaspin is perfectly readable to a human and almost useless to a model trained on edited prose. Five of its tokens are misspelt, abbreviated or numerals standing in for words. This is non-standard language, and it defeats normalisation: the step that is supposed to map surface forms to the vocabulary the model knows. For a KFUPM student the sharper version is diglossia. Farghaly and Shaalan describe Arabic as a language where Modern Standard Arabic is the formal written variety while everyday speech is Gulf, Egyptian or Levantine dialect. Text messages and social media carry that dialect into writing, and Darwish describes how it often arrives as Arabizi (Latin letters and digits standing in for Arabic sounds, as in 3ala for على), so a system trained on newswire MSA meets a different language on the phone.

Segmentation

The slide shows the New York-New Haven Railroad tokenized two ways. The naive split, on spaces alone, gives the | New | York-New | Haven | Railroad, gluing York to the wrong New. The right split, the | New York | - | New Haven | Railroad, needs to know that New York and New Haven are each one name. This is a Segmentation problem and it defeats Tokenization and named entity recognition together. Jurafsky and Martin note in their tokenization chapter that keeping a multiword expression such as New York as one token requires a multiword expression dictionary, so tokenization is tied to recognising names and to morphology. Arabic makes segmentation unavoidable rather than occasional: the preposition b (by, with) and the conjunction w (and) are clitics written attached to the following word, so وبالقلم is one orthographic word that a tokenizer must cut into w + b + al + qalam, four units, before anything else can run.

Idioms

Dark horse, get cold feet, lose face, throw in the towel. An Idiom is a multiword expression whose meaning is not built from its parts: no towel is thrown, no feet get cold. This defeats compositional semantics, the assumption that the meaning of a phrase is assembled from the meanings of its words, and it wrecks machine translation that translates word by word. Arabic has its own stock: على عيني is literally "on my eye" and means "gladly, of course".

Neologisms

Unfriend, Retweet, Malware, Webinar. Each of these entered everyday use, or in the case of unfriend returned to it with a new sense, only when a product or a threat made it necessary. A Neologism defeats any system with a closed vocabulary, which treats it as an out-of-vocabulary token and learns nothing. Vocabulary is open: new words arrive faster than lexicons can be updated. This is the motivation for the subword tokenization of lecture 2, where byte-pair encoding lets a model build unfriend from smaller, frequent pieces (ideally un plus friend) without ever having seen the whole word. Arabic coins verbs from loanwords the same way: speakers say سيّف, "to save" a file, forcing an English root into an Arabic verb pattern.

World knowledge

Mary and Sue are sisters. Mary and Sue are mothers. Same shape, same syntax, same plural predicate. Yet the first means sisters of each other and the second cannot mean mothers of each other. Nothing in the sentence tells you that; you know it because you know how sisterhood and motherhood work. This is world knowledge, and the subproblem it defeats is commonsense reasoning. It is the same in every language, which is why there is no Arabic column to add.

Tricky entity names

Where is A Bug's Life playing, Let It Be was recorded, a mutation on the for gene. A Named entity is supposed to be a proper name, but these names are made of ordinary words: an article, a pronoun, a preposition. Named entity recognition has to decide that for is a gene and Let It Be is a record without any lexical clue. In English the capital letters help a little. Arabic has no capital letters at all, so every person, place and organisation name looks like a common word. Farghaly and Shaalan list the missing capital letters among the central challenges for Arabic named entity recognition.

The lecture closes the list with "But that's what makes it fun!" and for a PhD student that line is literal. Each card is a research community: text normalisation, tokenization and segmentation, multiword expressions, open-vocabulary modelling, commonsense reasoning and named entity recognition all have their own shared tasks and leaderboards, and Arabic versions of most of them are still open.

Go back to Mary and Sue are mothers and ask what a system would need to read it correctly. It needs the syntax of a plural predicate, which is knowledge of language. It needs to know that motherhood is not reciprocal between two women, which is knowledge about the world. And it needs some procedure that brings the two together on this sentence, a way to combine knowledge sources. Those are exactly the three tools the lecture says progress requires.

The third tool is the interesting one, because it is where the four approaches of slide 15 come from. Each approach is one answer to how knowledge sources get combined. Rule-based NLP encodes linguistic knowledge by hand and combines it by the order in which rules fire. Machine learning based NLP learns the linguistic knowledge from annotated data and lets a classifier weigh it. End-to-end deep learning learns everything, including whatever world knowledge the text happens to contain, from raw input inside one network. A hybrid approach mixes them, typically rules where knowledge is crisp and models where it is statistical.

The second half of slide 24 says where the models, algorithms and theories come from: computer science, mathematics and linguistics. Slide 5 drew NLP where artificial intelligence, computer science and linguistics meet; slide 24 keeps computer science and linguistics but puts mathematics where artificial intelligence was. Jurafsky and Martin open their overview of the field with the same sentence, that the models are all drawn from the standard toolkits of computer science, mathematics and linguistics. Computer science supplies state space search, classifiers and dynamic programming. Mathematics supplies probability and linear algebra. Linguistics supplies the levels of part 3 and the categories, such as noun phrase and prepositional phrase, that the algorithms operate on.

The textbook behind the slides

The lecture credits its material mainly to Jurafsky and Martin, Speech and Language Processing. That is right; the duck sentence, the toolkit sentence and the whole shape of this lecture come from its first chapter. The edition details on the slide are not right.