# AIpedia

> The AI Encyclopedia: a growing collection of time-tested cool things in AI (papers, software, interviews, positions, demos, and blogs), the things worth knowing on the way into the singularity. Each entry has a plain-language explanation, an interactive demo on the website, and links to the originals.

Source: https://aipedia.org. 58 entries follow.


# AlexNet

> The deep CNN that won ImageNet 2012 and sparked the deep learning revolution

- Type: Paper
- By: Krizhevsky, Sutskever & Hinton
- Year: 2012
- Topics: Deep learning, CNNs, Vision, Imagenet
- Page: https://aipedia.org/alexnet

## Resources

- [ImageNet Classification with Deep Convolutional Neural Networks](https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks): Paper, Krizhevsky, Sutskever & Hinton, 2012

**AlexNet** is the deep convolutional neural network that won the 2012 ImageNet Large Scale Visual Recognition Challenge (ILSVRC). It cut the top-5 error rate from 26% to 15.3%, a huge jump that convinced the field that deep learning could dramatically outperform traditional computer vision methods.

> If convolutional networks are new to you, start with [CS231n](https://aipedia.org/cs231n), Stanford's course on CNNs. For what came after AlexNet, see [ResNet](https://aipedia.org/resnet).

## Why Students Should Care

- AlexNet is widely considered the **starting gun of the modern deep learning era**. Almost every architecture you will study came after it, and often in response to it.
- Its ingredients — ReLU, [dropout](https://aipedia.org/dropout), GPU training, big datasets — are still standard practice today.
- It is a compact case study in why deep learning works: a simple recipe, scaled up, beating years of hand-crafted engineering.

## The Problem It Solved

Before 2012, image classification systems were built by hand: researchers designed feature detectors (edges, corners, textures) and then trained a shallow classifier on top. Progress was slow and incremental.

AlexNet took the opposite approach: feed the network raw pixels and let it **learn its own features** from 1.2 million labeled ImageNet images. The result was not a small improvement — it was a 10+ percentage point gap over the runner-up.

## Architecture

AlexNet consists of 8 learned layers: 5 convolutional and 3 fully-connected:

$$
\text{Input} \rightarrow \text{Conv}_1 \rightarrow \text{Conv}_2 \rightarrow \text{Conv}_3 \rightarrow \text{Conv}_4 \rightarrow \text{Conv}_5 \rightarrow \text{FC}_6 \rightarrow \text{FC}_7 \rightarrow \text{FC}_8
$$

The network takes a 224×224 RGB image and processes it through progressively smaller spatial dimensions but increasing channel depth. Intuitively, early layers see small patches and detect simple patterns; later layers see larger regions and detect whole objects. The final layer is a 1000-way softmax, one output per ImageNet category.

## Key Innovations

**ReLU activation.** Instead of tanh or sigmoid, AlexNet used Rectified Linear Units:

$$
f(x) = \max(0, x)
$$

In plain English: pass positive values through, zero out negative ones. Because ReLU does not flatten out (saturate) for large positive inputs, gradients stay healthy and training runs about 6× faster than with tanh.

**Dropout.** During training, neurons are randomly zeroed with probability 0.5:

$$
\tilde{h} = h \cdot m, \quad m_i \sim \text{Bernoulli}(0.5)
$$

The idea: if any neuron can vanish at any moment, no neuron can rely too heavily on specific partners. This prevents complex co-adaptations and reduces overfitting in the large fully-connected layers. See [Dropout](https://aipedia.org/dropout) for the full story.

**Local Response Normalization.** Inspired by lateral inhibition in biological neurons (active neurons suppressing their neighbors), LRN normalizes activations across adjacent feature maps at each spatial position.

**Overlapping pooling.** Using 3×3 pooling windows with stride 2 — so neighboring windows overlap — slightly reduced error rates compared to non-overlapping pooling.

You do not need to memorize the details. The important idea is: **each trick either made training faster (ReLU, GPUs) or fought overfitting (dropout, pooling choices)**.

## Interactive Demo

Explore AlexNet's layer-by-layer architecture and key innovations:

*Interactive demo: https://aipedia.org/alexnet*

## Historical Impact

AlexNet's victory was decisive: the runner-up used hand-crafted features and achieved 26.2% error. That 10+ percentage point gap proved three things at once:

- Deep networks could learn hierarchical features automatically — no hand engineering needed
- GPUs were essential for training large models
- Sufficient data (1.2M ImageNet images) enables generalization

The paper has over 100,000 citations and is considered the catalyst of the modern deep learning era.

## Common Confusion

- **AlexNet did not invent convolutional networks.** CNNs existed earlier; AlexNet showed that a deep CNN, trained on GPUs with enough data, could win at scale.
- **AlexNet is a specific architecture; ImageNet is the dataset; ILSVRC is the competition.** "Winning ImageNet" is shorthand for winning the ILSVRC challenge on the ImageNet dataset.
- **[Dropout](https://aipedia.org/dropout) has its own paper and page.** AlexNet is one of its most famous applications, not its origin.

## Where To Go Next

- Read [ResNet](https://aipedia.org/resnet) for how skip connections took networks from 8 layers to 150+
- Read [Dropout](https://aipedia.org/dropout) for a deeper look at AlexNet's regularization trick
- Read [CS231n](https://aipedia.org/cs231n) for the Stanford course that teaches this whole lineage
- Read [Vision Transformer](https://aipedia.org/vision-transformer) for the architecture that eventually challenged CNNs


# Deep Q-Networks (DQN)

> Combining Q-learning with deep neural networks for Atari-level game playing

- Type: Paper
- By: Mnih et al.
- Year: 2013
- Topics: Deep learning, Reinforcement learning, Games, Classic
- Page: https://aipedia.org/dqn

## Resources

- [Playing Atari with Deep Reinforcement Learning](https://arxiv.org/abs/1312.5602): Paper, Mnih et al., 2013
- [google-deepmind/dqn](https://github.com/google-deepmind/dqn): Code, Original Lua/Torch code
- [Human-level control through deep reinforcement learning](https://www.nature.com/articles/nature14236): Paper, Mnih et al., Nature 2015
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://arxiv.org/abs/1710.02298): Paper, Hessel et al., 2017

**Deep Q-Networks (DQN)** showed that a neural network could learn to play Atari games at superhuman level directly from raw pixels, using nothing but trial and error. It was the landmark result that sparked the modern deep reinforcement learning revolution.

> If terms like "Q-value" or "policy" are new to you, read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) first. This page covers the classic **value-based** approach; [Policy Gradient](https://aipedia.org/policy-gradient) covers the other big family.

## Why Students Should Care

- DQN is the standard first "deep RL" algorithm: it connects supervised deep learning to reinforcement learning.
- Its two stabilization tricks (experience replay and target networks) show up all over modern RL.
- It opened the door to AlphaGo, robotic control, and much of today's RL research.

## The Setup in Plain English

Imagine learning to play a video game with no instructions. All you see is the screen, all you get is the score. You need a way to answer one question at every moment: **"How good is each button press right now, counting all the points it will lead to later?"**

A function that answers that question is called a **Q-function**. DQN's whole job is to learn it with a neural network.

## Q-Learning Refresher

Q-learning tries to learn the optimal action-value function: the best total future reward you can get by taking action $a$ in state $s$ and playing well afterwards.

$$
Q^*(s, a) = \mathbb{E}\left[r + \gamma \max_{a'} Q^*(s', a') \mid s, a\right]
$$

In words: the value of an action equals the immediate reward, plus the (discounted) value of the best action available in the next state.

Once you know $Q^*$, acting well is easy — just pick the highest-scoring action: $\pi^*(s) = \arg\max_a Q^*(s, a)$.

## The Challenge: Too Many States for a Table

Classic Q-learning stores one Q-value per state-action pair in a table. That works for tiny grid worlds, but an Atari screen has far too many possible pixel configurations to enumerate.

The fix is to **approximate** the table with a neural network:

$$
Q(s, a; \theta) \approx Q^*(s, a)
$$

Here $\theta$ is the network's weights. But there is a catch: naively combining deep learning with Q-learning is unstable. The network chases its own predictions and training tends to blow up. DQN's real contribution is two tricks that make it stable.

## Key Innovations

### 1. Experience Replay

Instead of training on experiences in the order they happen, store each transition $(s, a, r, s')$ in a large **replay buffer** and train on random mini-batches drawn from it.

Why this helps:

- Consecutive game frames are nearly identical. Random sampling breaks that correlation, which neural networks need for stable training.
- Each experience gets reused many times, so learning is more data-efficient.
- Overall, training becomes much more stable.

### 2. Target Network

The Q-learning update is strange: the network's training target is computed *from the network itself*. As the network changes, its own targets shift underneath it — like an archer aiming at a target strapped to their own arm.

DQN fixes this by computing targets with a frozen copy of the network:

$$
y = r + \gamma \max_{a'} Q(s', a'; \theta^-)
$$

where $\theta^-$ is a copy of $\theta$ that is only refreshed periodically (e.g., every 10k steps). Between refreshes the target stays still, which dramatically improves stability.

## The DQN Loss

Put together, DQN minimizes a squared error between predicted Q-values and the (frozen-target) estimates:

$$
\mathcal{L}(\theta) = \mathbb{E}_{(s,a,r,s') \sim \mathcal{D}}\left[(y - Q(s, a; \theta))^2\right]
$$

where $y = r + \gamma \max_{a'} Q(s', a'; \theta^-)$.

You do not need to memorize the equation. The important idea is: **make the network's Q-value prediction match "reward plus best next-state value", using a stale copy of the network for the second part.**

## Interactive Visualization

Watch DQN learn to estimate Q-values:

*Interactive demo: https://aipedia.org/dqn*

## Algorithm

```python
Initialize replay buffer D, Q-network θ, target network θ⁻
for episode in range(num_episodes):
    s = env.reset()
    for t in range(max_steps):
        # ε-greedy action selection
        if random() < ε:
            a = random_action()
        else:
            a = argmax_a Q(s, a; θ)
        
        s', r, done = env.step(a)
        D.store(s, a, r, s', done)
        
        # Sample and train
        batch = D.sample(batch_size)
        targets = r + γ * max_a' Q(s', a'; θ⁻) * (1 - done)
        loss = MSE(Q(s, a; θ), targets)
        θ.update(loss)
        
        # Periodic target update
        if t % target_update_freq == 0:
            θ⁻ = θ
```

The "ε-greedy" part handles **exploration**: with probability ε the agent tries a random action instead of its current best guess, so it keeps discovering new strategies.

## Hyperparameters

| Parameter | Typical Value |
|-----------|---------------|
| Replay buffer size | 1M transitions |
| Batch size | 32 |
| Learning rate | 0.00025 |
| Discount γ | 0.99 |
| Target update freq | 10,000 steps |
| ε decay | 1.0 → 0.1 over 1M steps |

## Improvements (Rainbow DQN)

Later work stacked several upgrades on top of vanilla DQN. The combination is called **Rainbow**:

| Enhancement | Benefit |
|-------------|---------|
| Double DQN | Reduces overestimation bias |
| Prioritized replay | Focus on important transitions |
| Dueling networks | Separate value and advantage |
| Multi-step returns | Better credit assignment |
| Distributional RL | Model return distribution |
| Noisy networks | Better exploration |

## Impact

DQN proved that:

1. Deep RL can learn from high-dimensional sensory input (raw pixels)
2. Experience replay + target networks stabilize training
3. A single architecture can master diverse tasks

This opened the door to AlphaGo, robotic manipulation, and modern RL research.

## Common Confusion

- **DQN vs. Q-learning**: Q-learning is the underlying update rule; DQN is Q-learning plus a neural network approximator plus the two stability tricks.
- **Value-based vs. policy-based**: DQN never represents a policy directly — it learns action *values* and derives the policy by taking the argmax. [Policy Gradient](https://aipedia.org/policy-gradient) methods learn the policy itself.
- **Target network vs. replay buffer**: both fight instability, but differently. Replay breaks *sample correlation*; the target network stops the *moving target* problem.
- **DQN and continuous actions**: the $\max_{a'}$ step requires enumerating actions, so vanilla DQN only works for discrete action spaces.

## Where To Go Next

- Read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) for the MDP framing and value functions DQN builds on.
- Read [Policy Gradient](https://aipedia.org/policy-gradient) for the other major family of RL algorithms.
- Read [PPO](https://aipedia.org/ppo) for the policy-based algorithm that dominates modern practice.
- Read [RLHF](https://aipedia.org/rlhf) to see how RL ideas reach language model training.


# Neural Machine Translation by Jointly Learning to Align and Translate

> The paper that introduced the attention mechanism for sequence-to-sequence models

- Type: Paper
- By: Bahdanau, Cho & Bengio
- Year: 2014
- Topics: Deep learning, Attention, NLP, Translation
- Page: https://aipedia.org/bahdanau-attention

## Resources

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://arxiv.org/abs/1409.0473): Paper, Bahdanau, Cho & Bengio, 2014
- [Attention and Augmented Recurrent Neural Networks](https://distill.pub/2016/augmented-rnns/): Article, Olah & Carter, Distill 2016

This landmark paper by Bahdanau, Cho, and Bengio introduced the **attention mechanism** for neural machine translation: instead of squeezing a whole sentence into one vector, let the decoder look back at the input and pick what is relevant at each step. It is one of the most influential papers in modern AI.

> If this page feels too fast, read [Sequence to Sequence](https://aipedia.org/seq2seq) first — this paper fixes seq2seq's biggest weakness. For where attention went next, see [Transformer](https://aipedia.org/transformer).

## Why Students Should Care

- This is where **attention** — the mechanism behind Transformers and every modern LLM — was born.
- It is a perfect case study in research: identify a bottleneck, design a mechanism that removes it, measure the gain.
- The idea generalizes far beyond translation: "let the model choose what to look at" shows up in vision, speech, and multimodal models.

## A Quick Example

Imagine translating a 50-word German sentence into English. A standard seq2seq model forces you to read the whole sentence once, memorize it as a single fixed-size summary, then write the translation purely from memory. A human translator does not work that way — they glance back at the relevant source words while writing each output word. Attention gives the model that ability to glance back.

## The Bottleneck Problem

In standard seq2seq models, the encoder compresses the entire input into a fixed-size context vector $c$:

$$
c = f(x_1, x_2, ..., x_T)
$$

This becomes a bottleneck for long sequences — all information must squeeze through a single vector, no matter how long the input is.

## The Attention Solution

Instead of a single context vector, attention computes a **different context for each output step**:

$$
c_i = \sum_{j=1}^{T} \alpha_{ij} h_j
$$

where $\alpha_{ij}$ is the attention weight that output position $i$ places on input position $j$, and $h_j$ is the encoder state for input word $j$.

The important idea is: each output word gets its own **weighted mix of all input words**, with the weights chosen by the model.

## Computing Attention Weights

How does the model choose the weights? An alignment model scores how relevant each input position is, then a softmax turns the scores into weights that sum to 1:

$$
e_{ij} = a(s_{i-1}, h_j)
$$

$$
\alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k=1}^{T} \exp(e_{ik})}
$$

The alignment function $a$ (often a small neural network) scores how well input $j$ and output $i$ match. You do not need to memorize the formulas — the recipe is: **score every input word, softmax the scores, use them as mixing weights**.

## Interactive Demo

Watch attention align source and target words during translation:

*Interactive demo: https://aipedia.org/bahdanau-attention*

## The Alignment Model

Bahdanau attention uses an additive alignment function:

$$
e_{ij} = v^T \tanh(W_s s_{i-1} + W_h h_j)
$$

This learnable function discovers which source words are relevant for generating each target word — no hand-built dictionary or word alignments required.

## Why This Changed Everything

1. **No bottleneck**: each output step accesses all encoder states
2. **Interpretable**: attention weights show what the model "looks at"
3. **Handles long sequences**: performance doesn't degrade with length
4. **Generalizable**: the mechanism applies far beyond translation

## Results

| Model | BLEU Score |
|-------|------------|
| RNNsearch (no attention) | 26.75 |
| RNNsearch-50 (attention) | **28.45** |
| Phrase-based SMT | 33.30 |

Attention closed the gap with statistical MT and enabled future improvements.

## Legacy

This paper's attention mechanism became:

- The foundation of **Transformers** (self-attention) — see [Transformer](https://aipedia.org/transformer)
- Used in **image captioning** (visual attention)
- Core to **speech recognition** (CTC-attention)
- Essential for **modern LLMs**

## Common Confusion

- **Bahdanau attention vs. self-attention.** Here, the decoder attends to the *encoder's* states (cross-attention between two sequences). In Transformers, tokens in one sequence attend to *each other* (self-attention).
- **Attention vs. alignment.** "Alignment" is the translation-specific framing (which source word maps to which target word); "attention" is the general mechanism computing it.
- **This paper vs. Attention Is All You Need.** This 2014 paper *introduced* attention as an add-on to RNNs; the 2017 [Transformer paper](https://aipedia.org/attention-is-all-you-need) removed the RNN entirely and kept only attention.

## Where To Go Next

- Read [Sequence to Sequence](https://aipedia.org/seq2seq) for the bottlenecked architecture this paper improved
- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the RNN machinery used underneath
- Read [Transformer](https://aipedia.org/transformer) for the architecture built purely from attention
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for the paper that took that final step


# Neural Turing Machines

> Neural networks augmented with external memory and attention-based read/write heads

- Type: Paper
- By: Graves, Wayne & Danihelka
- Year: 2014
- Topics: Deep learning, Memory, Attention, Reasoning
- Page: https://aipedia.org/neural-turing-machines

## Resources

- [Neural Turing Machines](https://arxiv.org/abs/1410.5401): Paper, Graves, Wayne & Danihelka, 2014
- [Attention and Augmented Recurrent Neural Networks](https://distill.pub/2016/augmented-rnns/): Article, Olah & Carter, Distill 2016

**Neural Turing Machines** (NTMs) bolt an external, readable-and-writable memory onto a neural network — like giving the network a notepad. Because every memory operation is differentiable, the whole system can learn *algorithms* (copy, sort, recall) end-to-end by gradient descent.

> Helpful background: [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the controller, and [Bahdanau Attention](https://aipedia.org/bahdanau-attention) for the attention idea the read/write heads are built on.

## Why Students Should Care

- NTMs are a landmark attempt to make neural networks compute more like computers — with explicit storage, not just learned reflexes.
- They pioneered **differentiable attention over memory**, an idea that echoes through Memory Networks, DNCs, and [Transformer](https://aipedia.org/transformer) attention.
- The core trick — replace a discrete choice ("read slot 7") with a soft, differentiable weighting over all choices — is one of the most reusable ideas in deep learning.

## Motivation

Think about how you multiply two long numbers by hand: you write down intermediate results and read them back later. A standard neural network cannot do this — its "memory" lives implicitly in weights and hidden activations, with no way to deliberately store a value and retrieve it later.

Computers, by contrast, have explicit addressable memory. NTMs bridge this gap.

The catch is that ordinary memory access is discrete ("read address 7"), and discrete choices block gradients. NTMs solve this by making every access *soft*: instead of reading one slot, read a weighted blend of all slots, with learnable weights.

## Architecture

An NTM consists of:

1. **Controller**: Neural network (LSTM or feedforward) — the "CPU" that decides what to read and write
2. **Memory Bank**: $N \times M$ matrix of memory locations — $N$ slots, each holding a vector of size $M$
3. **Read Head**: Retrieves information from memory
4. **Write Head**: Modifies memory contents

## Reading from Memory

The read head produces attention weights $w_t$ over memory locations, and the read result is a weighted average:

$$
r_t = \sum_{i=1}^{N} w_t(i) \cdot M_t(i)
$$

The read vector $r_t$ is a weighted sum of memory rows. If the weights concentrate on one slot, this behaves like a normal memory read; because the weights are soft, gradients flow through the operation.

## Writing to Memory

Writing combines **erase** and **add** operations — first partially blank a slot, then add new content:

$$
\tilde{M}_t(i) = M_{t-1}(i) \cdot [1 - w_t(i) \cdot e_t]
$$
$$
M_t(i) = \tilde{M}_t(i) + w_t(i) \cdot a_t
$$

The erase vector $e_t$ clears, the add vector $a_t$ writes new content. Both are scaled by the attention weight $w_t(i)$, so the head mostly modifies the slots it is "looking at."

The takeaway: **reads and writes are both just attention-weighted arithmetic**, which is why the whole machine trains with backpropagation.

## Addressing Mechanisms

How does the head decide *where* to look? NTMs compute the attention weights in four stages, combining two styles of addressing: **content-based** ("find the slot that looks like this") and **location-based** ("move one slot to the right of where I was").

### 1. Content Addressing

Compare a key vector $k_t$ to memory rows using cosine similarity, then softmax:

$$
w_t^c(i) = \frac{\exp(\beta_t \cdot K(k_t, M_t(i)))}{\sum_j \exp(\beta_t \cdot K(k_t, M_t(j)))}
$$

This is "search by similarity" — like looking up a memory by what it contains.

### 2. Interpolation

Blend content-based weights with the previous step's weights:

$$
w_t^g = g_t \cdot w_t^c + (1 - g_t) \cdot w_{t-1}
$$

The gate $g_t$ lets the head either jump to new content or stay where it was.

### 3. Convolutional Shift

Allow location-based addressing via circular convolution — the head can shift its focus left or right by a slot, enabling sequential iteration like a tape head.

### 4. Sharpening

Focus attention with a sharpening parameter $\gamma_t$, counteracting the blurring that shifting introduces.

## Interactive Demo

Explore memory read/write operations:

*Interactive demo: https://aipedia.org/neural-turing-machines*

## What NTMs Can Learn

The paper demonstrated learning of small algorithms from input-output examples alone:

- **Copy**: Reproduce an input sequence
- **Associative Recall**: Retrieve values by key
- **N-Gram modeling**: Track recent symbols
- **Priority Sort**: Sort by priority values

Notably, NTMs generalized to longer sequences than they were trained on — evidence they learned something algorithm-like, not just pattern matching.

## Legacy

NTMs pioneered ideas now central to modern AI:

- External memory augmentation
- Differentiable attention mechanisms
- Content-based retrieval

These concepts evolved into Memory Networks, Differentiable Neural Computers (DNC), and influenced Transformer attention.

## Common Confusion

- **NTM vs. Turing machine**: an NTM is not a formal Turing machine. The name signals the analogy — controller as CPU, memory bank as tape — but everything is continuous and learned.
- **NTM vs. LSTM**: an LSTM's memory is a fixed-size hidden state entangled with computation; an NTM separates computation (controller) from storage (memory bank), which can be made larger without adding parameters.
- **NTM attention vs. Transformer attention**: both use content-based, softmax-weighted lookup. But NTMs attend over an explicit *memory the model writes to*, while [Transformers](https://aipedia.org/transformer) attend over the input sequence's own representations, with no separate writable store.
- **NTM vs. DNC**: the Differentiable Neural Computer is the successor architecture by the same group, with improved memory management (e.g., tracking which slots are free).

## Where To Go Next

- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the recurrent controller at an NTM's core.
- Read [Bahdanau Attention](https://aipedia.org/bahdanau-attention) for the contemporaneous attention mechanism in translation.
- Read [Transformer](https://aipedia.org/transformer) and [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) to see where differentiable attention ended up.
- Read [Relational RNN](https://aipedia.org/relational-rnn) for a later memory-plus-attention architecture.


# Recurrent Neural Network Regularization

> How to apply dropout to LSTMs without disrupting memory dynamics

- Type: Paper
- By: Zaremba, Sutskever & Vinyals
- Year: 2014
- Topics: Deep learning, RNNs, LSTMs, Regularization
- Page: https://aipedia.org/rnn-regularization

## Resources

- [Recurrent Neural Network Regularization](https://arxiv.org/abs/1409.2329): Paper, Zaremba, Sutskever & Vinyals, 2014

**Recurrent Neural Network Regularization** is the paper by Zaremba, Sutskever, and Vinyals that solved an annoying practical problem: standard dropout, the go-to trick for preventing overfitting, breaks RNNs. Their fix — drop only the "vertical" connections, never the "horizontal" memory path — became the standard recipe.

> Prerequisites: know what [dropout](https://aipedia.org/dropout) is and how an [LSTM](https://aipedia.org/understanding-lstms) carries memory across timesteps. Both pages are short.

## Why Students Should Care

- LSTMs of this era overfit badly; without a working regularizer they had to be kept small. This paper let people train much larger recurrent models.
- It teaches a transferable lesson: **where** you apply a regularizer matters as much as whether you apply it.
- The "protect the memory path" insight echoes through later designs — residual streams in [Transformers](https://aipedia.org/transformer) are similarly kept clean.

## The Problem: Dropout Noise Compounds Over Time

Dropout randomly zeroes activations during training. In a feedforward net, each activation gets zapped at most once per forward pass — no big deal. But an RNN reuses its hidden state at *every* timestep. Naively dropping the recurrent connection looks like this:

$$
h_t = f(W_h \cdot \text{dropout}(h_{t-1}) + W_x \cdot x_t)
$$

Now the memory gets corrupted by fresh noise at every single step. Over a 100-step sequence, that is 100 rounds of damage — the network can no longer retain long-term information, which was the whole point of using an LSTM.

## The Solution: Only Drop the Non-Recurrent Connections

Apply dropout on the way *into* and *out of* each layer, but leave the timestep-to-timestep path untouched:

$$
h_t = f(W_h \cdot h_{t-1} + W_x \cdot \text{dropout}(x_t))
$$

$$
y_t = \text{dropout}(h_t)
$$

The recurrent path $h_{t-1} \rightarrow h_t$ remains clean, preserving memory. Information still gets regularized — but only once per layer it passes through, not once per timestep.

## Where to Apply Dropout

| Connection | Apply Dropout? |
|-----------|---------------|
| Input → Hidden | ✓ Yes |
| Hidden → Hidden (recurrent) | ✗ No |
| Hidden → Output | ✓ Yes |
| Between LSTM layers | ✓ Yes |

One rule of thumb captures the whole paper: **drop vertical arrows, never horizontal ones**.

## Interactive Demo

Visualize how dropout randomly masks neurons during training:

*Interactive demo: https://aipedia.org/rnn-regularization*

## LSTM-Specific Details

For multi-layer LSTMs, dropout is applied between layers:

```
Layer 1: dropout(x) → LSTM → h1
Layer 2: dropout(h1) → LSTM → h2
Layer 3: dropout(h2) → LSTM → h3
Output:  dropout(h3) → Linear → y
```

Within each LSTM cell, the recurrent connections remain untouched.

## Results

On Penn Treebank word-level language modeling (lower perplexity = better):

| Model | Perplexity |
|-------|------------|
| LSTM (no dropout) | 120.7 |
| LSTM (naive dropout) | Diverges |
| LSTM (this paper) | **78.4** |

Proper dropout reduces perplexity by 35% — and note that naive dropout is not just worse, it fails to train at all.

## Mathematical Formulation

During training with dropout rate $p$, kept activations are rescaled:

$$
\tilde{h}_t^l = \text{dropout}(h_t^l, p) \cdot \frac{1}{1-p}
$$

The scaling factor ensures expected values match at test time, so you can turn dropout off for inference without recalibrating anything.

## Key Insights

1. **Dropout placement matters**: the recurrent path needs to stay clean so memory and gradients survive
2. **Same mask per sequence**: use a consistent dropout mask across timesteps rather than resampling each step
3. **Higher dropout for deeper networks**: more layers tolerate — and benefit from — more regularization

## Common Confusion

- **This is not "no dropout in RNNs"**: dropout works great in RNNs — just on the input, output, and between-layer connections, not on the hidden-to-hidden loop.
- **Regularization vs. architecture**: this paper changes *training*, not the LSTM cell itself. The model at test time is a plain LSTM.
- **Later variants exist**: "variational dropout" (Gal and Ghahramani) later showed a principled way to drop recurrent connections using one fixed mask per sequence; this paper's simpler recipe was the established baseline.

## Where To Go Next

- Read [Dropout](https://aipedia.org/dropout) for the original technique and why randomly deleting neurons prevents overfitting.
- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the memory dynamics this paper is careful not to break.
- Read [RNN Effectiveness](https://aipedia.org/rnn-effectiveness) for the kind of language models this recipe made trainable at scale.
- Read [Layer Normalization](https://aipedia.org/layer-normalization) for another technique adapted specially for recurrent networks.


# Sequence to Sequence Learning

> Encoder-decoder architecture for mapping sequences to sequences

- Type: Paper
- By: Sutskever, Vinyals & Le
- Year: 2014
- Topics: Architecture, Deep learning, NLP, Encoder decoder, Seq2seq, RNNs
- Page: https://aipedia.org/seq2seq

## Resources

- [Sequence to Sequence Learning with Neural Networks](https://arxiv.org/abs/1409.3215): Paper, Sutskever, Vinyals & Le, 2014
- [Learning Phrase Representations using RNN Encoder-Decoder](https://arxiv.org/abs/1406.1078): Paper, Cho et al., 2014
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://arxiv.org/abs/1409.0473): Paper, Bahdanau, Cho & Bengio, 2014
- [Effective Approaches to Attention-based Neural Machine Translation](https://arxiv.org/abs/1508.04025): Paper, Luong et al., 2015

**Sequence-to-Sequence** (Seq2Seq) is a neural architecture that turns one sequence into another: read the input with an **encoder**, then write the output with a **decoder**. Introduced by Sutskever et al. at Google in 2014, it enabled neural machine translation and became the foundation for modern language models.

> This page assumes basic familiarity with recurrent networks — read [Understanding LSTMs](https://aipedia.org/understanding-lstms) first if needed. Seq2Seq's main weakness led directly to [Bahdanau Attention](https://aipedia.org/bahdanau-attention) and then the [Transformer](https://aipedia.org/transformer).

## Why Students Should Care

- The **encoder-decoder** split introduced here is still the mental model behind translation, summarization, and chat systems.
- Seq2Seq is the first step in the chain that leads to attention and Transformers — you cannot appreciate what attention fixed without knowing this design.
- Practical ideas born here — teacher forcing, beam search — are still used to train and run today's language models.

## The Problem

Traditional neural networks require fixed-size inputs and outputs. But many tasks have variable lengths on both sides:

- Translation: "Hello" (1 word) → "Bonjour" (1 word)
- Translation: "How are you?" (3 words) → "Comment allez-vous?" (2 words)

There is no fixed slot count you can design a plain feed-forward network around. Seq2Seq needed a way to map *any-length* input to *any-length* output.

## The Solution: Encoder-Decoder

Split the problem into two parts:

1. **Encoder**: read the entire input sequence and compress it into a fixed-size vector (the "thought vector" or "context")
2. **Decoder**: generate the output sequence, one token at a time, starting from this context vector

$$
\text{Input} \xrightarrow{\text{Encoder}} \mathbf{c} \xrightarrow{\text{Decoder}} \text{Output}
$$

Think of it as: read the whole sentence, form a thought, then say the thought in the other language.

## Interactive Demo

Watch how Seq2Seq encodes a sentence and decodes its translation:

*Interactive demo: https://aipedia.org/seq2seq*

## The Architecture

### Encoder (LSTM)

The encoder is an LSTM that processes the input sequence $x_1, x_2, ..., x_T$ one token at a time, updating its hidden state:

$$
h_t = \text{LSTM}(x_t, h_{t-1})
$$

The final hidden state $h_T$ becomes the context vector $\mathbf{c}$ — a summary of everything it read.

### Decoder (LSTM)

The decoder is another LSTM that generates the output sequence $y_1, y_2, ..., y_{T'}$, feeding each generated word back in as input for the next step:

$$
s_t = \text{LSTM}(y_{t-1}, s_{t-1})
$$

$$
P(y_t | y_{<t}, \mathbf{c}) = \text{softmax}(W_s \cdot s_t)
$$

The decoder is initialized with $s_0 = \mathbf{c}$ — the "thought" is its starting point.

## Key Innovations

### 1. Reversing the Input Sequence

Reversing the source sentence improved translation significantly:

```
Original: "A B C" → "X Y Z"
Reversed: "C B A" → "X Y Z"
```

Why it helps: the first source word ends up right next to the first target word, so the RNN has a shorter path between corresponding words at the start of the sentence.

### 2. Deep LSTMs

Using 4-layer LSTMs significantly outperformed shallow networks:

| Depth | BLEU Score |
|-------|------------|
| 1 layer | 25.9 |
| 2 layers | 29.6 |
| 4 layers | 34.8 |

### 3. Beam Search Decoding

Greedy decoding (taking the single most likely word at each step) can lock in an early mistake. Beam search instead keeps the top-k candidate sequences at every step:

```
Beam size = 3:
Step 1: [The, A, This]
Step 2: [The cat, The dog, A cat, ...]
...select top 3 sequences by total probability
```

## Training

Training uses **teacher forcing**: at each step, feed the decoder the ground-truth previous token $y_{t-1}^*$ rather than the model's own (possibly wrong) prediction:

$$
\mathcal{L} = -\sum_{t=1}^{T'} \log P(y_t^* | y_1^*, ..., y_{t-1}^*, \mathbf{c})
$$

The takeaway: during training the model always sees the correct history, which keeps learning stable; at inference it must rely on its own outputs.

## The Bottleneck Problem

The fixed-size context vector $\mathbf{c}$ must encode the entire input, and that is the design's Achilles' heel:

- Works well for short sequences
- Degrades for long sequences (information gets compressed away)
- Led directly to the invention of **attention mechanisms**

## From Seq2Seq to Attention

The limitation of a single context vector motivated [Bahdanau attention](https://aipedia.org/bahdanau-attention) (2014):

$$
\mathbf{c}_t = \sum_i \alpha_{ti} h_i
$$

Instead of one fixed summary, each decoder step gets its own weighted mix of *all* encoder states — the decoder can look back at whichever input words it needs. This solved the bottleneck.

## Applications

Seq2Seq enabled a huge range of "sequence in, sequence out" tasks:

| Task | Input | Output |
|------|-------|--------|
| Translation | "Hello world" | "Bonjour le monde" |
| Summarization | Long article | Short summary |
| Dialogue | User message | Response |
| Code generation | Description | Code |
| Speech recognition | Audio features | Text |

## Evolution

| Year | Model | Innovation |
|------|-------|------------|
| 2014 | Seq2Seq | Encoder-decoder RNNs |
| 2014 | Bahdanau | Attention mechanism |
| 2015 | Luong | Simplified attention variants |
| 2017 | Transformer | Self-attention, no recurrence |
| 2018+ | BERT, GPT | Pre-trained transformers |

## Why It Mattered

Seq2Seq established:

- **End-to-end learning**: no hand-crafted features or alignment
- **Encoder-decoder paradigm**: used by transformers today
- **Variable-length I/O**: fundamental for language tasks
- **Transfer learning path**: pre-trained encoders/decoders

## Code Example

A minimal Seq2Seq loop with teacher forcing:

```python
class Seq2Seq(nn.Module):
    def __init__(self, encoder, decoder):
        self.encoder = encoder
        self.decoder = decoder

    def forward(self, src, trg):
        # Encode: get context from final hidden state
        _, (hidden, cell) = self.encoder(src)

        # Decode: generate output sequence
        outputs = []
        input = trg[0]  # <SOS> token
        for t in range(1, len(trg)):
            output, (hidden, cell) = self.decoder(input, hidden, cell)
            outputs.append(output)
            input = trg[t]  # Teacher forcing

        return torch.stack(outputs)
```

## Common Confusion

- **Seq2Seq is an architecture pattern, not one specific model.** The 2014 paper used LSTMs, but "encoder-decoder" describes Transformers too.
- **The context vector is not attention.** Vanilla Seq2Seq has exactly one fixed summary vector; attention (a later addition) replaces it with a per-step weighted mix.
- **Teacher forcing happens only during training.** At inference time the decoder must consume its own predictions.

## Where To Go Next

- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the recurrent cells inside encoder and decoder
- Read [Bahdanau Attention](https://aipedia.org/bahdanau-attention) for the fix to the bottleneck problem
- Read [Transformer](https://aipedia.org/transformer) for the architecture that replaced recurrence entirely
- Read [GPT](https://aipedia.org/gpt) for modern decoder-only sequence generation


# Deep Speech 2: End-to-End Speech Recognition

> Scaling up end-to-end speech recognition with RNNs and CTC

- Type: Paper
- By: Amodei et al.
- Year: 2015
- Topics: Deep learning, Speech, RNNs, CTC
- Page: https://aipedia.org/deep-speech-2

## Resources

- [Deep Speech 2: End-to-End Speech Recognition in English and Mandarin](https://arxiv.org/abs/1512.02595): Paper, Amodei et al., 2015

**Deep Speech 2** is the 2015 Baidu paper that showed a single neural network — trained end-to-end on raw audio and text — could match or beat traditional speech recognition systems built from hand-engineered components. The same architecture worked for both English and Mandarin.

> Helpful background: [Understanding LSTMs](https://aipedia.org/understanding-lstms) for recurrent networks and [Batch Normalization](https://aipedia.org/batch-normalization) for the training trick this paper extends.

## Why Students Should Care

- It is one of the clearest early demonstrations of the "end-to-end beats pipelines" lesson that now dominates deep learning.
- Its scaling story — more data and deeper networks keep helping — foreshadows the [Scaling Laws](https://aipedia.org/scaling-laws) that later shaped language models.
- Modern speech systems like Whisper and Wav2Vec are direct descendants of this line of work.

## The Old Way vs. the New Way

Traditional speech recognizers were pipelines: an acoustic model mapped audio to phonemes (sound units), a pronunciation dictionary mapped phonemes to words, and a language model stitched words together. Each stage was engineered separately, often per-language.

Deep Speech 2 replaces the whole pipeline with one network that maps spectrograms directly to text:

$$
\text{Audio} \rightarrow \text{Spectrogram} \rightarrow \text{RNN} \rightarrow \text{CTC} \rightarrow \text{Text}
$$

No phonemes, no pronunciation dictionaries — just raw audio in, characters out.

## The Model

1. **Input**: power spectrogram of audio (a picture of which frequencies are loud over time)
2. **Convolution**: 1-3 conv layers for feature extraction
3. **Recurrent**: 5-7 bidirectional RNN layers (GRU or LSTM)
4. **Output**: softmax over characters + a special CTC blank token

## CTC Loss

Here is the core problem CTC solves: audio has thousands of time frames, but the transcript has only a few dozen characters, and nobody tells the network *which* frames correspond to *which* character.

**Connectionist Temporal Classification (CTC)** allows training without that frame-level alignment:

$$
P(y|x) = \sum_{\pi \in \mathcal{B}^{-1}(y)} P(\pi|x)
$$

where $\mathcal{B}$ collapses repeated characters and removes blanks.

You do not need to memorize the equation. The idea is: **sum the probability of every possible frame-by-frame alignment that spells out the target text, and train the network to make that total large.** The network figures out the alignment on its own.

## Interactive Demo

Explore the Deep Speech 2 pipeline:

*Interactive demo: https://aipedia.org/deep-speech-2*

## Key Innovations

### Batch Normalization for RNNs

[Batch normalization](https://aipedia.org/batch-normalization) was standard for feedforward nets, but applying it inside recurrent layers is a non-trivial extension:

$$
h_t = \text{BN}(W \cdot [h_{t-1}, x_t])
$$

This enabled training much deeper recurrent networks.

### SortaGrad

A curriculum learning strategy — start easy, then mix it up:

1. First epoch: sort utterances by length (shortest first)
2. Subsequent epochs: random order

Short clips give cleaner gradients early on, which stabilizes CTC training.

### Model Parallelism

Distributed training across multiple GPUs:

- Data parallelism for batches
- Model parallelism for large layers

## Results

Word error rate (WER — the fraction of words the system gets wrong; lower is better):

| Language | Test Set | WER |
|----------|----------|-----|
| English | WSJ eval92 | 3.60% |
| English | LibriSpeech clean | 5.33% |
| Mandarin | Internal test | 6.19% |

Achieved near-human performance on clean speech.

## Scaling Laws

The paper demonstrated:

- More data → better results (up to 12,000 hours)
- Deeper networks → better results (up to 7 RNN layers)
- Both English and Mandarin benefit similarly from scale

## Why This Matters

Deep Speech 2 showed that:

1. **End-to-end wins**: no need for hand-designed pipelines
2. **Scale matters**: more data and compute beat clever engineering
3. **Transfer works**: the same architecture handles very different languages

## Legacy

This work influenced:

- Modern speech systems (Whisper, Wav2Vec)
- End-to-end paradigm adoption
- Large-scale data collection for speech

## Common Confusion

- **Deep Speech 2 vs. Deep Speech 1**: same end-to-end philosophy; version 2 scales it up (deeper networks, far more data), adds batch norm for RNNs and SortaGrad, and extends to Mandarin.
- **CTC vs. seq2seq attention**: CTC assumes a monotonic, frame-aligned relationship between audio and text. [Seq2seq](https://aipedia.org/seq2seq) models with attention are a different way to handle unaligned input/output pairs, and later replaced CTC in many systems.
- **Characters, not phonemes**: the network outputs letters directly. The absence of a phoneme stage is the whole point of "end-to-end."

## Where To Go Next

- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the recurrent layers at the heart of the model.
- Read [Batch Normalization](https://aipedia.org/batch-normalization) for the technique this paper extended to RNNs.
- Read [Seq2seq](https://aipedia.org/seq2seq) for the alternative encoder-decoder approach to sequence transduction.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) to see the "more data, bigger model" story made quantitative for language models.


# Multi-Scale Context Aggregation by Dilated Convolutions

> Expanding receptive fields exponentially without losing resolution or adding parameters

- Type: Paper
- By: Yu & Koltun
- Year: 2015
- Topics: Deep learning, CNNs, Vision, Segmentation
- Page: https://aipedia.org/dilated-convolutions

## Resources

- [Multi-Scale Context Aggregation by Dilated Convolutions](https://arxiv.org/abs/1511.07122): Paper, Yu & Koltun, 2015

**Dilated convolutions** (also called atrous convolutions) are convolutions with gaps: the kernel samples the input at spaced-out intervals instead of adjacent pixels. This lets the receptive field grow exponentially without adding parameters or shrinking the image. This paper introduced them for dense prediction tasks like semantic segmentation.

> If convolutions and receptive fields are new to you, read [CS231n](https://aipedia.org/cs231n) first.

## Why Students Should Care

- Dilated convolutions solve a tension you will hit in any dense prediction task: **seeing a lot of context without throwing away resolution**.
- They became foundational far beyond vision — the same trick powers audio generation (WaveNet) and time-series models (TCNs).
- The core idea — restructure the operation instead of adding parameters — is a recurring pattern in architecture design worth internalizing.

## The Problem

Suppose you want to label **every pixel** in an image ("this pixel is road, this one is sky"). To label a pixel correctly you need context — a wide view of the surroundings — but you also need to keep the output at full resolution, because every pixel gets its own answer.

Standard tools force a tradeoff:

- **Pooling** increases the receptive field but loses spatial resolution — you literally shrink the image
- **Larger kernels** increase the receptive field but add parameters quadratically

For dense prediction we need both large context *and* high resolution. Dilated convolutions deliver both.

## Dilated Convolution

The trick: keep the same 3×3 kernel, but spread its taps apart. With dilation factor $d$, the kernel samples the input every $d$ pixels instead of every pixel:

$$
(F *_d k)(p) = \sum_{s+dt=p} F(s) \cdot k(t)
$$

You do not need to memorize the formula. The important idea is: **a 3×3 kernel with dilation $d$ covers a $(2d+1) \times (2d+1)$ region while still using only 9 parameters** — same cost, wider view.

## Exponential Expansion

The real power comes from stacking. Double the dilation at each layer ($1, 2, 4, 8, ...$) and the receptive field grows exponentially:

| Layer | Dilation | Receptive Field |
|-------|----------|-----------------|
| 1 | 1 | 3×3 |
| 2 | 2 | 7×7 |
| 3 | 4 | 15×15 |
| 4 | 8 | 31×31 |

After $L$ layers, the receptive field is $(2^{L+1} - 1) \times (2^{L+1} - 1)$. A handful of cheap layers can see the whole image — with no pooling and no downsampling anywhere.

## Interactive Demo

Visualize how different dilation rates expand the receptive field:

*Interactive demo: https://aipedia.org/dilated-convolutions*

## Context Module

The paper also proposes a multi-scale context aggregation module:

$$
\text{Context}(x) = \sum_{i=1}^{n} \text{DilatedConv}_{d_i}(x)
$$

In plain English: run several dilated convolutions in parallel, each with a different dilation rate, so each one sees the image at a different scale. Combining them gives the final prediction access to fine detail and broad context at once.

## Key Properties

- **No resolution loss**: unlike pooling, dilated convolutions maintain spatial dimensions
- **Parameter efficient**: same number of weights as a standard convolution
- **Flexible**: the dilation rate can be adjusted per layer or learned

## Applications

Dilated convolutions became foundational for:

- **Semantic segmentation** (DeepLab, PSPNet)
- **Audio generation** (WaveNet)
- **Time series** (TCN — Temporal Convolutional Networks)

## Common Confusion

- **"Dilated" and "atrous" are the same thing.** "Atrous" comes from the French *à trous* ("with holes"); papers use the terms interchangeably.
- **Dilation is not stride.** Stride skips *output* positions, shrinking the output. Dilation spreads the *kernel's* taps apart while producing an output at every position — resolution is preserved.
- **Dilation is not pooling.** Both enlarge the receptive field, but pooling downsamples the feature map; dilated convolutions do not.

## Where To Go Next

- Read [CS231n](https://aipedia.org/cs231n) for the fundamentals of convolutions and receptive fields
- Read [ResNet](https://aipedia.org/resnet) for the backbone architectures these modules often plug into
- Read [AlexNet](https://aipedia.org/alexnet) for where the deep CNN story began
- Read [Deep Speech 2](https://aipedia.org/deep-speech-2) for another take on convolutional models beyond images


# Order Matters: Sequence to Sequence for Sets

> How input and output ordering affects seq2seq learning on set-structured data

- Type: Paper
- By: Vinyals, Bengio & Kudlur
- Year: 2015
- Topics: Deep learning, Seq2seq, Sets, Attention
- Page: https://aipedia.org/order-matters

## Resources

- [Order Matters: Sequence to Sequence for Sets](https://arxiv.org/abs/1511.06391): Paper, Vinyals, Bengio & Kudlur, 2015

**Order Matters: Sequence to Sequence for Sets** asks a deceptively simple question: sequence models require you to feed elements in *some* order — so what happens when the data is really a **set**, with no natural order at all? The answer: the order you pick genuinely changes what the model learns, and there are architectures that fix this.

> This page builds on [Seq2Seq](https://aipedia.org/seq2seq) and [Pointer Networks](https://aipedia.org/pointer-networks). Read those first if the terms "encoder-decoder" or "pointer" are new.

## Why Students Should Care

- Lots of real data is set-shaped — point clouds, tags, detected objects — and pretending sets are sequences quietly hurts your model.
- The paper's fix, attention-based order-invariant processing, is an early blueprint for what [Transformers](https://aipedia.org/transformer) later made standard.
- It teaches a subtle general lesson: choices that look like formatting details (how you order your data) are actually part of your model design.

## The Problem, in Plain English

An LSTM reads its input one element at a time, so *something* has to come first. But if your input is the set of points A, B, and C, feeding "A, B, C" versus "C, A, B" should not change the answer — the set is the same. In practice, it does change the answer, because the model's hidden state depends on the order it read things.

Standard seq2seq models assume ordered sequences. But many tasks involve **sets**:

- **Input sets**: Point clouds, object collections
- **Output sets**: Predicted tags, detected objects
- **Both**: Sorting (input set → output sequence)

Naively treating sets as sequences introduces spurious ordering dependencies — the model wastes capacity learning to cope with orderings that never should have mattered.

## Input Order Sensitivity

Experiment: sort numbers using seq2seq. The same set, presented in different orders, can succeed or fail:

| Input Order | Output |
|-------------|--------|
| [3, 1, 4, 2] | [1, 2, 3, 4] ✓ |
| [1, 2, 3, 4] | [1, 2, 3, 4] ✓ |
| [4, 3, 2, 1] | [1, 2, 3, ?] ✗ |

Different input orderings can lead to different (wrong) outputs — even though logically the task is identical.

## Interactive Demo

Explore how input order affects set processing:

*Interactive demo: https://aipedia.org/order-matters*

## Solution: Read-Process-Write

The paper proposes a three-phase architecture. The trick: replace "read the elements in order" with "look at all elements through attention", which is order-invariant by construction.

### 1. Read

Embed all input elements independently (no order involved yet):

$$
\{e_1, e_2, ..., e_n\} = \text{Embed}(x_1, x_2, ..., x_n)
$$

### 2. Process

An LSTM repeatedly *attends over the whole set* instead of consuming elements one by one:

$$
q_t = \text{LSTM}(q_{t-1})
$$
$$
\alpha_i = \text{softmax}(e_i \cdot q_t)
$$
$$
r_t = \sum_i \alpha_i e_i
$$

The weighted sum $r_t$ is the same no matter how you shuffle the elements — that is where the order-invariance comes from. Multiple processing steps refine the representation.

### 3. Write

Generate the output sequence with a [pointer network](https://aipedia.org/pointer-networks), selecting input elements one at a time:

$$
p(y_i | y_{<i}, M) = \text{Attention}(s_i, M)
$$

## Output Order Learning

Some tasks have output *sets* too — the correct answer is a collection, but the model must emit it in some order. Which order should the training data use? The paper's answer: let the model search for the ordering that is easiest to learn:

$$
\mathcal{L} = \min_{\pi \in S_n} \sum_i -\log p(y_{\pi(i)} | y_{\pi(<i)})
$$

In words: among all permutations of the target output, train against the one the model currently finds most probable.

## Key Results

### Sorting

| Model | Accuracy |
|-------|----------|
| Seq2seq | 72% |
| Seq2seq + Attention | 87% |
| **Read-Process-Write** | **94%** |

### Convex Hull

Sorting input points by angle dramatically improved performance — demonstrating that "natural" orderings help learning even when the task is order-free in principle.

## Implications

1. **Order is a hyperparameter**: Choice of ordering affects learning
2. **Attention enables invariance**: Attention over sets removes order dependence
3. **Output order matters**: Some orderings are easier to learn than others

## Connection to Transformers

The Read-Process-Write architecture anticipated:

- **Set attention** (now standard in Transformers)
- **Iterative refinement** (multiple attention layers)
- **Permutation invariance** (via attention aggregation)

A [Transformer](https://aipedia.org/transformer) encoder without positional encodings is essentially a permutation-invariant set processor — the same core insight, scaled up.

## Common Confusion

- **"Order matters" — for what?** The title means input/output *element ordering* affects seq2seq training. It is not about word order in language.
- **Set vs. sequence**: a sequence has meaningful positions ("first", "second"); a set does not. The bug this paper diagnoses is feeding sets into models that assume positions mean something.
- **Order Matters vs. [Pointer Networks](https://aipedia.org/pointer-networks)**: Pointer Networks (same lead author) give models an input-sized output vocabulary; this paper studies ordering effects and *uses* a pointer network as its Write phase.
- **Invariance from attention vs. from sorting**: the paper offers two remedies — an architecture that ignores order (attention), and picking a good canonical order (e.g., sort by angle). Both work; they are different strategies.

## Where To Go Next

- Read [Pointer Networks](https://aipedia.org/pointer-networks) for the output mechanism used in the Write phase.
- Read [Seq2Seq](https://aipedia.org/seq2seq) for the baseline architecture whose assumptions this paper questions.
- Read [Transformer](https://aipedia.org/transformer) and [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) to see set attention become the dominant paradigm.
- Read [Bahdanau Attention](https://aipedia.org/bahdanau-attention) for the original attention mechanism.


# Pointer Networks

> Neural architecture that outputs pointers to input positions, enabling variable-size outputs

- Type: Paper
- By: Vinyals, Fortunato & Jaitly
- Year: 2015
- Topics: Deep learning, Attention, Seq2seq, Combinatorial
- Page: https://aipedia.org/pointer-networks

## Resources

- [Pointer Networks](https://arxiv.org/abs/1506.03134): Paper, Vinyals, Fortunato & Jaitly, 2015

**Pointer Networks** fix a blind spot in sequence-to-sequence models: a standard seq2seq model can only output words from a fixed, pre-decided vocabulary. A Pointer Network instead outputs *pointers back into its own input* — "the answer is element 3, then element 7, then element 1" — so the set of possible outputs grows and shrinks with the input.

> This page builds on [Seq2Seq](https://aipedia.org/seq2seq) and [Bahdanau Attention](https://aipedia.org/bahdanau-attention). If either is unfamiliar, read those first.

## Why Students Should Care

- Pointer Networks introduced the idea of **attention as output**, not just as an internal routing mechanism — a small twist with a long legacy.
- They are the standard tool when a neural network must *select* items from its input: copying rare words, choosing spans, ordering elements.
- Their "copy from the input" idea lives on in summarization models, extractive QA, and the copy mechanisms inside modern text generators.

## The Problem, Concretely

Suppose you want a neural network to compute the **convex hull** of a set of points: given 10 points, output the ones on the outer boundary, in order. Now give it 50 points. The "vocabulary" of possible answers just changed — it is the input points themselves, and there are 50 of them now instead of 10.

A standard seq2seq model produces outputs from a fixed dictionary:

$$
P(y_i | y_1, ..., y_{i-1}, x) = \text{softmax}(W \cdot h_i)
$$

The matrix $W$ has one row per vocabulary item, fixed at training time. There is no way for this output layer to say "point number 37" when the model was built for at most 10 points. For convex hull, the output is indices into the input — vocabulary size equals input size, and that changes every example.

## The Pointer Mechanism

The fix is elegant: you already have a mechanism that scores every input position at every decoding step — **attention**. Instead of using attention to build a context vector and then predicting from a fixed vocabulary, use the attention weights themselves *as the output distribution*:

$$
u_j^i = v^T \tanh(W_1 e_j + W_2 d_i)
$$

$$
P(y_i | y_1, ..., y_{i-1}, x) = \text{softmax}(u^i)
$$

Here $u_j^i$ is a score for "how much should output step $i$ point at input position $j$". Softmax over these scores gives a probability distribution over input positions — the attention weights $\alpha_{ij}$ directly become the output probabilities.

The takeaway: **a Pointer Network is a seq2seq model whose output layer is an attention mechanism over the input.** Nothing else changes.

## Architecture

1. **Encoder**: Process input sequence $(x_1, ..., x_n)$ to get representations $(e_1, ..., e_n)$
2. **Decoder**: At each step, produce hidden state $d_i$
3. **Pointer**: Compute attention over encoder states, output highest-attention position

## Interactive Demo

Watch a Pointer Network solve convex hull by pointing to input coordinates:

*Interactive demo: https://aipedia.org/pointer-networks*

## Applications

All of these share the same shape: the answer is a selection or ordering of the input elements.

### Convex Hull

Given points, output the subset forming the convex hull. Output size varies with input geometry.

### Delaunay Triangulation

Given points, output triangles. Number of triangles depends on point configuration.

### Traveling Salesman Problem

Approximate TSP by learning to output city visitation order.

### Sorting

Learn to sort sequences by outputting indices in sorted order.

## Why Pointers Matter

| Standard Seq2Seq | Pointer Network |
|-----------------|-----------------|
| Fixed vocabulary | Input-dependent vocabulary |
| Can't reference input | Output references input |
| Fixed output size | Variable output size |

## Key Equations

For reference, the full model. Encoder (bidirectional LSTM):

$$
e_j = [\overrightarrow{h}_j; \overleftarrow{h}_j]
$$

Decoder with attention:

$$
d_i = \text{LSTM}(d_{i-1}, [y_{i-1}; c_{i-1}])
$$

Pointer distribution:

$$
P(y_i = j) = \frac{\exp(u_j^i)}{\sum_k \exp(u_k^i)}
$$

You do not need to memorize these. They are a standard attention-based seq2seq model — the only novelty is that the last softmax ranges over input positions instead of a vocabulary.

## Influence

Pointer Networks introduced the idea of using attention as output, which influenced:

- **Copy mechanisms** in text generation
- **Pointer-generator networks** for summarization
- **Graph neural network outputs**

## Common Confusion

- **Pointer Networks vs. attention**: ordinary attention ([Bahdanau Attention](https://aipedia.org/bahdanau-attention)) is used *internally* to build a context vector; Pointer Networks repurpose the attention distribution as the *final output*.
- **Pointing vs. generating**: a pure Pointer Network can only select input elements — it cannot produce a token that is not in the input. Pointer-generator hybrids mix both abilities.
- **Pointer Networks vs. [Order Matters](https://aipedia.org/order-matters)**: same lead author, related problems. Pointer Networks solve *variable output vocabularies*; Order Matters studies how *element ordering* affects models operating on sets (and uses pointers in its Write phase).

## Where To Go Next

- Read [Order Matters](https://aipedia.org/order-matters) for the follow-up work on set-structured inputs and outputs.
- Read [Bahdanau Attention](https://aipedia.org/bahdanau-attention) for the attention mechanism being repurposed here.
- Read [Seq2Seq](https://aipedia.org/seq2seq) for the encoder-decoder backbone.
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) to see where attention-centric architectures went next.


# ResNet

> Deep residual learning with skip connections that enabled training of 152+ layer networks

- Type: Paper
- By: He et al.
- Year: 2015
- Topics: Deep learning, CNNs, Vision, Residual
- Page: https://aipedia.org/resnet

## Resources

- [Deep Residual Learning for Image Recognition](https://arxiv.org/abs/1512.03385): Paper, He, Zhang, Ren & Sun, 2015

**ResNet** (Residual Network) introduced skip connections: shortcuts that let a layer's input bypass the layer and be added back to its output. This simple change made it possible to train networks with over 150 layers, and ResNet won the 2015 ImageNet challenge with a 3.57% error rate — surpassing human-level performance.

> If CNNs are new to you, read [AlexNet](https://aipedia.org/alexnet) or [CS231n](https://aipedia.org/cs231n) first. This page covers the original ResNet. For the follow-up paper that refined the design, see [Identity Mappings in Deep Residual Networks](https://aipedia.org/resnet-identity).

## Why Students Should Care

- Skip connections are now **everywhere**: nearly every modern vision model and every [Transformer](https://aipedia.org/transformer) uses residual connections.
- ResNet explains a core lesson of deep learning: the obstacle to depth was not overfitting but **optimization** — and a small architectural change fixed it.
- ResNet-style backbones remained the default in computer vision for years and are still widely used.

## The Degradation Problem

Here is the puzzle that motivated ResNet. You take a 20-layer network that works well, add more layers, and expect it to do at least as well — the extra layers could simply copy their input. Instead, the deeper network gets *worse*:

$$
\text{Error}_{56\text{-layer}} > \text{Error}_{20\text{-layer}}
$$

Crucially, this was not overfitting — **training error** also increased. The deeper network was not memorizing too much; it was failing to optimize at all. Apparently, plain stacked layers find it surprisingly hard to learn even the identity function ("just pass the input through unchanged").

## Residual Learning

ResNet's fix: stop asking layers to learn the full mapping. Instead of learning a desired mapping $H(x)$ directly, each block learns only the **residual** — the difference between the output and the input:

$$
F(x) = H(x) - x
$$

The block's output then becomes:

$$
y = F(x) + x
$$

The key insight: if the best thing a block can do is nothing (identity), it is much easier to push $F(x) \rightarrow 0$ (just shrink some weights toward zero) than to make a stack of nonlinear layers learn $H(x) = x$ exactly.

You do not need to memorize the equations. The important idea is: **each block learns a small correction to its input, not a whole new representation**.

## Skip Connections

The identity shortcut $x$ bypasses the layers and is added to the output:

$$
y = \mathcal{F}(x, \{W_i\}) + x
$$

These shortcuts:

- Add **no extra parameters** — the shortcut is just addition
- Enable gradient flow through hundreds of layers
- Allow each block to refine features rather than transform them completely

## Block Architectures

- **Basic Block** (ResNet-18/34): two 3×3 convolutions
- **Bottleneck Block** (ResNet-50/101/152): 1×1 → 3×3 → 1×1 convolutions, where the 1×1 layers shrink and then restore the channel count for efficiency

## Interactive Demo

Explore residual blocks and toggle skip connections to see their effect:

*Interactive demo: https://aipedia.org/resnet*

## Why It Works

Skip connections create **gradient highways**. Look at how the gradient flows backward through a block:

$$
\frac{\partial \mathcal{L}}{\partial x} = \frac{\partial \mathcal{L}}{\partial y} \cdot \left(1 + \frac{\partial F}{\partial x}\right)
$$

The "1" term is the shortcut. Even if the gradient through the layers ($\partial F / \partial x$) becomes tiny, the gradient can still flow directly backward through the addition. That prevents vanishing gradients even in very deep networks.

One-line takeaway: **the shortcut guarantees every layer receives a usable gradient, no matter how deep the network is**.

## Impact

ResNet's influence extends far beyond image classification:

- Foundation for most modern vision architectures
- Inspired the residual connections used in [Transformers](https://aipedia.org/transformer)
- Enabled training of networks with 1000+ layers (see [Identity Mappings](https://aipedia.org/resnet-identity))

## Common Confusion

- **The degradation problem is not overfitting.** Overfitting means low training error but high test error. Degradation means even *training* error got worse with depth — an optimization failure, not a generalization failure.
- **ResNet is the architecture; a skip (residual) connection is the technique.** Skip connections now appear in many models that are not ResNets, including Transformers.
- **ResNet vs. [Identity Mappings](https://aipedia.org/resnet-identity):** the original 2015 paper introduced residual learning; the 2016 follow-up analyzed the shortcuts more carefully and proposed the improved pre-activation design.

## Where To Go Next

- Read [Identity Mappings in Deep Residual Networks](https://aipedia.org/resnet-identity) for the refined pre-activation design
- Read [AlexNet](https://aipedia.org/alexnet) for the network that started the deep CNN era
- Read [Batch Normalization](https://aipedia.org/batch-normalization) for the other key ingredient in training deep networks
- Read [Transformer](https://aipedia.org/transformer) to see residual connections outside of vision


# Identity Mappings in Deep Residual Networks

> Pre-activation ResNet design that enables training of 1000+ layer networks

- Type: Paper
- By: He et al.
- Year: 2016
- Topics: Deep learning, CNNs, Vision, Residual
- Page: https://aipedia.org/resnet-identity

## Resources

- [Identity Mappings in Deep Residual Networks](https://arxiv.org/abs/1603.05027): Paper, He, Zhang, Ren & Sun, 2016

**Identity Mappings in Deep Residual Networks** is the follow-up paper to [ResNet](https://aipedia.org/resnet). It asks a sharper question — *why exactly do skip connections work, and can we make them work better?* — and answers it with an improved design, the **pre-activation ResNet**, which enables training networks with over 1000 layers.

> Read [ResNet](https://aipedia.org/resnet) first. This page assumes you know what a residual block and a skip connection are.

## Why Students Should Care

- This paper shows how a **tiny architectural change** — reordering ReLU and batch norm — can be the difference between a network that trains and one that does not.
- It gives the cleanest mathematical picture of *why* skip connections help, via a direct gradient formula.
- The lesson generalizes: keep the shortcut path as clean as possible. Modern architectures follow this principle.

## The Problem with Original ResNet

Think of a residual network as having two paths: a **shortcut path** (the identity) and a **residual path** (the layers). The whole benefit of ResNet comes from the shortcut being a clean, unobstructed highway.

But in the original ResNet, the block applies ReLU *after* the addition:

$$
h_{l+1} = \text{ReLU}(h_l + \mathcal{F}(h_l, W_l))
$$

That means the shortcut path is not a pure identity — the signal passes through a nonlinearity at every block. Over hundreds of blocks, these small obstructions add up and can impede gradient flow in very deep networks.

## Pure Identity Shortcuts

The key insight: for optimal gradient propagation, the shortcut should be a **clean identity mapping** — nothing on the highway at all:

$$
h_{l+1} = h_l + \mathcal{F}(h_l, W_l)
$$

Why does this matter? Apply the formula repeatedly and something nice happens — any deep layer is just the sum of a shallow layer plus all the residuals in between:

$$
h_L = h_l + \sum_{i=l}^{L-1} \mathcal{F}(h_i, W_i)
$$

In plain English: **layer 1000 can see layer 1 directly**, with no nonlinearities in the way.

## Pre-activation Design

How do you get pure identity shortcuts while keeping batch norm and ReLU? Move them *before* the convolution instead of after (hence "pre-activation"):

$$
y = x + \text{Conv}(\text{ReLU}(\text{BN}(x)))
$$

Same components, different order. This subtle rearrangement leaves the shortcut path completely clean and enables training of 1001-layer networks.

## Interactive Demo

Compare the original post-activation design with the improved pre-activation version:

*Interactive demo: https://aipedia.org/resnet-identity*

## Why Pre-activation Works

The gradient of the loss with respect to any layer $l$:

$$
\frac{\partial \mathcal{L}}{\partial h_l} = \frac{\partial \mathcal{L}}{\partial h_L} \left(1 + \frac{\partial}{\partial h_l}\sum_{i=l}^{L-1}\mathcal{F}_i\right)
$$

You do not need to memorize this. The important part is the "1": it means the gradient at any layer includes a **direct, undiminished copy** of the gradient from the top of the network, unimpeded by nonlinearities. Vanishing gradients cannot happen along the shortcut path.

## Results

| Architecture | CIFAR-10 Error | CIFAR-100 Error |
|-------------|----------------|-----------------|
| ResNet-110 (original) | 6.61% | - |
| ResNet-110 (pre-act) | 6.37% | - |
| ResNet-1001 (pre-act) | 4.92% | 22.71% |

Pre-activation enables training of networks 10× deeper with better performance.

## Common Confusion

- **This is a different paper from ResNet.** [ResNet](https://aipedia.org/resnet) (2015) introduced residual learning; this paper (2016, same authors) analyzed it and improved the block design.
- **Post-activation vs. pre-activation** refers to *where ReLU and BN sit relative to the addition*: after the addition in the original design, before the convolution in the improved one.
- **Both designs use skip connections.** The difference is whether the shortcut path is a *pure* identity (pre-activation) or passes through a ReLU (original).

## Where To Go Next

- Read [ResNet](https://aipedia.org/resnet) if you have not already — this paper builds directly on it
- Read [Batch Normalization](https://aipedia.org/batch-normalization) to understand the BN component being reordered here
- Read [Transformer](https://aipedia.org/transformer) to see clean residual paths reused in modern architectures


# Variational Lossy Autoencoder

> Understanding VAEs as compression systems with a rate-distortion trade-off

- Type: Paper
- By: Chen et al.
- Year: 2016
- Topics: Deep learning, VAEs, Compression, Generative
- Page: https://aipedia.org/variational-lossy-autoencoder

## Resources

- [Variational Lossy Autoencoder](https://arxiv.org/abs/1611.02731): Paper, Chen et al., 2016

**Variational Lossy Autoencoder (VLAE)** is a way of looking at VAEs through the lens of compression. Instead of asking only "can the model reconstruct the input?", it asks "how many bits should the latent code use, and what reconstruction quality do we get in return?"

> Read [VAE](https://aipedia.org/vae) first if you are new to the topic. This page is best understood as a second pass that explains what the VAE objective means.

## A Compression Analogy

Think about compressing an image before sending it over a network.

- If you keep many details, the file is large but reconstruction is accurate
- If you compress aggressively, the file is small but details are lost

VLAE says a VAE is solving that same trade-off in learned form.

## VAEs as Compressors

A VAE has two main parts:

- **Encoder** $q(z|x)$: turn the input into a latent code
- **Decoder** $p(x|z)$: reconstruct the input from that code

This suggests two competing goals:

- **Rate**: how many bits are needed to describe the latent
- **Distortion**: how much reconstruction error we allow

## The Rate-Distortion Objective

The VAE objective can be written as:

$$
\mathcal{L} = \underbrace{-\mathbb{E}_{q(z|x)}[\log p(x|z)]}_{\text{Distortion}} + \underbrace{\beta \cdot D_{KL}(q(z|x) \| p(z))}_{\text{Rate}}
$$

The first term rewards accurate reconstruction. The second term discourages the model from storing too much information in the latent code.

## Interactive Demo

Explore the rate-distortion trade-off and bits-back coding:

*Interactive demo: https://aipedia.org/variational-lossy-autoencoder*

## Why This View Is Useful

Once you think of a VAE as a compressor, several behaviors make more sense:

- a stronger decoder can sometimes ignore the latent
- changing $\beta$ changes how much information the latent is allowed to carry
- "posterior collapse" becomes easier to interpret

## Bits-Back Coding

The famous bits-back argument says the KL term can overstate the true effective cost of the latent because stochastic decoding can recover some information "for free."

$$
\text{Rate} = D_{KL}(q(z|x) \| p(z))
$$

That is the technical idea behind why VAEs connect so naturally to information theory and compression.

For a first pass, the most important takeaway is simpler: **the latent cost is not just a regularizer; it is part of a coding trade-off**.

## Posterior Collapse

If the decoder becomes so strong that it can reconstruct well without using the latent, then the model may push:

$$
q(z|x) \approx p(z)
$$

In that case, the latent carries very little information. This is called **posterior collapse**.

## Common Fixes

| Method | Goal |
|--------|------|
| KL annealing | Let reconstruction stabilize before strongly penalizing rate |
| Free bits | Reserve a minimum amount of information in the latent |
| $\beta$-VAE | Directly control the rate-distortion trade-off |

## What To Remember

- VLAE interprets VAEs as lossy compression systems
- The KL term is about information budget, not just regularization
- Posterior collapse means the model has stopped using the latent effectively


# A Simple Neural Network Module for Relational Reasoning

> Relation Networks for learning to reason about object relationships

- Type: Paper
- By: Santoro et al.
- Year: 2017
- Topics: Deep learning, Reasoning, Attention, Visual QA
- Page: https://aipedia.org/relational-reasoning

## Resources

- [A Simple Neural Network Module for Relational Reasoning](https://arxiv.org/abs/1706.01427): Paper, Santoro et al., 2017

**A Simple Neural Network Module for Relational Reasoning** introduced Relation Networks (RNs) — a small, plug-in architecture built on one idea: to reason about relationships, explicitly look at **every pair of objects**. Despite its simplicity, it beat humans on a visual reasoning benchmark.

> No heavy prerequisites here — just basic neural network concepts (MLPs and CNNs). This is one of the most accessible "reasoning" papers in deep learning.

## Why Students Should Care

- It is a clean case study in **inductive bias**: bake the *shape* of the problem (pairwise relations) into the architecture, and a simple model suddenly beats much bigger generic ones.
- It achieved superhuman accuracy on CLEVR, a benchmark specifically designed to require reasoning, not pattern matching.
- Pairwise-interaction thinking is everywhere: self-attention in [Transformers](https://aipedia.org/transformer), edges in [graph neural networks](https://aipedia.org/neural-message-passing), and memory interactions in [Relational RNNs](https://aipedia.org/relational-rnn).

## The Problem

Standard neural networks struggle with questions that hinge on *relationships*:

- "Is object A larger than object B?"
- "What is between the red and blue objects?"
- "Are there more circles than squares?"

A CNN is great at detecting *what* is in an image, but nothing in its architecture compares one detected thing to another. These questions require comparing pairs of entities — and standard architectures give the model no direct way to do that.

## Relation Networks: Just Compare Every Pair

The key insight: don't hope the network discovers pairwise comparison — build it in. Run a small network over **all pairs** of objects, then sum the results:

$$
\text{RN}(O) = f_\phi\left(\sum_{i,j} g_\theta(o_i, o_j)\right)
$$

where:

- $o_i, o_j$ are object representations
- $g_\theta$ is a small MLP that processes each pair — the "relation" function
- $f_\phi$ is another MLP that turns the summed relations into an answer

In words: **score every pair, add up the scores, read out the answer**. That is the entire architecture.

## Interactive Demo

Explore relational reasoning on simple visual scenes:

*Interactive demo: https://aipedia.org/relational-reasoning*

## Why Pairs Matter

For $n$ objects, the RN considers all $n^2$ pairs. This:

- Captures relations regardless of object order (summing is order-independent)
- Scales to variable numbers of objects (the same $g_\theta$ is reused for every pair)
- Avoids hardcoding *which* relations matter — $g_\theta$ learns that from data

## Architecture Details

For visual question answering, "objects" don't need to be detected explicitly:

1. **CNN** extracts a feature map from the image
2. **Objects** = the spatial locations (cells) of that feature map
3. The **question** embedding is concatenated to each pair
4. **g network** (MLP) processes each $(o_i, o_j, q)$ triple
5. **Sum** over all pairs
6. **f network** (MLP) produces the answer

Step 3 is worth noticing: conditioning on the question lets the *same* pair of objects be related differently depending on what is being asked.

## Results on CLEVR

CLEVR is a visual reasoning benchmark with questions like "What size is the cylinder that is left of the brown metal thing?" — designed so that shortcut statistics don't work.

| Model | Accuracy |
|-------|----------|
| CNN + LSTM | 42.7% |
| CNN + LSTM + Attention | 68.5% |
| **Relation Network** | **95.5%** |
| Human | 92.6% |

RNs achieved superhuman performance — on a task where generic architectures barely beat chance-plus-heuristics.

## Key Properties

**Permutation invariant**: summing over pairs is order-independent, so shuffling the objects changes nothing

**Relation-centric**: pairwise interactions are modeled explicitly, not left for the network to discover

**Data efficient**: the strong inductive bias means less data is needed to learn relational tasks

## Beyond Vision

RNs also improved:

- **Text QA** (bAbI dataset)
- **Physical reasoning** (predicting dynamics)
- **Graph problems** (when combined with GNNs)

## Connection to Attention

Self-attention can be viewed as a form of relation network:

$$
\text{Attention}(Q, K, V) \approx \sum_{i,j} \text{softmax}(q_i \cdot k_j) \cdot v_j
$$

Both aggregate pairwise interactions; attention additionally learns *weights* for each pair instead of summing them uniformly.

## Common Confusion

- **Relation Networks vs. [Relational RNNs](https://aipedia.org/relational-rnn)**: RNs compare all object pairs within a single input; Relational RNNs let memory slots interact over *time*. Related idea, different setting.
- **Relation Networks vs. graph neural networks**: an RN is like one round of [message passing](https://aipedia.org/neural-message-passing) on a *fully connected* graph — every object talks to every object, no graph structure required.
- **"Objects" are not detections**: in the vision setup, objects are just feature-map cells. No object detector is involved.
- **The $n^2$ cost is real**: comparing all pairs is quadratic in the number of objects — the same scaling cost that self-attention pays over sequence length.

## Where To Go Next

- Read [Relational RNNs](https://aipedia.org/relational-rnn) for pairwise interaction applied to recurrent memory.
- Read [Neural Message Passing](https://aipedia.org/neural-message-passing) for the general graph-structured version of this idea.
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for learned, weighted pairwise interaction at scale.
- Read [CS231n](https://aipedia.org/cs231n) for the CNN background used in the vision pipeline here.


# Attention Is All You Need

> The 2017 paper that introduced the Transformer architecture

- Type: Paper
- By: Vaswani et al.
- Year: 2017
- Topics: Architecture, Attention, Deep learning, NLP, Transformers
- Page: https://aipedia.org/attention-is-all-you-need

## Resources

- [Attention Is All You Need](https://arxiv.org/abs/1706.03762): Paper, Vaswani et al., 2017
- [tensorflow/tensor2tensor](https://github.com/tensorflow/tensor2tensor): Code, Original implementation
- [The Annotated Transformer](https://nlp.seas.harvard.edu/annotated-transformer/): Article, Rush, 2018
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://arxiv.org/abs/1409.0473): Paper, Bahdanau, Cho & Bengio, 2014

**Attention Is All You Need** is the 2017 paper that introduced the Transformer. If you want the general concept first, start with [Transformer](https://aipedia.org/transformer). This page focuses on **what the paper changed, why it mattered, and what results it achieved**.

> Before this paper, neural machine translation was dominated by recurrent models such as LSTMs and GRUs. The paper's big claim was that a sequence model could work using attention alone.

## The Problem the Paper Solved

Older sequence-to-sequence models had three recurring problems:

- **They were slow to train** because tokens had to be processed one after another
- **They struggled with long-range dependencies** because information had to travel through many recurrent steps
- **They compressed the whole input too aggressively** in encoder-decoder setups

The paper asked: what if every token could directly look at every other token it needs?

## The Core Innovation

The main building block was **scaled dot-product attention**:

$$
\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V
$$

In plain English:

- compare each token's query to other tokens' keys
- turn those scores into weights
- use the weights to mix the values

That gave the model a direct way to connect related words, even when they were far apart in the sentence.

## Multi-Head Attention

Instead of learning one attention pattern, the paper learned several at once:

$$
\text{MultiHead}(Q, K, V) = \text{Concat}(\text{head}_1, \dots, \text{head}_h)W^O
$$

$$
\text{head}_i = \text{Attention}(QW_i^Q, KW_i^K, VW_i^V)
$$

This let different heads focus on different relationships, such as grammar, word alignment, or longer-range context.

## Positional Encoding

Attention by itself does not encode order, so the paper added sinusoidal positional encodings:

$$
PE_{(pos, 2i)} = \sin\left(\frac{pos}{10000^{2i/d_{\text{model}}}}\right)
$$

$$
PE_{(pos, 2i+1)} = \cos\left(\frac{pos}{10000^{2i/d_{\text{model}}}}\right)
$$

You can think of these as extra signals that tell the model where each token appears in the sequence.

## Interactive Demo

Explore scaled dot-product attention, multi-head patterns, positional encodings, and the full architecture:

*Interactive demo: https://aipedia.org/attention-is-all-you-need*

## The Architecture in Words

The paper used an **encoder-decoder** Transformer:

**Encoder**:
1. Multi-head self-attention
2. Residual connection + layer normalization
3. Feed-forward network
4. Another residual connection + layer normalization

**Decoder**:
1. Masked self-attention so future tokens stay hidden
2. Cross-attention to the encoder outputs
3. Feed-forward network

The original model used 6 encoder layers, 6 decoder layers, model width 512, and 8 heads.

## Why It Worked

| Property | RNN | Transformer |
|----------|-----|-------------|
| Sequential ops per layer | O(n) | O(1) |
| Maximum path length | O(n) | O(1) |
| Parallelizable | No | Yes |

Two practical consequences mattered:

- training became much more parallel
- any two positions could interact in one step instead of many

## Results from the Paper

The paper reached state-of-the-art machine translation results:

- **EN-DE**: 28.4 BLEU
- **EN-FR**: 41.0 BLEU
- **Training time**: about 3.5 days on 8 P100 GPUs

For students, the exact numbers matter less than the message: **this was not just a neat idea; it won on real benchmarks**.

## Legacy

This paper directly led to:

- [BERT](https://aipedia.org/bert) for bidirectional language understanding
- [GPT](https://aipedia.org/gpt) for autoregressive text generation
- [Vision Transformer](https://aipedia.org/vision-transformer) for images
- modern LLMs built on scaled Transformer variants

## What To Remember

- The paper introduced the Transformer
- The key mechanism was self-attention
- The breakthrough was both conceptual and practical: better long-range modeling and much better parallelism


# Neural Message Passing for Quantum Chemistry

> A unified framework for graph neural networks applied to molecular property prediction

- Type: Paper
- By: Gilmer et al.
- Year: 2017
- Topics: Deep learning, GNNs, Chemistry, Graphs
- Page: https://aipedia.org/neural-message-passing

## Resources

- [Neural Message Passing for Quantum Chemistry](https://arxiv.org/abs/1704.01212): Paper, Gilmer et al., 2017
- [A Gentle Introduction to Graph Neural Networks](https://distill.pub/2021/gnn-intro/): Article, Distill, 2021

**Neural Message Passing for Quantum Chemistry** introduced the Message Passing Neural Network (MPNN) framework — a single recipe that turned out to describe most existing graph neural networks. The paper both unified the field and set a new state of the art on predicting molecular properties.

> New to graphs in deep learning? The only prerequisite is the idea that data can be nodes connected by edges. If you want the "compare everything to everything" special case first, read [Relational Reasoning](https://aipedia.org/relational-reasoning).

## Why Students Should Care

- **Graphs are everywhere**: molecules, social networks, road maps, program syntax trees, citation networks. MPNN is the standard mental model for learning on all of them.
- The framework move — showing that many competing architectures are one algorithm with different plug-ins — is a pattern you will see repeatedly in ML research.
- The application is real: predicting quantum-chemical properties with a neural net in milliseconds instead of hours of physics simulation opened the door to ML-driven drug and materials discovery.

## The Problem

Molecules are naturally graphs: atoms are nodes, bonds are edges. Predicting properties like energy or toxicity requires learning from this graph structure.

Why not just use a standard network? Because molecules have no natural ordering (which atom is "first"?) and vary in size. A graph network handles both automatically, because it operates on the connectivity itself.

## Message Passing: The Gossip Protocol

Here is the intuition before any notation. Every atom starts out knowing only about itself ("I am carbon"). In each round, every atom sends a message to its bonded neighbors and updates its own summary based on what it hears. After one round, each atom knows about its neighbors; after two rounds, its neighbors' neighbors; after $T$ rounds, information has spread $T$ hops across the molecule. Finally, all the atom summaries are pooled into one prediction for the whole molecule.

MPNNs formalize this in two phases.

### 1. Message Passing Phase

For $T$ timesteps, each node $v$ collects messages from its neighbors $N(v)$:

$$
m_v^{t+1} = \sum_{u \in N(v)} M_t(h_v^t, h_u^t, e_{vu})
$$

Then updates its hidden state:

$$
h_v^{t+1} = U_t(h_v^t, m_v^{t+1})
$$

### 2. Readout Phase

Aggregate all final node states into a graph-level prediction:

$$
\hat{y} = R(\{h_v^T | v \in G\})
$$

You do not need to memorize the symbols. The important idea is: **a message function $M$ (what neighbors say), an update function $U$ (how a node revises its state), and a readout function $R$ (how the graph votes on the answer)**. Choose those three, and you have specified a graph neural network.

## Interactive Demo

Watch messages flow through a molecular graph:

*Interactive demo: https://aipedia.org/neural-message-passing*

## Key Components

| Component | Function | Common Choices |
|-----------|----------|----------------|
| **M** (Message) | Computes edge messages | MLP, attention |
| **U** (Update) | Updates node states | GRU, LSTM |
| **R** (Readout) | Graph-level output | Sum, attention |

## Unifying Prior Work

The MPNN framework encompasses:

- **Convolutional Networks on Graphs** (Duvenaud et al.)
- **Gated Graph Neural Networks** (Li et al.)
- **Interaction Networks** (Battaglia et al.)
- **Deep Tensor Neural Networks** (Schütt et al.)

Each is an MPNN with specific $M$, $U$, and $R$ functions. Before this paper, these looked like rival architectures; after it, they were points in one design space.

## Virtual Graph Elements

One limitation of pure message passing: information travels one bond per round, and some chemistry depends on atoms that are *near in space* but not bonded. The paper's fix is "virtual edges" connecting all atom pairs:

$$
e_{vu} = (d_{vu}, \text{bond type})
$$

where $d_{vu}$ is the 3D distance. This lets the network reason about non-bonded interactions directly.

## Results on QM9

Predicting molecular properties on the QM9 dataset (lower error = better):

| Property | Units | MPNN Error |
|----------|-------|------------|
| HOMO | eV | 0.043 |
| LUMO | eV | 0.038 |
| Gap | eV | 0.066 |
| μ | Debye | 0.030 |

MPNN achieved chemical accuracy on most targets — meaning errors small enough for the predictions to be practically useful to chemists.

## Why This Matters

1. **Unified framework**: clarified the design space of graph neural networks
2. **Practical impact**: enabled ML-accelerated drug discovery
3. **Architectural insight**: showed that message passing is the key inductive bias for graph data

## Legacy

MPNNs became the foundation for:

- **SchNet** — continuous-filter convolutions
- **DimeNet** — directional message passing
- **Equivariant GNNs** — respecting 3D symmetries

## Common Confusion

- **MPNN is a framework, not one model**: "an MPNN" usually means "some choice of $M$, $U$, $R$." The paper's best QM9 model is one instance.
- **Message passing vs. attention**: a [Transformer](https://aipedia.org/transformer) is essentially message passing on a fully connected graph where message weights come from attention. GNNs restrict messages to actual edges.
- **Rounds vs. layers**: each message-passing step plays the role of a layer; $T$ rounds means information can travel at most $T$ hops.
- **Graph-level vs. node-level tasks**: the readout phase is for predicting a property of the *whole* graph; node-level tasks (like classifying each atom) skip or change $R$.

## Where To Go Next

- Read [Relational Reasoning](https://aipedia.org/relational-reasoning) for the fully-connected, single-round special case of this idea.
- Read [Relational RNNs](https://aipedia.org/relational-rnn) for attention-based interaction applied to memory over time.
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) to see message passing with learned attention weights on a complete graph.
- Read [Neural ODE](https://aipedia.org/node) for another example of a paper reframing many architectures as one continuous framework.


# World of Bits

> Open-domain platform for web-based reinforcement learning agents

- Type: Paper
- By: Shi et al.
- Year: 2017
- Topics: Reinforcement learning, Web agents, Benchmark, Multimodal
- Page: https://aipedia.org/world-of-bits

## Resources

- [World of Bits: An Open-Domain Platform for Web-Based Agents](http://proceedings.mlr.press/v70/shi17a.html): Paper, Shi et al., ICML 2017
- [Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration](https://arxiv.org/abs/1802.08802): Paper, Liu et al., 2018
- [WebGPT: Browser-assisted question-answering with human feedback](https://arxiv.org/abs/2112.09332): Paper, Nakano et al., 2021

**World of Bits (WoB)** is a platform introduced by Shi et al. (2017) where AI agents learn to complete tasks on the web using the same interface humans use: looking at rendered pages and performing low-level keyboard and mouse actions.

> This page assumes basic [Reinforcement Learning](https://aipedia.org/reinforcement-learning) vocabulary (agent, environment, reward). If those terms are new, start there.

## Why Students Should Care

- WoB is the direct ancestor of today's computer-use and browser agents — the idea of "an AI that clicks around the web" starts here.
- It shows how to turn a messy real-world domain (the web) into a well-defined RL environment.
- The benchmark gap it exposed (agents far below human performance on multi-step web tasks) drove years of follow-up work and is still not fully closed.

## Core Idea

WoB treats the web as an open-domain reinforcement learning environment. At each timestep, an agent receives:

- **Pixels** $\mathcal{I} \in \mathbb{R}^{W \times H \times 3}$ — rendered webpage screenshot
- **DOM** $\mathcal{D}$ — Document Object Model (the page's element tree) with element coordinates
- **Reward** $r$ — task completion signal

The agent outputs mouse coordinates $(x, y)$ and keyboard actions to interact with the webpage. Nothing about the interface is simplified for the agent — it sees what you see and acts how you act.

The deeper point: by using the web as an environment, WoB bridges the gap between simulated benchmarks and real-world tasks. Agents learn from the same rich, semantic content that humans create and interact with daily.

## Why the Web?

Three key benefits make the web an ideal learning platform:

| Benefit | Description |
|---------|-------------|
| **Open-domain** | Unlimited websites provide diverse tasks and real-world semantics |
| **Open-source** | HTML/CSS/JS is inspectable and modifiable |
| **Data collection** | Human demonstrations can be crowdsourced easily |

Unlike robotics, web environments are fully digital — enabling fast iteration and massive scaling.

## Interactive Demo

Explore how a WoB agent perceives the DOM and takes actions to complete web tasks:

*Interactive demo: https://aipedia.org/world-of-bits*

## Benchmark Tasks

WoB introduces three task categories of increasing complexity.

### MiniWoB

100 hand-crafted web tasks with small synthetic pages:

- **click-button** — click a specific button
- **enter-text** — type text into an input field
- **use-slider** — adjust a slider to a target value
- **book-flight** — complete a multi-step booking form

These tasks feature clean reward functions and controlled complexity — the "gym exercises" of web interaction.

### FormWoB

Real flight booking websites (United, Alaska, etc.) packaged as reproducible environments:

- Live HTTP traffic is cached via a man-in-the-middle proxy
- Enables offline training while approximating real web dynamics
- Tests generalization to production websites

### QAWoB

Crowdsourced question-answering tasks on live websites. Queries are built from templates with fillable slots:

$$
\text{Query} = \text{Template}(\text{slot}_1, \text{slot}_2, \ldots)
$$

Examples:

- *"What is the population of **Paris**?"* (Wikipedia)
- *"Find flights from **NYC** to **LA** on **Dec 25**"* (Flight sites)

Workers provide demonstrations of how to answer queries using keyboard and mouse.

## Agent Architecture

The baseline WoB agent uses a CNN-LSTM architecture:

```
Observation → CNN(pixels) + MLP(DOM text) → LSTM → Policy(actions)
```

Key design choices:

- **Multimodal input**: combines visual features with semantic DOM information
- **Recurrent memory**: an LSTM tracks state across multiple interaction steps (see [Understanding LSTMs](https://aipedia.org/understanding-lstms))
- **Policy output**: coordinates $(x, y)$ for mouse, one-hot for keyboard

## Training Approaches

| Method | Description |
|--------|-------------|
| **Behavioral Cloning** | Supervised learning on human demonstrations |
| **REINFORCE** | Policy gradient with sparse task rewards |
| **Guided RL** | Warm-start with BC, then fine-tune with RL |

Behavioral cloning alone achieves reasonable performance but struggles to recover from errors it never saw in demonstrations. RL enables adaptation but requires reward shaping for complex tasks. (For the RL side, see [Policy Gradient](https://aipedia.org/policy-gradient).)

## Performance Gap

Even with demonstrations and RL, significant gaps remain:

| Task Type | Agent Success | Human Success |
|-----------|---------------|---------------|
| Simple clicks | ~80% | 100% |
| Multi-step forms | ~40% | 100% |
| Open-domain QA | ~20% | 100% |

This gap motivated years of continued research on web agents.

## Impact & Legacy

WoB pioneered the study of web-based agents and inspired subsequent benchmarks:

- **MiniWoB++** — extended tasks with improved reward signals
- **WebShop** — e-commerce navigation benchmark
- **WebArena** — realistic web task environment
- **Mind2Web** — large-scale web agent dataset

Modern LLM-based agents (GPT-4V, Gemini) are now evaluated on these benchmarks.

## Common Confusion

- **WoB vs. MiniWoB**: World of Bits is the whole platform; MiniWoB is just its easiest task suite (and the part that survived longest, as MiniWoB++).
- **Pixels-and-DOM vs. text-only agents**: WoB agents act through raw screen coordinates and keystrokes. Later LLM web agents often act on the DOM or text directly — an easier but less general interface.
- **This is 2017-era RL, not LLMs**: the baseline agent is a CNN-LSTM trained with behavioral cloning and REINFORCE. Modern browser agents solve these tasks very differently, but on benchmarks descended from this one.

## Where To Go Next

- Read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) for the framework WoB is built on.
- Read [Policy Gradient](https://aipedia.org/policy-gradient) for the REINFORCE algorithm used to train the baseline agent.
- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the recurrent memory in the agent architecture.
- Read [DQN](https://aipedia.org/dqn) for the other landmark "RL from pixels" line of work, in Atari games.


# BERT: Bidirectional Transformers

> Pre-training deep bidirectional representations for NLP

- Type: Paper
- By: Devlin et al.
- Year: 2018
- Topics: Architecture, Transformers, Deep learning, NLP, Pre training
- Page: https://aipedia.org/bert

## Resources

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://arxiv.org/abs/1810.04805): Paper, Devlin et al., 2018
- [google-research/bert](https://github.com/google-research/bert): Code, Official code and models
- [The Illustrated BERT, ELMo, and co.](https://jalammar.github.io/illustrated-bert/): Article, Jay Alammar
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://arxiv.org/abs/1907.11692): Paper, Liu et al., 2019
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://arxiv.org/abs/1909.11942): Paper, Lan et al., 2019

**BERT** (Bidirectional Encoder Representations from Transformers) is a language model that reads a sentence in both directions at once. Published by Devlin et al. at Google in 2018, it achieved state-of-the-art results on 11 NLP tasks and became one of the most cited AI papers ever.

> If this page feels too fast, read [Transformer](https://aipedia.org/transformer) first. BERT is an **encoder-only** Transformer trained for understanding; its sibling [GPT](https://aipedia.org/gpt) is a **decoder-only** Transformer trained for generation.

## Why Students Should Care

- BERT popularized the **pre-train then fine-tune** recipe that most of modern NLP still follows.
- It shows why **bidirectional context** matters: understanding a word often requires the words after it, not just before.
- BERT-style encoders still power search engines, classifiers, and embedding models today.

## A Quick Example

Fill in the blank:

`The man went to the [BLANK] to buy milk.`

You can guess "store" because you read the whole sentence — including "to buy milk," which comes **after** the blank. A left-to-right model only sees "The man went to the" and has far less to work with. BERT is trained on exactly this kind of fill-in-the-blank task, so every word gets to use context from both sides.

## The Key Insight

Previous language models were either left-to-right (GPT) or used shallow concatenation of left-to-right and right-to-left models (ELMo). BERT's breakthrough: **mask tokens and predict them using both left and right context simultaneously**.

$$
P(w_i | w_1, ..., w_{i-1}, w_{i+1}, ..., w_n)
$$

You do not need to memorize the notation. The important idea is: **predict a hidden word from everything around it**, so every token "sees" the entire sentence when building its representation.

## Pre-training Objectives

BERT is pre-trained on two tasks that need no human labels — the text itself is the supervision.

### 1. Masked Language Modeling (MLM)

Randomly mask 15% of tokens and predict them. The masked tokens are:

- 80% replaced with `[MASK]`
- 10% replaced with a random token
- 10% left unchanged

$$
\mathcal{L}_{MLM} = -\sum_{i \in \text{masked}} \log P(w_i | \mathbf{h}_i)
$$

In plain English: hide some words, make the model guess them, and penalize wrong guesses. The mix of replacements stops the model from only learning about the special `[MASK]` token, which never appears at fine-tuning time.

### 2. Next Sentence Prediction (NSP)

Given sentence A and sentence B, predict whether B actually follows A in the original text:

```
[CLS] The cat sat on the mat [SEP] It was comfortable [SEP]
Label: IsNext
```

This teaches the model relationships **between** sentences, useful for tasks like question answering.

## Architecture

BERT uses the **Transformer encoder** (no decoder), stacked deep:

| Model | Layers | Hidden | Heads | Parameters |
|-------|--------|--------|-------|------------|
| BERT-Base | 12 | 768 | 12 | 110M |
| BERT-Large | 24 | 1024 | 16 | 340M |

## Interactive Demo

Explore how BERT processes tokens bidirectionally and learns masked predictions:

*Interactive demo: https://aipedia.org/bert*

## Input Representation

Before any attention happens, BERT turns each token into a vector by adding three embeddings together:

$$
\text{Input} = \text{Token Emb} + \text{Segment Emb} + \text{Position Emb}
$$

- **Token embeddings**: which word piece this is (WordPiece vocabulary, 30K tokens)
- **Segment embeddings**: whether the token belongs to sentence A or sentence B
- **Position embeddings**: where the token sits in the sequence (learned, not sinusoidal)

## Fine-tuning

BERT popularized the "pre-train then fine-tune" paradigm:

1. **Pre-train** once on massive unlabeled text (BooksCorpus + Wikipedia)
2. **Fine-tune** cheaply on task-specific labeled data

Fine-tuning adds only a simple output layer on top of the pre-trained encoder:

- **Classification**: use the `[CLS]` token's representation
- **Token tagging**: use each token's representation
- **Question answering**: predict start/end span positions

The heavy lifting — learning what language means — happens once during pre-training and transfers to every downstream task.

## Why It Works

1. **Bidirectional context**: every token sees the full sentence
2. **Deep representations**: 12-24 Transformer layers
3. **Transfer learning**: pre-trained knowledge transfers to many tasks
4. **Attention patterns**: the model learns syntactic and semantic relationships

## Historical Impact

BERT sparked the "BERT-ology" era of follow-up models:

- **RoBERTa**: better training recipe (no NSP, more data)
- **ALBERT**: parameter sharing for efficiency
- **DistilBERT**: knowledge distillation (40% smaller, 60% faster)
- **SpanBERT**: span masking for better representations
- **ELECTRA**: replaced-token detection instead of masking

## Common Confusion

- **BERT is an encoder, GPT is a decoder.** BERT reads text in both directions but cannot naturally generate text; GPT generates text but only sees left context.
- **Masked language modeling is not the same as next-token prediction.** MLM fills in blanks anywhere in the sentence; GPT-style models always predict the next token.
- **BERT the model vs. the paradigm.** "BERT" often refers loosely to any encoder-only pre-trained Transformer (RoBERTa, ALBERT, etc.), not just the original 2018 model.

## Where To Go Next

- Read [Transformer](https://aipedia.org/transformer) for the architecture BERT is built on
- Read [GPT](https://aipedia.org/gpt) for the decoder-only, generative alternative
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for the original Transformer paper
- Read [Pre-training](https://aipedia.org/pre-training) for the broader pre-train-then-adapt paradigm
- Read [Word2Vec](https://aipedia.org/word2vec) for the earlier, static word embeddings BERT improved on


# GPT: Generative Pre-Training

> Autoregressive language models that learn to predict the next token

- Type: Paper
- By: Radford et al.
- Year: 2018
- Topics: Architecture, Transformers, Deep learning, NLP, Pre training, Generative
- Page: https://aipedia.org/gpt

## Resources

- [Improving Language Understanding by Generative Pre-Training](https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf): Paper, Radford et al., 2018
- [openai/gpt-2](https://github.com/openai/gpt-2): Code, GPT-2 code and models
- [Let's build GPT: from scratch, in code, spelled out](https://www.youtube.com/watch?v=kCc8FmEb1nY): Video, Andrej Karpathy
- [Language Models are Unsupervised Multitask Learners (GPT-2)](https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf): Paper, Radford et al., 2019
- [Language Models are Few-Shot Learners (GPT-3)](https://arxiv.org/abs/2005.14165): Paper, Brown et al., 2020
- [Training language models to follow instructions with human feedback](https://arxiv.org/abs/2203.02155): Paper, Ouyang et al., 2022 (InstructGPT)

**GPT** (Generative Pre-trained Transformer) is a family of language models built on one deceptively simple task: predict the next token. Starting with GPT-1 (2018) from OpenAI, the series demonstrated that scaling Transformer decoders creates increasingly capable general-purpose models.

> If this page feels too fast, read [Transformer](https://aipedia.org/transformer) first. GPT is a **decoder-only** Transformer trained for generation; its sibling [BERT](https://aipedia.org/bert) is an **encoder-only** Transformer trained for understanding.

## Why Students Should Care

- GPT is the direct ancestor of ChatGPT, Claude, and most modern LLMs — they are all decoder-only next-token predictors.
- The GPT series is the clearest demonstration of the **scaling hypothesis**: same recipe, more parameters and data, qualitatively new abilities.
- Ideas you will meet everywhere — prompting, few-shot learning, foundation models — were established by these papers.

## A Quick Example

Read this and predict the next word:

`The capital of France is`

You said "Paris." To do that reliably across billions of sentences, a model has to absorb grammar, facts, and even reasoning patterns. That is the whole training signal: guess the next token, get corrected, repeat.

## Core Idea: Next Token Prediction

Formally, GPT models the probability of a sequence as a chain of next-token predictions:

$$
P(x_1, x_2, ..., x_n) = \prod_{i=1}^{n} P(x_i | x_1, ..., x_{i-1})
$$

You do not need to memorize the equation. The important idea is: **each token is predicted from everything before it, and nothing after it**. This simple objective — predicting what comes next — turns out to encode rich understanding of language, facts, and reasoning.

## The Architecture

GPT uses the **Transformer decoder** with causal (masked) self-attention. "Causal" means each token can only attend to earlier tokens — the future is hidden:

$$
\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}} + M\right)V
$$

where $M$ is a causal mask preventing attention to future tokens. Without the mask, predicting the next token would be trivial cheating — the answer would be visible.

| Model | Year | Parameters | Context | Training Data |
|-------|------|------------|---------|---------------|
| GPT-1 | 2018 | 117M | 512 | BookCorpus |
| GPT-2 | 2019 | 1.5B | 1024 | WebText (40GB) |
| GPT-3 | 2020 | 175B | 2048 | 570GB filtered |
| GPT-4 | 2023 | ~1.7T* | 8K-128K | Unknown |

*Estimated, not officially disclosed

## Interactive Demo

Explore autoregressive generation and causal attention:

*Interactive demo: https://aipedia.org/gpt*

## GPT-2: The Scaling Revelation

GPT-2 demonstrated **emergent capabilities** from scale — abilities nobody explicitly trained for:

- Zero-shot task performance without fine-tuning
- Coherent long-form text generation
- Basic reasoning and arithmetic
- Translation and summarization (without training for it)

The paper's key insight: "Language models are unsupervised multitask learners." Learning to predict text well means implicitly learning the tasks that text describes.

## GPT-3: In-Context Learning

GPT-3 introduced **few-shot prompting**: show the model a couple of examples inside the prompt, and it picks up the pattern.

```
Translate English to French:
sea otter => loutre de mer
peppermint => menthe poivrée
cheese =>
```

The model learns new tasks from examples in the prompt, **without any gradient updates** — its weights never change. This emerged purely from scale. See [In-Context Learning](https://aipedia.org/in-context-learning) for more.

## Training Objective

Training minimizes the standard language modeling loss — how surprised the model is by each true next token:

$$
\mathcal{L} = -\sum_{i=1}^{n} \log P(x_i | x_1, ..., x_{i-1}; \theta)
$$

GPT-3 additionally uses:

- Sparse attention patterns for efficiency
- Model parallelism across many GPUs
- Careful data deduplication

## Why Decoder-Only?

BERT uses encoders (bidirectional), GPT uses decoders (causal). Why choose one or the other?

| Aspect | Encoder (BERT) | Decoder (GPT) |
|--------|---------------|---------------|
| Training | Masked LM | Next token |
| Generation | Cannot generate | Natural generation |
| Understanding | Both directions | Left context only |
| Use case | Classification, QA | Generation, chat |

Modern LLMs (GPT-4, Claude) use decoder-only architectures because generation is the primary interface.

## Scaling Laws

GPT-3 revealed that performance improves **predictably** with size:

$$
L(N) \approx \left(\frac{N_c}{N}\right)^{\alpha_N}
$$

Loss decreases as a power law with model size $N$, data size $D$, and compute $C$. The takeaway: you can forecast how good a bigger model will be before you train it. See [Scaling Laws](https://aipedia.org/scaling-laws) for the full story.

## From GPT to ChatGPT

A raw language model completes text; it does not naturally follow instructions. The path to conversational AI:

1. **GPT-3**: raw language model
2. **InstructGPT**: fine-tuned to follow instructions (RLHF)
3. **ChatGPT**: optimized for dialogue

RLHF (Reinforcement Learning from Human Feedback) aligns the model with human preferences — see [RLHF](https://aipedia.org/rlhf).

## Historical Impact

GPT established:

- **Scaling hypothesis**: bigger models → better capabilities
- **Emergent abilities**: capabilities appearing at scale
- **Prompt engineering**: programming via natural language
- **Foundation models**: one model, many tasks

## Common Confusion

- **GPT is the model family; ChatGPT is a product** built on GPT models plus instruction tuning and RLHF.
- **Decoder-only does not mean worse at understanding.** GPT models understand text too — they just build that understanding from left context only.
- **In-context learning is not fine-tuning.** Few-shot prompting changes no weights; fine-tuning does.

## Where To Go Next

- Read [Transformer](https://aipedia.org/transformer) for the underlying architecture
- Read [BERT](https://aipedia.org/bert) for the encoder-only alternative
- Read [Scaling Laws](https://aipedia.org/scaling-laws) for why bigger keeps getting better
- Read [In-Context Learning](https://aipedia.org/in-context-learning) for how prompting works as learning
- Read [RLHF](https://aipedia.org/rlhf) for how raw GPT became a helpful assistant


# Relational Recurrent Neural Networks

> RNNs with relational memory that enables reasoning across time

- Type: Paper
- By: Santoro et al.
- Year: 2018
- Topics: Deep learning, RNNs, Memory, Attention
- Page: https://aipedia.org/relational-rnn

## Resources

- [Relational Recurrent Neural Networks](https://arxiv.org/abs/1806.01822): Paper, Santoro et al., 2018

**Relational Recurrent Neural Networks** combine the step-by-step processing of RNNs with the relational reasoning of attention. Instead of one big memory vector, the model keeps several memory *slots* — and the slots can talk to each other using attention.

> Prerequisites: [Understanding LSTMs](https://aipedia.org/understanding-lstms) for gated memory, and the attention mechanism from [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need). This page combines the two.

## Why Students Should Care

- It is a bridge architecture: half LSTM, half [Transformer](https://aipedia.org/transformer). Seeing both in one model clarifies what each ingredient contributes.
- It shows *why* attention helps reasoning: some tasks need stored facts to be **compared**, not just stored.
- The multi-slot memory idea connects to [Neural Turing Machines](https://aipedia.org/neural-turing-machines) and to how we think about memory in agents today.

## The Motivating Problem

Suppose a model reads: "Ball A is 3m away. Ball B is 7m away. Ball C is 5m away. Which ball is second farthest?"

A standard LSTM squeezes everything into one fixed memory cell. It can *store* the three distances (roughly), but answering requires **comparing stored facts against each other** — an operation the LSTM cell simply does not have. Complex reasoning needs:

- Multiple pieces of information stored simultaneously
- Interactions *between* stored memories
- Dynamic retrieval based on relationships

## Relational Memory Core (RMC)

The fix: keep a set of memory slots $M = [m_1, m_2, ..., m_N]$, and at every timestep let the slots update each other using attention:

$$
M^{t+1} = \text{MHDPA}(M^t) + \text{MLP}(\text{MHDPA}(M^t))
$$

where MHDPA is Multi-Head Dot Product Attention — the same attention used in Transformers.

You do not need to memorize the equation. The important idea is: **each memory slot looks at all the other slots and updates itself based on what it finds** — exactly like tokens attending to each other in a Transformer, but applied to memories instead.

## Key Innovation

Memories attend to *each other*, not just to inputs:

$$
A = \text{softmax}\left(\frac{M W_Q (M W_K)^T}{\sqrt{d_k}}\right) M W_V
$$

This is standard query-key-value attention where the queries, keys, and values all come from the memory matrix itself. It is what lets the model compare "ball A's distance" against "ball B's distance" internally.

## Interactive Demo

Watch memory slots interact via attention:

*Interactive demo: https://aipedia.org/relational-rnn*

## Gating Mechanism

Attention alone would happily overwrite everything each step. Like LSTMs, the RMC uses gates to blend the new attended memory with the old one:

$$
\tilde{M} = \sigma(W_g[\tilde{A}; M]) \odot \tilde{A} + (1 - \sigma(W_g[\tilde{A}; M])) \odot M
$$

The takeaway: a learned gate decides, per element, how much of the freshly-computed memory to accept and how much of the old memory to keep — preventing catastrophic forgetting of important facts.

## Architecture

```
Input → Linear projection → Concatenate with memories
     → Multi-head self-attention over all slots
     → MLP (residual)
     → Gated update
     → Output from attended memories
```

## Results

### Language Modeling (WikiText-103)

| Model | Perplexity |
|-------|------------|
| LSTM | 48.7 |
| Transformer | 44.1 |
| **Relational Memory** | **31.6** |

### Program Evaluation (Nth Farthest)

Task: given N objects, find the Nth farthest from a query — a pure relational-comparison task.

| Model | Accuracy |
|-------|----------|
| LSTM | 17% |
| DNC | 37% |
| **RMC** | **91%** |

The gap on Nth Farthest is the headline: when the task is *all* comparison, memory interaction is not a nice-to-have — it is the difference between failing and solving it.

## Why It Works

1. **Multiple memories**: can store several facts side by side
2. **Memory interaction**: facts can "talk" to each other via attention
3. **Attention routing**: retrieval is dynamic, based on relevance
4. **Temporal integration**: still processes sequences step by step like an RNN

## Connection to Transformers

RMC uses key Transformer ingredients:

- Multi-head attention
- Residual connections
- Layer normalization

The main difference: RMC processes sequences recurrently (one step at a time, with a fixed number of memory slots), while Transformers process all positions in parallel.

## Common Confusion

- **Relational RNN vs. [Relation Networks](https://aipedia.org/relational-reasoning)**: same lab, related idea, different mechanism. Relation Networks compare all pairs of *objects in a single input*; the RMC lets *memory slots* interact *across time*.
- **Not a Transformer with extra steps**: the RMC is still recurrent — it has a bounded memory that persists across timesteps, whereas a Transformer re-reads the whole sequence.
- **Slots vs. cell state**: an LSTM has one memory vector updated by gates; the RMC has $N$ memory vectors updated by attention *and* gates.

## Where To Go Next

- Read [Relational Reasoning](https://aipedia.org/relational-reasoning) for the pairwise-comparison idea in its simplest form.
- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the gating machinery the RMC borrows.
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for the attention machinery it borrows.
- Read [Neural Turing Machines](https://aipedia.org/neural-turing-machines) for an earlier take on slot-based external memory.
- Read [Transformer](https://aipedia.org/transformer) for the architecture that ultimately won by dropping recurrence entirely.


# GPipe: Easy Scaling with Micro-Batch Pipeline Parallelism

> Training giant neural networks by pipelining micro-batches across devices

- Type: Paper
- By: Huang et al.
- Year: 2019
- Topics: Deep learning, Distributed, Training, Parallelism
- Page: https://aipedia.org/gpipe

## Resources

- [GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism](https://arxiv.org/abs/1811.06965): Paper, Huang et al., NeurIPS 2019

**GPipe** is a technique for training giant neural networks that don't fit on a single accelerator. It splits the model into consecutive stages across devices, then keeps every device busy by streaming small "micro-batches" through the pipeline like an assembly line.

> This page assumes you know the basic training loop (forward pass, backward pass, weight update). If not, read [Backpropagation](https://aipedia.org/backpropagation) first.

## Why Students Should Care

- Every large language model today is trained across many devices; pipeline parallelism is one of the core strategies, and GPipe is its classic formulation.
- The efficiency analysis here (pipeline "bubbles") is a clean, worked example of the kind of systems reasoning that dominates large-scale ML.
- The memory trick GPipe popularized — activation recomputation — shows up everywhere in modern training.

## The Problem

Some models are simply too large for one accelerator's memory. The obvious fix is to put different layers on different devices — layers 1-10 on device 1, layers 11-20 on device 2, and so on. But think about what happens with a single batch: device 2 cannot start until device 1 finishes, and device 1 then sits idle while everyone else works. At any moment, only one device is busy:

$$
\text{Utilization} = \frac{1}{K}
$$

where $K$ is the number of devices. With 8 devices, you pay for 8 accelerators and effectively use 1.

## The GPipe Solution

GPipe fixes this like a factory assembly line: instead of pushing one big batch through, push many small pieces so every station works at once.

1. **Partition** the model into $K$ consecutive stages across $K$ devices
2. **Split** each mini-batch into $M$ micro-batches
3. **Pipeline** micro-batches through the stages

While device 2 processes micro-batch 1, device 1 is already processing micro-batch 2.

## Pipeline Schedule

Forward passes flow left-to-right, backward passes right-to-left:

$$
\text{Time} = (K - 1) + M + (K - 1)
$$

The $(K-1)$ terms are "pipeline bubbles" — the ramp-up at the start (later stages waiting for their first micro-batch) and the drain at the end (earlier stages having nothing left to do).

## Interactive Demo

Watch micro-batches flow through a 4-device pipeline:

*Interactive demo: https://aipedia.org/gpipe*

## Efficiency Analysis

How much time is wasted in bubbles? The bubble fraction is:

$$
\text{Bubble} = \frac{2(K-1)}{2(K-1) + 2M} = \frac{K-1}{K-1+M}
$$

You do not need to memorize the formula. The important idea is: **the more micro-batches you push through relative to the number of stages, the smaller the fraction of time lost to ramp-up and drain.** With $M \gg K$, bubbles become negligible. GPipe recommends $M \geq 4K$.

## Memory Optimization

More micro-batches in flight would normally mean storing more activations for the backward pass. GPipe avoids this with **activation recomputation** (also called gradient checkpointing):

- Forward: Only store activations at partition boundaries
- Backward: Recompute intermediate activations as needed

This trades extra compute for less memory, enabling larger models.

## Synchronous Training

A worry you might have: does all this pipelining change what the model learns? No. Despite pipelining, GPipe maintains synchronous SGD semantics:

$$
\theta_{t+1} = \theta_t - \eta \cdot \frac{1}{M}\sum_{m=1}^{M} \nabla_\theta \mathcal{L}_m
$$

Gradients are accumulated across micro-batches before the update — mathematically the same update you would get from the full mini-batch on one giant device.

## Results

| Task | Model Size | Devices | Speedup |
|------|-----------|---------|---------|
| ImageNet | 557M params | 8 TPUs | 6.3× |
| Translation | 6B params | 2048 TPUs | Near-linear |

GPipe achieved 84.4% ImageNet accuracy with a 557M parameter AmoebaNet.

## Comparison with Data Parallelism

Pipeline parallelism is not the only way to use many devices. **Data parallelism** copies the full model to every device and splits the *data* instead:

| Aspect | Data Parallel | GPipe |
|--------|--------------|-------|
| Memory per device | Full model | 1/K model |
| Communication | Gradient sync | Activation transfer |
| Batch size | Scales with K | Independent of K |

GPipe is complementary — real large-scale training systems combine both approaches.

## Common Confusion

- **Micro-batch vs. mini-batch**: the mini-batch is the unit of one weight update; micro-batches are the smaller slices it is cut into purely for pipelining. Weights update once per mini-batch, not per micro-batch.
- **Pipeline parallelism vs. data parallelism**: pipeline parallelism splits the *model* across devices; data parallelism splits the *data* and replicates the model.
- **Pipelining does not change the math.** GPipe computes exactly the same gradients as ordinary synchronous training — it only changes the schedule.
- **Activation recomputation is not an approximation** either; it recomputes exact values, spending compute to save memory.

## Where To Go Next

- Read [Backpropagation](https://aipedia.org/backpropagation) to understand the forward/backward structure the pipeline schedules.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) for why anyone wants models too big for one device in the first place.
- Read [Transformer](https://aipedia.org/transformer) for the architecture that dominates large-scale distributed training.
- Read [Adam](https://aipedia.org/adam) for the optimizer side of large-model training.


# NODE (Neural Oblivious Decision Ensembles)

> Differentiable decision trees and oblivious ensembles for tabular learning

- Type: Paper
- By: Popov et al.
- Year: 2019
- Topics: Deep learning, Trees, Tabular data, Differentiable
- Page: https://aipedia.org/node

## Resources

- [Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data](https://arxiv.org/abs/1909.06312): Paper, Popov et al., 2019
- [Qwicen/node](https://github.com/Qwicen/node): Code, Official code
- [Distilling a Neural Network Into a Soft Decision Tree](https://arxiv.org/abs/1711.09784): Paper, Frosst & Hinton, 2017
- [Deep Neural Decision Forests](https://openaccess.thecvf.com/content_iccv_2015/html/Kontschieder_Deep_Neural_Decision_ICCV_2015_paper.html): Paper, Kontschieder et al., 2015

**NODE** (Popov et al., 2019) introduces *differentiable decision trees* built from **oblivious trees**, enabling end-to-end gradient-based learning on tabular data. In short: it takes the model family that dominates spreadsheet-style data — decision trees — and rebuilds it so it can be trained like a neural network.

> If you have not seen gradient-boosted trees, read [GBDT](https://aipedia.org/gbdt) first — NODE is best understood as a response to it. [Backpropagation](https://aipedia.org/backpropagation) is the training machinery NODE unlocks.

## Why Students Should Care

- Tabular data (rows and columns, like a database table) is the most common data type in industry, and tree ensembles like [GBDT](https://aipedia.org/gbdt) have long dominated it — deep learning has struggled here.
- NODE shows a general, widely reusable trick: **replace a hard, discrete decision with a soft, probabilistic one** so gradients can flow through it.
- It bridges two worlds: the inductive bias of trees and the end-to-end trainability of neural networks.

## The Problem: Trees Don't Have Gradients

A classic decision tree routes each example with hard yes/no questions: `if x < t`, go left, otherwise go right. That step function is flat almost everywhere, so its gradient is zero — backpropagation has nothing to work with. This is why classic trees are grown greedily, split by split, instead of trained end to end.

## Key Insight

NODE replaces the hard split with soft routing:

$$
P(\text{left}) = \sigma\left(\frac{t - x}{\tau}\right)
$$

Instead of a yes/no answer, the example goes left *with some probability* that changes smoothly as $x$ crosses the threshold $t$ — and smooth means differentiable. The temperature $\tau$ controls smoothness: low values approximate classic trees; higher values yield soft mixtures of paths.

The takeaway: **soften the split, and a decision tree becomes a neural network layer you can train with gradients**.

## Oblivious Decision Trees

An **oblivious tree** uses the **same feature and threshold at every depth**. Each level applies an identical split, producing a symmetric structure. ("Oblivious" is a historical term for this constraint — the split at a given level ignores which branch you came from.)

Benefits:

- Fewer parameters
- Efficient vectorization on GPUs
- Strong inductive bias for tabular data

NODE ensembles stack many such trees, each producing a weighted leaf prediction.

## entmax vs softmax

Which feature should a split look at? Rather than hard-picking one, NODE learns a weighting over features. Instead of softmax, NODE can use **entmax**, which yields sparse probabilities — most features get weight exactly zero:

$$
\mathrm{entmax}_\alpha(z) = \arg\max_p \; p^\top z + H_\alpha(p)
$$

You do not need to memorize this. The important idea is: for $\alpha = 1.5$, entmax interpolates between softmax (dense — every feature gets some weight) and argmax (hard — one feature gets everything), improving interpretability and stability.

## Interactive Visualization

*Interactive demo: https://aipedia.org/node*

## Why Differentiable Trees?

- Train trees with **backpropagation** instead of greedy split-by-split construction
- Combine tree structure with neural representations in one model
- Smooth optimization landscape vs greedy splits
- Naturally ensemble-friendly

## Comparison to Other Tabular Models

- **[GBDT](https://aipedia.org/gbdt)**: Strong but non-differentiable, trained greedily
- **TabNet**: Attention-based, less interpretable splits
- **MLPs**: Weak inductive bias for tabular data
- **NODE**: Tree bias + gradient learning

## Common Confusion

- **NODE here means Neural Oblivious Decision Ensembles** — not Node.js (the JavaScript runtime) and not Neural ODEs (neural ordinary differential equations), which share the abbreviation.
- **"Oblivious" does not mean the tree ignores the data** — it means every node at the same depth uses the same feature and threshold.
- **Soft routing is not the same as an ensemble average**: a single soft tree sends each example down *all* paths with different probabilities; an ensemble averages many separate trees. NODE does both.
- **NODE vs. [GBDT](https://aipedia.org/gbdt)**: both are tree ensembles for tabular data, but GBDT builds trees greedily one at a time, while NODE trains all its trees jointly with gradients.

## Where To Go Next

- Read [GBDT](https://aipedia.org/gbdt) for the classic gradient-boosted tree approach NODE competes with.
- Read [Backpropagation](https://aipedia.org/backpropagation) for the gradient machinery that soft splits make usable.
- Read [Adam](https://aipedia.org/adam) for the kind of optimizer typically used to train models like NODE end to end.


# Scaling Laws for Neural Language Models

> Why bigger models, more data, and more compute lead to predictable gains

- Type: Paper
- By: Kaplan et al.
- Year: 2020
- Topics: Deep learning, NLP, Scaling, Transformers
- Page: https://aipedia.org/scaling-laws

## Resources

- [Scaling Laws for Neural Language Models](https://arxiv.org/abs/2001.08361): Paper, Kaplan et al., 2020
- [Training Compute-Optimal Large Language Models](https://arxiv.org/abs/2203.15556): Paper, Hoffmann et al., 2022 (Chinchilla)

**Scaling laws** describe a practical pattern in modern ML: when you increase model size, training data, and compute in a sensible way, performance often improves smoothly and predictably rather than randomly.

> Read [Pre-training](https://aipedia.org/pre-training) and [GPT](https://aipedia.org/gpt) first if you want the surrounding context. This page is about the empirical rule behind "bigger models keep getting better."

## A Simple Mental Model

Suppose you have a fixed training budget. You could spend it on:

- a larger model
- more data
- more training steps

Scaling-law papers ask: **if I spend twice as much compute, how much better should I expect the model to get?**

Their answer was surprising: the curve is often smooth enough that you can predict it before running the full experiment.

## The Core Discovery

The original paper found that cross-entropy loss followed power laws with model size $N$, data size $D$, and compute $C$:

$$
L(N) = \left(\frac{N_c}{N}\right)^{\alpha_N}, \quad \alpha_N \approx 0.076
$$

$$
L(D) = \left(\frac{D_c}{D}\right)^{\alpha_D}, \quad \alpha_D \approx 0.095
$$

$$
L(C) = \left(\frac{C_c}{C}\right)^{\alpha_C}, \quad \alpha_C \approx 0.050
$$

The exact exponents are less important than the lesson: **performance improves in a regular way as scale increases**.

## Why This Was a Big Deal

Before scaling laws, training larger models involved much more guesswork.

After scaling laws, teams could:

- estimate expected gains before full runs
- decide whether more compute was worth the cost
- plan better trade-offs between parameters and data

## Interactive Visualization

Explore how loss decreases with scale:

*Interactive demo: https://aipedia.org/scaling-laws*

## Optimal Allocation

Given a compute budget $C$, the original paper suggested:

$$
N^* \propto C^{0.73}
$$

$$
D^* \propto C^{0.27}
$$

That meant: under the original estimate, you should spend more of the extra budget on **model size** than on **data**.

## A Helpful Interpretation

If a student asks, "Does this mean giant models always win?" the better answer is:

- larger models usually help
- but only when you also scale data and compute sensibly
- poor allocation can waste the budget

Scaling laws are about **how to scale well**, not just scaling blindly.

## The Chinchilla Update

Later work, especially Chinchilla-style analysis, argued that the original paper under-trained large models relative to the amount of available data.

That updated view suggests a more balanced rule:

$$
N^* \propto C^{0.5}, \quad D^* \propto C^{0.5}
$$

So a major lesson for students is that scaling laws are not one fixed formula forever. They are an evolving empirical picture.

## Practical Implications

| Question | Scaling-law answer |
|----------|--------------------|
| Should we expect smooth gains from more scale? | Often yes |
| Can we predict those gains ahead of time? | Roughly yes |
| Is bigger always enough by itself? | No |
| Does data allocation matter? | A lot |

## What To Remember

- Scaling laws made large-model training more predictable
- The important variables are model size, data, and compute
- Later work refined the original story, especially around data-optimal training


# Vision Transformer (ViT)

> Applying Transformers directly to image patches for visual recognition

- Type: Paper
- By: Dosovitskiy et al.
- Year: 2020
- Topics: Deep learning, Vision, Transformers, Attention
- Page: https://aipedia.org/vision-transformer

## Resources

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://arxiv.org/abs/2010.11929): Paper, Dosovitskiy et al., 2020
- [google-research/vision_transformer](https://github.com/google-research/vision_transformer): Code, Official code and models

The **Vision Transformer (ViT)** applies a plain Transformer to images by treating an image as a sequence of small patches — like words in a sentence. It demonstrated that pure Transformers can match or exceed CNNs on image classification, especially when pre-trained on large datasets.

> If this page feels too fast, read [Transformer](https://aipedia.org/transformer) first — ViT reuses the standard Transformer encoder almost unchanged. For the CNN approach it challenged, see [ResNet](https://aipedia.org/resnet).

## Why Students Should Care

- ViT showed that **one architecture can serve both language and vision**, ending the assumption that images require convolutions.
- It is a striking example of the **scale-vs-inductive-bias trade-off**: with enough data, a general architecture beats a specialized one.
- The patch-embedding idea underpins modern multimodal models — the same trick lets images enter an LLM.

## A Quick Example

A Transformer eats sequences of tokens. A sentence naturally splits into word tokens — but how do you tokenize a picture? ViT's answer: chop the image into a grid of small squares (say 16×16 pixels each), flatten each square into a vector, and treat those vectors as the "words" of the image. A 224×224 image becomes a sequence of 196 patch tokens, and from there the Transformer does not care that the data was ever an image.

## Core Idea: Images as Sequences

Instead of convolutions, ViT treats an image as a sequence of patches:

1. Split the image into fixed-size patches (e.g., 16×16)
2. Flatten each patch into a vector
3. Project through a linear embedding
4. Add positional embeddings
5. Process with a standard Transformer encoder

$$
z_0 = [x_{class}; x_1^p E; x_2^p E; \ldots; x_N^p E] + E_{pos}
$$

where $E$ is the patch embedding projection and $E_{pos}$ are learnable position embeddings. In plain English: the input is a class token plus one embedded vector per patch, with position information added so the model knows where each patch came from.

## Patch Embedding

How many patches does an image produce? For an image of size $H \times W$ with patch size $P$:

$$
N = \frac{HW}{P^2}
$$

Each patch $x_p \in \mathbb{R}^{P^2 \cdot C}$ (all its pixel values, across $C$ color channels) is projected to dimension $D$ by a single learned matrix:

$$
x_p E \in \mathbb{R}^D, \quad E \in \mathbb{R}^{(P^2 \cdot C) \times D}
$$

The takeaway: turning a patch into a token is just one linear layer — no convolutions needed.

## The `[CLS]` Token

Borrowed from [BERT](https://aipedia.org/bert): a learnable embedding $x_{class}$ is prepended to the sequence. It carries no image content itself, but through self-attention it gathers information from every patch. After processing through $L$ Transformer layers, its output serves as the summary representation of the whole image:

$$
y = \text{LN}(z_L^0)
$$

This is passed to an MLP head for classification.

## Architecture

ViT is a standard Transformer encoder with:

- Multi-head self-attention
- MLP blocks (GELU activation)
- Layer normalization (pre-norm variant)
- Residual connections

| Model | Layers | Hidden | MLP | Heads | Params |
|-------|--------|--------|-----|-------|--------|
| ViT-B/16 | 12 | 768 | 3072 | 12 | 86M |
| ViT-L/16 | 24 | 1024 | 4096 | 16 | 307M |
| ViT-H/14 | 32 | 1280 | 5120 | 16 | 632M |

(The number after the slash is the patch size — ViT-B/16 uses 16×16 patches.)

## Interactive Visualization

See how ViT splits images into patches and applies self-attention:

*Interactive demo: https://aipedia.org/vision-transformer*

## Key Insight: Scale Matters

CNNs bake in useful assumptions about images (nearby pixels relate; patterns repeat across locations). These **inductive biases** help when data is scarce. ViT has almost none of them — so it underperforms CNNs when trained on small datasets. But with large-scale pre-training (ImageNet-21k, JFT-300M), it learns those regularities from data and excels:

> "When pre-trained on large amounts of data, the Transformer architecture can match or exceed state-of-the-art CNNs."

The takeaway: **built-in assumptions win with little data; learned assumptions win with lots of data**.

## Impact

ViT unified vision and language under the same architecture, enabling:

- [CLIP](https://aipedia.org/clip) (vision-language)
- DALL-E (image generation)
- Multimodal models (GPT-4V, Gemini)

The patch embedding + Transformer paradigm now dominates computer vision.

## Common Confusion

- **ViT is an encoder, not a generator.** The original ViT classifies images; image *generation* models like DALL-E build on related ideas but are different systems.
- **Patches are not convolutions.** The patch embedding is a single linear projection applied to non-overlapping squares — there is no sliding filter or pooling hierarchy.
- **"Transformers beat CNNs" comes with a caveat.** The result holds under large-scale pre-training; on small datasets alone, CNNs' inductive biases still help.

## Where To Go Next

- Read [Transformer](https://aipedia.org/transformer) for the architecture ViT borrows wholesale
- Read [BERT](https://aipedia.org/bert) for the origin of the `[CLS]` token and encoder-style pre-training
- Read [ResNet](https://aipedia.org/resnet) and [AlexNet](https://aipedia.org/alexnet) for the CNN lineage ViT challenged
- Read [CLIP](https://aipedia.org/clip) for vision-language models built on ViT encoders


# CLIP: Contrastive Language-Image Pre-training

> Learning visual concepts from natural language supervision

- Type: Paper
- By: Radford et al.
- Year: 2021
- Topics: Deep learning, Multimodal, Vision, NLP, Foundation models
- Page: https://aipedia.org/clip

## Resources

- [Learning Transferable Visual Models From Natural Language Supervision](https://arxiv.org/abs/2103.00020): Paper, Radford et al., 2021
- [openai/CLIP](https://github.com/openai/CLIP): Code, Official code and models

**CLIP (Contrastive Language-Image Pre-training)** learns to connect images and text by training on 400 million image-text pairs from the internet. Instead of teaching a model a fixed list of categories, CLIP teaches it to answer one question — *does this caption describe this image?* — and that simple objective produces remarkably flexible visual representations.

> This page assumes you know what an encoder is. If not, read [Transformer](https://aipedia.org/transformer) and [Vision Transformer](https://aipedia.org/vision-transformer) first.

## Why Students Should Care

- CLIP is the bridge between **vision and language** — the recipe behind image search, open-vocabulary detection, and the visual side of many multimodal LLMs.
- It popularized **zero-shot classification**: classifying images from datasets the model was never trained on, just by describing the classes in words.
- Its text embeddings guide image generators like DALL-E and Stable Diffusion (see [Latent Diffusion](https://aipedia.org/latent-diffusion)).

## A Quick Example

Show CLIP a photo and two captions: "a photo of a dog" and "a photo of a cat". CLIP embeds the image and both captions into the same vector space and checks which caption's vector points in the most similar direction to the image's vector. Whichever caption matches best wins. That is the entire mechanism — everything below is about how those embeddings are learned.

## Core Idea: Learn from Captions

Instead of predicting fixed categories, CLIP learns to match images with their natural language descriptions. The match score is cosine similarity between the two embeddings:

$$
\text{similarity}(I, T) = \frac{f_I(I) \cdot f_T(T)}{\|f_I(I)\| \cdot \|f_T(T)\|}
$$

where $f_I$ is an image encoder (ViT or ResNet) and $f_T$ is a text encoder (Transformer).

In plain English: **two encoders map images and captions into a shared space, where matching pairs sit close together**.

## Contrastive Learning

How do you train those encoders? Take a batch of $N$ image-text pairs. For each image, its own caption is the "right answer" and the other $N-1$ captions are wrong answers — and vice versa for each caption. CLIP maximizes similarity for correct pairs while minimizing it for incorrect ones:

$$
\mathcal{L} = -\frac{1}{N} \sum_{i=1}^{N} \left[ \log \frac{\exp(s_{ii}/\tau)}{\sum_{j=1}^{N} \exp(s_{ij}/\tau)} + \log \frac{\exp(s_{ii}/\tau)}{\sum_{j=1}^{N} \exp(s_{ji}/\tau)} \right]
$$

where $s_{ij} = f_I(I_i) \cdot f_T(T_j)$ and $\tau$ is a learned temperature.

You do not need to memorize the loss. The important idea is: **every batch is a matching game — pull true pairs together, push mismatched pairs apart**.

## Zero-Shot Classification

Because CLIP understands captions, you can build a classifier for a dataset it has never seen — with no extra training:

1. Create text prompts: "a photo of a \{class\}"
2. Encode all prompts with the text encoder
3. Encode the image with the image encoder
4. Predict the class with the highest image-text similarity

$$
p(y|x) = \frac{\exp(f_I(x) \cdot f_T(\text{prompt}_y) / \tau)}{\sum_{c} \exp(f_I(x) \cdot f_T(\text{prompt}_c) / \tau)}
$$

In other words: **the class names themselves become the classifier**.

## Interactive Visualization

Explore how CLIP matches images to text descriptions:

*Interactive demo: https://aipedia.org/clip*

## Prompt Engineering

Because the classifier is built from text, *how you phrase* the text matters. Classification accuracy depends on the prompt:

| Prompt Template | ImageNet Acc |
|----------------|--------------|
| "\{class\}" | 63.5% |
| "a photo of a \{class\}" | 68.3% |
| "a good photo of a \{class\}" | 69.1% |
| Ensemble of 80 templates | 76.2% |

A bare class name underperforms because CLIP's training captions were full sentences, not single words.

## Why CLIP Works

1. **Scale**: 400M image-text pairs provide diverse supervision
2. **Natural language**: captures nuanced visual concepts that fixed label sets cannot
3. **Contrastive learning**: makes efficient use of every batch — each pair supplies many negative examples
4. **Zero-shot transfer**: no task-specific training needed

## Applications

CLIP powers:

- **Image search**: find images matching text queries
- **DALL-E / Stable Diffusion**: guide image generation
- **Open-vocabulary detection**: detect objects by name
- **Multimodal models**: visual understanding in LLMs

## Limitations

- Struggles with fine-grained recognition
- Inherits biases from internet data
- The text encoder limits complex reasoning
- Counting and spatial relationships remain challenging

## Common Confusion

- **CLIP does not generate images.** It scores image-text similarity. Generators like DALL-E and Stable Diffusion *use* CLIP-style embeddings for guidance, but the generation happens elsewhere — see [Diffusion Models](https://aipedia.org/diffusion-models).
- **"Zero-shot" here means no training on the target dataset** — CLIP still saw 400M image-text pairs during pre-training. It is zero-shot with respect to the task, not to data in general.
- **CLIP is a training method plus a pair of encoders, not one specific network.** The image encoder can be a [Vision Transformer](https://aipedia.org/vision-transformer) or a [ResNet](https://aipedia.org/resnet); the recipe is the same.

## Where To Go Next

- Read [Vision Transformer](https://aipedia.org/vision-transformer) for CLIP's strongest image encoder
- Read [Transformer](https://aipedia.org/transformer) for the architecture behind the text encoder
- Read [Pre-training](https://aipedia.org/pre-training) for the broader paradigm CLIP belongs to
- Read [Latent Diffusion](https://aipedia.org/latent-diffusion) to see text embeddings steering image generation


# Latent Diffusion Models

> High-resolution image generation by diffusing in learned latent spaces

- Type: Paper
- By: Rombach et al.
- Year: 2021
- Topics: Deep learning, Generative, Vision, Diffusion
- Page: https://aipedia.org/latent-diffusion

## Resources

- [High-Resolution Image Synthesis with Latent Diffusion Models](https://arxiv.org/abs/2112.10752): Paper, Rombach et al., 2021
- [CompVis/latent-diffusion](https://github.com/CompVis/latent-diffusion): Code, Official code
- [CompVis/stable-diffusion](https://github.com/CompVis/stable-diffusion): Code, Stable Diffusion v1
- [The Illustrated Stable Diffusion](https://jalammar.github.io/illustrated-stable-diffusion/): Article, Jay Alammar

**Latent Diffusion Models (LDMs)** make high-resolution image generation practical by running the diffusion process in a compressed latent space rather than pixel space. This is the architecture behind Stable Diffusion.

> Read [Diffusion Models](https://aipedia.org/diffusion-models) first — this page assumes you know the forward/reverse noising process. The [VAE](https://aipedia.org/vae) page explains the autoencoder used for compression here.

## Why Students Should Care

- This is the architecture of **Stable Diffusion**, one of the most widely used generative models ever released.
- It demonstrates a general and reusable pattern: **compress first, then model** — do the expensive learning in a small learned space instead of raw data space.
- The efficiency gains are what moved image generation from datacenter-only to consumer GPUs.

## The Problem with Pixel-Space Diffusion

Diffusing a 512×512×3 image requires processing 786,432 dimensions per step. For thousands of denoising steps, this is extremely expensive. Worse, most of that effort is wasted: the majority of pixel-level detail is imperceptible texture, not the content of the image.

## The Solution: Compress First

The idea: let a small autoencoder handle the perceptual detail, and let diffusion handle only the compressed "essence" of the image. LDMs use a two-stage approach:

1. **Encode**: Compress images to a smaller latent space
2. **Diffuse**: Run diffusion in latent space
3. **Decode**: Reconstruct to pixel space

$$
z = \mathcal{E}(x), \quad x' = \mathcal{D}(\hat{z})
$$

where $\mathcal{E}$ is the encoder, $\mathcal{D}$ is the decoder, and $\hat{z}$ is the denoised latent.

## The Autoencoder

The compressor is typically a **VQ-VAE** or **KL-VAE** trained separately, before any diffusion happens:

$$
\mathcal{L}_{AE} = \|x - \mathcal{D}(\mathcal{E}(x))\|^2 + \lambda \cdot \text{Reg}(\mathcal{E}(x))
$$

In plain English: reconstruct the image well (first term), while keeping the latent space well-behaved (second term). The latent space is typically 8× or 4× smaller per dimension (64× or 16× in total pixels).

## Diffusion in Latent Space

Once the autoencoder is trained and frozen, diffusion proceeds exactly as usual — same noising process, same noise-prediction loss — just on latents instead of pixels:

$$
\mathcal{L}_{LDM} = \mathbb{E}_{z, \epsilon, t}\left[\|\epsilon - \epsilon_\theta(z_t, t, c)\|^2\right]
$$

where $c$ is the conditioning (text, class, etc.). Nothing about diffusion itself changes; only the space it operates in.

## Interactive Visualization

See how the latent space compression enables efficient generation:

*Interactive demo: https://aipedia.org/latent-diffusion*

## Conditioning via Cross-Attention

How does the text prompt get into the model? Text conditioning is injected through cross-attention inside the denoising U-Net:

$$
\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d}}\right)V
$$

where:
- $Q$ comes from the latent (image features)
- $K, V$ come from the text encoder (CLIP or T5)

Intuitively, each spatial location of the image latent "looks up" the most relevant words in the prompt at every denoising step. This is the same attention mechanism as in the [Transformer](https://aipedia.org/transformer), used across two modalities.

## Architecture Overview

```
Text → CLIP → Cross-Attention
                    ↓
Noise → U-Net (in latent space) → Denoised Latent
                                        ↓
                                    Decoder → Image
```

## Efficiency Gains

The numbers make the case:

| Metric | Pixel Diffusion | Latent Diffusion |
|--------|-----------------|------------------|
| Dimensions | 512×512×3 | 64×64×4 |
| Total dims | 786,432 | 16,384 |
| Compression | 1× | 48× |
| GPU memory | ~24GB | ~8GB |

## Stable Diffusion Specifics

- **VAE**: KL-regularized autoencoder
- **U-Net**: ~860M parameters
- **Text encoder**: CLIP ViT-L/14 (frozen)
- **Latent size**: 64×64×4 for 512×512 images

## Training Pipeline

1. **Stage 1**: Train VAE on images (reconstruction + regularization)
2. **Stage 2**: Train U-Net on latents with frozen VAE
3. **Optional**: Fine-tune on specific domains

## Key Insight

By separating perceptual compression (autoencoder) from semantic generation (diffusion), LDMs achieve:
- High-quality generation
- Computational efficiency
- Flexible conditioning

## Common Confusion

- **"Latent diffusion" vs. "Stable Diffusion"**: latent diffusion is the general architecture; Stable Diffusion is one specific, famous instance of it.
- **The VAE here is not the generative model.** It is a fixed compressor/decompressor trained in advance; the diffusion U-Net does the actual generation. Compare with a standalone [VAE](https://aipedia.org/vae), where the VAE itself generates.
- **Two different "latents"**: the VAE's latent (a compressed image) and the diffusion process's noisy states are both called latents — in an LDM, diffusion's noisy states *live in* the VAE's latent space.
- **Cross-attention vs. self-attention**: self-attention lets image features attend to each other; cross-attention is what connects image features to the *text prompt*.

## Where To Go Next

- Read [Diffusion Models](https://aipedia.org/diffusion-models) for the denoising process this page builds on.
- Read [VAE](https://aipedia.org/vae) for how the compression stage is trained.
- Read [CLIP](https://aipedia.org/clip) for the frozen text encoder that powers prompting.
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for the attention mechanism behind cross-attention conditioning.


# Mamba: State Space Models

> A sequence model that keeps a running state instead of attending to every token pair

- Type: Paper
- By: Gu & Dao
- Year: 2023
- Topics: Deep learning, Architecture, Sequence modeling, Efficiency
- Page: https://aipedia.org/mamba

## Resources

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://arxiv.org/abs/2312.00752): Paper, Gu & Dao, 2023
- [state-spaces/mamba](https://github.com/state-spaces/mamba): Code, Official code
- [Efficiently Modeling Long Sequences with Structured State Spaces (S4)](https://arxiv.org/abs/2111.00396): Paper, Gu, Goel & Ré, 2021

**Mamba** is a sequence model designed for long contexts. Its selling point is efficiency: instead of comparing every token with every other token like a Transformer, it carries a learned internal state forward through the sequence.

> If you are new to sequence models, start with [Understanding LSTMs](https://aipedia.org/understanding-lstms) and [Transformer](https://aipedia.org/transformer). Mamba is easier to understand if you already know both recurrence and attention.

## The Intuition

Imagine reading a long textbook chapter. A Transformer repeatedly looks back at many earlier words. Mamba tries a different strategy: keep a smart running summary of what matters, then update that summary as each new token arrives.

That makes Mamba feel closer to an RNN in spirit, but with a more expressive update rule and much better engineering for modern hardware.

## Why People Care

Self-attention has quadratic cost in sequence length:

$$
O(n^2 \cdot d)
$$

For very long sequences, that becomes expensive in memory and time. Mamba aims for:

$$
O(n \cdot d)
$$

That difference matters a lot for long documents, audio, DNA, or other very long sequences.

## What a State Space Model Does

A **state space model (SSM)** keeps a hidden state that changes over time. You can think of it as a memory vector that gets updated every time a new token comes in.

In continuous form:

$$
h'(t) = Ah(t) + Bx(t)
$$

$$
y(t) = Ch(t)
$$

You do not need the control-theory background on first read. The useful mental model is:

- **state** = what the model is currently remembering
- **input** = the new token
- **output** = what the model produces from that memory

## From Continuous Time to Tokens

Because text arrives token by token, the model uses a discrete recurrence:

$$
h_t = \bar{A} h_{t-1} + \bar{B} x_t, \quad y_t = C h_t
$$

This is the part that makes Mamba look like a learned memory-update system.

## The Key Innovation: Selectivity

Classic SSMs use fixed dynamics. Mamba makes parts of the update depend on the current token:

$$
B_t = f_B(x_t), \quad C_t = f_C(x_t), \quad \Delta_t = f_\Delta(x_t)
$$

That means the model can decide, based on content, whether to keep information, forget it, or emphasize it. This is why people often describe Mamba as a **selective** state space model.

## Interactive Visualization

Compare Mamba's linear scaling with Transformer's quadratic growth:

*Interactive demo: https://aipedia.org/mamba*

## What a Mamba Block Contains

At a high level, a block has:

1. A projection to expand the representation
2. A short convolution for local mixing
3. The selective state space update
4. A gating interaction
5. A projection back to model size

## When Mamba Helps

Mamba is especially interesting when:

- sequences are very long
- inference cost matters a lot
- recurrence is acceptable if it is much more efficient

## Trade-offs

| Strength | Limitation |
|----------|------------|
| Linear scaling in sequence length | Harder to interpret than plain recurrence |
| Strong long-context efficiency | Smaller ecosystem than Transformers |
| Useful hybrid building block | Attention still wins on some tasks |

## What To Remember

- Mamba is a long-sequence alternative to attention-heavy models
- It keeps a learned running state instead of attending to all pairs of tokens
- Its main advantage is **efficiency at long context lengths**

## Where To Go Next

- Read [Transformer](https://aipedia.org/transformer) for the main comparison point
- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for the recurrence intuition
- Read [Pre-training](https://aipedia.org/pre-training) to see how these models fit into foundation-model pipelines


# Recursive Language Models

> A paradigm where LLMs treat context as an environment and recursively call themselves on sub-problems

- Type: Paper
- By: Zhang, Kraska & Khattab
- Year: 2025
- Topics: Language models, Inference, Long context, Agents
- Page: https://aipedia.org/recursive-language-models

## Resources

- [Recursive Language Models](https://arxiv.org/abs/2512.24601): Paper, Zhang, Kraska & Khattab, 2025
- [alexzhang13/rlm](https://github.com/alexzhang13/rlm): Code, Official implementation
- [Recursive Language Models: the paradigm of 2026](https://www.primeintellect.ai/blog/rlm): Article, Prime Intellect

**Recursive Language Models** (RLMs) are an inference strategy that lets a language model handle inputs far longer than its context window. Instead of stuffing the whole input into the prompt, the model treats the input as an external environment it can search, slice, and — crucially — hand pieces of to *copies of itself*.

> This page assumes you know what a context window is. If not, read [GPT](https://aipedia.org/gpt) and [In-Context Learning](https://aipedia.org/in-context-learning) first.

## Why Students Should Care

- Context windows are a hard limit of today's models; RLMs show a way around the limit without retraining anything.
- The core trick — recursion — is one you already know from intro CS, applied to LLMs.
- It is a clean example of the shift from "model as text predictor" to "model as agent that writes code and calls tools."

## The Problem: Context Rot

Standard language models suffer from **context rot** — performance degrades as input length approaches or exceeds the context window. Even models with 128K+ token windows struggle with:

- Retrieval accuracy in long documents
- Multi-hop reasoning across distant passages
- Maintaining coherence over extended contexts

So simply buying a bigger window does not solve the problem. RLMs address it by changing how the model *interacts* with its input.

## Core Insight

Instead of:

```python
# Traditional: context IN the prompt
response = llm.completion(f"{huge_context}\n\nQuestion: {query}")
```

RLMs do:

```python
# RLM: context AS a variable in an environment
repl.set_variable("context", huge_context)
response = rlm.completion(query)  # Model writes code to explore context
```

The context becomes an **environment variable** in a REPL (an interactive code environment) that the model can programmatically query, slice, search, and recursively process. The model never reads the whole input — it writes code that reads the parts it needs.

## How It Works

1. **Load context into REPL**: the full input is stored as a string variable in a Python environment
2. **System prompt**: the root model receives instructions on how to interact with the environment
3. **Programmatic access**: the model can read slices, write helper functions, and spawn sub-LLM calls
4. **Recursive decomposition**: complex queries trigger recursive calls on smaller chunks
5. **Result combination**: answers bubble up and combine into the final response

## Interactive Demo

Explore how RLMs decompose problems and search through massive contexts:

*Interactive demo: https://aipedia.org/recursive-language-models*

## Example: Needle in a Haystack

Concretely — say you need to find one specific fact buried in 10M tokens of text.

**Traditional LLM approach**:
- Load all 10M tokens into context
- Attention over every token: $O(N)$ complexity
- Fails due to context window limits

**RLM approach**:

```python
def find_needle(context_var, query):
    # Split into chunks
    chunks = rlm.call("Divide context into 10 sections")

    # Query each chunk
    for i, chunk in enumerate(chunks):
        result = rlm.call(f"Does section {i} contain: {query}?")
        if result.found:
            # Recursive drill-down
            return find_needle(chunk, query)

    # Base case: small enough to read directly
    return rlm.call(f"Extract answer from: {context_var}")
```

Complexity: $O(\log N)$ — exponentially faster than a linear scan. The takeaway: **divide-and-conquer works for reading, not just for sorting.**

## Architecture

The RLM system consists of:

| Component | Role |
|-----------|------|
| **Root LLM** | Orchestrates the search, never sees raw context |
| **REPL Environment** | Holds context as variable, executes model-generated code |
| **Sub-LLM Calls** | Recursive invocations on context slices |
| **Sandbox** | Secure execution (Docker, Modal, or local) |

## Results

From the paper's benchmarks:

| Task | Vanilla LLM | RLM | Improvement |
|------|-------------|-----|-------------|
| Needle-in-Haystack (1M tokens) | 23% | 94% | +71% |
| Multi-hop QA | 31% | 78% | +47% |
| Long Document Summarization | 45% | 82% | +37% |

Key findings:

- Processes inputs **100x beyond context windows**
- **No degradation** at 10M+ tokens
- **RLM-Qwen3-8B** outperforms base model by 28.3% on average
- Approaches GPT-5 quality on long-context tasks

## Code Example

Using the official RLM library:

```python
from rlm import RLM

# Initialize with any backend
rlm = RLM(
    backend="openai",
    backend_kwargs={"model_name": "gpt-5-nano"},
    verbose=True,
)

# Process arbitrarily long context
with open("giant_document.txt") as f:
    context = f.read()  # 10M+ characters

result = rlm.completion(
    query="What are the key findings about climate change?",
    context=context
)
print(result.response)
```

## Why "Recursive"?

The model **calls itself** on sub-problems — the classic definition of recursion:

```
rlm(query, full_context)
├── rlm(query, chunk_1)
│   ├── rlm(query, chunk_1a)
│   └── rlm(query, chunk_1b)
├── rlm(query, chunk_2)
└── combine(results)
```

Each sub-call can spawn its own sub-calls until reaching a base case small enough to answer directly.

## Limitations

- **Latency overhead**: synchronous sub-calls increase end-to-end time
- **Simple tasks**: overkill for short contexts where direct inference is faster
- **Cost**: multiple LLM calls per query
- **Complexity**: requires REPL environment setup

## Future Directions

- **Asynchronous sub-calls**: parallel recursive queries
- **Native training**: models trained end-to-end for recursive reasoning
- **Long-horizon agents**: tasks spanning weeks with persistent context management

## Common Confusion

- **RLMs vs. long-context models**: a long-context model reads more tokens in one forward pass; an RLM keeps the model's window small and *navigates* a large input with code. They attack the same problem from opposite directions.
- **RLMs vs. RAG (retrieval-augmented generation)**: RAG retrieves chunks with a separate search index chosen ahead of time; an RLM decides *at inference time*, in code it writes itself, which parts of the input to read and can recurse on them.
- **"Recursive" does not mean recurrent**: this has nothing to do with recurrent neural networks. The recursion is at the level of whole model calls, not hidden states.

## Where To Go Next

- Read [In-Context Learning](https://aipedia.org/in-context-learning) to understand what a model can do with the context it *does* see.
- Read [Chain-of-Thought](https://aipedia.org/chain-of-thought) — RLMs extend the same "spend more compute by generating more steps" idea to code and sub-calls.
- Read [Transformer](https://aipedia.org/transformer) to see why attention cost and context limits exist in the first place.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) for the background on model capability vs. compute.


# Maximum Likelihood Reinforcement Learning (MaxRL)

> A recent idea for training models on pass-fail tasks when sampling matters

- Type: Paper
- By: Tajwar et al.
- Year: 2026
- Topics: Deep learning, Reinforcement learning, Optimization, Policy gradients
- Page: https://aipedia.org/maximum-likelihood-rl

## Resources

- [Maximum Likelihood Reinforcement Learning](https://arxiv.org/abs/2602.02710): Paper, Tajwar et al., 2026
- [Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning](https://doi.org/10.1007/BF00992696): Paper, Williams, 1992 (REINFORCE)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://arxiv.org/abs/2402.03300): Paper, Shao et al., 2024 (introduces GRPO)

**Maximum Likelihood Reinforcement Learning (MaxRL)** is a framework for pass-fail tasks such as math or code generation. Its central claim is that standard RL objectives do not match the real goal very well when success is measured by whether **at least one sampled answer is correct**.

> Read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) and [Policy Gradient](https://aipedia.org/policy-gradient) first. This page is about a recent paper and is more advanced than the core RL pages.

## A Concrete Motivation

Imagine a model solving coding problems. For one prompt, it gets the right answer only 5% of the time.

Now ask two different questions:

- **RL-style question**: did this single sampled answer get reward 1 or 0?
- **Sampling question**: if I sample 8 answers, what is the chance that at least one is correct?

Those are not the same training target. MaxRL is about reducing that mismatch.

## The Main Idea

For a prompt $x$, let $p_\theta(x)$ be the probability that the model produces a correct answer:

$$
p_\theta(x) = \sum_y \pi_\theta(y \mid x) \cdot \mathbb{1}[\text{correct}(y, x)]
$$

If you care about correctness, the natural objective is to increase $\log p_\theta(x)$. The problem is that correctness is observed only after sampling, so people usually fall back to policy-gradient style surrogates.

MaxRL shows that common RL updates capture only the **first part** of the maximum-likelihood gradient.

## Why Standard RL Can Be Misaligned

The paper derives:

$$
\log p = -\sum_{k=1}^{\infty} \frac{(1-p)^k}{k}
$$

That expansion matters because each term corresponds to a different sampling depth. Standard RL effectively optimizes only the first term. MaxRL keeps more of the structure that matters when pass rates are low and test-time sampling is important.

If the derivation feels abstract, keep this simpler idea in mind:

- standard RL mostly cares about improving **one-shot success**
- MaxRL tries to better match **sample-until-success style evaluation**

## Interactive Visualization

Explore how the truncated series approximates $\log(p)$ at different orders:

*Interactive demo: https://aipedia.org/maximum-likelihood-rl*

## The MaxRL Objective

MaxRL defines a family of objectives indexed by the number of samples $K$:

$$
J_{\text{MaxRL}}^{(K)}(\theta) = -\sum_{k=1}^{K} \frac{(1 - p_\theta)^k}{k}
$$

Two endpoints matter most:

1. **At $K=1$**: it reduces to the familiar first-order RL view
2. **As $K \to \infty$**: it approaches exact maximum likelihood

That is why the framework is useful conceptually: it connects ordinary RL training to a clearer maximum-likelihood target.

## What Changes in Practice

The paper's practical message is that you can reweight the policy-gradient signal by an estimate of the prompt's pass rate. Hard prompts then get larger updates, and easy prompts get smaller ones.

```python
# Standard GRPO-style advantage
advantage = (reward - baseline) / std

# MaxRL-style idea
mean_reward = reward.mean()  # estimated pass rate
advantage = (reward - baseline) / (std * mean_reward)
```

You do not need to memorize the formula. The intuition is:

- if a prompt is already easy, do not spend too much gradient on it
- if a prompt is very hard, a small success signal is especially valuable

## Why This Helps

| Pass rate | Standard RL emphasis | MaxRL emphasis |
|-----------|----------------------|----------------|
| High | Similar across prompts | Slightly reduced relative priority |
| Medium | Moderate | Stronger |
| Very low | Often too weak | Much stronger |

This makes MaxRL most interesting for problems where the model rarely succeeds on the first try but can improve through repeated sampling.

## When To Use This Lens

MaxRL is most relevant when:

- rewards are basically pass/fail
- test-time sampling matters
- you care about pass@K, not just pass@1
- the tasks are hard enough that first-try success is low

## Key Results

The paper reports that MaxRL improves sampling efficiency and often beats GRPO-style baselines on mathematical reasoning tasks.

For students, the higher-level takeaway is stronger than the benchmark table: **the paper argues that the objective itself should better reflect how sampled generation is evaluated**.

## What To Remember

- MaxRL is a bridge between RL training and maximum-likelihood training
- It matters most on pass-fail tasks with low initial success rates
- The key conceptual move is to care about more than the first-order RL term


# Backpropagation

> The algorithm that enables neural networks to learn by computing gradients efficiently

- Type: Concept
- By: Rumelhart, Hinton & Williams
- Year: 1986
- Topics: Deep learning, Fundamentals, Optimization, Neural networks
- Page: https://aipedia.org/backpropagation

## Resources

- [Learning representations by back-propagating errors](https://www.nature.com/articles/323533a0): Paper, Rumelhart, Hinton & Williams, 1986
- [karpathy/micrograd](https://github.com/karpathy/micrograd): Code, A tiny autograd engine
- [The spelled-out intro to neural networks and backpropagation](https://www.youtube.com/watch?v=VMj-3S1tku0): Video, Andrej Karpathy
- [Calculus on Computational Graphs: Backpropagation](https://colah.github.io/posts/2015-08-Backprop/): Article, Chris Olah, 2015

**Backpropagation** is the algorithm that makes deep learning possible. It efficiently computes, for every weight in a neural network, how much a small change in that weight would change the loss — and it does so in roughly one extra pass through the network.

> This page assumes you know what a neural network layer is and what a loss function measures. If "gradient" is unfamiliar, think of it as "the direction and amount to nudge a number to reduce the loss."

## Why Students Should Care

- Every training run of every modern neural network — CNNs, Transformers, diffusion models — uses backpropagation under the hood.
- When you call `loss.backward()` in PyTorch, this is the algorithm that runs. Understanding it demystifies your framework.
- Classic training problems (vanishing gradients, exploding gradients) and their fixes (ReLU, residual connections, normalization) only make sense once you understand how gradients flow backward.

## The Core Problem

Training means adjusting weights to reduce the loss. To know which way to adjust each weight, we need:

$$
\frac{\partial L}{\partial w_i} \quad \text{for every weight } w_i
$$

A network can have millions of weights. Naively computing each gradient separately — for example, by nudging one weight at a time and re-running the network — would be prohibitively expensive. Backpropagation gets **all** of the gradients efficiently by reusing shared work.

## The Chain Rule

Here is the whole trick: backpropagation is just the chain rule from calculus, applied systematically.

$$
\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y} \cdot \frac{\partial y}{\partial x}
$$

If $y = f(x)$ and $L = g(y)$, we can compute $\frac{\partial L}{\partial x}$ from $\frac{\partial L}{\partial y}$ and the local gradient $\frac{\partial y}{\partial x}$.

In words: if you already know how the loss reacts to $y$, and you know how $y$ reacts to $x$, multiply them to get how the loss reacts to $x$. Chain this through every layer, from the loss back to the input, and you get every gradient in the network.

## Forward and Backward Pass

Training a network is a two-phase loop.

### Forward Pass

First, compute outputs layer by layer, exactly as when making a prediction:

$$
z^{(l)} = W^{(l)} a^{(l-1)} + b^{(l)}, \quad a^{(l)} = \sigma(z^{(l)})
$$

Store the activations along the way — the backward pass will need them.

### Backward Pass

Then propagate gradients from the output back toward the input. Each layer receives "how the loss reacts to my output" and produces "how the loss reacts to my input":

$$
\delta^{(l)} = \frac{\partial L}{\partial z^{(l)}} = \left( (W^{(l+1)})^T \delta^{(l+1)} \right) \odot \sigma'(z^{(l)})
$$

Then compute the weight gradients from the layer's error signal and its stored input:

$$
\frac{\partial L}{\partial W^{(l)}} = \delta^{(l)} (a^{(l-1)})^T
$$

You do not need to memorize these equations. The important idea is: **each layer combines the error signal arriving from the layer above with its own stored activations, producing both its weight gradients and the error signal to pass further back.**

## Interactive Visualization

Watch gradients flow backward through a network:

*Interactive demo: https://aipedia.org/backpropagation*

## Computational Graph View

Modern frameworks generalize this beyond simple layer stacks. They represent any computation as a **directed acyclic graph** of operations:

1. **Forward**: Traverse the graph, compute outputs
2. **Backward**: Traverse in reverse, accumulate gradients

Each node stores:
- Forward function: $y = f(x_1, \ldots, x_n)$
- Backward function: $\frac{\partial L}{\partial x_i}$ given $\frac{\partial L}{\partial y}$

This is why you can write nearly arbitrary code in PyTorch or JAX and still get gradients: every operation knows its own local derivative, and the framework chains them for you.

## Common Layer Gradients

| Layer | Forward | Backward |
|-------|---------|----------|
| Linear | $y = Wx$ | $\frac{\partial L}{\partial W} = \frac{\partial L}{\partial y} x^T$ |
| ReLU | $y = \max(0, x)$ | $\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y} \cdot \mathbf{1}_{x > 0}$ |
| Softmax+CE | $L = -\log p_c$ | $\frac{\partial L}{\partial z} = p - y$ |
| BatchNorm | $y = \gamma \hat{x} + \beta$ | (complex, involves batch statistics) |

Notice how simple most of these are: ReLU's backward pass just zeroes out gradients where the input was negative.

## Vanishing/Exploding Gradients

Backprop multiplies many local gradients together. In a deep network, the gradient reaching the earliest layer is a long product:

$$
\frac{\partial L}{\partial w^{(1)}} = \prod_{l=2}^{L} \frac{\partial z^{(l)}}{\partial z^{(l-1)}} \cdot \frac{\partial L}{\partial z^{(L)}}
$$

Long products of numbers behave badly:

- If the factors are less than 1: **vanishing gradients** (early layers barely learn)
- If the factors are greater than 1: **exploding gradients** (unstable training)

**Solutions**: ReLU, residual connections, careful initialization, normalization. Much of modern architecture design exists to keep this product well-behaved.

## Automatic Differentiation

Modern frameworks (PyTorch, JAX) implement backprop automatically — you write the forward pass, they derive the backward pass:

```python
# Forward
y = model(x)
loss = criterion(y, target)

# Backward (computes all gradients)
loss.backward()

# Update
optimizer.step()
```

## Why Backprop Matters

Backpropagation is:
- **Efficient**: $O(n)$ gradient computation for $n$ parameters
- **General**: Works for any differentiable computation graph
- **Foundational**: Enables all modern deep learning

## Common Confusion

- **Backpropagation is not a training algorithm by itself.** It only computes gradients. An optimizer (SGD, [Adam](https://aipedia.org/adam)) then decides how to use them to update the weights.
- **Backprop is not specific to neural networks.** It is reverse-mode automatic differentiation, applicable to any differentiable program.
- **The backward pass is not a second "reverse network."** It reuses the same weights and the activations stored during the forward pass.
- **"Gradient descent" and "backpropagation" are different things**: gradient descent is the update rule; backprop is how the gradients for that rule are computed.

## Where To Go Next

- Read [Adam](https://aipedia.org/adam) for what happens to the gradients after backprop computes them.
- Read [Batch Normalization](https://aipedia.org/batch-normalization) and [Layer Normalization](https://aipedia.org/layer-normalization) for techniques that keep gradients well-scaled in deep networks.
- Read [ResNet](https://aipedia.org/resnet) for how residual connections solved gradient flow in very deep networks.
- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for how recurrent networks confronted vanishing gradients across time.


# Policy Gradient Methods

> Directly optimizing policies through gradient ascent on expected returns

- Type: Concept
- By: Williams
- Year: 1992
- Topics: Deep learning, Reinforcement learning, Optimization
- Page: https://aipedia.org/policy-gradient

## Resources

- [Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning](https://doi.org/10.1007/BF00992696): Paper, Williams, 1992 (REINFORCE)
- [Policy Gradient Methods for Reinforcement Learning with Function Approximation](https://proceedings.neurips.cc/paper/1999/hash/464d828b85b0bed98e80ade0a5c43b0f-Abstract.html): Paper, Sutton et al., 1999
- [Policy Gradient Algorithms](https://lilianweng.github.io/posts/2018-04-08-policy-gradient/): Article, Lilian Weng, 2018
- [Intro to Policy Optimization](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html): Docs, OpenAI Spinning Up

**Policy Gradient Methods** learn a behavior directly: the policy $\pi_\theta(a|s)$ is a neural network, and we adjust its weights by gradient ascent so that actions leading to high reward become more likely. Unlike value-based methods such as [DQN](https://aipedia.org/dqn), they naturally handle continuous actions and stochastic policies.

> If "policy", "return", or "state" are unfamiliar, read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) first. This page is the foundation for [PPO](https://aipedia.org/ppo).

## Why Students Should Care

- Policy gradients are the second great family of RL algorithms (the other being value-based methods), and the family that modern practice mostly lives in.
- [PPO](https://aipedia.org/ppo) — and through it, [RLHF](https://aipedia.org/rlhf) for language models — is a direct descendant of the ideas on this page.
- The log-derivative trick used here is a general tool for optimizing through sampling, useful well beyond RL.

## The Idea in Plain English

Think of a coach reviewing game footage. After each game, the coach's advice is simple: **"Whatever you did in the games we won — do more of that. Whatever you did in the games we lost — do less of it."**

That is the entire policy gradient recipe. Play with the current policy, look at the total reward, and nudge the policy's parameters so that high-reward actions get higher probability.

## The Objective

Formally, we want the policy parameters $\theta$ that maximize expected return:

$$
J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_{t=0}^{T} \gamma^t r_t\right]
$$

To improve $\theta$ by gradient ascent, we need $\nabla_\theta J(\theta)$. The catch: the expectation is over trajectories $\tau$ produced by the environment, whose dynamics we usually cannot differentiate through — or even know.

## The Policy Gradient Theorem

The key result that makes this tractable anyway:

$$
\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_{t=0}^{T} \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot R_t\right]
$$

where $R_t = \sum_{t'=t}^{T} \gamma^{t'-t} r_{t'}$ is the return from step $t$ onward.

You do not need to memorize the equation. The important idea is: **for each action taken, push up its log-probability in proportion to how much reward followed it.** Actions followed by big rewards get strongly reinforced; actions followed by nothing get left alone.

## Why Log Probability?

The formula comes from the "log-derivative trick":

$$
\nabla_\theta \pi_\theta(a|s) = \pi_\theta(a|s) \nabla_\theta \log \pi_\theta(a|s)
$$

This identity rewrites the gradient of an expectation as an expectation of gradients — something we can estimate just by sampling actions and observing rewards. Crucially, the environment's dynamics never appear in the formula, so we never need to know or model them.

## REINFORCE Algorithm

The simplest policy gradient method turns the theorem directly into code:

```python
for episode in episodes:
    states, actions, rewards = collect_trajectory(policy)
    returns = compute_returns(rewards, gamma)
    
    loss = 0
    for s, a, R in zip(states, actions, returns):
        loss -= log_prob(policy(s), a) * R
    
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()
```

Note the minus sign: optimizers minimize, so we minimize the *negative* of the objective.

## Interactive Visualization

Watch how policy gradients update a simple policy:

*Interactive demo: https://aipedia.org/policy-gradient*

## High Variance Problem

REINFORCE works, but its gradient estimates are extremely noisy:

1. Returns vary widely across episodes — one lucky episode can swing the update
2. Credit assignment is imprecise: *every* action in a good episode gets reinforced, including the bad ones (which action actually caused the reward?)

High variance means you need many samples and small learning rates, which makes plain REINFORCE slow in practice.

## Variance Reduction: Baselines

A simple fix: judge each return against a **baseline** $b(s)$ — a running estimate of "how well things usually go from here" — and reinforce only the *difference*:

$$
\nabla_\theta J(\theta) = \mathbb{E}\left[\nabla_\theta \log \pi_\theta(a_t|s_t) \cdot (R_t - b(s_t))\right]
$$

Subtracting a baseline does not change the expected gradient (it is still unbiased), but it can shrink the variance a lot. The most common choice is the state value: $b(s) = V(s)$.

Intuition: instead of "you got 100 points, do more of that", the update becomes "you got 100 points when 90 was typical — do slightly more of that."

## Actor-Critic Methods

Take the baseline idea one step further and *learn* the value function with a second network:

- **Actor**: the policy $\pi_\theta(a|s)$ — decides what to do
- **Critic**: the value function $V_\phi(s)$ — estimates how good each state is

$$
\nabla_\theta J(\theta) \approx \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot (r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t))
$$

The term in parentheses is the **advantage** $A_t = r_t + \gamma V(s_{t+1}) - V(s_t)$: it tells us whether the action turned out better or worse than the critic expected. Positive advantage → do it more; negative → do it less.

## Key Algorithms

| Algorithm | Key Idea |
|-----------|----------|
| REINFORCE | Vanilla policy gradient |
| A2C | Actor-critic with advantage |
| A3C | Asynchronous parallel training |
| PPO | Clipped surrogate objective |
| TRPO | Trust region constraint |

## Advantages of Policy Gradients

1. **Continuous actions**: Natural parameterization — no need to enumerate actions and take a max
2. **Stochastic policies**: Better exploration comes built in
3. **Direct optimization**: Optimize what you care about (return), not a proxy
4. **Convergence**: Guaranteed to reach a local optimum

## When to Use

- Continuous action spaces (robot joints, steering angles)
- When you need stochastic policies
- When state representation is rich enough

## Common Confusion

- **Policy gradient vs. value-based**: policy gradient methods learn the policy directly; value-based methods like [DQN](https://aipedia.org/dqn) learn action values and derive the policy by taking the best-scoring action.
- **REINFORCE vs. policy gradient**: REINFORCE is the simplest *member* of the policy gradient family, not a synonym for it.
- **Baseline vs. critic**: a baseline is any comparison value subtracted from the return; a critic is a *learned* baseline (and its use defines actor-critic methods).
- **Return $R_t$ vs. advantage $A_t$**: the return is raw accumulated reward; the advantage is the return relative to what was expected. Modern methods almost always use advantages.

## Where To Go Next

- Read [PPO](https://aipedia.org/ppo) for the refinement of these ideas that dominates modern practice.
- Read [DQN](https://aipedia.org/dqn) for the contrasting value-based family.
- Read [RLHF](https://aipedia.org/rlhf) to see policy optimization applied to language models.
- Read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) for the MDP framing underneath it all.


# Dropout: Regularization for Neural Networks

> Randomly dropping units during training to prevent overfitting

- Type: Concept
- By: Hinton et al.
- Year: 2012
- Topics: Deep learning, Training, Regularization, Optimization
- Page: https://aipedia.org/dropout

## Resources

- [Improving neural networks by preventing co-adaptation of feature detectors](https://arxiv.org/abs/1207.0580): Paper, Hinton et al., 2012
- [Dropout: A Simple Way to Prevent Neural Networks from Overfitting](https://jmlr.org/papers/v15/srivastava14a.html): Paper, Srivastava et al., 2014
- [Dropout as a Bayesian Approximation](https://arxiv.org/abs/1506.02142): Paper, Gal & Ghahramani, 2016
- [DropBlock: A regularization technique for convolutional networks](https://arxiv.org/abs/1810.12890): Paper, Ghiasi et al., 2018

**Dropout**, introduced by Hinton et al. in 2012 and formalized by Srivastava et al. in 2014, is a simple yet powerful regularization technique: during training, randomly "drop" (zero out) neurons with probability $p$. Forcing the network to work with random pieces missing prevents neurons from co-adapting and dramatically reduces overfitting.

> Regularization means "anything that helps a model generalize to new data instead of memorizing its training data." If that idea is new, keep it in mind — it is the whole point of this page.

## Why Students Should Care

- Dropout was a key ingredient in [AlexNet](https://aipedia.org/alexnet), the 2012 ImageNet winner that kicked off the deep learning era.
- It is still used everywhere, including inside Transformers (attention dropout).
- It is the cleanest example of a big idea: adding *noise* during training can make a model *better* at test time.

## The Problem: Overfitting

Deep networks have millions of parameters and can easily memorize their training data — great training accuracy, poor performance on anything new. Traditional regularization (like L2 weight penalties) wasn't enough for very deep networks.

An intuition for one failure mode: neurons can form brittle "conspiracies," where one neuron's mistake is patched by another specific neuron. These co-adapted circuits fit the training set but fall apart on new data.

## The Solution: Random Dropout

During each training forward pass, flip a coin for every neuron and set its output to zero with probability $p$:

$$
\tilde{h}_i = \begin{cases}
0 & \text{with probability } p \\
h_i & \text{with probability } 1-p
\end{cases}
$$

Typically $p = 0.5$ for hidden layers, $p = 0.2$ for input layers. Every training step sees a different random "thinned" network.

## Interactive Demo

Visualize dropout in action across training iterations:

*Interactive demo: https://aipedia.org/dropout*

## Training vs. Inference

Dropout is only active during training. But that creates a mismatch: a neuron that was present only half the time during training is suddenly always present at test time, so downstream activations would be systematically larger. Scaling fixes this.

**Training**: Randomly drop neurons with probability $p$

**Inference**: Use all neurons but scale by $(1-p)$:

$$
h_{test} = (1-p) \cdot h
$$

Or equivalently, scale during training instead (inverted dropout — what frameworks actually do):

$$
h_{train} = \frac{h}{1-p} \cdot \text{mask}
$$

The takeaway: **the scaling exists so that the expected value of each activation matches between training and inference.**

## Why Dropout Works

### 1. Ensemble Effect
Each dropout mask creates a different "sub-network." Training with dropout is like training an ensemble of $2^n$ networks (where $n$ is the number of neurons), then averaging their predictions — and averaging many models is a classic way to generalize better.

### 2. Prevents Co-adaptation
Without dropout, neurons can become overly dependent on specific other neurons. Dropout forces each neuron to be useful on its own, because any of its partners might vanish at any moment.

### 3. Sparse Representations
Neurons must be robust to missing peers, encouraging more distributed, sparse representations.

## The Algorithm

The implementation is a few lines:

```python
def dropout_forward(x, p=0.5, training=True):
    if training:
        # Create binary mask
        mask = (torch.rand_like(x) > p).float()
        # Apply mask and scale (inverted dropout)
        return x * mask / (1 - p)
    else:
        # No dropout at inference
        return x
```

## Dropout Variations

The same idea — randomly remove something during training — has been applied at many granularities:

| Variant | Description |
|---------|-------------|
| **Standard Dropout** | Drop individual neurons |
| **DropConnect** | Drop individual weights instead |
| **Spatial Dropout** | Drop entire feature maps (for CNNs) |
| **DropBlock** | Drop contiguous regions in feature maps |
| **Attention Dropout** | Drop attention weights in transformers |

## Typical Dropout Rates

| Layer Type | Recommended Rate |
|------------|-----------------|
| Input layer | 0.1 - 0.2 |
| Hidden layers | 0.4 - 0.5 |
| Convolutional layers | 0.2 - 0.3 |
| Before final layer | 0.5 |

## Mathematical Interpretation

Beyond the intuitions above, dropout can be viewed more formally as:

1. **Approximate Bayesian inference**: Implicitly learning a distribution over weights
2. **Data augmentation**: Each example is seen with different network architectures
3. **Noise injection**: Adding multiplicative Bernoulli noise to hidden units

You do not need these framings to use dropout — they matter if you want to study *why* it works.

## Dropout + BatchNorm

There's a subtle interaction: [BatchNorm](https://aipedia.org/batch-normalization)'s statistics change when dropout is applied. Common practices:
- Apply dropout after BatchNorm
- Use lower dropout rates with BatchNorm
- Some architectures skip dropout entirely when using BatchNorm

## When Not to Use Dropout

1. **Small datasets**: May need even stronger regularization
2. **BatchNorm-heavy architectures**: BatchNorm already provides regularization
3. **At inference time**: Always disabled
4. **LSTMs/RNNs**: Use variational dropout (same mask across time steps)

## Impact on Training

Expect dropout to make training *look* worse while making generalization better:

| Aspect | Without Dropout | With Dropout |
|--------|----------------|--------------|
| Training loss | Lower | Higher |
| Validation loss | Often higher (overfit) | Lower |
| Training time | Faster per epoch | Slower convergence |
| Generalization | Poor | Better |

## Historical Impact

Dropout was transformative:
- Enabled training of much deeper networks
- Became standard in AlexNet (2012 ImageNet winner)
- Reduced reliance on hand-designed regularization
- Inspired numerous variants and theoretical analysis

## Common Confusion

- **$p$ is the probability of *dropping*, not keeping** — though some libraries define it the other way. Check your framework's docs.
- **Dropout is off at inference.** If your model behaves randomly at test time, you probably forgot to switch to evaluation mode.
- **Dropout is a regularizer, not a normalizer.** [BatchNorm](https://aipedia.org/batch-normalization) rescales activations; dropout removes them. They are different tools that happen to both fight overfitting.
- **Higher training loss with dropout is expected**, not a bug — the payoff shows up in validation loss.

## Where To Go Next

- Read [AlexNet](https://aipedia.org/alexnet) for the landmark model that made dropout famous.
- Read [Batch Normalization](https://aipedia.org/batch-normalization) for the other standard training-stabilizer and how the two interact.
- Read [RNN Regularization](https://aipedia.org/rnn-regularization) for how dropout is adapted to recurrent networks.
- Read [Transformer](https://aipedia.org/transformer) to spot where dropout appears in modern architectures.


# Variational Autoencoder (VAE)

> Probabilistic generative model with structured latent space

- Type: Concept
- By: Kingma & Welling
- Year: 2013
- Topics: Deep learning, Generative, Autoencoder, Latent space
- Page: https://aipedia.org/vae

## Resources

- [Auto-Encoding Variational Bayes](https://arxiv.org/abs/1312.6114): Paper, Kingma & Welling, 2013
- [Early Visual Concept Learning with Unsupervised Deep Learning](https://arxiv.org/abs/1606.05579): Paper, Higgins et al., 2016 (precursor to β-VAE)
- [Neural Discrete Representation Learning (VQ-VAE)](https://arxiv.org/abs/1711.00937): Paper, van den Oord et al., 2017

A **Variational Autoencoder (VAE)** is a generative model that learns a *distribution* over latent variables rather than a single compressed code, enabling smooth interpolation, sampling of new data, and principled uncertainty.

> This page introduces the VAE from scratch. Once it makes sense, read [Variational Lossy Autoencoder](https://aipedia.org/variational-lossy-autoencoder) for a second pass that explains what the VAE objective *means* in terms of compression.

## Why Students Should Care

- VAEs form the foundation of many modern generative models, including the latent spaces used by [latent diffusion](https://aipedia.org/latent-diffusion) (the architecture behind Stable Diffusion).
- Two of its tools — the **ELBO** and the **reparameterization trick** — appear all over machine learning, far beyond VAEs.
- It is the cleanest example of combining deep learning with probabilistic modeling: you get a generative model you can both *sample from* and *reason about*.

## The Problem VAEs Solve

Start with a plain autoencoder: a network that compresses an input (say, a face image) down to a short vector, then reconstructs it. This works for compression, but fails as a *generator*. If you pick a random vector and decode it, you usually get garbage — the latent space has "holes," because the model was never told how codes should be arranged.

The VAE fixes this by making the latent space *probabilistic and organized*: every input maps to a small cloud of codes rather than a single point, and all the clouds are nudged toward a standard shape. The result is a latent space where random samples decode to coherent outputs.

## Core Idea

Instead of encoding an input x to a single latent vector, a VAE learns a posterior distribution:

$$
q_\phi(z|x) = \mathcal{N}(z; \mu(x), \sigma^2(x))
$$

In plain English: the encoder outputs a *mean* and a *spread* for each input, defining a Gaussian over possible codes. Sampling from this distribution allows the model to generate diverse yet coherent outputs.

## Evidence Lower Bound (ELBO)

VAEs are trained by maximizing the **ELBO**:

$$
\mathcal{L}(x) = \mathbb{E}_{q(z|x)}[\log p_\theta(x|z)] - D_{KL}(q(z|x) \| p(z))
$$

The two terms make a deal:

- **Reconstruction term** (first): encourages accurate decoding of samples — "when you encode x and decode it, you should get x back."
- **KL divergence** (second): regularizes the posterior toward the prior p(z) = N(0,I) — "keep your codes close to a standard Gaussian, so the latent space stays smooth."

You do not need to memorize the equation. The important idea is: **the VAE trades off reconstruction fidelity against keeping the latent space simple enough to sample from**. This tradeoff balances fidelity and generalization.

## Reparameterization Trick

There is one technical obstacle: training requires gradients, but "sample z from q(z|x)" is a random operation, and you cannot backpropagate through a random draw. Directly sampling z from q(z|x) blocks gradients.

The solution is to rewrite sampling as:

$$
z = \mu + \sigma \cdot \epsilon, \quad \epsilon \sim \mathcal{N}(0, 1)
$$

Randomness is isolated in ε (a fixed noise source with no parameters), allowing gradients to flow through μ and σ. This one-line trick is what makes VAEs trainable end to end, and it reappears throughout deep learning whenever someone needs gradients through sampling.

## Interactive Visualization

Explore how VAEs encode distributions, sample latents, interpolate, and decode:

*Interactive demo: https://aipedia.org/vae*

## VAE vs. Autoencoder

| Autoencoder | Variational Autoencoder |
|------------|------------------------|
| Deterministic latent | Probabilistic latent |
| No prior on z | Explicit prior p(z) |
| Poor sampling | Smooth generation |
| Optimizes reconstruction | Optimizes ELBO |

## Extensions

- **β-VAE** – stronger disentanglement via increased KL weight
- **VQ-VAE** – discrete latent codes via vector quantization
- **Conditional VAE** – generation conditioned on labels
- **Hierarchical VAE** – multi-level latent variables

## Common Confusion

- **"Variational" refers to variational inference** (approximating an intractable posterior with a learnable one), not to variety in the outputs.
- **The KL term is not just generic regularization** like weight decay — it specifically shapes the latent space to match the prior, which is what makes sampling work. See [Variational Lossy Autoencoder](https://aipedia.org/variational-lossy-autoencoder) for the deeper compression view.
- **VAE vs. [GAN](https://aipedia.org/gan)**: a VAE has an encoder and an explicit training objective (the ELBO); a GAN has neither, and instead learns through an adversarial game. VAE samples tend to be blurrier but training is far more stable.
- **A VAE is a model plus a training objective**, not just an architecture — the encoder/decoder networks can be MLPs, CNNs, or anything differentiable.

## Where To Go Next

- Read [Variational Lossy Autoencoder](https://aipedia.org/variational-lossy-autoencoder) for the rate-distortion interpretation of the ELBO and posterior collapse.
- Read [GAN](https://aipedia.org/gan) for the adversarial alternative to likelihood-based generation.
- Read [Diffusion Models](https://aipedia.org/diffusion-models) for the generative approach that now leads image synthesis.
- Read [Latent Diffusion](https://aipedia.org/latent-diffusion) to see a VAE used as the compression stage of Stable Diffusion.


# Word2Vec: Word Embeddings

> Learning dense vector representations of words from text

- Type: Concept
- By: Mikolov et al.
- Year: 2013
- Topics: NLP, Embeddings, Deep learning, Representation learning
- Page: https://aipedia.org/word2vec

## Resources

- [Efficient Estimation of Word Representations in Vector Space](https://arxiv.org/abs/1301.3781): Paper, Mikolov et al., 2013
- [The Illustrated Word2vec](https://jalammar.github.io/illustrated-word2vec/): Article, Jay Alammar
- [Distributed Representations of Words and Phrases and their Compositionality](https://arxiv.org/abs/1310.4546): Paper, Mikolov et al., 2013
- [GloVe: Global Vectors for Word Representation](https://nlp.stanford.edu/pubs/glove.pdf): Paper, Pennington et al., 2014
- [Enriching Word Vectors with Subword Information (FastText)](https://arxiv.org/abs/1607.04606): Paper, Bojanowski et al., 2016

**Word2Vec** is a method for turning words into vectors of numbers so that words with similar meanings end up close together. Introduced by Mikolov et al. at Google in 2013, it revolutionized NLP — the famous equation "king - man + woman = queen" showed that these vectors capture meaningful relationships.

> This page is a good starting point for NLP — no Transformer knowledge needed. For what replaced static word vectors, see [BERT](https://aipedia.org/bert).

## Why Students Should Care

- **Embeddings are everywhere.** Every modern language model starts by mapping tokens to vectors — Word2Vec is where that idea took off.
- It is the cleanest demonstration that **meaning can emerge from prediction**: train on a simple guessing game, get semantic structure for free.
- The same trick was later applied to graphs, products, users, and more — "X2Vec" became a pattern.

## A Quick Example

How would you represent the word "cat" as numbers? The naive answer is a **one-hot vector**: a huge vector of zeros with a single 1 in the "cat" slot. But then "cat" and "dog" are exactly as different from each other as "cat" and "refrigerator" — every pair of one-hot vectors is equally far apart. There is no notion of similarity at all.

Word2Vec's answer: learn a short, dense vector for each word from how it is used in text. Words that appear in similar contexts ("cat" and "dog" both appear near "pet", "fur", "vet") end up with similar vectors.

## The Key Insight

Instead of one-hot vectors (sparse, no similarity), learn dense embeddings where:

- Similar words are close: vec("cat") ≈ vec("dog")
- Relationships are linear: vec("king") - vec("man") + vec("woman") ≈ vec("queen")

## Two Architectures

Both variants train embeddings by playing a prediction game over a sliding window of text — they just play it in opposite directions.

### Skip-gram

Given a word, predict the surrounding context words:

$$
P(w_{context} | w_{center}) = \frac{\exp(v_{w_c}^T v_{w_t})}{\sum_{w \in V} \exp(v_w^T v_{w_t})}
$$

**Objective**: maximize the probability of the context words given the center word. The dot product $v_{w_c}^T v_{w_t}$ measures how compatible two word vectors are — the softmax turns those scores into probabilities.

### CBOW (Continuous Bag of Words)

Given the context words, predict the center word:

$$
P(w_{center} | w_{context}) = \frac{\exp(v_{w_t}^T \bar{v}_{context})}{\sum_{w \in V} \exp(v_w^T \bar{v}_{context})}
$$

where $\bar{v}_{context}$ is the average of the context word vectors.

You do not need to memorize either formula. The important idea is: **words are pushed toward vectors that make their real contexts predictable**.

## Interactive Demo

Explore word embeddings and vector arithmetic:

*Interactive demo: https://aipedia.org/word2vec*

## Training with Negative Sampling

There is a practical problem: the softmax above sums over the *entire vocabulary* (hundreds of thousands of words) for every training example. That is far too expensive. **Negative sampling** approximates it:

$$
\log \sigma(v_{w_O}^T v_{w_I}) + \sum_{i=1}^{k} \mathbb{E}_{w_i \sim P_n(w)} [\log \sigma(-v_{w_i}^T v_{w_I})]
$$

Instead of normalizing over all words, contrast each positive pair against just $k$ random "negative" words. In plain English: **make the true context word score high, and a handful of random words score low**.

## The Training Process

```
Sentence: "The quick brown fox jumps"
Window size: 2

For center word "brown":
  Positive pairs: (brown, quick), (brown, fox)
  Negative samples: (brown, computer), (brown, elephant), ...

Objective: Push positive pairs together, negative pairs apart
```

## Why Linear Relationships?

Why does vector arithmetic like king - man + woman work at all? The optimization objective creates a structure where:

$$
\vec{v}_{king} - \vec{v}_{man} \approx \vec{v}_{queen} - \vec{v}_{woman}
$$

This emerges because words appearing in similar contexts get similar vectors, and gender/royalty patterns are consistent across the corpus. Nobody programmed this in — it is a side effect of the prediction objective.

## Hyperparameters

| Parameter | Typical Value | Effect |
|-----------|---------------|--------|
| Embedding dimension | 100-300 | Higher = more capacity |
| Window size | 5-10 | Larger = more syntactic |
| Negative samples | 5-20 | More = better for rare words |
| Min word count | 5 | Filter rare words |
| Subsampling | 1e-3 to 1e-5 | Downsample frequent words |

## Word2Vec vs. Later Methods

| Method | Year | Key Difference |
|--------|------|----------------|
| **Word2Vec** | 2013 | Static embeddings, one vector per word |
| **GloVe** | 2014 | Global co-occurrence statistics |
| **FastText** | 2016 | Subword embeddings (handles OOV) |
| **ELMo** | 2018 | Context-dependent embeddings |
| **BERT** | 2018 | Deep bidirectional context |

## Limitations

1. **One vector per word**: "bank" (river) = "bank" (financial) — the vector must average both meanings
2. **No morphology**: "run", "running", "runs" are unrelated
3. **Fixed vocabulary**: out-of-vocabulary words get no embedding
4. **Shallow context**: just neighboring words, not deep semantics

These limitations led to contextual embeddings (ELMo, [BERT](https://aipedia.org/bert)), where a word's vector changes depending on the sentence it appears in.

## Historical Impact

Word2Vec:

- Made NLP research accessible (fast to train)
- Introduced the embedding paradigm
- Enabled transfer learning in NLP
- Demonstrated emergent structure in learned representations
- Inspired similar approaches for graphs, products, etc.

## Common Confusion

- **Word2Vec embeddings are static; BERT embeddings are contextual.** Word2Vec gives each word one fixed vector; BERT computes a fresh vector for each occurrence based on the sentence.
- **Skip-gram and CBOW are two training setups, not two models.** Both produce the same kind of word vectors — they differ only in which side of the window is predicted.
- **Word2Vec is not a language model.** It learns representations from a prediction game, but it is not designed to generate text.

## Where To Go Next

- Read [BERT](https://aipedia.org/bert) for contextual embeddings that fixed Word2Vec's one-vector-per-word limit
- Read [Transformer](https://aipedia.org/transformer) for the architecture behind contextual embeddings
- Read [Seq2Seq](https://aipedia.org/seq2seq) for how word vectors feed into sequence models
- Read [Pre-training](https://aipedia.org/pre-training) for the broader idea of learning from unlabeled data first


# Adam Optimizer

> Adaptive learning rates with momentum for deep learning

- Type: Concept
- By: Kingma & Ba
- Year: 2014
- Topics: Deep learning, Training, Optimization
- Page: https://aipedia.org/adam

## Resources

- [Adam: A Method for Stochastic Optimization](https://arxiv.org/abs/1412.6980): Paper, Kingma & Ba, 2014
- [Decoupled Weight Decay Regularization (AdamW)](https://arxiv.org/abs/1711.05101): Paper, Loshchilov & Hutter, 2017
- [On the Variance of the Adaptive Learning Rate and Beyond (RAdam)](https://arxiv.org/abs/1908.03265): Paper, Liu et al., 2019
- [Symbolic Discovery of Optimization Algorithms (Lion)](https://arxiv.org/abs/2302.06675): Paper, Chen et al., 2023

**Adam** (Adaptive Moment Estimation), introduced by Kingma and Ba in 2014, is the most widely used optimizer in deep learning. The core idea is simple: instead of using one fixed step size for every parameter, Adam watches how each parameter's gradient behaves over time and gives each parameter its own momentum-smoothed, adaptively-scaled update.

> If gradients and training loops are new to you, read [Backpropagation](https://aipedia.org/backpropagation) first. Backprop computes the gradients; an optimizer like Adam decides how to use them to update the weights.

## Why Students Should Care

- Adam (or its variant AdamW) is the default optimizer in nearly every modern deep learning project, including Transformers and large language models.
- It combines the benefits of momentum and adaptive learning rates, requiring minimal tuning while working well across diverse problems.
- Understanding Adam explains a lot of practical training advice you will encounter: warmup schedules, weight decay choices, and optimizer memory costs.

## The Problem with Vanilla SGD

Plain Stochastic Gradient Descent takes the same size step for every parameter, scaled only by the raw gradient. That causes trouble:

- Same learning rate for all parameters (bad for sparse features, where some parameters get gradients rarely)
- Struggles with saddle points and ravines, where the loss surface is steep in one direction and flat in another
- Requires careful learning rate scheduling by hand

## Adam's Solution

Think of Adam as answering two questions for each parameter, using running averages of its gradient history:

- **Which direction have gradients been pointing lately?** (momentum)
- **How large have gradients been lately?** (adaptive scaling)

Concretely, Adam maintains two moving averages for each parameter:

1. **First moment (momentum)**: $m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t$
2. **Second moment (adaptive LR)**: $v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2$

Then it updates the weights using:

$$
\theta_{t+1} = \theta_t - \frac{\alpha}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t
$$

You do not need to memorize the equation. The important idea is: **step in the smoothed gradient direction ($\hat{m}_t$), but shrink the step for parameters whose gradients have been large ($\sqrt{\hat{v}_t}$ in the denominator).**

## Bias Correction

There is one subtlety. The moving averages start at zero, so early in training $m_t$ and $v_t$ are biased toward zero — they underestimate the true averages. Adam corrects this:

$$
\hat{m}_t = \frac{m_t}{1 - \beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1 - \beta_2^t}
$$

This correction is crucial for proper early training. Without it, the first steps would be far too small (or, after dividing, badly mis-scaled).

## Interactive Demo

Compare Adam with other optimizers on a loss landscape:

*Interactive demo: https://aipedia.org/adam*

## The Complete Algorithm

The whole optimizer fits in a few lines:

```python
def adam(params, grads, m, v, t, lr=0.001, beta1=0.9, beta2=0.999, eps=1e-8):
    t += 1
    for p, g, m_i, v_i in zip(params, grads, m, v):
        # Update biased moments
        m_i = beta1 * m_i + (1 - beta1) * g
        v_i = beta2 * v_i + (1 - beta2) * g**2

        # Bias correction
        m_hat = m_i / (1 - beta1**t)
        v_hat = v_i / (1 - beta2**t)

        # Update parameters
        p -= lr * m_hat / (sqrt(v_hat) + eps)

    return t
```

## Default Hyperparameters

| Parameter | Default | Description |
|-----------|---------|-------------|
| $\alpha$ (lr) | 0.001 | Step size |
| $\beta_1$ | 0.9 | First moment decay |
| $\beta_2$ | 0.999 | Second moment decay |
| $\epsilon$ | 1e-8 | Numerical stability |

These defaults work remarkably well across many problems — which is a big part of why Adam became so popular.

## Why Adam Works

### Momentum ($\beta_1$)
- Accumulates gradient direction over time
- Smooths out noisy gradients (mini-batches give noisy estimates)
- Helps escape shallow local minima

### Adaptive Learning Rate ($\beta_2$)
- Parameters with large gradients get smaller steps
- Parameters with small gradients get larger steps
- No manual learning rate scheduling needed

## Adam Variants

Researchers have proposed many tweaks. The names come up often in papers and codebases:

| Variant | Improvement |
|---------|-------------|
| **AdamW** | Decoupled weight decay (better generalization) |
| **AMSGrad** | Non-increasing step sizes (convergence fix) |
| **RAdam** | Rectified Adam (variance correction) |
| **AdaFactor** | Memory-efficient for large models |
| **LAMB** | Layer-wise adaptive for large batch training |
| **Lion** | Simplified, sign-based updates |

## AdamW: The Modern Default

The one variant you should actually know is **AdamW**. In standard Adam, L2 regularization gets mixed into the gradient and is therefore rescaled by the adaptive step sizes, which weakens it in unpredictable ways. AdamW decouples weight decay from the gradient update:

$$
\theta_{t+1} = \theta_t - \alpha \left( \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon} + \lambda \theta_t \right)
$$

The takeaway: **weight decay is applied directly to the weights, not passed through the adaptive scaling.** AdamW is now the default for Transformers and large language models.

## Comparison with Other Optimizers

| Optimizer | Momentum | Adaptive LR | Memory | Use Case |
|-----------|----------|-------------|--------|----------|
| **SGD** | Optional | No | 1x | Well-tuned vision models |
| **RMSprop** | No | Yes | 2x | RNNs |
| **Adam** | Yes | Yes | 3x | General purpose |
| **AdamW** | Yes | Yes | 3x | Transformers, LLMs |

The memory column matters: Adam stores two extra numbers ($m$ and $v$) for every parameter, so optimizer state can be twice the size of the model itself.

## When NOT to Use Adam

1. **ImageNet training**: SGD with momentum often generalizes better
2. **Memory-constrained**: Adam needs 3x memory of SGD
3. **Small datasets**: Can overfit more than SGD

## Learning Rate Scheduling

Adaptive steps do not remove the need for a schedule. Even with Adam, learning rate schedules help:

- **Warmup**: Start low, increase gradually (critical for transformers)
- **Cosine decay**: Smooth decrease to zero
- **Step decay**: Discrete reductions at milestones

## Historical Impact

Adam's impact:
- Became the default optimizer for most deep learning
- Enabled training without extensive hyperparameter search
- Made research more accessible (less tuning expertise needed)
- Foundation for modern optimizer development

## Common Confusion

- **Adam vs. AdamW**: Adam is the original algorithm; AdamW changes only how weight decay is applied. When a modern paper says "Adam," it often means AdamW in the code.
- **Adaptive learning rate does not mean "no learning rate."** You still choose $\alpha$; Adam only rescales it per parameter.
- **Momentum here is not classical momentum.** Adam's $m_t$ is an exponential moving average of gradients, closely related to but not identical to SGD-with-momentum.
- **Optimizer vs. loss function**: Adam does not change what you optimize (the loss), only how you take steps toward minimizing it.

## Where To Go Next

- Read [Backpropagation](https://aipedia.org/backpropagation) for where the gradients Adam consumes actually come from.
- Read [Batch Normalization](https://aipedia.org/batch-normalization) and [Dropout](https://aipedia.org/dropout) for the other standard training tricks used alongside Adam.
- Read [Transformer](https://aipedia.org/transformer) to see the architecture that made AdamW plus warmup the standard recipe.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) for how training choices play out at very large scale.


# Generative Adversarial Networks

> Two neural networks compete to generate realistic data

- Type: Concept
- By: Goodfellow et al.
- Year: 2014
- Topics: Architecture, Deep learning, Generative, Vision
- Page: https://aipedia.org/gan

## Resources

- [Generative Adversarial Nets](https://arxiv.org/abs/1406.2661): Paper, Goodfellow et al., 2014
- [Unsupervised Representation Learning with Deep Convolutional GANs (DCGAN)](https://arxiv.org/abs/1511.06434): Paper, Radford et al., 2015
- [Wasserstein GAN](https://arxiv.org/abs/1701.07875): Paper, Arjovsky et al., 2017
- [A Style-Based Generator Architecture for GANs (StyleGAN)](https://arxiv.org/abs/1812.04948): Paper, Karras et al., 2018

**GANs** (Generative Adversarial Networks), introduced by Goodfellow et al. in 2014, revolutionized generative modeling through a simple but powerful idea: pit two neural networks against each other in a game. One network learns to create fake data; the other learns to catch fakes. The competition pushes both to improve.

> This page assumes you know how a neural network is trained with a loss and [backpropagation](https://aipedia.org/backpropagation). For other ways to generate data, see [VAE](https://aipedia.org/vae) and [Diffusion Models](https://aipedia.org/diffusion-models).

## Why Students Should Care

- GANs were the dominant approach to image generation for years, and the core idea — adversarial training, where a second network acts as a *learned loss function* — still shows up across deep learning.
- GANs are a rare example of training framed as a **game between two models** rather than minimizing a single fixed loss. That framing is worth understanding on its own.
- Knowing why GANs are hard to train (mode collapse, instability) explains why the field later moved toward [diffusion models](https://aipedia.org/diffusion-models).

## The Counterfeiter and the Detective

Before any math, here is the whole idea as a story:

- A **counterfeiter** (the generator) prints fake money and tries to pass it off as real.
- A **detective** (the discriminator) inspects money and tries to spot the fakes.

Every time the detective catches a fake, the counterfeiter learns what gave it away and improves. Every time a fake slips through, the detective learns to look more carefully. As training progresses, both improve — until the fakes become indistinguishable from real.

## The Core Idea

Two networks compete:
- **Generator (G)**: Creates fake samples from random noise
- **Discriminator (D)**: Outputs the probability that a sample is real

The generator tries to fool the discriminator; the discriminator tries not to be fooled. Written as one objective:

$$
\min_G \max_D \mathbb{E}_{x \sim p_{data}}[\log D(x)] + \mathbb{E}_{z \sim p_z}[\log(1 - D(G(z)))]
$$

You do not need to memorize this equation. The important idea is: **D is trained to maximize this expression (be a good detective), while G is trained to minimize it (fool the detective)**. The first term rewards D for saying "real" on real data; the second rewards D for saying "fake" on generated data — and G wants exactly the opposite.

## Interactive Demo

Watch the generator and discriminator compete:

*Interactive demo: https://aipedia.org/gan*

## Architecture

### Generator
Takes random noise $z$ and transforms it into a sample:

$$
G: z \in \mathbb{R}^{d_z} \rightarrow x \in \mathbb{R}^{d_x}
$$

In plain English: the generator is just a neural network that maps a random vector (say, 100 numbers) to an image (say, 64×64 pixels). For images, it typically uses transposed convolutions to upsample the noise step by step.

### Discriminator
Takes a sample and outputs the probability it is real:

$$
D: x \in \mathbb{R}^{d_x} \rightarrow [0, 1]
$$

This is an ordinary binary classifier. For images, it uses standard convolutions.

## Training Algorithm

Training alternates between the two networks:

```python
for epoch in epochs:
    # Train Discriminator
    real_samples = sample_data(batch_size)
    fake_samples = G(sample_noise(batch_size))

    D_loss = -mean(log(D(real)) + log(1 - D(fake)))
    update(D, D_loss)

    # Train Generator
    fake_samples = G(sample_noise(batch_size))
    G_loss = -mean(log(D(fake)))  # or mean(log(1 - D(fake)))
    update(G, G_loss)
```

Note that G never sees real data directly — it only learns from the discriminator's feedback.

## Challenges

GANs are famously tricky to train. The three classic problems:

### Mode Collapse
The generator finds a few outputs that reliably fool the discriminator and produces only those, ignoring other modes of the data distribution. (Example: a face generator that only ever produces one type of face.)

### Training Instability
A delicate balance is required — if D is too good, G gets no useful gradient; if D is too weak, G doesn't improve. Neither network is minimizing a fixed target, so losses can oscillate rather than steadily decrease.

### Evaluation
GANs give no explicit likelihood, so there is no obvious number to measure progress. Metrics like FID (Fréchet Inception Distance) and IS (Inception Score) were developed to fill this gap.

## GAN Variants

| Variant | Innovation |
|---------|------------|
| **DCGAN** | Convolutional architecture, stable training |
| **WGAN** | Wasserstein distance, improved stability |
| **StyleGAN** | Style-based generator, unprecedented quality |
| **CycleGAN** | Unpaired image-to-image translation |
| **Pix2Pix** | Paired image-to-image translation |
| **BigGAN** | Large-scale, class-conditional generation |
| **ProGAN** | Progressive growing for high resolution |

## The Nash Equilibrium

What happens if training goes perfectly? At convergence, the optimal discriminator is:

$$
D^*(x) = \frac{p_{data}(x)}{p_{data}(x) + p_g(x)}
$$

When the generator's distribution matches the data ($p_g = p_{data}$), this gives $D^*(x) = 0.5$ everywhere — the discriminator can't tell real from fake and is reduced to guessing. That is the ideal endpoint of the game.

## Why GANs Work

1. **Implicit density**: No explicit likelihood computation needed — you only need to *sample*, not to score probabilities
2. **Sharp samples**: The adversarial loss produces crisp outputs (unlike blurry VAE reconstructions)
3. **Flexible architecture**: Works with any differentiable generator/discriminator

## Theoretical Connection

The original GAN objective, at the optimal discriminator, is equivalent to minimizing the Jensen-Shannon divergence between the data and generator distributions:

$$
\min_G JS(p_{data} || p_g)
$$

WGAN instead minimizes the Wasserstein (Earth Mover's) distance, which provides smoother gradients — one reason it trains more stably.

## Historical Impact

GANs enabled:
- **Photorealistic face generation** (ThisPersonDoesNotExist)
- **Image-to-image translation** (edges→photos, day→night)
- **Super-resolution** (enhance low-res images)
- **Art and design** (AI-generated art, fashion)
- **Data augmentation** (synthetic training data)

Though diffusion models now surpass GANs for image generation, the adversarial training concept remains influential.

## Common Confusion

- **"GAN" is the training setup, not a single network.** After training, you typically throw away the discriminator and keep only the generator.
- **The discriminator is not a classifier you deploy** — it is best understood as a *learned loss function* that teaches the generator what "realistic" means.
- **GAN vs. VAE**: a [VAE](https://aipedia.org/vae) has an encoder and optimizes an explicit likelihood bound (ELBO); a GAN has no encoder and no likelihood — it only learns to sample.
- **Falling loss does not mean better samples.** Because two networks are competing, GAN losses oscillate; sample quality must be judged separately (visually or with FID).

## Where To Go Next

- Read [VAE](https://aipedia.org/vae) for the other classic generative model — explicit likelihood instead of an adversarial game.
- Read [Diffusion Models](https://aipedia.org/diffusion-models) to see the approach that overtook GANs for image generation.
- Read [Latent Diffusion](https://aipedia.org/latent-diffusion) for the architecture behind Stable Diffusion, which borrows the "learned decoder" idea.
- Read [Backpropagation](https://aipedia.org/backpropagation) if the gradient-based training loop above felt unfamiliar.


# Batch Normalization

> Normalizing layer inputs to accelerate deep network training

- Type: Concept
- By: Ioffe & Szegedy
- Year: 2015
- Topics: Deep learning, Training, Optimization, Architecture
- Page: https://aipedia.org/batch-normalization

## Resources

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://arxiv.org/abs/1502.03167): Paper, Ioffe & Szegedy, 2015
- [Layer Normalization](https://arxiv.org/abs/1607.06450): Paper, Ba, Kiros & Hinton, 2016
- [Group Normalization](https://arxiv.org/abs/1803.08494): Paper, Wu & He, 2018
- [How Does Batch Normalization Help Optimization?](https://arxiv.org/abs/1805.11604): Paper, Santurkar et al., 2018

**Batch Normalization** (BatchNorm), introduced by Ioffe and Szegedy in 2015, is one of the most important techniques in deep learning. The idea: before passing a layer's outputs onward, rescale them so each feature has roughly zero mean and unit variance across the current mini-batch. This small change enables faster convergence, higher learning rates, and more stable training of deep networks.

> This page covers normalization across the **batch**. Its sibling, [Layer Normalization](https://aipedia.org/layer-normalization), normalizes across the features of a single example and is the default in Transformers. Reading both makes the contrast click.

## Why Students Should Care

- BatchNorm (or a variant of it) appears in nearly every modern architecture; it helped make very deep networks like [ResNet](https://aipedia.org/resnet) trainable.
- It is a classic example of a simple idea with a huge practical payoff — and a debated explanation for why it works.
- The train-vs-inference distinction in BatchNorm is a common source of real-world bugs (`model.eval()` exists largely because of it).

## The Problem: Shifting Inputs

Picture layer 5 of a deep network. Its input is the output of layers 1 through 4 — and those layers' weights change with every training step. So layer 5's input distribution keeps drifting: the "ground moves under its feet" while it tries to learn. The original paper named this **internal covariate shift**.

Networks must constantly adapt to new input distributions, slowing training.

## The Solution: Normalize Each Mini-Batch

BatchNorm's fix: standardize each feature using the statistics of the current mini-batch. For each feature in a layer:

$$
\hat{x}_i = \frac{x_i - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}}
$$

where:
- $\mu_B = \frac{1}{m}\sum_{i=1}^m x_i$ (batch mean)
- $\sigma_B^2 = \frac{1}{m}\sum_{i=1}^m (x_i - \mu_B)^2$ (batch variance)
- $\epsilon$ is a small constant for numerical stability

This is the familiar "subtract the mean, divide by the standard deviation" from statistics — applied per feature, per mini-batch, inside the network.

## Learnable Parameters

Forcing every feature to have zero mean and unit variance would limit what the layer can represent. So BatchNorm adds a learnable scale ($\gamma$) and shift ($\beta$):

$$
y_i = \gamma \hat{x}_i + \beta
$$

The takeaway: **the network normalizes first, then learns whatever scale and offset it actually wants** — including undoing the normalization entirely if that helps.

## Interactive Demo

Visualize how BatchNorm stabilizes activations during training:

*Interactive demo: https://aipedia.org/batch-normalization*

## Where to Apply BatchNorm

```
Without BatchNorm:    Input → Linear → Activation → Linear → ...
With BatchNorm:       Input → Linear → BatchNorm → Activation → Linear → ...
```

Typically applied after the linear transformation but before the activation function.

## Training vs. Inference

Here is the subtle part. At inference time you might process a single example — there is no batch to compute statistics from. So BatchNorm behaves differently in the two modes:

**During training**: Use mini-batch statistics ($\mu_B$, $\sigma_B^2$)

**During inference**: Use running averages computed during training:

$$
\mu_{running} = \alpha \cdot \mu_{running} + (1-\alpha) \cdot \mu_B
$$

This ensures deterministic outputs at inference time. Forgetting to switch modes (in PyTorch, `model.eval()`) is a classic bug.

## Why It Works

The original paper attributed success to reducing internal covariate shift, but later research suggests other factors:

1. **Smoother loss landscape**: BatchNorm makes the optimization surface smoother, allowing larger learning rates
2. **Gradient flow**: Normalization prevents gradients from vanishing or exploding
3. **Regularization**: Mini-batch noise acts as a regularizer

The honest summary: BatchNorm clearly helps, and the *why* is still partly an open research question.

## Benefits

| Benefit | Explanation |
|---------|-------------|
| **Faster training** | 10-14x fewer training steps |
| **Higher learning rates** | Stable training with larger steps |
| **Reduced initialization sensitivity** | Less dependent on weight initialization |
| **Regularization effect** | Reduces need for dropout |

## BatchNorm Variants

The family differs mainly in *which dimension* gets normalized:

| Variant | Normalization Dimension | Use Case |
|---------|------------------------|----------|
| **BatchNorm** | Across batch | CNNs (requires large batches) |
| **LayerNorm** | Across features | Transformers, RNNs |
| **InstanceNorm** | Per sample, per channel | Style transfer |
| **GroupNorm** | Groups of channels | Small batch sizes |

## The Forward Pass

The core computation is only a few lines:

```python
def batch_norm(x, gamma, beta, eps=1e-5):
    # x shape: (batch_size, features)
    mu = x.mean(dim=0)
    var = x.var(dim=0)

    x_norm = (x - mu) / torch.sqrt(var + eps)

    return gamma * x_norm + beta
```

## Limitations

1. **Batch size dependency**: Small batches give noisy statistics
2. **Not suited for RNNs**: Variable sequence lengths complicate batch statistics
3. **Train/test discrepancy**: Different behavior in train vs. inference modes

For transformers and RNNs, [Layer Normalization](https://aipedia.org/layer-normalization) is preferred.

## The Math: Backward Pass

BatchNorm is differentiable, so gradients flow through the normalization during [backpropagation](https://aipedia.org/backpropagation). The gradients for the learnable parameters are simple:

$$
\frac{\partial L}{\partial \gamma} = \sum_i \frac{\partial L}{\partial y_i} \cdot \hat{x}_i
$$

$$
\frac{\partial L}{\partial \beta} = \sum_i \frac{\partial L}{\partial y_i}
$$

The gradient through $\hat{x}$ involves the chain rule through the mean and variance — messier, but your framework handles it automatically.

## Historical Impact

BatchNorm enabled:
- Training of much deeper networks (ResNet's 152 layers)
- Higher learning rates (faster experimentation)
- Reduced hyperparameter sensitivity
- Standard component in nearly all modern architectures

## Common Confusion

- **BatchNorm vs. LayerNorm**: BatchNorm normalizes each feature *across examples in the batch*; LayerNorm normalizes *across the features of one example*. This is the single most important distinction to remember.
- **BatchNorm is not just preprocessing.** Input standardization happens once to the data; BatchNorm happens inside the network, at every normalized layer, on every step, with learnable parameters.
- **Training and inference behave differently.** BatchNorm is one of the few layers where the same input can produce different outputs depending on the mode.
- **"Internal covariate shift" is the historical motivation, not the settled explanation** — later work (Santurkar et al., 2018) argues the benefit comes mainly from a smoother loss landscape.

## Where To Go Next

- Read [Layer Normalization](https://aipedia.org/layer-normalization) for the batch-independent variant used in Transformers.
- Read [ResNet](https://aipedia.org/resnet) for the architecture whose extreme depth BatchNorm helped make trainable.
- Read [Dropout](https://aipedia.org/dropout) for the other classic regularizer, and how the two interact.
- Read [Backpropagation](https://aipedia.org/backpropagation) if the backward-pass section felt too fast.


# Layer Normalization

> Normalizing each example across its features

- Type: Concept
- By: Ba, Kiros & Hinton
- Year: 2016
- Topics: Deep learning, Fundamentals, Training, Transformers
- Page: https://aipedia.org/layer-normalization

## Resources

- [Layer Normalization](https://arxiv.org/abs/1607.06450): Paper, Ba, Kiros & Hinton, 2016
- [On Layer Normalization in the Transformer Architecture](https://arxiv.org/abs/2002.04745): Paper, Xiong et al., 2020
- [Root Mean Square Layer Normalization](https://arxiv.org/abs/1910.07467): Paper, Zhang & Sennrich, 2019

**Layer Normalization (LayerNorm)** rescales the features inside a single example so they have a more stable distribution. In practice, it helps deep models train more reliably, especially Transformers.

> Read [Batch Normalization](https://aipedia.org/batch-normalization) first if you want the easiest comparison. This page focuses on why LayerNorm became the default in Transformer-style models.

## A Small Example

Suppose one token embedding has four features:

`[2, 10, -4, 8]`

LayerNorm computes the mean and variance of those four numbers, normalizes them, then applies learned scale and shift parameters. The important point is that **the normalization happens within that one example**, not across the batch.

## BatchNorm vs LayerNorm

**BatchNorm** normalizes a feature using statistics collected across different examples in the batch.

**LayerNorm** normalizes across the features of one example at a time.

That difference is why LayerNorm works well when:

- batch size is small
- sequence lengths vary
- you are generating one token at a time

## The Formula

For an input $x \in \mathbb{R}^D$:

$$
\mu = \frac{1}{D}\sum_{d=1}^{D} x_d, \quad \sigma^2 = \frac{1}{D}\sum_{d=1}^{D} (x_d - \mu)^2
$$

$$
\hat{x} = \frac{x - \mu}{\sqrt{\sigma^2 + \epsilon}}, \quad y = \gamma \odot \hat{x} + \beta
$$

where $\gamma$ and $\beta$ are learnable parameters that let the model choose the final scale and offset.

## Interactive Visualization

Compare BatchNorm and LayerNorm normalization patterns:

*Interactive demo: https://aipedia.org/layer-normalization*

## Why Transformers Use It

Transformers rely on LayerNorm because it is:

1. **Batch-independent**: each sequence can be normalized on its own
2. **Stable at inference time**: train and test use the same basic computation
3. **Friendly to autoregressive generation**: it still works when batch size is 1

## Pre-Norm vs Post-Norm

Two common block layouts are:

**Post-Norm**:

$$
x' = \text{LayerNorm}(x + \text{Sublayer}(x))
$$

**Pre-Norm**:

$$
x' = x + \text{Sublayer}(\text{LayerNorm}(x))
$$

Modern large language models often prefer **pre-norm** because gradients tend to behave better in deep networks.

## RMSNorm

**RMSNorm** is a close relative that skips mean-centering:

$$
\hat{x} = \frac{x}{\sqrt{\frac{1}{D}\sum_d x_d^2 + \epsilon}} \cdot \gamma
$$

It is a simpler normalization choice used in many modern LLMs.

## Common Confusion

- LayerNorm does **not** normalize across the batch
- It does **not** remove the need for residual connections
- It helps optimization, but it is not a substitute for good architecture design

## What To Remember

- LayerNorm normalizes each example across its features
- That makes it a good fit for sequence models and Transformers
- Pre-norm and RMSNorm are the most relevant follow-on ideas for modern LLMs


# Proximal Policy Optimization (PPO)

> A stable, sample-efficient policy gradient algorithm for reinforcement learning

- Type: Concept
- By: Schulman et al.
- Year: 2017
- Topics: Deep learning, Reinforcement learning, Policy gradients, Optimization
- Page: https://aipedia.org/ppo

## Resources

- [Proximal Policy Optimization Algorithms](https://arxiv.org/abs/1707.06347): Paper, Schulman et al., 2017
- [openai/baselines](https://github.com/openai/baselines): Code, Reference implementations
- [Proximal Policy Optimization](https://spinningup.openai.com/en/latest/algorithms/ppo.html): Docs, OpenAI Spinning Up
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://arxiv.org/abs/1506.02438): Paper, Schulman et al., 2015
- [Trust Region Policy Optimization](https://arxiv.org/abs/1502.05477): Paper, Schulman et al., 2015

**Proximal Policy Optimization (PPO)** is the most widely used deep reinforcement learning algorithm. Its core idea is simple: improve the policy a little at a time, and clip any update that would change it too much. That one trick makes it stronger, simpler, and more stable than prior methods like TRPO.

> This page assumes you know what a policy gradient is. If not, read [Policy Gradient](https://aipedia.org/policy-gradient) first, and [Reinforcement Learning](https://aipedia.org/reinforcement-learning) before that.

## Why Students Should Care

- PPO is the default algorithm in most RL libraries and papers — if a project "uses RL", it probably uses PPO.
- It is the classic optimizer behind [RLHF](https://aipedia.org/rlhf), the technique used to align chat assistants.
- The clipping idea is a clean example of a broader lesson: in deep learning, *how big your update steps are* matters as much as their direction.

## The Problem, in Plain English

Policy gradient methods learn by nudging the policy toward actions that worked. The trouble is choosing the nudge size:

- Too large an update → the policy can collapse, and because the policy also *collects the data*, bad updates poison future learning
- Too small an update → learning crawls

Earlier fixes (like TRPO) enforced a "trust region" with heavy math. PPO gets a similar effect with one clipped objective you can implement in a few lines.

## The PPO-Clip Objective

$$
L^{CLIP}(\theta) = \mathbb{E}_t \left[ \min\left( r_t(\theta) \hat{A}_t, \text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_t \right) \right]
$$

where:

- $r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}$ is the **probability ratio**: how much more (or less) likely the new policy is to take the action than the old policy was
- $\hat{A}_t$ is the **advantage** estimate: was this action better or worse than average?
- $\epsilon$ is the clip range (typically 0.1-0.2)

You do not need to memorize the formula. The important idea is: **increase the probability of good actions and decrease the probability of bad ones, but never let a single update shift any action's probability by more than a factor of about $1 \pm \epsilon$.**

## How Clipping Works

The clip function pins the ratio to a narrow band around 1:

$$
\text{clip}(r, 1-\epsilon, 1+\epsilon) = \begin{cases}
1-\epsilon & \text{if } r < 1-\epsilon \\
r & \text{if } 1-\epsilon \leq r \leq 1+\epsilon \\
1+\epsilon & \text{if } r > 1+\epsilon
\end{cases}
$$

Taking the minimum of the clipped and unclipped terms makes the constraint one-sided in exactly the right way:

- If $\hat{A} > 0$ (the action was good): don't increase $r$ beyond $1+\epsilon$ — no runaway enthusiasm
- If $\hat{A} < 0$ (the action was bad): don't decrease $r$ below $1-\epsilon$ — no panic abandonment

Once the ratio leaves the band, the gradient through that sample becomes zero, so the optimizer simply stops pushing in that direction.

## Interactive Visualization

See how the clipping mechanism constrains policy updates:

*Interactive demo: https://aipedia.org/ppo*

## Advantage Estimation

PPO needs to know whether each action was better than expected. It typically uses **Generalized Advantage Estimation (GAE)**, which blends short-horizon and long-horizon estimates:

$$
\hat{A}_t = \sum_{l=0}^{\infty} (\gamma \lambda)^l \delta_{t+l}
$$

where $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ is the TD error — the one-step "surprise" relative to the value function's prediction.

The $\lambda$ parameter trades off bias vs variance: small $\lambda$ trusts the value function more (lower variance, more bias), large $\lambda$ trusts observed rewards more.

## Full Algorithm

```python
for iteration in range(num_iterations):
    # Collect trajectories with current policy
    trajectories = collect_rollouts(policy, env)
    
    # Compute advantages
    advantages = compute_gae(trajectories, value_fn)
    
    # Multiple epochs of updates
    for epoch in range(num_epochs):
        for batch in trajectories.batches():
            # PPO update
            loss = ppo_clip_loss(batch, advantages)
            optimizer.step(loss)
```

Note the inner loop: PPO reuses each batch of experience for **several epochs** of gradient updates. That is exactly what clipping makes safe — without it, repeated updates on the same data would push the policy too far from the one that collected it.

## Hyperparameters

| Parameter | Typical Value | Effect |
|-----------|---------------|--------|
| $\epsilon$ (clip) | 0.1-0.2 | Update constraint |
| $\gamma$ (discount) | 0.99 | Future reward weighting |
| $\lambda$ (GAE) | 0.95 | Advantage bias-variance |
| Epochs per update | 3-10 | Sample efficiency |
| Batch size | 32-4096 | Gradient stability |

## Why PPO is Popular

1. **Simple**: Easier to implement than TRPO
2. **Stable**: Clipping prevents catastrophic updates
3. **Sample efficient**: Multiple epochs per rollout
4. **General**: Works on continuous and discrete actions
5. **Scalable**: Parallelizes well across workers

## Applications

PPO powers:

- **RLHF**: Aligning language models (ChatGPT, Claude) — see [RLHF](https://aipedia.org/rlhf)
- **Game AI**: OpenAI Five, DOTA 2
- **Robotics**: Manipulation, locomotion
- **Autonomous driving**: Decision making

## Common Confusion

- **PPO vs. policy gradient**: PPO *is* a policy gradient method. The clipped objective is a safer stand-in for the vanilla policy gradient loss — see [Policy Gradient](https://aipedia.org/policy-gradient) for the base method.
- **PPO vs. TRPO**: both limit how far the policy moves per update. TRPO enforces a hard KL-divergence constraint with second-order optimization; PPO approximates the same effect with first-order clipping.
- **Clipping rewards vs. clipping the ratio**: PPO clips the *probability ratio* between new and old policies, not the rewards themselves.
- **PPO vs. [DQN](https://aipedia.org/dqn)**: PPO learns a policy directly (policy-based); DQN learns action values and derives the policy from them (value-based).

## Where To Go Next

- Read [Policy Gradient](https://aipedia.org/policy-gradient) for the foundation PPO is built on, including REINFORCE and actor-critic.
- Read [RLHF](https://aipedia.org/rlhf) to see PPO's most famous application: fine-tuning language models from human preferences.
- Read [DQN](https://aipedia.org/dqn) for the contrasting value-based approach.
- Read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) if you want the full MDP background.


# RLHF: Reinforcement Learning from Human Feedback

> Teaching language models to prefer responses that people rank higher

- Type: Concept
- By: Christiano et al.
- Year: 2017
- Topics: Deep learning, NLP, Alignment, Reinforcement learning, Foundation models
- Page: https://aipedia.org/rlhf

## Resources

- [Deep reinforcement learning from human preferences](https://arxiv.org/abs/1706.03741): Paper, Christiano et al., 2017
- [huggingface/trl](https://github.com/huggingface/trl): Code, RLHF training library
- [Illustrating Reinforcement Learning from Human Feedback](https://huggingface.co/blog/rlhf): Article, Hugging Face
- [Learning to summarize from human feedback](https://arxiv.org/abs/2009.01325): Paper, Stiennon et al., 2020
- [Training language models to follow instructions with human feedback](https://arxiv.org/abs/2203.02155): Paper, Ouyang et al., 2022 (InstructGPT)

**RLHF** is a training pipeline for making language models more helpful. The base model already knows how to predict text. RLHF adds a second question: **which responses do humans actually prefer?**

> Read [Pre-training](https://aipedia.org/pre-training) and [Reinforcement Learning](https://aipedia.org/reinforcement-learning) first if you are new to the setup. This page covers the classic RLHF pipeline; many modern systems also use related preference-optimization methods.

## A Concrete Example

Suppose a user asks:

`How do I prepare for my calculus exam?`

The model might generate three answers:

- one vague answer
- one correct but overly long answer
- one clear, accurate, and well-structured answer

Humans rank those responses. RLHF trains the model to produce more of the third kind.

## Why Pre-training Is Not Enough

A pre-trained language model is optimized for next-token prediction:

$$
\mathcal{L}_{\text{pretrain}} = -\sum_i \log P(x_i | x_{<i})
$$

That objective makes the model fluent, but fluency is not the same as being helpful, safe, or well-aligned with user intent.

## The Three-Stage Pipeline

### 1. Supervised Fine-Tuning (SFT)

Start with high-quality prompt-response examples written by humans or curated by trainers.

The model is fine-tuned to imitate those examples:

$$
\mathcal{L}_{\text{SFT}} = -\sum_i \log P_\theta(y_i | x, y_{<i})
$$

This gives the model a reasonable baseline style.

### 2. Reward Model Training

Next, humans compare multiple answers to the same prompt. A separate model learns to score responses so that preferred ones get higher scores.

$$
P(y_1 \succ y_2 | x) = \sigma(R_\phi(x, y_1) - R_\phi(x, y_2))
$$

You do not need the formula to follow the idea. It just says: **the reward model should assign a higher score to the answer humans liked more**.

### 3. RL Fine-Tuning

Finally, use reinforcement learning to make the policy produce higher-scoring answers while staying close to the supervised model:

$$
\mathcal{L}_{\text{RLHF}} = \mathbb{E}_{x \sim D, y \sim \pi_\theta}[R_\phi(x, y)] - \beta \cdot D_{KL}(\pi_\theta || \pi_{\text{SFT}})
$$

In plain English:

- maximize the reward model score
- but do not drift too far from the sensible SFT policy

The second term is a **KL penalty**. It acts like a leash that keeps the model from chasing weird high-reward hacks.

## Why the KL Penalty Matters

Without a constraint, the policy can learn to exploit mistakes in the reward model. That is called **reward hacking**.

The KL term reduces that risk by asking the updated model to stay reasonably close to the distribution of answers it produced after supervised fine-tuning.

## Interactive Visualization

Explore the RLHF pipeline: SFT, reward modeling, and PPO optimization:

*Interactive demo: https://aipedia.org/rlhf*

## Where PPO Fits In

Classic RLHF often uses **PPO** for the reinforcement learning stage. PPO is popular because it improves the policy gradually instead of allowing destructive jumps.

If you want the RL details, read [PPO](https://aipedia.org/ppo) after this page.

## Practical Challenges

| Challenge | Why it happens | Typical fix |
|-----------|----------------|-------------|
| Reward hacking | The policy exploits reward model shortcuts | KL penalty, better reward data |
| Label noise | Humans do not always agree | Multiple raters, calibration |
| High cost | Preference data is expensive | Better collection tools, active sampling |
| Distribution shift | The model changes during training | Refresh or expand feedback data |

## Where RLHF Shows Up

- Chat assistants
- Instruction-following models
- Safety tuning
- Preference-aware generation systems

## What To Remember

- Pre-training teaches language patterns
- RLHF teaches preference-aware behavior
- The classic pipeline is **SFT -> reward model -> RL**
- The hardest part is not optimization alone; it is getting reliable human preference data


# Transformer

> Self-attention models that process sequences in parallel

- Type: Concept
- By: Vaswani et al.
- Year: 2017
- Topics: Architecture, Attention, Deep learning, NLP, Transformers
- Page: https://aipedia.org/transformer

## Resources

- [Attention Is All You Need](https://arxiv.org/abs/1706.03762): Paper, Vaswani et al., 2017
- [The Illustrated Transformer](https://jalammar.github.io/illustrated-transformer/): Article, Jay Alammar
- [Let's build GPT: from scratch, in code, spelled out](https://www.youtube.com/watch?v=kCc8FmEb1nY): Video, Andrej Karpathy
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://arxiv.org/abs/1810.04805): Paper, Devlin et al., 2018
- [Improving Language Understanding by Generative Pre-Training](https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf): Paper, Radford et al., 2018

The **Transformer** is a neural network architecture for working with sequences such as text, code, and audio. Its key idea is simple: instead of reading tokens one at a time like an RNN, let every token look at the other relevant tokens and decide what matters most.

> If this page feels too fast, read [Sequence to Sequence](https://aipedia.org/seq2seq) and [Bahdanau Attention](https://aipedia.org/bahdanau-attention) first. This page teaches the **general architecture**. For the original 2017 paper, see [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need).

## Why Students Should Care

Transformers are the foundation of:

- **GPT-style models** for generation
- **BERT-style models** for understanding
- **Vision Transformers** for images
- Most modern LLMs

If you understand the Transformer, you understand the core design behind much of modern AI.

## A Quick Example

Take the sentence:

`The animal did not cross the street because it was tired.`

To understand what **it** refers to, the model should pay more attention to **animal** than to **street**. A Transformer does exactly this: it learns attention weights that tell each token which other tokens to focus on.

## Core Attention

In plain English:

- **Query (Q)**: what the current token is looking for
- **Key (K)**: what each other token can offer
- **Value (V)**: the information each token carries

Each token compares its query to the keys of the other tokens. Higher matches get higher attention weights, and those weights are used to combine the values.

$$
\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V
$$

You do not need to memorize the equation. The important idea is: **compare, weight, combine**.

## Multi-Head Attention

A single attention pattern is often too limited. So Transformers use several attention heads in parallel:

$$
\text{MultiHead}(Q,K,V) = \text{Concat}(head_1,\dots,head_h)W^O
$$

Different heads can specialize. One head may focus on nearby words, another on subject-verb agreement, and another on longer-range references.

## Positional Encoding

Attention alone does not know word order. Without extra information, `dog bites man` and `man bites dog` would look like the same bag of tokens.

Transformers fix this by adding a position signal to each token embedding:

$$
PE_{(pos,2i)} = \sin\left(\frac{pos}{10000^{2i/d}}\right), \quad
PE_{(pos,2i+1)} = \cos\left(\frac{pos}{10000^{2i/d}}\right)
$$

The equation is less important than the purpose: **tell the model where each token sits in the sequence**.

## Interactive Demo

Explore multi-head attention, token flow, and positional encodings below:

*Interactive demo: https://aipedia.org/transformer*

## The Architecture

The original Transformer had two parts:

- **Encoder**: reads the input and builds contextual representations
- **Decoder**: generates the output one token at a time

At a high level:

- Encoder block = self-attention -> add and norm -> feed-forward network
- Decoder block = masked self-attention -> cross-attention -> feed-forward network

Many modern LLMs use only the **decoder** side because text generation is the main task.

## Why It Beat RNNs

RNNs must process tokens one after another. Transformers can process all tokens in parallel.

| Property | RNN | Transformer |
|----------|-----|-------------|
| Sequential ops | O(n) | O(1) |
| Max path length | O(n) | O(1) |
| Parallelizable | No | Yes |

That made Transformers faster to train and better at connecting distant parts of a sequence.

## Common Confusion

- **Transformer** is the architecture.
- **Attention Is All You Need** is the paper that introduced it.
- **Self-attention** is one mechanism inside the architecture, not the whole model.

## Where To Go Next

- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for the original paper and results
- Read [BERT](https://aipedia.org/bert) for encoder-only Transformers
- Read [GPT](https://aipedia.org/gpt) for decoder-only Transformers
- Read [Vision Transformer](https://aipedia.org/vision-transformer) for image applications


# Diffusion Models

> Generative models that learn to denoise, enabling high-quality image and video synthesis

- Type: Concept
- By: Ho, Jain & Abbeel
- Year: 2020
- Topics: Deep learning, Generative, Vision, Diffusion, Foundation models
- Page: https://aipedia.org/diffusion-models

## Resources

- [Denoising Diffusion Probabilistic Models](https://arxiv.org/abs/2006.11239): Paper, Ho, Jain & Abbeel, 2020
- [hojonathanho/diffusion](https://github.com/hojonathanho/diffusion): Code, Official DDPM code
- [What are Diffusion Models?](https://lilianweng.github.io/posts/2021-07-11-diffusion-models/): Article, Lilian Weng, 2021
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://arxiv.org/abs/1503.03585): Paper, Sohl-Dickstein et al., 2015
- [Classifier-Free Diffusion Guidance](https://arxiv.org/abs/2207.12598): Paper, Ho & Salimans, 2022

**Diffusion Models** generate data by learning to reverse a gradual noising process. Starting from pure noise, they iteratively denoise to produce remarkably high-quality images, videos, and audio.

> Helpful background: [VAE](https://aipedia.org/vae) and [GAN](https://aipedia.org/gan) show the earlier approaches to generation. This page covers diffusion in pixel space; [Latent Diffusion](https://aipedia.org/latent-diffusion) covers the efficiency trick behind Stable Diffusion.

## Why Students Should Care

- Diffusion is the engine behind modern image and video generators — Stable Diffusion, DALL-E 2, and Imagen are all diffusion models.
- The training objective is astonishingly simple (a mean-squared error on noise), which is why diffusion trains stably where [GANs](https://aipedia.org/gan) struggle.
- The same "destroy data, learn to rebuild it" recipe generalizes beyond images to audio, video, and molecules.

## The Idea in One Paragraph

Take a photo and add a tiny amount of static. Add a little more. Repeat a thousand times and you end up with pure noise — the image is destroyed. Each single step of that destruction is easy to describe. The diffusion insight: train a network to *undo one small step* of noising. If it can do that at every noise level, you can start from pure random noise and denoise step by step until an image appears — generating data from nothing.

## Core Idea

The process has two phases:

**Forward process** (fixed, no learning): Gradually add Gaussian noise to data over $T$ steps:

$$
q(x_t | x_{t-1}) = \mathcal{N}(x_t; \sqrt{1-\beta_t} x_{t-1}, \beta_t I)
$$

**Reverse process** (learned): Denoise step by step:

$$
p_\theta(x_{t-1} | x_t) = \mathcal{N}(x_{t-1}; \mu_\theta(x_t, t), \Sigma_\theta(x_t, t))
$$

The takeaway: the forward direction is a fixed recipe for corrupting data; only the reverse direction — the denoiser — has parameters to train.

## The Closed-Form Forward Process

A convenient property: you never have to noise an image step by step during training. We can jump directly to any timestep $t$:

$$
q(x_t | x_0) = \mathcal{N}(x_t; \sqrt{\bar{\alpha}_t} x_0, (1-\bar{\alpha}_t) I)
$$

where $\bar{\alpha}_t = \prod_{s=1}^{t} (1-\beta_s)$.

This means: $x_t = \sqrt{\bar{\alpha}_t} x_0 + \sqrt{1-\bar{\alpha}_t} \epsilon$, where $\epsilon \sim \mathcal{N}(0, I)$.

In plain English: an image at noise level $t$ is just a weighted blend of the clean image and one fresh draw of Gaussian noise. That makes training samples cheap to produce.

## Training Objective

Instead of predicting the denoised mean $\mu_\theta$ directly, it works better to predict the noise $\epsilon$ that was added:

$$
\mathcal{L}_{\text{simple}} = \mathbb{E}_{t, x_0, \epsilon}\left[ \| \epsilon - \epsilon_\theta(x_t, t) \|^2 \right]
$$

The whole training loop is: sample a random timestep $t$, noise the image, ask the network "what noise did I add?", and penalize the squared error. Remarkably simple yet effective — no adversarial game, no delicate balance, just regression.

## Sampling (Inference)

To generate, start with pure noise $x_T \sim \mathcal{N}(0, I)$, then repeatedly take one denoising step:

$$
x_{t-1} = \frac{1}{\sqrt{\alpha_t}}\left(x_t - \frac{\beta_t}{\sqrt{1-\bar{\alpha}_t}} \epsilon_\theta(x_t, t)\right) + \sigma_t z
$$

where $z \sim \mathcal{N}(0, I)$ and $\sigma_t$ controls stochasticity.

You do not need to memorize this formula. The important idea is: **each step subtracts the network's noise estimate (scaled appropriately) and optionally re-injects a little fresh randomness**, gradually turning noise into data.

## Classifier-Free Guidance

How does a text prompt steer generation? Train the model both with and without conditioning, then at sampling time interpolate between the two predictions:

$$
\tilde{\epsilon}_\theta(x_t, t, c) = \epsilon_\theta(x_t, t, \emptyset) + w \cdot (\epsilon_\theta(x_t, t, c) - \epsilon_\theta(x_t, t, \emptyset))
$$

where $w > 1$ strengthens conditioning (e.g., on text prompts). Intuitively: figure out which direction the prompt pulls the denoising, then exaggerate that direction. This is the "guidance scale" knob in image generators.

## Interactive Visualization

Watch the diffusion process in action — forward noising and reverse denoising:

*Interactive demo: https://aipedia.org/diffusion-models*

## Architecture: U-Net

The denoising network is typically a U-Net with:
- **Time embedding**: Sinusoidal encoding of $t$, so one network can handle every noise level
- **Attention layers**: Self-attention and cross-attention (for conditioning on text or labels)
- **Skip connections**: Preserve spatial information between the downsampling and upsampling paths

## Key Models

| Model | Innovation |
|-------|------------|
| DDPM | Foundational formulation |
| DDIM | Deterministic sampling, fewer steps |
| Stable Diffusion | Latent space diffusion |
| DALL-E 2 | CLIP guidance |
| Imagen | Large language model conditioning |

## Why Diffusion Works

Unlike GANs (adversarial, unstable) or VAEs (blurry), diffusion models:
1. Have stable training (simple MSE loss)
2. Produce high-fidelity samples
3. Enable controllable generation
4. Scale effectively with compute

## Common Confusion

- **The forward process is not learned.** Only the reverse (denoising) network has trainable parameters; the noising schedule is fixed in advance.
- **The network predicts the *noise*, not the finished image** — the clean image emerges only after many denoising steps.
- **Diffusion vs. latent diffusion**: this page describes diffusion directly on pixels; [latent diffusion](https://aipedia.org/latent-diffusion) first compresses images with a [VAE](https://aipedia.org/vae) and diffuses in that smaller space.
- **Training steps vs. sampling steps**: training picks one random timestep per example, but generation walks through many steps — which is why samplers like DDIM that cut the step count matter so much in practice.

## Where To Go Next

- Read [Latent Diffusion](https://aipedia.org/latent-diffusion) to see how Stable Diffusion makes this process affordable.
- Read [VAE](https://aipedia.org/vae) and [GAN](https://aipedia.org/gan) for the generative models diffusion is usually compared against.
- Read [CLIP](https://aipedia.org/clip) to understand the text encoders used for conditioning and guidance.
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for the attention layers inside the U-Net.


# In-Context Learning

> How large language models learn from examples in the prompt without weight updates

- Type: Concept
- By: Brown et al.
- Year: 2020
- Topics: Deep learning, NLP, Language models, Emergent abilities, Foundation models
- Page: https://aipedia.org/in-context-learning

## Resources

- [Language Models are Few-Shot Learners](https://arxiv.org/abs/2005.14165): Paper, Brown et al., 2020
- [Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?](https://arxiv.org/abs/2202.12837): Paper, Min et al., 2022
- [In-context Learning and Induction Heads](https://arxiv.org/abs/2209.11895): Paper, Olsson et al., 2022

**In-Context Learning (ICL)** is the ability of large language models to pick up a new task from a few examples written directly in the prompt — with no gradient updates and no fine-tuning. You show the model what you want, and it does it.

> If you are unsure how language models are trained in the first place, read [Pre-training](https://aipedia.org/pre-training) and [GPT](https://aipedia.org/gpt) first. This page is about what a *frozen* model can do at inference time.

## Why Students Should Care

- ICL is the reason prompting works at all. Every "few-shot prompt" you write relies on it.
- It broke a core assumption of machine learning: that learning a new task requires updating weights.
- It is the foundation for [Chain-of-Thought](https://aipedia.org/chain-of-thought) prompting and most practical LLM usage.

## The Phenomenon

Give the model a few input-output examples, and it generalizes to a new input:

```
Input: "The movie was terrible" → Sentiment: negative
Input: "I loved every minute" → Sentiment: positive
Input: "It was a waste of time" → Sentiment:
```

The model completes with "negative" — having learned the task from context alone. Nobody trained it on this exact format; it inferred the pattern from two examples.

## Why It's Surprising

Traditional machine learning requires:

1. Collect labeled data
2. Define a loss function
3. Optimize weights via gradient descent (see [Backpropagation](https://aipedia.org/backpropagation))

ICL skips all of this. The model's weights remain frozen; "learning" happens through attention over the prompt. The examples never change the model — they only change what the model conditions on.

## Formal Framework

Here is the same idea in notation. Let $x_1, y_1, \ldots, x_k, y_k$ be demonstration examples and $x_{test}$ be a new input. The model computes:

$$
P(y_{test} | x_1, y_1, \ldots, x_k, y_k, x_{test})
$$

You do not need to memorize this. It just says: **the model predicts the next output given everything in the prompt — the demonstrations create a task pattern that the model conditions on.**

## How Many Examples?

| Setting | Examples | Use Case |
|---------|----------|----------|
| Zero-shot | 0 | Task described in natural language |
| One-shot | 1 | Single example + new input |
| Few-shot | 2-32 | Multiple examples |

More examples generally improve accuracy, but with diminishing returns.

## Interactive Visualization

See how adding examples affects model predictions:

*Interactive demo: https://aipedia.org/in-context-learning*

## What Makes ICL Work?

Nobody fully knows — this is an active research question. Several hypotheses:

1. **Task Recognition**: the model recognizes the task from the examples and retrieves behavior it already learned during pre-training
2. **Implicit Fine-Tuning**: attention over the demonstrations acts like a form of gradient descent, without touching the weights
3. **Bayesian Inference**: the model infers which task distribution the demonstrations came from
4. **Induction Heads**: specific attention patterns inside the [Transformer](https://aipedia.org/transformer) copy patterns from earlier in the context

These are not mutually exclusive; ICL may be all of them at once, in different situations.

## Emergent Ability

ICL appears only at scale:

- Small models: cannot do ICL effectively
- GPT-3 (175B): strong ICL ability emerges
- Larger models: increasingly robust ICL

This "phase transition" makes ICL an **emergent capability** — you cannot see it coming by studying small models. See [Scaling Laws](https://aipedia.org/scaling-laws) for the broader story of what scale buys you.

## Best Practices

| Practice | Effect |
|----------|--------|
| Diverse examples | Better generalization |
| Consistent format | Clearer task signal |
| Similar examples to test | Improved accuracy |
| Clear separators | Reduces confusion |

## Limitations

- **Context window**: limited by maximum sequence length — every demonstration costs tokens
- **Order sensitivity**: performance can vary with example ordering
- **Recency bias**: the model may weight recent examples more heavily
- **Task complexity**: struggles with multi-step reasoning on its own — that is where [Chain-of-Thought](https://aipedia.org/chain-of-thought) comes in

## Common Confusion

- **ICL vs. fine-tuning**: fine-tuning updates the model's weights with gradient descent; ICL leaves the weights frozen and only changes the prompt. "Learning" in ICL is conditioning, not training.
- **ICL vs. Chain-of-Thought**: ICL is the general ability to learn from in-prompt examples. [Chain-of-Thought](https://aipedia.org/chain-of-thought) is a specific style of examples that include reasoning steps.
- **Zero-shot is still ICL-adjacent**: even with zero examples, describing a task in plain language and getting correct behavior relies on the same conditioning machinery.

## Where To Go Next

- Read [Chain-of-Thought](https://aipedia.org/chain-of-thought) for the prompting technique that fixes ICL's weakness on multi-step reasoning.
- Read [GPT](https://aipedia.org/gpt) for the paper that made few-shot in-context learning famous.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) to see why abilities like ICL show up only in large models.
- Read [Transformer](https://aipedia.org/transformer) and [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) to understand the attention mechanism that makes conditioning on demonstrations possible.


# Chain-of-Thought Prompting

> Eliciting step-by-step reasoning in language models for complex problem solving

- Type: Concept
- By: Wei et al.
- Year: 2022
- Topics: Deep learning, NLP, Language models, Reasoning, Prompting
- Page: https://aipedia.org/chain-of-thought

## Resources

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://arxiv.org/abs/2201.11903): Paper, Wei et al., 2022
- [Large Language Models are Zero-Shot Reasoners](https://arxiv.org/abs/2205.11916): Paper, Kojima et al., 2022
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://arxiv.org/abs/2203.11171): Paper, Wang et al., 2022

**Chain-of-Thought (CoT) Prompting** is a simple trick that dramatically improves language model performance on reasoning tasks: instead of asking for the answer directly, you ask the model to show its work — writing out intermediate steps before the final answer.

> If you are new to prompting language models, read [In-Context Learning](https://aipedia.org/in-context-learning) first. CoT builds directly on the idea of putting examples in the prompt.

## Why Students Should Care

- CoT is one of the cheapest ways to make a model better at math, logic, and multi-step problems — no training required, just a different prompt.
- It is the ancestor of modern "reasoning models" that generate long internal thoughts before answering.
- It is a clear example of an **emergent ability**: a behavior that appears only when models get large enough.

## The Problem

Ask a model a multi-step question directly, and it often guesses:

```
Q: Roger has 5 tennis balls. He buys 2 cans of 3 balls each. How many does he have?
A: 11 ✗ (LLM might output wrong answer directly)
```

The model has to compress a whole calculation into a single predicted token. That is a lot to ask.

## The Solution: Show Your Work

CoT prompting includes the reasoning steps, the way a student would write them on an exam:

```
Q: Roger has 5 tennis balls. He buys 2 cans of 3 balls each. How many does he have?
A: Roger starts with 5 balls. 2 cans × 3 balls = 6 balls. 5 + 6 = 11 balls. ✓
```

The model now produces the intermediate arithmetic *before* the answer, and the answer improves.

## Why It Works

By generating intermediate steps, the model:

1. **Decomposes** complex problems into simpler sub-problems
2. **Maintains state** through the reasoning process (earlier steps stay visible in the context)
3. **Reduces error** by checking each step
4. **Allocates compute** proportional to problem difficulty — harder problems get more tokens, and more tokens means more computation

## Two Approaches

### Few-Shot CoT

Give the model worked examples that include reasoning chains, then ask your real question:

$$
\text{Prompt} = [(x_1, r_1, y_1), \ldots, (x_k, r_k, y_k), x_{test}]
$$

where each $x_i$ is a question, $r_i$ is the written-out reasoning chain, and $y_i$ is the answer.

You do not need to memorize the notation. The idea is: **the prompt contains a few solved problems with their reasoning, and the model imitates that pattern on the new problem.**

### Zero-Shot CoT

Even simpler — no examples at all. Just append "Let's think step by step":

```
Q: [problem]
A: Let's think step by step.
```

This single phrase unlocks reasoning in large models.

## Interactive Visualization

Compare standard vs chain-of-thought prompting:

*Interactive demo: https://aipedia.org/chain-of-thought*

## Performance Gains

The improvements are not subtle:

| Task | Standard | Chain-of-Thought |
|------|----------|------------------|
| GSM8K (math) | 18% | 57% |
| MultiArith | 33% | 93% |
| StrategyQA | 65% | 73% |

*Results for PaLM 540B*

## Emergent Ability

CoT benefits appear mainly at scale:

$$
\text{Accuracy gain} \propto \log(\text{model size})
$$

Small models may produce incoherent chains; large models generate meaningful reasoning. In other words, CoT is not a trick you can use to rescue a tiny model — the underlying capability has to be there first. See [Scaling Laws](https://aipedia.org/scaling-laws) for why model size matters so much.

## Self-Consistency

You can improve further by sampling several different reasoning chains and letting them vote:

$$
\hat{y} = \arg\max_y \sum_{i=1}^{n} \mathbf{1}[y_i = y]
$$

In plain English: generate $n$ reasoning paths, extract the final answer from each, and take the majority vote. Different chains make different mistakes, so the vote is more reliable than any single chain.

## Variants

| Method | Key Idea |
|--------|----------|
| CoT | Show reasoning steps |
| Zero-shot CoT | "Let's think step by step" |
| Self-Consistency | Sample multiple chains, vote |
| Tree of Thoughts | Explore branching reasoning paths |
| ReAct | Interleave reasoning and actions |

## When to Use CoT

**Effective for:**
- Math word problems
- Multi-step reasoning
- Logical deduction
- Code generation

**Less helpful for:**
- Simple factual questions
- Single-step tasks
- Creative writing

## Common Confusion

- **CoT vs. in-context learning**: [In-context learning](https://aipedia.org/in-context-learning) is the general ability to learn a task from examples in the prompt. CoT is a specific way of writing those examples (or the instruction) so they include reasoning steps.
- **CoT vs. fine-tuning**: CoT changes only the prompt. The model's weights are untouched — nothing is trained.
- **"Showing work" vs. "true reasoning"**: A CoT chain is text the model generates; it is not a guaranteed window into how the model actually computed the answer. The chain can look plausible while the real cause of the answer lies elsewhere.

## Where To Go Next

- Read [In-Context Learning](https://aipedia.org/in-context-learning) for the prompting foundation CoT builds on.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) to understand why CoT only emerges in large models.
- Read [GPT](https://aipedia.org/gpt) for the family of models where these prompting behaviors were first studied at scale.
- Read [RLHF](https://aipedia.org/rlhf) to see how models are trained to follow instructions like "think step by step" in the first place.


# Pre-training

> The stage where a model learns broad patterns from a very large dataset

- Type: Concept
- Topics: Deep learning, Training, Foundation models
- Page: https://aipedia.org/pre-training

## Resources

- [Improving Language Understanding by Generative Pre-Training](https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf): Paper, Radford et al., 2018
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://arxiv.org/abs/1810.04805): Paper, Devlin et al., 2018
- [Why Does Unsupervised Pre-training Help Deep Learning?](https://jmlr.org/papers/v11/erhan10a.html): Paper, Erhan et al., 2010
- [Training Compute-Optimal Large Language Models](https://arxiv.org/abs/2203.15556): Paper, Hoffmann et al., 2022 (Chinchilla)

**Pre-training** is the first major stage in building a modern foundation model. During this stage, the model is exposed to a huge amount of data and learns broad patterns in language, code, images, or other modalities before it is adapted to a narrower task.

> Good follow-up pages: [GPT](https://aipedia.org/gpt), [BERT](https://aipedia.org/bert), [Transformer](https://aipedia.org/transformer), and [Scaling Laws](https://aipedia.org/scaling-laws).

## A Simple Example

Suppose you want a model that can answer biology questions. You could train it only on biology examples, but that would be limiting.

Instead, pre-training teaches the model broad skills first:

- how sentences are structured
- how facts are expressed in text
- how code, math, or diagrams tend to look

After that broad stage, the model can be adapted more efficiently to specific tasks.

## Why Pre-training Matters

Pre-training does three important things:

1. It gives the model general-purpose representations
2. It reduces the amount of labeled task-specific data you need later
3. It creates a reusable base model for many downstream uses

That is why so much of modern AI development is really about building and adapting pre-trained models.

## Common Objectives

Most pre-training uses **self-supervised learning**, which means the training signal comes from the data itself.

### Causal Language Modeling

Predict the next token from the previous ones:

$$
P(x) = \prod_{i=1}^n P(x_i | x_{<i})
$$

This is the objective used by GPT-style models.

### Masked Language Modeling

Hide some tokens and ask the model to fill them in from context.

This is the objective used by BERT-style models.

## The Pre-training Pipeline

1. **Data curation**: collect, filter, deduplicate, and clean large corpora
2. **Tokenization**: convert raw text or other inputs into model-ready units
3. **Training**: optimize the model across many steps on large compute clusters
4. **Evaluation**: track loss and benchmark behavior

## What Makes Pre-training Hard

- huge compute requirements
- messy internet-scale data
- difficult decisions about data mixture and quality
- strong interactions between model size, tokens, and compute budget

That is where [Scaling Laws](https://aipedia.org/scaling-laws) become useful.

## Pre-training vs Fine-Tuning

| Stage | Goal |
|-------|------|
| Pre-training | Learn broad patterns from massive data |
| Fine-tuning | Adapt the model to a narrower behavior or task |
| Preference tuning / alignment | Make behavior more useful to people |

## What To Remember

- Pre-training is the broad learning stage, not the final product
- It usually uses self-supervised objectives
- Most modern AI systems start with a strong pre-trained base model


# Reinforcement Learning

> Learning by trial and error through rewards

- Type: Concept
- Topics: Deep learning, Reinforcement learning, Agents, Decision making
- Page: https://aipedia.org/reinforcement-learning

## Resources

- [Reinforcement Learning: An Introduction (2nd ed.)](http://incompleteideas.net/book/the-book-2nd.html): Book, Sutton & Barto, 2018
- [Spinning Up in Deep RL](https://spinningup.openai.com/en/latest/): Docs, OpenAI
- [Lectures on Reinforcement Learning](https://www.davidsilver.uk/teaching/): Course, David Silver, UCL

**Reinforcement Learning (RL)** is about learning by trial and error. An agent takes actions, sees what happens, and gets rewards or penalties. Over time, it learns which actions lead to better long-term outcomes.

> Good follow-up pages: [Policy Gradient](https://aipedia.org/policy-gradient), [DQN](https://aipedia.org/dqn), [PPO](https://aipedia.org/ppo), and [RLHF](https://aipedia.org/rlhf).

## A Simple Example

Imagine training a robot to leave a maze:

- every move costs `-1`
- reaching the exit gives `+100`
- falling into a trap gives `-50`

The robot is not told the correct path in advance. It has to explore, make mistakes, and gradually discover a strategy that earns the highest total reward.

## The RL Loop

At each step:

1. The agent observes the current **state** $s_t$
2. It chooses an **action** $a_t$
3. The environment returns a **reward** $r_t$ and a new state $s_{t+1}$
4. The process repeats

The goal is to learn a **policy** $\pi(a|s)$: a rule for choosing actions that maximizes long-term reward.

## Markov Decision Process (MDP)

RL problems are usually written as a **Markov Decision Process**:

- **States** $\mathcal{S}$: all situations the agent might be in
- **Actions** $\mathcal{A}$: what the agent can do
- **Transition** $P(s'|s,a)$: how the world changes after an action
- **Reward** $R(s,a,s')$: how good or bad that outcome is
- **Discount** $\gamma$: how much future rewards matter

If that notation is new, the main idea is still simple: **state -> action -> consequence -> reward**.

## The Objective

RL tries to maximize the expected discounted return:

$$
J(\pi) = \mathbb{E}_{\tau \sim \pi}\left[\sum_{t=0}^{\infty} \gamma^t r_t\right]
$$

That expression just means: add up rewards over time, with optional discounting so near-term rewards count more than distant ones.

## Value Functions

Two functions show up everywhere in RL:

- **State value** $V^\pi(s)$: how good it is to be in state $s$
- **Action value** $Q^\pi(s, a)$: how good it is to take action $a$ in state $s$

They help the agent estimate long-term consequences before it has seen every possible future.

$$
V^\pi(s) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s\right]
$$

$$
Q^\pi(s, a) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s, a_0 = a\right]
$$

## Bellman Equations

The Bellman equations say that the value of a state equals:

- the immediate reward you expect now
- plus the value of where you are likely to end up next

That recursive structure is what makes dynamic programming and many RL algorithms possible.

$$
V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^\pi(s')]
$$

## Interactive Visualization

Watch an agent learn to navigate through trial and error:

*Interactive demo: https://aipedia.org/reinforcement-learning*

## Two Big Families of Methods

**Value-based methods**
- learn a score for actions, such as $Q(s,a)$
- then pick the action with the highest score
- examples: Q-learning, [DQN](https://aipedia.org/dqn)

**Policy-based methods**
- learn the policy directly
- work well for continuous or stochastic actions
- examples: [Policy Gradient](https://aipedia.org/policy-gradient), [PPO](https://aipedia.org/ppo)

## Key Algorithms

| Algorithm | Type | Main idea |
|-----------|------|-----------|
| Q-Learning | Value | Update action values from experience |
| DQN | Value | Use a neural network to approximate Q-values |
| REINFORCE | Policy | Push up actions that led to high reward |
| PPO | Policy | Improve the policy while limiting unstable updates |
| SAC | Actor-Critic | Add entropy to encourage exploration |

## Exploration vs Exploitation

The hardest practical tradeoff in RL is:

- **Explore**: try uncertain actions that might be better
- **Exploit**: use the best strategy found so far

If you only exploit, you may miss better strategies. If you only explore, you never settle on one.

## Where RL Shows Up

- Game playing
- Robotics
- Recommender systems
- Resource allocation
- Language model alignment methods such as [RLHF](https://aipedia.org/rlhf)

## What To Remember

- RL is learning from reward, not labeled answers
- The objective is long-term reward, not immediate reward
- Most methods either learn values, policies, or both


# The First Law of Complexodynamics

> Why complexity rises then falls while entropy only increases

- Type: Blog
- By: Scott Aaronson
- Year: 2011
- Topics: Complexity, Entropy, Theory, Physics
- Page: https://aipedia.org/complexodynamics

## Resources

- [The First Law of Complexodynamics](https://scottaaronson.blog/?p=762): Article, Scott Aaronson, Shtetl-Optimized
- [Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton](https://arxiv.org/abs/1405.6903): Paper, Follow-up paper, 2014

**The First Law of Complexodynamics** is Scott Aaronson's blog-post exploration of a puzzle you can see in your coffee cup: physical systems start simple, become intricate and interesting, then fade into featureless equilibrium — complexity rises, peaks, and falls, even though entropy increases the whole time.

> This is the accessible entry point to a two-page story. The formal version, with an actual theorem, is [The Coffee Automaton](https://aipedia.org/coffee-automaton). The measurement machinery comes from [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity).

## Why Students Should Care

- It sharpens a distinction students constantly blur: **entropy is not complexity**. Maximum-entropy states are boring, not intricate.
- Defining "interesting structure" rigorously is surprisingly hard — and the candidate definitions here (complextropy, sophistication) connect directly to compression and [MDL](https://aipedia.org/mdl-tutorial).
- The rise-then-fall arc is a suggestive lens for thinking about learning dynamics in neural networks.

## The Puzzle

The Second Law of Thermodynamics says entropy never decreases:

$$
S(t_2) \geq S(t_1) \quad \text{for } t_2 > t_1
$$

If "more entropy" meant "more complex," the universe would just get steadily more complex forever. But look around: complexity behaves differently. A freshly shuffled deck isn't complex — it's random. A factory-ordered deck isn't complex — it's trivially simple. Complexity peaks somewhere in between order and randomness. Why? And can we define "complexity" so that statement is even meaningful?

## The Coffee Example

Consider cream being poured into coffee:

| Time | State | Entropy | Complexity |
|------|-------|---------|------------|
| t=0 | Separated layers | Low | Low |
| t=mid | Swirling patterns | Medium | **High** |
| t=∞ | Uniform mixture | High | Low |

The intricate swirls at mid-mixing are more "complex" than either extreme: the initial state is trivially describable, and the final state is just noise.

## Defining Complexity

Here is the hard part. Plain Kolmogorov complexity fails: it assigns its *highest* value to the fully mixed random state, which is exactly the state we want to call boring.

Aaronson proposes **complextropy**: roughly, the length of the shortest *efficient* program that outputs a set (or distribution) within which the observed state looks random. For a string $x$:

$$
\text{Complextropy}(x) = \min_{S: x \in S} K(S)
$$

where $K(S)$ is the Kolmogorov complexity of the set $S$, and $x$ must look random within $S$.

The idea in words: describe the *pattern*, and let the noise be noise. You pay only for the structure. Ordered states need a tiny pattern description; random states fit the trivial pattern "any string of this length"; only the in-between swirls force a long pattern description.

## Interactive Demo

Watch complexity rise and fall as a system evolves:

*Interactive demo: https://aipedia.org/complexodynamics*

## Why Complexity Peaks

At $t=0$: simple description ("all black on left, all white on right")

At $t=\text{mid}$: complex description (must specify the intricate mixing patterns)

At $t=\infty$: simple description ("random noise" or "uniform distribution")

Both endpoints are cheap to describe — for opposite reasons. Only the middle is expensive.

## The Sophistication Connection

Kolmogorov's own notion of **sophistication** formalizes the same instinct:

$$
\text{Soph}(x) = \min \{K(S) : x \in S, K(x|S) \geq \log|S| - O(1)\}
$$

You do not need to memorize the condition. It says: find the simplest set that contains $x$ as a *typical* (incompressible-within-the-set) member; the complexity of that set is the sophistication of $x$. It is the "structure only, noise excluded" measure — the [Coffee Automaton](https://aipedia.org/coffee-automaton) paper later uses it to prove the rise-and-fall rigorously.

## Implications for AI

Deep learning training may follow a similar arc:

- Early training: simple patterns (high loss, low complexity)
- Mid training: complex intermediate features
- Late training: simplified, generalizable representations

This is an analogy rather than a theorem — but it is one reason this blog post appears on ML reading lists.

## Common Confusion

- **Entropy vs. complexity**: entropy measures disorder and only goes up; complexity (complextropy/sophistication) measures *structure* and peaks in the middle. The uniform mixture has maximum entropy and near-zero complexity.
- **Random is not complex**: a random string is incompressible (high Kolmogorov complexity) but has no structure worth describing (low sophistication). The two measures deliberately disagree here.
- **"First Law" is a playful name**: this is a blog post proposing a conjecture and a definition, not an established law of physics.
- **This page vs. [Coffee Automaton](https://aipedia.org/coffee-automaton)**: this post asks the question and proposes complextropy; the paper builds a concrete model and proves the rise-and-fall theorem.

## Where To Go Next

- Read [The Coffee Automaton](https://aipedia.org/coffee-automaton) for the formal model and the main theorem.
- Read [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) for shortest-description reasoning from the ground up.
- Read [MDL Tutorial](https://aipedia.org/mdl-tutorial) for the practical "structure vs. noise" trade-off in model selection.
- Read [MDL Weights](https://aipedia.org/mdl-weights) for description-length ideas applied to neural networks.


# The Unreasonable Effectiveness of Recurrent Neural Networks

> Andrej Karpathy's influential blog post demonstrating RNN capabilities through character-level generation

- Type: Blog
- By: Andrej Karpathy
- Year: 2015
- Topics: Deep learning, RNNs, NLP, Generative
- Page: https://aipedia.org/rnn-effectiveness

## Resources

- [The Unreasonable Effectiveness of Recurrent Neural Networks](https://karpathy.github.io/2015/05/21/rnn-effectiveness/): Article, Andrej Karpathy, 2015
- [karpathy/char-rnn](https://github.com/karpathy/char-rnn): Code, Character-level RNN code

**The Unreasonable Effectiveness of Recurrent Neural Networks** is Andrej Karpathy's 2015 blog post showing that a simple RNN, trained only to guess the next character in raw text, can learn spelling, syntax, code structure, and even style. It captivated the AI community and previewed the idea behind modern language models.

> This page assumes you know roughly what an RNN is. If gates and hidden states are new to you, read [Understanding LSTMs](https://aipedia.org/understanding-lstms) first — Karpathy's actual models were LSTMs.

## Why Students Should Care

- This is the clearest early demonstration that **next-token prediction alone** produces rich language ability — the same objective that trains [GPT](https://aipedia.org/gpt) today.
- It shows that neural networks can learn structure (grammar, brackets, markup) without anyone programming rules in.
- The temperature-sampling trick introduced here is exactly the "temperature" knob you set when calling a modern LLM API.
- It is a great first project: char-RNNs are small enough to train on a laptop.

## The Core Idea

Train an RNN to predict the next character given all previous characters:

$$
P(x_{t+1} | x_1, x_2, ..., x_t)
$$

That's it. No parsing, no grammar rules, no hand-built structure — just characters in, probabilities out. Yet the results are remarkable.

A concrete picture: feed the model "hell" one letter at a time, and train it so that after "h" it predicts "e", after "he" it predicts "l", and so on. Do this over megabytes of text and the model is forced to internalize how the text is built.

## Character-Level Language Model

At each timestep, the RNN:

1. Takes a character as input
2. Updates its hidden state: $h_t = \tanh(W_{hh}h_{t-1} + W_{xh}x_t)$
3. Outputs a probability distribution over all characters: $P(x_{t+1}) = \text{softmax}(W_{hy}h_t)$

You do not need to memorize the equations. The important idea is: **the hidden state is a running summary of everything seen so far, and the output is a guess about what comes next**.

During generation, sample a character from the output distribution and feed it back in as the next input. Repeat, and the model writes text one character at a time.

## Interactive Demo

Watch an RNN generate text character by character:

*Interactive demo: https://aipedia.org/rnn-effectiveness*

## What RNNs Learn

Karpathy trained char-RNNs on various datasets and found they learned:

**Shakespeare**
- Spelling, punctuation, line structure
- Character names, stage directions
- Iambic pentameter patterns

**Wikipedia**
- XML/HTML markup structure
- Balanced brackets and tags
- Link syntax

**Linux Source Code**
- C syntax (brackets, semicolons)
- Indentation conventions
- Function/variable naming patterns

**LaTeX**
- Mathematical notation
- Environment matching (begin/end)
- Citation formats

Notice the pattern: none of this structure was labeled. The model discovered it because predicting the next character *requires* it.

## Temperature Sampling

When generating, you can control how adventurous the sampling is with a **temperature** parameter $T$ that reshapes the output distribution:

$$
P(x_i) = \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)}
$$

- **T near 0**: nearly greedy — always picks the highest-probability character (safe but repetitive)
- **T = 1**: standard sampling from the model's distribution
- **T above 1**: flatter distribution — more random, creative but potentially incoherent

The takeaway: low temperature sharpens the distribution, high temperature flattens it. This exact knob survives unchanged in today's LLM APIs.

## Hidden State Visualization

Karpathy also looked *inside* the trained network and found individual neurons tracking specific, human-interpretable features:

- One neuron activates inside quotes
- Another tracks line length
- Some detect URLs or code comments

Nobody assigned these jobs — the neurons specialized on their own. This was an early glimpse of what we now call interpretability research.

## Why This Matters

This post demonstrated that:

1. Simple models can capture complex structure
2. A raw prediction objective learns rich representations
3. Neural networks discover interpretable features

These insights presaged the success of [GPT](https://aipedia.org/gpt) and modern language models, which scale up the same recipe: predict the next token, on much more data, with a bigger model.

## Common Confusion

- **This is a blog post, not a paper**: it is famous for its demos and clarity, not for introducing a new architecture. The models are standard LSTMs.
- **Character-level vs. token-level**: char-RNNs predict one character at a time; modern LLMs predict subword *tokens*. Same objective, different vocabulary.
- **"Effectiveness" does not mean understanding**: the model imitates the statistics of its training text. Whether that constitutes understanding was — and remains — a live debate.
- **RNN vs. LSTM here**: Karpathy says "RNN" throughout, but the strong results use LSTM cells; vanilla RNNs struggle with the longer-range structure.

## Where To Go Next

- Read [Understanding LSTMs](https://aipedia.org/understanding-lstms) for how the recurrent cell actually keeps memory.
- Read [RNN Regularization](https://aipedia.org/rnn-regularization) for how these models were kept from overfitting.
- Read [Seq2Seq](https://aipedia.org/seq2seq) for RNNs applied to translation with an encoder-decoder design.
- Read [GPT](https://aipedia.org/gpt) to see next-token prediction scaled into a general-purpose language model.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) for what happens as you grow this recipe by orders of magnitude.


# Understanding LSTM Networks

> Christopher Olah's visual guide to Long Short-Term Memory networks

- Type: Blog
- By: Chris Olah
- Year: 2015
- Topics: Deep learning, RNNs, LSTMs, NLP
- Page: https://aipedia.org/understanding-lstms

## Resources

- [Understanding LSTM Networks](https://colah.github.io/posts/2015-08-Understanding-LSTMs/): Article, Chris Olah, 2015
- [Long Short-Term Memory](https://doi.org/10.1162/neco.1997.9.8.1735): Paper, Hochreiter & Schmidhuber, 1997

**Understanding LSTM Networks** is Christopher Olah's influential blog post that explains, with pictures and plain language, how Long Short-Term Memory networks work. It became the standard introduction to recurrent architectures, and this page follows its spirit: intuition first, equations second.

> If you have never seen a recurrent neural network before, read [The Unreasonable Effectiveness of RNNs](https://aipedia.org/rnn-effectiveness) first — it shows what RNNs can do. This page explains the machinery that makes them remember.

## Why Students Should Care

- LSTMs were the workhorse of sequence modeling (translation, speech, text generation) for a decade before [Transformers](https://aipedia.org/transformer).
- The core trick — a protected path that lets gradients flow across many steps — reappears in ResNet skip connections and Transformer residual streams.
- Gating (learned, soft on/off switches) is a fundamental design pattern you will meet again in GRUs, [Mamba](https://aipedia.org/mamba), and mixture-of-experts models.
- Understanding *why* vanilla RNNs fail teaches you about vanishing gradients, one of the central obstacles in deep learning.

## The Problem: Remembering Things From Long Ago

Try to fill in the blank: "I grew up in France... I speak fluent ___."

To predict "French", a model needs a clue ("France") from many words earlier. A standard RNN passes information forward through a single hidden state, squashed through a nonlinearity at every step. In theory it can carry that clue forward. In practice, gradients flowing backward through many steps either:

- **Vanish**: shrink exponentially, so the model never learns long-range patterns
- **Explode**: grow exponentially, making training unstable

So vanilla RNNs mostly learn short-range patterns and forget the rest.

## The LSTM Solution: A Conveyor Belt With Gates

LSTMs add a **cell state** — think of it as a conveyor belt running straight through time. Information placed on the belt can ride along for many timesteps with almost no modification. Small learned switches called **gates** control what gets put on the belt, what gets removed, and what gets read off.

That is the whole idea. The four equations below just implement the belt and its three kinds of workers.

## The Four Components

Each gate is a small neural layer that looks at the previous hidden state $h_{t-1}$ and the current input $x_t$, and outputs numbers between 0 and 1 (via the sigmoid $\sigma$). Think of each output as a percentage: "let this much through."

### 1. Forget Gate — what to erase from the belt

$$
f_t = \sigma(W_f \cdot [h_{t-1}, x_t] + b_f)
$$

Output near 0 means "forget this part of the cell state"; near 1 means "keep it."

### 2. Input Gate — which slots to write to

$$
i_t = \sigma(W_i \cdot [h_{t-1}, x_t] + b_i)
$$

### 3. Cell Candidate — what new content to write

$$
\tilde{C}_t = \tanh(W_C \cdot [h_{t-1}, x_t] + b_C)
$$

The candidate proposes new values; the input gate decides how much of them actually gets added.

### 4. Output Gate — what to read off the belt right now

$$
o_t = \sigma(W_o \cdot [h_{t-1}, x_t] + b_o)
$$

You do not need to memorize which letter is which. The important idea is: **three gates (forget, input, output) plus one candidate, all computed from the same two inputs**.

## Cell State Update

The belt update combines "erase a little" and "write a little":

$$
C_t = f_t \ast C_{t-1} + i_t \ast \tilde{C}_t
$$

In words: the new cell state is the old cell state (scaled by how much we keep) plus the new candidate (scaled by how much we admit). Everything else in the LSTM exists to compute those two scaling factors.

## Interactive Demo

Explore each gate and watch information flow through the LSTM cell:

*Interactive demo: https://aipedia.org/understanding-lstms*

## Why LSTMs Work

The cell state acts as a **gradient highway**. During backpropagation:

$$
\frac{\partial C_t}{\partial C_{t-1}} = f_t
$$

If the forget gate stays close to 1, the gradient passes through unchanged step after step — no repeated squashing, so no exponential shrinking. This solves the vanishing gradient problem for information the network has decided to keep.

## The Intuition, One More Time

Think of an LSTM as a conveyor belt (cell state) with workers (gates):

- **Forget gate**: workers removing items from the belt
- **Input gate**: workers adding new items
- **Output gate**: workers taking items off for current use

The belt keeps moving; workers only modify what's necessary.

## Variants

- **GRU (Gated Recurrent Unit)**: merges the forget and input gates into one — simpler, often just as good
- **Peephole connections**: gates get to look at the cell state directly
- **Bidirectional LSTM**: runs one LSTM forward and one backward over the sequence, so each position sees both past and future context

## Common Confusion

- **LSTM vs. RNN**: an LSTM *is* an RNN — a specific recurrent cell design. "Vanilla RNN" usually means the simple tanh cell without gates.
- **Cell state vs. hidden state**: the cell state $C_t$ is the long-term conveyor belt; the hidden state $h_t$ is the filtered, per-step output read off it by the output gate. They are different vectors.
- **Gates are not binary**: gate outputs are continuous values between 0 and 1, learned by gradient descent — not hard switches.
- **This page vs. the paper**: LSTMs were invented by Hochreiter and Schmidhuber in 1997; Olah's 2015 post is the explanation that made them widely understood.

## Where To Go Next

- Read [The Unreasonable Effectiveness of RNNs](https://aipedia.org/rnn-effectiveness) to see what LSTM-style models can generate.
- Read [RNN Regularization](https://aipedia.org/rnn-regularization) for how to apply dropout to LSTMs without breaking their memory.
- Read [Relational RNNs](https://aipedia.org/relational-rnn) for a memory design where stored facts interact via attention.
- Read [Seq2Seq](https://aipedia.org/seq2seq) for how two LSTMs (encoder and decoder) power machine translation.
- Read [Transformer](https://aipedia.org/transformer) for the architecture that replaced recurrence with attention.


# The Annotated Transformer

> Line-by-line PyTorch implementation of the Transformer architecture

- Type: Blog
- By: Sasha Rush
- Year: 2018
- Topics: Deep learning, Transformers, Attention, NLP
- Page: https://aipedia.org/annotated-transformer

## Resources

- [The Annotated Transformer](https://nlp.seas.harvard.edu/annotated-transformer/): Article, Harvard NLP, 2018
- [harvardnlp/annotated-transformer](https://github.com/harvardnlp/annotated-transformer): Code, Notebook source
- [Attention Is All You Need](https://arxiv.org/abs/1706.03762): Paper, Vaswani et al., 2017

**The Annotated Transformer** is a line-by-line guide to implementing the Transformer architecture in PyTorch. Created by Harvard NLP, it makes the seminal "Attention Is All You Need" paper concrete and reproducible: every equation in the paper is paired with the few lines of code that compute it.

> This page is about a **tutorial implementation**, not a new model. If you have not met the architecture yet, read [Transformer](https://aipedia.org/transformer) first; for the paper itself, see [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need).

## Why Students Should Care

- Reading a paper and *implementing* it are very different skills — this resource bridges the two.
- The full working Transformer fits in roughly 400 lines of PyTorch. Seeing that demystifies the architecture behind modern LLMs.
- The habits it teaches (map each equation to a small module, test pieces independently) transfer to implementing any paper.

## Why Code Matters

The original Transformer paper describes the architecture mathematically. The Annotated Transformer shows exactly how those equations become working code. For example, the attention equation

$$
\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V
$$

becomes just three lines:

```python
scores = torch.matmul(query, key.transpose(-2, -1)) / math.sqrt(d_k)
p_attn = scores.softmax(dim=-1)
return torch.matmul(p_attn, value)
```

If the math felt abstract, the code makes it concrete: a matrix multiply to compare queries with keys, a softmax to turn scores into weights, and another matrix multiply to mix the values.

## Core Components

The full Transformer in ~400 lines breaks down into six key pieces:

1. **Embeddings + Positional Encoding** — token lookup + position information
2. **Multi-Head Attention** — parallel attention heads
3. **Feed-Forward Network** — position-wise MLP
4. **Encoder Layer** — self-attention + FFN with residuals
5. **Decoder Layer** — masked self-attention + cross-attention + FFN
6. **Generator** — project to vocabulary for prediction

Each piece is a small, independent module — none of them is individually complicated.

## Interactive Code Explorer

Click through the architecture to see the implementation of each component:

*Interactive demo: https://aipedia.org/annotated-transformer*

## Key Implementation Details

### Scaled Dot-Product Attention

The complete attention function, including the mask used by the decoder to hide future tokens:

```python
def attention(query, key, value, mask=None, dropout=None):
    d_k = query.size(-1)
    scores = torch.matmul(query, key.transpose(-2, -1)) / math.sqrt(d_k)
    if mask is not None:
        scores = scores.masked_fill(mask == 0, -1e9)
    p_attn = scores.softmax(dim=-1)
    return torch.matmul(p_attn, value), p_attn
```

Note the trick: masked positions get a score of `-1e9`, so after the softmax their weight is effectively zero.

### Sublayer Connection (Residual + LayerNorm)

Every attention and feed-forward block is wrapped in the same pattern — normalize, apply the sublayer, add the result back to the input:

```python
class SublayerConnection(nn.Module):
    def forward(self, x, sublayer):
        return x + self.dropout(sublayer(self.norm(x)))
```

The residual `x +` is what lets gradients flow through many stacked layers.

## Learning Path

The Annotated Transformer is best approached in order:

1. **Embeddings** — how tokens become vectors
2. **Attention** — the core mechanism
3. **Multi-Head** — parallel attention
4. **Encoder/Decoder** — full architecture
5. **Training** — label smoothing, optimizer

## Common Confusion

- **The Annotated Transformer is a tutorial, not a model.** It introduces no new ideas — it faithfully implements the 2017 paper.
- **Transformer vs. Attention Is All You Need vs. this page.** [Transformer](https://aipedia.org/transformer) is the architecture, [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) is the paper, and the Annotated Transformer is the walkthrough that turns the paper into code.
- **~400 lines does not include training infrastructure.** Data loading, batching, and large-scale training are separate engineering concerns.

## Where To Go Next

- Read [Transformer](https://aipedia.org/transformer) for the conceptual overview of the architecture
- Read [Attention Is All You Need](https://aipedia.org/attention-is-all-you-need) for the original paper and results
- Read [Layer Normalization](https://aipedia.org/layer-normalization) for the normalization used in every sublayer
- Read [BERT](https://aipedia.org/bert) and [GPT](https://aipedia.org/gpt) for what people built once the architecture was implementable


# Stable Marriage Problem

> Finding a stable matching with the Gale-Shapley deferred acceptance algorithm

- Type: Misc
- By: Gale & Shapley
- Year: 1962
- Topics: Algorithm, Matching, Game theory, Optimization
- Page: https://aipedia.org/stable-marriage

## Resources

- [College Admissions and the Stability of Marriage](https://www.jstor.org/stable/2312726): Paper, Gale & Shapley, 1962
- [The Evolution of the Labor Market for Medical Interns and Residents](https://www.jstor.org/stable/1837229): Paper, Roth, 1984

The **Stable Marriage Problem** is the historical name for a matching problem between two groups with ranked preferences. Today, it is often explained more neutrally as a **stable matching** problem between applicants and programs, students and schools, or any two-sided market.

The classic solution is the **Gale-Shapley deferred acceptance algorithm**, which always produces a stable matching.

## A Simple Goal

We want a matching with no **blocking pair**: no applicant and program that would both prefer each other over their assigned match.

If such a pair exists, the matching is unstable because those two sides would rather deviate.

## Interactive Demo

*Interactive demo: https://aipedia.org/stable-marriage*

## Algorithm Explanation

At a high level, the Gale-Shapley algorithm works like this:

1. Everyone starts unmatched.
2. Each unmatched applicant proposes to the highest-ranked program they have not yet tried.
3. Each program tentatively keeps its favorite proposal so far and rejects the rest.
4. Rejected applicants move to their next choice.
5. The process repeats until no more proposals are needed.

The word **tentatively** matters. Programs may replace an earlier tentative match if a better proposal arrives later.

## Why the Result Is Stable

Gale-Shapley prevents blocking pairs because:

- applicants propose in order of preference
- programs only trade up, never down
- once a program rejects an applicant, it will never want that applicant later

So when the algorithm ends, there is no unmatched pair that would rather be together.

## Time Complexity

For $n$ participants on each side:

- each applicant proposes to each program at most once
- there are at most $n^2$ proposals

**Time complexity:** `O(n^2)`  
**Space complexity:** `O(n^2)` to store preferences

## Applications

- Medical residency matching
- College admissions and school choice
- Job matching platforms
- Organ exchange systems

## Historical Note

The historical title comes from the original 1962 paper, but the algorithm is now used far beyond marriage-style examples.


# Keeping Neural Networks Simple by Minimizing the Description Length of the Weights

> Hinton's MDL approach to neural network regularization through noisy weights

- Type: Misc
- By: Hinton & van Camp
- Year: 1993
- Topics: Deep learning, Regularization, MDL, Compression
- Page: https://aipedia.org/mdl-weights

## Resources

- [Keeping Neural Networks Simple by Minimizing the Description Length of the Weights](https://www.cs.toronto.edu/~hinton/absps/colt93.pdf): Paper, Hinton & van Camp, 1993

**Keeping Neural Networks Simple** by Hinton and van Camp (1993) turned regularization into an information-theory problem: train networks with deliberately *noisy* weights, because noisy weights need fewer bits to describe — and models that can be described in fewer bits generalize better.

> Prerequisite: the [MDL Tutorial](https://aipedia.org/mdl-tutorial) — this paper is the MDL principle applied to neural network weights. Skim that page's "Core Idea" section if nothing else.

## Why Students Should Care

- This 1993 paper is the origin of **variational inference for neural networks** — the math here reappears almost unchanged in [VAEs](https://aipedia.org/vae), Bayesian neural nets, and modern compression-based views of generalization.
- It answers a deep question simply: *why* do smaller/simpler models generalize? Because they encode fewer bits of the training set, so they cannot have memorized the noise.
- It anticipated [dropout](https://aipedia.org/dropout)-style noise injection and learned quantization decades early.

## A Concrete Way In

Imagine you must fax a trained network to a friend, and every bit costs money. Weight 0.73916402... is expensive. But do you really need all those digits? If sending "roughly 0.74, give or take 0.02" barely hurts accuracy, most of those digits were describing noise, not knowledge. This paper makes networks *train themselves* to need fewer digits.

## The MDL Principle

The **Minimum Description Length** principle states that the best model minimizes:

$$
L(\text{model}) + L(\text{data} | \text{model})
$$

For neural networks:

$$
L(\text{weights}) + L(\text{errors} | \text{weights})
$$

A network with fewer effective bits in its weights spends less on the first term; a network that fits the data well spends less on the second. Training should minimize the sum.

## The Key Insight: Noisy Weights Are Cheap Weights

Instead of transmitting precise weights, transmit *noisy* ones:

$$
\tilde{w} = w + \epsilon, \quad \epsilon \sim \mathcal{N}(0, \sigma^2)
$$

Higher noise $\sigma$ means:

- Fewer bits to describe the weights (coarser precision suffices)
- More bits to describe the prediction errors (the network is less exact)

The trade-off differs per weight — some weights matter a lot, others barely — so the network learns the optimal noise level *for each weight* during training.

## Interactive Demo

Explore the trade-off between weight precision and noise:

*Interactive demo: https://aipedia.org/mdl-weights*

## Mathematical Framework

Treat each weight not as a number but as a distribution:

$$
q(w) = \mathcal{N}(w; \mu, \sigma^2)
$$

The description length (in bits) for communicating weights drawn from $q$ relative to an agreed prior $p$ (often $\mathcal{N}(0, 1)$):

$$
L(w) \approx -\log \frac{q(w)}{p(w)}
$$

The takeaway: the cost of a weight is measured by how much its learned distribution $q$ deviates from the prior $p$ — a weight that stays vague and prior-like is nearly free; a sharply pinned-down weight is expensive.

## The Bits-Back Argument

A subtle and famous trick. When the sender transmits weights sampled from a known distribution $q$, the randomness used to pick the sample can itself carry other information, which the receiver can recover — the sender effectively gets those bits refunded:

$$
\text{Effective bits} = H[q] - D_{KL}[q \| p]
$$

Do not worry if this feels slippery on first read — it is. The punchline is that the *true* cost of the weights is exactly the KL divergence between $q$ and the prior. That is the same KL term that appears in [VAEs](https://aipedia.org/vae), derived here fifteen years earlier.

## Connection to Modern Regularization

This 1993 paper anticipated:

| MDL Concept | Modern Equivalent |
|-------------|------------------|
| Noisy weights | Dropout, weight noise |
| Description length | KL divergence in VAEs |
| Bits-back coding | Variational inference |
| Optimal precision | Learned quantization |

## Training Procedure

1. Forward pass with noisy weights: $\tilde{w}_i = w_i + \mathcal{N}(0, \sigma_i^2)$
2. Compute expected loss: $\mathbb{E}_\epsilon[\mathcal{L}(x, y; w + \epsilon)]$
3. Update both $w$ and $\sigma$ via gradient descent
4. The network learns which weights need precision and which can stay fuzzy

## Why This Matters

This paper established:

- **Information-theoretic regularization**: a derivation, not a heuristic
- **Learned precision**: different weights need different precision
- **Compression = generalization**: simpler (shorter-description) models generalize better

## Common Confusion

- **This paper vs. the [MDL Tutorial](https://aipedia.org/mdl-tutorial)**: Grünwald's tutorial explains the MDL *principle* in general; this paper is one specific application — compressing neural network weights.
- **Noise here vs. dropout**: [dropout](https://aipedia.org/dropout) zeroes activations at random; this method adds Gaussian noise to *weights*, with a per-weight learned magnitude and an information-theoretic justification.
- **Description length vs. parameter count**: a network with many low-precision (high-noise) weights can have a *shorter* description than a network with few high-precision ones. Bits, not parameters, are what count.
- **Not the same as post-hoc quantization**: precision is limited *during training*, so the network adapts to it, rather than being rounded after the fact.

## Where To Go Next

- Read [MDL Tutorial](https://aipedia.org/mdl-tutorial) for the general principle behind this paper.
- Read [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) for the deepest version of "short descriptions are good."
- Read [VAE](https://aipedia.org/vae) to see the same KL-divergence machinery powering deep generative models.
- Read [Variational Lossy Autoencoder](https://aipedia.org/variational-lossy-autoencoder) for a modern analysis of what variational codes capture.
- Read [Dropout](https://aipedia.org/dropout) for the heuristic noise-based regularizer this paper foreshadowed.


# Gradient Boosted Decision Trees

> Sequential tree ensembles optimized via gradient descent

- Type: Misc
- By: Jerome Friedman
- Year: 2001
- Topics: Machine learning, Ensemble, Boosting, Trees
- Page: https://aipedia.org/gbdt

## Resources

- [Greedy Function Approximation: A Gradient Boosting Machine](https://doi.org/10.1214/aos/1013203451): Paper, Friedman, 2001
- [XGBoost: A Scalable Tree Boosting System](https://arxiv.org/abs/1603.02754): Paper, Chen & Guestrin, 2016
- [dmlc/xgboost](https://github.com/dmlc/xgboost): Code, XGBoost library
- [LightGBM: A Highly Efficient Gradient Boosting Decision Tree](https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree): Paper, Ke et al., 2017
- [CatBoost: unbiased boosting with categorical features](https://arxiv.org/abs/1706.09516): Paper, Prokhorenkova et al., 2017

**Gradient Boosted Decision Trees (GBDT)** are an ensemble method that builds decision trees one at a time, where each new tree is trained to correct the mistakes the current ensemble is still making. The final model is the sum of all the trees.

> This is a classical machine learning method, not deep learning — no neural networks involved. But the word "gradient" here is the same gradient as in [Backpropagation](https://aipedia.org/backpropagation): both methods follow the derivative of a loss downhill.

## Why Students Should Care

- On tabular data (spreadsheet-style rows and columns), GBDT implementations like XGBoost and LightGBM are still the method to beat — they routinely win Kaggle competitions where deep learning does not.
- GBDT is the clearest example of **boosting**: turning many weak models into one strong one.
- The "gradient descent in function space" idea is a genuinely beautiful piece of ML theory that connects trees to the optimization you know from neural networks.

## A Concrete Picture First

Suppose you are predicting house prices. Your first tree is crude: it predicts 300,000 for a house that actually sells for 370,000 — an error of 70,000. Now train a *second* tree whose job is not to predict prices, but to predict those **errors**. Add its output to the first tree's prediction, and the combined model is closer to the truth. Repeat: every new tree cleans up whatever error is left. That is boosting.

## Core Idea: Gradient Descent in Function Space

Here is the elegant generalization. GBDT performs **gradient descent over functions** rather than parameters. Instead of nudging weights, we iteratively improve a model $F(x)$ by adding a new function (a tree) that points in the direction of steepest loss reduction.

At iteration $m$:

$$
F_m(x) = F_{m-1}(x) + \eta \, h_m(x)
$$

- $h_m(x)$ is a regression tree
- $\eta$ is the learning rate

You do not need to memorize the notation. The important idea is: **the model is a running sum of trees, and each new tree is a small step downhill on the loss.**

## Loss and Gradients

Why is "predict the errors" the same as "follow the gradient"? For squared error loss:

$$
L(y, F(x)) = \frac{1}{2}(y - F(x))^2
$$

The negative gradient of the loss with respect to the prediction is:

$$
-\frac{\partial L}{\partial F(x)} = y - F(x)
$$

That is exactly the residual — the leftover error. So each tree trained to predict residuals is literally fitting the negative gradient. For other losses (classification, ranking), the residuals are replaced by that loss's gradients, and the same machinery works.

## Interactive Visualization

The demo below shows:
- Data points and ensemble prediction curve
- Residuals as vertical lines
- Individual trees contributing to the final model
- Loss decreasing as trees are added

*Interactive demo: https://aipedia.org/gbdt*

## Key Hyperparameters

- **learning_rate (η)** – step size for each tree; smaller values improve generalization (but need more trees)
- **n_estimators** – number of trees in the ensemble
- **max_depth** – controls tree complexity and interaction order (how many features a single tree can combine)

The classic trade: lower the learning rate, raise the number of trees.

## GBDT vs Random Forest

Both are tree ensembles, but they combine trees in opposite ways: random forests train many independent trees in parallel and average them; GBDT trains trees sequentially, each depending on all previous ones.

| Aspect | GBDT | Random Forest |
|------|------|---------------|
| Training | Sequential | Parallel |
| Bias–Variance | Low bias | Low variance |
| Optimization | Gradient-based | Bagging |
| Overfitting | Controlled via learning rate | Controlled via averaging |

## When to Use GBDT

- Tabular data with mixed feature types
- Medium-sized datasets
- When strong performance and interpretability matter

For images, audio, and text, deep learning dominates — but for a table of customer records, reach for GBDT first.

## Common Confusion

- **Boosting vs. bagging**: boosting (GBDT) builds trees *sequentially*, each correcting the last; bagging (random forests) builds trees *independently* and averages them.
- **Gradient boosting vs. gradient descent**: same gradient idea, different space — gradient descent updates parameters; gradient boosting adds whole functions (trees).
- **GBDT is not deep learning.** No neural networks, no [backpropagation](https://aipedia.org/backpropagation) — though both follow gradients of a loss.
- **"Residuals" are a special case.** Trees fit plain residuals only under squared error; in general they fit the negative gradient of whatever loss you chose.

## Where To Go Next

- Read [Backpropagation](https://aipedia.org/backpropagation) to compare gradient descent in parameter space with the function-space version here.
- Read [Adam](https://aipedia.org/adam) for how gradient-based optimization is tuned in deep learning.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) for how deep learning behaves in the regimes where it *does* beat trees.

## Libraries

GBDT is widely available in:
- `xgboost`
- `lightgbm`
- `catboost`
- `sklearn.ensemble.GradientBoosting*`


# A Tutorial Introduction to the Minimum Description Length Principle

> Grünwald's comprehensive guide to MDL for model selection and learning

- Type: Misc
- By: Peter Grünwald
- Year: 2004
- Topics: MDL, Information theory, Model selection, Theory
- Page: https://aipedia.org/mdl-tutorial

## Resources

- [A Tutorial Introduction to the Minimum Description Length Principle](https://arxiv.org/abs/math/0406077): Paper, Grünwald, 2004

**A Tutorial Introduction to the Minimum Description Length Principle** by Peter Grünwald is the definitive guide to MDL — the idea that learning *is* compression: the best model of your data is the one that lets you describe the data in the fewest bits.

> This page pairs naturally with [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity), which supplies the theory of "shortest descriptions." MDL is the practical, computable cousin of that theory.

## Why Students Should Care

- MDL gives a principled answer to the most common question in practice: **how complex should my model be?** (What polynomial degree? How many clusters? Which features?)
- It formalizes Occam's razor — "prefer simpler explanations" stops being a slogan and becomes an equation.
- The compression view of learning runs straight through modern ML: regularization, [variational autoencoders](https://aipedia.org/vae), and the argument that LLMs are powerful *because* they compress the internet well.

## A Concrete Example First

Suppose you have 100 noisy data points and you must fit a polynomial. A degree-1 line misses the curvature (big errors). A degree-99 polynomial hits every point exactly (zero error) but is obviously absurd — it has memorized the noise. Some middle degree is right. But which, exactly, and *why*?

MDL's answer: imagine you must transmit the dataset to a friend. You could send the model (cheap for a line, expensive for 100 coefficients) plus the errors the model makes (expensive for the line, cheap for a good fit). The best model is the one that minimizes the **total** message length.

## The Core Idea

$$
L_{\text{total}} = L(\text{model}) + L(\text{data}|\text{model})
$$

- $L(\text{model})$: bits to describe the model itself
- $L(\text{data}|\text{model})$: bits to describe the prediction errors

Minimize the sum, not just the error. An overfit model wins the second term but loses badly on the first; an underfit model does the reverse.

## Occam's Razor, Formalized

MDL provides a mathematical justification for preferring simpler models:

$$
\text{Simple model} \Rightarrow \text{Low } L(\text{model})
$$

But simpler models may have higher errors — a bigger $L(\text{data}|\text{model})$. MDL finds the optimal trade-off, automatically. There is no tuning knob for "how much to penalize complexity"; the bit-counting does it.

## Interactive Demo

Compare models of varying complexity:

*Interactive demo: https://aipedia.org/mdl-tutorial*

## Two-Part Codes

The simplest version of MDL is exactly the transmit-to-a-friend scheme above:

1. Encode the model using $L_1$ bits
2. Encode the data given the model using $L_2$ bits
3. Choose the model minimizing $L_1 + L_2$

This is "crude" MDL. It works, but the split into two parts is somewhat arbitrary — refined versions fix that.

## Connection to Bayesian Inference

MDL relates to the Bayesian posterior. Take logs of Bayes' rule:

$$
\log P(\text{model}|\text{data}) = \log P(\text{data}|\text{model}) + \log P(\text{model}) - \log P(\text{data})
$$

Since an event with probability $P$ costs about $-\log P$ bits to encode, maximizing the posterior is (approximately) minimizing description length: the prior plays the role of the model-encoding cost, and the likelihood plays the role of the error-encoding cost.

## Normalized Maximum Likelihood

Refined MDL replaces the two-part code with the **stochastic complexity**, based on normalized maximum likelihood:

$$
\text{COMP}(x | \mathcal{M}) = \log \frac{P(x | \hat{\theta}(x), \mathcal{M})}{\sum_{x'} P(x' | \hat{\theta}(x'), \mathcal{M})}
$$

You do not need to memorize this. The idea: a model class is penalized by how well it *could have* fit every possible dataset. A very flexible class fits everything well, so its denominator is large — flexibility itself is what gets charged, not just parameter count.

## Key Applications

| Domain | MDL Application |
|--------|-----------------|
| Model selection | Choose polynomial degree |
| Change detection | Find breakpoints in time series |
| Clustering | Determine number of clusters |
| Feature selection | Which features to include |

## MDL vs. Other Criteria

You may have met AIC and BIC in a statistics class. They live in the same family:

| Criterion | Formula |
|-----------|---------|
| AIC | $-2\log L + 2k$ |
| BIC | $-2\log L + k\log n$ |
| MDL | $-\log L + \text{COMP}(\mathcal{M})$ |

MDL is often equivalent to BIC in the large-sample limit but has stronger theoretical foundations — its penalty is derived from coding, not chosen as a convention.

## Practical Insights

1. **More complex is not better**: overfitting literally wastes bits encoding noise
2. **Compression = learning**: a good compressor of the data is a good predictor of it
3. **Prior knowledge counts**: how you encode models reflects your assumptions, just like a Bayesian prior

## Common Confusion

- **MDL vs. Kolmogorov complexity**: [Kolmogorov complexity](https://aipedia.org/kolmogorov-complexity) is the ideal, uncomputable "shortest program" notion. MDL restricts descriptions to a chosen model class, which makes the lengths actually computable.
- **MDL vs. Bayes**: closely related (the correspondence above), but MDL needs no belief that any model is "true" — it is about compression, not truth.
- **"Description length" is not file size**: no file is literally compressed. Code lengths are computed from probabilities via $-\log P$.
- **Crude vs. refined MDL**: two-part codes are the teaching version; normalized maximum likelihood is the principled version. Papers saying "MDL" may mean either.

## Where To Go Next

- Read [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) for the theoretical foundation of description length.
- Read [MDL Weights](https://aipedia.org/mdl-weights) for Hinton's application of MDL to neural network regularization.
- Read [VAE](https://aipedia.org/vae) to see description-length thinking (the KL term) inside a modern deep generative model.
- Read [Variational Lossy Autoencoder](https://aipedia.org/variational-lossy-autoencoder) for a deeper look at what codes and latents actually capture.


# Machine Super Intelligence

> Shane Legg's PhD thesis formalizing universal intelligence and the AIXI agent

- Type: Misc
- By: Shane Legg
- Year: 2008
- Topics: AGI, Theory, Intelligence, AIXI
- Page: https://aipedia.org/machine-superintelligence

## Resources

- [Machine Super Intelligence](https://www.vetta.org/documents/Machine_Super_Intelligence.pdf): Paper, Shane Legg, PhD thesis, 2008

**Machine Super Intelligence** is Shane Legg's 2008 PhD thesis. It tackles a deceptively simple question — *what is intelligence, mathematically?* — and answers it with a formal definition, plus a proof that a hypothetical agent called **AIXI** is as intelligent as any agent can be.

> This page leans on two ideas worth meeting first: [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) (how "simple" a thing is, measured by the shortest program that produces it) and [Reinforcement Learning](https://aipedia.org/reinforcement-learning) (agents acting in environments to maximize reward).

## Why Students Should Care

- This is the closest thing AI theory has to a *definition* of intelligence — not a vibe, an equation.
- Legg went on to co-found DeepMind; these ideas shaped how a generation of researchers thinks about AGI.
- The thesis connects compression, prediction, and intelligence — the same connection that helps explain why language models trained to predict text end up looking smart.

## The Question, In Plain English

Before the math: Legg's proposal is that an agent is intelligent if it **performs well across many different environments**, with a twist — simple environments count more than convoluted ones. A chess engine that only plays chess is narrow; an agent that racks up reward in *any* world you drop it into is intelligent.

## Defining Intelligence

Formally:

$$
\Upsilon(\pi) = \sum_{\mu \in E} 2^{-K(\mu)} V_\mu^\pi
$$

where:

- $\pi$ is an agent (policy)
- $\mu$ is an environment
- $K(\mu)$ is the Kolmogorov complexity of $\mu$
- $V_\mu^\pi$ is the expected reward of $\pi$ in $\mu$

You do not need to memorize the formula. It says: **intelligence is average performance across all computable environments, where simpler environments get exponentially more weight.** The weighting $2^{-K(\mu)}$ is a mathematical version of Occam's razor.

## The AIXI Agent

Given that definition, is there a *best possible* agent? Yes — AIXI:

$$
a^*_t = \arg\max_{a_t} \sum_{o_t r_t} \sum_{\mu \in E} 2^{-K(\mu)} \mu(o_t r_t | a_t h_{<t})
$$

At each step, AIXI:

1. Considers all possible environments (weighted by complexity)
2. Computes expected reward for each action
3. Chooses the action maximizing expected future reward

In plain English: AIXI hedges across every theory of how the world might work, favors the simple theories, and picks whatever action does best on average.

## Interactive Demo

Explore the key concepts from the thesis:

*Interactive demo: https://aipedia.org/machine-superintelligence*

## Solomonoff Induction

How does AIXI predict what happens next? It uses Solomonoff's universal prior:

$$
P(x) = \sum_{p: U(p) = x*} 2^{-|p|}
$$

The probability of observing $x$ is the sum over all programs that output $x$, weighted by their brevity. Short programs dominate — again, Occam's razor made precise. If many short programs produce your observations so far, their shared predictions get high probability.

## Key Results

**Theorem (Optimality)**: AIXI is the most intelligent agent:

$$
\Upsilon(\text{AIXI}) \geq \Upsilon(\pi) \quad \forall \pi
$$

No other agent achieves higher expected performance across all environments.

**Theorem (Incomputability)**: AIXI cannot be computed.

The universal prior requires solving the halting problem, so no real machine can run AIXI. Real systems must approximate. This pair of results is the punchline of the thesis: *perfect* intelligence exists on paper and is provably out of reach in practice.

## The Compression-Intelligence Connection

A key insight: **compression and prediction are equivalent**.

$$
K(x_{1:n}) \approx -\log P(x_{1:n})
$$

A good predictor is a good compressor, and vice versa: if you can predict the next symbol well, you can encode data in few bits, and a short description of data is exactly what a good predictor exploits. This connects AIXI to practical language models, which are trained purely to predict. See [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) and the [MDL Tutorial](https://aipedia.org/mdl-tutorial) for more on this thread.

## Practical Approximations

Real AI systems approximate AIXI through:

- **Bounded computation**: limited search depth
- **Finite environments**: specific domain knowledge
- **Learned priors**: neural networks instead of Solomonoff

Modern LLMs can be viewed as crude AIXI approximations trained on text.

## Implications

- Intelligence *can* be formalized mathematically
- Optimal intelligence requires universal prediction
- Real AI must make tractability/optimality tradeoffs
- Scaling leads toward AIXI-like behavior

## Common Confusion

- **AIXI vs. AGI**: AIXI is a mathematical ideal, not a buildable system. It defines the ceiling, not a blueprint.
- **"Optimal" does not mean "achievable"**: the thesis proves AIXI is best *and* that it is incomputable. Both theorems matter; quoting only the first is misleading.
- **Kolmogorov complexity vs. ordinary complexity**: $K(\mu)$ is the length of the shortest program describing $\mu$ — a precise quantity (itself uncomputable), not an informal notion of "complicated."

## Where To Go Next

- Read [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) for the simplicity measure at the heart of the definition.
- Read [Reinforcement Learning](https://aipedia.org/reinforcement-learning) for the agent-environment-reward framing AIXI lives in.
- Read the [MDL Tutorial](https://aipedia.org/mdl-tutorial) for the compression-as-learning idea in a practical setting.
- Read [Scaling Laws](https://aipedia.org/scaling-laws) to see how "better prediction with more compute" plays out in real models.


# Quantifying the Rise and Fall of Complexity in Closed Systems

> The Coffee Automaton paper formalizing how complexity peaks then declines

- Type: Misc
- By: Aaronson, Carroll & Ouellette
- Year: 2014
- Topics: Complexity, Entropy, Automata, Theory
- Page: https://aipedia.org/coffee-automaton

## Resources

- [Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton](https://arxiv.org/abs/1405.6903): Paper, Aaronson, Carroll & Ouellette, 2014

**The Coffee Automaton** paper by Aaronson, Carroll, and Ouellette takes an everyday observation — cream stirred into coffee forms beautiful swirls before dissolving into boring uniformity — and turns it into a theorem: in closed systems, complexity provably rises, peaks, and falls, even while entropy only rises.

> This page is the formal follow-up to [The First Law of Complexodynamics](https://aipedia.org/complexodynamics), which poses the puzzle in blog form. Read that first for the setup, and [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) for the measurement tool both pages rely on.

## Why Students Should Care

- It demonstrates how to take a vague idea ("the universe got interesting before it gets boring") and make it precise enough to prove things about.
- The measurement problem it solves — separating *meaningful structure* from *random noise* — is the same problem behind compression-based views of learning like [MDL](https://aipedia.org/mdl-tutorial).
- The rise-and-fall pattern is a useful lens on neural network training dynamics (see below).

## The Model

Consider a cellular automaton initialized in a "simple" state — the digital version of cream layered on top of coffee:

$$
\text{Initial: } \underbrace{1111...1111}_{n/2}\underbrace{0000...0000}_{n/2}
$$

Cells then mix under simple local update rules. As the system evolves, it passes through intricate intermediate states before reaching a fully mixed equilibrium. The question: can we *prove* the middle is more complex than either end?

## Measuring Complexity: Sophistication

Plain [Kolmogorov complexity](https://aipedia.org/kolmogorov-complexity) will not work here — a fully mixed random state has the *highest* Kolmogorov complexity, but it is obviously not "complex" in the interesting sense. The paper instead uses **sophistication**:

$$
\text{Soph}(x) = \min\{K(S) : x \in S, K(x|S) \geq \log|S| - O(1)\}
$$

In words: find the simplest *set* $S$ that captures $x$'s structure, such that within $S$, $x$ looks like a typical random member. The sophistication of $x$ is the description length of that set.

The takeaway: sophistication counts only the "interesting" part of a description — the structure — and charges nothing for the residual randomness. Random strings have high $K$ but low sophistication, because the set "all strings of length n" is simple.

## Interactive Demo

Watch complexity rise and fall in a cellular automaton:

*Interactive demo: https://aipedia.org/coffee-automaton*

## The Main Theorem

For a broad class of reversible cellular automata, there exist times $t_1$ and $t_2$ such that:

$$
\text{Soph}(x_{t_1}) \gg \text{Soph}(x_0)
$$

$$
\text{Soph}(x_{t_2}) \ll \text{Soph}(x_{t_1})
$$

Complexity provably rises then falls. The blog-post intuition becomes a theorem once the right complexity measure is in hand.

## The Three Phases

| Phase | State | Entropy | Complexity |
|-------|-------|---------|------------|
| Initial | Ordered layers | Low | Low |
| Mixing | Intricate patterns | Medium | **High** |
| Equilibrium | Uniform random | High | Low |

## Why This Happens

**Initial state**: described by a short program ("n/2 ones, n/2 zeros") — simple.

**Mixing state**: the partly-mixed patterns have real structure (tendrils, boundaries) that any faithful description must spell out — complex.

**Final state**: described as "a sample from the uniform distribution" — simple again, because all the detail is now pure noise that sophistication does not charge for.

The set of intermediate states is "special" — neither trivially ordered nor purely random.

## Connection to Learning

A similar arc appears in neural network training:

1. **Early**: random weights, simple predictions
2. **Middle**: complex feature detectors emerge
3. **Late**: simplified, generalizable representations

Loss landscapes may follow similar complexity dynamics — a suggestive analogy, though not something this paper proves.

## Compression Perspective

Any state's description splits into two parts:

$$
K(x) = K(\text{structure}) + K(\text{noise}|\text{structure})
$$

At peak complexity:

- Non-trivial structure to describe
- Non-trivial variation around that structure

At equilibrium:

- The structure is just "uniform distribution" (simple)
- Everything else is noise

Sophistication tracks only the first term — which is exactly why it peaks in the middle.

## Common Confusion

- **Complexity is not entropy**: entropy rises monotonically the whole time; sophistication rises *and falls*. The final state has maximum entropy and near-minimum sophistication.
- **This paper vs. [Complexodynamics](https://aipedia.org/complexodynamics)**: Aaronson's blog post poses the question and sketches "complextropy"; this paper builds the concrete automaton model and proves the rise-and-fall result using sophistication.
- **Random does not mean sophisticated**: high Kolmogorov complexity means incompressible, not structured. Sophistication was chosen precisely to filter randomness out.
- **"Closed system" matters**: no outside input is adding order — the complexity peak emerges purely from internal mixing dynamics.

## Where To Go Next

- Read [The First Law of Complexodynamics](https://aipedia.org/complexodynamics) for the original puzzle in accessible blog form.
- Read [Kolmogorov Complexity](https://aipedia.org/kolmogorov-complexity) for the foundation under $K(\cdot)$ and sophistication.
- Read [MDL Tutorial](https://aipedia.org/mdl-tutorial) for the structure-plus-noise decomposition applied to model selection.
- Read [MDL Weights](https://aipedia.org/mdl-weights) for compression thinking applied to neural networks.


# CS231n: CNNs for Visual Recognition

> Stanford's foundational course on deep learning for computer vision

- Type: Misc
- By: Stanford
- Year: 2015
- Topics: Deep learning, CNNs, Vision, Course
- Page: https://aipedia.org/cs231n

## Resources

- [CS231n: Deep Learning for Computer Vision](https://cs231n.stanford.edu/): Course, Stanford University
- [CS231n course notes](https://cs231n.github.io/): Article, Written guides
- [Lecture videos (Spring 2017)](https://www.youtube.com/playlist?list=PL3FW7Lu3i5JvHM8ljYj-zLfQRF3EO8sYv): Video, Full lecture series

**CS231n** is Stanford's renowned course on Convolutional Neural Networks for Visual Recognition. It builds deep learning up from first principles — starting with basic classifiers, working through neural networks and [backpropagation](https://aipedia.org/backpropagation), and ending at state-of-the-art architectures.

> This page is about a **course**, not a paper or an architecture. If you want a specific architecture, jump straight to [AlexNet](https://aipedia.org/alexnet) or [ResNet](https://aipedia.org/resnet).

## Why Students Should Care

- CS231n is arguably the most popular on-ramp into deep learning: lectures, notes, and assignments are all **free online**.
- It teaches the skill frameworks hide from you — implementing [backpropagation](https://aipedia.org/backpropagation) by hand — which pays off every time you debug a model.
- Its syllabus doubles as a reading map for this wiki: many pages here ([AlexNet](https://aipedia.org/alexnet), [ResNet](https://aipedia.org/resnet), [Dropout](https://aipedia.org/dropout), [GAN](https://aipedia.org/gan)) are covered in the course.

## Course Philosophy

The course emphasizes:

1. **First principles understanding** — implementing backpropagation from scratch
2. **Mathematical foundations** — understanding why techniques work, not just how
3. **Practical experience** — hands-on assignments with real datasets

## Core Topics

### Image Classification Pipeline

The course starts with the fundamental task: mapping pixels to categories. In plain English, a classifier is a function that takes an image (a grid of numbers) and outputs one of $K$ labels:

$$
f: \mathbb{R}^{H \times W \times C} \rightarrow \{1, 2, ..., K\}
$$

Students implement k-NN, linear classifiers, and loss functions before touching a neural network — so that when networks arrive, they feel like a natural upgrade rather than magic.

### Backpropagation

The heart of deep learning: computing gradients through computational graphs by chaining local derivatives.

$$
\frac{\partial L}{\partial w} = \frac{\partial L}{\partial y} \cdot \frac{\partial y}{\partial w}
$$

That is just the chain rule — but implementing it from scratch, gate by gate, builds intuition that frameworks like PyTorch abstract away. See [Backpropagation](https://aipedia.org/backpropagation) for the full treatment.

### CNN Architectures

The course walks through the landmark architectures in order:

- **LeNet** → **[AlexNet](https://aipedia.org/alexnet)** → **VGG** → **GoogLeNet** → **[ResNet](https://aipedia.org/resnet)**

Each step introduces a key concept: depth, skip connections, inception modules. Reading them in sequence shows *why* each idea was invented, not just what it is.

## Interactive Overview

Explore the course structure and key concepts:

*Interactive demo: https://aipedia.org/cs231n*

## Key Assignments

| Assignment | Skills Developed |
|-----------|------------------|
| k-NN & SVM | Vectorized numpy, loss functions |
| Neural Networks | Backprop, modular design |
| CNNs | Conv layers, architectures |
| RNNs & Attention | Sequence modeling |
| GANs | Generative modeling |

## Common Confusion

- **CS231n is a course, not a model or a paper.** Citing "CS231n" means citing teaching material, not a research result.
- **The website vs. the notes:** cs231n.stanford.edu is the official course page; cs231n.github.io hosts the written lecture notes. Both are freely accessible.
- **CNNs vs. deep learning in general:** the course focuses on *vision*. For sequences and language, see [Understanding LSTMs](https://aipedia.org/understanding-lstms) or [Transformer](https://aipedia.org/transformer).

## Where To Go Next

- Read [Backpropagation](https://aipedia.org/backpropagation) for the algorithm at the heart of the course
- Read [AlexNet](https://aipedia.org/alexnet) and [ResNet](https://aipedia.org/resnet) for the landmark architectures it covers
- Read [Dropout](https://aipedia.org/dropout) for the regularization technique used throughout the assignments
- Read [GAN](https://aipedia.org/gan) for the generative modeling covered in the final assignment

## Key Insight

CS231n's lasting value isn't specific architectures — it's building intuition for how neural networks learn hierarchical representations from data.


# Kolmogorov Complexity and Algorithmic Randomness

> Measuring how short the best description of an object can be

- Type: Misc
- By: Shen, Uspensky & Vereshchagin
- Year: 2017
- Topics: Complexity, Information theory, Computation, Theory
- Page: https://aipedia.org/kolmogorov-complexity

## Resources

- [Kolmogorov Complexity and Algorithmic Randomness](https://www.lirmm.fr/~ashen/kolmbook-eng-scan.pdf): Book, Shen, Uspensky & Vereshchagin

**Kolmogorov complexity** asks a surprisingly intuitive question: how short is the shortest program that can describe a given object? If a string has a short description, it is structured. If it has no shorter description than writing it out directly, it is close to random.

> This page is theory-heavy. If you mainly want the ML connection, jump to **Applications to AI** and then read [MDL Tutorial](https://aipedia.org/mdl-tutorial).

## A Simple Example

Compare these two strings:

- `0101010101010101`
- `0110100011101010`

The first one has an obvious pattern: "print `01` eight times." The second might have no noticeably shorter description than listing the bits exactly.

That is the core intuition behind Kolmogorov complexity.

## Core Definition

The **Kolmogorov complexity** $K(x)$ of a string $x$ is the length of the shortest program that outputs $x$:

$$
K(x) = \min \{|p| : U(p) = x\}
$$

where $U$ is a universal Turing machine and $|p|$ is the program length in bits.

In words: **complexity = shortest exact description**.

## What This Means Intuitively

- Repetitive objects have low complexity
- Highly structured objects can have low complexity even if they are long
- Truly patternless objects have high complexity

This is different from difficulty or usefulness. A random string can have **high complexity** even though it has no interesting structure.

## Key Properties

### Most strings are incompressible

Most length-$n$ strings do not have short descriptions:

$$
|\{x : |x| = n, K(x) < n - c\}| < 2^{n-c}
$$

That formalizes the idea that randomness is common and compression is special.

### Complexity is machine-independent up to a constant

If you switch from one universal machine to another, the exact number changes only by a fixed constant:

$$
|K_U(x) - K_V(x)| \leq c_{UV}
$$

So the concept is robust even though the exact encoding details vary.

## Interactive Demo

Explore how different strings have different Kolmogorov complexities:

*Interactive demo: https://aipedia.org/kolmogorov-complexity*

## Algorithmic Randomness

A string is **algorithmically random** if it cannot be compressed much:

$$
K(x) \geq |x| - O(1)
$$

That does not mean "generated by a random process" in the everyday sense. It means "has no much shorter exact description."

## Why We Cannot Compute It Exactly

One of the deepest results is that Kolmogorov complexity is **uncomputable**.

There is no general algorithm that takes any string and always returns the true shortest program for it. This is closely related to the halting problem.

## Conditional Complexity

Sometimes you already know another object $y$. Then the relevant question is how many extra bits are needed to describe $x$ given $y$:

$$
K(x|y) = \min \{|p| : U(p, y) = x\}
$$

This leads to an information-style view of shared structure.

## Applications to AI

Kolmogorov complexity motivates several important ideas:

- [MDL Tutorial](https://aipedia.org/mdl-tutorial): prefer models that compress the data well
- [MDL Weights](https://aipedia.org/mdl-weights): connect description length to regularization
- [Machine Super Intelligence](https://aipedia.org/machine-superintelligence): use algorithmic ideas in idealized intelligence
- Occam's razor: simpler explanations are preferred because they need shorter descriptions

## Common Confusion

- High complexity does **not** mean meaningful structure
- Randomness can increase complexity
- The quantity is theoretically powerful even though it is not exactly computable

## The Chain Rule

One useful identity is:

$$
K(x, y) = K(x) + K(y|x) + O(\log K(x, y))
$$

This says the complexity of a pair is roughly:

- describe the first object
- then describe the second using the first as context

## What To Remember

- Kolmogorov complexity measures the shortest exact description
- Compression and randomness are two sides of the same idea
- The concept is foundational for MDL, algorithmic information theory, and theoretical AI