Chapter 01

Foundations of NLP & Text Preprocessing

What natural language is, why it is hard to process, and how to turn raw bytes into the tokens a model can read — tokenisation, normalisation, stemming vs lemmatisation, and the regular expressions that still do the surgical work.

Reading: ~45 min Interactive: 7 widgets Source: Polimi NLP 2024/25 — Lecture 1 · Jurafsky & Martin, Speech and Language Processing (3rd ed.) Ch. 2

01 · Definition

What is Natural Language Processing?

Natural language is compositional, ambiguous, and unbounded. Every preprocessing decision you make is a trade-off between throwing information away and keeping the input tractable.

NLP is the computational analysis, interpretation, and production of natural language in written or spoken form. Strip away the marketing and every NLP system is a function: it takes one piece of language as input and returns another piece of language — or a label, a number, a score, a tree. The differences between systems are which input, which output, and how the mapping is learned.

Three vocabularies show up across the syllabus — keep them straight from day one:

  • NLU — Natural Language Understanding: text → labels, structure, vectors. Classification, NER, parsing, sentiment.
  • NLG — Natural Language Generation: structure or text → text. Summarisation, translation, dialogue.
  • NLP — the umbrella that contains both, plus the engineering around them.
why

Why this field exists

Virtually all of human knowledge lives in text — books, papers, emails, web pages, medical records, legal contracts. Before NLP, every one of those documents required a human reader. NLP is the long project of giving computers the same access.

Hands-on

Identify the NLP task

Pick an example I/O pair, then click the task you think it is. Look at the shape of the output — a label, a span, another sentence — that alone usually pins the task.

"This phone is amazing" → POSITIVE
Q

Name the task and a core difficulty

Given a system that maps a 1000-word document to a one-paragraph headline, name the NLP task and one difficulty. Graders want summarisation and the extractive vs abstractive distinction (any headline shorter than the source title is almost always abstractive), plus at least one of information selection, faithfulness / hallucination, or length control. Trap: calling it “compression”, or confusing it with translation because both shorten text.

02 · Properties

What makes human language special?

Animal communication is largely signalling: one signal, one meaning, no novelty. Human language is fundamentally different. Four properties matter for the exam.

1 · Compositionality

Meaning of the whole is a function of the parts. Combine 100 nouns, 100 verbs and 100 objects and you get 1003=106100^3 = 10^6 distinct sentences. No finite signal dictionary can capture that.

2 · Displacement

Language can refer to things not here, now, or even real: Caesar, next Tuesday, the square root of two, a unicorn in your fridge. Animal signals are anchored to the immediate situation.

3 · Productivity

A speaker produces — and a listener understands — sentences neither has heard before. “The purple bicycle sneezed eloquently” is grammatical, odd, and instantly parseable.

4 · Ambiguity

Almost every sentence has more than one reading at some level — phonetic, lexical, syntactic, semantic, pragmatic. Humans use context to pick one. The biggest engineering problem in NLP.

key

The dolphin contrast

Dolphins have an estimated ~125 distinct whistles. Each signals something — danger, food, identity — but you cannot combine two whistles to invent a new meaning. Human language is the opposite: a small set of rules generating unbounded sentences.

Hands-on

Spot the ambiguity

Pick a sentence, then choose the ambiguity type you think dominates. Lexical = a word has two meanings; syntactic = the structure parses two ways; semantic = fixed parse, unclear meaning; pragmatic = meaning depends on context.

“I saw her duck.”

Q

Three distinguishing properties, one example each

Pick from compositionality, displacement, productivity, ambiguity. Each example must be one concrete sentence, not a description. Traps: “vocabulary size” is not a property (dolphins have vocabulary too); “grammar” alone is too vague — graders want compositional grammar.

03 · Difficulty

Why processing language is hard

Six recurring difficulties show up in every NLP system, in roughly increasing order of severity:

  1. Ambiguity at every level. Phonetic (“ice cream” / “I scream”), lexical (“bank”), syntactic (“I saw her duck”), semantic (“every man loves a woman”), pragmatic (“can you pass the salt?”).
  2. Variation. The same meaning expressed a thousand ways: buy / purchase / pick up / get.
  3. Sparsity. Words follow a Zipfian distribution — about half of all word types in a corpus appear exactly once. A model that must see a word to learn it has a problem.
  4. Productivity. Test data contains words and structures the training data never saw.
  5. Context dependence. Meaning depends on speaker, listener, time, place, prior discourse, world knowledge.
  6. Encoding the discrete. Text is a sequence of categorical symbols, but most modern ML runs on continuous vectors. Bridging the two (Ch. 4–6) is most of the course.
!

The classic confusion

Ambiguity is one input, many meanings. Variation is the mirror — one meaning, many inputs. The exam asks about both and expects the right term.

Hands-on

Zipf’s law — the sparsity problem, visualised

Plot frequency vs rank. A handful of words dominate; a long tail of types appears once or twice. That tail is why models need smoothing and sub-word units.

thefoxdogquickjumpslazyisbrownoverbarks

29 tokens · 12 types · 5 hapax (1×) · 42% of types appear once

TakeawayWord frequencies are heavy-headed and long-tailed. Roughly half of the types in real text occur exactly once — any model that must see a word to learn it has a problem.
Q

Lexical vs syntactic ambiguity for a parser

Give one lexical and one syntactic example sentence, plus the mechanism: lexical ambiguity is resolved by word-sense disambiguation (classification over senses); syntactic ambiguity by parse selection (choosing one tree out of many).

04 · The pipeline

The text preprocessing pipeline

Before any model sees your text, it goes through a sequence of irreversible decisions. Every step throws information away in exchange for a more tractable input. The canonical order:

  1. Decode. Bytes → Unicode characters. Pick UTF-8 unless you have a reason not to.
  2. Normalise. Lower-case, strip diacritics, NFC vs NFKC, collapse whitespace, strip HTML.
  3. Tokenise. Character stream → list of tokens.
  4. Filter. Optionally drop stopwords, punctuation, very rare or very frequent tokens.
  5. Morphology. Optionally stem or lemmatise.
  6. Vectorise. Tokens → vectors (BoW, embeddings, subword IDs).
Hands-on

Preprocessing pipeline simulator

Toggle each step and watch the token list change. The toolbar order matches the order the pipeline runs — dropping stopwords before lower-casing would miss “The”.

thecatsarerunningquicklythroughmilano'spiazzas—n.l.p.isn'teasy,isit?:)

Pipeline: 23 → 15 tokens kept · 65% retention

TakeawayEvery step is permanent with respect to the downstream model. Choose what to throw away based on the task, not by reflex.
!

Every step is destructive

You cannot recover “Milano’s” from “milano”, or “isn’t” from “isn t” / “is not”. Preprocessing decisions are permanent with respect to the downstream model.

Q

Stopwords and case for three tasks

For (a) sentiment, (b) author identification, (c) information retrieval — decide whether to remove stopwords and lower-case:

  • Sentiment — keep stopwords (“not”, “no”, “never” flip sentiment); lower-casing is fine.
  • Author ID — keep stopwords (a function-word histogram is the strongest authorship signal); do not lower-case (capitalisation is a stylistic fingerprint).
  • IR — remove stopwords (they bloat the index, rarely change the topic); lower-case is standard.

05 · Tokenization

Tokenization — three regimes

Tokenisation converts a character stream into a list of discrete units. Every model in this course operates on tokens, never raw text. Three families dominate.

Word tokens

Split on whitespace and punctuation. Easy, interpretable. But a huge vocabulary (English Wikipedia ≈ 1.3 M types) and zero handling of the unseen — tokenize("antidisestablishmentarianism") → [UNK].

Character tokens

Split on every Unicode code-point. Tiny vocabulary (≈ 300), never an unknown token, but sequences are 4–6× longer and the model must learn what a “word” is from scratch.

Sub-word tokens

BPE, WordPiece, SentencePiece — the modern compromise every transformer uses. Vocabulary ≈ 30–50 k. Frequent words stay whole; rare words decompose into pieces.

Hands-on

Tokenizer playground — word vs char vs sub-word

Try a sentence with rare or compound words. At the word level “antidisestablishmentarianism” is one token; at the character level it is 31. The sub-word BPE finds a sensible middle by greedily merging the most frequent character pairs.

TheantidisestablishmentarianismresearchersfromMilanostudiedtokenization.

8 tokens · 8 unique · avg 9.8 chars/token

TakeawaySub-word tokenisation keeps a small fixed vocabulary while never emitting [UNK]: frequent words stay whole, rare words decompose into known pieces.
Formal Byte-Pair Encoding (BPE) — the merge algorithm

BPE is a greedy, frequency-based vocabulary builder:

  1. Initialise the vocabulary V0\mathcal{V}_0 with every character that appears in the corpus.
  2. Represent every word as a sequence of those characters, ending in a boundary symbol.
  3. At step kk, find the adjacent pair (a,b)(a,b) with the highest co-occurrence count across the corpus.
  4. Add the merged symbol abab to Vk\mathcal{V}_k and rewrite every (a,b)(a,b) as abab.
  5. Repeat until ∣Vk∣|\mathcal{V}_k| reaches the target size (typically 30–50 k).
Vk+1  =  Vk∪{ arg⁡max⁡(a,b)count⁡(ab) }\mathcal{V}_{k+1} \;=\; \mathcal{V}_k \cup \bigl\{\, \arg\max_{(a,b)} \operatorname{count}(ab) \,\bigr\}

Common words become single tokens; rare words decompose into their most-merged pieces. At inference the same merges run in learned order, so tokenisation is deterministic.

Q

Three reasons transformers use sub-words

  • No [UNK] — any unseen string still decomposes into known sub-words.
  • Fixed, small vocabulary — keeps the embedding matrix and softmax tractable (30 k rows, not 1 M).
  • Morphological sharing — play, playing, played share the play piece, so generalisation comes free.
  • (Bonus) Language-agnostic — the same algorithm trains on any script.

06 · Normalisation

Normalisation: stemming vs lemmatisation

Both reduce surface forms to a base form. The difference is whether they care about what the word means.

  • Stemming chops suffixes with rule-based heuristics. Fast, language-specific (Porter, Snowball, Lancaster), and frequently produces non-words: "studies" → "studi", "running" → "run", "better" → "better" (irregular — rules can’t help).
  • Lemmatisation looks up the canonical dictionary form (the lemma) via morphological analysis. It needs POS to be accurate: "studies" → "study", "better" → "good". Slower, but the output is always a real word.
Hands-on

Stem vs lemma, side by side

Type words (space-separated). Try better, flies, organization — stemmers handle regular suffixes but break on irregulars and homographs, where the dictionary-based lemmatiser still gets the real base form.

SurfaceStem (heuristic)Lemma (dictionary)
studiesstudistudy
studyingstudystudy
studiedstudistudy
betterbettergood
catscatcat
runningrunnrun
fliesflifly
organizationorganorganization
TakeawayStemming is faster and cruder; lemmatisation is slower but always returns a real word. Neither is “more accurate” in the abstract — pick by task.
Q

When to choose which

  • Stemming — large-scale IR where speed dominates; non-words are fine because the query goes through the same stemmer.
  • Lemmatisation — anything read by a human, or that needs morphological correctness.
  • Trap. “Stemming is more accurate.” It isn’t — it is faster and cruder.

07 · Tool

Regular expressions — the workhorse

Before neural networks, before BoW, there were regular expressions — still the right tool for surgical text matching. Exam regex problems are almost always: write a pattern, read a pattern, identify a bug, or compute what a pattern matches. The building blocks to know cold:

  • . any character except newline · \d \w \s digit, word-char, whitespace (uppercase = negation)
  • [abc] [^abc] [a-z] character classes · ? * + {m,n} quantifiers
  • ^ $ anchors · (…) capture · (?:…) non-capturing · \1 back-reference
  • (?=…) (?!…) look-ahead · | alternation
Hands-on

Regex tester

The preset matches a capitalised word. Try \b\d{4}\b for 4-digit years, or \b[A-Z][A-Z]+(?:-[0-9])?\b for tech acronyms like BERT, GPT-4.

Professor Maria Rossi taught NLP at Politecnico di Milano in 2024. She published 3 papers about BERT and GPT-4 with her PhD students.

6 matches

Q

Italian postal codes (5 digits)

Answer: \b\d{5}\b. Trap: forgetting the word boundaries — without \b the pattern matches the first five digits of any longer number. [0-9]{5} is equivalent unless Unicode digits matter.

Worked example Worked exam problem — tokens, types, and TTR

Take “The cats sat on a mat; the cat ran.” Apply: lowercase → drop punctuation → remove stop words {the, a, on} → stem plurals (drop a trailing “s”). How many tokens and distinct types remain, and what is the type–token ratio (TTR)?

  1. Lowercase + drop punctuation → the cats sat on a mat the cat ran (9 tokens).
  2. Remove stop words {the, a, on} → cats sat mat cat ran (5 tokens).
  3. Stem trailing “s” → cat sat mat cat ran.
  4. Tokens = 5; distinct types = {cat, sat, mat, ran} = 4.
  5. TTR = types / tokens = 4 / 5 = 0.8.

Answer: 5 tokens, 4 types, TTR = 0.8. “cat” appears twice (once from stemming “cats”), so types < tokens.

08 · Self-check

Three questions before you move on

A system maps "Caesar crossed the Rubicon in 49 BC" to [Caesar]PER [Rubicon]LOC [49 BC]DATE. What NLP task is this?

You're building a sentiment classifier. A colleague suggests removing stopwords to reduce noise. What's the strongest objection?

Which is the strongest reason modern transformers use sub-word tokenisation?

09 · Recap

One-screen summary

Chapter 01 — load-bearing ideas

  1. Human language is compositional — finite rules generate unbounded sentences. That is why no signal-dictionary approach works.
  2. Ambiguity is one input → many meanings; variation is one meaning → many inputs. Use the right term.
  3. Every preprocessing step is destructive. Choose what to throw away by the downstream task, not by reflex.
  4. Tokenisation has three regimes — word (huge vocab, [UNK]), character (tiny vocab, long sequences), sub-word/BPE (the modern compromise).
  5. BPE merge rule: Vk+1=Vk∪{arg⁡max⁡(a,b)count⁡(ab)}\mathcal{V}_{k+1} = \mathcal{V}_k \cup \{\arg\max_{(a,b)} \operatorname{count}(ab)\}.
  6. Stemming vs lemmatisation: crude rule-based suffix stripping vs dictionary + morphology. Stemming is faster, not more accurate.
  7. Zipf’s law — about half of all types occur once (hapax), which is why we need smoothing (Ch. 4) and sub-words.
  8. Regular expressions remain the workhorse for span-level extraction.

10 · Exam · past papers

Past-paper questions

A curated bank of real Polimi past-paper items for this chapter. Click an option for instant feedback; “Reveal all” exposes every answer.

Answered 0 / 12 · 0 correct

  1. Q143Why are Natural Language Processing (NLP) techniques important?

  2. Q144Which of the following tasks would NOT usually be considered a Natural Language Processing task?

  3. Q145Sentences in natural language can often be ambiguous (e.g. "I made her duck"), because:

  4. Q146The sentence "Colourless green ideas sleep furiously." is an example of a phrase that:

  5. Q117Which of the following is NOT a text pre-processing step in an NLP application?

  6. Q120What is the difference between stemming and lemmatization?

  7. Q123What are ASCII and UTF-8, and what is the difference between them?

  8. Q121What effect does Byte-Pair Encoding (BPE) achieve in Transformer models?

  9. Q149Which one of the following is NOT a valid description of a Regular Expression component?

  10. Q147Which regular expression would match a student email of the form "first.lastname@mail.polimi.it"?

  11. Q148Which string would the regex [A-Z]{6}\d{2}[A-Z]\d{2}[A-Z]\d{3}[A-Z] match?

  12. Q127Which of the following would NOT be considered a limitation of regular-expression based text extraction?