Math Foundations

Av = λv - multiplying matrix A by eigenvector v only scales it (by λ), never changes its direction.

• PCA: eigenvectors of the covariance matrix are the principal components (directions of max variance). Eigenvalues = variance explained in each direction. Sort descending, take top-k.
• RNN stability: a recurrent network blows up if the spectral radius (largest eigenvalue magnitude) of the weight matrix > 1. Gradient clipping and orthogonal init address this.
• Kernel SVMs: the kernel matrix must be PSD (all eigenvalues ≥ 0). Indefinite kernels break the dual formulation.
• Covariance matrices are always PSD - all eigenvalues ≥ 0 because x^TCx = ||X x||² ≥ 0.

Note: PCA on MNIST - first eigenvector captures global brightness, later ones capture strokes. Draw this connection to what each dimension "means."

A = UΣV^T where U (m×m) and V (n×n) are orthogonal, Σ (m×n) is diagonal with non-negative singular values σ₁ ≥ σ₂ ≥... ≥ 0.

• Dimensionality reduction: keep top-k columns of U, V and top-k singular values. Minimizes reconstruction error (Eckart-Young theorem).
• Recommender systems: matrix factorization of user-item rating matrix.
• PCA connection: right singular vectors V = eigenvectors of A^TA. Singular values σ_i = √λ_i.
• Pseudo-inverse: A^† = VΣ^†U^T - solves least squares even for non-square/singular matrices.
• Why not eigendecomposition: SVD works on any m×n matrix; eigendecomposition requires square symmetric. SVD is more numerically stable.

Jacobian J_ij = ∂f_i/∂x_j - matrix of first-order partial derivatives for vector-valued functions. Shape: (output_dim, input_dim).

Hessian H_ij = ∂²L/∂x_i∂x_j - matrix of second-order partial derivatives of a scalar loss. Shape: (params, params).

• Jacobian in backprop: the chain rule is a product of Jacobians. ∂L/∂x = (∂y/∂x)^T · ∂L/∂y.
• Hessian for analysis: positive definite H = local minimum; indefinite = saddle point. Eigenvalues of H = curvature in each direction.
• Why Hessian is rarely used for training: O(n²) to compute, O(n²) to store for n parameters. Newton's method uses H^-1g - infeasible for billions of params. Approximations: L-BFGS, K-FAC (Kronecker factored).

For input X of shape [batch, seq_len, d_model]:

• Q = X @ W_Q → [batch, seq_len, d_k] - project to query space
• K = X @ W_K → [batch, seq_len, d_k] - project to key space
• V = X @ W_V → [batch, seq_len, d_v] - project to value space
• scores = Q @ K.T / sqrt(d_k) → [batch, seq_len, seq_len] - pairwise compatibility
• out = softmax(scores) @ V → [batch, seq_len, d_v] - weighted aggregation
• out = out @ W_O → [batch, seq_len, d_model] - output projection
• ffn = Linear(ReLU(Linear(out))) → two more matrix multiplications

Total per Transformer block: ~8 matrix multiplications. The attention matrix QK^T is the only O(n²) operation - the bottleneck for long sequences.

• Orthogonal matrix: W^TW = I. Columns are unit vectors, pairwise perpendicular.
• Norm preservation: ||Wx|| = ||x|| - orthogonal matrices are isometries. They rotate/reflect but don't scale.
• In deep networks: an orthogonal weight matrix has all singular values = 1. This prevents both vanishing (σ < 1) and exploding (σ > 1) gradients through layers.
• Orthogonal initialization: initialize W as a random orthogonal matrix (QR decomposition of random Gaussian). Proven to help with deep networks.
• Spectral normalization: divide W by its largest singular value σ_max at each step. Used in GANs (discriminator Lipschitz constraint).

MLE: θ* = argmax P(data|θ) - parameters that maximize likelihood of observed data.

MAP: θ* = argmax P(data|θ)·P(θ) = argmax [log-likelihood + log-prior]

• They coincide when the prior is uniform (flat) - then log-prior is a constant and doesn't affect the argmax.
• MAP with Gaussian prior P(θ) ∝ exp(-||θ||²/2σ²) → adds -λ||θ||² to log-likelihood → L2 / Ridge regularization
• MAP with Laplace prior P(θ) ∝ exp(-|θ|/b) → adds -λ||θ||₁ → L1 / LASSO regularization

So regularization is Bayesian inference with different priors - L2 says you believe weights are Gaussian around 0; L1 says you believe they're sparse.

For a model f̂ trained on dataset D:

MSE = Bias² + Variance + Irreducible Noise

• Bias: error from wrong assumptions in the model. High-bias = underfitting (linear model for nonlinear data).
• Variance: sensitivity to training data fluctuations. High-variance = overfitting (memorizes training set).

Complex models (deep nets, many parameters): low bias, high variance. Simple models (linear regression): high bias, low variance. Regularization reduces variance at cost of some bias.

Twist: deep nets with SGD can have low bias AND surprisingly low variance (double descent phenomenon). Traditional tradeoff breaks for very overparameterized models.

Entropy H(P) = -Σ P(x) log P(x) - average surprise / uncertainty of distribution P. Maximized by uniform distribution, 0 for deterministic distribution.

Cross-entropy H(P,Q) = -Σ P(x) log Q(x) - average bits needed to encode P-distributed data using code optimized for Q.

Relationship: H(P,Q) = H(P) + KL(P||Q)

The cross-entropy loss in classification: L = -Σ y_i log p̂_i where y is one-hot true label, p̂ is predicted probability. This equals H(y, p̂). Minimizing cross-entropy = minimizing KL divergence from true distribution (H(y) is fixed - it's 0 for one-hot labels).

P(H|E) = P(E|H) · P(H) / P(E)

Posterior = Likelihood × Prior / Evidence

• Naive Bayes classifier: P(class|features) ∝ P(features|class)·P(class)
• Bayesian neural networks: maintain a distribution over weights instead of point estimates - better uncertainty quantification
• MAP estimation: mode of posterior = combining likelihood with prior (see MLE vs MAP)
• Calibration: a well-calibrated model's confidence should match Bayesian posterior probabilities

• Type I (false positive): rejecting true null hypothesis. e.g., spam filter marks legitimate email as spam. Rate = 1 - Precision.
• Type II (false negative): failing to reject false null hypothesis. e.g., spam filter misses actual spam. Rate = 1 - Recall = FNR.

In ML: you control the tradeoff via decision threshold. Lower threshold → more positives → fewer false negatives (higher recall) but more false positives (lower precision). The ROC curve and PR curve visualize this.

When to prioritize: Medical diagnosis - minimize Type II (miss no cancer); spam filter - minimize Type I (don't block legitimate email).

The sum (or mean) of n independent, identically distributed random variables approaches a normal distribution as n → ∞, regardless of the original distribution. Mean → population mean, variance → σ²/n.

• Mini-batch gradient estimates: each mini-batch estimate of the gradient is approximately normal for large batch sizes
• Statistical testing: comparing two models' performance - can use t-tests because sample means are approximately normal
• Confidence intervals: model accuracy ± margin of error relies on CLT
• Why SGD works: noise in gradient estimates is approximately Gaussian, which has nice theoretical properties

p-value: probability of observing data at least as extreme as what you got, assuming the null hypothesis is true.

p < 0.05 means: if null were true, you'd see this only 5% of the time. It does NOT mean: 95% chance the hypothesis is correct.

Limitations in ML:

• Multiple comparisons: test 20 models - expect 1 to hit p<0.05 by chance. Use Bonferroni correction.
• Effect size ignored: p=0.001 for a 0.01% accuracy improvement is statistically but not practically significant
• Data leakage: repeated evaluation on same test set inflates apparent significance
• Better alternatives: bootstrapped confidence intervals, effect size (Cohen's d), held-out test sets

Let z be logits, p = softmax(z), y be one-hot target. Loss L = -Σ y_i log p_i.

Compute ∂p_j/∂z_i using softmax derivative:

• If j = i: ∂p_i/∂z_i = p_i(1 - p_i)
• If j ≠ i: ∂p_j/∂z_i = -p_jp_i

Applying chain rule: ∂L/∂z_i = -Σ_j y_j/p_j · ∂p_j/∂z_i = p_i - y_i

This beautiful result: gradient is simply predictions minus one-hot labels. For the correct class it's p_c-1, for others it's p_j. This is why cross-entropy + softmax is the universal classification loss.

• SGD: θ ← θ - α·∇L. Simple. Noisy with single samples. Full-batch = slow. Mini-batch = good tradeoff.
• Momentum: v ← βv + ∇L; θ ← θ - αv. Accumulates gradient direction. Dampens oscillations, accelerates in consistent directions. Like a ball rolling downhill with inertia. β=0.9 typical.
• RMSprop: v ← βv + (1-β)∇L²; θ ← θ - α·∇L/√(v+ε). Adapts learning rate per-parameter based on recent gradient magnitude. Good for RNNs.
• Adam = Momentum + RMSprop: m ← β₁m + (1-β₁)g; v ← β₂v + (1-β₂)g²; θ ← θ - α·m̂/√(v̂+ε). Bias-corrected (divides by 1-β^t at start). β₁=0.9, β₂=0.999, ε=1e-8.
• AdamW: Adam with weight decay applied directly to weights, not gradient estimate. Standard for LLMs.

Backprop multiplies Jacobians through each layer. If each layer's Jacobian has spectral radius < 1, the product → 0 exponentially fast. For sigmoid: derivative max is 0.25; after 10 layers, gradient ~ 0.25^10 ≈ 10^-6.

Fixes:

• ReLU: gradient = 1 when active (no saturation). Propagates gradient unchanged.
• Residual connections: gradient can flow directly through identity skip. Even if F(x) has small gradient, the total gradient ≥ 1.
• Batch/Layer normalization: normalizes activations, preventing saturation in sigmoid/tanh regions.
• Proper initialization: Xavier/He keeps variance constant across layers.
• LSTM/GRU: cell state highway with near-identity gradient through forget gate.

A saddle point has ∇L = 0 but is neither a minimum nor maximum - some directions curve up, some down (Hessian has positive and negative eigenvalues).

In high dimensions: most critical points are saddle points, not local minima. For a d-dimensional problem, local minima require ALL d eigenvalues of the Hessian to be positive. The probability of this decreases exponentially with d.

Are they a problem in practice? Not really:

• SGD noise helps escape saddle points
• Near saddle points, loss is still decreasing in many directions
• Local minima in deep nets tend to have similar loss to global minima (Goodfellow et al. 2015)

The real concern is flat regions / plateaus, not saddle points.