NLP Study Notes (1): Text Processing and Statistical Methods - Bojin Li

These are my notes from COMP90042 (NLP) at the University of Melbourne. This article covers text preprocessing, BPE, N-grams and smoothing, text classification, POS tagging, HMMs and Viterbi.

1. Text preprocessing

1.1 Basic definitions

Term	Definition
Word	A string of characters with meaning and/or a grammatical function (a sequence of characters with a meaning and/or function)
Sentence	A unit of words arranged according to grammatical rules to express a complete thought, ending at a punctuation or structural boundary
Document	A continuous unit of text, such as a news article or an email, consisting of several sentences
Corpus	A collection of texts gathered at scale for training or evaluation (singular: corpus; plural: corpora)
Word token	A word instance at each occurrence in a text; "to be or not to be" has 6 tokens
Word type	A distinct word after deduplication; "to be or not to be" has 4 types
Lexicon	The set of all word types in a language or domain, together with their lexical entries

Remember: number of tokens ≥ number of types; corpus size is often described by $\vert V\vert$ (vocabulary size) and the total number of tokens.

1.2 Why preprocess text?

Language is compositional. Humans understand documents by breaking them into components; for computers to understand language, they need to perform a similar decomposition.

Preprocessing gradually converts raw strings into representations suited to the task. Here is a schematic pipeline for traditional text processing:

TEXT

"<p> Hi there. I'm TARS. </p>"
  → Remove formatting  "Hi there. I'm TARS."
  → Segment sentences  ["Hi there.", "I'm TARS."]
  → Tokenise           [["Hi","there","."], ["I","'m","TARS","."]]
  → Normalise          [["hi","there","."], ["i","be","tars","."]]
  → Remove stopwords   [["hi","tars","."]]        (example)

1.3 A five-step preprocessing pipeline

Choose these steps according to the task; not every model needs all of them. Language models generally need to retain punctuation, word forms and function words. Modern pretrained models should also use the same tokenizer used during training.

Figure 1-1 The five-step text preprocessing pipeline, showing the same sentence after each step.

Step	English term	Goal
1	Remove unwanted formatting	Remove HTML/XML tags, Markdown markup, extra whitespace and escape characters
2	Sentence segmentation	Split a document into sentences
3	Word tokenisation	Split sentences into tokens, including subword approaches such as BPE
4	Word normalisation	Standardise case, spelling and word forms (lemmatisation / stemming)
5	Stopword removal	Remove frequent function words that carry little information

Step 2: Sentence segmentation

Four approaches, from simple to more complex:

Punctuation-based splitting: split at . ! ?.
- Problem: abbreviations (Dr. Smith), decimals (3.14) and URLs (example.com) may be split incorrectly.
Regular-expression splitting: use pattern matching to handle common exceptions, for example (?<!\bDr)\.\s+, or require a capital letter after a full stop.
Dictionary-based methods: maintain a dictionary of abbreviations and exceptions (Mr., Dr., U.S.A., e.g.), and do not split when a match is found.
Machine learning (sequence labelling):
- Method: treat each candidate boundary, usually punctuation, as a binary classification decision: "Is this really a sentence boundary?" The task can also be framed as sequence labelling.
- Model: logistic regression / maximum entropy / CRF / BiLSTM-CRF / a small Transformer classifier.
- Features:
- - The punctuation mark itself (. vs ? vs !)
  - The preceding token and its form: abbreviation, number, length and capitalisation
  - Whether the following token starts with a capital letter or is a common sentence-initial word
  - Whether the punctuation is immediately followed by a closing quotation mark, bracket or similar symbol
  - Token n-gram features within a context window, and membership in an abbreviation dictionary

Step 3: Word tokenisation

English: first split on whitespace, then handle punctuation and contractions or abbreviations (for example, Penn Treebank rules: don't → do + n't, while retaining U.S. → U.S. as one token). The tricky question is what's a word? (is New York one word or two?)
Chinese: Chinese has no spaces between words, so word segmentation is needed. See MaxMatch (maximum matching).
Subwords: BPE and related methods; see Section 2.

Chinese MaxMatch (maximum matching)

Idea: given a dictionary, greedily select the longest matching string in the dictionary as a word, working from the left or the right.

Example:

TEXT

Dictionary: {去买新, 西兰花, 西兰花新}
Sentence: 去买新西兰花

Forward maximum matching (FMM, left to right, longest match first):
  Position 0: try "去买新" (length 3, in dictionary) → segment as 「去买新」
  Position 3: try "西兰花" (length 3, in dictionary) → segment as 「西兰花」
  Result: 去买新 / 西兰花

Key points and limitations:

FMM (forward maximum matching) and RMM (reverse maximum matching) may produce different results. In practice, both are often run and rules are used to resolve ambiguity.
A greedy strategy does not guarantee a global optimum: ambiguous strings, such as "新西兰/花" versus "新/西兰花", can be segmented incorrectly.
Out-of-vocabulary (OOV) words cannot be handled by the dictionary alone; rules or statistical methods, such as HMM/CRF segmentation or jieba, are needed.
Advantages: very simple to implement, fast and requires no training data.

Step 4: Word normalisation

Goals:

Reduce vocabulary size (USA / U.S.A. / usa → one word), alleviating data sparsity;
Map different word forms to the same semantic unit so that the model can learn more reliable statistics from limited data;
Standardise case, full-width/half-width characters and spelling variants to support matching and retrieval.

Methods:

Case folding: The → the (information in proper names and abbreviations may be lost)
Spelling normalisation: colour → color, organise → organize
Number/date normalisation: 2024-01-01, 3.14 are both mapped to <NUM>
Morphological normalisation: Lemmatisation or Stemming (see below)

Removing morphology: two types of morphological change

Type	Inflectional morphology	Derivational morphology
Meaning	Different grammatical forms of the same word	New words formed from existing words
Examples	Plural nouns +s; third-person singular verbs +s, tense/aspect forms +ed/+ing; comparative adjectives +er, superlatives +est	Suffixes change word class: person → personally; prefixes change meaning: write → rewrite
Changes word class or meaning?	No	Yes

Lemmatisation versus stemming

Aspect	Lemmatisation	Stemming
Operation	Remove inflection to recover the lemma (dictionary form)	Remove suffixes, retaining a stem
Approach	Lexicon-based (dictionary + part of speech)	Rule-based (usually a set of affix-stripping rules)
Output	Meaningful, valid words	Possibly a stem that is not a valid word (studies → studi)
Speed	Slower (dictionary and POS lookup required)	Faster
Suitable tasks	Tasks needing valid word forms or sensitive to meaning, such as generation and tasks requiring readable output	Large-scale statistics, retrieval and classification, where consistent word forms are sufficient

Porter Stemmer

The most popular English stemming algorithm, introduced by Porter in 1980, driven by rules and conditions (the measure $m$ ).
Processing order: remove inflectional suffixes first (inflectional: -s, -es, -ed, -ing), then remove derivational suffixes (derivational: -ational, -fulness, -ness, -ment).
Characteristics: fast and dictionary-free. Limitations: over-stemming and under-stemming (university → univers, generously → gener).

Step 5: Stopword removal

Definition: words that occur frequently in a corpus but carry little topical information, such as the, a, of, is, and, to.
Goals:
- Reduce feature dimensionality, computation and storage costs;
- Remove noise so that the model focuses on content words;
- Usually beneficial for retrieval and topic classification tasks.
Selection methods:
1. Closed-class words / function words: determiners, prepositions, conjunctions, pronouns, auxiliaries and so on; these classes have limited membership and rarely acquire new words.
2. High-frequency words: count corpus frequencies and take the top- $k$ words (inspect manually to avoid removing negators such as not, no).
3. Existing lists: NLTK's stopwords and spaCy's stopword lists, which can be loaded by language.
Caution: do not apply stopword lists blindly in sentiment analysis, negation detection or parsing. For example, in not good, removing not changes its meaning. Whether to remove a word should depend on the task and validation results.

2. BPE subword segmentation

2.1 Motivation

The vocabulary-size dilemma: too large → an explosion of parameters and sparse data; too small → many OOV words.
Subwords offer a compromise: keep common words whole and split rare words into smaller, meaningful pieces.
- Colourless green ideas sleep furiously → [colour] [less] [green] [idea] [s] [sleep] [furious] [ly]

2.2 Algorithm (Byte-Pair Encoding)

Training (learning merge rules)

Split every word into a sequence of characters, append an end-of-word marker _ (or </w>) and count word frequencies.
Count the occurrences of all adjacent symbol pairs.
Take the most frequent pair and merge it into a new symbol, adding it to the vocabulary.
Repeat Steps 2–3 until reaching the specified number of merges $k$ (or vocabulary size).
Output: a list of merge rules in the order learned, plus the final subword vocabulary.

Encoding (tokenising new text)

Apply the rules in the learned merge order; pieces not covered by any rule remain as individual characters. Encoding is therefore deterministic and does not require recounting frequencies.

2.3 Worked example

Corpus (word endings marked with _):

Corpus	Frequency
o l d _	7
o l d e r _	3
f i n e s t _	9
l o w e s t _	4

Initial adjacent-pair frequencies

Pair	Count	Explanation
(e, s)	13	finest_ 9 + lowest_ 4
(s, t)	13	finest_ 9 + lowest_ 4
(t, _)	13	finest_ 9 + lowest_ 4
(o, l)	10	old_ 7 + older_ 3
(l, d)	10	old_ 7 + older_ 3
(f, i)	9	finest_ 9
(i, n)	9	finest_ 9
(n, e)	9	finest_ 9
(d, _)	7	old_ 7
(l, o)	4	lowest_ 4
(o, w)	4	lowest_ 4
(w, e)	4	lowest_ 4
(d, e)	3	older_ 3
(e, r)	3	older_ 3
(r, _)	3	older_ 3

Merge process (ties are resolved according to the implementation, commonly by first occurrence or lexicographic order)

Round	Merge	Frequency	Resulting corpus
1	e + s → es	13	o l d _(7) o l d e r _(3) f i n es t _(9) l o w es t _(4)
2	es + t → est	13	f i n est _(9) l o w est _(4)
3	est + _ → est_	13	f i n est_(9) l o w est_(4)
4	o + l → ol	10	ol d _(7) ol d e r _(3)
5	ol + d → old	10	old _(7) old e r _(3)
6	f + i → fi	9	fi n est_(9)
7	fi + n → fin	9	fin est_(9)
8	fin + est_ → finest_	9	finest_(9)
9	old + _ → old_	7	old_(7)

Each row shows only the words affected by that merge; all other words remain unchanged.

Final vocabulary (partial): o, l, d, e, r, f, i, n, s, t, w, _, es, est, est_, ol, old, fi, fin, finest_, old_, …

Figure 2-1 Merge operations learned by BPE from the corpus (r · → r·, l o → lo, lo w → low, e r· → er·). This uses the original example from the paper. Source: Sennrich et al., Neural Machine Translation of Rare Words with Subword Units, ACL 2016, Figure 1.

2.4 Key points and extensions

Hyperparameters: the number of merges / target vocabulary size controls the granularity trade-off between "words" and "characters".
Advantages: vocabulary size is controllable; frequent words can remain whole, while rare words split into subwords, reducing sparsity. Splitting remains possible as long as the required characters belong to the initial character inventory. Uncovered characters may still become unknown symbols; byte-level BPE or byte fallback can address this further.
Limitations: segmentation is frequency-based rather than semantic, so boundaries may be unnatural; different corpora or domains produce different segmentations.
Common approaches: BPE, WordPiece (used by BERT) and Unigram (used by T5). SentencePiece is a toolkit supporting algorithms such as BPE and Unigram. It can process raw text directly without requiring prior whitespace tokenisation. The toolkit's name is not synonymous with any one of its algorithms.

3. N-gram language models

3.1 Task

A language model (LM) assigns a word sequence a probability $P(w_1, w_2, \dots, w_m)$ .

Generating a sentence: sample or take the argmax from $P(w_t \mid w_{<t})$ step by step, generating one word at a time until <eos>.
Comparing sentences: compare the model's whole-sentence probabilities, log probabilities or perplexities. Under the same model and tokenisation rules, higher probability generally means a closer fit to the training-data distribution. Comparing different lengths also requires attention to length normalisation.

3.2 Applications

Spelling correction / input-method candidate ranking (I have a gu → guy? gun? gut?)
Speech recognition (distinguishing homophones)
Machine translation (selecting more fluent translations)
Fluency scoring for text generation and summarisation

3.3 What is an N-gram?

N-gram: a sequence of $n$ consecutive tokens.

$n$	Name	Example (the dog barks)
1	unigram	the / dog / barks
2	bigram	the dog / dog barks
3	trigram	the dog barks

An N-gram language model assumes that the word at position $t$ depends only on the preceding $n-1$ words.

3.4 Three concepts and assumptions behind N-grams

(a) From joint to conditional probabilities (chain rule)

Take I like apple as an example:

Joint probability: $P(\text{I like apple}) = P(\text{I}) \cdot P(\text{like} \mid \text{I}) \cdot P(\text{apple} \mid \text{I like})$
Chain rule (valid for any sequence length):

P(w_1, w_2, \dots, w_m) = \prod_{i=1}^{m} P(w_i \mid w_1, \dots, w_{i-1})

Problem: later conditional terms have longer histories, making them almost impossible to estimate directly from corpus counts because of sparsity. As sentence length grows, the number of parameters grows exponentially.
Conditional probability: $P(A\mid B) = \dfrac{P(A,B)}{P(B)}$ .

(b) Markov assumption

Depend only on the preceding $n-1$ words, rather than the entire history:

P(w_1, \dots, w_m) \approx \prod_{i=1}^{m} P(w_i \mid w_{i-n+1}, \dots, w_{i-1})

$n$	Model	Formula
1	unigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i)$
2	bigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-1})$
3	trigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-2}, w_{i-1})$

Estimate conditional probabilities using relative frequencies:

P(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}, \qquad P(w_i) = \frac{C(w_i)}{M}

Here $C(\cdot)$ denotes a count, and $M$ is the total number of tokens.

A hand-calculated example

Corpus (two sentences, with boundaries marked by <s> <eos>):

TEXT

<s> yes no no no no yes <eos>
<s> no no no yes yes no <eos>

Probability	Calculation	Result
$P(\text{yes} \mid \text{<s>})$	$1 / 2$	0.5
$P(\text{no} \mid \text{yes})$	$2 / 4$	0.5
$P(\text{no} \mid \text{no})$	$5 / 8$	0.625
$P(\text{yes} \mid \text{no})$	$2 / 8$	0.25
$P(\text{<eos>} \mid \text{yes})$	$1 / 4$	0.25
$P(\text{<eos>} \mid \text{no})$	$1 / 8$	0.125

In the corpus, yes occurs 4 times and no occurs 8 times. The possible successors to a given word must include the end-of-sentence marker. For example, the successor probabilities for no sum to $5/8+2/8+1/8=1$ .

3.5 Three problems with N-grams

Problem	What happens	Remedy
a) Long-distance dependencies	Considers only the preceding $n-1$ words, ignoring distant context (in "The trophy would not fit in the suitcase because it was too big", resolving it requires long-distance information)	Increase $n$ (at the cost of sparsity), use cache models, or use an RNN/Transformer
b) Very small probabilities	Multiplying dozens of values $<1$ can underflow to 0	Add log probabilities: $\log P = \sum \log P(w_i\mid\cdot)$ ; when computing perplexity, first calculate the mean negative log probability
c) Unseen N-grams (zero probability)	An N-gram absent from training has count 0 → the entire sentence receives probability 0	Smoothing; see Section 4

4. Smoothing

Goal: assign nonzero probabilities to unseen N-grams while keeping the distribution normalised, with probabilities summing to 1 (conservation of probability mass).

4.1 Add-one (Laplace) smoothing

Basic idea: pretend that every N-gram has occurred at least once; increment every count by $+1$ .

P_{\text{add1}}(w_i) = \frac{C(w_i) + 1}{M + \vert V\vert } \qquad\text{(unigram)}

P_{\text{add1}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1} w_i) + 1}{C(w_{i-1}) + \vert V\vert } \qquad\text{(bigram)}

Adding $\vert V\vert$ to the denominator keeps the probabilities summing to 1 (each of the $\vert V\vert$ candidates receives one extra count).

Problem: $+1$ is "too much" for low-frequency words and sparse corpora. It assigns a large amount of probability mass to unseen events, substantially reducing the probabilities of seen N-grams and introducing considerable distortion.

4.2 Add-k (Lidstone) smoothing

P_{\text{add-}k}(w_i \mid w_{i-2}, w_{i-1}) = \frac{C(w_{i-2}, w_{i-1}, w_i) + k}{C(w_{i-2}, w_{i-1}) + k\,\vert V\vert }

$k$ is a hyperparameter that must be chosen by the practitioner; $0<k<1$ usually works better than $k=1$ ; the best $k$ must be determined experimentally on a validation set.
Limitations:
1. You need to choose $k$ ; different values of $k$ can produce substantially different smoothing effects;
2. For the same context, all unseen N-grams receive the same probability. All zero counts are treated alike, without distinguishing "plausible but unseen" from "almost impossible";
3. The original ratios between counts are changed.

4.3 Absolute discounting

Idea: from each seen word, "borrow" a fixed count $d$ (for example $d=0.1$ ) and give the corresponding probability mass to unseen words.

P_{\text{abs}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) - d}{C(w_{i-1})}, \quad \text{if } C(w_{i-1},w_i) > 0

Example (context = alleged; 5 seen bigrams and 2 unseen bigrams)

Word	counts	Unsmoothed probability	Add-α (α=0.1) effective count	Add-α smoothed probability	Discounting (d=0.1) effective count	Discounted probability
impropriety	8	0.4	7.826	0.391	7.9	0.395
offense	5	0.25	4.928	0.246	4.9	0.245
damage	4	0.2	3.961	0.198	3.9	0.195
deficiencies	2	0.1	2.029	0.101	1.9	0.095
outbreak	1	0.05	1.063	0.053	0.9	0.045
infirmity	0	0	0.097	0.005	0.25	0.013
alleged	0	0	0.097	0.005	0.25	0.013
Total	20	1.0	20	1.0	20	1.0

After discounting, the seen counts become $8-0.1=7.9$ , $5-0.1=4.9$ …; the total "borrowed" effective count is $5\times0.1=0.5$ , corresponding to probability mass $0.5/20=0.025$ ;
The borrowed effective count of $0.5$ is split equally between the 2 unseen words: $0.5/2 = 0.25$ (effective count), which normalises to $0.25/20=0.0125\approx0.013$ .

4.4 Katz backoff

Idea: use discounted probabilities for seen events; for unseen events, redistribute the reserved mass according to a lower-order model.

P_{\text{katz}}(w \mid h) = \begin{cases} \dfrac{C^*(h,w)}{C(h)}, & \text{if } C(h,w) > 0 \\[2mm] \alpha(h)\,P_{\text{lower}}(w), & \text{otherwise} \end{cases}

Here $h=w_{i-1}$ is the context, and $C^*(h,w)$ is the discounted count. Katz typically uses Good–Turing-based count discounts rather than subtracting the same constant from every seen count. The backoff weight is:

\alpha(h)=\frac{1-\sum_{w:C(h,w)>0}C^*(h,w)/C(h)}{\sum_{w:C(h,w)=0}P_{\text{lower}}(w)}

The numerator is the probability mass left by the higher-order model. The denominator sums the lower-order probabilities of words unseen in the current context. Together, they keep the final distribution normalised.

A limitation of Katz backoff

Backoff uses only the raw probabilities of the lower-order model, which do not themselves capture how readily a word appears after a new context.
Illustrative example: I can not see without my reading ______
- Intuitive answer: glasses (reading glasses)
- Suppose reading glasses and reading Kong are both unseen, but King Kong is frequent in the corpus. Under a unigram model, $P(\text{Kong})$ may exceed $P(\text{glasses})$ , so Kong could be selected incorrectly even though it almost always follows King.
- Root cause: a high unigram probability does not imply suitability after reading. Kneser–Ney addresses this with continuation probability.

4.5 Kneser–Ney smoothing

Idea: allocate discounted mass according to versatility—the number of distinct words a word can follow—rather than raw counts.

Low versatility, high frequency: if Francisco follows only San, its continuation count is just 1, even when its total frequency is high. When completing an unseen context, high frequency alone should not give it a high probability.
High versatility: glasses can follow reading, sun, wine, beer, eye… → a high continuation count makes it more likely under backoff, addressing the error illustrated for Katz.

Formula: interpolated form

The following is the common interpolated Kneser–Ney formulation. The lower-order distribution contributes even when the higher-order count is nonzero: it is added to the discounted higher-order probability.

P_{KN}(w_i \mid w_{i-1}) = \frac{\max(C(w_{i-1},w_i)-D,0)}{C(w_{i-1})} +\lambda(w_{i-1})\,P_{\text{cont}}(w_i)

P_{\text{cont}}(w_i)= \frac{\vert\{u:C(u,w_i)>0\}\vert}{\vert\{(u,v):C(u,v)>0\}\vert},\qquad \lambda(h)=\frac{D\,\vert\{v:C(h,v)>0\}\vert}{C(h)}

Numerator: how many distinct preceding words have been followed by $w_i$ (that is, $w_i$ 's number of context types);
Denominator: the sum of context-type counts over all words, for normalisation;
$\lambda(h)$ : the total probability mass discounted in context $h$ ; when $0<D<1$ , each seen successor contributes $D/C(h)$ . Adding the higher-order and lower-order distributions still gives total probability 1.

4.6 Interpolation

Idea: instead of selecting one order through backoff, form a weighted mixture of N-gram models of different orders, with weights tuned on held-out data.

P_{IN}(w_i \mid w_{i-1}, w_{i-2}) = \lambda_3 P_3(w_i \mid w_{i-2}, w_{i-1}) + \lambda_2 P_2(w_i \mid w_{i-1}) + \lambda_1 P_1(w_i)

\sum_k \lambda_k = 1, \qquad \lambda_k \ge 0

$\lambda$ is learned on held-out data using EM or grid search, rather than chosen arbitrarily;
Advantage: retains higher-order precision while providing lower-order support, usually outperforming pure backoff.

4.7 Comparing smoothing methods

Method	Core idea	Advantages	Limitations
Add-1	Add 1 to every count	Simplest; ensures nonzero, normalised probabilities	Adds too much to sparse data and sharply reduces seen-event probabilities
Add-k	Add k to every count	Milder than add-one	Must tune $k$ ; all unseen words receive the same probability; changes original ratios
Absolute Discounting	Subtract $d$ from each seen count and give the remainder to unseen words	Simple; works better than add-k	Does not distinguish the information carried by lower-order contexts
Katz Backoff	Back off to a lower order for unseen events	Retains higher-order precision	Uses raw backoff probabilities, ignoring context diversity (the reading Kong problem)
Kneser-Ney	Use continuation probabilities to allocate discounted mass	A strong baseline for classical N-gram models	More complex formulas; requires two sets of counts
Interpolation	Weighted mixture of different model orders	Stable; often better than backoff	Must tune on held-out data: $\lambda$

5. Text classification

5.1 Task definition

Input: a document $d$ (usually represented as a feature vector) plus a fixed set of classes $C=\{c_1, c_2, \dots, c_k\}$ (categorical, rather than continuous or ordinal values).
Output: a predicted class $\hat{c} \in C$ .

5.2 Applications

Topic classification (economics / politics / sport)
Sentiment analysis
Native-language identification (for example, inferring an author's native-language background from their writing in a foreign language)
Natural language inference (entailment / contradiction / neutral)
Automatic fact-checking
Paraphrase identification

5.3 Standard workflow

Identify a task of interest
Collect an appropriate corpus
Annotate the data
Select features (bag of words, N-grams, TF-IDF, embeddings…)
Choose a machine learning algorithm
Train the model and tune hyperparameters on held-out development data.
Repeat earlier steps as needed
Train the final model
Evaluate the model on held-out test data.

5.4 What to consider when choosing a method

Aspect	Meaning
Bias	Systematic error caused by a model's limitations or simplifying assumptions; assumptions that do not match the true data can introduce substantial bias
Variance	The model's sensitivity to its training set. Greater sensitivity means larger changes in results when trained on a different sample, making overfitting more likely
Underlying assumptions	Conditions the model relies on, such as feature independence, linear boundaries or meaningful distances; violations can affect performance
Complexity	Time and space costs of training and inference, and scalability to large datasets
Speed	Whether training and prediction latency meet production requirements

Bias–variance trade-off: high bias often corresponds to underfitting, while high variance often corresponds to overfitting. Under squared loss, expected prediction error decomposes into squared bias, variance and irreducible noise. This framework also helps explain modelling choices in classification.

5.5 Comparing common algorithms

(1) Naïve Bayes

Basic idea: use Bayes' rule to choose the class with maximum posterior probability:

P(C\mid F) \propto P(F\mid C)\,P(C)

That is, "class prior × probability of these features given the class".

Naïve assumption: features are conditionally independent:

P(F \mid C) = \prod_{f \in F} P(f \mid C)

Pro: extremely fast; training needs only counts; robust with small datasets and high-dimensional sparse features; naturally supports multiple classes and incremental updates.
Con: the independence assumption almost never holds because words are strongly correlated; probabilities are poorly calibrated, often taking extreme values near 0 or 1; smoothing is needed for zero probabilities.

(2) Logistic regression / maximum entropy

Despite "regression" in the name, this is a classifier.
A linear model using softmax to convert linear scores into valid probabilities:

P(y=c \mid x) = \frac{\exp(w_c^\top x + b_c)}{\sum_{c'} \exp(w_{c'}^\top x + b_{c'})}

Training objective: maximise the likelihood of the training data, equivalently minimise cross-entropy, with regularisation to encourage small or sparse weights.
Pro: interpretable probability outputs, fast training, L1/L2 regularisation for feature selection, and linear models that scale to large corpora.
Con: can learn only linear decision boundaries unless nonlinear interactions are introduced through manually designed feature crosses; sensitive to feature scaling; severe class imbalance may require class weighting.

(3) Support Vector Machine (SVM)

Definition: find a hyperplane that separates the training data with the largest margin.

\min_{w,b}\ \tfrac{1}{2}\Vert w\Vert ^2 \quad \text{s.t.}\quad y_i(w^\top x_i + b) \ge 1

Pro: strong performance on high-dimensional sparse text, making it a classic text-classification baseline; maximum margins support good generalisation; kernels can handle nonlinearity.
Con: inherently binary, requiring approaches such as one-vs-rest for multiclass classification; kernel SVMs are expensive to train on large datasets; calibrated probabilities are not direct outputs. Linear SVMs admit more efficient optimisation, so complexity should not be generalised across all SVMs.

(4) K-Nearest Neighbour (KNN)

Definition: find the $k$ nearest training examples in feature space and classify by their majority class.
"Nearest" can be defined in different ways: Euclidean distance, cosine distance (common for text because it considers direction rather than length).
Pro: no training phase (lazy learning), natural multiclass support, potentially highly nonlinear boundaries, and easy implementation.
Con: prediction requires distance calculations against all examples, making inference slow and memory-intensive; highly sensitive to feature scaling and distance metrics; distances become less useful in high dimensions (the curse of dimensionality); majority classes dominate under class imbalance.

(5) Decision Tree

Definition: build a tree whose internal nodes test a single feature and whose leaves give the final class. Splits are chosen greedily using criteria such as information gain or Gini impurity.
Pro: interpretable, readable rules; no feature scaling required; handles nonlinearity and feature interactions; fast training.
Con: very prone to overfitting, requiring pruning or depth limits; greedy splits are only locally optimal; unstable under data perturbations (high variance); favours features with many possible values.

(6) Random Forest

Definition: an ensemble classifier comprising decision trees trained on different training subsets (bootstrap samples) and different feature subsets. The final result is determined by majority voting.
Pro: substantially reduces variance and overfitting; usually robust to noise; provides feature importance. Tree depth, leaf size and other parameters still need task-specific tuning; missing-value support depends on the implementation.
Con: less interpretable than a single readable tree; larger model size and slower inference than a single tree; less efficient than linear models on high-dimensional sparse text.

(7) Neural Network

Definition: a collection of interconnected nodes, usually arranged in layers: an input layer for features, an output layer for class probabilities, and hidden layers. Each node forms a weighted linear combination of inputs from the previous layer, then passes it through an activation function to the next layer.
Pro: automatically learns feature representations; highly expressive; supports end-to-end training; scales to large datasets and pretraining.
Con: needs substantial data and compute; many hyperparameters; poor interpretability; prone to overfitting without regularisation or dropout; may not outperform linear models on small datasets.

5.6 Hyperparameter tuning and evaluation

Hold-out evaluation: split data into train / dev (validation) / test sets. Select hyperparameters on dev; use test only once for the final report.

Confusion matrix (binary example)

	Classified As A	Classified As B
True A	79 (TP)	13 (FN)
True B	8 (FP)	10 (TN)

Calculating metrics

Accuracy

\text{Accuracy} = \frac{TP + TN}{N} = \frac{79+10}{110} = 0.809

Precision: the proportion of predicted positives that are actually positive

P = \frac{TP}{TP + FP} = \frac{79}{79+8} = 0.908

Recall: the proportion of actual positives that are retrieved

R = \frac{TP}{TP + FN} = \frac{79}{79+13} = 0.859

F1-Score: the harmonic mean of precision and recall

F_1 = \frac{2PR}{P+R} = \frac{2 \times 0.908 \times 0.859}{0.908 + 0.859} = 0.883

Why the harmonic mean rather than the arithmetic mean? The harmonic mean is pulled down by the smaller value: F1 is high only when both P and R are high. This prevents either high recall with low precision or high precision with low recall from receiving a high score.

Multiclass metrics

Metric	Method	Characteristics
Macro-average	Calculate P/R/F1 separately for each class, then take the arithmetic mean across classes	Every class has equal weight, increasing the influence of minority classes and exposing poor long-tail performance
Micro-average	First pool TP/FP/FN across all classes, then calculate P/R/F1 once	Every example has equal weight, so larger classes dominate; in single-label multiclass classification, micro-F1 = accuracy

6. Part-of-speech tagging

6.1 What is POS tagging?

Definition: assign each word in a sentence its grammatical category, or part of speech.

Example: Janet/NNP will/MD back/VB the/DT bill/NN

Notice that back is a verb here, meaning "support", rather than a noun or adverb; its role depends on context.

Applications:

A precursor to constituency parsing: POS information supports the construction of phrase structure.
A precursor to information extraction: identifying entities and relations can rely on POS information, for example extracting only NN/NNP phrases.
Features for other tasks: provide linguistic features for NER, sentiment analysis and translation.
Speech synthesis (pronunciation and stress), lexicography and proofreading.

6.2 Word classes

Open classes: new words can be added and old words can disappear

Class	Subcategories
Nouns	Proper (Melbourne) / common; common nouns divide further into mass (water) / count (chair)
Lexical verbs	Can have rich inflection (sing/sang/sung); transitive or intransitive according to use
Adjectives	Gradable (very tall) / non-gradable (dead)
Adverbs	Locative (here, there) / degree (very, extremely)

Closed classes: relatively fixed membership, with additions and removals uncommon

Prepositions (of, in, on)
Particles (up, off, as in give up)
Determiners (the, a, this)
Pronouns (he, they, who)
Conjunctions (and, but, because)
Auxiliary / modal verbs (be, have, do, can, must, should; classification depends on the tagset)

6.3 The challenge of ambiguity

The same word form can have several parts of speech, with a highly uneven distribution:

back: noun (a body part) / verb ("support") / adverb ("backwards") / adjective
flies: plural noun (insects) / third-person singular verb ("fly")
like: preposition ("similar to") / verb ("enjoy")

A simple baseline assigns each word its most frequent POS tag in the training set. This exploits the uneven distribution of tags but cannot disambiguate using the current context. Accuracy depends on the corpus and the treatment of OOV words.

6.4 POS tagsets

Tagset	Number of tags	Characteristics
Brown	87	One of the earliest corpus tagsets; fine-grained
Penn Treebank (PTB)	45	The most widely used in NLP, including NN, NNS, NNP, VB, VBD, VBG, JJ, RB, IN, DT, MD, CC, PRP…
CLAWS5 / BNC	61	One version of CLAWS; tag counts differ between versions
Early Universal Tagset	12	NOUN, VERB, ADJ, ADV, PRON, DET, ADP, NUM, CONJ, PRT, ., X; do not confuse this with the 17 UPOS categories in Universal Dependencies

A classic ambiguity example (Penn Treebank tags)

TEXT

Time  flies like an arrow
Time/NN  flies/VBZ  like/IN  an/DT  arrow/NN

Fruit flies like a banana
Fruit/NN  flies/NNS  like/VBP  a/DT  banana/NN

The same word, flies, is a verb in the first sentence ("time passes quickly") and a noun in the second ("fruit flies"). Context is needed to tell them apart.

7. Hidden Markov models (HMMs)

7.1 Why do we need HMMs?

Task: POS tagging—given the entire word sequence $W = w_1 \dots w_n$ , find the optimal tag sequence $T = t_1 \dots t_n$ .

Limitations of existing approaches: predicting each word independently cannot use dependencies between tags. A greedy classifier that conditions on previously predicted tags can propagate errors: an earlier mistake affects later predictions.

New idea: give the model the whole sentence and have it produce an entire tag sequence.

New problem: sentence length varies, and the number of possible tag combinations is $\vert T\vert ^n$ , which is exponential, so enumeration is infeasible.

Solution: use a model that models individual words while treating the whole sentence as a unit during learning and prediction. This is called sequence labelling, or structured prediction.

How an HMM works: given a sentence, find the tag sequence with the highest probability among all possible sequences.

Advantages:

Data-driven, without hand-crafted rules
Finds a globally optimal tag sequence rather than making greedy word-by-word choices
Can learn its parameters from an annotated corpus

7.2 Formula

\hat{T} = \arg\max_{T} P(T \mid W) = \arg\max_{T} \frac{P(W \mid T)\,P(T)}{P(W)} = \arg\max_{T} P(W \mid T)\,P(T)

( $P(W)$ does not depend on $T$ , so it can be ignored; this applies Bayes' rule and drops the denominator)

Figure 7-1 HMM graphical model: solid arrows represent state transitions $P(t_i\mid t_{i-1})$ (matrix A), and dashed arrows represent emissions $P(w_i\mid t_i)$ (matrix O).

7.3 Two assumptions

Assumption	Statement	Role
Output independence	The word at position $i$ depends only on the tag at position $i$ , independently of other words and tags: $P(W\mid T)=\prod_i P(w_i\mid t_i)$	Factorises the sentence probability given the tags into a product over words
Markov assumption	The current tag depends only on the previous tag: $P(T)=\prod_i P(t_i \mid t_{i-1})$	Factorises the tag-sequence probability into a product of first-order transitions

Therefore:

\hat{T} = \arg\max_{T} \prod_{i=1}^{n} \underbrace{P(w_i \mid t_i)}_{\text{emission}} \cdot \underbrace{P(t_i \mid t_{i-1})}_{\text{transition}}

This also explains why an HMM is a generative model: it models the joint probability $P(W,T) = P(T)P(W\mid T)$ .

7.4 Training: estimate two probability tables

Parameter	Name	Meaning
$P(w_i \mid t_i)$	Emission / observation probability O	Probability that a tag generates a particular word
$P(t_i \mid t_{i-1})$	Transition probability A	Probability of a particular tag following the previous tag

Estimation: again, use maximum likelihood estimation (MLE), by counting:

P(w_i \mid t_i) = \frac{\text{Count}(w_i, t_i)}{\text{Count}(t_i)}, \qquad P(t_i \mid t_{i-1}) = \frac{\text{Count}(t_{i-1}, t_i)}{\text{Count}(t_{i-1})}

What about the first tag? Add a special start symbol <s> before each sentence, so the first term is $P(t_1 \mid \text{<s>})$ :

P(t_1 \mid \text{<s>}) = \frac{\text{Count}(\text{<s>}, t_1)}{\text{Count}(\text{<s>})}

Similarly, append </s> at the end, making $P(\text{</s>} \mid t_n)$ a learnable transition. The earlier product omits this end-of-sentence factor for brevity; the complete path probability also includes it.

What about unseen words? Use smoothing again (Section 4): add-k or add-one for the emission table, or map low-frequency words to <UNK> so that the emission probability of <UNK> is shared by all low-frequency words.

7.5 Prediction

Given a trained HMM (two tables: transition matrix A and emission matrix O), predict the tag sequence for the input sentence.

Core idea: choose the tag combination with the highest joint probability:

\hat{t} = \arg\max_{t} P(W \mid t)\,P(t) = \arg\max_{t} \prod_{i=1}^{n} P(w_i \mid t_i)\,P(t_i \mid t_{i-1})

Why not predict one word at a time? (the limitation of greedy decoding)

Taking the argmax word by word is locally optimal: the best tag for the current word may make the best tag for the next word extremely unlikely;
Optimising the whole sentence is a global problem that must weigh both earlier and later choices;
Enumerating $\vert T\vert ^n$ combinations is infeasible → use Viterbi dynamic programming to find the global optimum; for a fixed tagset size, runtime grows linearly with sentence length.

7.6 Generative versus discriminative

Aspect	Generative (HMM)	Discriminative (CRF / classifier)
What is modelled	Joint probability $P(X, Y)$	Conditional probability $P(Y \mid X)$ (or $P(T\mid W)$ )
Typical uses	Can generate language; HMMs also support unsupervised learning	Classification, prediction and sequence labelling
Training	Usually supervised or semi-supervised; also unsupervised through EM	Usually supervised
Features	Limited features: uses emission probabilities for the observations themselves	Rich features such as prefixes, suffixes, word forms, context words and external dictionaries
Data requirements	Simple structural assumptions may help when learning from small datasets	Often better predictions with sufficient data and features; still depends on the task and model
Examples	Naïve Bayes, HMMs; neural language models can also perform generative modelling	Logistic regression, CRFs, SVMs and neural classifiers

Discriminative models directly optimise "predict the output given the input", without explicitly modelling the input distribution $P(W)$ . They can therefore focus on prediction; whether they perform better still depends on the task, data and model.

8. The Viterbi algorithm

8.1 Core idea

Keep not just "the best tag for the current word", but "the best path score for each possible ending tag", considering every combination when moving to the next word.

For each position $t$ and tag $j$ , record the cumulative score of the best path ending in $j$ , $\delta_t(j)$ , and its backpointer $\psi_t(j)$ .

8.2 Recurrence

\delta_1(j) = P(t_1 = j \mid \text{<s>}) \cdot P(w_1 \mid j)

\delta_t(j) = \max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j \mid i)\Big]\cdot P(w_t \mid j)

\psi_t(j) = \arg\max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j\mid i)\Big]

Termination:

\hat{t}_n = \arg\max_{j}\big[\delta_n(j)\,P(\text{</s>}\mid j)\big], \qquad \hat{t}_{t} = \psi_{t+1}(\hat{t}_{t+1}) \ \text{(backtracking)}

If the model has no explicit end state, simply compare $\delta_n(j)$ at termination. Both examples below use this simplification.

Intuitive example: Can Play

For can, record separate scores for MD (modal verb) and NN (noun);
When processing play, for each candidate tag (VB, NN):
- Combine "can tag score × transition probability × emission probability";
- Find the path with the highest overall probability;
Finally, compare the cumulative scores for all ending tags, take the largest, and backtrack to recover the whole path.

8.3 Example 1: Janet will back the bill

Transition matrix (excerpt; rows give the conditioning event $P(\cdot\mid \text{row})$ )

	NNP	MD	VB	JJ	NN	RB	DT
<s>	0.2767	0.0006	0.0031	0.0453	0.0449	0.0510	0.2026
NNP	0.3777	0.0110	0.0009	0.0084	0.0584	0.0090	0.0025
MD	0.0008	0.0002	0.7968	0.0005	0.0008	0.1698	0.0041
VB	0.0322	0.0005	0.0050	0.0837	0.0615	0.0514	0.2231
JJ	0.0366	0.0004	0.0001	0.0733	0.4509	0.0036	0.0036
NN	0.0096	0.0176	0.0014	0.0086	0.1216	0.0177	0.0068
RB	0.0068	0.0102	0.1011	0.1012	0.0120	0.0728	0.0479
DT	0.1147	0.0021	0.0002	0.2157	0.4744	0.0102	0.0017

(Data from Jurafsky and Martin's Speech and Language Processing, Chapter 18, Figure 18.12, based on the WSJ corpus without smoothing. Only some tags are shown, so the rows need not sum to 1; it is the full transition distribution that is normalised.)

Emission matrix (Speech and Language Processing, Figure 18.13)

	Janet	will	back	the	bill
NNP	0.000032	0	0	0.000048	0
MD	0	0.308431	0	0	0
VB	0	0.000028	0.000672	0	0.000028
JJ	0	0	0.000340	0	0
NN	0	0.000200	0.000223	0	0.002337
RB	0	0	0.010446	0	0
DT	0	0	0	0.506099	0

Procedure: build a $\vert T\vert \times n$ trellis, fill in $\delta$ column by column, and record the preceding tag in each cell. Backtrack from the largest value in the final column.

8.4 Example 2: they fish (can be checked by hand)

This two-state toy model uses artificial values solely to demonstrate dynamic programming. N and V are state labels; it does not imply that they can function as a verb in real English.

Emission probabilities

	they	fish
N	0.7	0.3
V	0.4	0.6

Transition probabilities

	N	V
<s>	0.6	0.4
N	0.8	0.2
V	0.7	0.3

Figure 8-1 they fish Viterbi trellis: each cell retains only the "best prefix score ending in this tag" $\delta$ . The red arrows show the optimal path recovered by backtracking: they/N → fish/N.

Enumerating all 4 paths

Path	Calculation	Probability
N N	$0.6\times0.7 \times 0.8\times0.3$	0.1008 ✅ Optimal
N V	$0.6\times0.7 \times 0.2\times0.6$	0.0504
V N	$0.4\times0.4 \times 0.7\times0.3$	0.0336
V V	$0.4\times0.4 \times 0.3\times0.6$	0.0288

Result: they/N fish/N. Looking only at the emission probabilities of fish, we find that $P(\text{fish}\mid V)=0.6$ exceeds $P(\text{fish}\mid N)=0.3$ . Once transition probabilities are included, however, the optimal path ends in N. Emission probabilities are not tag posteriors and cannot directly determine the tag. This example demonstrates the value of transition information; it does not establish a case where greedy decoding that incorporates transitions at each step necessarily fails.

8.5 Algorithm properties

Property	Explanation
Time complexity	$O(T^2 N)$ : $T$ = tagset size, $N$ = sequence length. At each of the $N$ positions, for each of the $T$ tags, compare all $T$ tags at the previous position
Space complexity	If only the optimal score is needed, retain two rolling columns, using $O(T)$ space; recovering the whole path requires $O(TN)$ backpointers
Why it works	Optimal substructure: the best path to position $t$ with tag $j$ must have a prefix that is itself the best path to some tag at position $t-1$ , otherwise replacing the prefix would improve the solution; the Markov property: given the current tag, the future is independent of earlier history. Each cell can therefore retain only its best prefix score and safely discard suboptimal paths
Numerical underflow	Products of probabilities quickly underflow to 0. Practical implementations use log probabilities (multiplication becomes addition, with $O(T^2N)$ unchanged)
Higher-order variants	Use a tag trigram (second-order HMM): $P(t_i \mid t_{i-2}, t_{i-1})$ with interpolation smoothing; complexity rises to $O(T^3 N)$