Problem Set 4 stands as the longest and most conceptually dense assignment in XCS229, reflecting the complexity of modern machine learning. With 50 total points distributed across four problems, the weightings vary: problem 1 (KL divergence) carries 10 points, problem 2 (MNIST) carries 15 points, problem 3 (spam classification) carries 12 points, and problem 4 (double descent) carries 13 points. This distribution emphasizes deep learning and empirical phenomena exploration equally with theoretical foundations.

The problems connect logically: theoretical understanding of KL divergence explains the cross-entropy loss used in MNIST training; MNIST neural network experience provides context for understanding generalization phenomena in double descent; Naive Bayes and logistic regression on spam offer alternative perspectives on optimization and generalization. Students are expected to implement non-trivial code, including neural network training loops and careful empirical analysis, making this assignment computation-intensive. Typical submissions include 500+ lines of code, numerous visualizations, and detailed written analysis. The assignment requires engagement with probability theory, optimization, implementation skills, and experimental methodology simultaneously.

Learning Objectives

By completing PS4, students should: (1) Understand KL divergence as fundamental to information theory and machine learning, (2) Implement and train neural networks on real data, (3) Evaluate models systematically using confusion matrices and per-class metrics, (4) Compare generative and discriminative approaches to text classification, (5) Explore the double descent phenomenon empirically and develop intuition for implicit regularization. The assignment balances theory with practice, encouraging students to verify mathematical predictions through experiments.

The formal definition of Kullback-Leibler divergence is D_KL(P||Q) = Σ_x P(x) log(P(x)/Q(x)). This can be rewritten as D_KL(P||Q) = E_x~P[log(P(x)/Q(x))] or D_KL(P||Q) = E_x~P[log P(x)] - E_x~P[log Q(x)], separating into an entropy term and a cross-entropy term. For continuous distributions, the sum becomes an integral: D_KL(P||Q) = ∫ p(x) log(p(x)/q(x)) dx.

Proving non-negativity requires Gibbs' inequality: E_x~P[log(Q(x)/P(x))] ≤ 0, which follows from Jensen's inequality applied to the concave function log. This yields D_KL(P||Q) = -E_x~P[log(Q(x)/P(x))] ≥ 0, with equality if and only if P(x) = Q(x) almost everywhere. The asymmetry D_KL(P||Q) ≠ D_KL(Q||P) reflects distinct interpretations: D_KL(P||Q) penalizes regions where P(x) is large but Q(x) is small (miss-mass), while D_KL(Q||P) penalizes regions where Q(x) is large but P(x) is small (hallucination).

Information-Theoretic Interpretation

KL divergence quantifies the expected surprise or information loss when assuming distribution Q while true distribution is P. If you assign probability Q(x) to events with true probability P(x), the expected number of extra bits needed is D_KL(P||Q) / ln(2). This interpretation explains why minimizing KL divergence appears throughout machine learning: you want your model distribution to match the data distribution as closely as possible in expectation.

Relationship to Mutual Information

Mutual information I(X;Y) = D_KL(P(x,y)||P(x)P(y)) measures dependence between X and Y. Conditional KL divergence D_KL(P(y|x)||Q(y|x)) = E_x~P[D_KL(P(y|x)||Q(y|x))] generalizes to conditional distributions. These relationships connect KL divergence to information-theoretic measures of independence and dependence, foundational for understanding variational inference and information-theoretic aspects of learning.

The connection to maximum likelihood estimation emerges from the fundamental relationship: minimizing D_KL(P_data||P_θ) is equivalent to maximizing E_x~P_data[log P_θ(x)], the log-likelihood of the model under observed data. This equivalence explains why cross-entropy loss L = -Σ_i y_i log(ŷ_i) appears ubiquitously: it is the negative log-likelihood (NLL) of the model, equivalent to KL divergence between empirical and learned distributions.

In variational inference, KL divergence constrains the learned approximation q(z|x) to stay close to the prior p(z), preventing posterior collapse and ensuring meaningful latent representations. The Evidence Lower Bound (ELBO) = E_q[log p(x|z)] - D_KL(q(z|x)||p(z)) naturally decomposes into reconstruction loss and a KL regularizer. When D_KL(q||p) is too large, training prioritizes matching the prior over reconstructing data; when too small, the model may ignore the latent variable entirely. Balancing this tradeoff via the β-VAE formulation E_q[log p(x|z)] - β D_KL(q(z|x)||p(z)) allows practitioners to tune the model's behavior.

Cross-Entropy Loss Derivation

For classification with true labels from empirical distribution P_data (one-hot vectors y_i) and model distribution P_θ (softmax outputs), KL divergence is D_KL(P_data||P_θ) = -H(P_data) + E_x~P_data[-log P_θ(y_i|x)] = -log(1) + E[-log P_θ] = E[-log P_θ]. Since entropy of one-hot distribution is zero, minimizing KL reduces to minimizing cross-entropy, the standard classification loss.

Variational Inference Framework

The ELBO also decomposes as ELBO = log p(x) - D_KL(q(z|x)||p(z|x)), showing that ELBO lower bounds the marginal likelihood p(x), with gap equal to the divergence between learned and true posterior. Maximizing ELBO simultaneously maximizes marginal likelihood and minimizes posterior approximation error, providing a principled objective for learning both encoder and decoder in generative models.

Implementing a neural network for MNIST requires careful attention to preprocessing, architecture design, and training mechanics. Input preprocessing normalizes pixel values from [0,255] to [0,1] or standardizes to zero mean and unit variance. This normalization stabilizes gradients and accelerates convergence. Some practitioners flatten 28×28 images to 784-dimensional vectors for fully-connected networks; others reshape to 1×28×28 for convolutional architectures.

A baseline architecture consists of two hidden layers with 128–256 units each, using ReLU activations σ(x) = max(0,x), followed by a softmax output layer. The ReLU choice matters: compared to sigmoid σ(x) = 1/(1+e^{-x}) or tanh(x), ReLU avoids vanishing gradients in deep networks and trains faster. The forward pass computes hidden activations h₁ = σ(W₁x + b₁), h₂ = σ(W₂h₁ + b₂), and logits z = W₃h₂ + b₃, with softmax probabilities ŷ_i = exp(z_i)/Σ_j exp(z_j).

Training Loop Structure

The training loop repeats for multiple epochs: (1) Sample a mini-batch of examples, (2) Forward pass to compute logits and softmax probabilities, (3) Compute cross-entropy loss L = -(1/n)Σ_i Σ_k y_ik log(ŷ_ik), (4) Backward pass via backpropagation to compute gradients ∂L/∂w, (5) Update parameters via gradient descent w := w - α∇L. With momentum or Adam optimization, updates incorporate accumulated gradients or adaptive learning rates per parameter.

Hyperparameter Tuning

Learning rate α typically ranges 0.001–0.01; too large causes oscillation, too small causes slow convergence. Batch size 32–128 provides good gradient estimates without excessive memory. Weight decay λ (L2 regularization) of 0.0001–0.001 prevents overfitting. Dropout with probability 0.2–0.5 randomly deactivates units during training, acting as an ensemble method. Early stopping monitors validation loss and halts training when validation performance ceases improving, preventing overfitting. Typical training requires 10–50 epochs to converge on MNIST.

After training, evaluation begins with computing overall test accuracy: the fraction of test examples the model classifies correctly. Well-trained networks achieve 97–99% accuracy, but this single number obscures important patterns. Per-class accuracy reveals that the model achieves 98–99% on some digits (0, 1) while achieving only 95–96% on others (4, 9). Creating a 10×10 confusion matrix C where C_ij counts predictions of digit j when true label is i reveals systematic confusion patterns: digit 4 is frequently misclassified as 9, digit 3 as 8.

Examining misclassified examples provides qualitative insights. Some misclassifications are genuinely ambiguous: a badly-written 4 can resemble 9, and vice versa. Others reveal true weaknesses: the model consistently mistakes certain digit styles. Visualizing learned features—the first-layer weight matrix or convolutional filters—shows that early layers learn edge and texture detectors (horizontal, vertical, diagonal edges), while deeper layers learn digit-specific shape detectors. This hierarchy reflects the network's bottom-up feature construction.

Error Analysis Techniques

Hard negative mining identifies examples that the model struggles with consistently. Creating separate accuracy metrics for clean vs. noisy data reveals robustness. Examining calibration—comparing predicted probabilities to actual accuracy—shows whether the model's confidence correlates with correctness. Adversarial example generation (small perturbations that flip predictions) reveals surprising brittleness, highlighting that MNIST accuracy is partly misleading about true robustness.

Feature Visualization

Visualizing hidden layer activations for specific test examples shows which units activate for which digits. Inverting network weights to generate optimal stimuli (the digit maximizing a neuron's activation) reveals what features each unit has learned to detect. Saliency maps highlighting pixels contributing to the model's prediction identify which image regions drive decisions. These interpretability techniques deepen understanding of what the network has learned.

Spam classification exemplifies text classification on a practical problem where avoiding false positives (marking legitimate email as spam) is critical. The bag-of-words representation treats each document as a vector of word frequencies, ignoring word order and syntax but capturing informative vocabulary differences. Building a vocabulary of V words creates V-dimensional feature vectors x ∈ ℝ^V where x_j counts or indicates presence of word j.

Naive Bayes models P(y|x) = P(x|y)P(y)/P(x) by factorizing P(x|y) = ∏_j P(x_j|y), assuming conditional independence of features given the class. With multinomial likelihood, P(x_j|y) = θ_{j,y}^{x_j} where θ_{j,y} are word-given-class probabilities estimated via maximum likelihood with Laplace smoothing. The decision rule is argmax_y P(y|x) = argmax_y log P(y) + Σ_j x_j log θ_{j,y}.

Logistic Regression Approach

Logistic regression models P(y=1|x) = σ(w^T x + b) where σ is the sigmoid function. Unlike Naive Bayes, it makes no independence assumptions, learning weights w directly via maximum likelihood. The loss function is L = -(1/n)Σ_i[y_i log ŷ_i + (1-y_i) log(1-ŷ_i)], optimized via gradient descent. Decision boundary is the line w^T x + b = 0 in the original feature space.

Feature Engineering & Preprocessing

Raw text requires preprocessing: tokenization (splitting into words), lowercasing, removing punctuation, lemmatization (reducing words to base forms), and stop word removal (eliminating common but uninformative words like "the," "a"). TF-IDF weighting assigns weights w_j = tf_j × idf_j where tf_j is term frequency and idf_j = log(N/n_j) is inverse document frequency, down-weighting words appearing in many documents and upweighting rare informative words.

Model Comparison & Deployment

Both models achieve 95%+ accuracy on standard benchmarks, but with tradeoffs: Naive Bayes trains very quickly, interprets easily (word-specific log-odds clearly indicate spam indicators), but may underfit with limited data due to independence assumptions. Logistic regression requires more computation but fits the boundary more flexibly, achieving marginal accuracy gains. In production, precision-recall tradeoffs matter: adjusting decision threshold to minimize false positives (legitimate emails marked spam) may accept more false negatives (spam reaching inbox), prioritizing user experience.

The classical bias-variance tradeoff predicts test error decreases as model complexity increases (variance decreases), reaching minimum near the interpolation threshold where training error becomes zero, then increases as overfitting dominates. Empirically, deep neural networks often violate this prediction: beyond the interpolation threshold, test error initially rises but then descends again, creating a double-descent risk curve with two minima.

The interpolation threshold occurs when model capacity equals effective number of parameters, allowing the model to fit all training data perfectly. In neural networks, this threshold depends on network width, depth, and dataset size. The classic U-shaped bias-variance curve predicts catastrophic overfitting beyond this point, yet double descent shows improvement. This phenomenon reflects implicit regularization: SGD's stochasticity acts as regularization, preventing pathological memorization even when training error is zero. The second descent indicates that higher-capacity models actually generalize better, seeming to contradict classical theory.

Implicit Regularization via SGD

Stochastic gradient descent, despite using no explicit regularization, exhibits implicit regularization properties. The stochastic noise from mini-batch sampling effectively regularizes solutions, selecting among multiple solutions fitting the training data the one with properties favorable for generalization (e.g., solutions with small norm). This implicit regularization explains benign overfitting: the model fits all training data while still generalizing well because SGD guides it toward solutions that generalize despite achieving zero training error.

Benign vs Harmful Overfitting

Benign overfitting occurs when the model achieves zero training error yet maintains good test performance—the new normal in deep learning. Harmful overfitting, the classical concern, occurs when training error is zero but test error is high due to fitting noise. The double descent phenomenon suggests that with sufficient model capacity and proper optimization, benign overfitting becomes the typical regime. This explains why modern deep networks with millions of parameters often generalize well despite vastly exceeding training set size.

Empirical Verification

Exploring double descent requires training networks of increasing width on fixed training sets, plotting test error vs. width. Clear visualization shows the classical U-shape (descent to interpolation threshold, then increase) giving way to the second descent at higher widths. The peak of the double descent—maximum test error—represents the most dangerous regime where the model is complex enough to overfit but not regularized enough to recover. Understanding this phenomenon guides practitioners toward either models complex enough to achieve the second descent or explicit regularization preventing entry into the high-error interpolation region.

Problem Set 4 integrates theory and practice, demonstrating that modern machine learning rests on solid mathematical foundations. KL divergence is not merely academic abstraction but grounds the cross-entropy loss ubiquitous in deep learning. When implementing MNIST training loops, students directly optimize cross-entropy, experiencing first-hand the connection between information-theoretic principles and algorithmic practice. This concrete experience deepens mathematical understanding far more effectively than theory alone.

The comparative study of Naive Bayes and logistic regression on spam data illuminates fundamental machine learning dichotomies: generative vs. discriminative modeling, parametric distributions vs. learned boundaries, interpretability vs. accuracy. Neither approach dominates universally; the choice depends on data characteristics, interpretability requirements, and computational constraints. This flexibility reflects how mature machine learning practice involves toolkit mastery rather than universal principles.

Challenging Conventional Wisdom

Double descent is perhaps the most intellectually valuable outcome, challenging the classical bias-variance intuition that shapes much of machine learning pedagogy. That highly complex models can generalize better than moderately sized ones contradicts age-old wisdom and forces reconsideration of how we think about overfitting and regularization. The realization that implicit regularization from SGD prevents pathological overfitting suggests that algorithm design matters as much as model selection.

Practical Implications

Understanding these concepts has immediate practical value: (1) Recognizing when models interpolate training data yet generalize well, (2) Choosing between generative and discriminative approaches based on problem structure, (3) Implementing neural networks correctly with proper optimization and evaluation, (4) Interpreting model failures through confusion matrices and feature analysis. These skills transfer broadly to any machine learning application.

Future Directions

The phenomena explored in PS4 connect to active research: implicit bias of gradient descent, generalization bounds in high-dimensional settings, understanding when interpolation succeeds, and optimal model complexity selection. Students completing this assignment successfully have achieved sophisticated understanding suitable for advanced coursework, research, or professional practice in machine learning.

Stanford CS229 Course Materials

Stanford CS229: Machine Learning — Official course page with lectures on information theory, neural networks, and loss functions. Weeks 5-7 materials directly cover Problem Set 4 topics.

Information Theory & KL Divergence

Wikipedia: KL Divergence — Comprehensive treatment of KL divergence, asymmetry, non-negativity, relationship to relative entropy, and applications.

Wikipedia: Cross-Entropy — Definition, relationship to KL divergence and maximum likelihood, and applications in machine learning.

Wikipedia: Information Theory — Foundational concepts including entropy, mutual information, and channel capacity essential for understanding KL divergence.

Neural Networks & Deep Learning

Wikipedia: Artificial Neural Network — Overview of neural network architecture, layers, activation functions, and backpropagation.

Wikipedia: Backpropagation — Detailed explanation of backpropagation algorithm for computing gradients in neural networks.

Wikipedia: Convolutional Neural Networks — Architecture and design of CNNs, particularly relevant for MNIST image classification.

Generalization & Double Descent

Wikipedia: Bias-Variance Tradeoff — Classical theory of bias-variance decomposition and its relationship to model complexity and generalization.

Wikipedia: Overfitting — Definition, causes, and classical mitigation strategies including regularization and early stopping.

Text Classification & Naive Bayes

Wikipedia: Naive Bayes Classifier — Theory and application of Naive Bayes for text classification, conditional independence assumption, and interpretability.

Wikipedia: Bag-of-Words Model — Overview of BoW representation for text, feature extraction, and applications.

Comprehensive References

The Elements of Statistical Learning (ESL) - Free PDF — Authoritative reference covering neural networks, regularization, and statistical learning theory. Chapters 7-11 are particularly relevant to PS4.

Deep Learning by Goodfellow, Bengio, Courville — Comprehensive modern textbook on deep learning, covering neural networks, optimization, and regularization extensively.