CS489 Course Notes

Professor: Freda Shi | Term: Winter 2026

Lecture 1

This course will be helpful if:

• You are curious about the fundamentals and detailed implementations of language models
• You are looking to apply state-of-the-art NLP techniques to your own goals
• You are interested in NLP and computational linguistics research

This course will not cover:

• Basics of Python programming, probability, and algorithms
• System and architectures for efficient language model training and deployment
• GPU programming (except for a few high-level basics)

Following background knowledge is strongly recommended:

• Basic knowledge of calculus, linear algebra, and probability
• Python programming proficiency
• Fundamentals of algorithms
• Understanding of basic data structures

Question

What is Natural Language Processing?

Goal: Understand natural language with computational models.

End system we want to build

• Simple: Text classification, grammatical error correction
• Complex: Translation, question answering, speech recognition
• Unknown: Human-level comprehension

This course will cover the foundation models of language models.

Question

Why is NLP difficult?

Ambiguity: One form can have multiple meanings.

”She saw a cat with a telescope”. Who was with a telescope?

Variability: Multiple forms can share the same meaning.

”The cat is chasing the mouse”. “The mouse is being chased by the cat”.

Cross-lingual awareness, dialects and accents.

Orilla (Spanish) $\to$ 银行 (Chinese)

Orilla is a shore bank, 银行 is a financial bank. Translation uses English as the middle language.

Underlying meanings: Politeness, humour, irony.

Q: Do you have iced tea? A1: No A2: We have iced coffee

Roadmap: Levels of language

• Morphology: What words/subwords are we dealing with?
• Syntax: What phrases are we dealing with?
• Semantics: What is the literal meaning?
• Pragmatics: What is the underlying meaning?

Roadmap: Modeling Approaches

Classification:

• Sentiment Classifier: Take input sentence, run it through a sentiment classifier, and output a label.
• Local Consistency Checker: Take a pair of sentences, and output a label to the relationship of the sentences.

Language Modeling:

• GPT: Next-word predictor. Take a prefix of a sentence, and predict the next word
• BERT: [Mask] Token Predictor. Collect text, mask some word in the middle of the text, and predict the masked word based on the context.

Brief History of NLP

1960s-1990s: Classical NLP

• Linguistic theories
• Manually-defined rules

1980s-2013: Statistical NLP

• Supervised machine learning with annotated data
• Mostly linear models with manually-defined features

2012-now: Neural NLP

• Neural network as primary architecture
• Learning representations from large corpora
• Less hand-crafting features/linguistic knowledge

2022-now: Large language models

• Pretrain a language model
• Use the pretrained language model for various tasks

Common notations of discrete probability

$P(X=x)$ denotes the probability that random variable $X$ takes on the value $x$.

Given two random variables $X,Y$.

Joint probability: $P(X=x,Y=y)=P(x,y)$

Marginal probability: $P(X=x)=P(x)={\sum }_{y}P(x,y)$. $X$ and $Y$ are independent $⟺$ $P(x,y)=P(x)P(y)$.

Conditional probability: $P(X=x|Y=y)=P(x|y)=\frac{P(x,y)}{P(y)}$. $X$ and $Y$ are independent $⟺$ $P(x|y)=P(x)⟺P(y|x)=P(y)$.

Expectation: $\mathbb{E}[X]={\mathbb{E}}_{x\sim P}[x]={\sum }_{x}xP(x)$

Finding the optimum of a function

Find the minimum of a convex function $\mathcal{L}(w:X,y)$.

Gradient descent: $w^{\prime }\leftarrow w-\eta {\nabla }_w\mathcal{L}(w;X,y);$ $\eta$ is the learning rate (“step size”).

Lecture 2

Question

What is a word?

A single distinct meaningful element of speech or writing, used with others to form a sentence.

Things in dictionaries? (new words are often created).

Things between spaces and punctuation? (not all languages treat spaces the same).

Smallest unit that can be uttered in isolation? (one can utter “unimpressively” and “impress”).

Each of the above captures some but not all aspects of what word is.

Linguistic Morphology

Definition

Morphology is the study of how words are built from smaller meaning-bearing units

Types of morphemes:

• Stem: Core meaning-bearing unit
• Affix: A piece that attaches to a stem, adding some function or meaning (e.g. prefix, suffix). ‘Speedometer’ is an interfix. Infixes and circumfixes exist in other languages.

Definition

Inflection: Adding morphemes to a word to indicate grammatical information.

walk $\to$ walked

cat $\to$ cats

Definition

Derivation: Adding morphemes to a word to create a new word with a different meaning.

happy $\to$ happiness

define $\to$ predefine

Definition

Compounding: Combining two or more words to create a new word.

key + board $\to$ keyboard

law + suit $\to$ lawsuit

In languages like Classical Chinese, Vietnamese, and Thai

Each word form typically consists of one single morphene. There is litlte moprhology other than compounding.

Few examples of inflection and derivation.

Most Chinese words are created by compounding.

Usually, morphological decomposition is simply splitting a word into its morphemes:

walked = walk + ed

greatness = great + ness

But it can be a hierarchical structure:

unbreakable = un + (break + able)

internationalization = (((inter + nation) + al) + iz[e]) + tion

There is ambiguity in hierarchical decomposition. The door is unlockable.

Tasks that address morphology:

Lemmatization: Putting words/tokens in a standard format.

• Lemma is a canonical/dictionary form of a word.

• Wordform: Fully inflected or derived form of a word as it appears in text.

wordform	lemma
run	run
ran	run
running	run
keyboards	keyboard

Stemming: Reducing words to their stems by removing affixes. More conventional engineering-oriented approach used in applications such as retrieval.

”Caillou is an average, imaginative” $\to$ “Caillou is an averag imagin”.

Lexical Semantics

Lemmatization and stemming tackles the problem of variability. Multiple forms could share the same or similar meanings.

One wordform could refer to multiple meanings.

Definition

Polysemy: A word has multiple related meanings.

She is a star or the star is shining.

Definition

Homonymy: A word has multiple meanings originated from different sources.

I need to go to the bank for cash or I am sitting on the bank of the river.

Question

Which one is the case for a crane?

Crane is a polysemy. The machine was named after the bird.

Definition

Synonyms: Words that have the same meanings according to some criteria.

There are few examples of perfect synonymy.

Synonymy is a relation between senses rather than words.

Definition

Antonyms: Senses that are opposite with respect to at least one dimensionality of meaning.

dark and light (colours)

dark and bright (light)

Sense $A$ is a hyponym of sense $B$ is $A$ is more specific, denoting a subclass of $B$.

Conversly, $B$ is a hypernym of $A$.

Dog is a hyponym of animal

Corgi is a hyponym of dog

Sense $A$ is a meronym of sense $B$ is $A$ is a part of $B$.

Conversely, $B$ is a holonym of $A$.

Hand is a meronym of body

Finger is a meronym of hand

Definition

Word-Sense Disambiguation (WSD): The task of determining which sense of a word is used in a particular context, given a set of predefined possible senses.

Definition

Word Sense Induction (WSI): Requires clustering word usages into senses without predefined ground truths.

Default solution: encode the context of words with a pretrained model, and train a neural network to predict the sense.

Question

We now have powerful neural language models, which do not distinguish word senses. Is WSD still a meaningful task? Do discrete word senses even exist?

Definition

Tokenization: The process that converts running text into a sequence of tokens.

	Penn Treebank	Moses
don’t	do n’t	don ‘t
aren’t	are n’t	aren ‘t
can’t	ca n’t	can ‘t
won’t	wo n’t	won ‘t

Important to check and ensure consistency when comparing results across tokenizers.

There is no explicit whitespace between words in some languages, and tokenization becomes highly nontrivial in these cases.

姚明 进入 总决赛 (Chinese Treebank) vs 姚 明 进入 总 决赛 (Peking University).

Type: A unique word.

Token: An instance of a type in the text.

Question

How does the type/token ratio change when adding more data?

Ratio drops fast. Common words appear a lot

Zipf’s Law (also covered in CS451): Frequency of a word is roughly inversely proportional to its rank in the word frequency list.

Tokenization in Modern NLP Systems

There are many words, but the words have shared internal structures and meanings.

Modern NLP systems always convert tokens into numerical indices for further processing. Can we do better than assigning each word a unique index?

flowchart LR
tokenizer --> a[NLP model]
a[NLP model] --> detokenizer

Data-driven tokenizers offer an option that learns the tokenization rules from data, tokenizing texsts into subword units using statistics of character sequences in the dataset.

Two most popular methods:

• Byte Pair Encoding (BPE)
• SentencePiece

Byte Pair Encoding

Originally introduced in 1994 for data compression, later adapted and revived for NLP.

Key idea: Merge symbols with a greedy algorithm.

Initialize the vocabulary with the set of characters, and iteratively merge the most frequent pair of symbols to extend the vocabulary.

Training Corpus

• cat
• cats
• concatenation
• categorization

Initial vocabulary

• a c e g i n o r s t z

Count Symbol-Pair Frequencies

• <a t>: 6, <c a>: 4, <o n>: 3,

Update vocabulary

• a c e g i n o r s t z at

Count Symbol-Pair Frequencies

• <c at>: 4, <o n>: 3,

Update vocabulary

• a c e g i n o r s t z at cat

We repeat this process until the vocabulary reaches the desired size.

The BPE proposal is not optimal in terms of compression rate under the same vocabulary size.

A better vocabulary

• a c e g i n o r s t z cat on

Apply Trained BPE to a New Corpus

In addition to having the tokens, we will also need to know the merge rules. Starting from individual characters, and merge following the rules.

Terminate vocabulary

• a c e g i n o r s t z at cat

Merge Rules

• a t $\to$ at
• c at $\to$ cat

Word to be tokenized

• c a t e g o r y

Result

• cat e g o r y

SentencePiece Tokenization

Find the vocabulary for a unigram language model that maximizes the likelihood of the training corpus.

$$\begin{array}{rl}P(⟨x_1,x_2,\dots ,x_n⟩)& =\prod _{i=1}^{n}P(x_i)\\ P(x_i)& :=\mathrm{optional}-\mathrm{smoothing}\left(\frac{\mathrm{count}(x_i)}{{\sum }_{x\in V}\mathrm{count}(x)}\right)\end{array}$$

Byte-Level BPE

Question

How do large language models tokenize texts from different languages, with a unified tokenizer and fixed vocabulary size?

Convert to hexadecimal.

Prepend zeroes to fix the length of tokens (to ensure the unique decoding), and do BPE on the bit/multi-bit level.

Lecture 3

Recap: Tokenization in Modern NLP Systems

The natural first step is to convert tokens into numerical indices for further processing.

Question

Can we do better than assigning each word a unique index?

Recap: Byte-Level BPE Tokenization

Consider UTF-8 encoding of “Hello world!”

Character	UTF-8 Hex
H	48
e	65
l	6C
l	6C
o	6F
(space)	20
W	57
o	6F
r	72
l	6C
d	64
!	21

We will work with the sequence 48 65 6C 6F 20 57 6F 72 6C 64 21.

The base vocabulary: $2^8=256$ entries from 00 to FF. At each step, evaluate frequency of consecutive vocabulary entry pairs, and add a new entry.

This is not much different from character-based BPE.

Question

What about non-English characters?

Consider UTF-8 encoding of “Hello 世界” (world).

Character	UTF-8 Hex
H	48
e	65
l	6C
l	6C
o	6F
(space)	20
世	E4 B8 96
界	E7 95 8C

We will work with the sequence of 48 65 6C 6F 20 E4 B8 96 E7 95 8C. Base vocabulary is still $2^8=256$.

Edit Distance: Comparing similarity of two sequences

Question

How to measure the similarity between two strings?

We need to design algorithms to assign a numerical score to measure similarity.

A proposal: The minimum number of single-character edits required to change one string $A$ into another $B$.

Three allowed operations:

• Insertion
• Deletion
• Substitution

This is known as Levenshtein Distance

teh $\to$ the

• Delete e at position 2, add e at position 3; or
• Add h at position 2, delete h at position 4; or
• Substitute e at position 2 with h, substitute h at position 3 with e .

cat $\to$ bat

• Substitute c at position 1 with b

cat $\to$ cats

• Add s at position 4

Unified Algorithmic Solution

Question

How about sitting $\to$ extension?

Dynamic Programming (CS341):

Let $f[i][j]$ represent the edit distance (minimal number of edits) between the first $i$ characters of $A$ and the first $j$ characters of $B$.

$$\begin{array}{rl}f[i][j]=\min & \{\begin{array}{ll}f[i-1][j]+1& \text{deletion}\\ f[i][j-1]+1& \text{insertion}\\ f[i-1][j-1]+cost& \text{substitution, or do nothing}\end{array}\\ & \\ & cost=0\text{ if }A[i]=B[j],\text{ otherwise }1\end{array}$$

Edge cases: $f[0][i]=f[i][0]=i$

	0 $\varnothing$	1 e	2 x	3 t	4 e	5 n	6 s	7 i	8 o	9 n
0 $\varnothing$	0	1	2	3	4	5	6	7	8	9
1 s	1	1	2	3	4	5	5	6	7	8
2 i	2	2	2	3	4	5	6	5	6	7
3 t	3	3	3	2	3	4	5	6	6	7
4 t	4	4	4	3	3	4	5	6	7	7
5 i	5	5	5	4	4	4	5	5	6	7
6 n	6	6	6	5	5	4	5	6	7	6
7 g	7	7	7	6	6	5	5	6	7	7

The equation implies doing nothing when $A[i]=B[j]$ when calculating $f[i][j]$.

Question

Why is this correct?

Intuition: In such cases, doing nothing may not be the unique best solution, but it is one of the best.

$f[4][3]=3$ for sitting $\to$ extension, which could come from $f[3][2]$, or $f[3][3]+1$.

Extension: Different Operations with Different Costs

The minimum cost of single-character edits required to change one word into the other. Each operation could have a different non-negative cost.

Three allowed operations:

• Insertion with cost $a$
• Deletion with cost $b$
• Substitution with cost $c$.

$$\begin{array}{rl}f[i][j]=\min & \{\begin{array}{ll}f[i-1][j]+a& \text{deletion}\\ f[i][j-1]+b& \text{insertion}\\ f[i-1][j-1]+cost& \text{substitution, or do nothing}\end{array}\\ & \\ & cost=0\text{ if }A[i]=B[j],\text{ otherwise }c\end{array}$$

Word Vectors

Until 2010, in NLP, words meant atomic symbols.

Nowadays, it’s natural to think about word vectors when talking about words in NLP. Each word is represented by a vector.

Key idea: Similar words are nearby in a good vector space.

How models represent words

We map each word to a (very high-dimensional) vector.

One of the key challenges for NLP is variability of language (multiple forms having the same meaning).

Representation Learning for Engineering

Engineering: These representations are often useful for downstream tasks.

Transfer learning:

• Image $\to$ Segmentation, Visual QA $\to$ Object classification
• Text $\to$ Classification, QA $\to$ Context prediction

How to represent a word: One-hot representation of words

$\mathrm{Rep}(w)\in \{0,1{\}}^{|V|}$.

$|V|$ could be very large, word vectors are orthogonal.

$$\begin{array}{r}|V|\begin{array}{cccc}\left[\begin{array}{c}1\\ 0\\ 0\\ 0\\ ⋮\\ 0\end{array}\right]& \left[\begin{array}{c}0\\ 1\\ 0\\ 0\\ ⋮\\ 0\end{array}\right]& \left[\begin{array}{c}0\\ 0\\ ⋮\\ 1\\ 0\\ 0\end{array}\right]& \left[\begin{array}{c}0\\ 0\\ 0\\ ⋮\\ 0\\ 1\end{array}\right]\\ w=\text{better}& \text{winner}& \text{cat}& \text{champion}\\ \in V& & & \end{array}\end{array}$$

Question

What is an ideal word representation?

It should probably capture information about usage and meaning:

• Part of speech tags (noun, verb, adj., adv., etc.)
• The intended sense
• Semantic similarities (winner vs champion)
• Semantic relationships (antonyms, hypernyms)

Features

$$\begin{array}{ccccc}\begin{array}{c}\text{Is noun?}\\ \text{Is verb?}\\ \text{Is adj.?}\\ \text{Is animal?}\\ ⋮\\ .\\ .\\ .\end{array}& \left[\begin{array}{c}0\\ 0\\ 1\\ 0\\ ⋮\\ 0\\ 0\\ 0\end{array}\right]& \left[\begin{array}{c}1\\ 0\\ 0\\ 0\\ ⋮\\ 0\\ 0\\ 0\end{array}\right]& \left[\begin{array}{c}1\\ 0\\ 0\\ 1\\ ⋮\\ 0\\ 1\\ 0\end{array}\right]& \left[\begin{array}{c}1\\ 1\\ 0\\ 0\\ ⋮\\ 0\\ 0\\ 1\end{array}\right]\\ & \text{better}& \text{winner}& \text{cat}& \text{champion}\end{array}$$

Features could extend infinitely.

Distributional Semantics: How much of this can we capture from context/data alone?

”The meaning of a word is its use in the language.” - Ludwig Wittgenstein.

The use of a word is defined by its contexts.

Distributional Semantics

Consider a new word: tezgüino.

1. A bottle of tezgüino is on the table.
2. Everybody likes tezgüino.
3. Don’t have tezgüino before you drive.
4. We make tezgüino out of corn.

Question

What do you think tezgüino is?

Loud, motor oil, tortillas, choices, wine.

	1	2	3	4
tezgüino	1	1	1	1
loud	0	0	0	0
motor oil	1	0	0	1
tortillas	0	1	0	1
choices	0	1	0	0
wine	1	1	1	0

Question

How can we automate the process of constructing representations of word meaning from its company?

First solution: word-word cooccurrence counts (CS451).

Counting for Word Vectors

’the club may also employ a chef to prepare and cook food items'

'is up to Remy, Linguini, and the chef Colette to cook for many people'

'cooking program the cook and the chef with Simon Bryant, who’

The top word is the word we are computing the vector for, the words on the side are the context words

$$\begin{array}{r}\text{Window size }w=1\begin{array}{cc}& \text{chef}\\ \begin{array}{l}\text{the}\\ \text{cat}\\ \text{chicken}\\ \text{city}\\ \text{cook}\end{array}& \left[\begin{array}{c}2\\ 0\\ 0\\ 0\\ 0\end{array}\right]\end{array}\end{array}$$ $$\begin{array}{r}\text{Window size }w=4\begin{array}{cc}& \text{chef}\\ \begin{array}{l}\text{the}\\ \text{cat}\\ \text{chicken}\\ \text{city}\\ \text{cook}\end{array}& \left[\begin{array}{c}3\\ 0\\ 0\\ 0\\ 3\end{array}\right]\end{array}\end{array}$$ $$\begin{array}{ccccccc}& \text{cat}& \text{chef}& \text{chicken}& \text{civic}& \text{cooked}& \text{council}\\ \begin{array}{l}\text{the}\\ \text{cat}\\ \text{chicken}\\ \text{city}\\ \text{cook}\end{array}& \left(\begin{array}{c}24708\\ 2336\\ 23\\ 116\\ 12\end{array}\right)& \left(\begin{array}{c}7410\\ 14\\ 21\\ 89\\ 113\end{array}\right)& \left(\begin{array}{c}7853\\ 23\\ 1640\\ 62\\ 34\end{array}\right)& \left(\begin{array}{c}16486\\ 0\\ 1\\ 943\\ 6\end{array}\right)& \left(\begin{array}{c}3463\\ 1\\ 181\\ 7\\ 34\end{array}\right)& \left(\begin{array}{c}316380\\ 36\\ 7\\ 27033\\ 51\end{array}\right)\end{array}$$

Once we have word vectors, we can compute word similarities.

Among many ways to define the similarity of two vectors, a simple way is the dot product:

$$\begin{array}{r}\mathbf{u}\cdot v={\mathbf{u}}^{⊺}\mathbf{v}=\sum _i{u}_i{v}_i\end{array}$$

Dot product is large when the vectors have very large (in terms of absolute values) in the same dimensions.

With dot product as the similarity function, we can find the most similar words (nearest neighbours) to each word:

cat	chef	chicken	civic	cooked	council
council	council	council	council	council	council
cat	cat	cat	cat	cat	cat
civic	civic	civic	civic	civic	civic
chicken	chicken	chicken	chicken	chicken	chicken
chef	chef	chef	chef	chef	chef
cooked	cooked	cooked	cooked	cooked	cooked

Council is always a top neighbour because its vector has very large magnitudes, and dot products care about magnitude.

Cosine similarity:

$$\begin{array}{r}\cos (\mathbf{u},v)=\frac{\mathbf{u}\cdot \mathbf{v}}{|\mathbf{u}||\mathbf{v}|}=\frac{{\sum }_i{u}_i{v}_i}{\sqrt{{\sum }_i{u}_i^2}\sqrt{{\sum }_i{v}_i^2}}\end{array}$$

Now using cosine similarity:

cat	chef	chicken	civic	cooked	council
cat	chef	chicken	civic	cooked	council
chef	civic	cooked	council	chef	civic
cooked	cooked	chef	chef	ciic	chef
civic	council	civic	cooked	council	cooked
council	cat	council	cat	cat	cat
chickedn	chicken	cat	chicken	chicken	chicken

Issues with Counting-Based Vectors

Raw frequency count is probably a bad representation. Count of common words are very large, but not very useful. “The”, “it”, “they” are not very informative.

There are many ways proposed for improving raw counts.

• Removing “stop words”
• Down-weight less informative words

TF (Term Frequency) - IDF (Inverse Document Frequency)

• Information Retrieval (IR) workhouse
• A common baseline model
• Sparse vectors
• Words are represented by a simple function of nearby words

Consider a matrix of word counts across documents: term-document matrix

$$\begin{array}{rl}\mathrm{tf}(w,d)& =\text{\# of times word }w\text{ appears in document }d\\ \mathrm{idf}(w)& =\log \left(\frac{\text{\# of documents}}{\text{\# of documents in which word }w\text{ occurs}}\right)\\ \mathrm{tf}-\mathrm{idf}(w,d)& =\mathrm{tf}(w,d)\cdot \mathrm{idf}(w)\end{array}$$

Term Frequency:

	As You Like it	Twelfth Night	Julius Caesar	Henry V
battle	1	0	7	13
good	114	80	62	89
fool	36	58	1	4
wit	20	15	2	3

Columns are bag-of-words (document representation). Rows are word vectors.

Lecture 4

Pointwise Mutual Information

Consider two random variables, $X$ and $Y$.

Question

Do two events $X=x$ and $Y=y$ occur together more often than if they were independent?

$$\begin{array}{r}\mathrm{PMI}(x,y)={\log }_2\frac{p_{X,Y}(x,y)}{p_X(x)p_Y(y)}\end{array}$$

If they are independent, then $\mathrm{PMI}=0$.

PMI for word vectors

For words $X$ and its context $Y$, each probability can be estimated using counts we already computed.

$$\begin{array}{r}{p}_{X,Y}(x,y)=\frac{\#(x,y)}{N-1},p_X(x)=\frac{{\sum }_z\#(x,z)}{N},p_Y(y)=\frac{{\sum }_z\#(z,y)}{N}\end{array}$$

Some have found benefit by truncating PMI at $0$ (positive PMI).

$$\begin{array}{r}\mathrm{PPMI}(x,y)=\max (0,\mathrm{PMI}(x,y))\end{array}$$

Negative PMI: words occur together less than we would expect (they are anti-correlated).

These anti-correlation may need more data to reliably estimate.

But, negative PMIs do seem reasonable.

Word2Vec

Instead of counting, train a classifier (neural network) to predict context.

Training is self-supervised: no annotated data is required, just raw text. Word embeddings are learned via backpropagation.

Definition

CBOW (Continuous bag-of-words): learning representations that predict a word given a bag of context (many-to-one-prediction).

$$\begin{array}{r}P(w_t|w_{t+1},\dots ,w_{t+k},w_{t-1},\dots ,w_{t-k})\end{array}$$

Given context, need to predict the centre word.

Definition

Skipgram: Learning representations that predict the context given a word.

$$\begin{array}{r}P(w_{t+1},\dots ,w_{t+k},w_{t-1},\dots ,w_{t-k}|w_t)=P(w_{t+1}|w_t)\dots P(w_{t-k}|w_t)\end{array}$$

Given centre word, and need to predict surrounding words.

Skipgram

$$\begin{array}{rl}& \theta =\{W,U\}\\ & W:V\times d\text{ input embedding matrix}\\ & U:V\times d\text{ output embedding matrix}\end{array}$$ $$\begin{array}{r}{p}_{\theta }(\text{out}|\text{input})=\frac{\exp (u_{\text{out}}\cdot w_{\text{input}})}{\underset{\text{softmax}}{\underbrace{\sum _{v\in V}\exp (u_v\cdot w_{\text{input}})}}}\end{array}$$

This is a log linear model.

‘it is a far, far better rest that I go to, than I have ever known’

$$\begin{array}{rl}{L}_t& =-\log p_{\theta }(\stackrel{\text{far}}{\overbrace{x_{t-2}}}|x_t)-\log p_{\theta }(\stackrel{\text{better}}{\overbrace{x_{t-1}}}|x_t)\\ & -\log p_{\theta }(\underset{\text{that}}{\underbrace{x_{t+1}}}|x_t)-\log p_{\theta }(\underset{\text{I}}{\underbrace{x_{t+2}}}|x_t)\end{array}$$

CBOW

Use the context to predict the centre word

$$\begin{array}{r}{p}_{\theta }(x_t|x_{t-w},\dots ,x_{t+w})\propto \exp \left(u_{x_t}\cdot \frac{1}{2w}\sum _{k\in \{-w,\dots ,-1,1,w\}}{w}_{x_{t+k}}\right)\end{array}$$ $$\begin{array}{rl}{L}_t& =-\log p_{\theta }(x_t|x_{t-2},x_{t-1},x_{t+1},x_{t+2})\end{array}$$

Information we get from the ordering of words is lost with bag of words.

Skipgram with negative sampling

$$\begin{array}{r}{p}_{\theta }(\text{out}|\text{input})=\frac{\exp (u_{\text{out}}\cdot w_{\text{input}})}{\underset{\text{softmax}}{\underbrace{\sum _{v\in V}\exp (u_v\cdot w_{\text{input}})}}}\end{array}$$

This denominator is very memory intensive. Doing the dot product of a row with the entire matrix every single time.

The vocabulary size $V$: $50$k - $30$M

Very expensive: $O(|V|)$

Treat the target word and neighbouring context word as positive examples. Randomly sample other words outside of context to get negative samples.

Learn to distinguish between positive and negative samples with a binary classifier.

$$\begin{array}{r}\log p((x,y)\text{ is a true pair})+\underset{C=\text{Negative Samples}}{\underbrace{\sum _{x\in C}}}\log p((x,k)\text{ is a negatiev pair})\\ p((x,c)\text{ is a true pair})=\sigma (u_c\cdot w_x)=\frac{1}{1+\exp (-u_c\cdot w_x)}\end{array}$$

This is essentially the softmax between the negative dot product and $0$.

You shall know anything by the company it keeps $\to$ Node2Vec, Concept2Vec, World2Vec.

Classification

Simplest user facing NLP application.

flowchart LR
Text --> Model
Model --> Category

Rule-Based Classifier

Sentiment classification of sentence $s$ (classes: positive, negative)

If $s$ contains words in [good, excellent, extraordinary, $\dots$] return positive.

If $s$ contains words in [bad, terrible, awful, $\dots$] return negative.

This has nice interpretability and can be very accurate. But rules are difficult to define, system can be very complicated, and is hardly generalizable.

Statistical Classifiers: General Formulation

Data: A set of labeled sentences $\mathcal{D}=\{(s_1,y_1),(s_2,y_2),\dots ,(s_n,y_n)\}$.

• $s_i$: a sentence (or a piece of text)
• $y_i$: label, usually represented as an integer

Deliverable: A classifier that takes an arbitrary sentence $s$ as input, and predicts the label $y$.

$$\begin{array}{r}\mathrm{classify}(s)=\arg \underset{y}{\max }\mathrm{score}(s,y;\theta )\\ \theta :\text{parameters of score function}\end{array}$$

Inference: solve $\arg \max$. Modeling: define $\mathrm{score}$ function. Learning: choose parameter $\theta$.

First approach to the modeling problem, Naïve Bayes.

Probabilistic model: $\mathrm{score}(s,y;\theta ):=P(y|s)$ estimated from the data.

Question

How to estimate $P(y|s)$ to ensure sufficient generalizability?

The Bayes rule:

$$\begin{array}{r}P(y|s)=\frac{P(s|y)P(y)}{P(s)}\propto P(s|y)P(y)\end{array}$$

Unigram assumption:

$$\begin{array}{r}P(s|y)=P(w_1|y)P(w_2|y)\dots P(w_k|y)\text{if }s=w_1{w}_2\dots w_k\end{array}$$

$\theta$ in $\mathrm{score}(s,y;\theta )$: look-up table that stores $P(w|y)$ and $P(y)$.

Each $P(w|y)$ and $P(y)$ can be estimated by counting from the corpora.

$$\begin{array}{rl}P(w|y)& =\frac{\mathrm{count}(w,y)}{{\sum }_{w^{\prime }\in V}\mathrm{count}(w^{\prime },y)}\\ P(y)& =\frac{\mathrm{count}(y)}{n}\end{array}$$

This is the estimation that maximizes dataset probability.

Issue: an unseen word in certain class will lead to a zero probability (same problem from CS451)

Solution: Smoothing

$$\begin{array}{r}P(w|y)=\frac{\mathrm{count}(w,y)+\alpha }{{\sum }_{w^{\prime }\in V}\mathrm{count}(w^{\prime },y)+\alpha |V|}\end{array}$$

Inference

$$\begin{array}{r}\mathrm{classify}(s)=\arg \underset{y}{\max }\mathrm{score}(s,y;\theta )=\arg \underset{y}{\max }P(y|s)\\ P(y|s)\propto P(y)P(s|y)=P(y)P(w_1|y)P(w_2|y)\dots P(w_k|y)\end{array}$$

Smoothing applies to words seen in the training data. If the word never existed in the training data, we just ignore it.

Lecture 5

Recap

Logistic function: $\sigma (x)=\frac{1}{1+e^{-x}}$, $\sigma :\mathbb{R}\to (0,1)$.

Logistic Regression: Modeling

Suppose we can represent sentence $s$ with a vector $x$.

Probabilistic model:

$$\begin{array}{rl}\mathrm{score}(s,y=1;\theta )& :=P(y=1|s)=\sigma (\theta \cdot \mathbf{x}+b)\\ \mathrm{score}(s,y=0;\theta )& :=P(y=0|s)=1-\sigma (\theta \cdot \mathbf{x}+b)\end{array}$$

$\theta \cdot \mathbf{x}+b$ can be written as $\theta \cdot x$ if $x$ has a constant dimension.

Logistic Regression: Learning

Objective: Maximizing the dataset probability, under the assumption that each example is sampled independently.

$$\begin{array}{r}\hat{\theta }=\arg \underset{\theta }{\max }\prod _{i=1}^n\sigma (\theta \cdot {\mathbf{x}}_{\mathbf{i}}{)}^{y_i}(1-\sigma (\theta \cdot {\mathbf{x}}_{\mathbf{i}}){)}^{1-y_i}\end{array}$$

For better numerical representation, we usually take the negative logarithm of the probability as the loss and minimize it:

$$\begin{array}{r}\mathrm{Loss}(\theta )=-\sum _{i=1}^n{y}_i\log \sigma (\theta \cdot {\mathbf{x}}_{\mathbf{i}})+(1-y_i)\log (1-\sigma (\theta \cdot {\mathbf{x}}_{\mathbf{i}}))\end{array}$$

Gradient descent:

$$\begin{array}{r}\theta =\theta -\eta {\nabla }_{\theta }\mathrm{Loss}(\theta )\end{array}$$

Logistic Regression: Inference

Compute whether class 0 or 1 has larger probability.

Question

What if there are more than 2 classes?

• 1 vs. 1 for $\frac{C(C-1)}{2}$ class pairs and do voting; or
• 1 vs. all for $C$ classes and do $\arg \max$.

Probabilistic interpretation over classes no longer hold for multi-class classification with logistic regression.

Generative vs. Discriminative Model for Classification

• Generative models: $P(s,y)$ is accessible when modeling $P(y|s)$.
• Discriminative models: $P(y|s)$ is directly modelled.

Question

What are the key differences?

Difference: If you can generate a new data example once you have the model. Naïve Bayes is a generative model, logistic regression is a discriminative model.

Neural-Network Classifier

A neural network is a function. It has inputs and outputs. Neural modeling now is better thought of as dense representation learning.

$$\begin{array}{r}\mathrm{classify}(s)=\stackrel{\text{Inference: solve }\arg \max }{\overbrace{\arg \underset{y}{\max }}}\underset{\text{Modeling: define score function}}{\underbrace{\mathrm{score}}}(s,y;\stackrel{\text{Learning: choose parameter}}{\overbrace{\theta }})\end{array}$$

With a neural network based function $f_{\theta }$, we input $x$ and collects a vector $\hat{y}=f_w(x)$; $\mathrm{score}(x,y;\theta )$ is defined by selecting the corresponding entry in $\hat{y}$.

Common Neural Network Notations:

• $\mathbf{u}$: a vector
• $u_i$: entry $i$ in the vector
• $\mathbf{W}$: a matrix
• $w_{i,j}$ entry $(i,j)$ in the matrix

Perceptron

$$\begin{array}{r}\mathrm{perceptron}(\mathbf{x};\theta )=\mathrm{step}({\theta }^{⊺}\mathbf{x})\end{array}$$ $$\begin{array}{r}step(z)=\{\begin{array}{ll}1& \text{if }z\ge 0\\ 0& \text{if }z<0\end{array}\end{array}$$

If the dot product between $x$ and $\theta$ is less than $0$, then category for $x$ will be $0$.

Predict the label: ${\hat{y}}^{(i)}=\mathrm{perceptron}({\mathbf{x}}^{(i)};\theta )$.

Update weights: $\theta =\theta +\eta \cdot (y^{(i)}-{\hat{y}}^{(i)}){\mathbf{x}}^{(i)}$.

${\hat{y}}^{(i)}$	$y^{(i)}$	What happens
0	0	Nothing
1	1	Nothing
1	0	$\theta =\theta -\eta \cdot {\mathbf{x}}^{(i)}$
0	1	$\theta =\theta +\eta \cdot {\mathbf{x}}^{(i)}$

Neural Layer: Generalized Perceptron

A neural layer = affine transformation $+$ nonlinearity

$$\begin{array}{r}\mathrm{perceptron}(\mathbf{x})=\mathrm{step}({\theta }^{⊺}\mathbf{x}+b)\\ neural\_layer(\mathbf{x})=g({\mathbf{W}}^{⊺}\mathbf{x}+\mathbf{b})\end{array}$$

Output is a vector (results from multiple independent perceptrons). Can have other activation functions for nonlinearity.

Stacking Neural Layers

Multiple neural layers can be stacked together

$$\begin{array}{rl}\text{hidden units}{\mathbf{z}}^{(1)}& =g\left({\mathbf{W}}^{(0)}\mathbf{x}+{\mathbf{b}}^{(0)}\right)\\ {\mathbf{z}}^{(2)}& =g\left({\mathbf{W}}^{(1)}{\mathbf{z}}^{(1)}+{\mathbf{b}}^{(1)}\right)\\ & ⋮\end{array}$$

We use the output of one layer as input to the next. This is a feed forward (and/or fully-connected layers). Also called multi-layer perceptron (MLP).

Nonlinearities (activation function)

$$\begin{array}{r}{\mathbf{z}}^{(1)}=g\left({\mathbf{W}}^{(0)}\mathbf{x}+{\mathbf{b}}^{(0)}\right)\end{array}$$

$g$ can be applied to each entry in a vector in an element-wise manner. Common activation functions: $\tanh$, $\mathrm{sigmoid}$, and $\mathrm{ReLU}$.

Question

Why nonlinearities?

Otherwise stacking neural layers results in a simple affine transformation.

Nonlinearity: $\tanh$

$$\begin{array}{r}y=\tanh (x)=\frac{e^x+e^{-x}}{e^x-e^{-x}}\end{array}$$

Nonlinearity: $\mathrm{sigmoid}$

$$\begin{array}{r}y=\sigma (x)=\frac{1}{1+e^{-x}}\end{array}$$

$$\begin{array}{rl}\sigma (x)& =\frac{1}{1+e^{-x}}\\ \tanh (x)& =\frac{e^x-e^{-x}}{e^x+e^{-x}}\text{divide both sides by }{e}^x\\ & =\frac{1-e^{-2x}}{1+e^{-2x}}\\ & =\sigma (2x)-(1-\sigma (2x))=2\sigma (2x)-1\end{array}$$

Nonlinearity: $\mathrm{ReLU}$

$$\begin{array}{r}y=\mathrm{ReLU}(x)=\max \{0,x\}\end{array}$$

Sentiment Classification with Neural Networks

$$\begin{array}{rl}{\mathbf{z}}^{(1)}& =g\left({\mathbf{W}}^{(0)}\mathbf{x}+{\mathbf{b}}^{(0)}\right)\\ s& ={\mathbf{W}}^{(1)}{\mathbf{z}}^{(1)}+{\mathbf{b}}^{(1)}\end{array}$$

We empirically don’t pass the final layer into an activation function.

Question

How can we get $\mathbf{x}$ for a sentence?

Average word embeddings, or more complicated neural network structures.

Neural Network: Training

$$\begin{array}{r}\mathbf{s}=\left[\begin{array}{c}\mathrm{score}(\mathbf{x},0;\mathbf{w})\\ \mathrm{score}(\mathbf{x},1;\mathbf{w})\end{array}\right]\stackrel{\mathrm{softmax}}{⟹}\mathbf{p}=\left[\begin{array}{c}\frac{e^{\mathrm{score}(\mathbf{x},0;\mathbf{w})}}{Z}\\ \frac{e^{\mathrm{score}(\mathbf{x},1;\mathbf{w})}}{Z}\end{array}\right]\\ Z=e^{\mathrm{score}(\mathbf{x},0;\mathbf{w})}+e^{\mathrm{score}(\mathbf{x},1;\mathbf{w})}\end{array}$$

Maximize the probability (minimizing the negative log probability) of gold standard label.

$$\begin{array}{r}\mathrm{loss}=-\log P(y|x)=-\log \left(\frac{e^{\mathrm{score}(\mathbf{x},y;\mathbf{w})}}{Z}\right)\end{array}$$

Also called cross entropy loss.

Backpropagation

Chain rule: suppose $y=f(x)$, $z=g(y)$, then $\frac{\mathrm{d}z}{\mathrm{d}x}=\frac{\mathrm{d}z}{\mathrm{d}y}\cdot \frac{\mathrm{d}y}{\mathrm{d}x}$

$$\begin{array}{rl}{\mathbf{z}}^{(1)}& =g\left({\mathbf{W}}^{(0)}\mathbf{x}+{\mathbf{b}}^{(0)}\right)\\ s& ={\mathbf{W}}^{(1)}{\mathbf{z}}^{(1)}+{\mathbf{b}}^{(1)}\\ \mathrm{loss}(\mathbf{s};\mathbf{x},y)& =-\log \left(\frac{e_y^s}{Z}\right)\end{array}$$

Question

Now we have $\frac{\partial \mathrm{loss}}{\partial \mathbf{s}}$, how should we update ${\mathbf{W}}^{(0)}$.

$$\begin{array}{r}\frac{\partial \mathrm{loss}}{\partial {\mathbf{W}}^{(0)}}=\frac{\partial \mathrm{loss}}{\partial s}\frac{\partial s}{\partial {\mathbf{z}}^{(1)}}\frac{\partial {\mathbf{z}}^{(1)}}{\partial {\mathbf{W}}^{(0)}}\end{array}$$

What is actually happening is the concatenation as below.

$$\begin{array}{r}\frac{\partial z^{(1)}}{\partial {\mathbf{W}}^{(0)}}=\left(\sum _{z\in Z^{(1)}}\frac{\partial {\mathbf{z}}^{(1)}}{\partial {\mathbf{w}}_{i,j}^{(0)}}\right)\end{array}$$

We calculate as they are scalars, and then reform to get the original shape of the matrix.

Visualization of an Average Word Vector Classifier

$$\begin{array}{rl}\mathbf{s}& ={\mathbf{W}}^{(1)}{\mathbf{z}}^{(1)}+{\mathbf{b}}^{(1)}\\ {\mathbf{z}}^{(1)}& =g\left({\mathbf{W}}^{(0)}\mathbf{x}+{\mathbf{b}}^{(0)}\right)\\ \mathbf{x}& =\frac{1}{k}\sum _{i=1}^k\mathrm{emb}(w_k)\end{array}$$

Common Neural Architectures

Convolutional Neural Networks

$$\begin{array}{ccccc}\left[\begin{array}{cccccc}1& 0& 1& 0& 1& 0\\ 0& 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 1& 1& 0\\ 0& 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1& 0\end{array}\right]& \stackrel{\text{extract patch}}{\to }& \left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 1& 0& 1\end{array}\right]& \times & \left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]\\ \text{Input image}& & \text{Image patch}& & \text{Kernel}\end{array}$$ $$\begin{array}{c}\text{Output value}\\ \left[\begin{array}{c}31\end{array}\right]\end{array}$$

Introduced for vision tasks; also used in NLP to extract feature vectors.

We apply kernels (filters) to image patches (local receptive fields). The kernels are learnable.

Take the dot product between the filter and the stretched word embeddings.

Lecture 6

Pooling

Each kernel/filter extracts one type of feature.

A kernel’s output size depends on sentence length. A fixed dimensional vector is desirable for MLP inputs.

Solution: Mean pooling/max pooling converts a vector to a scalar.

Final feature: Concatenating pooling results of all filters.

Word order matters

Example

Kernel size $=2$ ‘a cat drinks milk’ $\to$ (a cat), (cat drinks), (drinks milk) ‘a milk drinks cat’ $\to$ (a milk), (milk drinks), (drinks cat)

An $n$-gram “matches” with a kernel when they have high dot product.

Drawbacks

Cannot capture long-term dependency. Often used for character-level processing: filters look at character $n$-grams.

Recurrent Neural Networks (RNNs)

Idea: Apply the same transformation to tokens in time order.

$h_t=W[x_t;h_{t-1}]+b$

$h_{t+1}=W[x_{t+1};h_t]+b$

flowchart LR
a[xt-1]
b[xt]
c[xt+1]
d[ht-1]
e[h_t]
f[ht+1]
a --> d
d --> e
b --> e
e --> f
c --> f

Gradient update for ${\mathbf{h}}_t=\mathbf{W}[x_t;{\mathbf{h}}_{t-1}]+\mathbf{b}$.

Suppose ${\mathbf{h}}_k$ is the representation passed to the classifier.

We can easily calculate $\frac{\partial \mathrm{loss}}{\partial {\mathbf{h}}_k}$.

Question

What about $\frac{\partial \mathrm{loss}}{\partial \mathbf{W}}$.

$$\begin{array}{rl}\frac{\partial \mathrm{loss}}{\partial \mathbf{W}}& =\sum _{t=1}^k\frac{\partial \mathrm{loss}}{\partial {\mathbf{h}}_t}\frac{\partial {\mathbf{h}}_t}{\partial \mathbf{W}}\\ \frac{\partial \mathrm{loss}}{\partial {\mathbf{h}}_t}& =\frac{\partial \mathrm{loss}}{\partial {\mathbf{h}}_{t+1}}\frac{\partial {\mathbf{h}}_{t+1}}{\partial {\mathbf{h}}_t}\end{array}$$

Bug

An important issue of simple RNNs.

$$\begin{array}{rl}{\mathbf{h}}_t& =\mathbf{W}[x_t;{\mathbf{h}}_{t-1}]+\mathbf{b}\\ & =\mathbf{W}[x_t;(\mathbf{W}[{\mathbf{x}}_{t-1}{\mathbf{h}}_{t-2}]+\mathbf{b})]+\mathbf{b}\end{array}$$

Absolute value of entries grow and vanish exponentially with respect to sequence length.

This motivates the development of more advanced RNN architecture.

Long Short-Term Memory Networks (LSTMs)

Designed to tackle the gradient vanishing problem.

$$\begin{array}{rlrl}& \text{Forget gate: }& & {\mathbf{f}}_t=\sigma ({\mathbf{W}}_f[{\mathbf{x}}_t;{\mathbf{h}}_{t-1}]+{\mathbf{b}}_f)\\ & \text{Input gate: }& & {\mathbf{i}}_t=\sigma ({\mathbf{W}}_i[{\mathbf{x}}_t;{\mathbf{h}}_{t-1}]+{\mathbf{b}}_i)\\ & \text{Cell: }& & {\tilde{\mathbf{c}}}_t=\tanh ({\mathbf{W}}_c[{\mathbf{x}}_t;{\mathbf{h}}_{t-1}]+{\mathbf{b}}_c)\\ & \text{Update: }& & {\mathbf{c}}_t\cdot {\mathbf{c}}_{t-1}+{\mathbf{i}}_t\cdot {\tilde{\mathbf{c}}}_t\\ & \text{Output gate: }& & {\mathbf{o}}_t=\sigma ({\mathbf{W}}_o[{\mathbf{x}}_t;{\mathbf{h}}_{t-1}]+{\mathbf{b}}_o)\\ & \text{Hidden state: }& & {\mathbf{h}}_t={\mathbf{o}}_t\times \tanh ({\mathbf{c}}_t)\end{array}$$

Idea: Keep entries in ${\tilde{\mathbf{c}}}_t$ and ${\mathbf{h}}_t$ in the range of $(-1,1)$.

Gated Recurrent Units

Fewer parameters and generally works quite well.

• Update gate: ${\mathbf{z}}_t=\sigma ({\mathbf{W}}_z[{\mathbf{x}}_t;{\mathbf{h}}_{t-1}]+{\mathbf{b}}_z)$
• Reset gate: ${\mathbf{r}}_t=\sigma ({\mathbf{W}}_r[{\mathbf{x}}_t;{\mathbf{h}}_{t-1}]+{\mathbf{b}}_r)$

$$\begin{array}{r}{\mathbf{h}}_t=(1-{\mathbf{z}}_t)\cdot {\mathbf{h}}_{t-1}+{\mathbf{z}}_t\cdot \tanh (\mathbf{W}[{\mathbf{x}}_t;{\mathbf{r}}_t\cdot {\mathbf{h}}_{t-1}]+\mathbf{b})\end{array}$$

Forget gate is just 1 minus the input gate. Reset gate is applied to the previous hidden contribution.

RNN: Practical Approaches

Gradient clip: Gradient sometimes goes very large even with LSTMs. Empirical solution: After calculating gradients, require the $L_2$ norm to be at most $C$, set by hyperparameters.

At time step $t$, what matters to ${\mathbf{h}}_t$ is mostly ${\mathbf{x}}_{t^{\prime }}$ where $t^{\prime }$ is close to $t$.

Bidirectional modeling typically results in more powerful features.

Recursive Neural Networks

Run constituency parser on sentence, and construct vector recursively. All nodes share the same set of parameters.

flowchart BT
a[h5]
b[h1]
c[h4]
d[h2]
e[h3]
b --> a
c --> a
d --> c
e --> c

$$\begin{array}{r}{\mathbf{h}}_5=g(\mathbf{W}[{\mathbf{h}}_1;{\mathbf{h}}_4]+\mathbf{b})\\ {\mathbf{h}}_4=g(\mathbf{W}[{\mathbf{h}}_2;{\mathbf{h}}_3]+\mathbf{b})\end{array}$$

Tree LSTMs typically work well. Slight modification of LST cells needed.

$$\begin{array}{rl}& {\mathbf{f}}_t=\sigma ({\mathbf{W}}_{\ell }[{\mathbf{h}}_{\ell };{\mathbf{h}}_r]+{\mathbf{b}}_{\ell })\\ & {\mathbf{r}}_n=\sigma ({\mathbf{W}}_r[{\mathbf{h}}_{\ell };{\mathbf{h}}_r]+{\mathbf{b}}_r)\\ & {\tilde{\mathbf{c}}}_t=\tanh ({\mathbf{W}}_c[{\mathbf{h}}_{\ell };{\mathbf{h}}_r]+{\mathbf{b}}_c)\\ & {\mathbf{c}}_n\cdot {\mathbf{l}}_n\cdot {\mathbf{c}}_{\ell }+{\mathbf{r}}_n\cdot {\mathbf{c}}_r+{\tilde{\mathbf{c}}}_n\\ & {\mathbf{o}}_n=\sigma ({\mathbf{W}}_o[{\mathbf{h}}_{\ell };{\mathbf{h}}_r]+{\mathbf{b}}_o)\\ & {\mathbf{h}}_n={\mathbf{o}}_n\times \tanh ({\mathbf{c}}_n)\end{array}$$

Recursive neural networks with left-branching trees are basically equivalent to recurrent neural networks.

Syntactically meaningful parse trees are not necessary for good representations. Balanced trees work well for most tasks.

Attention

Can be thought of as weighted sum; each token receives weight.

From (unweighted) bag of words to (weighted) bag of words. Each word receives a fixed weight, normalize the weights with $\mathrm{softmax}$.

$$\begin{array}{rl}{\alpha }_{w_i}& ={\mathrm{softmax}}_{i^{\prime }=1}^k(weigh{t}_{w_i})=\frac{e^{weigh{t}_{w_i}}}{{\sum }_{i^{\prime }=1}^k{e}^{weigh{t}_{w_i^{\prime }}}}\\ \mathbf{x}& =\sum _{i=1}^k{\alpha }_{w_i}\cdot emb(w_i)\end{array}$$

Parameterized attention: Word tokens with the same word type should probably receive different weights in different sentences. Implement attention with an MLP.

$$\begin{array}{rl}\bar{\mathbf{x}}& =\frac{1}{k}\sum _{i=1}^{k}emb(w_i)\\ \alpha (w_i|\bar{\mathbf{x}})& ={\mathrm{softmax}}_{i^{\prime }=1}^k(\mathrm{MLP}([emb(w_i);\bar{\mathbf{x}}]))\in \mathbb{R}\\ \mathbf{x}& =\sum _{i=1}^k\alpha (w_i|\bar{\mathbf{x}})\cdot emb(w_i)\end{array}$$

Self-Attentive RNNs

The last hidden state of RNN could be a bad feature. Why?

At time step $t$, what matters to ${\mathbf{h}}_t$ is mostly ${\mathbf{x}}_t^{\prime }$ where $t^{\prime }$ is close to $t$.

$$\begin{array}{rl}{\alpha }_i& ={\mathrm{softmax}}_{i^{\prime }=1}^k(\mathrm{MLP}({\mathbf{h}}_i))\in \mathbb{R}\\ \mathbf{x}& =\sum _{i=1}^k{\alpha }_i{\mathbf{h}}_i\end{array}$$

Attention weights over RNN hidden states could be bad indicators on which token is more important.

Lecture 7

Transformer: Attention-based sentence encoding, and optionally, decoding.

Idea: Every token has “attention” to every other token.

For sentence with tokens $(w_1,\dots ,w_k)$.

$$\begin{array}{rlrl}\mathbf{E}& =(emb(w_1),\dots ,emb(w_k))& & \in {\mathbb{R}}^{d_1\times k}\\ \mathbf{K}& ={\mathbf{W}}_k\mathbf{E}& & {\mathbf{W}}_k\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{Q}& ={\mathbf{W}}_q\mathbf{E}& & {\mathbf{W}}_q\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{V}& ={\mathbf{W}}_v\mathbf{E}& & {\mathbf{W}}_v\in {\mathbb{R}}^{d_3\times d_1}\end{array}$$

${\mathbf{W}}_{k|q|v}$ are trainable parameters.

$$\begin{array}{rlrl}\mathbf{E}& =(emb(w_1),\dots ,emb(w_k))& & \in {\mathbb{R}}^{d_1\times k}\\ \mathbf{K}& ={\mathbf{W}}_k\mathbf{E}& & {\mathbf{W}}_k\in {\mathbb{R}}^{d_2\times d_1},\mathbf{K}\in {\mathbb{R}}^{d_2\times k}\\ \mathbf{Q}& ={\mathbf{W}}_q\mathbf{E}& & {\mathbf{W}}_q\in {\mathbb{R}}^{d_2\times d_1},\mathbf{Q}\in {\mathbb{R}}^{d_2\times k}\\ \mathbf{V}& ={\mathbf{W}}_v\mathbf{E}& & {\mathbf{W}}_v\in {\mathbb{R}}^{d_3\times d_1},\mathbf{V}\in {\mathbb{R}}^{d_3\times k}\end{array}$$ $$\begin{array}{r}\boxed{\tilde{E}=\mathbf{V}\mathrm{softmax}\left(\frac{{\mathbf{K}}^{⊺}\mathbf{Q}}{\sqrt{d_2}}\right)}\end{array}$$

Question

What is $\sqrt{d_2}$ for?

Question

Consider $⟨\mathbf{a},\mathbf{b}⟩$: if each entry in both vector is drawn from a distribution with zero mean and unit variance, what would happen if the dimensionality grows?

The variance of the dot product grows.

$\mathrm{softmax}([-1,1])=[0.8808,0.1192]$

$\mathrm{softmax}([10,-10])=[1,2.0612\times 10^{-9}]$

For independent zero-mean, unit-variance random variables $X$ and $Y$, recall (STAT230)

$$\begin{array}{rl}\mathrm{Var}& =\mathbb{E}[X^2{Y}^2]-{\mathbb{E}}^2[XY]\\ & =(\mathrm{Cov}[X^2,Y^2]+\mathbb{E}[X^2][Y^2])-(\mathrm{Cov}[X,Y]+\mathbb{E}[X]\mathbb{E}[Y]{)}^2\\ & =\mathbb{E}[X^2]\mathbb{E}[Y]-{\mathbb{E}}^2[X]{\mathbb{E}}^2[Y]\\ & =\mathrm{Var}[X]\mathrm{Var}Y+\mathrm{Var}[X]{\mathbb{E}}^2[Y]+\mathrm{Var}[Y]{\mathbb{E}}^2[X]\\ & =1\end{array}$$

For independent zero-mean, unit-variance random variables $X$ and $Y$ $\mathrm{Var}[XY]=1$.

If we have $2n$ independent zero-mean, unit variance variables $X_1,Y_1,X_2,Y_2,\dots ,X_n,Y_n$.

$$\begin{array}{rl}& \mathrm{Var}\left[\sum _{i=1}^n{X}_i{Y}_i\right]=\sum _{i=1}^n\mathrm{Var}[X_i{Y}_i]=n\\ & \mathrm{Var}\left[\sum _{i=1}^n\frac{X_i{Y}_i}{\sqrt{n}}\right]=\sum _{i=1}^n\mathrm{Var}\left[\frac{X_i{Y}_i}{\sqrt{n}}\right]=\sum _{i=1}^n\frac{1}{n}\mathrm{Var}[X_i{Y}_i]=1\end{array}$$

Transformer Encoder

$$\begin{array}{rl}& \mathrm{Var}\left[\sum _{i=1}^n\frac{X_i{Y}_i}{\sqrt{n}}\right]=\sum _{i=1}^n\mathrm{Var}\left[\frac{X_i{Y}_i}{\sqrt{n}}\right]=\sum _{i=1}^n\frac{1}{n}\mathrm{Var}[X_i{Y}_i]=1\\ & \tilde{\mathbf{E}}=\mathbf{V}\mathrm{softmax}\left(\frac{{\mathbf{K}}^{⊺}\mathbf{Q}}{\sqrt{d_2}}\right)\end{array}$$

The application of $\sqrt{d_2}$ is theoretically motivated.

See also Xavier initialization: initialize a dot product parameter vector with values drawn from $U\left(-\sqrt{\frac{3}{d}},\sqrt{\frac{3}{d}}\right)$

Positional Encoding

Columns of $\tilde{\mathbf{E}}$ for “a cat” $=$ permutation of columns of $\tilde{\mathbf{E}}$ for “cat a”.

$$\begin{array}{r}{\mathbf{p}}_{p,2i}=\sin \left(\frac{p}{10000^{\frac{2i}{d}}}\right),{\mathbf{p}}_{p,2i+1}=\cos \left(\frac{p}{10000^{\frac{2i}{d}}}\right)\end{array}$$

The choice of $n=10,000$ is somewhat arbitrary, but it’s overall theoretically motivated: The positional add$-\delta$ relation can be represented by a linear transformation.

$$\begin{array}{r}\forall \delta ,\exists {\mathbf{M}}_{\delta },\text{ s.t. }{\mathbf{p}}_{p+\delta }={\mathbf{M}}_{\delta }{\mathbf{p}}_p(\forall p)\end{array}$$

Proof idea: Use the addition theorems on trigonometric functions.

Limitation: Only fixed number of positions are available. Another option is learnable positional encoding.

$$\begin{array}{rlrl}\mathbf{E}& =(emb(w_1),\dots ,emb(w_k))+P& & \in {\mathbb{R}}^{d_1\times k}\\ \mathbf{K}& ={\mathbf{W}}_k\mathbf{E}& & {\mathbf{W}}_k\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{Q}& ={\mathbf{W}}_q\mathbf{E}& & {\mathbf{W}}_q\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{V}& ={\mathbf{W}}_v\mathbf{E}& & {\mathbf{W}}_v\in {\mathbb{R}}^{d_3\times d_1}\\ \tilde{\mathbf{E}}& =\mathbf{V}\mathrm{softmax}\left(\frac{{\mathbf{K}}^{⊺}\mathbf{Q}}{\sqrt{d_2}}\right)& & \end{array}$$

Multi-Head Attention

We can parallelize multiple ${\mathbf{W}}_k$, ${\mathbf{W}}_q$, ${\mathbf{W}}_v$, with different random initialization (and hope they learn different ways to attend tokens).

We stack transformer layers. Earlier layers’ output are added to the vector stream.

Normalization: Preserve variance:

$$\begin{array}{rlrl}\mathbf{E}& =\mathrm{Normalized}(E^{(0)}+P+\tilde{\mathbf{E}})& & \\ \mathbf{K}& ={\mathbf{W}}_k\mathbf{E}& & {\mathbf{W}}_k\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{Q}& ={\mathbf{W}}_q\mathbf{E}& & {\mathbf{W}}_q\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{V}& ={\mathbf{W}}_v\mathbf{E}& & {\mathbf{W}}_v\in {\mathbb{R}}^{d_3\times d_1}\\ \tilde{\mathbf{E}}& =\mathbf{V}\mathrm{softmax}\left(\frac{{\mathbf{K}}^{⊺}\mathbf{Q}}{\sqrt{d_2}}\right)& & \end{array}$$

Lecture 8

Recap: Distributional Semantics

Language Models: General Formulation

Language models compute a probability distribution over strings in a language: $P(x)$, $x$ is a string with tokens $x_1,x_2,\dots ,x_n$.

Language modeling: Assign probabilities to token sequences.

Modeling: Define a statistical model $P_{\theta }(x)$, where $x$ is a string.

Learning: Estimate the parameters $\theta$ from data.

Goal - compute the probability of a sequence of words.

$$\begin{array}{r}P(x_{1:n})=P(x_1,x_2,\dots ,x_n)\end{array}$$

Relatedly, modeling probability of the next word:

$$\begin{array}{r}P(x_n\mid x_1,x_2,\dots ,x_{n-1})\end{array}$$

Relatedly, modeling the probability of a masked word given its context

$$\begin{array}{r}P(x_k\mid x_1,\dots ,x_{k-1},x_{k+1},\dots ,x_n)\end{array}$$

A model that computes any of the above is called a language model. A good language model will assign higher probabilities to sentences that are more likely to appear.

Question

How do we model this?

Recap: The chain rule of probability

$$\begin{array}{r}P(A,B)=P(A)P(B\mid A)\end{array}$$ $$\begin{array}{rl}P(x_{1:n})& =P(x_1,x_2,\dots ,x_n)\\ & =P(x_1)P(x_2\mid x_1)P(x_3\mid x_1,x_2)\dots P(x_n\mid x_1,\dots ,x_{n-1})\end{array}$$

We haven’t yet made independence assumptions.

This is autoregressive language modeling.

Important detail: Modeling length

A language model assigns probability to token sequences $x$. $x$ can be of any length, and the probabilities should sum to 1 across all possible sequences of different lengths.

Usually length is modelled by including a stop symbol </s> at the end of each sequence. Predicting </s> = modeling stopping probabilities. Relatedly, a start symbol <s> should be added to the beginning.

Language model with both start and stop symbols:

$$\begin{array}{r}P(x_{1:n})=P(⟨/s⟩\mid ⟨s⟩,x_1,\dots ,x_n)\prod _{i=1}^{n}P(x_i\mid ⟨s⟩,x_1,\dots ,x_{i-1})\end{array}$$

We need to ensure:

$$\begin{array}{r}\sum _{n=1}^{\infty }\sum _{x_{1:n}}P(x_{1:n})=1\end{array}$$

Consider removing stopping probabilities

$$\begin{array}{r}P(x_{1:n})=\prod _{i=1}^{n}P(x_1\mid ⟨s⟩,x_1,\dots ,x_{i-1})\end{array}$$

Question

What happens if we don’t model stopping probability?

Sums of probabilities for all possible length$-1$ and length$-2$ sequences:

$$\begin{array}{rl}\sum _{n=1}^1\sum _{x_{1:n}}P(x_{1:n})& =\sum _{x\in V}P(x\mid ⟨s⟩)=1\\ \sum _{n=2}^2\sum _{x_{1:n}}P(x_{1:n})& =\sum _{x\in V}\sum _{x^{\prime }\in V}P(x\mid ⟨s⟩,x^{\prime })P(x^{\prime }\mid ⟨s⟩)=1\end{array}$$ $$\begin{array}{r}\sum _{n=1}^2\sum _{x_{1:n}}P(x_{1:n})=1+1=2>1\end{array}$$

With the stop symbol

$$\begin{array}{r}\sum _{n=1}^{\infty }\sum _{x_{1:n}}P(x_{1:n},⟨/x⟩)=\sum _{n=1}^{\infty }\sum _{x_{1:n}}P(x_{1:n})P(⟨/s⟩\mid x_{1:n})\end{array}$$

Proof sketch: Once you reach the </s> token after sampling some certain sequence, certain probability mass is taken away because <s> is in the same distribution as other vocabulary entries.

Longer sequences that have the same prefix share the remaining probability.

Alternatively, we can model the length $n$ explicitly (e.g., using a zero-truncated Poisson distribution).

$$\begin{array}{r}P(x_{1:n})=P(n)\prod _{i=1}^{n}P(x_1\mid ⟨s⟩,x_1,\dots ,x_{i-1})\end{array}$$

Estimating language model probabilities.

<s>I do not like green eggs and ham</s>

$P(\text{ham}|\text{<s> I do not like green eggs and})$

We can use maximum likelihood estimation (from STAT231)

$$\begin{array}{r}P(\text{ham}|\text{<s> I do not like green eggs and})=\frac{\mathrm{count}(\text{<s> I do not like green eggs and ham})}{\mathrm{count}(\text{<s> I do not like green eggs and})}\end{array}$$

Problem: We will never have enough data.

Markov Assumption

Independence assumption: The next word only depends on the most recent past (most recent $k$ words). Reduces the number of estimated parameters in exchange for modeling capacity.

$$\begin{array}{r}P(x_1|⟨s⟩,x_1,\dots ,x_{i-2},x_{i-1})\approx P(x_i|x_{i-k},\dots ,x_{i-2},x_{i-1})\end{array}$$

1st order Markov: $k=1$. $P(\text{mat}\mid \text{the cat sat on the})\approx P(\text{mat}\mid \text{the})$.

2nd order Markov: $k=2$. $P(\text{mat}|\text{the cat sat on the})\approx P(\text{mat}|\text{on the})$.

N-Gram Language Models

$n=1$: Unigram language model

$$\begin{array}{r}P(\text{I})P(\text{do})P(\text{like})P(\text{green})P(\text{eggs})\cdots \end{array}$$

$n=2$: Bigram language model

$$\begin{array}{r}P(\text{I}\mid ⟨s⟩)P(\text{do}\mid \text{I})P(\text{not}\mid \text{do})P(\text{like}\mid \text{not})\cdots P(\text{ham}\mid \text{and})P(⟨/s⟩\mid \text{ham})\end{array}$$

Recap:

$$\begin{array}{r}\mathrm{classify}(s)=\stackrel{\text{Inference: solve }\arg \max }{\overbrace{\arg \underset{y}{\max }}}\underset{\text{Modeling: define score function}}{\underbrace{\mathrm{score}}}(s,y;\stackrel{\text{Learning: choose parameter}}{\overbrace{\theta }})\end{array}$$

Modeling, learning, and inference

$$\begin{array}{r}\mathrm{nextword}(s)=\arg \underset{y}{\max }\mathrm{score}(s,y;\theta )\end{array}$$

Estimating n-gram probabilities

Maximum likelihood estimate (MLE):

$$\begin{array}{r}P(x\mid x^{\prime })=\frac{\mathrm{count}(x^{\prime },x)}{\mathrm{count}(x^{\prime })}\end{array}$$

Training data:

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

A few estimated bigram probabilities given our MLE estimator:

$$\begin{array}{rlrlrlr}P(\text{I}\mid ⟨s⟩)& =\frac{2}{3}& & P(\text{am}\mid \text{I})=\frac{2}{3}& & & P(\text{Sam}\mid \text{am})=\frac{1}{2}\\ P(\text{Sam}\mid ⟨s⟩)& =\frac{1}{3}& & P(\text{do}\mid \text{I})=\frac{1}{3}& & & P(⟨/s⟩\mid \text{am})=\frac{1}{2}\end{array}$$

Test data: <s> I like green eggs and ham</s>

Problem: $P(\text{like}\mid \text{I})+0$. This is an over-penalization

Smoothing in n-gram LMs, just add 1 to all counts. This is Laplace smoothing.

MLE Estimate

$$\begin{array}{r}{P}_{\text{MLE}}(x\mid x^{\prime })=\frac{\mathrm{count}(x^{\prime },x)}{\mathrm{count}(x^{\prime })}\end{array}$$

Add-1 estimate:

$$\begin{array}{r}{P}_{\text{add-1}}(x\mid x^{\prime })=\frac{\mathrm{count}(x^{\prime },x)+1}{\mathrm{count}(x^{\prime })+\underset{\text{vocabularay size}}{\underbrace{|\mathcal{V}|}}}\end{array}$$

Greedy search: Choose the most likely word at every step.

To predict the next word given the previous two words $w_1,w_2.w_3=\arg \underset{w\in V}{\max }P(w\mid w_1,w_2)$.

Problem is we will generate the same sentence many times, and may be missing out on a higher probability continued sentences (multiple words down the line).

Bigram model - sampling

• Generate the first word: $w_1\sim P(x_1\mid ⟨s⟩)$.
• Generate the second word: $w_2\sim P(x_2\mid x_1)$.
• Generate the third word: $w_3\sim P(x_3\mid x_2)$.

Generating from a language model

Two effective sampling strategies: excluding the possibility for tokens with very-low probabilities. Top-$k$ vs top-$p$ sampling.

Top-$k$, sort all vocabulary in terms of the next token probability, only take top $k$.

Top-$p$, do the same thing, but don’t fix the number of tokens, fix the portion of cumulative probability mass we are considering. Number of tokens we take is a function of $p$.

A good language model will assign higher probabilities to sentences that are more likely to appear.

Compute probability on held-out data. Standard metric is perplexity.

Probability of held-out sentences:

$$\begin{array}{r}\prod _{i}P(x^{(i)})\end{array}$$

Let’s work with $\log$-probabilities:

$$\begin{array}{r}{\log }_2\prod _{i}P(x^{(i)})=\sum _i{\log }_{2}P(x^{(i)})\end{array}$$

Divide by number of words $M$ (including stop symbols) in held-out sentences:

$$\begin{array}{r}\frac{1}{M}\sum _i{\log }_{2}P(x^{(i)})\end{array}$$

From probability $\to$ perplexity.

Average token $\log$-probability of held-out data:

$$\begin{array}{r}\ell =\frac{1}{M}\sum _i{\log }_{2}P(x^{(i)})\end{array}$$

Perplexity:

$$\begin{array}{r}\mathrm{ppl}=2^{\boxed{-\ell }}\ell \text{ is cross-entropy loss}\end{array}$$

The lower the perplexity, the better the model

$$\begin{array}{r}\mathrm{ppl}={\left(\prod _{i}P(x^{(i)})\right)}^{-\frac{1}{M}}\end{array}$$

Lecture 9

Neural Language Modeling

Recap: Language Modeling as Classification

$$\begin{array}{r}P(x_{1:n})=P(x_1,x_2,\dots ,x_n)=P(⟨/s⟩\mid x_1,\dots ,x_n)=\prod _{i=1}^{n}P(x_i\mid x_1,x_2,\dots ,x_{i-1})\end{array}$$

This is just a probabilistic classification problem.

Neural Trigram Language Model

Given two previous words, compute probability distribution over possible next words.

$$\begin{array}{r}P(x\mid x^{\prime },x^{\prime \prime })\end{array}$$

Input is concatenation of vectors (embeddings) of previous two words.

$$\begin{array}{r}\mathbf{c}=\mathrm{cat}(emb(x^{\prime }),emb(x^{\prime \prime }))emb(\cdot )\in {\mathbb{R}}^d\end{array}$$

Output is a vector $S$ containing probabilities of all possible next words.

To get $S$, do matrix multiplication of parameter matrix $W$ and input, then $\mathrm{softmax}$ transformation.

$$\begin{array}{r}s=\mathrm{softmax}(\mathbf{Wc})\\ \mathbf{W}\in {\mathbb{R}}^{|V|\times 2d}\mathbf{c}\in {\mathbb{R}}^{2d}\end{array}$$

Neural Trigram Language Model

$$\begin{array}{rl}{P}_{\Theta }(x_t\mid x_1,\dots ,x_{t-1})& =s_{x_t}\\ \text{loss }L& =-\sum _i\log P_{\Theta }(x^{(i)})\\ & =-\sum _i\sum _j\log P_{\Theta }(x_j^{(i)}\mid x_1^{(i)},\dots ,x_{j-1}^{(i)})\end{array}$$

$i$ denotes indices of sentences, $j$ denotes indices of tokens.

${\nabla }_{\Theta }L$ via backpropagation.

Trigram vs Neural Trigram LMs

Trigram language model: Separate parameters for every combination of $x$, $x^{\prime }$, $x^{\prime \prime }$, so approximately $|V{|}^3$ parameters. # of parameters is exponential in $n$-gram size. Most parameters are zero (even with smoothing).

Neural trigram language model: Only has $O(d|V|)$ parameters. $d$ can be chosen to scale # parameters up or down and are linear in $n$-gram size. Almost no parameters are zero. No explicitly smoothing, though smoothing is done implicitly via distributed representations.

Removing N-Gram Constraints

$$\begin{array}{rl}& P(x_i\mid x_1,x_2,\dots ,x_{i-1})\\ & x_i\stackrel{\text{look-up in }\mathbf{U}}{\to }{\mathbf{w}}_i\in {\mathbb{R}}^d\\ & x_1,x_2,\dots ,x_{i-1}\to \frac{1}{i}\sum _{j=1}^{i-1}{\mathbf{w}}_j\in {\mathbb{R}}^d\\ & P(w_1=v\mid x_1,x_2,\dots ,x_{i-1})\\ & ={\mathrm{softmax}}_v\mathbf{W}\left(\frac{1}{i}\sum _{j=1}^{i-1}{\mathbf{w}}_j\right)\mathbf{W}\in {\mathbb{R}}^{|V|\times d}\end{array}$$

RNN Language Models

Hidden stat is a function of previous hidden state and current input. Same weights at each state.

$$\begin{array}{rl}& {\mathbf{h}}_t=f({\mathbf{W}}_{hh}{\mathbf{h}}_{t-1}+{\mathbf{W}}_{xh}{\mathbf{x}}_t)\\ & P_{\theta }(x_t\mid x_1,\dots ,x_{t-1})={\mathrm{softmax}}_{x_t}({\mathbf{Wh}}_t)\end{array}$$

Vector for each word is combined with the history vector. Use last layer hidden state as new hidden representation, instead of the average of the previous.

$$\begin{array}{rl}{L}_t& =-\log P_{\Theta }(x_t\mid x_1,\dots ,x_{t-1})\\ \Theta & =\{\mathbf{U},{\mathbf{W}}_{xh},{\mathbf{W}}_{hh}\}\\ L& =\sum _t{L}_t\\ & =\sum _t-\log P_{\Theta }(x_t\mid x_1,\dots ,x_{t-1})\\ & =-\log P_{\Theta }(\mathbf{x})\end{array}$$

${\nabla }_{\Theta }L$ via back propagation.

Transformer Language Models

A token “attends” to all previous tokens.

$$\begin{array}{rlrl}\mathbf{E}& =(emb(w_1),\dots ,emb(w_k))+\mathbf{P}& & \in {\mathbb{R}}^{d_1\times k}\\ \mathbf{K}& ={\mathbf{W}}_k\mathbf{E}& & {\mathbf{W}}_k\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{Q}& ={\mathbf{W}}_q\mathbf{E}& & {\mathbf{W}}_q\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{V}& ={\mathbf{W}}_v\mathbf{E}& & {\mathbf{W}}_v\in {\mathbb{R}}^{d_3\times d_1}\\ \tilde{\mathbf{E}}& =\mathbf{V}\mathrm{softmax}\left(\frac{{\mathbf{K}}^{⊺}\mathbf{Q}}{\sqrt{d_2}}\right)& & {\mathbb{R}}^{d_3\times k}\end{array}$$

Use ${\tilde{\mathbf{E}}}_{.,k}$ as feature to predict the next token.

Language models encode knowledge about language.

The pre-training-finetuning paradigm: Language modeling, as the pre-training task, helps encode knowledge. The knowledge helps with downstream tasks. Use the hidden state as the feature for the downstream task.

Masked Language Models

Motivation: learning useful representations of text.

$$\begin{array}{rlrl}\mathbf{E}& =(emb(w_1),\dots ,emb(w_k))+\mathbf{P}& & \in {\mathbb{R}}^{d_1\times k}\\ \mathbf{K}& ={\mathbf{W}}_k\mathbf{E}& & {\mathbf{W}}_k\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{Q}& ={\mathbf{W}}_q\mathbf{E}& & {\mathbf{W}}_q\in {\mathbb{R}}^{d_2\times d_1}\\ \mathbf{V}& ={\mathbf{W}}_v\mathbf{E}& & {\mathbf{W}}_v\in {\mathbb{R}}^{d_3\times d_1}\\ \tilde{\mathbf{E}}& =\mathbf{V}\mathrm{softmax}\left(\frac{{\mathbf{K}}^{⊺}\mathbf{Q}}{\sqrt{d_2}}\right)& & {\mathbb{R}}^{d_3\times k}\end{array}$$

Replace token at position $i$ with a placeholder. Use ${\tilde{\mathbf{E}}}_{.,i}$ as feature to predict token at position $i$.

Probing

Question

What is encoded in a trained language model?

Empirical answer: linguistic probe.

Take a fixed model as the “frozen” filter feature extractor, train a lightweight model to predict labels.

Frozen: the base model never gets updated when training the lightweight model.

Confounding

Question

Does above-chance performance on held out data mean the model encode part-of-speech knowledge?

Not necessarily, the model might just encode word identity, and the probe learns to group them together.

Solution (control tasks): Draw conclusion $⟺$ performance on main task is significantly better than that on the control task.

Syntax: Constituency

Sentence: the cat is cute

Bracketing: ((the cat) is cute))

Task: given any span of words, is it a constituent?

Probing is required as candidate constituents may be of different lengths but MLP could only take a fixed dimensional vector.

Task: Given a constituent, what’s the label?

Constituent labels: Syntactic Substitutability

Pooling is required to accommodate the variable length of constituents.

Lecture 10

Phrase Structures/Constituency Grammar

Constituency grammars focus on the constituent relation.

Informally: Sentences have hierarchical structures.

A sentence is made up of two pieces:

• Subject, typically a noun phrase (NP)
• Predicate, typically a verb phrase (VP)

NPs and VPs are made up of pieces:

• A cat = (a + cat)
• Walked to the park = (walk + (to + (the + school)))

Each parenthesized phrase is a constituent in the constituent parse.

Constituent: A group of words that functions as a single unit.

Linguists try to determine constituents via constituency tests. A constituency test follows some rules to construct a new sentence, focusing on the constituent candidate of interests. If the constructed sentence looks good, we find some evidence about constituency.

Consider the sentence: Drunks could put off the customers.

Constituency Test: Coordination

Coordinate the candidate constituent with something else.

• Drunks could [put off the customers] and sing.
• Drunks could put off [the customers] and the neighbours.
• Drunks [could] and [would] put off the customers.

Constituency Test: Topicalization

Moving the candidate constituent to the front. Modal adverbs can be added to improve naturalness.

• $\dots$ and [the customers], drunks certainly could put off.
• $\dots$ and [customers], drunks could certainly put off the.

Constituency Test: Deletion

Delete the span of interest. Word orders can be changed to improve naturalness.

• Drunks could put off the customers [in the bar].
• Drunks could put off the customers [in the] bar.

Constituency Test: Substitution

Substitute the candidate constituent with the appropriate proform (pronoun/proverb etc.). Slight word over adjustment is allowed to improve naturalness.

• Drunks could [do so = put off the customers].
• Drunks could put [them = the customers] off.
• Drunks could put the [them = customers] off.

Constituency Parsing as Bracketing

Question

Brackets: Which spans of words are the constituents in a sentence?

Sentence: The main walked to the park.

Bracketing: ((the man) (walked (to (the park)))

The brackets can be translated into trees.

There are categories associated with constituents.

flowchart TD
a[NP]
b[NP]
c[the]
d[the]

S --> a
a -----> c
a -----> man
PP ----> to
PP --> b
b ---> d
b ---> park
S --> VP
VP -----> walked
VP --> PP

The internal nodes are called nonterminals, the leaves are called terminals. Non terminals connect to pre-terminals, which connect to terminals.

The head of a constituent is the most responsible/important word for the constituent label.

Question

Which word makes ‘the cat’ an NP?

Cat

Question

Which word makes ‘walked to the park’ a VP?

Walked

There are syntactic ambiguities. Consider the sentences ‘time flies like an arrow’ and ‘fruit flies like a banana’.

flowchart TD
a[NP]
b[NP]
c[NN]
d[NN]

S --> a
a --> c
c --> time
S --> VP
VP --> V
VP --> PP
V --> flies
PP --> P
PP --> b
P --> like
b --> DT
DT --> an
b --> d
d --> arrow

flowchart TD
x[NP]
b[NP]
c[NN]
d[NN]

S --> x
x --> ADJ
x --> c
ADJ --> fruit
c --> flies


S --> VP
VP --> VBP
VP --> b
VBP --> like

b --> DT
b --> d
DT --> a
d --> banana

NLP Task: Constituency Parsing

Given a sentence, output its constituency parse. Widely studied task with a rich history. Most studies are based on the Penn Treebank.

Constituency parsing with general formulation.

$$\begin{array}{rl}& \mathrm{parse}(x)=\arg \underset{y}{\max }\mathrm{score}(x,y:w)\\ & x:\text{sentence}\\ & y:\text{constituent parse tree}\end{array}$$

The score of a tree is defined by the sum of constituent scores

$$\begin{array}{r}\mathrm{score}(x,y:w)=\sum _{s\in y}\text{span-score}(s;y,w)\end{array}$$

Each span score can be modeled with a neural network.

Training objective: Let the collection of the true spans have the highest accumulated span scores among all parses.

$$\begin{array}{rl}& \mathrm{Loss}\mathcal{L}(w)=\max \left(0,\sum _{s\in \hat{y}}\text{span-score}(s;x,w)-\sum _{s\in y}\text{span-score}(s;x,w)+\delta \right)\\ & \hat{y}:\text{Tree with the highest score}\end{array}$$

Question

How do we solve this?

Constituency Parsing: Inference (solving $\arg \max$).

Let’s first assume $y$ is a binary unlabeled parse tree. Each node is either a terminal node or the parent of two other nodes. There is one root node.

The simplified CKY Algorithm

$f_{\ell ,r}:$ The maximum sum of subtree scores if [$\ell ,r$] is a constituent.

$f_{1,n}:$ The maximum possible sum of subtree scores if the sentence is fuller parsed.

$$\begin{array}{r}{f}_{\ell ,r}={\mathrm{score}}_{l,r}+\underset{l\le m<r}{\max }\{f_{l,m}+f_{m+1,r}\}\end{array}$$

Edge case: $f_{i,i}=0$.

Context-Free Grammar (CFG) (CS241)

A generative way to describe constituency parsing. A CFG defines some “rewrite rules” to rewrite nonterminals as other nonterminals or terminals.

In previous ‘the man walked to the park’ example, we would have a sequence of rewrites corresponding to a bracketing.

$$\begin{array}{rl}\text{S}& \to \text{NP VP}\\ \text{NP}& \to \text{DT NN}\\ \text{VP}& \to \text{VBD PP}\\ \text{PP}& \to \text{IN NP}\\ \text{NN}& \to \text{man}\\ \text{DT}& \to \text{the}\end{array}$$

Question

Why context-free?

A rule to rewrite NP does not depend the context of that NP. The left-hand size (LHS) of a rule is only a single non-terminal (without any other context).

Probabilistic Context-Free Grammar (PCFG)

We assign probabilities to rewrite rules.

Probabilities must sum to 1 for each left-hand side nonterminal. Given a sentence $s$ and its tree $T$, the probability of generating $s$ with rules $T$ in grammar $\mathcal{G}$ is $P(s,T:\mathcal{G})={\prod }_{r\in T}p(r)$, where $r$ denotes a rule.

Given a treebank, what is the MAP estimation of the PCFG?

$$\begin{array}{rl}p(A\to B)& =\frac{\mathrm{count}(A\to B)}{\mathrm{count}(A)}\\ P(A\to BC)& =\frac{\mathrm{count}(A\to BC)}{\mathrm{count}(A)}\end{array}$$

A PCFG assigns probabilities to sequences of rewrite operations that terminate in terminals, this sequence implies the natural-language yield, and bracketing of sentences.

CKY with PCFG Formalism

Find the max-probability tree for a sentence

$$\begin{array}{rl}\mathrm{score}(x,y:w)& =\log \prod _{r\in y}p(r:w_r)\mathrm{yield}(y)=x\\ & =\sum _{r\in y}\log p(r;w_r)\end{array}$$

$f_{\ell ,r,b}:$ the maximum possible log probability that words within range [ $\ell ,r$] are the outcome of a nonterminal label $b$.

$$\begin{array}{r}{f}_{\ell ,r,b}=\underset{(b\to ac)\in {\mathcal{R}}_b}{\max }\underset{\ell \le m<r}{\max }\log p(b\to ac)+f_{\ell ,m,a}+f_{m+1,r,c}\end{array}$$

Edge case: Set the appropriate $f_{i,i,\ell }=0$ when word $i$ could have label $\ell$, and otherwise $-\infty$.

Inside algorithm

Find the probability for generating a sequence from a certain non-terminal (counting all possible trees).

$$\begin{array}{r}P(s_{\ell \dots r},b)=\sum _{(b\to ac)\in {\mathcal{R}}_b}\sum _{l\le m<r}p(b\to ac)P(s_{\ell \dots m},a)P(s_{m+1\dots r},c)\end{array}$$

The Chomsky Normal Form (CNF)

For any free-form PCFG, there exists an equivalent PCFG in which each node has zero or two children. Trees satisfying the latter conditions are said to be in the Chomsky normal form.

To go from constituency to dependency, we need to propagate lexical heads up the tree, remove non-lexical parts, merge redundant nodes. Result is the dependency parse tree.

Dependency parses directly model the relation between words.

Lecture 11

Grounded Semantics: Meanings demonstrated from other sources of data in addition to the language systems.

Distributional Semantics

A bottle of tezgüino is on the table. Everybody likes tezgüino. Don’t have tezgüino before you drive.

Visually grounded semantics

Picture of tezgüino.

Symbol Grounding Problem

Symbol $\to$ meaning: How do we make sense of symbols?

Practical implication: Enable the reliably meaningful interaction between language models and humans/physical world.

Whether this is a stochastic parrot or semantic comprehension is under debate.

Grounding can be categorized into:

• A: Referential grounding
• B: Sensorimotor grounding
• C: Relational grounding
• D: Communicative grounding
• E: Epistemic grounding

A, B, C, E: Semantic (static) grounding

D: Communicative (dynamic) grounding

Recap: Text-Only Language Models

Two types of text-only ungrounded language models:

Autoregressive models, good for generation.

$$\begin{array}{r}{P}_{\Theta }(w_{n+1}\mid w_1,\dots ,w_n)\end{array}$$

Masked language models, good for feature extraction.

$$\begin{array}{r}{P}_{\Theta }(w_i\mid w_1,\dots ,w_{i-1},w_{i+1},w_n)\end{array}$$

Incorporating visual signals leads to two families of vision-language models.

BERT $\to$ joint visual semantic embeddings

GPT $\to$ generative vision-language models.

Joint Visual-Semantic Embeddings (and CLIP)

Idea: Encode visual and textual information into a shared space.

Embedding: Vector space

• Text encoder (turn text into vector)
• Image encoder (turn image into vector)

Design a loss function to “align” the two vector spaces. End up with one single vector space that encodes both.

Training data: Images and their descriptions.

Visual encoding: Convert an image to a fixed-dimensional vector representation.

Joint Visual-Semantic Embedding Space Objective

Idea: Matched image-caption pair should be closer than mismatched pairs in the embedding space.

$$\begin{array}{rl}{\Theta }^{\ast }=\arg \underset{\Theta }{\min }& +\sum _{(I^{+},T^{+},T^{-})}\max (0,\delta -\cos (I_{\Theta }^{+},T_{\Theta }^{-})+\cos (I_{\Theta }^{+},T_{\Theta }^{-}))\\ & +\sum _{(T^{+},I^{+},I^{-})}\max (0,\delta -\cos (T_{\Theta }^{+},I_{\Theta }^{+})+\cos (T_{\Theta }^{+},I_{\Theta }^{-}))\end{array}$$

This is triplet-based hinge loss. Anything close should be close in joint embedding space, anything far should be far.

Properties of the Joint Space

Images and text are close in a good joint embedding space if they are semantically related.

Example applications:

• Bidirectional image-caption retrieval
• Image captioning

Text in the training data can be at any level of granularity (words, phrases, sentences, paragraphs, etc.)

Contrastive Language-Image Pretraining (CLIP)

Image-to-text retrieval: Given a pool of text, model the probability of choosing the correct text; and vice versa.

$$\begin{array}{r}{\Theta }^{\ast }=\arg \underset{\Theta }{\min }{\mathbb{E}}_{[(I_1,T_1),\dots ,(I_n,T_n)]}\left[\sum _i-\log P_{\Theta }(T_i\mid I_i;[T_{1\dots n}])-\log P_{\Theta }(I_i\mid T_i;[I_{1\dots n}])\right]\end{array}$$ $$\begin{array}{r}{P}_{\Theta }(T_j\mid I_i;[T_{1\dots n}])=\mathrm{softmax}([T_{1\dots n}]\cdot I_j)=\frac{\exp (⟨I_i,T_j⟩)}{{\sum }_{k=1}^n\exp (⟨I_i,T_k⟩)}\end{array}$$

Generative vision-language models

Recap: Generative autoregressive language models

Text-only language models: Predicting the next token conditioned on the history.

Extending to Vision-Language Models (VLMs).

General VLM: Training Objective

$$\begin{array}{r}{\Theta }^{\ast }=\underset{\Theta }{\min }\sum _i\sum _j-\log P_{\Theta }(w_j^{(i)};{\text{Image}}^{(i)},w_j^{(i)},\dots ,w_{j-1}^{(i)})\end{array}$$

Loss function only calculated on textual positions.

Fine-Grained Vision-Language Tasks

• Object retrieval (assuming objects’ bounding boxes are given).
  • Cognitive plausibility: Recognizing objects is very easy for humans.
• Multimodal coreference resolution (without assuming bounding boxes)
• Phrase grounding: Mapping phrases to objects in the image.
• Dense captioning (reverse): Write a short description for each detected object.

Limitations of current VLMs

• Lack of physical knowledge, and the neural architecture makes it hard to incorporate knowledge.
• Poor in recognizing spatial relations.
• Lack of cultural diversity representation.

Lecture 12

Definition

Large Language Model: A computational agent capable of conversational interaction and text generation.

Fundamentally: A probabilistic model that predicts the next token in a sequence based on context.

Core Mechanism: Conditional generation. Input is context (prefix), and output is the probability distribution over next tokens.

Pretraining

Dataset of 100B to > 5T tokens. Task is next-token prediction on unlabeled texts, and the output is a base model.

ELIZA (1966)

Joseph Weizenbaum’s rule-based system simulating a Rogerian psychologist. The ELIZA effect: Humans easily form emotional connections with machines. Limitation is that there is no real understanding, purely pattern matching/rules.

Modern LLMs: Unlike rule-based systems, these learn language patterns and world knowledge from vast corpora.

The Knowledge Bottleneck

Human learning

Children learn ~7-10 words/day to reach adult vocabularies 30k-100k words. Most knowledge is acquired as a by-product of reading and contextual processing.

Machine Learning

Distributional Hypothesis: We learn meaning from the company words keep. The NLP revolution relies on this principle: learning syntax, semantics, and facts from data distribution.

Pretraining: The Core Idea

Definition

Pretraining: Learning knowledge about language and the world by iteratively predicting tokens in massive text corpora.

The Result: A pretrained model containing rich representations of syntax, semantics, and facts.

Foundation: Serves as the base for downstream tasks (QA, translation). This phase is self-supervised.

Question

What does a model learn by predicting the blank?

”With roses, dahlias, and peonies, I was surrounded by x” $\leftarrow$ learns ontology (category: flowers)

“The room wasn’t just big it was x” $\leftarrow$ learns semantics/intensity (enormous > big)

“The square root of 4 is x” $\leftarrow$ learns arithmetic/math

”The author of ‘A room of One’s Own’ is x” $\leftarrow$ learns world knowledge (Virginia Woolf)

Three major architectures

• Decoder-only (Generative: GPT-4, Llama)
• Encoder-only (Understanding: BERT)
• Encoder-decoder (Translation: T5, BART)

Decoder Architecture

Mechanism: Auto-regressive generation. Takes tokens as input and generates tokens one by one (left-to-right).

Causal: Masked attention ensures it can only see past tokens, not future ones.

Use Case: Generative tasks (text generation, code completion).

flowchart LR
a[The cat sat on]
b[Decoder-only model]
c[the]

a --> b
b --> c

Example

GPT-3, GPT-4, Llama, Claude, Mistral

We focus on decoders as they are the standard for generative LLMs.

Encoder Architrecture

Mechanism: Outputs a vector representation (encoding) for each input token.

Bidirectional: Can see context from both left and right directions simultaneously.

Training: Typically masked language modeling.

Use case: Classification, sentiment analysis, NER.

flowchart LR
a["The [MASK] sat on the mat"]
b[Encoder-only model]
c[cat]

a --> b
b --> c

Example

BERT, RoBERTa

Encoder-Decoder Architecture

Mechanism: Maps an input sequence of tokens to a (potentially different) output sequence.

Key feature: Decouples input understanding from output generation. Input and output can have different lengths.

Use case: Translation (english $\to$ french), summarization.

flowchart LR
a[Hello world]
b[Encoder]
c[Decoder]
d[le]
e[Bonjour]

a --> b
b --> c
c --> d
e --> c

The “Black box” view

Input: Sequence of tokens (context)

The cat sat on the

$$\begin{array}{rl}P(w_t=i\mid w_{<t})& =\frac{\exp (f_{\theta }(w_{<t}{)}_i)}{{\sum }_{j=1}^{|V|}\exp (f_{\theta }(w_{<t}{)}_j)}\\ P(w_t\mid w_1,\dots ,w_{t-1})& =\mathrm{softmax}(f_{\theta }(w_1,\dots ,w_{t-1}))\end{array}$$

Output: Probability distribution over the vocabulary for the next token

mat: 0.5 bench: 0.3 dog: 0.01

We sample from this distribution to generate the next word.

Self-supervised learning

$$\begin{array}{r}\mathcal{L}(\theta )=-\frac{1}{T}\sum _{t=1}^T\log P(w_t\mid w_{<t};\theta )\end{array}$$

The idea: We do not need manually labeled data. The text itself is supervision. At every step $t$, predict the next word $w_{t+1}$ given the history $w_{1:t}$. Since we possess the source text, we always know the correct next token.

We train the network to minimize Cross-Entropy Loss

It measures the difference between the model’s predicted distribution and the true distribution.

The loss simplifies to the negative log probability of the correct next word.

Teacher Forcing

Inference vs Training

Inference: Errors accumulate as model predicts its own future context.

Training (Teacher Forcing): We do not use the model’s own prediction. We always feed the correct history sequence.

Advantage: Allows massive parallelization (all tokens trained simultaneously).

Training Visualization

1. Input: Sequence of tokens $w_1,\dots ,w_T$
2. Forward pass: Model computes distribution ${\hat{y}}_t$ for every position $t$ simultaneously.
3. Update: Calculate loss, batch, and backpropagate to update weights

Conditional Generation

$w_t\sim P(w_t\mid w_{<t},\theta )$

We model NLP tasks as conditional text generation.

Probability of token given all previous tokens is $P(W)={\prod }_{t=1}^{T}P(w_t\mid w_1,\dots ,w_{t-1})$.

Sampling loop: Compute probability distribution, sample token, add to context, repeat.

We go from logits to text by taking the logits (raw scores from the model), converting to probabilities via softmax, and then decoding (selecting the next token).

Greedy decoding

Algorithm: Always select the single token with the highest probability

$$\begin{array}{r}\hat{w}=\arg \underset{w}{\max }P(w\mid \text{context})\end{array}$$

Pros: Deterministic, optimal for short factual queries.

Cons: Often leads to repetitive, degenerate text. Misses creative paths.

Random Sampling

Algorithm: Sample the next token randomly according to the probability distribution $P(w)$. Effect: A word with 10% probability is chosen 10% of the time.

Pros: High diversity, human-like variance.

Cons: Tail risk, sampling a very low probability word that derails coherence.

Temperature Sampling

Rescale logits by a temperature parameter $\tau$.

$$\begin{array}{r}{P}_i=\frac{\exp (u_i/\tau )}{{\sum }_j\exp (u_j/\tau )}\end{array}$$

Low ($\tau <1$): Confident/Greedy

High ($\tau >1$): Diverse/Creative

Top-k and Nucleus Sampling

Top-$k$: Only sample from the top $k$ most likely words. Renormalize weights and do random sampling on just the $k$.

Nucleus (top-$p$): Sample from the smallest set of words whose cumulative probability exceeds $P$ (e.g. 0.9).

Preview: Task Modeling

Almost any task can be cast as next-token prediction.

Sentiment Analysis

Input: “The sentiment of the sentence ‘I like Jackie Chan’ is:” Model Compares: $P(\text{“positive”}\mid \text{context})$ vs $P(\text{“negative”}\mid \text{context})$. Decision: Choose the token with higher probability

Question

What determines performance?

Performance (Loss) is determined by three main power-law factors:

• Number of parameters (model size)
• Number of tokens (dataset size)
• Compute budget (FLOPS)

Pretraining Corpora: LLMs are trained on massive datasets (trillions of tokens)

• Web crawls
• Quality data
• Code

Example

The Pile: An 825 GB corpus of diverse text sources.

Filtering: Quality

Raw web text is noisy, we must filter for quality.

• Heuristics: Removing short documents, excessive symbols, or malformed text
• Model-based: Train classifiers to distinguish high quality text from low-quality text
• Deduplication: Remove duplicate documents. Reduces memorization and improves generalization.

Filtering: Safety & Ethics

PII Removal: Scrubbing Personally Identifiable Information.

Toxicity Filtering: Removing hate speech and abusive content.

Error

Bias: Classifiers may be biased against minority dialects. Trade-off: Models trained on sanitized data may be worse at detecting toxicity themselves.

Ethical & Legal Issues

• Copyright
• Consent
• Privacy
• Skew

The Power of Law of Scaling

Kaplan et al. (2020) empirically showed that loss $L$ scales as a power law:

$$\begin{array}{r}L(N,D)=E+\frac{A}{N^a}+\frac{B}{D^b}\end{array}$$

Implication: To improve performance, we must scale up $N$ and $D$ simultaneously.

Diminishing returns: To halve the error, you need exponentially more compute.

Compute-Optimal Scaling (Chinchilla)

The Chinchilla ratio: To train optimally for a fixed compute budget, scale parameters $(N)$ and data $(D)$ equally. (~20 tokens per parameter)

Example: A 70B model $\to$ 1.4 trillion tokens (current trend is that models are over-trained to make inference cheaper).

Approximate parameter count:

For a Transformer model, the number of non-embedding parameters $N$ is roughly: $N\approx 12n_{\text{layer}}{d}^2$

• $n_{\text{layer}}:$ Number of layers
• $d:$ Model dimensionality

GPT-3: 96 layers, $d=$ 12288 $\approx$ 175 billion parameters.

Question

How do we know it works?

Perplexity (Intrinsic)

Definition

The inverse probability of the test set, normalized by the number of words.

Interpretation: The branching factor of the model.

$$\begin{array}{r}PPL(W)=\sqrt[n]{\prod _{i=1}^N\frac{1}{P(w_i\mid w_1,\dots ,w_{i-1})}}\end{array}$$

If $PP=10$, the model is as confused as if it were choosing uniformly from 10 words.

Downstream Benchmarks (Extrinsic)

Perplexity does not always predict reasoning ability. We use standard benchmarks:

• MMLU: 15k+ multiple choice questions
• Code: HumanEval.
• Reasoning: GSM8K

Method: Zero-shot or few-shot prompting.

Data contamination

Error

Did the model memorize the answer?

Contamination: When test set questions appear in the training data.

Consequence: High scores but fails to generalize to new problems.

Mitigation: Rigorous decontamination ($n$-gram matching) before training.

Using Pretrained Models: Prompting

• Prompt: The input text provided to the model to elicit a specific response.
• System Prompt: A hidden prefix instruction that defines the model’s personality.
• Prompt Engineering: The empirical science of designing prompts to maximize model performance.

Definition

In-Context Learning (ICL): The ability of a model to improve performance on a specific task given context in the prompt, without updating model parameters.

Mechanism: The model ‘learns’ the pattern or format from the input buffer activations.

Zero-Shot Prompting

Providing the task instruction without any examples

”Translate the following sentence into French: The cat sat on the mat.”

Reliance: Relies entirely on the model’s pretraining data to understand the instruction verb.

Few-Shot Prompting

Providing $k$ examples (demonstrations) of the task before the actual query.

Translate English to French: Dog $\to$ Chien, Cheese $\to$ Fromage, Cat $\to$ ?

Effect: Significantly improves performance on complex or novel tasks by demonstrating the expected output formats.

Question

Why do demonstrations work?

• Format constraints: They teach the model the output structure.
• Task location: They help the model locate the specific task manifold in its parameter space.
• Counter-intuitive finding: Correctness of labels matters less than format. Models improve even with incorrect labels.

Lecture 13

Pretraining creates a base model. Excellent at completing text, possessing vast world knowledge and syntactic fluency.

However there’s an alignment gap.

We expect an intelligent assistant that follows instructions. In reality, base models are trained to complete text, not obey commands.

Failure 1: Misinterpretation

Prompt:

“Explain the moon landing to a six year old in a few sentences”

Base Model Output:

“Explain the theory of gravity to a 6 year old”

The model say a pattern of list of questions in its training questions, and generated the next item in the list.

Failure 2: Continuation vs Answer

Prompt:

“Translate to French: The small dog”

Base Model Output:

“The small dog crossed the road”

Model treated the input as the start of a story rather than a translation command.

The goal of post-training is to bridge the gap between next-token prediction and intent following. We want the model to be helpful, honest, and harmless.

Three stages of training

1. Pretraining (covered in last lecture)
2. Instruction Tuning (Supervised fine-tuning)
3. Alignment (RLHF/DPO)

Definition

Instruction Tuning: The process of further training a base model on a datset of (Instruction, Response) pairs.

Goal: Teach the model to recognize the “instruction” format and generate the appropriate “response”.

Meta-learning: The goal is not just to learn about the specific tasks in the training set, but to learn the general skill of following instructions.

flowchart LR

a[Base model weights]
b[Fine-tuning]
c[Instruction]
d[Response]
e[Adapted Model Weights]

a --> b
c --> d
d --> b
b --> e

Supervised fine-tuning (SFT) uses the same cross-entropy loss as pretraining.

We want the model to answer the user, not learn to predict/mimic the user’s questions.

Domain adaptation vs instruction tuning

The goal of domain adaptation is to adapt a model to new jargon. The data is unlabeled documents and we continue pretraining on raw text.

The goal of instruction tuning is to adapt model to a behavioural interface. Data is labeled pairs (Q, A) via supervised training.

Full SFT: Update all parameters of the model. This requires significant compute/memory.

PEFT: Freezes the base model, adds small trainable adapter matrices. Updates only the adapters.

Traditional Fine-Tuning (BERT-style masked LM): Add a traditional head on top. Train for one specific task. Model cannot do other tasks anymore.

Instruction Tuning: No new layers, the model outputs text. Task is specified in natural language in the prompt. Our model remains a general-purpose engine.

Formatting of SFT Data

We wrap data in a conversational format. The model learns that after the <Instruction> tag comes a command, and it should generate text after the <Response> tag.

<Instruction> Summarize the main idea of the text.
[Input text]...
[Input text]...
<Response> The main idea is that instruction tuning adapts base models to follow user commands effectively.

<Instruction> Translate the following sentence into French: "The weather is beautiful today."
<Response> Le temps est magnifique aujourd'hui.

To train a robust SFT model, we need thousands of diverse instructions.

Source 1: Human Annotation

Hire crowd-workers or experts to write realistic prompts and high-quality answers. This does result in high quality, “real” user distribution, but is expensive and slow.

Aya: A massive multilingual instruction dataset developed by 3,000 fluent speakers across 114 languages.

Source 2: Templating Existing Datasets

NLP researchers have created thousands of labeled datasets over the decades. Convert these rigid datasets into natural language prompts.

How templating works.

Original Dataset (Sentiment)

Input: “The movie was terrible” Label: 0 (Negative)

Template 1

”Review: {Input}. Is this positive or negative? Answer: Negative”

Template 2

”I just read the following review: {Input}. How did the reviewer feel? Answer: They hated it”

SuperNaturalInstructions

12 million examples from 1,600 different NLP tasks. Each task is paired with multiple natural language templates to ensure the model doesn’t overfit to one phrasing.

Source 3: LLM Synthesis (Self-Instruct)

Use a very strong model to generate training data for a smaller model

Loop:

• Give GPT-4 a few seed examples of tasks
• Ask it to generate 100 new, unique tasks.
• Ask it to generate the solutions.
• Filter for quality.
• Train the small model on this synthetic data.

We can explicitly engineer safety into SFT. Use an LLM to generate a “safe” refusal, add this pair to the training set. The model learns to refuse harmful instructions via pattern matching, even before RLHF.

Our goal is to generalize.

If we train on 1,000 tasks, we don’t want the model to be good at just those 1,000 tasks. Learning to follow instructions transfers.

Evaluation Methodology

Hold-one-out: Train on $n-1$ tasks, test on the $n$th task.

Caution

If you train on “SQuAS” (QA) and test on “NaturalQuestions” (QA), it’s not really an unseen task.

Solution is task clustering. Group datasets by type, hold out entire clusters for evaluation.

Instruction-tuned models significantly outperform base models on zero-shot tasks. The more tasks you add during fine-tuning, the better the generalization (but there are diminishing returns).

Question

Can we teach models to reason via SFT?

Chain-of-Thought (CoT): Prompting models to think step-by-step.

SFT can be used to “bake in” this behaviour.

Data: (Question, Rationale + Answer) pairs. Result: Models learn to output reasoning steps automatically before answering.

The quality vs quantity trade-off

Early SFT (Flan): Focused on quantity (millions of examplse)

Recent work (LIMA): Suggests quality is more important

Pretraining takes months on thousands of GPUs. SFT can take days on dozens of GPUs (or hours on 1 GPU for PEFT).

Problem

SFT can cause the model to forget knowledge from pretraining.

Mitigations include mixing in some pretraining data during SFT, use low learning rates, use PEFT to preserve original weights.

Evaluating generation is hard. There are metrics (but most are bad), human eval is good but expensive, LLM-as-a-Judge (using GPT-4 to grade the outputs of smaller models).

SFT datasets can contain test set leakage. If MMLU questions are in your SFT set, your evaluation score is invalid. Need to decontaminate by creating private, held-out evaluation sets.

Challenge: Multilingual SFT

Most SFT data is in English. SFT in English often improves performance in other languages too. The model learns the concept of following instructions, which maps to its internal multilingual representations. The best practice is still to use multilingual data for best results.

Challenge: Reproducibility Issues

Many open weights model release the weights but not the SFT model. The SFT data is often the secret sauce or proprietary.

Challenge: Synthetic Data Risks

Using GPT-4 to train Llama creates a feedback loop. Model Collapse: If we keep training on synthetic data, models might drift away from real human language distribution.

SFT makes model helpful, but not aligned. If the training data contains errors, the model mimics them. Sycophancy - models might agree with the user’s incorrect premise just to be helpful.