Foundations — 10 Documents

y = f(x; θ)

Input:  "Hello, world!"
Tokens: ["Hello", ",", " world", "!"]
IDs:    [15496, 11, 995, 0]

Token ID:  [15496]      →  Embedding:  [0.12, -0.45, 0.78, ..., 0.33]
Dimension:   1          →  Dim:        d_model (e.g., 4096)

Q = X * W_Q
K = X * W_K
V = X * W_V

Score(i, j) = Q_i · K_j

Attention(Q, K, V) = softmax(QK^T / √d_k) * V

Mask matrix:
Token 0: [1, 0, 0, 0]
Token 1: [1, 1, 0, 0]
Token 2: [1, 1, 1, 0]
Token 3: [1, 1, 1, 1]

# Pseudo for 8 heads
head_0 = attention(Q_0, K_0, V_0)  # Syntax relationships?
head_1 = attention(Q_1, K_1, V_1)  # Entity relationships?
head_2 = attention(Q_2, K_2, V_2)  # Long-distance dependencies?
# ... etc

MultiHead(Q, K, V) = Concat(head_0, ..., head_h) * W_O

FFN(x) = act(x * W_1 + b_1) * W_2 + b_2

LayerNorm(x) = γ * (x - μ) / √(σ² + ε) + β

RMSNorm(x) = x / √(mean(x²) + ε) * γ

Input:  [token_1, token_2, ..., token_n]
            ↓
        [Embeddings + Positional Encoding]
            ↓
        ┌───────────────────────┐
        │ Transformer Layer x N  │  (repeated L times)
        │                       │
        │   ┌─────────────────┐ │
        │   │ RMSNorm         │ │
        │   │   → Self-Attn   │ │  (causal mask)
        │   │   → Residual +  │ │
        │   └─────────────────┘ │
        │   ┌─────────────────┐ │
        │   │ RMSNorm         │ │
        │   │   → FFN (MLP)   │ │
        │   │   → Residual +  │ │
        │   └─────────────────┘ │
        └───────────────────────┘
            ↓
        [RMSNorm] → [LM Head] (linear projection to vocab)
            ↓
        Token probabilities

L = Σ log P(x_t | x_<t, θ)

Web crawl:     60-70%
Books:         10-15%
Code:          10-15%
Academic:      5-10%
Other:         5%

User: "Explain what a transformer is."
Assistant: "A transformer is a neural network architecture..."

Objective = E[r(x, y)] - β * KL(π_RL || π_SFT)

L_DPO = -E[log σ(β * log(π_θ(y_w | x) / π_ref(y_w | x)) - β * log(π_θ(y_l | x) / π_ref(y_l | x)))]

Prompt: "The capital of France is"
→ "Paris. It is known for the Eiffel Tower, which was built in 1889."

User: "What is the capital of France?"
Assistant: "The capital of France is Paris."

# LLaMA 3 Instruct
<|begin_of_text|><|start_header_id|>user<|end_header_id|>
What is 2+2?<|eot_id|><|start_header_id|>assistant<|end_header_id|>
4<|eot_id|>

# Mistral Instruct
<s>[INST] What is 2+2? [/INST] 4</s>

# ChatML (GPT-4, Qwen)
<|im_start|>user
What is 2+2?<|im_end|>
<|im_start|>assistant
4<|im_end|>

Memory ≈ P * bytes_per_param

For each token:
  router(embedding) → probabilities over 8 experts
  top-2: expert_3 (0.6), expert_7 (0.3)
  output = 0.6 * expert_3(token) + 0.3 * expert_7(token)

Compute-optimal: 20 tokens of data per parameter

token = argmax(probabilities)

token = sample(probabilities)

Top-k tokens → renormalize → sample

Cumulative probability sorted descending.
Keep tokens until sum ≥ p.
Renormalize → sample from this set.

logits_scaled = logits / temperature
probabilities = softmax(logits_scaled)

threshold = min_p * max_probability
Keep tokens with prob ≥ threshold

Repeat penalty: 1.0–1.2 (1.0 = no penalty)
Higher penalty = less repetition

Without KV cache:
  Step 1: compute attn over [t1]        → O(1)
  Step 2: compute attn over [t1, t2]    → O(2)
  Step N: compute attn over [t1..tN]     → O(N)
  Total: O(N²)

With KV cache:
  Step 1: compute K1, V1, store → produce token 1
  Step 2: load K1,V1, compute K2,V2, store → produce token 2
  Step N: load K1..K(N-1), compute KN,VN, store → produce token N
  Total: O(N)

KV cache per token = 2 (K+V) * d_model * num_layers * 2 bytes (FP16)

Draft model (fast, e.g., 1B): generates 5 candidate tokens
Target model (slow, e.g., 70B): evaluates all 5 in a single forward pass
→ Accept correct candidates, reject and resample at rejection point

"Hello, world!" → ["Hello", ",", " world", "!"]
"unbelievable" → ["un", "believe", "able"]
"ChatGPT" → ["Chat", "G", "PT"]

vector("king") - vector("man") + vector("woman") ≈ vector("queen")

Translate to French: "Hello, how are you?"
→ "Bonjour, comment allez-vous ?"

Classify the sentiment:
Text: "This movie was amazing!" → Positive
Text: "I hated every minute" → Negative
Text: "It was okay, I guess" →

Q: Roger has 5 tennis balls. He buys 2 more cans of tennis balls.
   Each can has 3 balls. How many does he have now?
A: Roger starts with 5 balls. 2 cans × 3 balls = 6 balls.
   5 + 6 = 11. The answer is 11.
Q: The cafeteria had 23 apples. They used 20 for lunch and bought 6 more.
   How many apples do they have?
A:

You are a helpful AI assistant. You respond concisely and accurately.
If you don't know the answer, say so. Always cite sources when possible.

Generate a JSON object with fields: name, age, email.
Example: {"name": "Alice", "age": 30, "email": "alice@example.com"}
Input: Bob is 25 years old, his email is bob@test.com

You are an expert physicist explaining quantum mechanics to a 10-year-old.
Use simple analogies and no math.

Do NOT mention politics. Do NOT use technical jargon.

User: "What was Q3 revenue?"
        ↓
  [Retrieval: search "Q3 revenue report 2024"]
        ↓
  [Context: "Q3 revenue was $2.1B..."]
        ↓
  Model generates answer based on context

Loss = α * KL(student_logits || teacher_logits) + (1-α) * CrossEntropy(student, hard_labels)

Layer 1:
  [LLaMA 3] → Response A
  [Mistral] → Response B
  [Qwen]   → Response C

Layer 2 (optional):
  [LLaMA 3] sees A+
📄 Machine Learning — 1961 lines
A comprehensive, deeply technical exploration of machine learning — from classical supervised and unsupervised methods to modern self-supervised learning, reinforcement learning, and the statistical foundations that underpin them all.
AgentBERTCLIPDeploymentDiffusionEnsembleEvaluationGPUInferenceInterpretability
1. Foundations of Machine Learning
1.1 What is Machine Learning?
Machine learning (ML) is a subset of artificial intelligence focused on algorithms that improve their performance on a task through experience (data). Formally, a computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance on T, as measured by P, improves with experience E (Mitchell, 1997).
The core paradigm is to learn a function f: X → Y that maps inputs x ∈ X to outputs y ∈ Y, parameterized by a set of learnable parameters θ:
y = f(x; θ)


The learning process finds the optimal parameters θ* that minimize a loss function L over the training data:
θ* = argmin_θ Σ_i L(y_i, f(x_i; θ))


1.2 Categories of Machine Learning



Category
Data
Labels
Goal




Supervised Learning
x_i, y_i pairs
Required
Predict y from x


Unsupervised Learning
x_i only
None
Discover structure in x


Semi-Supervised Learning
Few labeled, many unlabeled
Partial
Leverage unlabeled data


Self-Supervised Learning
x_i only (with pretext tasks)
Auto-generated
Learn representations


Reinforcement Learning
States, actions, rewards
Reward signal
Learn optimal policy



1.3 The Machine Learning Pipeline
A standard ML pipeline consists of:

Problem definition: Formulate the task, define inputs/outputs
Data collection: Gather representative samples
Data preprocessing: Clean, normalize, augment
Feature engineering/selection: Extract/select informative features
Model selection: Choose algorithm family
Training: Optimize parameters on training data
Evaluation: Assess on held-out data
Hyperparameter tuning: Optimize meta-parameters
Deployment: Serve model in production
Monitoring: Track performance drift

1.4 Inductive Bias
Every ML algorithm has an inductive bias — a set of assumptions that allows it to generalize beyond training data. Understanding inductive bias is critical for model selection:

Linear models: Assume linear separability
Decision trees: Assume axis-aligned decision boundaries
k-NN: Assume similarity in input space implies similar outputs
Neural networks: Assume compositional hierarchies (via depth)
SVM with RBF kernel: Assume smoothness in transformed space

2. Supervised Learning
Supervised learning is the most mature and widely deployed category of ML. Given a dataset of input-output pairs {(x_i, y_i)}_i=1^N, the goal is to learn a mapping from inputs to outputs.
2.1 Regression
Regression predicts a continuous output y ∈ ℝ.
2.1.1 Linear Regression
The simplest regression model assumes a linear relationship:
y = w^T x + b = Σ_j w_j x_j + b


where w are weights and b is bias.
Ordinary Least Squares (OLS) minimizes the mean squared error (MSE):
L(w, b) = (1/N) Σ_i (y_i - (w^T x_i + b))²


The closed-form solution (for the weights) is:
w = (X^T X)^{-1} X^T y


where X is the N × d design matrix. This requires X^T X to be invertible (full column rank).
Computational complexity: O(Nd² + d³) for the closed form, dominated by matrix inversion.
Limitations:

- Assumes linear relationship

- Sensitive to outliers (since MSE squares errors)

- Assumes homoscedasticity (constant variance of errors)

- Features should be uncorrelated (multicolinearity inflates variance)
Diagnostics:

- R² (coefficient of determination): 1 - SS_res / SS_tot

- Adjusted R²: penalizes adding irrelevant features

- F-test for overall significance

- t-tests for individual coefficients
2.1.2 Ridge Regression (L2 Regularization)
Adds an L2 penalty to prevent overfitting and handle multicolinearity:
L(w) = (1/N) Σ_i (y_i - w^T x_i)² + λ ||w||_2²


Closed form: w = (X^T X + λI)^{-1} X^T y
The λI term ensures X^T X + λI is always invertible, even when X^T X is singular. Ridge shrinks coefficients toward zero but never exactly to zero.
2.1.3 Lasso Regression (L1 Regularization)
Uses L1 penalty for automatic feature selection:
L(w) = (1/N) Σ_i (y_i - w^T x_i)² + λ ||w||_1


No closed form — solved via coordinate descent or subgradient methods. Lasso drives coefficients exactly to zero (sparsity). The λ parameter controls sparsity: larger λ → more zeros.
Elastic Net combines L1 and L2:
L(w) = MSE + λ₁||w||₁ + λ₂||w||₂²


2.1.4 Polynomial Regression
Extends linear regression by adding polynomial features:
y = w_0 + w_1 x + w_2 x^2 + ... + w_p x^p


Still linear in the parameters (w), but nonlinear in the input (x). Higher degree → more flexibility but risk of overfitting.
2.1.5 Support Vector Regression (SVR)
SVR finds a function f(x) = w^T x + b that deviates from the actual targets by at most ε, while being as flat as possible:
minimize (1/2)||w||² + C Σ_i (ξ_i + ξ_i*)


subject to:
y_i - (w^T x_i + b) ≤ ε + ξ_i
(w^T x_i + b) - y_i ≤ ε + ξ_i*
ξ_i, ξ_i* ≥ 0


Points within ε of the prediction contribute no loss (ε-insensitive tube). The kernel trick allows nonlinear SVR.
2.2 Classification
Classification predicts a discrete label y ∈ {1, ..., K}.
2.2.1 Logistic Regression
Despite the name, logistic regression is a classification algorithm. It models the probability of a binary outcome:
P(y=1|x) = σ(w^T x + b) = 1 / (1 + e^{-(w^T x + b)})


where σ is the sigmoid/logistic function.
Loss: Binary cross-entropy (log loss):
L(w) = -(1/N) Σ_i [y_i log(ŷ_i) + (1-y_i) log(1-ŷ_i)]


Multi-class extension (Softmax Regression):
P(y=k|x) = exp(w_k^T x + b_k) / Σ_j exp(w_j^T x + b_j)


Loss: categorical cross-entropy: L = -Σ_k y_k log(ŷ_k)
Properties:

- Well-calibrated probabilities (if well-specified)

- Linear decision boundary

- Can be regularized (L1, L2, Elastic Net)

- Fast to train (convex optimization via Newton-CG, L-BFGS, SGD)
2.2.2 k-Nearest Neighbors (k-NN)
A non-parametric, instance-based learner:

Training: Store all training examples
Inference: For a new point x, find k closest training points (by Euclidean distance or other metric), vote on label (classification) or average values (regression)

Key hyperparameters:

- k: Number of neighbors (smaller → more complex, larger → smoother)

- Distance metric: Euclidean, Manhattan, Minkowski, cosine

- Weighting: Uniform or distance-weighted
Properties:

- No training phase (lazy learning)

- Decision boundary is piecewise linear

- Sensitive to irrelevant features (curse of dimensionality)

- O(Nd) inference cost (can be reduced with KD-trees, ball trees, ANN)
Curse of dimensionality: In high dimensions, distances become nearly uniform, making k-NN ineffective. The volume of space grows exponentially with dimension.
2.2.3 Naive Bayes
A probabilistic classifier based on Bayes' theorem with the naive assumption of conditional independence:
P(y|x) = P(y) * Π_j P(x_j|y) / P(x)


Variants:

- Gaussian NB: P(x_j|y) ~ N(μ_{j,y}, σ_{j,y}²)

- Multinomial NB: For discrete counts (text classification)

- Bernoulli NB: For binary features
Properties:

- Fast to train and predict

- Works well with high-dimensional data (text)

- Strong independence assumption rarely holds, but often works anyway

- Well-calibrated for binary classification
2.2.4 Support Vector Machines (SVM)
SVM finds the maximum-margin hyperplane that separates classes:
maximize 2/||w||  (margin width)
subject to y_i(w^T x_i + b) ≥ 1, ∀i


Primal problem:
minimize (1/2)||w||²
subject to y_i(w^T x_i + b) ≥ 1


Soft-margin SVM (allows misclassifications via slack variables):
minimize (1/2)||w||² + C Σ_i ξ_i
subject to y_i(w^T x_i + b) ≥ 1 - ξ_i, ξ_i ≥ 0


C controls the trade-off between margin width and training error.
Dual formulation (using Lagrange multipliers α_i):
maximize Σ_i α_i - (1/2) Σ_i Σ_j α_i α_j y_i y_j (x_i·x_j)
subject to 0 ≤ α_i ≤ C, Σ_i α_i y_i = 0


Decision function: f(x) = sign(Σ_i α_i y_i (x_i·x) + b)
The Kernel Trick: Replace dot products (x_i·x_j) with a kernel function K(x_i, x_j) that computes dot products in an implicit high-dimensional feature space:

Linear: K(x, z) = x^T z
Polynomial: K(x, z) = (γ x^T z + r)^d
RBF (Gaussian): K(x, z) = exp(-γ ||x - z||²)
Sigmoid: K(x, z) = tanh(γ x^T z + r)

The RBF kernel corresponds to an infinite-dimensional feature space. γ controls the influence radius of each support vector.
Properties:

- Effective in high-dimensional spaces

- Memory efficient (uses support vectors only)

- Versatile via kernel trick

- Requires careful hyperparameter tuning (C, γ)

- No direct probability estimates (Platt scaling needed)

- O(N²) to O(N³) training time with kernels
SVM vs Logistic Regression:



Aspect
SVM
Logistic Regression




Objective
Maximum margin
Maximum likelihood


Output
Distance to hyperplane
Calibrated probabilities


Kernel trick
Natural
Requires explicit feature expansion


Outliers
Less sensitive (hinge loss)
More sensitive


Calibration
Needs Platt scaling
Naturally calibrated



2.2.5 Decision Trees
Decision trees partition the feature space into axis-aligned regions, each assigned a prediction (label or value). They are built recursively:

Select the best feature and split point to maximize information gain
Split the data
Repeat recursively on each child
Stop when a criterion is met (max depth, min samples per leaf, purity threshold)

Split criteria for classification:

Gini impurity: G = 1 - Σ_k p_k² where p_k is proportion of class k in a node
Entropy: H = -Σ_k p_k log(p_k)
Misclassification error: E = 1 - max_k p_k

Information gain: IG = H(parent) - Σ_c (N_c/N) H(child_c)
Split criteria for regression:

MSE: (1/N) Σ_i (y_i - ȳ)²
MAE: (1/N) Σ_i |y_i - ȳ|

Tree hyperparameters:

- max_depth: Maximum depth (controls complexity)

- min_samples_split: Minimum samples to split

- min_samples_leaf: Minimum samples per leaf

- max_features: Features considered per split

- ccp_alpha: Cost-complexity pruning parameter
Pruning: Reduce overfitting by cutting back branches. Cost-complexity pruning finds a subtree that minimizes R(T) + α|T| where R(T) is training error, |T| is number of leaves, and α controls the trade-off.
Properties:

- Interpretable (can be visualized as rules)

- No feature scaling needed

- Handles mixed data types

- Non-linear, non-parametric

- High variance (small changes in data → different tree)

- Prone to overfitting without pruning
2.2.6 Random Forests
Random forests are an ensemble of decision trees, each trained on a bootstrap sample of the data with random feature subsets:
for t = 1 to T:
    sample N points with replacement (bootstrap)
    build a decision tree, at each split consider m < d random features
    grow tree to full depth (no pruning)
final prediction = majority vote (classification) or average (regression)


Key insight: Random forests reduce variance by averaging many high-variance, low-bias trees. The error of a random forest is bounded by:
E_rf ≤ ρ * σ² / T


where ρ is average correlation between trees, σ² is individual tree variance, and T is number of trees.
Out-of-bag (OOB) error: Each tree uses ~63.2% of data (bootstrap). The remaining ~36.8% (OOB) can be used as a validation set without held-out data.
Feature importance: Two types:

- Impurity-based: Total reduction in split criterion (Gini/entropy) by each feature, averaged across trees

- Permutation-based: Drop in accuracy when a feature's values are shuffled
Properties:

- Excellent out-of-the-box performance

- Robust to outliers and noise

- Handles high-dimensional data

- Provides feature importance

- Cannot extrapolate beyond training range

- Large model size (many trees)

- Slower inference than single tree
2.2.7 Gradient Boosting Machines (GBM)
Gradient boosting builds an ensemble sequentially, where each new tree corrects errors of the previous ensemble:
F_0(x) = argmin_γ Σ_i L(y_i, γ)
for m = 1 to M:
    r_im = -[∂L(y_i, F(x_i)) / ∂F(x_i)]_F = F_{m-1}  (pseudo-residuals)
    fit a tree h_m to pseudo-residuals
    find optimal step size: ρ_m = argmin_ρ Σ_i L(y_i, F_{m-1}(x_i) + ρ h_m(x_i))
    F_m(x) = F_{m-1}(x) + ν ρ_m h_m(x)


where ν is the learning rate (shrinkage).
Key hyperparameters:

- n_estimators (M): Number of boosting rounds

- learning_rate (ν): Shrinkage factor (smaller → more robust, needs more trees)

- max_depth: Typically 3-8 (shallower than random forest trees)

- subsample: Row sampling for stochastic gradient boosting

- min_samples_leaf: Minimum samples per leaf

- max_features: Column sampling
Loss functions:

- Regression: L2 (MSE), L1 (MAE), Huber, Quantile

- Classification: Deviance (log loss), Exponential, Binomial
2.2.8 XGBoost
XGBoost (Extreme Gradient Boosting) is an optimized implementation of gradient boosting with several innovations:
1. Regularized objective:
L = Σ_i l(y_i, ŷ_i) + Σ_k [γT_k + (1/2)λ||w_k||² + α||w_k||₁]


where T_k is number of leaves in tree k, w_k are leaf weights.
2. Second-order approximation (Newton boosting):
Uses both gradient and Hessian (second derivative) for better convergence:
L ≈ Σ_i [g_i f(x_i) + (1/2) h_i f(x_i)²] + Ω(f)


where g_i = ∂L(y_i, ŷ)/∂ŷ and h_i = ∂²L(y_i, ŷ)/∂ŷ².
3. Weighted quantile sketch: Efficient histogram-based split finding for large data.
4. Column block structure: Data is pre-sorted into blocks for parallel computation.
5. Column sub-sampling: Reduces overfitting and speeds computation.
6. Sparsity-aware split finding: Handles missing values natively (learns default direction).
7. Built-in cross-validation and early stopping.
8. System optimizations: Cache-aware access, out-of-core computation, distributed training.
Hyperparameters:

- max_depth: Default 6

- learning_rate (eta): Default 0.3

- subsample: Default 1.0

- colsample_bytree, colsample_bylevel, colsample_bynode

- min_child_weight: Minimum sum of instance weight (Hessian) in a child

- gamma: Minimum loss reduction required to split

- lambda (L2), alpha (L1): Regularization on leaf weights

- tree_method: 'auto', 'exact', 'approx', 'hist', 'gpu_hist'
XGBoost vs Standard GBM:



Feature
Standard GBM
XGBoost




Regularization
None
L1 + L2 on leaf weights


Tree building
Greedy, level-wise
Level-wise (default) or histogram


Missing values
Requires imputation
Learned default direction


Parallelism
Limited
Feature parallelism via column block


Second-order
No
Yes (Newton)


Cross-validation
Manual
Built-in



2.2.9 LightGBM
LightGBM (Light Gradient Boosting Machine) focuses on efficiency and scalability:
Key innovations:
1. Gradient-based One-Side Sampling (GOSS): Retains instances with large gradients (under-trained) and randomly samples instances with small gradients (well-trained). This focuses the algorithm on the hardest examples.
2. Exclusive Feature Bundling (EFB): Bundles mutually exclusive features (features that rarely take non-zero values simultaneously) to reduce dimensionality.
3. Leaf-wise tree growth: Unlike level-wise growth (XGBoost default), LightGBM grows the leaf with the largest loss reduction, leading to deeper, more asymmetric trees with faster convergence.
3. Unsupervised Learning
Unsupervised learning finds hidden patterns, structure, or representations in unlabeled data.
3.1 Clustering
Clustering partitions data into groups (clusters) where intra-cluster similarity is high and inter-cluster similarity is low.
3.1.1 K-Means Clustering
Algorithm:
1. Initialize K centroids μ_1, ..., μ_K (randomly or via k-means++)
2. Repeat until convergence:
   a. Assignment: assign each point to nearest centroid
      c_i = argmin_k ||x_i - μ_k||²
   b. Update: recompute centroids as mean of assigned points
      μ_k = (1/|C_k|) Σ_{i∈C_k} x_i


K-Means++ Initialization:

1. Choose first centroid uniformly at random from data points

2. For each subsequent centroid, choose x_i with probability proportional to D(x_i)² (distance to nearest existing centroid)

3. Repeat until K centroids are chosen
This reduces the chance of poor initial centroids compared to random initialization.
Objective: Minimize within-cluster sum of squares (WCSS):
J = Σ_{k=1}^K Σ_{i∈C_k} ||x_i - μ_k||²


Properties:

- O(N·K·d·I) complexity (I = iterations)

- Converges to local minimum

- Assumes spherical clusters of similar size

- Sensitive to outliers

- Requires K as input
Choosing K:

- Elbow method: Plot WCSS vs K, look for "elbow"

- Silhouette score: s = (b - a) / max(a, b) where a = intra-cluster distance, b = nearest-cluster distance

- Gap statistic: Compare WCSS to null reference distribution

- Davies-Bouldin index: Ratio of within-cluster to between-cluster distances
K-Medoids (PAM): Uses actual data points as centroids (medoids), more robust to outliers.
3.1.2 DBSCAN (Density-Based Spatial Clustering of Applications with Noise)
Parameters:

- ε (eps): Radius for neighborhood

- minPts: Minimum points to form a dense region
Concepts:

- Core point: Has at least minPts points within ε (including itself)

- Border point: Within ε of a core point but has fewer than minPts neighbors

- Noise point: Neither core nor border
Algorithm:
1. For each unvisited point p:
   a. Mark p as visited
   b. Find all points within ε of p (neighbors)
   c. If neighbors < minPts, mark p as noise
   d. Else, create new cluster C, expand cluster:
      i.   Add p to C
      ii.  For each q in neighbors:
           - If q is unvisited, mark visited, find its ε-neighbors
           - If q's ε-neighbors >= minPts, add them to neighbors
           - If q is not in any cluster, add q to C


Properties:

- Does not require K

- Finds arbitrarily shaped clusters

- Robust to outliers

- Deterministic (order-independent for core points)

- Struggles with varying density clusters

- Poor performance in high dimensions (curse of dimensionality)

- ε is sensitive: too small → many noise points; too large → one cluster
HDBSCAN: Hierarchical extension that builds a cluster hierarchy and extracts flat clustering based on cluster stability. More robust to varying densities.
3.1.3 Hierarchical Clustering
Two approaches:
Agglomerative (bottom-up):
1. Start with each point as its own cluster
2. Repeatedly merge the two most similar clusters
3. Stop when K clusters remain or similarity threshold reached


Divisive (top-down):
1. Start with one cluster containing all points
2. Repeatedly split the most heterogeneous cluster
3. Stop when K clusters formed or all clusters pure enough


Linkage criteria (agglomerative):



Linkage
Similarity Definition
Tendency




Single-link
Min distance between clusters
Produces long, chain-like clusters


Complete-link
Max distance between clusters
Produces compact, spherical clusters


Average-link
Average distance between clusters
Balance between single and complete


Ward's
Variance increase when merging
Minimizes within-cluster variance (similar to K-means objective)



Dendrogram: A tree diagram showing merge/split history. Cluster assignment determined by cutting at a chosen height.
Complexity: O(N³) naive, O(N² log N) with priority queues.
3.1.4 Gaussian Mixture Models (GMM)
Models data as a mixture of K Gaussian distributions:
P(x) = Σ_{k=1}^K π_k · N(x | μ_k, Σ_k)


where π_k are mixing coefficients (Σ π_k = 1, π_k ≥ 0).
Parameters: π_k, μ_k, Σ_k for each component k.
EM Algorithm:
E-step: Compute responsibilities γ_{ik} = P(z_i = k | x_i)
          γ_{ik} = π_k · N(x_i | μ_k, Σ_k) / Σ_j π_j · N(x_i | μ_j, Σ_j)

M-step: Update parameters using weighted MLE
          μ_k = Σ_i γ_{ik} x_i / Σ_i γ_{ik}
          Σ_k = Σ_i γ_{ik} (x_i - μ_k)(x_i - μ_k)^T / Σ_i γ_{ik}
          π_k = (1/N) Σ_i γ_{ik}


Properties:

- Soft clustering (probabilistic membership)

- Captures elliptical clusters (full covariance matrix)

- Model selection via BIC/AIC

- Sensitive to initialization

- Can degenerate (singular covariance) with insufficient data
3.2 Dimensionality Reduction
3.2.1 Principal Component Analysis (PCA)
PCA finds orthogonal directions of maximum variance in the data.
Computation:
1. Center the data: X_centered = X - μ
2. Compute covariance matrix: C = (1/N) X_centered^T X_centered
3. Eigendecomposition: C = V Λ V^T
4. Select top k eigenvectors (principal components) by largest eigenvalues
5. Project: X_reduced = X_centered · V_k


Variance explained: λ_i / Σ_j λ_j for component i. Cumulative variance guides k selection.
Properties:

- Linear, orthogonal transformation

- Unsupervised (ignores labels)

- Decorrelates features

- Maximizes variance, which may not align with class separability
SVD Approach: For high-dimensional data (N < d), use SVD instead of eigendecomposition:
X = U Σ V^T
Principal components = V_k
Projected data = U_k Σ_k


Kernel PCA: Uses kernel trick for nonlinear dimensionality reduction:
K_centered = K - 1_N K - K 1_N + 1_N K 1_N
Solve: K_centered α = λ α
Projection: z_i = Σ_j α_j K(x_i, x_j)


Incremental PCA: Processes data in mini-batches for out-of-core computation.
3.2.2 t-SNE (t-Distributed Stochastic Neighbor Embedding)
t-SNE is a nonlinear dimensionality reduction technique optimized for visualization (typically 2D or 3D).
How it works:

Compute pairwise similarities in high-dimensional space using Gaussian kernels:

p_{j|i} = exp(-||x_i - x_j||² / 2σ_i²) / Σ_{k≠i} exp(-||x_i - x_k||² / 2σ_i²)
p_{ij} = (p_{j|i} + p_{i|j}) / 2N  (symmetrized)


Perplexity controls σ_i: Perp(P_i) = 2^{H(P_i)} where H is entropy. Higher perplexity → larger σ.


Initialize low-dimensional points y_i (random or PCA).


Compute low-dimensional similarities using Student's t-distribution (heavy tails prevent crowding):


q_{ij} = (1 + ||y_i - y_j||...
4. Semi-Supervised Learning
Semi-supervised learning leverages a small set of labeled data (X_l, y_l) and a large set of unlabeled data X_u to improve model performance.

4.1 Assumptions

Smoothness assumption: Points close in input space should have similar labels
Cluster assumption: Points in the same cluster likely share a label
Manifold assumption: High-dimensional data lies on a low-dimensional manifold

4.2 Self-Training (Pseudo-Labeling)
1. Train model on labeled data
2. Use model to predict labels for unlabeled data (pseudo-labels)
3. Add high-confidence predictions to labeled set
4. Retrain and repeat


Risk: Error reinforcement — incorrect pseudo-labels compound.
Mitigation: Use confidence thresholds, uncertainty estimation, or agreement across models.
4.3 Co-Training
1. Split features into two independent views (sets)
2. Train separate models on each view
3. Each model labels unlabeled data for the other
4. Repeat


Requirement: Natural feature split exists (e.g., words from two sources describing same web page).
4.4 Label Propagation
Construct a graph where nodes are labeled + unlabeled points. Propagate labels via graph diffusion:
F = (I - αS)^{-1} Y


where S is the normalized adjacency matrix, Y contains label indicators, and α controls propagation strength.
4.5 Consistency Regularization
Enforce that the model's predictions are consistent under small perturbations of the input:
L = L_supervised(x_l, y_l) + λ * ||f(x_u) - f(x_u + ε)||²


where ε is small noise (Gaussian, dropout, data augmentation). This is the foundation of FixMatch, MixMatch, and other modern SSL methods.
FixMatch:

- For each unlabeled example, compute pseudo-label from weakly-augmented version

- Enforce prediction consistency on strongly-augmented version

- Only keep pseudo-labels above a confidence threshold
5. Self-Supervised Learning
Self-supervised learning (SSL) creates supervision signals from unlabeled data by designing pretext tasks that require understanding of data structure.

5.1 Contrastive Learning
Core idea: Pull representations of similar (positive) pairs together, push dissimilar (negative) pairs apart.
SimCLR (Chen et al., 2020):

Apply random augmentations to each image to create two views
Encode both views with a neural network
Project to a lower-dimensional space
Maximize agreement between positive pairs (same image, different augmentations) using NT-Xent loss (normalized temperature-scaled cross-entropy):

L(i, j) = -log(exp(sim(z_i, z_j)/τ) / Σ_{k≠i} exp(sim(z_i, z_k)/τ))


where sim() is cosine similarity, τ is temperature.
Key components:

- Strong data augmentation

- Large batch size (or memory bank) for many negatives

- Projection head (improves representation quality)

- Temperature scaling
SimCLR vs Other Methods:



Method
Negatives
Architecture
Key Innovation




SimCLR
Batch-level
Standard
NT-Xent, projection head


MoCo
Queue
Momentum encoder
Large negative queue


BYOL
None
Online + target
Bootstrap without negatives


SwAV
None
Online + prototypes
Cluster-based


CLIP
Batch-level
Dual encoders
Image-text pairs



MoCo (Momentum Contrast): Maintains a queue of negative samples and a slowly-updated momentum encoder for consistent representations.
BYOL (Bootstrap Your Own Latent): Uses an online network and a target network (EMA of online) — no negatives needed. The target network provides regression targets that prevent collapse.
SimSiam: Simplified BYOL without momentum encoder — collapse prevented by stop-gradient and predictor.
5.2 Masked Modeling
Masked Autoencoders (MAE, He et al., 2022):

Mask a large portion (75%) of image patches
Encode visible patches only
Decode complete image in pixel space
Loss: MSE on masked patches

This is the vision analog of masked language modeling (BERT).
Spectral SSL: Predict the Fourier coefficients or frequency components of the signal, forcing the model to learn global structure.
5.3 Pretext Tasks
Beyond contrastive and masked modeling, various pretext tasks have been proposed:

Jigsaw puzzles: Solve rearranged image patches (predict permutation)
Rotation prediction: Predict rotation angle (0°, 90°, 180°, 270°)
Relative position: Predict spatial relationship between patches
Colorization: Predict color channels from grayscale
Context prediction: Predict surrounding context from a patch
Video frame order: Predict temporal ordering of frames

6. Reinforcement Learning
Reinforcement learning (RL) studies how agents learn optimal behavior through interaction with an environment, receiving rewards or penalties.

6.1 Markov Decision Processes (MDP)
An MDP is defined by the tuple (S, A, P, R, γ):

S: Set of states
A: Set of actions
P(s'|s, a): Transition probability from s to s' when taking action a
R(s, a, s'): Reward function
γ ∈ [0, 1]: Discount factor

Policy: π(a|s): Probability of taking action a in state s.
Return: G_t = Σ_{k=0}^∞ γ^k R_{t+k+1}
State-value function: V_π(s) = E_π[G_t | S_t = s]
Action-value function (Q-function): Q_π(s, a) = E_π[G_t | S_t = s, A_t = a]
Bellman equations:
V_π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s, a)[R(s, a, s') + γ V_π(s')]
Q_π(s, a) = Σ_{s'} P(s'|s, a)[R(s, a, s') + γ Σ_{a'} π(a'|s') Q_π(s', a')]


Optimal value functions:
V*(s) = max_a Q*(s, a)
Q*(s, a) = Σ_{s'} P(s'|s, a)[R(s, a, s') + γ max_{a'} Q*(s', a')]  (Bellman optimality)


6.2 Value-Based Methods
6.2.1 Q-Learning
An off-policy, model-free RL algorithm that learns the optimal Q-function directly:
Q(s, a) ← Q(s, a) + α[R + γ max_{a'} Q(s', a') - Q(s, a)]



Off-policy: Learns about optimal policy while following a behavior policy (ε-greedy)
Model-free: Doesn't learn transition dynamics
Convergence: Guaranteed in tabular case with sufficient exploration

ε-greedy exploration: With probability ε, choose random action (explore); otherwise choose greedy action argmax_a Q(s, a) (exploit). ε typically decays over time.
6.2.2 Deep Q-Networks (DQN)
DQN (Mnih et al., 2013) uses a neural network to approximate the Q-function:

Input: State (e.g., game screen pixels)
Output: Q-values for each action
Loss: L = E[(r + γ max_{a'} Q(s', a'; θ') - Q(s, a; θ))²]

Two key innovations:


Experience Replay: Store transitions (s, a, r, s') in a buffer, sample random mini-batches during training. This breaks temporal correlations and improves data efficiency.


Target Network: A separate network θ' (periodically updated from θ) is used to compute target Q-values. This stabilizes training by reducing moving target problem.


DQN improvements:

- Double DQN: Use online network for action selection, target network for value estimation (reduces overestimation bias)

- Dueling DQN: Split Q-value into state-value V(s) and action advantage A(s, a): Q(s, a) = V(s) + A(s, a)

- Prioritized Experience Replay: Sample transitions with higher TD error more frequently

- Noisy Nets: Learnable noise in network parameters for exploration
6.3 Policy Gradient Methods
Policy gradient methods directly optimize the policy π_θ(a|s) via gradient ascent on expected return.
REINFORCE (Monte Carlo policy gradient):
∇J(θ) = E[ G_t · ∇_θ log π_θ(a_t|s_t) ]


The gradient points in the direction that increases the probability of actions that led to higher returns.
Reduce variance by subtracting baseline:
∇J(θ) = E[ (G_t - b(s_t)) · ∇_θ log π_θ(a_t|s_t) ]


A common baseline is the state-value function V(s).
Actor-Critic: Combines policy gradient (actor) with value function (critic). The actor updates the policy, the critic evaluates the current policy:
∇J(θ) = E[ (Q_w(s, a) - V_v(s)) · ∇_θ log π_θ(a|s) ]


The term A(s, a) = Q(s, a) - V(s) is the advantage function — how much better is action a compared to the average.
6.4 Proximal Policy Optimization (PPO)
PPO (Schulman et al., 2017) is the most widely used deep RL algorithm. It addresses the problem of choosing the right step size in policy gradients.
Clipped Surrogate Objective:
L_CLIP(θ) = E_t[min(r_t(θ) Â_t, clip(r_t(θ), 1-ε, 1+ε) Â_t)]


where r_t(θ) = π_θ(a_t|s_t) / π_θ_old(a_t|s_t) is the probability ratio, and Â_t is the estimated advantage.
The clipping prevents the policy from changing too much in a single update. If the ratio moves outside [1-ε, 1+ε], the gradient is clipped, providing a stable trust region.
PPO-Clip vs PPO-Penalty:

- PPO-Clip: Clips the objective directly (most common)

- PPO-Penalty: Adds a KL divergence penalty to constrain policy change
PPO Algorithm:
for iteration = 1 to N:
    for actor = 1 to M:
        Run policy π_θ_old for T timesteps, collect {s, a, r}
        Compute advantages Â_t using GAE
    Optimize L_CLIP with SGD for K epochs, mini-batch size B
    Update θ_old ← θ


Generalized Advantage Estimation (GAE):
Â_t = Σ_{l=0}^{∞} (γλ)^l δ_{t+l}


where δ_t = r_t + γV(s_{t+1}) - V(s_t) is the TD error, and λ controls bias-variance trade-off.
6.5 Soft Actor-Critic (SAC)
SAC (Haarnoja et al., 2018) is an off-policy, maximum-entropy RL algorithm:
Objective: Maximize both expected return and policy entropy:
J(π) = Σ_t E[(r(s_t, a_t) + α H(π(·|s_t)))]


where α is the temperature parameter controlling exploration (higher α → more stochasticity).
Key components:

- Soft policy evaluation: Q(s, a) = r + γ E[V(s')] where V(s) = E[Q(s, a)] - α log π(a|s)

- Soft policy improvement: π_new = argmin D_KL(π_new(·|s) || exp(Q_π_old(s,·)/α))

- Automated temperature tuning: Adjust α to match target entropy
SAC typically uses:

- Two Q-networks (to reduce overestimation bias)

- A policy network

- A value network (optional, can be computed from Q and policy)
SAC vs PPO:



Aspect
PPO
SAC




Type
On-policy
Off-policy


Sample efficiency
Lower
Higher


Stability
Very stable
Stable


Exploration
Entropy bonus
Max-entropy framework


Hyperparameters
Fewer
More (α, target entropy)


Continuous control
Good
Excellent



6.6 Model-Based RL
Instead of learning policy/value from experience alone, model-based RL learns a model of the environment dynamics:
learn: ŝ_{t+1} = f(s_t, a_t)
       r̂_t = g(s_t, a_t)


The learned model can be used for planning (e.g., via Model Predictive Control) or to generate synthetic experience for model-free RL.
MuZero (Schrittwieser et al., 2020): Combines model-based and model-free by learning a model that predicts only reward, value, and policy (not full environment state). This enables planning without access to the true dynamics.
6.7 Multi-Agent RL
Multiple agents learn and interact simultaneously, leading to non-stationary environments. Key approaches:

- Independent Q-learning: Each agent learns independently, ignoring others

- Centralized training, decentralized execution (CTDE): Critics have global information, actors only local observations (MADDPG, QMIX, VDN)

- Multi-agent PPO (MAPPO): Extends PPO to multi-agent setting
7. Statistical Learning Theory
7.1 Bias-Variance Tradeoff

The generalization error of a model can be decomposed into three components:
E[(y - f̂(x))²] = Bias[f̂(x)]² + Var[f̂(x)] + σ²


where:

- Bias: Error due to model's assumptions (simplifications that miss true patterns)

- Variance: Error due to model's sensitivity to training data fluctuations

- σ²: Irreducible noise (Bayes error)
Bias² = (E[f̂(x)] - f*(x))²    where f* is the true function
Var = E[(f̂(x) - E[f̂(x)])²]


The tradeoff:

- High bias, low variance: Underfitting (e.g., linear model for non-linear data)

- Low bias, high variance: Overfitting (e.g., deep tree on noisy data)
As model complexity ↑:
  Bias ↓ (model can fit more patterns)
  Variance ↑ (model memorizes noise)
  Total error ↓ then ↑ (U-shaped curve)


Visualization:
Error
  ^
  |  Total Error
  |   /\
  |  /  \
  | /    \_______ Irreducible Error
  |/ Bias²
  |----------------------> Model Complexity
           Var


7.2 Learning Curves
Learning curves show model performance as a function of training set size:

High bias: Training and validation errors converge to a high value (not enough model capacity)
High variance: Training error is low, validation error is high (too much capacity for data size)

7.3 Vapnik-Chervonenkis (VC) Dimension
The VC dimension is a measure of model capacity — the maximum number of points that can be shattered (perfectly classified in all possible labelings) by the model class.

Linear classifier in ℝ²: VC dimension = 3
Linear classifier in ℝᵈ: VC dimension = d + 1
SVM with RBF kernel: Infinite VC dimension

For binary classification, with probability 1 - η:
R(f) ≤ R_emp(f) + sqrt((h(log(2N/h) + 1) - log(η/4)) / N)


where R(f) is true risk, R_emp(f) is empirical risk, h is VC dimension, N is sample size. This bounds generalization error in terms of model complexity.
7.4 Probably Approximately Correct (PAC) Learning
PAC learning bounds the number of samples needed to achieve a given error with high probability:
P(R(f) ≤ ε) ≥ 1 - δ


Sample complexity N(ε, δ) scales with 1/ε and log(1/δ).
PAC-Bayes: Extends PAC to randomized predictors, providing tighter bounds for neural networks.
7.5 Regularization
Regularization constrains model complexity to improve generalization. See Section 10 for a detailed treatment.
7.6 Cross-Validation
See Section 11 for cross-validation methods.
8. Loss Functions
8.1 Regression Losses

8.1.1 Mean Squared Error (MSE / L2 Loss)
MSE = (1/N) Σ_i (y_i - ŷ_i)²



Gradient: ∂L/∂ŷ = (2/N)(ŷ - y) — linear in residual
Properties: Penalizes large errors heavily (quadratic), optimal for Gaussian noise
Sensitivity: Very sensitive to outliers

8.1.2 Mean Absolute Error (MAE / L1 Loss)
MAE = (1/N) Σ_i |y_i - ŷ_i|



Gradient: ∂L/∂ŷ = (1/N) sign(ŷ - y) — constant magnitude
Properties: Robust to outliers, optimal for Laplacian noise
Issue: Non-differentiable at zero (subgradient used)

MSE vs MAE:



Aspect
MSE
MAE




Outlier sensitivity
High
Low


Gradient magnitude
Proportional to error
Constant


Optimal for
Gaussian noise
Laplacian noise


Convergence
Faster initially
Slower near optimum



8.1.3 Huber Loss
Combines MSE and MAE:
L_δ(e) = { 0.5 e²,            if |e| ≤ δ
          { δ|e| - 0.5 δ²,    if |e| > δ


where e = y - ŷ.

Properties: Quadratic for small errors (smooth, differentiable), linear for large errors (robust to outliers)
δ: Controls transition point (tunable hyperparameter)

8.1.4 Quantile Loss
Used for quantile regression (predicting conditional quantiles):
L_τ(e) = { τ · e,          if e ≥ 0
          { (τ-1) · e,     if e < 0


where τ ∈ (0, 1) is the target quantile.

τ=0.5: Median regression (L1 loss)
τ=0.9: Predicts the 90th percentile
Asymmetric: Over-predictions and under-predictions are penalized differently

8.1.5 Log-Cosh Loss
L = Σ_i log(cosh(ŷ_i - y_i))


Similar to Huber but twice differentiable everywhere.
8.2 Classification Losses
8.2.1 Cross-Entropy (Log Loss)
Binary:
L = -(1/N) Σ_i [y_i log(ŷ_i) + (1-y_i) log(1-ŷ_i)]


Categorical:
L = -(1/N) Σ_i Σ_k y_{ik} log(ŷ_{ik})



Properties: Penalizes confident wrong predictions heavily, convex in logits
Calibration: Well-calibrated probabilities with proper training

8.2.2 Hinge Loss (SVM)
L = (1/N) Σ_i max(0, 1 - y_i · ŷ_i)


where y_i ∈ {-1, 1}, ŷ_i is the raw score (not probability).

Properties: Creates margin, only penalizes points on wrong side of margin
Subgradient: Zero for well-classified points outside margin

8.2.3 Focal Loss
Designed for class imbalance (object detection):
L = -(1/N) Σ_i α (1 - ŷ_i)^γ y_i log(ŷ_i)


where γ ≥ 0 reduces the relative loss for well-classified examples, focusing on hard, misclassified examples.

γ=0: Standard cross-entropy
γ=2: Common default for object detection (e.g., RetinaNet)
α: Class balancing weight

8.2.4 Contrastive Loss
Used in representation learning to pull positive pairs together and push negative pairs apart:
L = (1/N) Σ_i [y · D² + (1-y) · max(0, m - D)²]


where D = ||z_1 - z_2|| is distance between embeddings, y=1 for positive pairs, y=0 for negative pairs, m is margin.
8.2.5 Triplet Loss
Operates on triplets (anchor, positive, negative):
L = max(0, D(a, p)² - D(a, n)² + α)


where D(a, p) is distance between anchor and positive, D(a, n) is distance between anchor and negative, α is margin.
Hard negative mining: Only train on triplets where D(a, p) - D(a, n) + α > 0 (semi-hard or hard triplets).
8.2.6 InfoNCE (Noise Contrastive Estimation)
Used in contrastive learning:
L = -log(exp(sim(z_i, z_j)/τ) / Σ_k exp(sim(z_i, z_k)/τ))


Maximizes mutual information between positive pairs. Equivalent to (K+1)-way softmax classification where one class is positive and K are negatives.
9. Optimization Algorithms
9.1 Gradient Descent Variants

9.1.1 Batch Gradient Descent (BGD)
θ_{t+1} = θ_t - η · ∇_θ J(θ_t)



Uses the entire dataset per update
Deterministic (no noise)
Slow for large datasets

9.1.2 Stochastic Gradient Descent (SGD)
θ_{t+1} = θ_t - η · ∇_θ J(θ_t; x^{(i)}, y^{(i)})



One sample per update
High variance (noisy gradients)
Can escape shallow local minima

9.1.3 Mini-Batch Gradient Descent
θ_{t+1} = θ_t - η · (1/B) Σ_{i=1}^B ∇_θ J(θ_t; x^{(i)}, y^{(i)})



B: batch size (typically 16-1024)
Reduces variance vs SGD
Enables vectorized computation (GPU)
Balances convergence speed and stability

9.2 Momentum Methods
9.2.1 SGD with Momentum
Accumulates a velocity vector to accelerate convergence:
v_{t+1} = γ · v_t + η · ∇_θ J(θ_t)
θ_{t+1} = θ_t - v_{t+1}



γ (momentum coefficient, typically 0.9): Controls contribution of past gradients
Effect: Accelerates in consistent gradient directions, dampens oscillations
Analogy: Ball rolling downhill gaining speed

9.2.2 Nesterov Accelerated Gradient (NAG)
Look-ahead momentum:
v_{t+1} = γ · v_t + η · ∇_θ J(θ_t - γ · v_t)
θ_{t+1} = θ_t - v_{t+1}



Computes gradient at "look-ahead" position
Provides more stable convergence than standard momentum
Theoretical convergence rate: O(1/t²) for convex functions

9.3 Adaptive Learning Rate Methods
9.3.1 AdaGrad
Adapts learning rate per parameter based on historical gradients:
g_t = ∇_θ J(θ_t)
G_t = G_{t-1} + g_t ⊙ g_t  (accumulated squared gradients)
θ_{t+1} = θ_t - η / (√(G_t) + ε) ⊙ g_t



Effect: Larger updates for infrequent features, smaller updates for frequent features
Issue: Accumulated gradient sum grows monotonically, learning rate → 0

9.3.2 RMSProp
Modifies AdaGrad with exponential moving average of squared gradients:
E[g²]_t = β · E[g²]_{t-1} + (1-β) · g_t ⊙ g_t
θ_{t+1} = θ_t - η / (√(E[g²]_t) + ε) ⊙ g_t



β (typically 0.9): Decay rate for moving average
Effect: Non-monotonic learning rate decay, works well in non-convex settings

9.3.3 Adam (Adaptive Moment Estimation)
Combines momentum (first moment) with RMSProp (second moment):
m_t = β₁ · m_{t-1} + (1-β₁) · g_t            (biased first moment)
v_t = β₂ · v_{t-1} + (1-β₂) · g_t ⊙ g_t      (biased second moment)
m̂_t = m_t / (1 - β₁^t)                        (bias correction)
v̂_t = v_t / (1 - β₂^t)                        (bias correction)
θ_{t+1} = θ_t - η · m̂_t / (√(v̂_t) + ε)


Default hyperparameters (from Kingma & Ba, 2014):

- η = 0.001 (learning rate)

- β₁ = 0.9 (momentum decay)

- β₂ = 0.999 (RMS decay)

- ε = 1e-8 (numerical stability)
Properties:

- Per-parameter learning rates

- Scale-invariant (resilient to gradient scaling)

- Well-suited for sparse gradients and noisy data

- Often requires less tuning than SGD
Limitations:

- Can fail to generalize as well as SGD with proper tuning

- Some variants found to not converge in certain cases
9.3.4 AdamW (Adam with Decoupled Weight Decay)
Fixes a bug in the original Adam where weight decay interacts poorly with adaptive learning rates:
θ_{t+1} = θ_t - η · (m̂_t / (√(v̂_t) + ε) + λ · θ_t)


Adam's L2 regularization: θ = θ - η·m̂/√v̂ - η·λ·θ

AdamW weight decay: θ = θ - η·m̂/√v̂ - λ_decay·θ

Key insight: Weight decay should be separated from gradient-based updates
Effect: Better generalization, especially in large models and transfer learning
Default λ: 0.01-0.1 typical for vision, 0.1-1.0 for language models

9.3.5 Other Optimizers



Optimizer
Key Idea
When to Use




AdaBelief
Uses variance of gradients instead of squared gradients
When Adam is unstable


RAdam
Rectified Adam, warmup-based variance correction
Training from scratch


Lion
Symbolic discovery, sign operations only
Very large models


Sophia
Uses Hessian diagonal for preconditioning
Large-scale training


Shampoo
Full-matrix preconditioning (Kronecker approx)
Very deep networks


LAMB
Layer-wise Adaptive Moments, large batch training
Large batch (≥16K)



9.4 Learning Rate Scheduling
9.4.1 Step Decay
η_t = η_0 · γ^{⌊t / step_size⌋}


Drop learning rate by factor γ every step_size iterations.
9.4.2 Exponential Decay
η_t = η_0 · γ^t


Smooth, continuous decay.
9.4.3 Cosine Annealing
η_t = η_min + (η_max - η_min) · (1 + cos(π · t / T)) / 2



Smooth decay from η_max to η_min
Often combined with warm restarts (SGDR): periodically reset to η_max
Cosine with warmup: Standard in modern LLM training

9.4.4 Polynomial Decay
η_t = η_0 · (1 - t/T)^p



p=1: Linear decay
p=2: Quadratic decay
p=0.5: Square root decay

9.4.5 Warmup
Linearly increase learning rate from 0 to target over W steps:
η_t = η_target · min(1, t/W)


Why warmup? In early training, model parameters are random; large gradients combined with high learning rate can cause divergence. Warmup allows the optimizer to accumulate stable statistics (momentum, Adam state) before full updates.
9.5 Gradient Clipping
Prevent exploding gradients by scaling down large gradients:
If ||g|| > threshold:
    g = g · threshold / ||g||



L2 norm clipping: Scale whole gradient vector
Value clipping: Clip each element individually
Typical threshold: 0.5-10 for RNNs, 1.0 for Transformers

10. Regularization Techniques
10.1 L1 (Lasso) Regularization

L_reg = L_data + λ ||w||_1 = L_data + λ Σ_j |w_j|



Drives weights exactly to zero (sparsity)
Feature selection property
Non-differentiable at zero (subgradient methods)

10.2 L2 (Ridge) Regularization
L_reg = L_data + λ ||w||_2² = L_data + λ Σ_j w_j²



Shrinks weights toward zero (no exact zeros)
Equivalent to Gaussian prior on weights
Differentiable everywhere

10.3 Elastic Net
Combines L1 and L2:
L_reg = L_data + λ₁||w||_1 + λ₂||w||_2²



Groups correlated features (unlike Lasso which picks one)
Maintains sparsity

10.4 Early Stopping
Stop training when validation loss stops improving:
1. Track validation loss at each epoch
2. If no improvement for P epochs (patience), stop
3. Restore model from best validation epoch


Acts as implicit regularization by limiting the effective model complexity (similar to L2 regularization).
10.5 Dropout
Randomly "drop" (zero out) a fraction p of neurons during training:
For each training step (forward pass):
    r_j ~ Bernoulli(1 - p)  (binary mask)
    h_j' = r_j · h_j / (1 - p)    (inverted dropout, scaling at training time)



During inference: All neurons active, no scaling needed (in inverted dropout)
Effect: Forces network to learn redundant representations (prevents co-adaptation)
Interpretation: Approximate Bayesian inference over network weights
Dropout rate p: 0.5 for hidden layers, 0.2-0.3 for input layers

10.6 DropConnect
Generalization of dropout that drops individual weights (connections) rather than whole neurons:
For each weight w_ij:
    r_ij ~ Bernoulli(1 - p)
    w_ij' = r_ij · w_ij


10.7 Label Smoothing
Replaces hard targets (0/1) with soft targets:
y'_i = y_i · (1 - α) + α / K


where K is number of classes, α is smoothing parameter (typically 0.1).
Effect: Prevents overconfidence, improves calibration, acts as regularization.
10.8 Data Augmentation
Generate modified versions of training data:

Images: Rotation, crop, flip, color jitter, cutout, mixup, CutMix
Text: Back-translation, synonym replacement, token masking, mixup
Audio: SpecAugment (time/freq masking), noise addition, pitch shift

10.9 Stochastic Depth
Used in deep networks (ResNets): randomly drop entire layers during training:
For each layer l in forward pass:
    if random() < p_l:  # drop layer
        output = input (skip via residual connection)
    else:
        output = layer(input)


Training is an ensemble of networks of varying depths.
11. Cross-Validation and Model Selection
11.1 Hold-Out Validation

Split data into training (70-80%) and validation (20-30%) sets.
Pros: Simple, fast

Cons: High variance estimate, wastes data
11.2 k-Fold Cross-Validation
1. Split data into k equal folds (k=5 or 10 typical)
2. For each fold i:
   a. Train on all folds except i
   b. Evaluate on fold i
3. Report average performance across all k trials


Stratified k-fold: Preserves class proportions in each fold (important for imbalanced data).
Repeated k-fold: Repeat k-fold multiple times with different random splits.
11.3 Leave-One-Out Cross-Validation (LOOCV)
k = N (one sample per validation set).
Extreme case: Low bias, high variance, very expensive (O(N) training runs). Used for very small datasets.
11.4 Bootstrapping
Sample N points with replacement B times:
for b = 1 to B:
    sample N points with replacement (bootstrap sample)
    train model on bootstrap sample
    evaluate on out-of-bag (OOB) points


.632 Bootstrap: Weighted average of training error and OOB error to correct optimistic bias.
11.5 Hyperparameter Tuning
Grid Search
Exhaustive search over a predefined parameter grid:
params = {'learning_rate': [0.001, 0.01, 0.1],
          'max_depth': [3, 5, 7],
          'n_estimators': [100, 200, 300]}

for combination in all_combinations:
    score = cross_val_score(model, params=combination)
    best = combination with highest score


Cost: O(P^D) where P = parameters per dimension, D = dimensions.
Random Search
Sample hyperparameters randomly from distributions:
for i = 1 to N:
    learning_rate ~ LogUniform(0.0001, 1.0)
    max_depth ~ Uniform(3, 10)
    n_estimators ~ UniformInt(50, 500)
    ...


More efficient than grid search when some parameters are more important (Bergstra & Bengio, 2012).
Bayesian Optimization
Build a probabilistic model (Gaussian Process or Tree-structured Parzen Estimator) mapping hyperparameters to performance, then select next hyperparameters to evaluate via acquisition function (Expected Improvement, Upper Confidence Bound).
Key libraries: Hyperopt, Optuna, SMAC, GPyOpt
Evolutionary Optimization
Use genetic algorithms or CMA-ES to evolve hyperparameter populations.
12. Ensemble Methods
Ensemble methods combine multiple models to improve prediction accuracy and robustness.

12.1 Voting Ensembles

Hard voting: Majority vote across models (classification)
Soft voting: Average predicted probabilities (classification)
Averaging: Mean prediction (regression)

12.2 Bagging (Bootstrap Aggregating)
for b = 1 to B:
    sample N points with replacement
    train model M_b on bootstrap sample
final = average(M_1(x), ..., M_B(x))


Reduces variance without increasing bias. Most effective for high-variance models (decision trees).
12.3 Boosting
Sequential training where each model focuses on mistakes of the previous ensemble. See Section 2.2.7-2.2.10.
12.4 Stacking (Stacked Generalization)
Train a meta-learner to combine base model predictions:
Level 0: Train diverse base models on original data
         Get predictions P_1(x), P_2(x), ..., P_M(x)
Level 1: Train meta-model on predictions from level 0
         Use predictions as features for meta-model


Best practice: Level 0 predictions should come from cross-validation (not training data) to prevent overfitting.
12.5 Bayesian Model Averaging
Weight models by their posterior probability:
P(y|x) = Σ_m P(y|x, M_m) · P(M_m|data)


12.6 Weighted Ensembles
Assign learnable weights to ensemble members:
final(x) = Σ_m w_m · f_m(x)


Weights can be optimized on a validation set.
📄 Deep Learning — 2116 lines
A comprehensive, deeply technical exploration of deep learning — from the perceptron through modern diffusion models. Covers fundamental architectures, mathematical derivations, training procedures, and practical implementation guidance.
AlignmentAttentionBERTBenchmarkCLIPCNNDeploymentDiffusionEnsembleGPT
1. History of Deep Learning
1.1 The Perceptron (1958)

The modern deep learning revolution traces its roots to the Mark I Perceptron, developed by Frank Rosenblatt in 1958 at the Cornell Aeronautical Laboratory. The perceptron was the first algorithmically described neural network — a single-layer binary classifier designed for supervised learning.
Mathematical formulation:
Given an input vector x ∈ ℝ^n, weights w ∈ ℝ^n, bias b ∈ ℝ, the perceptron computes:
z = w^T x + b
ŷ = φ(z) = 1 if z ≥ 0, else 0


The perceptron learning algorithm updates weights when a misclassification occurs:
w ← w + η(y - ŷ)x
b ← b + η(y - ŷ)


Where η is the learning rate. The perceptron convergence theorem (Novikoff, 1962) guarantees that if the data is linearly separable, the algorithm will converge to a solution in a finite number of steps. However, Minsky and Papert's 1969 book "Perceptrons" demonstrated fundamental limitations — most famously, the perceptron cannot learn XOR because XOR is not linearly separable. This led to the first AI winter.
1.2 The Multi-Layer Perceptron and Backpropagation (1986)
The solution to XOR and other non-linear problems was the multi-layer perceptron (MLP), which introduced one or more hidden layers between input and output. The critical enabling technology was backpropagation, popularized by Rumelhart, Hinton, and Williams in 1986 (though its roots trace to Werbos's 1974 PhD thesis).
The MLP with one hidden layer computes:
h = σ(W_1 x + b_1)
ŷ = σ(W_2 h + b_2)


Where σ is a differentiable non-linear activation function (typically sigmoid or tanh). The chain rule of calculus enables gradient propagation through the layers.
1.3 Convolutional Neural Networks (1989-2012)
The convolutional neural network (CNN) was pioneered by Kunihiko Fukushima's Neocognitron (1980) and formalized by Yann LeCun et al. (1989) for handwritten digit recognition (LeNet). CNNs exploit spatial locality through weight sharing and local receptive fields. The 2012 ImageNet victory of AlexNet (Krizhevsky, Sutskever, Hinton) marked the watershed moment that ignited the modern deep learning era.
1.4 Recurrent Neural Networks and Long Short-Term Memory (1997)
Recurrent neural networks (RNNs), introduced by Rumelhart et al. (1986) and Jordan (1986), process sequences by maintaining a hidden state. The Long Short-Term Memory (LSTM) by Hochreiter and Schmidhuber (1997) solved the vanishing gradient problem through gated cell states, enabling long-range dependency learning.
1.5 Generative Adversarial Networks (2014)
Ian Goodfellow's GAN (2014) introduced adversarial training as a generative framework — a generator learns to produce realistic data while a discriminator learns to distinguish real from fake. This spawned a proliferation of variants (DCGAN, StyleGAN, CycleGAN, BigGAN).
1.6 The Transformer Revolution (2017)
The Transformer (Vaswani et al., 2017) replaced recurrence with self-attention, enabling parallel processing of sequences and scaling to unprecedented sizes. This architecture underlies all modern large language models (GPT, BERT, T5, Llama, Claude, Gemini).
1.7 Diffusion Models (2020-present)
Diffusion models (Sohl-Dickstein 2015; Ho, Jain, Abbeel 2020 - DDPM) reverse a gradual noising process to generate high-quality data. Latent diffusion (Rombach et al., 2022 - Stable Diffusion) reduced computational cost by operating in a compressed latent space, making high-resolution image generation practical. Flow matching and rectified flow represent the latest evolution.
2. Multi-Layer Perceptrons (MLPs)
2.1 Architecture

An MLP is a feedforward neural network composed of:

An input layer of d neurons (one per feature)
One or more hidden layers of n_h neurons each
An output layer of c neurons (one per class for classification, or 1 for regression)

Each layer performs an affine transformation followed by a non-linear activation:
a^(1) = W^(1) x + b^(1)
h^(1) = f(a^(1))
a^(2) = W^(2) h^(1) + b^(2)
h^(2) = f(a^(2))
...
ŷ = g(a^(L))


Where:

- W^(ℓ) ∈ ℝ^(d_ℓ × d_{ℓ-1}) is the weight matrix at layer ℓ

- b^(ℓ) ∈ ℝ^(d_ℓ) is the bias vector

- f is a non-linear activation function (applied element-wise)

- g is the output activation (softmax for classification, identity for regression)
2.2 Universal Approximation Theorem
The universal approximation theorem (Cybenko 1989; Hornik 1991) states that a feedforward network with a single hidden layer containing a finite number of neurons can approximate any continuous function on a compact subset of ℝ^n to arbitrary accuracy, provided the activation function is non-constant, bounded, and continuous (e.g., sigmoid).
Key insight: While a single hidden layer suffices in theory, deep networks (many layers) are far more parameter-efficient — they can represent complex functions exponentially more compactly than shallow networks (Telgarsky, 2016).
2.3 Backpropagation: Full Derivation
Backpropagation computes the gradient of the loss function with respect to all network parameters using the chain rule. We derive it for a general MLP.
Forward pass (for a single training example (x, y)):
z^(1) = W^(1) x + b^(1)
a^(1) = σ(z^(1))
z^(2) = W^(2) a^(1) + b^(2)
a^(2) = σ(z^(2))
...
z^(L) = W^(L) a^(L-1) + b^(L)
ŷ = a^(L) = σ(z^(L))  (for output layer)


Loss: L = ℓ(ŷ, y) where ℓ is, e.g., mean squared error or cross-entropy.
Backward pass:
We define the error signal (delta) at each neuron as the derivative of the loss with respect to the pre-activation:
δ_j^(ℓ) = ∂L / ∂z_j^(ℓ)


For the output layer (layer L):
δ_j^(L) = ∂L / ∂z_j^(L)
        = ∑_k (∂L / ∂a_k^(L)) · (∂a_k^(L) / ∂z_j^(L))
        = (∂L / ∂a_j^(L)) · σ'(z_j^(L))


Because a_j^(L) = σ(z_j^(L)) and a_k^(L) for k≠j does not depend on z_j^(L).
In vector form:
δ^(L) = ∇_a L ⊙ σ'(z^(L))


Where ⊙ is the Hadamard (element-wise) product.
For cross-entropy loss with softmax output:
L = -∑_k y_k log(ŷ_k)
ŷ_k = exp(z_k^(L)) / ∑_j exp(z_j^(L))


Then:
δ_j^(L) = ŷ_j - y_j


A famously elegant gradient — the difference between prediction and ground truth.
For a hidden layer ℓ:
δ_j^(ℓ) = ∂L / ∂z_j^(ℓ)
        = ∑_k (∂L / ∂z_k^(ℓ+1)) · (∂z_k^(ℓ+1) / ∂a_j^(ℓ)) · (∂a_j^(ℓ) / ∂z_j^(ℓ))
        = ∑_k δ_k^(ℓ+1) · W_kj^(ℓ+1) · σ'(z_j^(ℓ))


Where z_k^(ℓ+1) = ∑_j W_kj^(ℓ+1) a_j^(ℓ) + b_k^(ℓ+1) and a_j^(ℓ) = σ(z_j^(ℓ)).
In vector form (the backpropagation formula):
δ^(ℓ) = ((W^(ℓ+1))^T δ^(ℓ+1)) ⊙ σ'(z^(ℓ))


Gradients with respect to parameters:
∂L / ∂W_ij^(ℓ) = δ_i^(ℓ) · a_j^(ℓ-1)
∂L / ∂b_i^(ℓ) = δ_i^(ℓ)


In matrix form:
∂L / ∂W^(ℓ) = δ^(ℓ) · (a^(ℓ-1))^T
∂L / ∂b^(ℓ) = δ^(ℓ)


Parameter updates (stochastic gradient descent):
W^(ℓ) ← W^(ℓ) - η · ∂L / ∂W^(ℓ)
b^(ℓ) ← b^(ℓ) - η · ∂L / ∂b^(ℓ)


2.4 Backpropagation Algorithm Pseudocode
ALGORITHM: Backpropagation
─────────────────────────
Input: Network with L layers, training example (x, y)
Output: Gradients ∂L/∂W^(ℓ), ∂L/∂b^(ℓ) for ℓ = 1, ..., L

// Forward pass
a^(0) = x
for ℓ = 1 to L:
    z^(ℓ) = W^(ℓ) a^(ℓ-1) + b^(ℓ)
    a^(ℓ) = σ(z^(ℓ))
ŷ = a^(L)
L = loss(ŷ, y)

// Backward pass (output layer)
δ^(L) = ∇_a L ⊙ σ'(z^(L))

// Backward pass (hidden layers)
for ℓ = L-1 down to 1:
    δ^(ℓ) = ((W^(ℓ+1))^T δ^(ℓ+1)) ⊙ σ'(z^(ℓ))

// Compute gradients
for ℓ = 1 to L:
    ∂L/∂W^(ℓ) = δ^(ℓ) · (a^(ℓ-1))^T
    ∂L/∂b^(ℓ) = δ^(ℓ)


2.5 Practical Considerations for MLPs
Weight initialization:

- Xavier/Glorot initialization: W ~ U(-√(6/(n_in + n_out)), √(6/(n_in + n_out))) for tanh/sigmoid

- He initialization: W ~ N(0, √(2/n_in)) for ReLU

- Proper initialization prevents vanishing/exploding gradients in deep networks
Normalization:

- Batch normalization (Ioffe & Szegedy, 2015): Normalize each mini-batch to zero mean and unit variance, then learn scale γ and shift β

- Layer normalization (Ba et al., 2016): Normalize across the feature dimension; preferred in Transformers

- Both accelerate training, enable higher learning rates, and provide some regularization
Regularization:

- L1/L2 weight decay: Adds penalty λ||W||_2^2 or λ||W||_1 to the loss

- Dropout (Srivastava et al., 2014): Randomly sets a fraction p of neurons to zero during training — prevents co-adaptation

- Early stopping: Monitor validation loss and stop when it begins to increase

- Data augmentation: Artificially expand training set with label-preserving transformations
Optimization:

- SGD with momentum: v_t = γv_{t-1} + η∇L(θ); θ ← θ - v_t

- Adam (Kingma & Ba, 2015): Adaptive moment estimation with bias-corrected first and second moments

- AdamW (Loshchilov & Hutter, 2019): Decoupled weight decay — Adam with proper L2 regularization
3. Activation Functions
3.1 Sigmoid (Logistic)

σ(x) = 1 / (1 + e^{-x})
σ'(x) = σ(x) · (1 - σ(x))


Range: (0, 1)

Properties:

- Smooth, differentiable, monotonic

- Outputs can be interpreted as probabilities

- Saturation problem: Gradient vanishes for |x| > ~5 (σ'(x) → 0)

- Not zero-centered — outputs are always positive, causing zigzag gradient updates

- σ'(0) = 0.25 — acceptable but not ideal
When to use: Output layer for binary classification. Rarely used in hidden layers since the 2010s due to vanishing gradients in deep networks.
3.2 Tanh (Hyperbolic Tangent)
tanh(x) = (e^x - e^{-x}) / (e^x + e^{-x}) = 2σ(2x) - 1
tanh'(x) = 1 - tanh^2(x)


Range: (-1, 1)

Properties:

- Zero-centered — mitigates the zigzag problem of sigmoid

- Still saturates for large |x|, though gradients are steeper near x=0 (tanh'(0) = 1.0)

- Often preferred over sigmoid in hidden layers of shallow networks or RNNs
When to use: Hidden layers in smaller networks or when zero-centered output is beneficial. Largely supplanted by ReLU variants in deep feedforward networks.
3.3 ReLU (Rectified Linear Unit)
ReLU(x) = max(0, x)
ReLU'(x) = 1 if x > 0, else 0


Range: [0, ∞)

Properties:

- Computationally cheap — just max(0, x)

- Non-saturating for x > 0 — mitigates vanishing gradient

- Sparse activation — approximately 50% of neurons are "dead" (output 0)

- Dying ReLU problem: If a neuron's weights push all inputs to negative, the gradient is 0 and the neuron never recovers

- Not differentiable at x=0 (practical implementations use subgradient 0 or 1)
Why ReLU works: The non-saturating nature allows gradients to flow freely through active neurons, enabling training of very deep networks (much deeper than sigmoid/tanh networks).
When to use: Default choice for hidden layers in CNNs and MLPs. The most widely used activation since 2012.
3.4 Leaky ReLU
LeakyReLU(x) = max(αx, x)  where α ∈ (0,1), typically 0.01 or 0.2
LeakyReLU'(x) = 1 if x > 0, else α


Range: (-∞, ∞)

Properties:

- Addresses dying ReLU by allowing a small gradient when x < 0

- Still non-saturating for x > 0

- The hyperparameter α is typically small (0.01)—too large risks linearity
Parametric ReLU (PReLU) learns α via backprop, potentially improving performance at the cost of additional parameters.
3.5 ELU (Exponential Linear Unit)
ELU(x) = x if x ≥ 0, else α(e^x - 1)
ELU'(x) = 1 if x > 0, else ELU(x) + α


Range: (-α, ∞)

Properties:

- Smooth (differentiable at x=0 when α=1)

- Negative values push mean activation toward zero, speeding up learning

- Saturates for very negative inputs — provides noise-robustness

- More computationally expensive than ReLU due to exp()

- α controls the value at which negative saturation occurs (typically 1.0)
When to use: When training deeper networks where mean-shift toward zero helps convergence. Often outperforms ReLU on some benchmarks.
3.6 SELU (Scaled Exponential Linear Unit)
SELU(x) = λ · (x if x > 0, else α(e^x - 1))
where λ ≈ 1.0507, α ≈ 1.6733


Properties:

- Designed for self-normalizing networks (Klambauer et al., 2017)

- Under specific conditions (normalized weights, standardized inputs), the output of each layer automatically converges to zero mean and unit variance

- Enables training of very deep networks without batch normalization

- Requires careful initialization (LeCun Normal) and specific dropout variant (AlphaDropout)
Theoretical guarantee: For networks with SELU activations, there exists a fixed point where mean and variance are preserved across layers, enabling deep networks to be self-normalizing.
3.7 GELU (Gaussian Error Linear Unit)
GELU(x) = x · Φ(x)  where Φ(x) = P(X ≤ x) for X ~ N(0,1)
        ≈ 0.5x · (1 + tanh(√(2/π) · (x + 0.044715x^3)))
        ≈ x · σ(1.702x)  (sigmoid approximation)


Range: (-0.17..., ∞) — has a slight negative dip near x=0
GELU'(x) = Φ(x) + x · φ(x) where φ(x) is the standard normal PDF.
Properties:

- Smooth everywhere (unlike ReLU's kink at 0)

- Non-convex, non-monotonic — has a small negative region for x ∈ (-1, 0)

- Provides a probabilistic interpretation: gates input by its probability of being "greater than random"

- Used in BERT, GPT-3, ViT, and virtually all modern Transformer models

- Outperforms ReLU empirically in deep Transformer architectures
Approximation quality: The tanh approximation is accurate to ~0.001 over the range [-3, 3] and is the form used in most implementations.
3.8 Swish (SiLU — Sigmoid Linear Unit)
Swish(x) = x · σ(βx)  where σ is the sigmoid function
Swish'(x) = β · Swish(x) + σ(βx) · (1 - β · Swish(x))
         = σ(βx) + βx · σ(βx) · (1 - σ(βx))


Range: (-0.5/β..., ∞) for β > 0
Properties:

- Self-gated: x · σ(x) — the input gates itself

- Smooth, non-monotonic (dips slightly below 0 for x negative)

- The β parameter controls the "closeness" to ReLU:

  - As β → ∞: Swish(x) → ReLU(x) (hard gating)

  - As β → 0: Swish(x) → x/2 (linear scaling)

  - β=1 is the standard SiLU (Ramachandran et al., 2017)

- No dead neurons — the gradient is always positive for x < 0 (unlike ReLU)

- Used in EfficientNet (Swish), Llama (SiLU), and many modern architectures
When to use: Generally outperforms ReLU in deep networks at the cost of more computation. Preferred in attention-based architectures.
3.9 SwiGLU (Swish-Gated Linear Unit)
SwiGLU(x) = Swish(W_1 x + b_1) ⊙ (W_2 x + b_2)


Structure: A gated linear unit where one path uses Swish activation and the other is a linear projection. The component-wise product of the gated and linear paths gives the output.
Properties:

- From Shazeer (2020): "GLU Variants Improve Transformer"

- The Swish gating mechanism provides a "soft" version of ReLU gating

- Typically uses an intermediate expansion factor of 8/3 (≈2.67) times the hidden dimension

- Used in PaLM, Llama 2/3, Mistral, GPT-4 — the standard FFN activation in modern LLMs

- More expressive than plain Swish but uses more parameters (3 weight matrices instead of 2)
Comparison to ReLU FFN:
ReLU FFN: FFN(x) = W_2 · ReLU(W_1 x + b_1) + b_2
  Params: 2 · d_model · d_ff (where d_ff = 4 · d_model typically)

SwiGLU FFN: FFN(x) = (Swish(W_1 x + b_1) ⊙ (W_2 x + b_2)) · W_3 + b_3
  Params: 3 · d_model · d_ff
  With d_ff adjusted to (8/3)·d_model, parameter count matches ReLU FFN


3.10 Mish
Mish(x) = x · tanh(ln(1 + e^x)) = x · tanh(softplus(x))
Mish'(x) = sech^2(softplus(x)) · x · σ(x) + Mish(x)/x


Range: Approximately (-0.31..., ∞)
Properties:

- Smooth everywhere (like Swish, GELU)

- Self-gated but with the softplus inside tanh, creating a different curvature than Swish

- Has a slight negative dip at x ≈ -0.5 (minimum ≈ -0.308)

- Empirically shown to outperform Swish+BN in some vision tasks (Misra, 2019)

- More computationally expensive than Swish due to nested softplus and tanh

- Not widely adopted in production compared to GELU/Swish/SwiGLU
3.11 Activation Function Comparison Summary



Function
Range
Smooth
Zero-Centered
Dead Neurons
Compute Cost
Saturation




Sigmoid
(0, 1)
Yes
No
No
Medium (exp)
Yes


Tanh
(-1, 1)
Yes
Yes
No
Medium (exp)
Yes


ReLU
[0, ∞)
No
No
Yes
Cheap
No (pos)


Leaky ReLU
(-∞, ∞)
No
No
No
Cheap
No


ELU
(-α, ∞)
Yes
Near
No
Medium (exp)
Yes (neg)


SELU
(λ·(-α), ∞)
Yes
Self-norm
No
Medium (exp)
Yes (neg)


GELU
(-0.17..., ∞)
Yes
No
No
Medium (Φ)
No


Swish/SiLU
(-0.28..., ∞)
Yes
No
No
Medium (σ)
No


Mish
(-0.31..., ∞)
Yes
No
No
High (exp+tanh)
No



3.12 Practical Guidance for Activation Selection

MLP hidden layers: ReLU is the safe default. Use Swish/GELU if you have compute budget.
CNN hidden layers: ReLU is standard. Swish used in EfficientNet. Mish can give marginal gains.
Transformer FFN: SwiGLU is the dominant modern choice (Llama, Mistral, GPT-4). GELU (BERT, GPT-2).
Output layer: Softmax (multiclass), Sigmoid (binary/multi-label), Linear (regression).
Very deep networks (>50 layers): Consider SELU for self-normalizing properties, or use Swish/GELU with layer normalization.
Mobile/edge devices: ReLU is fastest due to zero compute cost and no exponential operations.

4. Convolutional Neural Networks (CNNs)
4.1 The Convolution Operation

A convolution is a mathematical operation that combines two functions to produce a third. In CNN context, we convolve an input tensor (image) with a kernel (filter).
Discrete 2D convolution:
S(i, j) = (I * K)(i, j) = Σ_m Σ_n I(m, n) · K(i - m, j - n)


In practice, CNNs use cross-correlation (which is equivalent up to kernel rotation):
S(i, j) = (I ⋆ K)(i, j) = Σ_m Σ_n I(i + m, j + n) · K(m, n)


For a multi-channel input with C_in channels and C_out filters of size K_h × K_w:
S_k(i, j) = Σ_{c=1}^{C_in} Σ_{m=1}^{K_h} Σ_{n=1}^{K_w} I_c(i+m, j+n) · K_k_c(m, n) + b_k


Output spatial dimensions:
Given input size H × W, kernel size K_h × K_w, padding P, stride S:
H_out = floor((H - K_h + 2P) / S) + 1
W_out = floor((W - K_w + 2P) / S) + 1


Parameter count per layer: C_out × (C_in × K_h × K_w + 1) — the +1 is for bias.
4.2 Properties of Convolution
Weight sharing: The same kernel is applied across all spatial locations. This dramatically reduces parameters compared to fully-connected layers and provides translation equivariance.
Local connectivity: Each output neuron connects to only a local region of the input (the receptive field). This matches the local structure of natural images.
Sparse interactions: A single output neuron depends on K_h × K_w × C_in input values, not the entire input.
Equivariance to translation: Shifting the input by (dx, dy) and convolving produces approximately the same result as convolving then shifting the output (exact down to boundary effects).
Receptive field: After L layers of 3×3 convolutions with stride 1, the receptive field is (2L+1) × (2L+1). For dilated convolutions with dilation d: (1 + d·(K-1)) per layer.
4.3 Pooling Operations
Max Pooling: Takes the maximum value in each pooling window. Provides local translation invariance. Most common in vision CNNs.
MaxPool(I)(i, j) = max_{m,n ∈ window} I(i + m, j + n)


Average Pooling: Takes the mean value in each pooling window. Less aggressive than max pooling.
AvgPool(I)(i, j) = (1/|window|) · Σ_{m,n ∈ window} I(i + m, j + n)


Global Average Pooling (GAP): Pools the entire feature map to a single value per channel. Used instead of fully-connected layers before the output — has zero parameters, prevents overfitting, and is structure-agnostic.
Strided Convolution vs Pooling: Modern architectures (ResNet, ConvNeXt) often use strided convolutions (stride=2) instead of explicit pooling layers, as they are learnable and more expressive.
Other pooling variants:

- Lp Pooling: (Σ |x|^p)^(1/p) — generalizes average (p=1) and max (p=∞)

- Stochastic Pooling (Zeiler & Fergus, 2013): Samples from a multinomial distribution over spatial regions

- Spatial Pyramid Pooling (He et al., 2015): Pools at multiple scales to handle variable-sized inputs

- Soft Pooling (Stergiou et al., 2021): Differentiable softmax-weighted pooling
4.4 Convolution Mathematics: Detailed Derivations
Gradient of convolution (for backpropagation):
During backprop, we need to compute:

1. ∂L / ∂K — gradient w.r.t. kernel weights

2. ∂L / ∂I — gradient w.r.t. input (to propagate to earlier layers)
Given S = I * K (cross-correlation form), and δ = ∂L/∂S from above:
∂L / ∂K_{m,n} = Σ_i Σ_j δ_{i,j} · I_{i+m, j+n}


This is itself a convolution of δ with I (technically cross-correlation).
∂L / ∂I_{i,j} = Σ_m Σ_n δ_{i-m, j-n} · K_{m,n}
              = (δ full-convolved with rotated K)


This is a full convolution with the kernel rotated 180°.
Dilated Convolution:
S(i, j) = Σ_m Σ_n I(i + d·m, j + d·n) · K(m, n)


Where d is the dilation rate. Dilated convolutions expand the receptive field without increasing parameters.
Depthwise Separable Convolution:
Factorizes a standard convolution into:

1. Depthwise convolution: Apply one filter per input channel (no cross-channel mixing)

2. Pointwise convolution: 1×1 convolution to mix channels
Parameters standard: C_in × C_out × K_h × K_w
Parameters depthwise: C_in × K_h × K_w + C_in × C_out × 1 × 1


The ratio is approximately 1/C_out + 1/K^2, offering dramatic parameter reduction at K=3.
4.5 Transposed Convolution (Deconvolution)
Used for upsampling in encoder-decoder architectures (segmentation, super-resolution, GAN generators).
Forward pass: Given input feature map x of size H × W, kernel K, stride S, padding P, output size is:
H_out = S · (H - 1) + K - 2P


Transposed convolution can be thought of as:

1. Insert S-1 zeros between every element of input

2. Pad the resulting array

3. Apply standard convolution with unit stride
Checkerboard artifacts: Transposed convolutions with kernel sizes not divisible by stride can create artifacts. Better alternatives: resize + convolution, or sub-pixel convolution (Shi et al., 2016).
5. CNN Architectures
5.1 LeNet-5 (LeCun et al., 1998)

Designed for handwritten digit recognition (MNIST). The pioneering CNN that demonstrated the power of learned hierarchical features.
Architecture:
Input: 32×32 grayscale image
Layer 1: Conv(5×5, 6 filters) → AvgPool(2×2, stride 2) → Tanh
Layer 2: Conv(5×5, 16 filters) → AvgPool(2×2, stride 2) → Tanh
Layer 3: FC(120) → Tanh
Layer 4: FC(84) → Tanh
Layer 5: FC(10) → Softmax
Total params: ~60,000


Key innovations: Use of local receptive fields, weight sharing, and spatial subsampling. The gradients are computed via backpropagation (LeNet already used proper BP, though it wasn't yet widely popularized).
5.2 AlexNet (Krizhevsky, Sutskever, Hinton, 2012)
The landmark architecture that won ImageNet 2012 with a dramatic margin (top-5 error 15.3% vs 26.2% for second place). Ignited the deep learning revolution.
Architecture:
Input: 227×227×3 RGB image
Conv1: 96 filters of 11×11, stride 4, padding 0 → ReLU → LRN → MaxPool(3×3, stride 2)
Conv2: 256 filters of 5×5, stride 1, padding 2 → ReLU → LRN → MaxPool(3×3, stride 2)
Conv3: 384 filters of 3×3, stride 1, padding 1 → ReLU
Conv4: 384 filters of 3×3, stride 1, padding 1 → ReLU
Conv5: 256 filters of 3×3, stride 1, padding 1 → ReLU → MaxPool(3×3, stride 2)
FC6: 4096 → ReLU → Dropout(0.5)
FC7: 4096 → ReLU → Dropout(0.5)
FC8: 1000 → Softmax
Total params: ~60 million


Key innovations:

- ReLU activation — enabled much deeper training than tanh/sigmoid

- Dropout (0.5) — reduced overfitting of the 4096-unit FC layers

- Data augmentation — random crops, horizontal flips, PCA color jitter

- Local Response Normalization (LRN) — lateral inhibition, now largely deprecated

- GPU training (2x GTX 580) — demonstrated practical parallelism
Training details: SGD with momentum 0.9, batch size 128, learning rate 0.01 reduced manually by factor 10 when validation accuracy plateaued. Trained for ~90 epochs over 5-6 days.
5.3 VGGNet (Simonyan & Zisserman, 2014)
Demonstrated that depth is critical: VGG-16 (16 weight layers) and VGG-19 (19 weight layers).
Architecture design principle: Use only 3×3 convolutions with stride 1, padding 1 (preserves spatial size). Spatial downsampling via max pooling (2×2, stride 2) after some conv blocks.
Input: 224×224×3
Block 1: [Conv(64, 3×3) × 2] → MaxPool(2,2)
Block 2: [Conv(128, 3×3) × 2] → MaxPool(2,2)
Block 3: [Conv(256, 3×3) × 3] → MaxPool(2,2)
Block 4: [Conv(512, 3×3) × 3] → MaxPool(2,2)
Block 5: [Conv(512, 3×3) × 3] → MaxPool(2,2)
FC layers: 4096 → 4096 → 1000


Why 3×3? Two stacked 3×3 convolutions have a 5×5 receptive field (3 layers = 7×7) but with fewer parameters: 2 × 9 × C² = 18C² vs 25C² for a single 5×5 layer. The ReLU between two 3×3 layers also adds non-linearity.
Total params: VGG-16 has 138M parameters, mostly from the three FC layers (4096+4096+1000=~119M). Modern architectures use GAP to avoid this parameter explosion.
Practical note: VGG is slow to train and has large memory footprint, but its simplicity and uniform architecture make it excellent for feature extraction and transfer learning. It remains a common baseline.
5.4 ResNet (He et al., 2015 — Best Paper CVPR 2016)
Introduced residual learning, enabling training of networks with 152+ layers. Before ResNet, deeper networks suffered from degradation — higher training error, not just generalization gap, caused by vanishing gradients.
Residual Block:
x → [Conv(3×3) → BN → ReLU → Conv(3×3) → BN] → + → ReLU
    └────────────────────────────────── shortcut ───┘

y = F(x, {W_i}) + x


Where F(x) = W_2 · σ(W_1 x + b_1) + b_2 and σ is ReLU. When input/output dimensions don't match, the shortcut uses either (a) zero-padded identity or (b) 1×1 convolution with stride to match dimensions.
Why residual connections work:

- Gradient highway: The identity skip connection allows gradients to flow directly through the network without vanishing — ∂L/∂x = ∂L/∂y · (1 + ∂F/∂x)

- Ensemble interpretation: ResNets behave like ensembles of shallow networks (Veit et al., 2016) — during forward pass, information can skip any subset of residual blocks

- Easier optimization: It's easier to learn the residual F(x) near zero than to learn the full mapping H(x) = F(x) + x from scratch
Common ResNet variants:
ResNet-18: 4 blocks of [2, 2, 2, 2] basic blocks (64→128→256→512)
ResNet-34: 4 blocks of [3, 4, 6, 3] basic blocks
ResNet-50: 4 blocks of [3, 4, 6, 3] bottleneck blocks
ResNet-101: 4 blocks of [3, 4, 23, 3] bottleneck blocks
ResNet-152: 4 blocks of [3, 8, 36, 3] bottleneck blocks


Bottleneck Block (for ResNet-50+):
1×1 Conv (reduce channels by 4×)
3×3 Conv (spatial processing)
1×1 Conv (expand channels back)


This reduces computational cost: a 3×3 on 256 channels vs on 64 channels after reduction.
Bottleneck parameter comparison:
Basic block: 2 × 3×3 × 256 × 256 = 1,179,648 params
Bottleneck: 1×1(256→64) + 3×3(64→64) + 1×1(64→256) = 64*256 + 9*64*64 + 256*64 = 69,632 params


The bottleneck is ~17× more parameter-efficient.
Pre-activation ResNet (He et al., 2016):
BN → ReLU → Conv → BN → ReLU → Conv


Putting BN and ReLU before the convolution (instead of after addition) improves gradient flow and regularization.
ResNeXt (Xie et al., 2017):

Applies grouped convolutions — splits filters into cardinality g...
6. Recurrent Neural Networks (RNNs)
6.1 Vanilla RNN

A recurrent neural network processes sequential data by maintaining a hidden state that is updated at each time step.
h_t = tanh(W_hh · h_{t-1} + W_xh · x_t + b_h)
ŷ_t = W_hy · h_t + b_y


Where:

- x_t ∈ ℝ^d is the input at time step t

- h_t ∈ ℝ^h is the hidden state

- ŷ_t ∈ ℝ^o is the output (prediction)

- W_hh ∈ ℝ^(h×h) is the recurrent weight matrix

- W_xh ∈ ℝ^(h×d) is the input weight matrix

- W_hy ∈ ℝ^(o×h) is the output weight matrix
Unrolling through time: The RNN can be "unrolled" into a deep feedforward network with T layers, where each layer shares the same weights. This is purely for analysis — the computation graph has T× the depth.
6.2 Backpropagation Through Time (BPTT)
BPTT applies standard backpropagation to the unrolled computation graph. The critical challenge is that the loss at time t depends on hidden states from all earlier time steps.
Gradient of loss at time t w.r.t. hidden state at time t:
∂L_t / ∂h_t = (∂L_t / ∂ŷ_t) · W_hy^T


Gradient propagated backward through time:
∂L_t / ∂h_k = ∂L_t / ∂h_{k+1} · ∂h_{k+1} / ∂h_k
            = ∂L_t / ∂h_{k+1} · W_hh^T · diag(tanh'(h_{k+1}))


Total gradient w.r.t. W_hh:
∂L / ∂W_hh = Σ_t Σ_{k=1}^{t} (∂L_t / ∂h_k · h_{k-1}^T)


6.3 The Vanishing and Exploding Gradient Problem
The Jacobian of the hidden state transition involves repeated multiplication by W_hh:
∂h_t / ∂h_1 = Π_{k=2}^{t} W_hh^T · diag(tanh'(h_k))


If the eigenvalues of W_hh are small (< 1), the gradient vanishes exponentially with sequence length. If they are large (> 1), it explodes.
Impact:

- Vanishing gradients: Network cannot learn long-range dependencies (>10-20 time steps)

- Exploding gradients: Training becomes unstable; weights may go to NaN
Mitigations:

- Gradient clipping: Scale gradients if their norm exceeds a threshold (typically 1.0 or 5.0)

- Proper initialization: Orthogonal initialization of W_hh (suggested by Saxe et al., 2014)

- Gated architectures (LSTM, GRU) — the primary practical solution

- ReLU activation: Less saturation than tanh, but can cause exploding activations
6.4 Gradient Clipping Pseudocode
ALGORITHM: Gradient Clipping
────────────────────────────
θ = model parameters
g = ∇L(θ)  (gradients)

// Clip by global norm (most common)
threshold = 1.0
global_norm = sqrt(Σ ||g_i||² for g_i in g)

if global_norm > threshold:
    scale = threshold / global_norm
    g_i = g_i * scale for all g_i

θ ← θ - η · g


6.5 RNN Training: Practical Considerations
Sequence batching: Pad sequences to equal length within a batch. Use masking to ignore padding contributions to the loss.
Bucketing: Group sequences of similar length into the same batch to minimize padding waste.
Truncated BPTT (TBPTT): Instead of backpropagating through the entire sequence, unroll for a fixed window of T steps. This limits memory usage and speeds training, though it technically biases the gradient computation.
Teacher forcing: During training, feed the ground-truth previous output as input to the next time step (instead of the model's own prediction). This stabilizes training but creates exposure bias — the model never sees its own errors during training.
Scheduled sampling (Bengio et al., 2015): Gradually anneal from teacher forcing to model-generated outputs during training to mitigate exposure bias.
7. Gated RNN Variants: LSTM and GRU
7.1 Long Short-Term Memory (LSTM)

Hochreiter & Schmidhuber (1997) introduced the LSTM to address the vanishing gradient problem. The key innovation is the cell state c_t — a separate memory line with linear self-loops that allows gradients to flow unchanged over many time steps.
LSTM Gate Math:
// Forget gate: decides what to discard from cell state
f_t = σ(W_f · [h_{t-1}, x_t] + b_f)
// Alternative formulation with separate weight matrices:
f_t = σ(W_hf · h_{t-1} + W_xf · x_t + b_f)

// Input gate: decides what new information to store
i_t = σ(W_i · [h_{t-1}, x_t] + b_i)

// Candidate cell state: new candidate values
\tilde{c}_t = tanh(W_c · [h_{t-1}, x_t] + b_c)

// Cell state update: forget old + add new
c_t = f_t ⊙ c_{t-1} + i_t ⊙ \tilde{c}_t

// Output gate: decides what to output from cell state
o_t = σ(W_o · [h_{t-1}, x_t] + b_o)

// Hidden state (output)
h_t = o_t ⊙ tanh(c_t)


Dimensions: If x_t ∈ ℝ^d and hidden size = h, then W_f, W_i, W_c, W_o ∈ ℝ^(h × (h+d)). Total LSTM params = 4 × (h × (h + d) + h).
Why LSTMs solve vanishing gradients:
The cell state recurrence c_t = f_t ⊙ c_{t-1} + i_t ⊙ \tilde{c}_t has additive (not multiplicative) dynamics. The gradient flows through the forget gate:
∂c_t / ∂c_{t-1} = diag(f_t) + ∂(other terms)/∂c_{t-1}


When f_t ≈ 1 (forget gate open), the gradient is ≈ 1 and can propagate unchanged. The LSTM learns when to open/close the forget gate, giving it the ability to capture long-range dependencies when needed.
Peephole connections (Gers & Schmidhuber, 2000): Add connections from c_{t-1} to the gate computations, allowing the gates to "see" the cell state directly.
LSTM Variants:

- Bidirectional LSTM (BiLSTM): One LSTM processes forward, another backward, concatenating hidden states at each step

- Stacked LSTM: Multiple LSTM layers on top of each other

- Layer-Normalized LSTM: Apply LayerNorm to the hidden-candidate computation
7.2 Gated Recurrent Unit (GRU)
Cho et al. (2014) introduced the GRU as a simplified alternative to LSTM with fewer parameters (no separate cell state, output gate removed).
GRU Gate Math:
// Reset gate: controls influence of previous hidden state
r_t = σ(W_r · [h_{t-1}, x_t] + b_r)

// Update gate: combines forget and input gates
z_t = σ(W_z · [h_{t-1}, x_t] + b_z)

// Candidate hidden state (with reset gate applied)
\tilde{h}_t = tanh(W_h · [r_t ⊙ h_{t-1}, x_t] + b_h)

// Hidden state update (interpolation of old and new)
h_t = (1 - z_t) ⊙ h_{t-1} + z_t ⊙ \tilde{h}_t


Dimensions: GRU has 3 weight matrices per layer vs LSTM's 4. GRU total params = 3 × (h × (h + d) + h).
GRU vs LSTM tradeoffs:

- GRU has fewer parameters, trains faster, and needs less data

- LSTM has an explicit cell state that may better capture very long-range dependencies (>100 steps)

- In practice, GRU often matches LSTM performance on many tasks (especially with sufficient data)

- LSTM remains more common in academic baselines; GRU is preferred for compute-constrained settings
7.3 Bidirectional RNNs
A bidirectional RNN processes sequences in both forward and backward directions, then concatenates the representations.
Forward: h_t^→ = RNN_forward(x_t, h_{t-1}^→)
Backward: h_t^← = RNN_backward(x_t, h_{t+1}^←)
h_t = [h_t^→; h_t^←]


Each position's representation incorporates context from both past and future — essential for tasks like named entity recognition, POS tagging, and text classification where full sequence context helps.
Note: Bidirectional RNNs cannot be used for autoregressive generation (language modeling) because they peek at future tokens. They are used for sequence encoding tasks.
7.4 Depth and Stacking
Stacked RNNs (also called deep RNNs) have multiple recurrent layers:
h_t^(1) = RNN(x_t, h_{t-1}^(1))
h_t^(2) = RNN(h_t^(1), h_{t-1}^(2))
...
ŷ_t = W_hy · h_t^(L) + b_y


Each layer operates at a different timescale (higher layers tend to model slower-changing representations). Residual connections between layers help training for deep (>4 layer) stacks.
8. Sequence-to-Sequence Models and Attention
8.1 Encoder-Decoder Architecture

The seq2seq architecture (Sutskever et al., 2014; Cho et al., 2014) uses two RNNs:

Encoder: Reads the source sequence (x_1, ..., x_T) and produces a sequence of hidden states (h_1, ..., h_T) and a final context vector c = h_T (or a function of all hidden states)
Decoder: Generates the target sequence (y_1, ..., y_T') auto-regressively, conditioned on c

Encoder: 
h_t = RNN_enc(x_t, h_{t-1})


Decoder:
s_0 = tanh(W_c · c)  // initialize decoder state from context
s_t = RNN_dec(y_{t-1}, s_{t-1})
p(y_t | y_<t, c) = softmax(W_o · s_t)


8.2 Bahdanau Attention (Additive Attention)
The fixed context vector c becomes a bottleneck. Attention (Bahdanau et al., 2015) computes a dynamic context vector at each decoding step.
Attention mechanism:
// Alignment scores: how well encoder position j matches decoder position i
e_{ij} = v_a^T · tanh(W_a · s_{i-1} + U_a · h_j)

// Attention weights (normalized)
α_{ij} = exp(e_{ij}) / Σ_k exp(e_{ik})

// Context vector (weighted sum of encoder states)
c_i = Σ_j α_{ij} · h_j

// Decoder input (concatenate context with decoder input)
s_i = RNN_dec([y_{i-1}; c_i], s_{i-1})


Properties:

- The alignment model v_a^T · tanh(W·s + U·h) is a small MLP that is jointly trained

- Attention provides an alignment matrix that can be visualized to understand what the model focuses on

- The decoder directly accesses the full source sequence at each step, eliminating the bottleneck
8.3 Luong Attention (Multiplicative/Dot-Product Attention)
Luong et al. (2015) proposed simpler, more efficient attention variants:
Score functions:
dot:      score(s_i, h_j) = s_i^T · h_j
general:  score(s_i, h_j) = s_i^T · W_a · h_j
concat:   score(s_i, h_j) = v_a^T · tanh(W_a · [s_i; h_j])


Dot-product is the simplest and most efficient but requires matching dimensions. The "general" variant adds a learned transformation.
Global vs Local Attention:

- Global: Attends to all encoder positions (like Bahdanau)

- Local: Predicts a position p_t and attends to a window around it — computationally cheaper and differentiable
8.4 Teacher Forcing and Scheduled Sampling
Teacher Forcing: During training, feed the ground-truth previous token as decoder input at each step:
Training:  s_t = RNN_dec(y_{t-1}^*, s_{t-1})  // y* is ground truth
Inference: s_t = RNN_dec(ŷ_{t-1}, s_{t-1})    // ŷ is model-generated


Problem: Exposure bias — during inference, the model sees its own errors, which compound over time.
Scheduled Sampling: Gradually anneal from teacher forcing to autoregressive generation:
ε = max(ε_0 · exp(-k · epoch), ε_min)
Use y* with probability ε, ŷ with probability 1-ε


More robust alternatives to scheduled sampling:

- Professor forcing (Lamb et al., 2016): Adversarial training to make the hidden state distributions of teacher-forced and free-running modes indistinguishable

- Sequence-level objectives: Train with REINFORCE or minimum risk training to optimize discrete sequence metrics (BLEU, ROUGE)

- Dataset aggregation (DAgger): Collect rollouts and add them to the training set
8.5 Bucketing and Padding
Problem: Sequences in a batch have variable lengths. Padding to the max length in the dataset wastes computation.
Bucketing: Group sequences by length into buckets:
Buckets: [1-10], [11-20], [21-30], [31-50], [51-100]


Within each bucket, pad to the bucket max length. This reduces per-batch padding by 50-80%.
Implementation:

1. Pre-sort all training examples by length

2. Create buckets (manually or via quantile boundaries)

3. During training, shuffle within each bucket and sample batches from buckets

4. Optionally, weight bucket sampling probability by size
9. Autoencoders
9.1 Vanilla Autoencoder

An autoencoder learns to reconstruct its input through a bottleneck (lower-dimensional representation). It consists of an encoder f_φ and a decoder g_θ.
z = f_φ(x) = σ(W_e · x + b_e)         // encode
ŷ = g_θ(z) = σ'(W_d · z + b_d)        // decode
L = ||x - ŷ||_2^2                       // reconstruction loss


If both encoder and decoder are linear (σ = identity), the autoencoder learns the same subspace as PCA. Non-linear activations enable learning of non-linear manifolds.
Undercomplete vs Overcomplete:

- Undercomplete (bottleneck dim < input dim): Forces the model to learn efficient representations

- Overcomplete (bottleneck dim ≥ input dim): Risk of learning identity mapping; requires regularization
9.2 Denoising Autoencoder (DAE)
Vincent et al. (2008) proposed corrupting the input and training the autoencoder to reconstruct the clean original:
\tilde{x} = x + noise (e.g., Gaussian noise or masking)
z = f_φ(\tilde{x})
ŷ = g_θ(z)
L = ||x - g_θ(f_φ(x + noise))||_2^2


The model learns to denoise, which implicitly forces it to capture the data manifold (denoising requires understanding of the underlying structure).
Types of corruption:

- Gaussian noise: \tilde{x} = x + ε, ε ~ N(0, σ²)

- Masking noise: Randomly set a fraction of input dimensions to 0

- Salt-and-pepper noise: Randomly set dimensions to min/max values
Connection to score matching: Vincent (2011) showed that denoising autoencoders implicitly estimate the score function ∇_x log p(x).
9.3 Sparse Autoencoder
Adds a sparsity constraint on the hidden representation. This forces the model to use only a few active neurons per input, encouraging feature disentanglement.
Sparsity methods:

L1 penalty: L_sparse = L_recon + λ · ||z||_1
KL divergence sparsity: Enforce that average activation ρ̂_j of neuron j equals a target ρ (small, e.g., 0.05):

L_sparse = L_recon + β · Σ_j KL(ρ || ρ̂_j)
KL(ρ || ρ̂_j) = ρ · log(ρ/ρ̂_j) + (1-ρ) · log((1-ρ)/(1-ρ̂_j))



Competitive (winner-take-all) sparsity: Only the top-k activations survive; all others are zeroed during forward pass

Practical note: Sparse autoencoders have seen a major resurgence in 2023-2024 as a tool for mechanistic interpretability of LLMs — training sparse autoencoders on the residual stream activations to discover interpretable features.
9.4 Contractive Autoencoder (CAE)
Rifai et al. (2011) add a penalty on the Jacobian of the encoder — the sensitivity of the representation to small input changes:
L = L_recon + λ · ||J_f(x)||_F^2


Where J_f(x)_ij = ∂z_i / ∂x_j is the Jacobian of the encoder at x, and ||·||_F is the Frobenius norm.
For a sigmoid encoder z = σ(Wx + b):
||J_f(x)||_F^2 = Σ_i (σ'(W_i·x + b_i))² · ||W_i||_2^2


Properties:

- Encourages the representation to be locally invariant to input perturbations

- Explicitly penalizes the representation's variance along tangent directions of the data manifold

- Typically yields better features than DAEs for classification tasks

- Computationally expensive (requires JVP for each training example)
9.5 Variational Autoencoder (VAE)
The VAE (Kingma & Welling, 2014) is a generative model that merges autoencoders with variational inference. See Section 11 for complete treatment.
10. Generative Adversarial Networks (GANs)
10.1 The GAN Framework

Introduced by Goodfellow et al. (2014), GANs consist of two neural networks playing a minimax game:

Generator G(z; θ_g): Maps noise z ~ p(z) (e.g., N(0, I)) to data space, producing fake samples G(z)
Discriminator D(x; θ_d): Outputs probability that x is a real training sample (vs. generated/fake)

Objective (minimax game):
min_G max_D V(D, G) = E_{x ~ p_data}[log D(x)] + E_{z ~ p_z}[log(1 - D(G(z)))]


Vanilla GAN training loop:
for n iterations:
    // Train discriminator
    for k steps:
        Sample batch {z_i} from noise prior p(z)
        Sample batch {x_i} from real data
        ∇_D = ∇_θ_d [ (1/m) Σ log D(x_i) + (1/m) Σ log(1 - D(G(z_i))) ]
        θ_d ← θ_d + η · ∇_D

    // Train generator
    Sample batch {z_i} from noise prior p(z)
    ∇_G = ∇_θ_g [ (1/m) Σ log(1 - D(G(z_i))) ]
    θ_g ← θ_g - η · ∇_G


The non-saturating loss (recommended over the original): Instead of minimizing log(1 - D(G(z))), maximize log(D(G(z))). This provides stronger gradients early in training when D easily rejects G's samples.
10.2 Theoretical Properties
Global optimum: The optimal discriminator for a fixed generator is:
D*(x) = p_data(x) / (p_data(x) + p_g(x))


Substituting into the value function:
V(G, D*) = 2 · JSD(p_data || p_g) - 2·log(2)


Where JSD is the Jensen-Shannon divergence. Training G is equivalent to minimizing JSD — a proper divergence with minimum 0 when p_g = p_data.
Convergence and mode collapse:
In theory, GAN training has a unique Nash equilibrium at p_g = p_data, D(x) = 1/2. In practice:

- Mode collapse: Generator produces limited diversity (only a few modes of the data distribution)

- Non-convergence: The minimax optimization may oscillate rather than converge

- Vanishing gradients: When D is too strong, G receives near-zero gradient
10.3 DCGAN (Radford et al., 2015)
The first widely successful GAN architecture, establishing design guidelines:
Generator architecture:
z (100-dim noise) → FC → BN → ReLU
→ Transposed Conv 4×4 (512 channels) → BN → ReLU
→ Transposed Conv 4×4 (256 channels) → BN → ReLU
→ Transposed Conv 4×4 (128 channels) → BN → ReLU
→ Transposed Conv 4×4 (3 channels) → Tanh → 64×64 image


Discriminator architecture: Mirror of generator, using strided convolutions instead of transposed conv, Leaky ReLU (α=0.2), no batch norm in input layer.
Key guidelines:

1. Replace any pooling layers with strided convolutions (D) or fractional-strided convolutions (G)

2. Use batch norm in both networks (except G output and D input)

3. Remove fully-connected hidden layers (FC only before first conv in G)

4. Use ReLU in G (all layers except output Tanh)

5. Use LeakyReLU in D (all layers)
10.4 StyleGAN (Karras et al., 2019-2022)
StyleGAN v1 (2019):
Key innovation: Style-based generator that separates high-level attributes from stochastic variation.
Architecture changes from DCGAN:

1. Mapping network f: 8-layer MLP that maps latent z to intermediate latent w — the mapping network disentangles the latent space

2. AdaIN (Adaptive Instance Normalization) at each layer:
AdaIN(x_i, y) = y_{s,i} · (x_i - μ(x_i)) / σ(x_i) + y_{b,i}


Where y_s (scale) and y_b (bias) are derived from w. AdaIN injects style information.

3. Synthesis network G: Starts from a learned constant (4×4×512), not from a noise vector

4. Stochastic variation: Noise (Gaussian) injected per pixel per layer for fine-grained detail
Style mixing: Two different w vectors at different layers -> the coarse layers (4-8²) control pose/identity while fine layers (32-1024²) control colors/textures, demonstrating disentanglement.
StyleGAN v2 (2020):
Fixes droplets and blob artifacts in v1.
Architectural improvements:

1. Weight demodulation: Replace AdaIN with normalization based on the convolution weights:
W'_{ijk} = W_{ijk} / sqrt(Σ_k W_{ijk}^2 + ε)


This standardizes feature maps without explicit mean/variance computation.

2. Lazy regularization: Compute path length regularization every N steps (not every step) to speed training

3. No progressive growing — the network is trained at full resolution from scratch using a residual block structure

4. Better conditioning: Removes unnecessary noise inputs and biases
StyleGAN v3 (2021):
Addresses texture sticking — the tendency of generated features to be locked to specific pixel coordinates.
Key innovation: Aliasing-free operation — all layers are designed to respect the continuous signal processing pipeline:

- All up/downsampling uses proper low-pass filters (not nearest-neighbor or bilinear)

- Activation functions are designed to avoid creating aliased high frequencies

- The generator produces truly continuous representations that can be queried at arbitrary coordinates
StyleGAN v3 achieves unprecedented quality at any resolution and eliminates the "positional preference" artifacts of v2.
10.5 Conditional GANs (cGANs)
Both generator and discriminator receive a conditioning variable c (e.g., class label, text description, image):
min_G max_D V(D, G) = E_{x ~ p_data}[log D(x|c)] + E_{z ~ p_z}[log(1 - D(G(z|c)|c))]


Implementation: Simply concatenate the condition to the input of D and G (or use projection-based conditioning in advanced variants).
10.6 Pix2Pix (Isola et al., 2017)
Conditional GAN for image-to-image translation with paired data:

Generator U-Net: Skip connections between encoder and decoder preserve low-level details
Discriminator PatchGAN: Classifies N×N patches as real/fake rather than the whole image — enforces local texture/structure realism
Combined loss:

L = L_cGAN(G, D) + λ · L_L1(G)


Where L_L1(G) = E_{x,y}[||y - G(x)||_1] encourages the generator to stay close to the ground truth (L1 encourages less blur than L2).
U-Net Generator: Encoder-downsample → bottleneck → decoder-upsample with skip connections from each encoder layer to the corresponding decoder layer.
PatchGAN discriminator: Using a small receptive field (e.g., 70×70 patches) forces the model to focus on high-frequency local structure.
10.7 CycleGAN (Zhu et al., 2017)
Enables unpaired image-to-image translation without paired examples. Uses two generators (G: X→Y, F: Y→X) and two discriminators (D_X, D_Y).
Cycle consistency loss:
L_cyc(G, F) = E_{x ~ p_data}[||F(G(x)) - x||_1] + E_{y ~ p_data}[||G(F(y)) - y||_1]


Full objective:
L(G, F, D_X, D_Y) = L_GAN(G, D_Y, X, Y) + L_GAN(F, D_X, Y, X) + λ · L_cyc(G, F)


Theoretical guarantee: Cycle consistency prevents the degenerate solution where G maps all X to the same Y image — the cycle loss forces G and F to be near-inverses.
Identity loss (optional): L_id(G, F) = E_y[||G(y) - y||_1] + E_x[||F(x) - x||_1] — encourages the generator to preserve color composition when fed target-domain images.
10.8 BigGAN (Brock, Donahue, Simonyan, 2019)
Demonstrated high-fidelity class-conditional generation at large scale (up to 256×256 ImageNet).
Key techniques:

1. Spectral normalization in both G and D: Constrains the Lipschitz constant of each layer for training stability

2. Shared class embeddings: Class embeddings shared across generator layers

3. Skip connections in generator: For better gradient flow

4. Orthogonal regularization: Encourages weight matrices to be orthogonal (optional, not in final model)

5. Large batch size: 2048 samples per batch on 512 TPUs

6. Truncation trick: At inference, sample z from a truncated normal (sample values beyond 2σ are re-sampled). This trades diversity for fidelity.
Scaling insights: BigGAN showed that GANs benefit from scaling — larger models, larger batches, and more compute consistently improve FID.
10.9 Diffusion vs GAN Comparison



Property
GANs
Diffusion Models




Training
Adversarial (unstable, sensitive to hyperparameters)
Likelihood-based (stable)


Sample quality (FID)
Excellent (leading pre-2022)
State-of-the-art (post-2022)


Sample diversity
Can suffer mode collapse
Excellent (full distribution coverage)


Sample speed
Single forward pass (fast)
~50-1000 sequential denoising steps (slow)


Likelihood estimation
Not available (no tractable likelihood)
Available (continuous-time diffusion)


Latent space structure
Can be excellent (StyleGAN)
Linear in diffusion latent space


Training compute
Moderate
Higher (longer to converge)


Parameter sensitivity
Very high (requires careful tuning)
Moderate


Theoretical foundation
Nash equilibrium, JSD minimization
ELBO, score matching, SDE theory



When to use GANs: Latent space manipulation, real-time generation (single forward pass), domain-specific applications where FID is paramount.
When to use Diffusion: Maximum fidelity and diversity required, likelihood estimation needed, avoiding training instability.
11. Variational Autoencoders (VAEs)
11.1 Probabilistic Formulation

The VAE (Kingma & Welling, 2014) frames autoencoding as variational inference over a latent variable model.
Generative model (decoder): p_θ(x|z) · p(z)

- Prior: p(z) = N(0, I) (standard Gaussian)

- Likelihood: p_θ(x|z) — typically Gaussian (for real-valued x) or Bernoulli (for binary x)
Inference model (encoder/recognition): q_φ(z|x) ≈ p_θ(z|x)
11.2 The Evidence Lower Bound (ELBO)
We maximize the marginal log-likelihood log p_θ(x), which is intractable due to the integral over z. We instead maximize the ELBO:
log p_θ(x) = KL(q_φ(z|x) || p_θ(z|x)) + ELBO(θ, φ; x)


Since KL ≥ 0:
log p_θ(x) ≥ ELBO(θ, φ; x)


ELBO derivation:
ELBO(θ, φ; x) = E_{z ~ q_φ(z|x)}[log p_θ(x|z)] - KL(q_φ(z|x) || p(z))



Reconstruction term: E_{z~q}[log p_θ(x|z)] — how well does the decoder reconstruct x from z
KL regularization term: KL(q_φ(z|x) || p(z)) — how close is the approximate posterior to the prior

Full ELBO (minibatch form):
L(θ, φ; x) = E_{z ~ q_φ(z|x)}[log p_θ(x|z)] - β · KL(q_φ(z|x) || N(0, I))


Where β = 1 for standard VAE. (See β-VAE below.)
11.3 The Reparameterization Trick
The sampling operation z ~ q_φ(z|x) is non-differentiable. The reparameterization trick moves the randomness outside the network:
Instead of: z ~ N(μ_φ(x), σ_φ²(x)), we write:
ε ~ N(0, I)
z = μ_φ(x) + σ_φ(x) ⊙ ε


Now z is a deterministic function of φ and ε, and gradients can flow from the decoder loss back through μ_φ and σ_φ.
Without reparameterization: ∇_φ E_z[q] requires score function estimator (REINFORCE) — high variance.
With reparameterization: ∇_φ E_ε[p(x|μ+σ⊙ε)] is a standard Monte Carlo gradient — low variance.
11.4 VAE Loss Computation (Per Example)
// Encoder
μ_z, log_σ_z² = encoder_φ(x)
σ_z = exp(0.5 · log_σ_z²)

// Sample z via reparameterization
ε ~ N(0, I)
z = μ_z + σ_z ⊙ ε

// Decoder
ŷ = decoder_θ(z)

// Reconstruction loss (Gaussian decoder, σ²=1)
L_recon = ||x - ŷ||_2² / (2 · σ²) + 0.5 · log(2π · σ²)
        = ||x - ŷ||_2² / 2 + const (for σ²=1)

// For Bernoulli decoder (binary x):
L_recon = -Σ [x_i · log(ŷ_i) + (1-x_i) · log(1-ŷ_i)]

// KL divergence: KL(N(μ_z, σ_z²) || N(0, I))
L_KL = 0.5 · Σ (μ_z_i² + σ_z_i² - 1 - log(σ_z_i²))

// Total loss
L = L_recon + L_KL   // (for β=1)


11.5 KL Divergence Derivation
For two multivariate Gaussians with diagonal covariance:
KL(q || p) = ∫ q(z) · log(q(z)/p(z)) dz

q(z) = N(z; μ, σ²I)
p(z) = N(z; 0, I)

KL = 0.5 · [tr(σ²I) + μ^T μ - k - log|σ²I|]
   = 0.5 · Σ_j (σ_j² + μ_j² - 1 - log σ_j²)


Where k is the dimensionality of z.
11.6 β-VAE (Higgins et al., 2017)
Adds a weight β to the KL term:
L = E[log p_θ(x|z)] - β · KL(q_φ(z|x) || p(z))


β > 1 (>1): Stronger constraint on the latent bottleneck. Encourages disentanglement — each dimension of z captures an independent factor of variation (e.g., rotation, scale, color in images).
Tradeoff: Higher β → more disentangled but worse reconstruction (the "information bottleneck" tradeoff).
β = 4-8 typically gives good disentanglement on simple datasets (dSprites, 3D Shapes). For complex data, annealing β from 0 to the target value helps.
Annealed VAE (Bowman et al., 2016): Gradually increase β from 0 during training (KL annealing). Prevents the model from ignoring the latent variable (a common failure where the decoder learns to be autoregressive and ignores z — "posterior collapse").
11.7 VQ-VAE (van den Oord et al., 2017)
Discrete latent variable model that avoids the "posterior collapse" issue of continuous VAEs.
Architecture:

1. Encoder produces continuous representation z_e(x)

2. Vector quantization (VQ) maps z_e to nearest embedding e_k in a learned codebook {e_1, ..., e_K}:
z_q(x) = e_k where k = argmin_j ||z_e(x) - e_j||_2



Decoder reconstructs x from z_q

Loss function:
L = ||x - decoder(z_q)||_2²       // reconstruction
  + ||sg[z_e(x)] - e||_2²          // codebook loss (move embeddings toward encoder)
  + β · ||z_e(x) - sg[e]||_2²      // commitment loss (move encoder toward embeddings)


Where sg[·] is the stop-gradient operator. β is typically 0.25.
Straight-through gradient estimator: The gradient of the VQ operation (argmin is non-differentiable) is approximated by copying gradients from z_q directly to z_e. This works because z_e and z_q are close.
VQ-VAE-2 (Razavi et al., 2019): Hierarchical VQ-VAE with multiple latent scales (e.g., top-level captures global structure, bottom-level captures local texture). Produces high-fidelity 1024×1024 images.
Practical use: VQ-VAE is the backbone of many modern generative models:

- DALL-E (discrete VAE tokenizer for text-to-image)

- Image GPT (VQ-VAE tokens → autoregressive Transformer)

- Parti (ViT-VQGAN)
11.8 VAE vs GAN vs Diffusion



Property
VAE
GAN
Diffusion




Likelihood
ELBO (lower bound)
Not available
Exact (continuous)


Sample quality
Often blurry
Sharp (can be excellent)
State-of-the-art


Mode coverage
Excellent (full distribution)
Poor (mode collapse)
Excellent


Training stability
Stable
Unstable
Stable


Latent space
Well-structured
Variable
Well-structured


Computational cost
Low (single pass)
Low (single pass)
High (many steps)



12. Normalizing Flows
12.1 The Change of Variables Formula

Normalizing flows model a complex distribution p_X(x) by applying an invertible transformation f to a simple base distribution p_Z(z) (typically N(0, I)):
x = f(z) where f is invertible, z = f^{-1}(x)


The density is given by the change of variables:
p_X(x) = p_Z(f^{-1}(x)) · |det(J_f⁻¹(x))|
       = p_Z(z) · |det(J_f(z))|^{-1}


Where J_f(z) is the Jacobian of f at z.
The key constraint: The Jacobian determinant must be tractable. This has driven flow architecture design.
12.2 RealNVP (Dinh et al., 2017)
RealNVP uses affine coupling layers — a clever choice that makes the Jacobian triangular.
Affine coupling layer:
Given input u ∈ ℝ^D, split into two parts: u_1 = u_{1:d}, u_2 = u_{d+1:D}.
v_1 = u_1
s, t = NN(u_1)    // scale and translation from neural network
v_2 = u_2 ⊙ exp(s) + t

// Output: v = [v_1; v_2]


Inverse:
u_1 = v_1
s, t = NN(v_1)
u_2 = (v_2 - t) ⊙ exp(-s)


Jacobian determinant:
The Jacobian of the coupling layer is lower triangular:
J = [ I         0   ]
    [ ∂v_2/∂u_1  diag(exp(s)) ]

det(J) = Π_i exp(s_i) = exp(Σ_i s_i)


This is trivially computable without evaluating the full Jacobian.
Masking: Alternate between splitting patterns (checkerboard vs channel-wise) across layers to ensure all dimensions interact.
Multi-scale architecture: Use squeeze operations to trade spatial resolution for channels, then apply coupling layers at each scale.
12.3 Glow (Kingma & Dhariwal, 2018)
Extends RealNVP with:


Actnorm (Activation Normalization): A learnable per-channel scale and shift, initialized such that the first minibatch has zero mean and unit variance. Faster than batch norm and works with invertibility.


Invertible 1×1 convolution: A learned permutation of channels. The determinant is det(W) where W is the D×D weight matrix. This is computed via LU decomposition of W for O(D) cost instead of O(D³).


Affine coupling layers (same as RealNVP)


Glow architecture:
x → ActNorm → Invertible 1×1 Conv → AffineCoupling → Squeeze → [repeat]


Log-likelihood computation for a batch:
log p(x) = log p(z) + Σ_log_det(J_l)
         = -0.5 · Σ z_i² - 0.5 · D · log(2π) + Σ_l log|det(J_l)|


12.4 Flow-Based Generative Model Training
ALGORITHM: Flow Training (Maximum Likelihood)
─────────────────────────────────────────────
for each batch {x_i}:
    // Forward: x → z
    z, log_det_sum = f^{-1}(x)  // invertible transformation
    // z_i should be ~ N(0, I) if model captures data

    // Log-likelihood
    log_p_x = log_p_z(z) + log_det_sum
    // log_p_z(z) = -0.5 * Σ z_i² - 0.5 * D * log(2π)

    Loss = -mean(log_p_x)  // negative log-likelihood

    θ ← θ - η · ∇_θ Loss  // standard gradient descent


Sampling:
z ~ N(0, I)
x = f(z)  // generate new data


12.5 Flow Limitations

Volume preservation: Each transformation must be invertible with tractable determinant, constraining expressivity
Computational cost: Forward and inverse passes are both needed, each roughly 2× the cost of a standard forward pass
Dimensionality constraint: Flow must transform to same-dimensional latent space (no dimensionality reduction/fixed compression)
Less widely adopted than VAEs or diffusion for large-scale generation, though flows remain important in:
Variational inference: As flexible posterior approximations for VAEs
Density estimation: For low-dimensional data with known structure
Audio generation: WaveGlow, WaveFlow

12.6 Residual Flows
An alternative to coupling-based flows using invertible residual networks (i-ResNet, Behrmann et al., 2019):
z → z + g(z) → z'


With Lipschitz constraint on g (via spectral normalization), the inverse can be approximated via fixed-point iteration. The log-determinant is estimated via a stochastic trace estimator (Hutchinson's trace) using the Neumann series or Russian roulette estimator.
📄 Data Engineering for AI: Building the Foundation — 627 lines
AlignmentBERTBenchmarkData EngineeringEvaluationFine-tuningGNNGPTGPUGovernance
1. Introduction
Data is the foundation of every AI system. The quality, quantity, and diversity of training data determine model capabilities more than architecture or compute. A poorly curated dataset cannot be compensated by a larger model, but a well-curated dataset can make smaller models competitive with much larger ones.

The Data Trilemma: Every dataset faces three competing constraints:

1. Scale (enough data for generalization)

2. Quality (high signal-to-noise ratio)

3. Diversity (coverage of desired capabilities)
Optimizing all three simultaneously is the central challenge of data engineering for AI.
1.1 The Data Pipeline at Scale
Raw Data Sources
    ↓
Data Collection → Crawling, APIs, Licensing, Partnerships
    ↓
Data Processing → Extraction, Normalization, Language Detection
    ↓
Data Filtering → Quality, Safety, PII, Deduplication, Decontamination
    ↓
Data Selection → Mixing, Curriculum, Heuristic/Metric-based Selection
    ↓
Data Preparation → Tokenization, Formatting, Packing, Shuffling
    ↓
Training Ready → Sharded, Indexed, Ready for Loaders


2. Data Collection Strategies
2.1 Web Crawling

The primary source of pre-training data for most LLMs.
Crawling Infrastructure:

- Common Crawl: Free, publicly available crawl of 50B+ web pages. Used by GPT-3, LLaMA, Mistral, most open models. Monthly snapshots, 50-80 TB per month.

- Custom Crawling: For domain-specific data or curation control. Frameworks: Scrapy, Apache Nutch, StormCrawler.

- Human-Curated: Wikipedia, Books (Project Gutenberg, Bibliotik), Academic papers (arXiv, PubMed, Semantic Scholar), Code (GitHub, Stack Overflow).
Crawling Challenges:

- DNS resolution: Billions of domain lookups needed

- Politeness: Rate limiting to avoid overwhelming servers

- Freshness: Content changes over time; need periodic re-crawls

- Exclusion: robots.txt compliance, content restrictions

- Language: Detecting/classifying languages for multi-lingual training
2.2 Licensed Data
Increasingly important as copyright concerns grow:

Reddit: Licensed to Google (Gemini), $60M/year
Stack Overflow: Licensed to OpenAI
News Corp: Licensed to OpenAI ($250M+)
Shutterstock: Licensed to OpenAI, Meta
Getty Images: Licensed to NVIDIA, Google
AP News: Licensed to OpenAI
GitHub Code: Training data for code models (Copilot, Codex, StarCoder)
Scientific articles: PubMed Central (open), Elsevier (licensed), Springer (licensed)

2.3 Domain-Specific Data Collection
Code Models:

- GitHub public repositories (filtered by license, language, quality)

- Stack Overflow Q&A

- Documentation (readthedocs, MDN, official docs)

- Code review datasets

- Jupyter notebooks with outputs
Medical Models:

- PubMed abstracts and full-text articles

- Clinical trial registries (ClinicalTrials.gov)

- Electronic Health Records (de-identified)

- Medical textbooks, guidelines

- FDA documents, drug labels
Legal Models:

- Court cases (PACER, case.law, CourtListener)

- Legislation (Congress.gov, state legislatures)

- Regulations (Federal Register, Code of Federal Regulations)

- Legal documents (contracts, briefs, filings)

- Patent databases (USPTO, EPO, WIPO)
3. Data Quality and Filtering
3.1 Heuristic Filtering

Simple, fast filters applied before model-based filtering:



Filter Type
Description
Example Threshold




Length filter
Too short or too long documents are noise
200-100,000 tokens


Symbol-to-word ratio
High symbol content = low quality
<0.5 ratio of symbols


Stop word frequency
Indicates natural language
>0.1 stop word ratio


Character repetition
Gibberish detection
<0.5 repeated character ratio


Word repetition
Keyword stuffing detection
<0.3 repeated word ratio


Language detection
Keep only desired languages
fastText, CLD2, LangDetect


Perplexity filter
High perplexity = off-distribution
Train a small LM, filter outliers


Toxicity filter
Remove explicitly harmful content
Classifier-based


PII filter
Remove or flag personal information
Regex, NER, classifier



3.2 Quality Classifiers
Train a classifier to predict whether a document is "high quality":
Training Data:

- Positive: Wikipedia, books, curated articles

- Negative: Uncategorized web pages, spam, low-quality content
Architecture:

- FastText (fast, good for many languages)

- BERT/RoBERTa (more accurate, slower)

- Custom transformer (domain-specific)
LLaMA 3 Approach: Used a transformer-based quality classifier to score and filter 15T+ tokens from 5× that raw data. The classifier was trained on 10K+ hand-labeled examples covering 100+ quality dimensions.
3.3 Perplexity Filtering
Train a small reference model (e.g., KenLM, 6M-parameter transformer) and filter documents where the model assigns high perplexity (surprising content).
Use: Remove documents that are unlike the distribution of high-quality text. Documents about rare topics, unusual formatting, or off-domain content get filtered.
LLaMA 2 Approach: Perplexity filtering removed URLs with very high or very low perplexity relative to a Wikipedia-based reference model.
3.4 FineWeb Quality Signals
The FineWeb dataset (Hugging Face, 2024) introduced multiple quality signals for web data:



Signal
Method
What It Measures




C4 quality
Heuristic filters from C4 dataset
Basic web page quality


WET quality
Character-level statistics
Formatting consistency


DupLM score
LM-based duplication detection
Uniqueness of content


URL score
URL structure analysis
Likelihood of being spam/not


Category score
GNN-based on page structure
Indicates article-like quality


Domain quality
Aggregated per-domain rating
Domain-level trustworthiness



4. Data Deduplication
Deduplication is one of the most important and impactful data processing steps. It improves model performance by preventing memorization and reducing training redundancy.

4.1 Exact Deduplication
Remove identical documents:
Techniques:

- Hash-based (SHA256, MD5 of normalized text)

- Bloom filters for memory-efficient de-duplication at scale

- Hash tables for exact matching
Scale: LLaMA 3 deduplicated 30 trillion tokens → removed ≈10-15% of data

Impact: Prevents models from memorizing specific examples, improves generalization
4.2 Near-Deduplication
Remove documents that are similar but not identical:
Locality-Sensitive Hashing (LSH):

- MinHash: Jaccard similarity estimation

- SimHash: Cosine similarity via hash collisions

- Parameters: number of hashes, bands, rows per band

- Typically: 256 hashes, 16 bands, 16 rows = similarity threshold ~0.75
Document/Fuzzy Deduplication:

- Prefix filtering: documents sharing long prefix are similar

- Edit distance: Levenshtein, Damerau-Levenshtein

- k-mer overlap: DNA-inspired (ATCG for nucleotides → tokens for text)
Sentence-Level Deduplication:

- Find repeated sentences across documents

- Flag documents with excessive repeated sentences

- Important for: news articles (same story from multiple sources)
Embedding-Based Deduplication:

- Embed documents → cluster embeddings → remove near neighbors

- More expensive but more accurate

- Pre-filter with LSH, then use cosine similarity for final dedup
4.3 Datasets and Deduplication Rates



Dataset
Raw Size
After Basic Dedup
After Near-Dedup
Retention Rate




Common Crawl (2024)
100T tokens
~60T tokens
~40T tokens
40%


C4
~800B
~360B
~180B
22%


RefinedWeb
5T tokens
—
~0.6T tokens
12%


FineWeb
15T tokens
—
~3.4T tokens
23%


LLaMA 3
30T+ tokens
—
~15T tokens
~50%



5. Data Decontamination
Decontamination ensures that evaluation data does not overlap with training data. Contamination inflates benchmark scores and masks true model capability.

5.1 n-gram Matching
Method: Check if any n-gram from an evaluation example appears in the training data.
n-gram sizes: typically 8-13 for text, 50+ for code

Threshold: If an n-gram match is found, the example is contaminated
Issues:

- Too short n-grams: false positives (common phrases)

- Too long n-grams: false negatives (rephrased contamination)

- Simple rephrasing bypasses n-gram detection
5.2 Contamination Detection at Scale
Prefix-based matching: Check if the first 50 characters of an eval question match training data — if so, the model likely saw the exact or near-exact question.
Embedding-based: Embed eval queries → find nearest neighbors in training data → manual inspection of matches.
Training dynamics: Monitor loss curve for eval data during training — if loss drops suspiciously fast, the model may have seen similar data earlier.
Exact submission matching: For coding benchmarks (HumanEval, MBPP), check if eval problems or solutions appear in training data (Stack Overflow, GitHub).
5.3 Known Contamination Incidents



Model
Contamination
Impact




GPT-3
Training data included Wikipedia, which overlaps with many benchmarks
Overstated few-shot learning (memorization vs generalization)


Codex
Training on GitHub included code similar to HumanEval problems
Up to 40% of HumanEval solutions may have been seen


LLaMA 1
Training on C4/C4 overlaps with many eval datasets
Multiple benchmarks likely inflated


GPT-4 Technical Report
Acknowledged contamination but argued it was "limited"
Unknown


DeepSeek-R1
Explicit contamination analysis — reported minimal
Cleanest large-scale contamination report



5.4 Best Practices

Publish contamination analysis with model releases (method + results)
Use multiple benchmark versions (augmented, paraphrased, translated)
Hide benchmark data sources from crawlers (robots.txt)
Post-hoc decontamination: Remove contaminated examples from eval + re-evaluate
Dynamic benchmarks: LiveBench, HumanEval+, fresh data regularly

6. Data Mixing and Curriculum
6.1 The Data Mixing Problem

Given multiple data sources (web, books, code, math, science), what proportions produce the best model?
Key Findings:

- Web data: Provides broad knowledge but is noisy (typically 50-70% of mix)

- Books/long-form: Improves coherence, narrative understanding (5-15%)

- Code: Improves reasoning, logical structure, instruction following (5-20%)

- Math/science: Improves formal reasoning (2-10%)

- Academic papers: Improves technical depth (2-10%)
6.2 Optimal Data Mixes from Major Models



Model
Web
Books
Code
Math
Academic
Other




GPT-3
60%
20%
5%
3%
7%
5%


LLaMA 1
67%
15%
4%
—
4%
10%


Chinchilla
80%
10%
—
—
10%
—


LLaMA 2
65%
10%
5%
5%
5%
10%


LLaMA 3
50%
15%
15%
5%
5%
10%


Qwen 2.5
55%
10%
15%
8%
7%
5%


DeepSeek-V2
50%
12%
15%
10%
8%
5%



6.3 Curriculum Learning
Train on easier data first, harder data later:
Data Ordering Heuristics:

- Perplexity-based: Lower-perplexity first (web data), higher-perplexity later (code, math)

- Document length: Short first (for learning token statistics), longer later (for coherence)

- Quality score: Higher quality first (essential patterns), lower quality later (broad coverage)

- Domain ordering: Wikipedia → web → books → code → math → academic
LLaMA 3 Curriculum:

1. Start: web data (broad coverage, learn token patterns)

2. Middle: code + web (develop reasoning)

3. Late: math + science (specialized reasoning)

4. Final mix: anneal on high-quality data
6.4 Annealing and Data Quality Upsampling
Annealing: In the final stages of training, increase the proportion of high-quality data (curated, human-written). This "polishes" the model without changing its broad knowledge.
LLaMA 3: Used 1.5T tokens of annealed high-quality data at the end of training

Mistral: Annealed on 1T tokens of high-quality curated data

Chinchilla: Showed longer training on more data beats training on less compute-optimal data (contradicting Kaplan scaling)
6.5 Data Selection by Model Feedback
Model-based data selection:

1. Train a small model on a subset of data

2. Evaluate on a held-out validation set

3. Identify which data points contributed most to improvement

4. Upsample those data types
DSIR (Data Selection via Importance Resampling): Resample from a large pool to match a target distribution of high-quality data. Used by Pythia, LLaMA.
DoReMi (Domain Reweighting with Minimax): Optimize data weights to minimize worst-case domain loss. Automatically finds optimal mixing ratios.
7. Synthetic Data Generation
7.1 When to Use Synthetic Data




Use Case
Best For
Limitations




Instruction-tuning data
SFT data (query → response pairs)
Risk: model collapse if purely synthetic


Code generation training
Functions, tests, documentation
Works well — code is verifiable


Math problem generation
Reasoning training, RLHF steps
Quality control needed for correctness


Preference data for alignment
RLHF pairs (chosen/rejected)
Might amplify existing model biases


Data augmentation
Increasing diversity of existing data
Requires careful quality filtering


Long-context data
Need long examples for context-window training
Complex to generate correctly


Domain-specific training
Specialized knowledge areas (medicine, law)
Requires seed data from domain experts



7.2 Techniques
Self-Instruct (Stanford, 2022):

1. Seed tasks: write 175 diverse instruction templates

2. Generate instructions: for each template, use LLM to produce concrete instructions

3. Generate responses: for each instruction, use LLM to produce a response

4. Filter: remove low-quality, duplicate, or off-topic samples

5. Repeat: with each iteration, expand the instruction pool
Evol-Instruct (WizardLM, 2023):

1. Depth evolving: "Make this instruction more complex by adding constraints"

2. Breadth evolving: "Generate a different, novel instruction on the same topic"

3. Each iteration makes instructions harder and more diverse

4. Result: SFT data that teaches models to handle complex instructions
Data Dreaming (Meta, 2024):

- Generate coherent multi-turn conversations from single prompts

- Simulate realistic user interactions with an LLM playing the "user" role

- Used for: chatbot training data where real conversations are scarce
7.3 Model Collapse
When synthetic data is used recursively (training on model outputs), quality degrades:
Generation 1: Real data → Model A
Generation 2: Model A's outputs → Model B (trained on A's outputs + real)
Generation 3: Model B's outputs → Model C
...
Generation N: Models drift toward low-variance, generic outputs


Mitigation Strategies:

- Always mix synthetic with real data (≥30% real)

- Filter generated data aggressively (quality classifiers, human review)

- Use diversity constraints during generation

- Periodically refresh from real data sources

- Use multiple model architectures for generation
8. Data Annotation and Labeling
8.1 Annotation Types




Type
Description
Typical Cost
Best For




Binary labels
Good/bad, relevant/irrelevant
$0.05-0.10/sample
Safety filtering, preference data


Categorical labels
Topic, sentiment, toxicity category
$0.10-0.50/sample
Quality classification


Ranking labels
Ranking of multiple responses
$0.50-2.00/comparison
RLHF reward modeling


Free-text critique
Write feedback on model output
$2.00-10.00/task
Detailed alignment data


Demonstration writing
Write ideal response from scratch
$5.00-20.00/response
SFT data


Expert annotation
Domain-expert labeled data (medical, legal)
$20.00-100+/sample
Specialized domains



8.2 Annotation Platforms



Platform
Type
Scale
Quality




Scale AI
Managed workforce
Massive
High (managed)


Surge AI
AI-specialized annotators
Large
Very high


LabelBox
Self-managed + marketplace
Medium-large
Variable


Appen
Crowd + managed
Massive
Medium


Amazon SageMaker Ground Truth
Managed + auto-labeling
Large
High


Prodigy
In-house annotation tool
Small-medium
High (in-house)


Label Studio
Open-source tool
Custom
Custom



8.3 Quality Control
Inter-annotator agreement:

- Measure: Cohen's κ (2 annotators), Fleiss' κ (3+ annotators)

- Target: κ > 0.7 for clear categories, κ > 0.5 for subjective tasks

- Low agreement → refine instructions, retrain annotators, or use adjudication
Adjudication:

- Third annotator resolves disagreements

- Expert reviewer for final decisions on contested labels
Gold Standard Questions:

- Insert known-quality questions into annotation batches

- Annotators who fail gold standards → retraining or removal
9. Data Governance and Compliance
9.1 Copyright and Licensing

Current Legal Landscape (2026):

- Training on copyrighted data is being challenged in courts worldwide

- Authors Guild vs OpenAI (SDNY, ongoing)

- NYT vs OpenAI and Microsoft (SDNY, ongoing)

- Getty Images vs Stability AI (UK High Court, ongoing)

- European copyright directive: text and data mining exception for research

- Japan Copyright Law: allows TDM for AI training

- Singapore Copyright Act: allows TDM for AI training
Mitigation Strategies:

- Licensing data directly (OpenAI's approach: $1B+ in licensing deals)

- Using only public domain/Creative Commons/open-source data

- Opt-out mechanisms: websites can declare AI training exclusion

- Model output fingerprinting (detect memorized copyrighted content)
9.2 Privacy and PII
PII Types to Handle:

- Names, addresses, phone numbers, email addresses

- Social security numbers, passport numbers, driver's license numbers

- Medical records, biometric data

- Financial account numbers

- User credentials, tokens, API keys
PII Detection:

- Regex patterns for structured PII (SSN, credit cards)

- NER models for unstructured PII (names, addresses)

- Rule-based heuristics for context-based PII

- Embedding-based for novel PII patterns
PII Handling:

- Removal: Replace PII with placeholder ([NAME], [PHONE])

- Generalization: Replace "123 Main St, Springfield" with "Springfield"

- Synthesis: Replace real PII with realistic fake PII

- Suppression: Remove entire documents containing PII above threshold
10. Data Infrastructure and Pipelines
10.1 Storage Systems




System
Best For
Scale
Strengths




HDFS
Large raw data storage
10+ PB
Batch processing native


S3/GCS/Blob
Cloud-native object storage
Unlimited
Scalable, durable, streaming


NFS/Lustre
High-throughput model access
100+ TB
Direct mounting, GPU cluster native


SQL databases
Metadata, annotations
10+ TB
ACID, indexing, querying


Vector databases
Embedding storage, similarity search
10B+ vectors
ANN search, hybrid search



10.2 Processing Frameworks

Apache Spark: Distributed data processing, ETL at petabyte scale
Apache Beam: Unified batch + streaming pipeline model
Ray Data: ML-native data processing with Python-first API
Dask: Parallel computing in Python for moderate scale
Apache Flink: Real-time streaming data processing

10.3 Data Loaders for Training



Loader
Ecosystem
Features




PyTorch DataLoader
PyTorch
Distributed, sharded, streaming


MosaicML Streaming
Composer
Cloud-native streaming from S3/GCS


WebDataset
PyTorch
Tar-based efficient data storage


Hugging Face Datasets
HF Transformers
Hub integration, caching, processing


DeepSpeed Data Efficiency
DeepSpeed
Mixed precision, on-demand loading



11. Data for Fine-Tuning
11.1 Instruction-Tuning Data

Essential Properties:

- Diversity: Instructions should cover many use cases, domains, and formats

- Difficulty: Mix of easy, medium, and hard instructions

- Format consistency: Consistent instruction format for generalization

- Answer quality: Well-written, accurate responses
Key Datasets:



Dataset
Size
Description
Quality




ShareGPT
100K+
Real user-shared conversations
Variable


OpenAssistant
150K
Human-annotated human-AI conversations
High


Dolly
15K
Databricks employee-written tasks
Very high


User-or-LLM
200K
Mix of human and LLM-generated data
Medium-high


No Robots
10K
Hand-curated by Hugging Face team
Very high


LIMA
1K
Minimal, highest-quality SFT data
Highest



11.2 Data Composition for Fine-Tuning



Component
Proportion
Purpose




General instruction following
40-60%
Broad capabilities


Chat/multi-turn
10-20%
Conversation ability


Reasoning (math, logic)
10-15%
Reasoning improvement


Code
5-10%
Code generation


Safety/refusal
5-10%
Safety behavior


Structured output (JSON)
2-5%
Format compliance



12. Data for RLHF and Alignment
12.1 Preference Data Construction

Collection Pipeline:

1. Generate multiple responses per prompt from different models/configurations

2. Present responses to human annotators

3. Collect pairwise preferences (which is better?)

4. Also collect: ranking, rating, justification

5. Quality metrics: inter-annotator agreement, label distribution
Preference Data Dimensions:

- Helpfulness: Which response better addresses the user's intent?

- Harmlessness: Which response is safer and more appropriate?

- Honesty: Which response is more truthful?

- Format: Which response is better structured?
Data Scale for RLHF:

- Reward model training: 100K-1M+ preference comparisons

- PPO training: 10K-100K prompts for online generation

- Anthropic's RLHF data: 1M+ preference comparisons

- OpenAI's InstructGPT: 20K+ demonstrations + 40K+ comparisons
📄 Training Methodologies — 3276 lines
A comprehensive, deeply technical exploration of training methodologies for modern deep learning and large language models. Covers pre-training objectives, data pipelines, scaling laws, fine-tuning, RLHF/alignment, instruction tuning, synthetic data, and augmentation — with complete mathematical derivations, pseudocode, and practical implementation guidance.
AlignmentAttentionBERTBenchmarkCLIPConstitutional AIDPODeploymentEnsembleEvaluation
1. Pre-Training Objectives
1.1 Autoregressive Language Modeling

The autoregressive (AR) objective — also called causal LM — is the most fundamental and widely used pre-training objective. The model predicts the next token given all previous tokens, factorizing the joint probability via the chain rule:
p(x) = Π_{t=1}^{T} p(x_t | x_{<t})


Training loss (next-token prediction):
L_AR(θ) = -Σ_{t=1}^{T} log p_θ(x_t | x_{1:t-1})


Properties:

- Causal masking: Each token can only attend to preceding tokens (left-to-right)

- Inherently generative: The model can generate text autoregressively

- Zero-shot capabilities: Emergent abilities at sufficient scale (GPT-2, GPT-3)

- Token efficiency: Every token is used for both context and prediction (no "wasted" tokens like MLM)
Implementation:
# Autoregressive forward pass
def autoregressive_loss(model, tokens, attention_mask=None):
    logits = model(tokens)  # [batch, seq_len, vocab_size]
    # Shift: predict token t from context of tokens[:t]
    shift_logits = logits[:, :-1, :].contiguous()
    shift_labels = tokens[:, 1:].contiguous()
    loss = cross_entropy(shift_logits.view(-1, vocab_size), shift_labels.view(-1))
    return loss


Architectures using AR objective:

- GPT family (GPT-1, GPT-2, GPT-3, GPT-4)

- Llama / Llama 2 / Llama 3

- Mistral / Mixtral

- PaLM / Gemini

- Qwen / DeepSeek

- Gemma / Phi
1.2 Masked Language Modeling (MLM)
Introduced by BERT (Devlin et al., 2019), MLM randomly masks some input tokens and trains the model to predict them from the bidirectional context.
Objective:
L_MLM(θ) = -Σ_{t ∈ masked} log p_θ(x_t | x_mask)


Masking strategy (BERT-style):

- Randomly select 15% of tokens in each sequence

- Of the selected tokens:

  - 80% replaced with [MASK]

  - 10% replaced with random token

  - 10% left unchanged
This mitigates the mismatch between pre-training (masked) and fine-tuning (unmasked) input.
Efficiency concern: Only 15% of tokens are used for computing the loss. This makes MLM less token-efficient than AR.
Variants:

- Whole Word Masking (WWM): Mask all tokens in a word together (used by RoBERTa)

- Entity-level Masking: Mask named entities or phrases

- Span-level Masking: Mask contiguous spans of tokens (used by SpanBERT)
1.3 Prefix Language Modeling
Also known as Prefix LM or Causal MLM, this objective combines elements of AR and MLM (UniLM, Dong et al., 2019).
Formulation:

Given a sequence split into two parts:

- Prefix (first k tokens): Bidirectional attention — tokens attend to all other tokens in the prefix

- Suffix (remaining tokens): Causal attention — each token attends to all prefix tokens and previous suffix tokens
Training loss:
L = -Σ_{t=k+1}^{T} log p_θ(x_t | x_{1:k}, x_{k+1:t-1})


Properties:

- Efficient for encoder-decoder tasks: the prefix acts as the "encoder" input

- Used in T5's "prefix LM" mode, GLM (Du et al., 2022)

- Less common than pure AR or span corruption in modern models
1.4 Span Corruption / Denoising Objective
T5 (Raffel et al., 2020) introduced span corruption: replace contiguous spans of tokens with a single sentinel token, and train the model to predict the dropped-out tokens.
Formulation:
Input:  "The [MASK_0] and [MASK_1] in the park."
Target: "[MASK_0] best [MASK_0] walked [MASK_1] dog [MASK_1] <EOS>"


Procedure:

1. Sample a mean span length λ (e.g., λ=3) and corruption rate ρ (e.g., ρ=0.15)

2. Randomly select corrupted spans such that ~ρ·T tokens are masked

3. Replace each span with a unique sentinel token (, , ...)

4. Target: concatenate the sentinel tokens + their corresponding spans in order
Properties:

- More token-efficient than MLM (no unmasked tokens in loss)

- Encourages long-span generation (harder than single-token prediction)

- The model learns to both understand corrupted input and generate coherent output — naturally suited for encoder-decoder architectures

- Can be applied in decoder-only mode (called "masked LM with causal masking" in some works)
Span Masking vs Token Masking (variance analysis):
Span corruption has higher variance per gradient step but also provides more learning signal per masked token. The optimal span length depends on the data modality: λ=3 for general text, λ=6 for code, λ=1 for tasks requiring fine-grained token prediction (entities).
1.5 UL2 Objectives
UL2 (Tay et al., 2022) unified multiple pre-training objectives within a single model using a mixture-of-denoisers framework.
Three denoising paradigms:
1. S-denoising (Span corruption):

Standard T5-style span corruption with medium spans. Enables next-token prediction at scale.
2. X-denoising (Extreme denoising):

Large corruption rates (50-100%) with large span lengths. Teaches the model to generate long coherent passages from minimal context.
3. R-denoising (Prefix LM):

Causal prefix + full generation suffix. Prepares the model for tasks like summarization and dialogue.
Training formulation:
UL2 alternates between these modes, either deterministically or stochastically. The modes can use:

- A common Transformer backbone

- Mode-specific attention masks (non-causal for S/X, causal for R)

- Mode-specific sentinel tokens (optional)
Key insight: Different denoising objectives teach different skills:

- S-denoising: Local coherence, lexical matching

- X-denoising: Long-range reasoning, production of long outputs

- R-denoising: Generation conditioned on prefix, summarization
Architecture: UL2 uses a Mixture-of-Experts (MoE) Transformer (Switch Transformer style) with a non-causal Prefix LM architecture.
Modern influence: The UL2 framework influenced:

- PaLM 2 / Gemini: Mixed objective training

- FIM (Fill-in-the-Middle): Used in Code LLMs (InCoder, SantaCoder, Code Llama)

- Mixture of denoisers in T5-style continual pre-training
1.6 Fill-in-the-Middle (FIM)
FIM (Bavarian et al., 2022) trains the model to fill in a missing middle section of code, given a prefix and suffix.
Objective:

Given a document split into three parts: prefix P, middle M, suffix S:
Training input: [P] [FIM_MID] [S]
Target: [M]


Corruption variants:

- PSM (Prefix-Suffix-Middle): Most common

- SMP (Suffix-Middle-Prefix): Rearranged to prevent positional bias

- Token-level FIM: Apply FIM at the token level (more noise)
Training ratio: Typically 50% of training examples use FIM, 50% use standard AR. FIM examples use a special sentinel token to indicate where the gap is.
Impact: FIM is standard in virtually all code LLMs (Codex, CodeGen, StarCoder, Code Llama, DeepSeek Coder). It significantly improves code infilling performance while maintaining or slightly improving standard generation.
1.7 Comparison of Pre-training Objectives



Objective
Masking
Attention
Loss Tokens
Strengths
Weaknesses




Autoregressive
None
Causal
All tokens
Generative, simple, scalable
Unidirectional context


MLM (BERT)
15%
Bidirectional
15% of tokens
Strong bidir representations
Not generative, inefficient


Prefix LM
None on prefix
Prefix: full; Suffix: causal
Suffix tokens
Balanced encoding/generation
More complex masking


Span Corruption
~15% spans
Bidirectional (enc)
Corrupted spans
Efficient, generative
Encoder-decoder complexity


UL2 mix
Variable
Mode-dependent
Variable
All-rounder
Complex training pipeline


FIM
50% examples
Causal
Middle section
Code infilling
Domain-specific benefit



1.8 Consistency and Positional Embedding Notes
Different pre-training objectives often interact with positional embeddings:

- ALiBi (Press et al., 2022): Linear attention bias — works best with AR objectives. Used in BLOOM, MPT

- RoPE (Su et al., 2021): Rotary position embeddings — works with AR and prefix LM. Used in Llama, Mistral, PaLM, Gemma

- Absolute PE: Traditional sinusoidal or learned — used in BERT, GPT-2, T5
RoPE is the dominant choice in modern LLMs due to its natural extrapolation to longer sequences and compatibility with relative position computation.
2. Training Data Pipeline
2.1 Overview

The training data pipeline for large language models is a critical factor in final model quality. The pipeline typically consists of:
Internet → Crawling → Filtering → Deduplication
  → Quality Rating → Data Mixing → Tokenization
  → Sharding → Training


Each stage involves significant engineering and research challenges. We cover each in depth below.
2.2 Web Crawling
CommonCrawl is the primary source for most LLM training datasets. It provides raw web page data collected at scale (monthly snapshots of tens of petabytes).
Crawling strategies:

- Broad crawl: Capture as much of the web as possible (CommonCrawl)

- Focused crawl: Target specific domains or types of content (e.g., academic papers, code repositories)

- Incremental crawl: Continuously update, replacing stale pages

- Custom crawlers: Some organizations build their own (Google, OpenAI, Anthropic, Meta)
WARC format: Crawled data is stored in WARC (Web ARChive) files containing:

- WARC headers (URL, date, IP, content type)

- Raw HTTP response (HTML, headers, metadata)

- Metadata about the crawl
Wet vs Wat vs Warc:

- WARC: Full raw data including headers

- WAT: Metadata only (links, text metadata — lighter)

- WET: Extracted plain text only (no HTML) — most common for LLM training
2.3 HTML Extraction and Text Processing
Raw HTML must be converted to clean text:
Tools:

- trafilatura (Barbaresi, 2021): State-of-the-art HTML-to-text extraction. Used in FineWeb, DCLM, RedPajama

- jusText: Rule-based boilerplate removal

- readability-lxml: Mozilla Readability port — article extraction

- html2text: Simple HTML→Markdown conversion

- Newspaper3k: Article extraction with metadata
Pipeline:
def extract_text(html, url):
    # 1. Parse HTML
    doc = trafilatura.load_html(html)

    # 2. Extract main content
    text = trafilatura.extract(doc, 
        output_format='txt',
        include_comments=False,
        include_tables=True,
        no_fallback=False)

    # 3. Post-processing
    text = normalize_whitespace(text)
    text = remove_excess_newlines(text)

    return text


Heuristics for low-quality pages:

- Page with < 200 characters of extracted text

- Ratio of extracted text to raw HTML < 0.1 (too much markup, likely spam)

- Contains excessive punctuation or ALL CAPS

- Missing closing HTML tags

- Non-standard character sets
2.4 Language Filtering
Identify and remove non-target-language documents:

FastText language classifier (Joulin et al., 2017): Trained on Wikipedia data, covers 157 languages. This is the standard tool used by most LLM projects.
CLD2/CLD3 (Compact Language Detector): Chromium's built-in detector
Human validation: Sample documents to verify language classification accuracy

Implementation pattern:
from fasttext import load_model

lang_model = load_model('lid.176.bin')

def classify_language(text, threshold=0.5):
    predictions = lang_model.predict(text)
    lang = predictions[0][0].replace('__label__', '')
    confidence = predictions[1][0]
    return lang, confidence

# Keep only target language documents
if lang == target_lang and confidence >= threshold:
    keep_document()


Data leakage across languages: Even when filtering for one language, multilingual documents may contain code-switching. Some pipelines include a "multilingual" category.
2.5 Heuristic Quality Filtering
Simple rule-based filters that remove low-quality documents. Based on analysis from The Pile (Gao et al., 2020), C4 (Raffel et al., 2020), and subsequent work.
Common heuristics:
def heuristic_filter(text, stats):
    checks = []

    # 1. Minimum length
    checks.append(len(text) >= 200)  # at least 200 chars

    # 2. Remove placeholder/lorem ipsum pages
    placeholder_phrases = ['lorem ipsum', 'this is a sample', 'under construction']
    checks.append(not any(p in text.lower() for p in placeholder_phrases))

    # 3. Punctuation ratio (high = likely bad)
    punct = sum(c in string.punctuation for c in text)
    punct_ratio = punct / max(1, len(text))
    checks.append(punct_ratio < 0.3)

    # 4. Upper case ratio
    upper = sum(c.isupper() for c in text if c.isalpha())
    upper_ratio = upper / max(1, sum(c.isalpha() for c in text))
    checks.append(upper_ratio < 0.4)  # SHOUTING pages

    # 5. Stop word ratio
    stop_words = {'the', 'a', 'an', 'in', 'of', 'to', 'and', 'is', 'it', 'that'}
    words = text.lower().split()
    stop_ratio = sum(w in stop_words for w in words) / max(1, len(words))
    checks.append(stop_ratio > 0.01)  # not gibberish

    # 6. Bullet point ratio (too many lists = likely navigation)
    bullet_count = text.count('*') + text.count('-')
    checks.append(bullet_count / len(text) < 0.1)

    # 7. Symbol-to-word ratio
    symbols = sum(c in '#@💙💪😂😍' for c in text)
    checks.append(symbols / len(text.split()) < 0.3)

    return all(checks)


The RedPajama heuristics (Together Computer, 2023): Include 7 quality filters including:

- A histogram of character classes (digits, punctuation, uppercase, lowercase, spaces)

- A "word count" ≥ 50 after extraction

- Mean word length between 3 and 10

- At least 90% of lines end with a proper line-ending character
FineWeb heuristics (Penedo et al., 2024): A refined set including:

- Minimum 128 tokens after tokenization

- Maximum perplexity threshold (using a reference model)

- Minimum stop word ratio

- Remove pages with repeated lines (n-gram dedup at line level)
2.6 Classifier-Based Quality Filtering
Train a classifier to distinguish "high quality" from "low quality" text:
Approach 1: Binary classifier (high-quality vs. random web)
1. Collect positive examples: Wikipedia, books, arXiv papers, curated articles
2. Collect negative examples: random CommonCrawl samples (or known low-quality)
3. Train a fastText / linear classifier / BERT classifier
4. Score all documents and keep top k% or above a threshold


Approach 2: Perplexity-based scoring
Use a well-trained language model (e.g., a previously trained model or a small reference model like KenLM) to score documents:
def perplexity_score(text, model):
    # Tokenize and compute loss
    tokens = tokenizer.encode(text)
    with torch.no_grad():
        loss = model(tokens, labels=tokens).loss
    ppl = torch.exp(loss).item()
    return ppl

# Typical thresholds (depends on domain):
# Wikipedia: ~50-80
# Reddit: ~80-120
# Gibberish: > 500
3. Data Deduplication and Filtering
3.1 Exact Deduplication

Remove identical documents (byte-for-byte or hash-for-hash):
Approach: Compute a hash (SHA-256, MD5, xxHash) of each document and remove duplicates:
def exact_dedup(documents):
    seen = set()
    unique = []
    for doc in documents:
        # Hash the normalized text
        text_normalized = doc.strip().lower()
        doc_hash = hashlib.sha256(text_normalized.encode()).hexdigest()
        if doc_hash not in seen:
            seen.add(doc_hash)
            unique.append(doc)
    return unique


Normalization: Simple normalization can catch more duplicates:

- Collapse whitespace

- Lowercase (optional)

- Remove HTML tags

- Normalize Unicode (NFC normalization)
Scaling: For datasets of billions of documents, use:

- Spark/MapReduce: Partition by hash prefix, deduplicate within each partition

- RocksDB/LevelDB: On-disk key-value stores for hash → doc mapping

- Bloom filters: Probabilistic dedup — fast but can miss some duplicates
3.2 MinHash for Near-Duplicate Detection
MinHash (Broder, 1997) is the standard algorithm for finding near-duplicate documents (e.g., articles from different news sources covering the same story, or documents that differ only in boilerplate).
Algorithm:


Tokenization: Convert document to set of shingles (n-grams at the word level, typically k=5-13)


Signature computation: Use k hash functions to create a signature vector:


def minhash_signature(doc, num_hashes=256, shingle_size=5):
    # Generate shingles
    shingles = set()
    words = doc.split()
    for i in range(len(words) - shingle_size + 1):
        shingle = ' '.join(words[i:i+shingle_size])
        shingles.add(shingle)

    # Compute signature
    signature = [float('inf')] * num_hashes
    for shingle in shingles:
        for i in range(num_hashes):
            # Use a hash function (typically random linear hash)
            h = hash_shingle(shingle, i)
            signature[i] = min(signature[i], h)

    return signature



Band-based LSH (Locality Sensitive Hashing): Split the signature into b bands of r rows each. Two documents are candidate near-duplicates if any band hash matches:

def lsh_bands(signature, num_bands=16):
    """Split signature into bands and hash each band."""
    rows_per_band = len(signature) // num_bands
    band_hashes = []
    for b in range(num_bands):
        band = signature[b * rows_per_band : (b + 1) * rows_per_band]
        band_hash = hash(tuple(band))
        band_hashes.append(band_hash)
    return band_hashes


Probability of detection (Jaccard similarity s):
P(detection | s) = 1 - (1 - s^r)^b


Where:

- s = Jaccard similarity of the two documents

- r = rows per band

- b = number of bands
For b=16, r=4: P ≈ 1 - (1 - s^4)^16

- s=0.5: P ≈ 0.53

- s=0.7: P ≈ 0.96

- s=0.9: P ≈ 1.00
Threshold estimation:
s_threshold ≈ (1 / b)^(1/r)


For b=16, r=4: s_threshold ≈ (1/16)^(1/4) = 0.5
Documents with Jaccard similarity > ~0.5 are likely detected.
Practical concerns:

- Shingle size: k=5 words is standard for English. Too small: false positives. Too large: missed near-duplicates.

- Number of hashes: 256 is typical. More hashes → higher accuracy but more memory/time.

- Scaling: Tools like DEDUP (Penedo et al., 2024) using Spark can process billions of documents.

- Memory: For 10B documents with 256 hashes: 10B × 256 × 8 bytes = 20.5 TB — must use distributed LSH.
3.3 SimHash for Near-Duplicate Detection
SimHash (Charikar, 2002) is an alternative to MinHash that works by computing a fingerprint from a weighted sum of hash values.
Algorithm:
def simhash_fingerprint(doc, num_bits=64):
    """Compute SimHash fingerprint for a document."""
    v = [0] * num_bits
    words = doc.split()

    for word in set(words):  # or use tf-idf weighting
        # Word hash
        h = hash_words(word)  # returns 64-bit integer

        # tf-weight (number of occurrences)
        weight = words.count(word)

        # Accumulate bits
        for i in range(num_bits):
            if (h >> i) & 1:
                v[i] += weight
            else:
                v[i] -= weight

    # Compress to fingerprint
    fingerprint = 0
    for i in range(num_bits):
        if v[i] > 0:
            fingerprint |= (1 << i)

    return fingerprint


Similarity detection: Two documents are near-duplicates if their SimHash fingerprints have a Hamming distance ≤ threshold (e.g., 3 for 64-bit fingerprints).
Pros vs MinHash:

- SimHash: Faster (single pass), more memory efficient, good for short documents

- MinHash: More flexible (configurable threshold), better for varying document lengths, standard in large-scale datasets
Both are used in major LLM datasets. MinHash is the more common choice (C4, The Pile, RedPajama, FineWeb, DCLM).
3.4 URL-Level Deduplication
Remove duplicate URLs that point to the same content:
def url_normalize(url):
    # Remove fragments
    url = url.split('#')[0]
    # Lowercase scheme and host
    parsed = urlparse(url)
    normalized = f"{parsed.scheme.lower()}://{parsed.hostname.lower()}{parsed.path}"
    # Remove trailing slash
    normalized = normalized.rstrip('/')
    # Remove www prefix
    normalized = normalized.replace('://www.', '://')
    return normalized

def url_dedup(documents):
    seen_urls = set()
    for doc in documents:
        url_norm = url_normalize(doc.url)
        if url_norm not in seen_urls:
            seen_urls.add(url_norm)
            yield doc


3.5 Line-Level Dedup and Repetition Removal
Documents with repeated lines, boilerplate, or templated content degrade model quality and can cause training divergence.
Approaches:
def remove_repeated_lines(text, threshold=3):
    """Remove lines that appear more than threshold times."""
    lines = text.split('\n')
    line_counts = Counter(lines)
    filtered = [l for l in lines if line_counts[l] <= threshold]
    return '\n'.join(filtered)

def remove_repeated_ngrams(text, n=50, threshold=10):
    """Remove documents where any n-gram repeats excessively."""
    tokens = text.split()
    ngrams = [tuple(tokens[i:i
4. Data Mixing Strategies
4.1 The Data Mixing Problem

Given multiple data sources (Wikipedia, books, code, web, social media, scientific papers), how should they be mixed for optimal downstream performance?
Key insight: The optimal data distribution is not proportional to data source size, availability, or perceived "quality." It must be empirically determined through ablations.
4.2 Mixing Strategies
1. Uniform sampling: Sample equal number of tokens from each domain. Simple but wasteful (smaller domains get oversampled, larger domains undersampled).
# Uniform mixing
domains = ['wikipedia', 'books', 'web', 'code']
sample_ratio = 1.0 / len(domains)  # 0.25 each


2. Proportional sampling: Sample in proportion to dataset size. Most common baseline.
# Proportional to size
total_size = sum(len(d) for d in datasets)
proportions = [len(d) / total_size for d in datasets]


3. Quality-weighted mixing: Weight domains by quality score.
# Quality weighting (simplified)
QUALITY_WEIGHTS = {
    'wikipedia': 3.0,
    'books': 2.5,
    'arxiv': 2.0,
    'code': 1.5,
    'web': 0.5,
}
effective_weight = {d: size * QUALITY_WEIGHTS.get(d, 1.0) for d in domains}
total_eff = sum(effective_weight.values())
proportions = {d: w / total_eff for d, w in effective_weight.items()}


4. Perplexity-based mixing (DoReMi) (Xie et al., 2023):
DoReMi (Domain Reweighting with Minimax optimization) automatically determines domain weights by minimizing the worst-case loss across domains.
# DoReMi: Minimax weight optimization
# 1. Train small reference model (300M params) on uniform data
# 2. For each domain, compute loss gap vs reference model
# 3. Update domain weights to minimize worst-case gap
# 4. Use optimal weights to train the large model

def doremi_update(domain_losses, reference_losses, weights, lr=0.01):
    """One step of DoReMi weight update."""
    # Compute excess loss per domain
    excess = domain_losses - reference_losses

    # Update weights using gradient descent on worst-case excess
    # Soft-minimax: update weights to emphasize high-excess domains
    weights = weights * (1 + lr * torch.exp(excess / temperature))
    weights = weights / weights.sum()  # normalize
    return weights


5. Temperature-based smoothing: Smooth proportions to prevent over-dominance of large domains:
def smooth_proportions(size_dict, temperature=1.0):
    """Apply temperature to smooth domain proportions."""
    # Exponential scaling
    scaled = {k: v ** temperature for k, v in size_dict.items()}
    total = sum(scaled.values())
    return {k: v / total for k, v in scaled.items()}


Temperature < 1 → more uniform (promotes diversity)

Temperature > 1 → more extreme (promotes biggest domains)
6. Dynamic mixing (annealing): Change data mix over training course.
def dynamic_mix_annealing(step, total_steps, domains):
    """Annealed data mixing.
    Early: more high-quality data for learning
    Late: more diverse web data for generalization
    """
    early_mix = {'wikipedia': 0.3, 'books': 0.3, 'code': 0.2, 'web': 0.2}
    late_mix = {'wikipedia': 0.1, 'books': 0.1, 'code': 0.1, 'web': 0.7}

    fraction = step / total_steps  # 0 to 1
    mix = {}
    for domain in domains:
        mix[domain] = (1 - fraction) * early_mix[domain] + fraction * late_mix[domain]
    return mix


4.3 Effect of Data Mix on Model Capabilities
Empirical findings from major LLM projects:



Domain
Improves
Can Harm




Wikipedia
Factual accuracy, QA
Creative writing (overly formal)


Books
Narrative, long-form coherence
Token efficiency (too many tokens per fact)


Code
Reasoning, structured output, math
Fluency in prose


Scientific papers
Domain knowledge, formal reasoning
General conversation


Web (C4, FineWeb)
General knowledge, diversity
Factual accuracy, coherence


Social media
Dialogue, conversational text
Toxicity, redundancy



Key example: Adding 1% code data to a language model significantly improves reasoning benchmarks (MATH, GSM8K) without degrading language performance. This was demonstrated by DeepSeek Code and Code Llama.
Practical recommendation for data mixing:
Typical LLM mix (undisclosed in most papers but approximately):
- Web (C4/FineWeb): 60-80%
- Books: 10-15%
- Wikipedia: 3-5%
- Code (GitHub): 3-10%
- Academic papers (arXiv/Pubmed): 3-5%
- Other (Reddit, forums, news): 5-10%


5. Scaling Laws
5.1 The Kaplan Scaling Law

Kaplan et al. (2020, also called "Scaling Laws for Neural Language Models") established the foundational scaling relationships for Transformer language models.
Empirical power laws:
The test loss L(N, D) as a function of model parameters N and dataset tokens D follows a power law:
L(N) ≈ (N_c / N)^{α_N}    for fixed D (compute-bounded)
L(D) ≈ (D_c / D)^{α_D}    for fixed N (data-bounded)


Where:

- α_N ≈ 0.076 (parameter scaling exponent)

- α_D ≈ 0.095 (data scaling exponent)

- N_c, D_c are constants (compute-bounded scaling)
Key finding 1: Large models are more token-efficient.

Given a fixed compute budget, larger models with fewer training steps (fewer tokens) achieve lower loss than smaller models trained on more tokens.
Key finding 2: Compute-optimal frontier.

For a given compute budget C (FLOPs), the optimal allocation is:
N_opt ∝ C^{0.73}
D_opt ∝ C^{0.27}


Where N_opt is the optimal model size and D_opt is the optimal number of training tokens.
Key finding 3: Transfer follows scaling.

Fine-tuning performance on downstream tasks also scales with pre-training compute, though with a larger exponent (bigger models benefit more from fine-tuning).
Key finding 4: Smooth predictable scaling.

Loss decreases predictably as power law — no "phase changes" where increasing scale suddenly changes performance trajectory for in-distribution evaluation.
The famous scaling equation (compute budget C):
L(N, D) = [(N_c / N)^{α_N / α_D} + (D_c / D)]^{α_D}


5.2 The Chinchilla Scaling Law
Hoffmann et al. (2022, "Training Compute-Optimal Large Language Models") re-examined the scaling law and found that the Kaplan law overestimated the value of model parameters — compute-optimal models are actually smaller, trained on more data.
Chinchilla methodology:
For each model size {70M, 100M, 300M, 500M, 1B, 3B, 6B}, they trained the model on varying amounts of data and measured the final loss. They fit a parametric model:
L(N, D) = E + A / N^{α} + B / D^{β}


Where:

- E = irreducible loss (entropy of text)

- A / N^{α} = loss from parameter-limited capacity

- B / D^{β} = loss from data-limited capacity
Three approaches to find compute-optimal boundary:
Approach 1: IsoFLOP profiles (most commonly cited).

Train models at multiple sizes and data volumes, group results by FLOP budget, find the optimal point for each budget.
For a given FLOP budget C:
    N_opt(C) ∝ C^{0.5}
    D_opt(C) ∝ C^{0.5}


This means: proportional scaling — doubling compute budget should double both model parameters and training tokens.
Approach 2: Parametric fitting. Fit the parametric loss function L(N, D) = E + A/N^α + B/D^β.
Chinchilla fitted parameters: α ≈ 0.34, β ≈ 0.28, E ≈ 1.69, A ≈ 406.4, B ≈ 410.7.
Approach 3: Test fit on a fixed FLOP frontier. Train models at different (N, D) combinations with the same FLOP budget, find minimum loss.
Chinchilla recommendation:
N_opt = C / (6 × 1.92) ≈ C / 11.52  (for Chinchilla, N_opt=70B, D_opt=1.4T)


Where 6 is the FLOPs per token per parameter (forward + backward pass), and 1.92 is the optimal tokens-per-parameter ratio.
Compare Kaplan vs Chinchilla:



Aspect
Kaplan 2020
Chinchilla 2022




Optimal tokens/param
~30:1 (300B params, 300B tokens)
~20:1 (70B params, 1.4T tokens)


Param scaling exponent
α_N ≈ 0.076
α ≈ 0.34 (in loss function)


Model compute scaling
N_opt ∝ C^{0.73}
N_opt ∝ C^{0.5}


Data compute scaling
D_opt ∝ C^{0.27}
D_opt ∝ C^{0.5}


Implication
Bigger models, fewer tokens
Bigger models AND more tokens



Practical impact of Chinchilla:
The Chinchilla paper fundamentally changed LLM training. Post-2022 models are trained on significantly more tokens relative to their size:

- Llama 1 (6.7B → 1T tokens, ratio ~150:1)

- Llama 2 (7B → 2T tokens, ratio ~286:1)

- Llama 3 (8B → 15T tokens, ratio ~1875:1)

- Mistral 7B → ~9T tokens, ratio ~1286:1

- DeepSeek V3 (671B MoE) → 14.8T tokens
Modern models far exceed the Chinchilla-optimal ratio, suggesting either:

1. Scaling exponents are steeper than Chinchilla assumed

2. Data quality (not just quantity) improves with more tokens

3. Emergent capabilities benefit from more data beyond the loss-scaling optimum
5.3 IsoFLOP Profiles
The IsoFLOP method is the most direct way to determine compute-optimal training:
def isoflop_profiles(model_sizes, token_counts, flop_budget):
    """Find optimal (N, D) for a given FLOP budget."""
    results = []

    for N in model_sizes:
        for D in token_counts:
            # FLOPs for training with transformers:
            # ~6 * N * D FLOPs (forward + backward)
            F = 6 * N * D

            if abs(F - flop_budget) / flop_budget > 0.1:
                continue  # Skip non-matching combos

            # Train and measure loss
            model = Transformer(..., d_model=..., n_layers=...)
            loss = train(model, n_tokens=D)

            results.append({'N': N, 'D': D, 'F': F, 'loss': loss})

    # Find minimum loss at this FLOP budget
    best = min(results, key=lambda x: x['loss'])
    return best['N'], best['D']


Practical guidance for IsoFLOP experiments:

Train models at 4-6 different sizes (e.g., 70M, 150M, 300M, 500M, 1B, 3B)
For each size, train at 3-5 different token counts (e.g., 5B, 10B, 20B, 50B, 100B tokens)
Plot loss vs FLOP budget curves
Find the Pareto-optimal frontier
Extrapolate to larger compute budgets using power-law fits

5.4 Data Scaling vs Model Scaling
The core question: Given additional compute budget, should you increase model size or training data?
Kaplan answer (2020): Increase model size. At compute-optimality, 73% of additional compute goes to model size, 27% to data.
Chinchilla answer (2022): Increase both equally. 50%/50% split.
Modern understanding (2024+): The answer depends on:


Data quality: With high-quality data, data scaling provides more benefit per token. Low-quality data may require more model capacity to "filter" noise.


Model architecture: MoE models (Mixtral, DeepSeek-V3) decouple total params from active params — they benefit more from data scaling as capacity is cheap.


Training regime: 

   - Pre-training scale (10B-30T tokens): Chinchilla regime holds reasonably

   - Continued pre-training / domain adaptation: Data scaling dominates (small model on domain data beats large model on less domain data)

   - Fine-tuning: More data almost always helps regardless of model size


Diminishing returns: Both model and data scaling show diminishing returns. The marginal benefit of 1% more data = 1% more params varies.


// Modern intuition for data vs model scaling returns:
// For 8B-70B models:
//   Doubling data: loss reduction ≈ 0.05-0.10 nats
//   Doubling model size: loss reduction ≈ 0.10-0.15 nats
// Ratio: model scaling ~1.5-2× more effective per FLOP
// But: data can be parallelized across GPUs; model scaling requires more memory


5.5 Scaling Law Breakdown and Limitations
Known breakdowns of scaling laws:


Small model → large model extrapolation: Power laws fitted on models up to 1B params may not hold at 100B+ due to:

   - Emerging capabilities (few-shot reasoning, in-context learning)

   - Variance in training dynamics (larger models train differently)

   - Architectural constraints (attention head count, vocabulary size)


Compute-extrapolation: The functional form L = E + A/N^α + B/D^β assumes smooth monotonic improvement. In practice, there can be:

   - Threshold effects: Certain capabilities (arithmetic, multi-step reasoning) emerge only past a critical scale

   - Plateauing: Some benchmarks saturate (models achieve >95% on some tasks)

   - Capability scaling is non-uniform: Some tasks improve smoothly with scale, others show sharp transitions


Data quality matters: Scaling laws are derived from IID data. With data selection:

   - High-quality data can achieve same loss with 2-10× fewer tokens

   - The "effective data size" depends on quality, not just quantity


Training compute ≠ inference compute: Optimal pre-training models may be suboptimal for deployment. Smaller models can be distilled or pruned for inference efficiency.


5.6 Beyond Scaling Laws: Recent Understanding
The "Three Scaling Regimes" (Michaud et al., 2023):

Under-trained regime (D < N^0.5): Model capacity underutilized. More data helps most.
Compute-optimal regime (D ≈ N^0.5): Balanced allocation.
Over-trained regime (D > N^0.5): Limited by model capacity. Larger model would help.

Modern models (Llama 3 8B on 15T tokens) are in the over-trained regime — they benefit more from architectural improvements or increased model size than from more data of the same quality.
The "Data Scaling Wall":
There is concern that the web's natural language data is finite and will be exhausted by 2026-2030 (Villalobos et al., 2022). This has driven:

- Synthetic data generation (see Section 15)

- Multi-turn augmentation

- Code and structured data sources

- Multilingual data collection

- Proprietary data licensing
Does scaling always work? (Schaeffer et al., 2024):
"E=mc²" (Emergent magnitudes = claims, counter-claims) — the notion that capabilities "emerge" abruptly at certain scales has been challenged as an artifact of discontinuous evaluation metrics. Continuous metrics (loss, BLEU, accuracy on fine-grained rubrics) show gradual improvement with scale.
5.7 Practical Scaling Guidelines (2024+)
Model Size    → Recommended Training Tokens (current best practice)
──────────────────────────────────────────────────────
1B params     → 500B - 2T tokens
3B params     → 1T - 5T tokens
7B params     → 2T - 15T tokens
13B params    → 3T - 20T tokens
34B params    → 5T - 30T tokens
70B params    → 10T - 40T tokens
130B params   → 15T - 60T tokens
300B params   → 30T - 100T tokens (MoE often used)
1T+ params    → 50T+ tokens (mostly MoE)


These ratios exceed Chinchilla by 5-100×, reflecting the focus on data quality and the value of extended training for emergent capabilities.
6. Curriculum Learning
6.1 Core Idea

Curriculum learning (Bengio et al., 2009) organizes training data from "easy" to "hard," mimicking how humans learn. The hypothesis is that this ordering accelerates convergence and improves final performance.
Mathematical formulation:
Given a set of training examples {(x_i, y_i)} ordered by difficulty d_i, the curriculum presents them in increasing difficulty order:
L_curriculum(θ) = Σ_{t=1}^{T} w_t · L(θ; (x_{π(t)}, y_{π(t)}))


Where π is a permutation sorted by difficulty d_i, and w_t is a time-dependent weight (typically 1 for early examples in easy phase, switching to include hard examples later).
6.2 Difficulty Metrics
Data-driven difficulty:

- Loss-based: Loss of a pre-trained model on each example

- Perplexity-based: PPL of a small reference model

- Gradient magnitude: Norm of the gradient on each example (high gradient = harder)

- Language model probability: -log p(x_i)
Structural difficulty:

- Sequence length: Shorter sequences first

- Vocabulary complexity: Rare words count

- Syntactic complexity: Parse tree depth

- Readability scores: Flesch-Kincaid, Dale-Chall
Task-specific difficulty:

- For math: Number of reasoning steps, equation length

- For code: Lines of code, cyclomatic complexity

- For translation: BLEU score against reference
6.3 Curriculum Schedules
1. Pacing function: Controls how quickly hard examples are introduced.
p(t) = min(1, (t/T)^k)  // k controls sharpness



k=1 (linear): Gradually increase
k<1 (concave): Quickly introduce hard examples
k>1 (convex): Delay hard examples

2. Competence-based curriculum: Switch difficulty when model achieves a target accuracy:
if val_acc_on_easy > 0.8:
    mix_in_medium = 0.5
if val_acc_on_medium > 0.8:
    mix_in_hard = 0.5


3. Self-paced learning (Kumar et al., 2010): Model selects which examples to train on based on its current competence:
min_θ Σ_i v_i · L(θ; x_i, y_i) - λ · ||v||_1
s.t. v_i ∈ [0, 1]


Where v_i are learned example weights. Easy examples (low loss) get v_i=1; hard examples (high loss) get v_i=0 (skipped).
6.4 Curriculum Learning in LLM Training
Current consensus: Curriculum learning does not significantly improve large-scale LLM pre-training. The dominant practice is random shuffling of training data.
However, curriculum is effective for:

Domain-adaptive pre-training: Start with general web data, transition to domain-specific data (code, biology, finance)
Multi-stage training: 

   - Stage 1: Pre-training on filtered web

   - Stage 2: Continued pre-training on high-quality curated data

   - Stage 3: Instruction tuning
Length extension: Train on short sequences first, gradually increase context length (used by GPT-3, Llama 2: 2k → 4k → 8k → 32k)
Math reasoning training: Start with simple arithmetic, progress to multi-step problems

Example: Multi-stage curriculum for math LLM:
Stage 1: General pre-training (500B tokens, random order)
Stage 2: Math+Github code (100B tokens, random order)
Stage 3: Reasoning chain data (10B tokens, easy→hard)
Stage 4: Instruction tuning (1B tokens, random order)


6.5 Practical Implementation
def curriculum_dataloader(dataset, difficulty_fn, batch_size, 
                          total_steps, schedule='linear'):
    """Curriculum learning dataloader."""
    # Compute difficulties for all examples
    difficulties = [difficulty_fn(x) for x in dataset]

    # Sort by difficulty
    sorted_idx = np.argsort(difficulties)
    sorted_data = [dataset[i] for i in sorted_idx]

    # Define pacing function
    def pacing(t):
        if schedule == 'linear':
            return min(1.0, t / (0.3 * total_steps))
        elif schedule == 'concave':
            return min(1.0, (t / total_steps) ** 0.5)
        elif schedule == 'convex':
            return min(1.0, (t / total_steps) ** 2)

    step = 0
    while step < total_steps:
        fraction = pacing(step)
        n_easy = int(fraction * len(sorted_data))

        # Sample from the easiest n_easy examples
        batch_indices = np.random.choice(n_easy, batch_size)
        yield [sorted_data[i] for i in batch_indices]
        step += 1


7. Multi-Task Learning
7.1 Multi-Task Learning Formulation

Multi-task learning (MTL) trains a single model on multiple tasks simultaneously, sharing representations across tasks. The goal is that learning one task improves performance on others (inductive transfer).
Loss function for MTL:
L_total(θ_shared, {θ_t}) = Σ_{t=1}^{T} λ_t · L_t(θ_shared, θ_t; D_t)


Where:

- θ_shared = shared parameters (e.g., Transformer backbone)

- θ_t = task-specific parameters (e.g., classification heads)

- λ_t = task weight

- D_t = dataset for task t
7.2 Task Weighting Strategies
Uniform weighting: λ_t = 1/T — simple but suboptimal when tasks have different scales or learning speeds.
Uncertainty weighting (Kendall et al., 2018): Learn task weights as the log variance of each task:
L_total = Σ_t (1 / 2σ_t²) · L_t + log σ_t


Tasks with high uncertainty (noise) are downweighted automatically.
Dynamic prioritization (Guo et al., 2018): Weight tasks by their performance gap:
λ_t ∝ 1 / (current_performance_t - target_performance_t + ε)


Tasks far from target get higher weight.
Gradient balancing (Chen et al., 2018): Adjust λ_t so all tasks have similar gradient magnitudes.
min_λ || Σ_t λ_t · g_t - g_avg ||_2
where g_t = ∇_θ L_t(θ)


7.3 Multi-Task Learning in LLM Context
FLAN (Wei et al., 2022) showed that instruction-tuning on many tasks simultaneously (massive multi-task learning) dramatically improves zero-shot generalization.
Key insight: Multi-task training on diverse NLP tasks (question answering, translation, summarization, reasoning) creates models that follow instructions more reliably than those trained on a single task.
Task diversity considerations:
Best MTL setups include:
- Diverse task types: classification, generation, extraction, reasoning
- Diverse domains: science, creative, business, technical
- Diverse output formats: multiple choice, free text, structured
- Diverse difficulty: simple to complex


8. Transfer Learning
8.1 The Transfer Learning Paradigm

Transfer learning leverages knowledge from a source domain/task to improve learning on a target domain/task.
In deep learning / NLP, this is overwhelmingly:

Pre-training on large general-domain data (source)
Fine-tuning on smaller task-specific data (target)

Types of transfer:

- Inductive: Source and target tasks differ but are related (e.g., pre-train on language modeling → fine-tune on classification)

- Transductive: Same task, different domains (e.g., pre-train on English → fine-tune on French)

- Unsupervised pre-training: Self-supervised pre-training → supervised fine-tuning
8.2 Pre-Training then Fine-Tuning
This is the dominant paradigm since BERT (2019). The typical sequence:
1. Pre-train on massive unlabeled data (web, books, code)
   - AR or MLM objective
   - Billions of tokens
   - High computational cost ($1M-$100M+)

2. Fine-tune on labeled downstream task data
   - Task-specific objective (classification, QA, generation)
   - Thousands to millions of labeled examples
   - Low computational cost


Key insight: Pre-training provides broad linguistic and world knowledge; fine-tuning adapts to specific task formats and domain distributions.
8.3 Linear Probing vs Fine-Tuning
Linear probing: Freeze pre-trained weights, train only a new classification head:
z = f_θ(x)       // frozen encoder
ŷ = W · z + b    // trainable linear classifier
L = cross_entropy(ŷ, y)


Fine-tuning: Update all pre-trained weights:
ŷ = g_φ(f_θ(x))   // both encoder f and head g are updated
L = cross_entropy(ŷ, y)


Comparison:

| Property | Linear Probing | Full Fine-Tuning |

|---|---|---|

| Parameters trained | Very few (only head) | All parameters |

| Compute cost | Low | Moderate |

| Overfitting risk | Low | Higher (especially small target data) |

| Task-specific adaptation | Limited (only last features) | Full adaptation |

| Feature preservation | Preserves pre-trained features | May overwrite features |

| Performance (data-rich) | Lower | Higher |

| Performance (data-poor) | Good | Can overfit |
Probing vs fine-tuning gap: The difference between linear probe and fine-tuned performance indicates how much the pre-trained features need to be transformed for the target task.
8.4 Progressive Transfer and Continual Pre-Training
Progressive transfer: Gradually reduce the gap between pre-training distribution and target distribution:
Stage 1: General pre-training (web)
Stage 2: Domain-adaptive pre-training (biomedical papers)
Stage 3: Task-adaptive pre-training (specific benchmark)
Stage 4: Fine-tuning (labeled task data)


Pragmatic approach (used by most LLM developers):
1. Pre-train base model on general web data (15T tokens)
2. Continue pre-training on curated high-quality data (500B tokens)
3. Multi-task instruction tuning (10M examples)
4. Alignment (RLHF/DPO) on preference data (10K-100K examples)


9. Fine-Tuning
9.1 Full Fine-Tuning

Full fine-tuning updates all model parameters on the target task.
Formulation:
θ* = argmin_θ L(θ; D_target)
    = argmin_θ Σ_{(x,y) ∈ D_target} ℓ(f_θ(x), y)


Where θ is initialized from pre-trained weights θ_pretrain and ℓ is the task loss (typically cross-entropy for language tasks).
Empirical findings:

- Fine-tuning with a small learning rate (1e-6 to 5e-5) is critical

- Full fine-tuning is expensive for large models (70B+ requires 8× A100s per node)

- Performance varies significantly with hyperparameters (LR, batch size, epochs)

- Catastrophic forgetting: Fine-tuning on a narrow task degrades general capabilities
Mitigating catastrophic forgetting:

- Elastic Weight Consolidation (EWC) (Kirkpatrick et al., 2017): Penalize changes to important parameters:
L = L_task + λ Σ_i F_i · (θ_i - θ_pretrain,i)²


Where F_i is the Fisher information matrix diagonal (importance of parameter i).

Replay / Experience replay: Mix fine-tuning data with pre-training data:

L = L_task + α · L_pretrain(D_replay)


9.2 Hyperparameter Considerations for Fine-Tuning
# Common fine-tuning hyperparameters (Llama/Mistral scale)

FINE_TUNING_CONFIG = {
    # Optimizer
    'optimizer': 'AdamW',
    'learning_rate': 2e-5,         # typical range: 1e-6 to 5e-5
    'weight_decay': 0.1,           # default
    'beta1': 0.9,
    'beta2': 0.999,
    'epsilon': 1e-8,

    # LR schedule
    'lr_scheduler': 'cosine',
    'warmup_ratio': 0.03,          # 3% of total steps
    'min_lr_ratio': 0.1,           # decay to 10% of peak

    # Training
    'batch_size': 128,             # per GPU batch, then gradient accumulation
    'num_epochs': 3,               # typical: 2-5 for instruction tuning
    'gradient_clip': 1.0,          # max gradient norm
    'gradient_accumulation_steps': 1,  # adjust based on GPU count

    # Precision
    'dtype': 'bfloat16',           # or 'float16' with gradient scaling

    # Regularization (optional for fine-tuning)
    'dropout': 0.0,                # typically 0 for fine-tuning
    'label_smoothing': 0.0,        # optional for classification
}


10. Parameter-Efficient Fine-Tuning (PEFT)
10.1 Motivation

Full fine-tuning of large models (70B-400B parameters) requires:

- Storing full-precision gradients (huge memory)

- Downloading/distributing full checkpoints

- Expensive hardware (multiple nodes of A100/H100)
PEFT methods update only a small fraction of parameters (0.01%-2%) while keeping most parameters frozen. At this low level of parameter change, PEFT often matches full fine-tuning quality.
10.2 LoRA (Low-Rank Adaptation)
Hu et al. (2021) proposed LoRA — the most widely used PEFT method.
Core idea: The weight update ΔW = W - W_pretrain during fine-tuning has low intrinsic rank. Instead of learning a full d × k matrix, we learn a low-rank decomposition:
W' = W_pretrain + BA


Where:

- W_pretrain ∈ ℝ^{d×k} is frozen

- B ∈ ℝ^{d×r}, A ∈ ℝ^{r×k} are trainable

- r << min(d, k) is the LoRA rank (typically 4-64)
Initialization:

- A is initialized with random Gaussian (e.g., Kaiming normal)

- B is initialized to zero — so W' = W_pretrain at the start of training
Forward pass:
h = W_pretrain · x + BA · x = W_pretrain · x + B(Ax)


Scaling:
W' = W_pretrain + (α / r) · BA


Where α is a scaling hyperparameter (typically 8-32). This controls the magnitude of the update. In practice, α/r acts as a learning rate for the update.
Why low rank works:

- Pre-trained models have a low-dimensional "intrinsic dimension" (Li et al., 2018)

- Fine-tuning adjustments lie in a low-rank subspace

- Aghajanyan et al. (2021) showed that pre-trained models have intrinsic rank of ~1 for full dataset fine-tuning
Where to apply LoRA:
Typically applied to attention weight matrices W_q, W_k, W_v, W_o. Also applicable to feedforward layers.
class LoRALayer(nn.Module):
    "Low-Rank Adaptation layer."
    def __init__(self, base_layer, r=8, alpha=16, dropout=0.0):
        super().__init__()
        self.base = base_layer  # frozen pre-trained weight
        d, k = base_layer.weight.shape

        # Low-rank decomposition
        self.lora_A = nn.Parameter(torch.randn(r, k) * 0.01)
        self.lora_B = nn.Parameter(torch.zeros(d, r))
        self.scaling = alpha / r
        self.dropout = nn.Dropout(dropout)

    def forward(self, x):
        base_out = self.base(x)
        lora_out = (self.lora_B @ (self.lora_A @ x.T)).T * self.scaling
        # Equivalent: lora_out = (x @ self.lora_A.T) @ self.lora_B.T * self.scaling
        return base_out + lora_out


10.3 LoRA Rank Selection
The rank r controls the expressiveness vs efficiency tradeoff:
r = 1: Very constrained, limited adaptation. Works for simple style changes.
r = 4-8: Sweet spot for most tasks. Matches full fine-tuning on many benchmarks.
r = 16-32: More capacity, needed for complex tasks or large domain shifts.
r = 64-256: Approaches full fine-tuning expressiveness but reduces parameter savings.


Heuristic for rank selection:
def suggest_lora_rank(task_type, domain_shift, n_examples):
    """Suggest LoRA rank based on task characteristics."""
    if n_examples < 1000:
        base_rank = 4
    elif n_examples < 10000:
        base_rank = 8
    else:
        base_rank = 16

    if domain_shift == 'large':  # e.g., general → biomedical
        base_rank *= 2
    elif domain_shift == 'small':  # e.g., same domain, new task
        pass

    if task_type == 'generation':  # harder than classification
        base_rank = int(base_rank * 1.5)

    return min(base_rank, 64)


Empirical finding: Rank 8 often matches full fine-tuning on most NLU tasks. Higher ranks (32-64) help for domain adaptation and generation tasks.
10.4 QLoRA: Quantized Low-Rank Adaptation
Dettmers et al. (2023) combined 4-bit quantization with LoRA to fine-tune 65B models on a single GPU.
Key innovations:

NF4 (NormalFloat4) quantization: A new data type optimized for normally distributed weights.

NF4 quantization math:
The NF4 datatype is a quantization scheme specifically designed for neural network weights, which are approximately normally distributed (mean 0, standard deviation σ).
Unlike uniform quantization, NF4 allocates more quantization levels near the center of the distribution (where most weights lie) and fewer at the tails.
Quantization process:
def nf4_quantize(weight_tensor):
    """Quantize tensor to NF4."""
    # 1. Compute absolute max of the tensor
    abs_max = weight_tensor.abs().max()

    # 2. Normalize to [-1, 1]
    normalized = weight_tensor / abs_max

    # 3. Quantize to 4-bit (16 levels)
    # NF4 quantization levels (for normally distributed values):
    # q_i = quantiles of N(0,1) at positions (i+0.5)/16 for i = 0..15

    # Map normalized values to nearest quantile level
    quant_levels = [-1.0, -0.6962, -0.5251, -0.3949, -0.2844, -0.1848, 
                    -0.0911, 0.0, 0.0792, 0.1609, 0.2461, 0.3379,
                    0.4407, 0.5626, 0.7230, 1.0]

    # Each value maps to 4-bit index (0-15)
    indices = torch.bucketize(normalized, quant_levels) - 1
    indices = indices.clamp(0, 15)

    return indices.to(torch.uint8), abs_max  # store quantization stats


Dequantization:
def nf4_dequantize(indices, abs_max):
    """Dequantize NF4 indices back to bf16."""
    quant_levels = [-1.0, -0.6962, -0.5251, -0.3949, -0.2844, -0.1848,
                    -0.0911, 0.0, 0.0792, 0.1609, 0.2461, 0.3379,
                    0.4407, 0.5626, 0.7230, 1.0]
    levels_tensor = torch.tensor(quant_levels, device=indices.device)
    values = levels_tensor[indices.long()] * abs_max
    return values


NF4 vs other quantization:
NF4 achieves better quality than FP4 (naive 4-bit floating point) and close to FP8/bfloat16 performance for a wide range of model sizes.
QLoRA training pipeline:
QLoRA training:
1. Load model in 4-bit NF4 (doubles memory efficiency vs 8-bit)
2. Add LoRA adapters
11. RLHF: Reinforcement Learning from Human Feedback
11.1 RLHF Pipeline Overview

RLHF (Christiano et al., 2017; Stiennon et al., 2020; Ouyang et al., 2022) is the standard method for aligning LLMs with human preferences. The pipeline has three stages:
Stage 1: SFT (Supervised Fine-Tuning)
    Train on high-quality demonstration data (prompt → ideal response)

Stage 2: RM (Reward Model Training)
    Collect human preference comparisons (A vs B)
    Train a reward model to predict human preferences

Stage 3: RL Fine-Tuning (PPO)
    Use the reward model as a reward signal
    Fine-tune the SFT model using PPO


11.2 Stage 1: Supervised Fine-Tuning (SFT)
Train the base model on high-quality human-written demonstrations:
L_SFT(θ) = -E_{(x, y) ~ D_sft} [log π_θ(y | x)]


Where:

- x is the prompt

- y is the ideal response (human-written)

- π_θ is the policy (the SFT model)
SFT data: Typically 10K-100K demonstration pairs, covering diverse tasks.
Key concern: Models may learn stylistic patterns rather than true capabilities from this small dataset.
11.3 Stage 2: Reward Model Training
Data collection:

- Present model-generated responses to human raters

- Human chooses which response is better (or provides Elo ranking)

- Typical dataset: 100K-1M comparison pairs
Score function formulation:
For a pair of responses (y_a, y_b) to prompt x, with human preference that y_a is better than y_b:
p(y_a > y_b | x) = σ(r(x, y_a) - r(x, y_b))


Where r(x, y) is the reward model output (a scalar), and σ is the sigmoid function.
Bradley-Terry preference model:
p(y_a > y_b) = exp(r(x, y_a)) / (exp(r(x, y_a)) + exp(r(x, y_b)))


Reward model loss:
L_RM(φ) = -E_{(x, y_w, y_l) ~ D_rm} [log σ(r_φ(x, y_w) - r_φ(x, y_l))]


Where y_w is the winning response and y_l is the losing response.
Reward model architecture:

- Start from SFT model

- Replace the final layer with a linear head that outputs a scalar

- Typically use a small model (e.g., 1B-7B) even for training a 70B policy
Training details:

- Batch size: 64-512 pairs

- Learning rate: 1e-6 to 1e-5

- Regularization: weight decay, dropout

- Accuracy goal: 60-75% on held-out comparisons (human agreement is ~75%)
11.4 Stage 3: PPO (Proximal Policy Optimization)
PPO (Schulman et al., 2017) is used to optimize the policy against the learned reward model.
RLHF objective:
max_θ E_{x ~ D, y ~ π_θ(y|x)} [r_φ(x, y)] - β · KL(π_θ(y|x) || π_ref(y|x))


Where:

- π_θ is the policy being optimized

- π_ref is the reference policy (frozen SFT model)

- β controls the KL penalty strength (typically 0.01-0.1)

- KL penalty prevents the policy from diverging too far from the reference (reduces reward hacking)
PPO in RLHF — detailed steps:
ALGORITHM: PPO for RLHF
────────────────────────
Input: SFT model π_ref, reward model r_φ
Initialize: π_θ = π_ref

for each iteration:
    // 1. Collect rollouts
    for each prompt x in batch:
        y = sample(π_θ(y | x))  // generate response
        reward = r_φ(x, y)  // score from reward model
        kl = KL(π_θ(y|x) || π_ref(y|x))  // KL per token
        advantage = reward - β * kl  // penalized reward

    // 2. Compute PPO loss
    for each (x, y) in batch:
        π_old = prob from old policy (before update)
        π_new = prob from current policy

        ratio = π_new(y|x) / π_old(y|x)
        clipped_ratio = clamp(ratio, 1-ε, 1+ε)

        L_policy = -E[min(ratio * A, clipped_ratio * A)]
        L_value = E[(V_θ(x) - reward)²]  // value function loss (optional)

        L_PPO = L_policy + c_v * L_value - c_e * H(π_θ)  // entropy bonus

    // 3. Update policy
    θ ← θ - η · ∇_θ L_PPO


PPO in RLHF — implementation details:
PPO epoch: Typically 1-4 epochs per batch of rollouts. Multiple epochs increase sample efficiency but risk overfitting to the reward model.
KL penalty variants:


Fixed KL: β is constant during training. Simple but requires tuning.


Adaptive KL (approximate KL per batch):


def adaptive_kl_beta(kl_current, kl_target=0.01, beta=0.01):
    """Adjust β to maintain target KL divergence."""
    if kl_current > 2 * kl_target:
        beta *= 1.5
    elif kl_current < 0.5 * kl_target:
        beta /= 1.5
    return beta



KL budget: Maintain a running KL budget. Penalize only when budget is exceeded.

Value function (critic):

- Often initialied from the reward model

- Learns to predict the expected return from state x

- Reduces variance of advantage estimates

- Optional: can be omitted (use reward directly as advantage)
Advantage estimation:
GAE (Generalized Advantage Estimation):
A_t = Σ_{k=0}^{T-t-1} (λγ)^k · δ_{t+k}
δ_t = r_t + γ · V(s_{t+1}) - V(s_t)


In RLHF, the simpler approach is often used:
A_t = r_φ(x, y) - V_θ(x)  // per-sequence advantage


11.5 Reward Hacking and Over-Optimization
Reward hacking: The policy exploits the reward model by generating responses that score high but are actually not good (e.g., nonsensical text that the RM incorrectly scores high).
Signs of reward hacking:

1. Reward model score increases but human evaluation plateaus

2. Generated text becomes repetitive, overly long, or uses unusual phrasing

3. The KL divergence from the reference model grows large
Mitigations:


KL penalty (as described above) — the primary defense


Reward normalization:


# Normalize rewards to have zero mean, unit variance
rewards = reward_model(batch)
rewards = (rewards - rewards.mean()) / (rewards.std() + 1e-8)



Ensemble reward models: Average scores from multiple independently trained reward models:

r_ensemble(x, y) = (1/M) Σ_{i=1}^{M} r_i(x, y)



Reward scaling: Clip rewards to a reasonable range:

reward = torch.clamp(reward, -5.0, 5.0)



Per-token KL vs per-sequence KL: Per-token KL provides finer-grained control:

per_token_kl = Σ_t KL(π_θ(y_t | x, y_{<t}) || π_ref(y_t | x, y_{<t}))


Reward over-optimization (Gao et al., 2023):
Empirically, the true reward (human satisfaction) increases with PPO iterations but then decreases, while the proxy reward (RM score)...
12. DPO and Direct Alignment Methods
12.1 DPO: Direct Preference Optimization

Rafailov et al. (2023, "Direct Preference Optimization: Your Language Model is Secretly a Reward Model") showed that the RLHF objective can be solved in closed form, eliminating the need for a separate reward model.
Key insight: The optimal policy under the KL-constrained RL objective has a closed-form solution in terms of the reward function:
π*(y|x) = (1/Z(x)) · π_ref(y|x) · exp(r(x, y) / β)


Rearranging to express the reward:
r(x, y) = β · log(π*(y|x) / π_ref(y|x)) + β · log Z(x)


DPO loss derivation:
Substituting the reward expression into the Bradley-Terry preference model:
p(y_w > y_l | x) = σ(r(x, y_w) - r(x, y_l))


Yields the DPO loss:
L_DPO(θ) = -E_{(x, y_w, y_l)} [log σ(β · log(π_θ(y_w|x) / π_ref(y_w|x)) 
                                       - β · log(π_θ(y_l|x) / π_ref(y_l|x)))]


Where:

- y_w is the preferred/won response

- y_l is the dispreferred/lost response

- β is the temperature parameter (controls how far the policy can deviate from π_ref)

- π_θ is the policy being optimized

- π_ref is the frozen reference policy
Simplified DPO loss:
L_DPO = -log σ(β · (log π_θ(y_w|x) - log π_ref(y_w|x) 
                   - log π_θ(y_l|x) + log π_ref(y_l|x)))
     = -log σ(β · (r_θ(x, y_w) - r_θ(x, y_l)))


Where implicitly r_θ(x, y) = β · log(π_θ(y|x) / π_ref(y|x)).
The key difference between DPO and PPO:



DPO
PPO




Directly optimizes preference loss
RL optimization via reward model


No explicit reward model needed
Requires trained reward model


Single-stage preference optimization
Three-stage (SFT → RM → RL)


No online sampling during training
Online sampling (rollouts)


Computationally simpler
More complex, more hyperparameters


Sensitive to off-policy preference data
More stable with online exploration


Objective: maximize log-likelihood of preferred response
Maximize reward subject to KL constraint



12.2 DPO Gradient
The gradient of the DPO loss provides insight into how DPO works:
∇_θ L_DPO = -β · E[σ(-β · (log(π_θ(y_w|x)/π_ref(y_w|x)) - log(π_θ(y_l|x)/π_ref(y_l|x))))
                    · (∇_θ log π_θ(y_w|x) - ∇_θ log π_θ(y_l|x))]


The sigmoid weight σ(-β·Δ) is high when:

- The preferred response has low likelihood (compared to reference)

- The dispreferred response has high likelihood
Thus DPO automatically focuses on:

- Increasing probability of preferred responses when they are currently under-priced

- Decreasing probability of dispreferred responses when they are currently over-priced
12.3 DPO Implementation
def dpo_loss(policy_chosen_logps, policy_rejected_logps,
             ref_chosen_logps, ref_rejected_logps, beta=0.1):
    """Compute DPO loss.

    Args:
        policy_chosen_logps: log π_θ(y_w|x)
        policy_rejected_logps: log π_θ(y_l|x)
        ref_chosen_logps: log π_ref(y_w|x)
        ref_rejected_logps: log π_ref(y_l|x)
        beta: temperature parameter
    """
    # Log ratios
    log_ratio_chosen = policy_chosen_logps - ref_chosen_logps
    log_ratio_rejected = policy_rejected_logps - ref_rejected_logps

    # Preference margin
    margin = log_ratio_chosen - log_ratio_rejected

    # DPO loss
    loss = -F.logsigmoid(beta * margin).mean()

    # Optional: accuracy metric
    with torch.no_grad():
        accuracy = (margin > 0).float().mean()

    return loss, accuracy


Training loop:
def train_dpo(policy, ref_policy, dataloader, beta=0.1, lr=1e-6):
    optimizer = torch.optim.AdamW(policy.parameters(), lr=lr)

    for batch in dataloader:
        prompts, chosen, rejected = batch

        # Forward pass through policy (current)
        policy_chosen_logps = policy.get_log_probs(prompts, chosen)
        policy_rejected_logps = policy.get_log_probs(prompts, rejected)

        # Forward pass through reference (frozen)
        with torch.no_grad():
            ref_chosen_logps = ref_policy.get_log_probs(prompts, chosen)
            ref_rejected_logps = ref_policy.get_log_probs(prompts, rejected)

        # DPO loss
        loss, _ = dpo_loss(
            policy_chosen_logps, policy_rejected_logps,
            ref_chosen_logps, ref_rejected_logps,
            beta=beta
        )

        loss.backward()
        optimizer.step()
        optimizer.zero_grad()


12.4 GRPO: Group Relative Policy Optimization
GRPO (Shao et al., 2024 / DeepSeek-R1) is a variant of PPO that eliminates the need for a value function by using group-based advantage estimation.
Core idea: For each prompt, sample G responses from the current policy. Compute the advantage of each response relative to the group average:
A_i = (r_i - mean({r_1, ..., r_G})) / std({r_1, ..., r_G})


Where r_i is the reward for response i (from a reward model or rule-based reward).
GRPO loss:
L_GRPO(θ) = -E_{(x, {y_i})} [ (1/G) Σ_i A_i · min(r_i(θ), clip(r_i(θ), 1-ε, 1+ε)) 
                                 - β · KL(π_θ || π_ref) ]


Where r_i(θ) = π_θ(y_i|x) / π_old(y_i|x) is the importance sampling ratio.
Why GRPO works without a value function:

- The group-based normalization provides a zero-mean, unit-variance advantage signal

- Like DPO, the "baseline" is computed from the group mean (not from a learned value function)

- This eliminates the critic network, reducing memory and complexity
GRPO vs PPO:

| Aspect | PPO | GRPO |

|---|---|---|

| Value function | Required | Not needed |

| Advantage estimation | GAE or residual from value | Group-normalized reward |

| Memory | Policy + Value + Reward + Reference | Policy + Reward + Reference |

| Complexity | Higher (need to train critic) | Lower |

| Sample efficiency | Higher (value function stabilizes) | Lower (rely on group size) |

| Group size G | N/A | 4-32 responses per prompt |
12.5 KTO: Kahneman-Tversky Optimization
KTO (Ethayarajh et al., 2024) aligns models using a prospect theory-inspired loss that only requires knowing whether each response is "desirable" or "undesirable" (not paired preferences).
KTO loss:
L_KTO(θ) = E_{x, y} [ w(y) · (log(1 + exp(β · (KL(π_θ||π_ref)(x, y) - δ_ref(x)))))
                          - (1 - w(y)) · (log(1 + exp(β · (δ_ref(x) - KL(π_θ||π_ref)(x, y))))) ]


Where:

- w(y) is 1 for desirable (chosen) responses, 0 for undesirable (rejected)

- KL(π_θ||π_ref)(x, y) = log(π_θ(y|x) / π_ref(y|x))

- δ_ref is a reference point (typically the average KL of the reference model on good responses)
Key advantage: KTO works with unpaired "desired/undesired" labels (e.g., thumbs up/down) instead of paired comparisons. This simplifies data collection.
12.6 ORPO: Odds Ratio Preference Optimization
ORPO (Hong et al., 2024) combines SFT and preference learning into a single loss, eliminating the reference model.
ORPO loss:
L_ORPO(θ) = E_{(x, y_w, y_l)} [ -log p_θ(y_w|x) 
                                 - λ · log σ(log(odds_θ(y_w|x) / odds_θ(y_l|x))) ]


Where odds_θ(y|x) = p_θ(y|x) / (1 - p_θ(y|x)) and λ is a weighting parameter.
The odds ratio:
odds_θ(y_w|x) / odds_θ(y_l|x) = [π_θ(y_w|x) / (1 - π_θ(y_w|x))] / [π_θ(y_l|x) / (1 - π_θ(y_l|x))]


Key insight: ORPO avoids the reference model entirely by using the odds ratio as the implicit reward. The first term is the standard SFT loss (maximize likelihood of preferred), and the second term maximizes the odds ratio between preferred and rejected.
Advantages:

- No reference model needed (2× memory savings vs DPO)

- Single-stage training (SFT + alignment)

- Simpler pipeline
Disadvantages:

- May be less stable than DPO for challenging alignment tasks

- The odds ratio assumption (that odds reflect preference quality) may not always hold
12.7 SimPO: Simple Preference Optimization
SimPO (Meng et al., 2024) further simplifies DPO by replacing the reference model with a length-normalized reward based on the average log probability.
SimPO reward:
r_θ(x, y) = (β / |y|) · log π_θ(y|x)


Where |y| is the response length. Length normalization prevents the model from preferring longer responses (a common issue in unnormalized methods).
SimPO loss:
L_SimPO(θ) = -E_{(x, y_w, y_l)} [log σ(β · ((1/|y_w|) log π_θ(y_w|x) - (1/|y_l|) log π_θ(y_l|x)) - γ)]


Where γ is a margin hyperparameter (typically 0.5-1.5).
Advantages over DPO:

- No reference model needed

- Length normalization reduces verbosity bias

- Margin γ allows controlling the separation between chosen and rejected
SimPO vs DPO on verbosity:
DPO: r_θ(x, y) = β · log(π_θ(y|x) / π_ref(y|x))
     → Longer responses can have lower probability, reducing bias
     But: if π_ref assigns low probability to long responses, DPO may favor long responses

SimPO: r_θ(x, y) = (β / |y|) · log π_θ(y|x)
     → Explicitly penalizes length by normalizing
     → More robust to response length differences


12.8 Rejection Sampling and Best-of-N
Rejection sampling: Sample N responses from the model, select the best one according to a reward model or heuristic:
def rejection_sampling(policy, prompt, reward_model, N=16):
📄 Reinforcement Learning: Foundations, Algorithms, and Modern Applications — 351 lines
AgentAlignmentCLIPDPOEvaluationLLMLoRAMulti-AgentMultimodalPPO
1. Introduction
Reinforcement Learning (RL) is the branch of machine learning concerned with how agents ought to take actions in an environment to maximize cumulative reward. Unlike supervised learning (learning from labeled data) or unsupervised learning (finding patterns in unlabeled data), RL learns from interaction — the agent tries actions, observes outcomes, and learns which actions produce the most reward.

1.1 The RL Loop
Agent → Action → Environment → State + Reward → Agent...
1.2 RL vs Supervised vs Unsupervised



Aspect
Supervised
Unsupervised
Reinforcement




Data
Labeled examples
Unlabeled data
Interaction history


Feedback
Per-instance labels
None (patterns)
Delayed reward signal


Goal
Generalize from examples
Find structure
Maximize cumulative reward


Time
Static
Static
Sequential (credit assignment)


Exploration
Not needed
Not needed
Essential



2. Markov Decision Processes
MDPs formalize sequential decision-making. Defined by (S, A, P, R, γ):

- S: state space

- A: action space

- P: transition dynamics P(s'|s,a)

- R: reward function R(s,a,s')

- γ: discount factor [0,1]

2.1 Policy
π(a|s) = probability of taking action a in state s
2.2 Value Functions

V^π(s) = E[Σγ^t R_t | s_0=s, π] — expected return from state s following π
Q^π(s,a) = E[Σγ^t R_t | s_0=s, a_0=a, π] — expected return taking a in s then following π

2.3 Bellman Equations
V^π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a)[R(s,a,s') + γV^π(s')]

Q^π(s,a) = Σ_{s'} P(s'|s,a)[R(s,a,s') + γ Σ_{a'} π(a'|s')Q^π(s',a')]
2.4 Optimality
V(s) = max_a Q(s,a)

Q(s,a) = Σ_{s'} P(s'|s,a)[R(s,a,s') + γ max_{a'} Q(s',a')]
3. Dynamic Programming
3.1 Policy Iteration


Evaluate: compute V^π for current π
Improve: π'(s) = argmax_a Σ_{s'} P(s'|s,a)[R(s,a,s') + γV^π(s')]
Repeat until convergence

3.2 Value Iteration
V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a)[R(s,a,s') + γV_k(s')]

Converges to V* without explicit policy representation.
3.3 Generalized Policy Iteration
Most RL algorithms alternate (partial) evaluation and (partial) improvement.
4. Model-Free Prediction
4.1 Monte Carlo Learning

Average returns from complete episodes.

V(s) ← V(s) + α(G_t - V(s))

where G_t is the actual return from state s.
4.2 Temporal Difference Learning
Learn from incomplete episodes by bootstrapping.

V(s_t) ← V(s_t) + α(r_t + γV(s_{t+1}) - V(s_t))

TD error: δ_t = r_t + γV(s_{t+1}) - V(s_t)
4.3 TD(λ)
Eligibility traces combine MC (λ=1) and TD(0) (λ=0).

V(s) ← V(s) + αδ_t e_t(s) where e_t(s) = γλ e_{t-1}(s) + 1(s_t=s)
5. Model-Free Control
5.1 Q-Learning (Watkins, 1989)

Off-policy TD control — learns optimal Q-function regardless of behavior policy.

Q(s,a) ← Q(s,a) + α[r + γ max_{a'} Q(s',a') - Q(s,a)]
5.2 SARSA
On-policy TD control — learns Q-function for the current policy.

Q(s,a) ← Q(s,a) + α[r + γ Q(s',a') - Q(s,a)]
5.3 Exploration vs Exploitation

ε-greedy: with probability ε, take random action; otherwise greedy
Boltzmann (softmax): P(a|s) ∝ exp(Q(s,a)/τ), τ controls exploration
Upper Confidence Bound: a = argmax_a Q(s,a) + c√(ln t/N(s,a))
Thompson Sampling: sample Q from posterior, act greedily w.r.t. sample

6. Function Approximation
When state/action spaces are too large for tables, use function approximators:

- Q(s,a) ≈ Q_θ(s,a) — parameterized by θ (neural network weights)

- V(s) ≈ V_θ(s)

- π(a|s) ≈ π_θ(a|s)

6.1 Linear Function Approximation
Q(s,a) = φ(s,a)ᵀw. Simple, stable, but limited expressivity.
6.2 Neural Function Approximation
Q(s,a) = NN_θ(s,a). Powerful but can be unstable.

Three "deadly sins" (Van Hasselt et al., 2018):

1. Function approximation (bias)

2. Bootstrapping (self-referential targets)

3. Off-policy learning (distribution mismatch)
7. Deep Q-Networks
7.1 DQN (Mnih et al., 2015)

First stable deep RL algorithm, playing Atari from pixels.
Key Innovations:

1. Experience Replay: Store (s,a,r,s') in a buffer, sample randomly to break correlations

2. Target Network: Fixed Q-target network, periodically updated to reduce moving target problem

3. Frame Stacking: 4 consecutive frames as input to capture motion
Loss: L(θ) = E[(r + γ max_{a'} Q(s',a'; θ⁻) - Q(s,a; θ))²]

where θ⁻ is the target network (frozen, periodically copied from θ)
7.2 DQN Improvements



Variant
Innovation
Gain




Double DQN
Decouple action selection from evaluation
Reduces overestimation bias


Dueling DQN
Separate V(s) + A(s,a) streams
Better policy evaluation


Prioritized Replay
Sample important transitions more
2-4× faster learning


C51 (Categorical DQN)
Learn distribution of returns, not just mean
State-of-the-art for years


Rainbow
Combine all improvements
Best DQN variant



8. Policy Gradient Methods
8.1 The Policy Gradient Theorem

∇J(θ) = E_π[∇log π_θ(a|s) Q^π(s,a)]
Key insight: increase probability of actions with high Q-values, decrease those with low Q-values, weighted by the gradient of log probability.
8.2 REINFORCE (Williams, 1992)
Monte Carlo policy gradient:

∇J(θ) = Σ_t G_t ∇log π_θ(a_t|s_t)

where G_t is the actual return from step t.
Issues: High variance because G_t is a sample estimate.
8.3 Variance Reduction

Baseline: Subtract a state-dependent baseline b(s) from Q-values
Advantage function: A(s,a) = Q(s,a) - V(s) — how much better is a than average?
Actor-Critic: Learn both policy (actor) and value function (critic)

9. Actor-Critic Methods
9.1 Advantage Actor-Critic (A2C)

Two networks:

- Actor: π_θ(a|s) — learns the policy

- Critic: V_φ(s) — learns state values
Losses:

- Actor: ∇J(θ) = ∇log π_θ(a|s) (r + γV(s') - V(s))

- Critic: L(φ) = (r + γV_φ(s') - V_φ(s))²
9.2 A3C (Asynchronous Advantage Actor-Critic)
Multiple parallel workers each with their own environment copy. Workers update a shared model asynchronously.
9.3 PPO (Proximal Policy Optimization, Schulman et al., 2017)
The default RL algorithm for 2022-2026.
Key idea: trust region optimization via clipped surrogate objective.

L_CLIP(θ) = E[min(r_t(θ)A_t, clip(r_t(θ), 1-ε, 1+ε)A_t)]

where r_t(θ) = π_θ(a_t|s_t)/π_θ_old(a_t|s_t) is the probability ratio.
Why PPO works:

- Simple to implement (no Lagrange multipliers)

- Stable (clipping prevents large policy updates)

- Compatible with discrete and continuous actions

- Used for: RLHF, Dota 2, robotics, game playing
9.4 SAC (Soft Actor-Critic, Haarnoja et al., 2018)
Maximum entropy RL — optimizes both reward and entropy:

J = Σ E[r_t + α H(π(·|s_t))]
Advantages:

- Off-policy (sample efficient)

- Automatically tunes α (temperature)

- State-of-the-art for continuous control

- Used for: robotics, autonomous driving
10. Model-Based RL
10.1 Dyna Architecture

Learn a model of the environment, then use it for planning:

1. Interact with real environment → store experience

2. Learn model: P_θ(s'|s,a), R_θ(s,a) from experience

3. Plan using the model: simulate trajectories, update Q-values

4. Act: use Q-values to select actions
10.2 MuZero (Schrittwieser et al., 2020)
Learns a model in latent space without explicit reward or transition prediction.

- Representation function: h(s) = latent state

- Dynamics function: g(latent, a) = next latent + reward

- Prediction function: f(latent) = policy + value

- Uses MCTS for planning in latent space

- Achieves superhuman performance in Go, Chess, Shogi, Atari
11. Inverse RL and Imitation Learning
11.1 Behavioral Cloning

Supervised learning: learn π(a|s) from expert demonstrations.

Problem:* Distribution mismatch — the agent makes small mistakes, enters states the expert never was in, and compounding errors grow.
11.2 Inverse Reinforcement Learning
Given expert demonstrations, learn the reward function R(s) that the expert was optimizing.
Methods:

- Maximum Entropy IRL (Ziebart et al., 2008): find R that maximizes the likelihood of expert behavior under maximum entropy model

- GAIL (Generative Adversarial Imitation Learning): discriminator distinguishes expert vs agent, agent tries to fool it
12. Multi-Agent RL
12.1 Challenges


Non-stationarity: Other agents' policies change → environment distribution shifts
Scalability: Joint action space grows exponentially with agents
Credit assignment: Which agent's action contributed to the reward?
Communication: What information should agents share?

12.2 Key Algorithms



Algorithm
Approach
Best For




Independent Q-Learning
Each agent learns Q-function independently
Simple tasks


VDN
Factorized Q-functions: Q_tot = Σ Q_i
Cooperative tasks


QMIX
Monotonic mixing: Q_tot = f(Q_1,...,Q_n)
More complex coordination


MADDPG
Centralized critic, decentralized actors
Mixed competitive/cooperative


MAPPO
Multi-agent PPO
General multi-agent RL



📄 Graph Neural Networks: Theory and Applications — 168 lines
AttentionGNNMultimodalRAGRL
1. Introduction
Graph Neural Networks (GNNs) extend deep learning to graph-structured data. Unlike images (grid) or sequences (line), graphs have irregular structure — varying connectivity, arbitrary node degrees, and permutation-invariant representations. GNNs learn from node features, edge features, and graph topology.

Why Graphs?

Molecular structures are graphs (atoms=nodes, bonds=edges)
Social networks are graphs (users=nodes, follows=edges)
Knowledge bases are graphs (entities=nodes, relations=edges)
Code (ASTs are graphs)
Transit/transportation networks

2. Graph Theory Refresher
A graph G = (V, E, X_v, X_e) where:

- V: set of n nodes with features X_v ∈ R^{n×d}

- E: set of m edges with features X_e

- A: adjacency matrix A ∈ R^{n×n} (A_ij = 1 if edge from i to j)

- D: degree matrix (diagonal, D_ii = Σ_j A_ij)

- L: Laplacian L = D - A

- Normalized Laplacian: L_norm = I - D^{-1/2} A D^{-1/2}

Key Properties:

- Permutation invariance: graph representations should be unchanged by node reordering

- Locality: most information is in local neighborhoods

- Sparsity: real-world graphs are extremely sparse
3. Message Passing Framework
The core paradigm: each node aggregates messages from its neighbors to update its representation.

3.1 General Message Passing
h_v^{(k+1)} = UPDATE^{(k)}(h_v^{(k)}, AGGREGATE^{(k)}({h_u^{(k)}: u ∈ N(v)}))

- AGGREGATE: mean, sum, max, attention-weighted sum, LSTM

- UPDATE: MLP, GRU, linear transformation

- After K layers, h_v^{(K)} contains information from the K-hop neighborhood
3.2 Over-smoothing Problem
As K increases, node representations converge to the same value. This is the fundamental limitation of deep GNNs.

- Practical depth: 2-4 layers for most tasks

- Mitigation: skip connections, residual connections, PairNorm, DropEdge
4. Convolutional GNNs
4.1 Graph Convolutional Network (GCN, Kipf & Welling, 2017)

H^{(k+1)} = σ(Â H^{(k)} W^{(k)})

where  = D^{-1/2} à D^{-1/2} and à = A + I
Intuition: Each node averages its neighbors' features, then applies a learned linear transformation.
4.2 GraphSAGE (Hamilton et al., 2017)
Instead of full neighborhood, sample a fixed-size neighbor set.

h_v^{(k+1)} = σ(W·CONCAT(h_v^{(k)}, AGG({h_u^{(k)}, u ∈ N_s(v)})))

- Mean: average neighbor features

- LSTM: order neighbors randomly, apply LSTM

- Pool: MLP → max/mean pool over neighbors
4.3 GIN (Graph Isomorphism Network, Xu et al., 2019)
h_v^{(k)} = MLP^{(k)}((1+ε^{(k)})·h_v^{(k-1)} + Σ_{u∈N(v)} h_u^{(k-1)})

The most expressive GNN — as powerful as the Weisfeiler-Lehman graph isomorphism test.
5. Attentional GNNs
5.1 Graph Attention Network (GAT, Veličković et al., 2018)

Compute attention weights between connected nodes:

α_ij = softmax_j(LeakyReLU(a^T[Wh_i || Wh_j]))

h_i' = σ(Σ_{j∈N(i)} α_ij W h_j)
Multi-head attention: K independent attention heads, concatenate or average outputs.
5.2 GATv2 (Brody et al., 2022)
GAT's attention computes a_ij = LeakyReLU(a^T[Wh_i || Wh_j]) — the attention score is a function of the concatenation of both node features. GATv2 changes the order:

e(h_i, h_j) = a^T LeakyReLU(W[h_i || h_j])

More expressive — can represent any attention function.
6. Spectral Methods
Graph convolutions in the spectral domain (Fourier transform on graphs).

6.1 ChebNet (Defferrard et al., 2016)
Filter in the graph Fourier domain using Chebyshev polynomials:

g_θ(L) = Σ_{k=0}^K θ_k T_k(Λ̃) where T_k are Chebyshev polynomials
Localized in the node domain — K-th order polynomial gives K-localized filters.
6.2 GCN as ChebNet-1
GCN approximates ChebNet with K=1 and λ_max≈2, creating the simple first-order formulation that became the standard.
7. Graph Pooling
Reduce graph size while preserving structure.




Method
Approach
Complexity




Top-K pooling
Select top-K nodes by learned score
O(n)


DiffPool (Ying et al., 2018)
Learn assignment matrix S to cluster nodes
O(n²)


SAGPool
Self-attention on node features
O(n)


MinCut pooling
Differentiable graph cut
O(n²)


EdgePool
Contract edges with learned scores
O(m)



8. Scalability



Method
Strategy
Training Scale
Test Scale




Full graph
Full-batch training
10K-100K nodes
Same


Cluster-GCN
Graph partitioning into clusters
1M-100M nodes
All


GraphSAINT
Random walk-based sampling
100M-1B nodes
All


ShadowGNN
Neighborhood sampling
1B+ nodes
All



9. Graph Generative Models



Model
Approach
Applications




MoFlow
Normalizing flows on graphs
Molecular generation


DiGress
Discrete denoising on graphs
Drug design


GCPN
RL for graph generation
Molecular optimization


GraphARM
Autoregressive graph generation
Protein design



10. Applications



Domain
Task
Model




Drug discovery
Molecular property prediction
GIN, MPNN


Fraud detection
Transaction networks, account collusion
GAT, GraphSAGE


Recommendation
User-item interaction graph
LightGCN, PinSage


Knowledge graphs
Link prediction, relation extraction
R-GCN, CompGCN


Traffic
Traffic flow prediction, ETA
STGCN


Physics
Particle tracking, force prediction
GNS, MeshGraphNet


Code
Code analysis (AST)
GGNN, Code2Vec



📄 Machine Learning Mathematics: Foundations — 173 lines
LLMLoRAQuantizationRAGRLRNN
1. Linear Algebra
1.1 Vectors and Matrices


Vector: v ∈ R^d. Dot product: v·w = Σ v_i w_i
Matrix: A ∈ R^{m×n}. Operations: transpose, inverse, trace, determinant
Norm: L1 (Σ|v_i|), L2 (√Σ v_i²), L∞ (max|v_i|), Frobenius (√Σ A_ij²)

1.2 Eigenvalues and Eigenvectors
Av = λv — v is eigenvector, λ is eigenvalue

- Symmetric matrices: real eigenvalues, orthogonal eigenvectors

- Singular Value Decomposition (SVD): A = UΣV^T

  - U: left singular vectors (A^TA eigenvectors)

  - Σ: singular values (diagonal)

  - V: right singular vectors (AA^T eigenvectors)

- Key in ML: PCA, matrix factorization, low-rank approximation
1.3 Matrix Calculus

∂(Ax)/∂x = A^T
∂(x^TAx)/∂x = (A+A^T)x
∂log|X|/∂X = (X^{-1})^T

1.4 Key Concepts for Deep Learning

Rank: dimension of range — low rank = low effective dimension
Low-rank approximation: A ≈ UV^T (U ∈ R^{m×k}, V ∈ R^{n×k}) — foundation of LoRA
Positive definiteness: x^TAx > 0 ∀x — important for optimization

2. Probability Theory
2.1 Basic Rules


P(A|B) = P(A∩B)/P(B) (conditional)
P(A∩B) = P(A|B)P(B) (chain rule)
P(A∪B) = P(A)+P(B)-P(A∩B)
P(B) = Σ P(B|A_i)P(A_i) (law of total probability)

2.2 Distributions



Distribution
Parameters
Mean
Variance
Use Case




Bernoulli
p
p
p(1-p)
Binary classification


Binomial
n,p
np
np(1-p)
Count of successes


Gaussian N(μ,σ²)
μ,σ²
μ
σ²
Continuous data, noise assumption


Log-normal
μ,σ²
e^{μ+σ²/2}
(e^{σ²}-1)e^{2μ+σ²}
Positive values


Exponential
λ
1/λ
1/λ²
Wait times


Dirichlet
α
α_i/Σα_j
—
Topic proportions



2.3 Bayes' Theorem
P(A|B) = P(B|A)P(A)/P(B)

- P(A): prior

- P(B|A): likelihood

- P(A|B): posterior

- P(B): evidence (marginal)
2.4 Maximum Likelihood Estimation (MLE)
θ_MLE = argmax_θ log P(data|θ)

For Gaussian: MLE → mean of data, (1/n)Σ(x_i-μ)² for variance

For Bernoulli: MLE → observed frequency
2.5 Maximum A Posteriori (MAP)
θ_MAP = argmax_θ [log P(data|θ) + log P(θ)]

MLE + prior = MAP
3. Calculus
3.1 Derivatives


∂/∂x (f(x) + g(x)) = f'(x) + g'(x)
∂/∂x (f(x)g(x)) = f'(x)g(x) + f(x)g'(x) (product rule)
∂/∂x f(g(x)) = f'(g(x))g'(x) (chain rule)
∂/∂x (x^n) = nx^{n-1}
∂/∂x (e^x) = e^x
∂/∂x (log x) = 1/x

3.2 Chain Rule (Vector)
∂L/∂x = (∂y(x)/∂x)^T · (∂L/∂y) — chain rule for vectors, used in backpropagation
3.3 Gradients
∇f = [∂f/∂x₁, ∂f/∂x₂, ..., ∂f/∂x_d]^T — direction of steepest ascent

Gradient descent: x_{t+1} = x_t - η∇f(x_t)
3.4 Jacobian and Hessian

Jacobian: J_ij = ∂f_i/∂x_j (first derivative matrix)
Hessian: H_ij = ∂²f/∂x_i∂x_j (second derivative matrix, symmetric for smooth f)
Hessian properties determine local curvature

4. Statistics
4.1 Hypothesis Testing


Null hypothesis H₀: no effect
Alternative Hₐ: there is an effect
p-value: P(observed data | H₀ true)
Significance level α = 0.05 (conventional)
Type I error: rejecting true H₀ (false positive)
Type II error: failing to reject false H₀ (false negative)

4.2 Common Tests



Test
Purpose
Assumptions




t-test
Compare two means
Normal, independent


ANOVA
Compare k means
Normal, independent, equal variance


χ² test
Test independence
Categorical data, expected ≥ 5


Kolmogorov-Smirnov
Compare distributions
Continuous, non-parametric



4.3 Confidence Intervals
95% CI: x̄ ± 1.96·σ/√n — means the true parameter lies in interval with 95% confidence (not probability).
5. Information Theory
5.1 Entropy

H(X) = -Σ P(x) log P(x) — average information content or uncertainty

- Binary: H ≤ 1 bit (fair coin = 1 bit, biased = less)

- 256 values: H ≤ 8 bits
5.2 Cross-Entropy
H(P,Q) = -Σ P(x) log Q(x) — average # bits needed to encode data from P using Q's distribution

Training loss for classification: cross-entropy loss = H(p_data, p_model)
5.3 KL Divergence
D_KL(P||Q) = Σ P(x) log(P(x)/Q(x))

- Measures dissimilarity between distributions

- D_KL ≥ 0, equality iff P=Q

- Asymmetric: D_KL(P||Q) ≠ D_KL(Q||P)
5.4 Mutual Information
I(X;Y) = H(X) - H(X|Y) = D_KL(P(x,y)||P(x)P(y))

- Measures dependence between variables

- I(X;Y) = 0 iff X and Y are independent

- Used for: feature selection, representation learning
6. Optimization
6.1 Gradient Descent Variants




Method
Update
Characteristics




SGD
θ ← θ - η∇L
Basic, noisy


Momentum
v ← γv + η∇L, θ←θ-v
Accelerates along consistent directions


Adam
Adaptive step per parameter
Default for deep learning


AdamW
Adam + weight decay decoupled
Better generalization


RMSprop
Adaptive, divide by RMS of recent gradients
Good for RNNs



6.2 Convex vs Non-convex Optimization

Convex: one global minimum, guarantees
Non-convex: many local minima, saddle points, no guarantees
Most deep learning problems are non-convex

6.3 Lagrangian Duality
Lagrangian: L(x,λ) = f(x) + λg(x) — optimize f subject to constraints g

SVM, KKT conditions, constrained optimization
📄 Federated Learning and Privacy-Preserving Machine Learning — 149 lines
CLIPDeploymentDifferential PrivacyFederated LearningFine-tuningGovernanceInferenceLLMQuantizationRAG
1. Introduction
Privacy-preserving ML techniques enable training and inference on sensitive data without compromising privacy. This is critical for healthcare (patient data), finance (transaction data), and personal AI assistants.

Privacy Threats in ML

Model inversion: reconstructing training data from model parameters
Membership inference: determining if a specific example was in training data
Gradient leakage: reconstructing data from shared gradients
Prompt leakage: extracting system prompts from LLM interactions

2. Federated Learning
2.1 Core Concept

Train a model across decentralized data without centralizing the data:

1. Server sends current model to clients

2. Clients train locally on their own data

3. Clients send model updates (gradients/weights) back

4. Server aggregates updates (Federated Averaging)

5. Repeat
2.2 Algorithm: FedAvg
w_{t+1} = Σ (n_k/N) w_{t+1}^k — weighted average of client models

Where: n_k is data size of client k, N is total data size
2.3 Challenges

Data heterogeneity (non-IID): Client data distributions differ
Solutions: FedProx, SCAFFOLD, FedBN, MOON
Communication cost: Expensive for large models
Solutions: compression (gradient quantization, sparsification), local SGD
Client heterogeneity: Different compute, connectivity
Solutions: asynchronous aggregation, partial participation
Security: Malicious clients poisoning the global model
Solutions: robust aggregation (Trimmed Mean, Krum, Median)

2.4 Frameworks



Framework
Language
Scale
Features




Flower
Python
Cross-device + cross-silo
OOTB strategies, simulation


TensorFlow Federated
Python
Simulation-focused
TF integration


PySyft
Python
Research
Secure aggregation, MPC


OpenFL
Python
Healthcare
Intel ecosystem


FATE
Python + Java
Enterprise
Production ready


NVIDIA FLARE
Python
Enterprise
Healthcare specialization



3. Differential Privacy (DP)
3.1 Definition

A mechanism M is ε-differentially private if for all datasets D, D' differing by one record:

P(M(D) ∈ S) ≤ e^ε · P(M(D') ∈ S)
ε is privacy budget: lower = more privacy (typical ε = 1-10)
3.2 Mechanisms

Laplace mechanism: Add Laplace noise proportional to sensitivity/ε
Gaussian mechanism: Add Gaussian noise proportional to sensitivity · √(2log(1.25/δ))/ε
Exponential mechanism: Sample from a distribution weighted by utility

3.3 DP-SGD (Training with DP)
For each training step:

1. Sample a mini-batch

2. Compute per-sample gradients

3. Clip gradients to L2 norm C (per-sample clipping)

4. Add Gaussian noise to the sum of gradients

5. Update model with noisy gradients
Cost: DP-SGD reduces accuracy by 2-10% depending on ε and model size
3.4 LLM Privacy

RANTEXT: DP text generation via token-level DP
DP-Prompt: DP for LLM prompt data
DP-SGD for fine-tuning: Add DP to fine-tuning (expensive but effective)

4. Secure Multi-Party Computation (MPC)
Multiple parties compute a function on their private inputs without revealing inputs.

4.1 Core Protocols



Protocol
Efficiency
Rounds
Security Model




Garbled Circuits
Best for boolean
Constant
Semi-honest or malicious


Secret Sharing
Best for linear operations
Linear
Honest or dishonest majority


Oblivious Transfer
Cryptographic building block
Constant
Various



4.2 Applications

Private inference: server has model, client has input — compute without revealing either
Private training: multiple institutions train on combined data without sharing

5. Homomorphic Encryption (HE)
Compute directly on encrypted data without decrypting.

5.1 Types



Type
Operations
Efficiency




Partially HE (PHE)
Either addition or multiplication
Fast


Somewhat HE (SWHE)
Limited depth addition + multiplication
Moderate


Fully HE (FHE)
Unlimited depth addition + multiplication
Very slow (1000-10000×)


Leveled HE
Up to L-depth circuits
Slower with depth



5.2 For ML

Linear layers: Efficient with HE (matrix multiplication)
Non-linear layers (ReLU, softmax): Very expensive (polynomial approximations)
Practical: Only linear layers encrypted; non-linear operations on decrypted intermediate values
HE-Transformer (Microsoft SEAL): Protocol for neural network inference

6. Privacy in LLMs
6.1 Attack Vectors


Prompt injection: Extract system prompt (often proprietary)
Membership inference: Determine if specific text was in training data
Data extraction: Extract memorized training data (credit cards, personal info)
Fine-tuning leakage: Fine-tuning on private data can leak through model outputs

6.2 Defenses



Defense
Protection
Cost




Deduplication
Reduce memorization
Moderate


DP-SGD training
Data-level DP
High


Prompt sandboxing
Prompt/system leakage
Low


Output filtering
PII in generation
Low


On-device inference
Data never leaves device
Requires on-device model



📄 Causal Inference and Machine Learning — 125 lines
Causal InferenceEvaluationGNNInferenceRAGRL
1. Introduction
Causal inference studies cause-and-effect relationships: what happens to Y if we change X? This is fundamentally different from prediction, which asks: given X, what is Y? Causal reasoning powers: A/B testing, drug effectiveness, policy evaluation, and decision-making under intervention.

Key Problem: Correlation ≠ causation. Ice cream sales and drowning deaths are correlated (both increase in summer), but banning ice cream won't reduce drownings.
2. Causal vs Statistical



Aspect
Statistical
Causal




Question
P(Y
X)?


Data
Observational only
Observational + intervention


Answer
Association
Effect


Assumptions
Standard stats
Causal assumptions (graph, ignorability)



3. Causal Graphs (Directed Acyclic Graphs)
Nodes = variables, Edges = causal relationships.

3.1 Three Fundamental Structures

Chain: X → Z → Y (X causes Z causes Y). Conditioning on Z blocks the path.
Fork (confounder): X ← Z → Y (Z causes both X and Y). Conditioning on Z removes spurious correlation.
Collider: X → Z ← Y (X and Y both cause Z). Conditioning on Z induces spurious correlation.

3.2 d-Separation
A path is blocked if it contains a non-collider that's conditioned on, or a collider that's not conditioned on. If all paths between two sets are blocked, they're d-separated (conditionally independent).
4. Potential Outcomes Framework (Rubin Causal Model)
For each unit i:

- Y_i(1): outcome if treated

- Y_i(0): outcome if control

- Individual treatment effect: τ_i = Y_i(1) - Y_i(0)

- Problem: we only observe one of Y_i(1), Y_i(0) — the fundamental problem of causal inference

4.1 Average Treatment Effect (ATE)
ATE = E[Y(1) - Y(0)] — average effect across population
4.2 Conditional Average Treatment Effect (CATE)
CATE(x) = E[Y(1) - Y(0) | X=x] — effect for subgroup with features x

Also called: heterogeneous treatment effect, uplift
4.3 Key Assumptions



Assumption
Meaning




Ignorability (unconfoundedness)
No unmeasured confounders


Positivity (overlap)
Everyone has non-zero probability of treatment


Consistency
Treatment is well-defined (SUTVA)


No interference
One unit's treatment doesn't affect another's outcome



5. Treatment Effect Estimation
5.1 Experimental (RCT)

Gold standard: Randomize treatment assignment → no confounding

Analysis: simple difference in means
5.2 Observational Methods



Method
Idea
When to Use




Matching
Match treated/control on covariates
High-dimensional covariates


Propensity Score Matching
Match on P(treatment
X)


IPW (Inverse Probability Weighting)
Weight by 1/propensity score
Few treated units


Doubly Robust (AIPW)
Combine outcome model + propensity model
Best of both


IV (Instrumental Variables)
Use instrument (Z) that affects treatment but not outcome
Unmeasured confounding


DiD (Difference-in-Differences)
Compare treated/control over time
Longitudinal data


RDD (Regression Discontinuity)
Compare units just above/below threshold
Policy changes at threshold



5.3 Causal ML (Meta-Learners)



Learner
Approach
Best For




S-Learner
Single model with treatment as feature
Simple, when T confounds X


T-Learner
Two models (control, treated)
Strong treatment interactions


X-Learner
Cross predictions, propensity weighting
Unbalanced treatment/control


Uplift Tree
Tree that maximizes treatment effect split
Marketing, targeting


Causal Forest
Random forest for CATE
SOTA non-linear effects



6. Causal Discovery
Learn causal structure from observational data.




Algorithm
Type
Output




PC algorithm
Constraint-based (conditional independence tests)
CPDAG (equivalence class)


GES
Score-based (search for best graph)
CPDAG


LiNGAM
Linear non-Gaussian
Full DAG


NOTEARS
Continuous optimization for DAG
Full DAG


DAG-GNN
Non-linear causal discovery
Full DAG



7. Causal ML in Practice



Application
Method
Impact




Drug effectiveness
RCT (gold), Causal Forest (observational)
Treatment effect estimation


Marketing campaign
Uplift modeling: who responds to ads?
20-40% better targeting


Pricing elasticity
CATE estimation per customer segment
Optimized pricing


Policy evaluation
DiD, RDD, synthetic control
Policy effectiveness


Fairness analysis
Causal fairness criteria
Non-discriminatory AI



AI Library of Alexandria — Foundations · 10 Docs · 10,334 Lines
Home · June 2026