ICS 582Lecture 01Reference

Reference sheet

Introduction to natural language processing compressed onto one page: the definitions, formulas and numbers to have in your head before a quiz or exam.

Definition, goals and names

Define NLP by its goal, not its tool. The definition has survived two complete changes of technique. Part 01: What is NLP

Slide 4, verbatim structure

NLP (slide 4): A branch of artificial intelligence concerned with interactions between computers and human language.
Three goals, in slide order: Enabling human-machine communication; improving human-human communication; or simply doing useful processing of text or speech.
Three other names, in slide order: Computational linguistics (linguistics side, the ACL); speech and language processing (speech is in scope, the textbook title); human language technology (engineering side, systems that ship).
Newest label: Language modeling, which the 3rd edition calls the most recent name of the field, not a replacement for it.

Name	Facet	What it stresses	Anchor
Computational linguistics	Linguistics	Language as object of study, computation as method	ACL, founded 1962 as AMTCL, renamed 1968
Speech and language processing	Speech	Spoken language belongs to the field	Title of Jurafsky and Martin
Human language technology	Engineering	Deployable systems, not theory	Search engines, assistants, filters

Three names, three facets

The Venn and the AI subfields

Slide 5: NLP at the intersection of linguistics, computer science and AI, with an ellipsis for mathematics. Slide 6: five AI subfields, deep learning indented under machine learning. Part 01: What is NLP

Discipline	Contribution	Example
Linguistics	The object: levels of description, grammar, the idea of ambiguity	What counts as a word; five readings of a sentence
Computer science	Algorithms and data structures: search, dynamic programming, classifiers	Viterbi, a vocabulary hash table, a spam classifier
Artificial intelligence	Learning from data, representing knowledge, choosing the most probable reading	Weights trained from reported mail
The ellipsis	Mathematics (probability and statistics), plus signal processing and psychology	Linear algebra, vector spaces, acoustics

What each parent discipline gives NLP

Subfield	Studies	Touches NLP through
Natural language processing	Human language	The subject of this course
Knowledge representation and deduction	Storing facts and drawing conclusions	Question answering over a knowledge graph (Taj Mahal: monument or musician)
Machine learning (deep learning inside it)	Learning behaviour from data	Supplies almost every modern NLP model
Computer vision	Images and video	Image captioning, OCR
Robotics	Perceiving and acting physically	Following natural language instructions (SayCan)

Five AI subfields on slide 6 and where each touches NLP

Company	Product	Goal served
Google	Search (BERT), Translate	Human-machine, human-human
Apple	Siri	Human-machine
Microsoft	Translator	Human-human
Twitter (now X)	Feed ranking and moderation	Useful processing
Amazon	Alexa	Human-machine
Facebook (Meta)	NLLB translation	Human-human
Grammarly	Writing assistant	Useful processing

Slide 2 logos sorted by goal

Machine translation

Two modes, sorted by who owns the final text. Camera and conversation translation wrap MT inside OCR, speech recognition and speech synthesis. Part 02: Applications

Mode	Who produces the final text	Typical use	Slide example
Fully automatic	The system	Information access, gisting	Google Translate rendering the NLP definition in Arabic
Assisted, post-editing	The human, fixing a machine draft	Localisation, documentation	Not pictured; the common industrial workflow
Assisted, interactive prediction	The human, accepting or amending predicted suffixes	Professional news, legal, medical text	The ranked list under the typed word lebanese

Modes of machine translation (slide 7)

Interactive CAT (Barrachina et al., 2009): the human validates a prefix, the system proposes the best or n-best suffix. The list under lebanese is an n-best set; suffered and exposed are two readings of the Arabic verb تعرض.

Product	Chain	Failure it inherits
Camera translation	OCR, then MT, then render the overlay	A wrong letter becomes a wrong word
Conversation mode	Speech recognition, then MT, then speech synthesis	A misheard word is translated faithfully
AI Overview	Retrieve, then prompt, then generate, then cite	Fluent text that is not faithful to the sources
Aspect sentiment	Aspect extraction, then polarity classification	Right polarity on the wrong target

Products that are pipelines, and where each one breaks

Slide 8 counts (historical)

Google Translate, typing: 103 languages
Google Translate, offline: 52 languages
Google Translate, instant camera: 30 languages
Google Translate, camera photos: 37 languages
Google Translate, conversation: 32 languages
Skype Translator, voice: 7 languages
Skype Translator, chat: more than 50 languages
Today: Google added 110 languages on 27 June 2024 (about 243 total, help pages say over 200). Skype retired 5 May 2025.

Question answering: extract or generate

Slide 9 is a knowledge graph card. Slide 10 is retrieval-augmented generation on the same query, several years apart. Part 02: Applications

How the answer box answers 'how heavy is our planet'

1. Word sense disambiguation: "heavy" is read as mass, not the sense in heavy rain or heavy traffic.
2. Entity resolution: "our planet" is mapped to the knowledge graph node Earth (things, not strings).
3. Fact retrieval: (Earth, mass) returns 5.972 × 10^24 kg, a value information extraction once pulled from text.

\hat{a} = \text{LLM}\big(\text{prompt}(q,\; \text{retrieve}(q, k))\big)

Retrieval-augmented generation: retrieve the top k passages, build a prompt, generate, cite

Property	Answer box (slide 9)	AI Overview (slide 10)
Output	One field, rendered as a card	A paragraph with headings and citations
Source	A knowledge graph entry	Retrieved pages fed to an LLM
Core steps	Sense disambiguation, entity resolution, lookup	Retrieval, prompt construction, generation
Provenance	Implicit, the graph itself	Explicit citation chips
Main failure	A stale or missing fact	Fluent but unfaithful text (hallucination)
Cost per query	A lookup	A large model inference

Answer box versus AI Overview

Planet	Slide value	Earth masses	NASA value
Earth	5.972 × 10^24 kg	1	5.9722 × 10^24 kg
Mars	6.39 × 10^23 kg	0.107	6.4169 × 10^23 kg
Venus	4.867 × 10^24 kg	0.815	4.8673 × 10^24 kg
Jupiter	1.898 × 10^27 kg	317.8	1.89813 × 10^27 kg

Slide 9 masses checked against NASA

Ratios from the slide's own numbers: 6.39 / 59.72 = 0.107, 4.867 / 5.972 = 0.815, 1898 / 5.972 = 317.8. A hallucination is a response not faithful to the facts of the world; fluency is a property of the generator, faithfulness of the grounding.

Spelling: non-word versus real-word errors

A dictionary catches the first kind. Only context catches the second. Part 02: Applications

	Non-word error	Real-word error
Example on slide 11	ofcourse	then for than
Underline in Word	Red (spelling)	Blue (grammar)
Detected by	Dictionary lookup, no context	Context: a language model or a grammar rule
Share of all spelling errors	The remainder	25 to 40 percent
Noisy channel term that decides	Channel model prefers a nearby common word	Language model P(w) in context does the work

Slide 11, the two underlines

\hat{w} = \arg\max_{w \in V} P(x \mid w)\, P(w)

Noisy channel: channel model (how likely this typo given w) times language model (how likely w here)

Candidates V are kept within Damerau-Levenshtein distance 1; most errors are a single-letter change.
For then versus than, P(x | w) is high either way, so P(w) in "bigger ___ that" decides.

Information extraction and sentiment

Template filling: slots are copied from the text or inferred from it. Temporal normalization anchors relative expressions to the document date. Part 02: Applications

Slot	Value	Copied or inferred
Event	Curriculum mtg	Copied from the subject line, abbreviated
Date	Jan-16-2012	Inferred: header date January 15, 2012 plus one day
Start	10:00am	Inferred: range split, morning assumed
End	11:30am	Inferred: range split, morning assumed
Where	Gates 159	Copied: a location named entity

The five slots on slide 12

\text{tomorrow} = \text{anchor} + 1\ \text{day} = 2012\text{-}01\text{-}15 + 1 = 2012\text{-}01\text{-}16

Relative date resolved against the email header

Sentence	Cue words	Polarity
nice and compact to carry!	nice, compact	Positive
small and light, unlike heavy, bulky professional cameras	small, light versus heavy, bulky	Positive
feels flimsy, is plastic and very light in weight	flimsy, plastic, delicate	Negative

Slide 13: three opinions on the aspect size and weight

Four ways to build NLP

One axis: how much of the knowledge of language a human writes versus how much the data supplies. Part 03: How NLP is done

Approach	Human writes	Data supplies	Strength	Weakness
Rule-based	Grammars, lexicons, regexes, finite-state machines	Nothing	Precise, inspectable, no training data	Brittle, every phenomenon needs a rule
Classical ML	Feature templates, choice of model	The weights	Robust, probabilistic	Needs labels and hand-designed features
End-to-end deep learning	Architecture and loss	Representations and weights	Highest accuracy, no feature engineering	Large data and compute, hard to inspect
Hybrid	Normalisation rules, constraints, checks	The learned core	Practical, safe, works when data is scarce	Two systems to maintain

The four approaches on slide 15

Dates to know

7 January 1954: Georgetown-IBM demonstration: 250 words, six grammar rules.
1966: ELIZA: a cascade of regex substitutions (rule-based).
1965 to early 1990s: Symbolic era (Jurafsky and Martin, Figure 1.6).
1975 to 1985: Jelinek's IBM speech group starts the statistical turn.
Late 1980s to 2017: Empiricist era: naive Bayes, HMM, CRF (2001).
2014, 2017, 2019: seq2seq, the Transformer, prompting. GPT-2 tokenizer: regex pre-tokenizer plus learned BPE merges.

The text pipeline

Three cuts, each a decision that a rule or a model makes and can get wrong. Part 03: How NLP is done

Cut	Step	Where it goes wrong
Paragraphs to sentences	Sentence boundary disambiguation	The period is ambiguous: Dr., 3.14, or Inc. ending a sentence (both at once)
Sentences to words	Tokenization	Clitics ('s, n't, Arabic b and w), hyphens, numbers, no spaces in Chinese, Japanese, Thai
Words to morphology	Stemming or lemmatization	Porter: experiments to experi. Lemmatizer: are to be

Slide 16 pipeline

Worked sentence, Penn Treebank convention: "Dr. Ahmad's students are running experiments." gives 8 tokens (Dr. / Ahmad / 's / students / are / running / experiments / .), 2 Porter stems that are not words (ar, experi) and 1 lemma no suffix rule reaches (be).

	Stemming	Lemmatization
Method	Chops suffixes by rule	Looks up the dictionary form with a vocabulary and morphological analysis
Output	May be a non-word	Always a real word, the lemma
Needs	Only the rules	A lexicon, often the part of speech
Example	experiments to experi, are to ar	experiments to experiment, are to be
Over-stemming	university and universal both to univers	Not applicable
Use	Search indexing	Anything shown to people or fed to a parser

Stemming versus lemmatization

Levels of linguistic knowledge

Order from sound to discourse. Speech enters through phonetics and phonology, text through orthography, and both meet at morphology. Part 03: How NLP is done

Level	Unit	Input	Example task
Phonetics	Phone (speech sound)	Speech only	Speech recognition front end
Phonology	Phoneme	Speech only	Pronunciation modelling
Orthography	Character, code point	Text only	Unicode handling, script normalisation
Morphology	Morpheme	Both	Stemming, lemmatization, subword tokenization
Lexical	Lexeme and its senses	Both	Word sense disambiguation (heavy on slide 9)
Syntax	Phrase, sentence	Both	Parsing, PP attachment (slide 21)
Semantics	Proposition	Both	Semantic role labelling, question answering
Pragmatics	Utterance in context	Both	Resolving tomorrow (slide 12), dialogue
Discourse	Multi-sentence text	Both	Coreference resolution

Slide 17, complete list

Ambiguity

Most or all NLP tasks resolve ambiguity at one of the levels above. The marks are in the level column, not the glosses. Part 04: Why NLP is hard

Reading	Gloss	Level of ambiguity
1	I cooked waterfowl for her	Part of speech and word sense
2	I cooked waterfowl belonging to her	Syntactic, and part of speech of her
3	I created the plaster duck she owns	Word sense of make
4	I caused her to quickly lower her head	Part of speech of duck and syntactic
5	I turned her into a duck	Syntactic (ditransitive make)
Bonus, speech only	eye / maid instead of I / made	Phonetic

Five readings of 'I made her duck' (Jurafsky and Martin, 2000 and 2009, chapter 1)

Bracketing	Attachment	Meaning
[saw [the man [with a telescope]]]	Inside the noun phrase	The man has the telescope
[saw [the man] [with a telescope]]	To the verb phrase	I used the telescope to see him
saw as the cutting verb	Lexical, stacked on top	I am sawing the man

'I saw the man with a telescope': PP attachment (slide 21)

Both parses are grammatical, so grammar alone cannot choose. The two common structural ambiguities in English are attachment and coordination (old men and women). A crash blossom is a real headline whose compressed syntax admits a garden-path reading; named after Violinist Linked to JAL Crash Blossoms (Japan Today, August 2009), popularised by Ben Zimmer in January 2010.

Headline	Garden-path reading	Ambiguous word and type
Violinist Linked to JAL Crash Blossoms	A species called crash blossoms	blossoms: verb or noun; compound segmentation
Teacher Strikes Idle Kids	A teacher hits lazy children	strikes: noun or verb, which flips idle
Red Tape Holds Up New Bridges	Tape robs or supports the bridges	holds up: phrasal verb sense
Hospitals Are Sued by 7 Foot Doctors	Doctors seven feet tall	[7 [foot doctors]] versus [[7 foot] doctors]
Juvenile Court to Try Shooting Defendant	The court will attempt to shoot him	try: sense; shooting: part of speech
Local High School Dropouts Cut in Half	Students were bisected	cut in half: literal or figurative; world knowledge

Slide 22 headlines: garden path and the ambiguous word

Six more reasons, and the tools for progress

Beyond ambiguity, six cards on slide 23, each defeating a named subproblem. Slide 24 lists three tools and three disciplines. Part 04: Why NLP is hard

Difficulty	Slide example	What it defeats	Arabic counterpart
Non-standard text	Guys plz d/l the lettr Ive written 2 Jeff Gaspin	Normalisation	Diglossia: MSA versus dialect, Arabizi (3ala)
Segmentation	the New York-New Haven Railroad	Tokenization, named entity recognition	Clitics: w + b + al + qalam as one word
Idioms	dark horse, get cold feet, throw in the towel	Compositional semantics, translation	on my eye, meaning gladly
Neologisms	unfriend, Retweet, Malware, Webinar	Closed vocabularies (OOV words)	Loanword verbs such as to save a file
World knowledge	Mary and Sue are sisters / are mothers	Commonsense reasoning	Same in every language
Tricky entity names	A Bug's Life, Let It Be, the for gene	Named entity recognition	No capital letters, every name looks common

Slide 23 with the Arabic counterpart

Three tools: knowledge of language, knowledge about the world, a way to combine knowledge sources.
Three disciplines: computer science (search, classifiers, dynamic programming), mathematics (probability, linear algebra), linguistics (levels and categories).
A bigger dictionary fixes neither idioms (non-compositional meaning) nor neologisms (open vocabulary). The fixes are structural: multiword units, and subword models.

Approach	Knowledge of language from	World knowledge from	Combined by
Rule-based	Hand-written grammars and lexicons	Hand-written facts and ontologies	Order of rule firing
Machine learning	Annotated corpora	Whatever the features encode	A classifier weighs features
End-to-end deep learning	Raw text	Absorbed implicitly from huge corpora	One network mixes everything
Hybrid	Rules plus learned components	Rules, knowledge bases, learned parts	A pipeline or a vote

The four approaches as four ways to combine the knowledge sources

Numbers worth memorising

Figures quoted across the four parts

Vocabulary by age 20: 30,000 to 100,000 words, about 7 to 10 a day, mostly from reading.
Real-word spelling errors: 25 to 40 percent of all spelling errors are valid words in the wrong place.
LLM hallucination, legal questions: 69 to 88 percent of the time, and models are poorly calibrated.
BERT in Search (2019): Helps one in 10 English searches.
NLLB: 200 languages.
Chinese word length: Roughly 1.5 to 1.9 characters; no orthographic word boundaries.
Earth mass in pounds: 5.972 × 10^24 kg × 2.20462 lb/kg ≈ 1.317 × 10^25 lb, the 13.1 septillion pounds of slide 10.

Slide errata

Answer with the corrected fact, and name the slide if a question depends on it. Part 04: Why NLP is hard

What the slides get wrong, or leave dated

Slide 1: Footer reads ICS472, the undergraduate twin. Same slides, same content for ICS 582.
Slide 2: Dated logos: the Twitter bird (X since 24 July 2023) and Facebook (now Meta). A snapshot, not an error.
Slide 6: Says knowledge representation and deduction. The standard phrase is knowledge representation and reasoning; deduction is one kind of reasoning.
Slide 8: Language counts are from an old app page, and Skype Translator was retired on 5 May 2025. Learn the categories, not the numbers.
Slide 9: Mars shows 6.39 × 10^23 kg; NASA lists 6.4169 × 10^23 kg. Google's stale fact, not the lecturer's; a live example of staleness.
Slide 12: Jan-16-2012 does not contradict the January 15 header. Tomorrow is anchor plus one day. No error.
Slide 13: The screenshot covers the middle of the second and third review bullets. Full sentences are in the PDF text layer.
Slide 16: {parsing, tokenization} sits on the sentences-to-words arrow. Tokenization does that alone; parsing builds structure over existing tokens. Also reads pragmatcs.
Slide 17: Pragmatcs again. The rings omit the lexical level and orthography; read the stack as the complete list and the rings as the speech-first view.
Slide 25: Prentice-Hall 2020 does not exist. Editions: 2000 and 2009 (ISBN 978-0-13-187321-6); the 3rd edition is a free online draft (19 August 2026) whose chapter 1 no longer contains the duck sentence.