Stanford CS329H: Machine Learning from Human Preferences | Autumn 2024 | Mechanism Design

This lesson builds a solid foundation in basic machine learning by focusing on the simplest and most essential algorithms. It starts by clarifying what a machine learning system is: data as input-output pairs (X and Y), a model f(x;θ) with parameters θ, a loss function to measure how wrong predictions are, and an optimizer to tune the parameters to reduce the loss. The lecture quickly reviews the three main learning settings—supervised learning (with labeled targets), unsupervised learning (with no labels), and reinforcement learning (with rewards)—and then dives deeply into supervised learning, with short but clear coverage of unsupervised learning at the end.

Within supervised learning, two problem types are highlighted: regression and classification. Regression predicts continuous values (like house prices), and the simplest approach is linear regression, which fits a straight line to data when there is one input, or a flat plane/linear function when there are multiple inputs (features). The model is f(x; w, b) = w^T x + b. To learn the parameters w and b, you minimize mean squared error (MSE), which averages the squares of the prediction errors. The optimizer of choice here is gradient descent, an iterative method that updates parameters in steps proportional to how much the loss changes with respect to them (their gradients). An example with two data points, (1,1) and (2,2), demonstrates how gradient descent starts with w=0, b=0 and progressively adjusts them until the loss stops decreasing—this is called convergence.

The lecture also answers a common question: what if the relationship isn’t a straight line? Linear regression won’t fit well if the pattern is curved or complex. In those cases, we can use nonlinear models such as polynomial regression, decision trees, or neural networks. The point is to understand linear regression thoroughly as a baseline, because it’s interpretable, fast to run, and a building block for more advanced methods.

For classification, the lesson introduces logistic regression. The idea is similar to linear regression, but instead of directly predicting a number, the model produces a probability by passing a linear score through the sigmoid function σ(z)=1/(1+e^(−z)). This gives outputs between 0 and 1 and allows easy thresholding (e.g., classify as 1 if probability ≥ 0.5). The training objective switches to cross-entropy (also called negative log-likelihood), which heavily penalizes confident wrong predictions and encourages correct high-confidence ones. The gradient-based updates look similar to linear regression but use the predicted probabilities in the derivatives. The instructor uses a tiny dataset, (1,0) and (2,1), to show how learning proceeds from initial guesses to sensible probabilities that separate the classes.

Finally, the lecture introduces unsupervised learning through k-means clustering, which finds structure in data without labels by grouping points into k clusters. K-means alternates between two steps: assignment (send each point to its nearest centroid) and update (move each centroid to the mean of its assigned points). The objective is to minimize the within-cluster sum of squares (WCSS): the total squared distances from points to their centroids. Choosing k is important: the elbow method looks for a bend in the WCSS curve where adding more clusters yields diminishing returns, and the silhouette score compares within-cluster tightness to separation from other clusters, preferring values closer to 1. A 2D point cloud example with k=2 walks through random initialization, assignment, update, and convergence.

By the end, you will understand how to define problems as regression or classification, select linear or logistic regression as strong baselines, compute losses (MSE and cross-entropy), perform gradient descent updates, and run k-means to discover patterns without labels. You’ll also know how to think about hyperparameters like learning rate and k, plus when to consider moving beyond linear models. This knowledge sets the stage for more advanced algorithms like decision trees and neural networks, which build on the same ideas of models, losses, and optimization.

1. Overall Architecture/Structure

• The general machine learning pipeline has four key parts: data, model, loss, and optimizer. Data consists of inputs X and possibly labels Y; each example (x_i, y_i) teaches the model about a small piece of the world. The model f(x;θ) encodes our assumptions about how inputs relate to outputs—linear, logistic, or otherwise—using parameters θ that we will learn. The loss L(θ) measures how far the model’s predictions are from the target pattern; it is designed to be small when the model does well and large when it fails. The optimizer updates θ step-by-step to reduce L, gradually improving performance until the loss stabilizes (converges).

• Supervised learning splits into regression and classification. In regression, outputs are real-valued numbers. In classification, outputs are discrete class labels (e.g., {0,1}). Two canonical models anchor these tasks: linear regression for regression and logistic regression for binary classification. Both share a linear core (w^T x + b), but logistic regression wraps the linear score with a sigmoid function to interpret it as a probability.

• Unsupervised learning looks only at X and finds structure like clusters. The classic method is k-means clustering, which alternates between assigning points to their nearest centroid and moving centroids to the mean of their assigned points. Its goal is to minimize within-cluster sum of squares (WCSS), creating tight, well-separated groups when possible. Because there are no labels, evaluation relies on internal measures (like WCSS or silhouette) and domain sense.

1. Code/Implementation Details (conceptual and step-by-step) A. Linear Regression with MSE and Gradient Descent

• Model: f(x; w, b) = w^T x + b. Inputs x can be a single number (e.g., size) or a vector (size, bedrooms, age). w is a vector of the same dimension as x. b is a scalar offset.
• Loss: MSE = (1/n) Σ (y_i − (w^T x_i + b))^2. This squares each error to emphasize large mistakes and ensures the loss is smooth, aiding optimization.
• Gradients: Using calculus (chain rule), ∂MSE/∂w = −(2/n) Σ x_i (y_i − ŷ_i) and ∂MSE/∂b = −(2/n) Σ (y_i − ŷ_i), where ŷ_i = f(x_i). Intuitively, if predictions are too low for positive x_i, we should increase w to raise ŷ.
• Update Rules: Choose a learning rate η. Iteratively update w ← w − η ∂MSE/∂w and b ← b − η ∂MSE/∂b until the loss change is tiny (or a fixed number of steps is reached).
• Example Walkthrough: With data points (x,y) = (1,1) and (2,2), initialize w=0, b=0. Predictions are both 0; errors are 1 and 2; gradients point toward increasing w and b. After several iterations, the line y = w x + b tilts toward y = x and shifts slightly so MSE shrinks. Convergence happens when updates barely change w and b and the MSE plateaus.
• Practical Notes: Standardizing features (mean 0, std 1) often helps. Batch gradient descent uses all data per update; stochastic gradient descent (SGD) uses one example; mini-batch uses small batches—SGD variants can be faster and escape shallow traps. For linear regression, there’s also a closed-form solution (normal equation), but gradient descent is more general and scales better with many features.

B. Logistic Regression with Cross-Entropy and Gradient Descent

• Model: f(x; w, b) = σ(z) with z = w^T x + b and σ(z) = 1 / (1 + e^(−z)). This maps any real z to (0,1), naturally interpreted as P(y=1 | x).
• Loss: Cross-entropy L = −(1/n) Σ [ y_i log f(x_i) + (1 − y_i) log (1 − f(x_i)) ]. If y=1 and f is near 1, the loss is small; if y=1 and f is near 0, the loss is huge, strongly penalizing confident mistakes.
• Gradients: ∂L/∂w = −(1/n) Σ x_i (y_i − f(x_i)) and ∂L/∂b = −(1/n) Σ (y_i − f(x_i)). The term (y_i − f(x_i)) measures the prediction error in probability space: positive if the model underestimates P(y=1), negative if it overestimates.
• Update Rules: w ← w − η ∂L/∂w, b ← b − η ∂L/∂b. Like linear regression, you repeat these updates until convergence.
• Example Walkthrough: For points (1,0) and (2,1), w=0,b=0 ⇒ z=0 for both ⇒ f=0.5 for both. Loss is moderate; gradients push f(1) downward (toward 0) and f(2) upward (toward 1). After iterative updates, predicted probabilities separate: f(1) < 0.5 and f(2) > 0.5, matching labels.
• Thresholding: Typically, classify as 1 if f(x) ≥ 0.5, else 0. For imbalanced classes or special costs, you can adjust the threshold.
• Practical Notes: Feature scaling helps convergence. Regularization (L2) can be added to discourage overly large weights (not covered in the core example but common in practice). Logistic regression is a strong, interpretable baseline for many binary classification tasks.

C. K-Means Clustering (Unsupervised)

• Goal: Partition n data points into k clusters to minimize WCSS. Each cluster has a centroid μ_j (a point in the same space as x).
• Algorithm Steps:
  1. Initialize: Pick k initial centroids, often randomly from the data points.
  2. Assignment: For each point x_i, find nearest centroid μ_j by Euclidean distance and assign x_i to cluster j.
  3. Update: For each cluster j, recompute μ_j as the mean of its assigned points.
  4. Repeat: Alternate assignment and update until assignments stabilize or centroids move less than a small tolerance.
• Example Walkthrough: For a set of 2D points with k=2, start with two random centroids. On the first pass, points are split roughly into two groups by which centroid is closer. The centroids shift to the centers of these groups; assignments may change next round. After a few rounds, centroids and memberships stop changing—convergence.
• Choosing k: • Elbow Method: Compute WCSS for k=1,2,3,...; plot WCSS vs. k and look for the elbow where adding clusters yields diminishing returns. • Silhouette Score: For each point, compute how well it fits in its cluster vs. the next best cluster; average across points; pick k with higher scores (closer to 1 is better).
• Practical Notes: Different random initializations can lead to different final clusters; run k-means multiple times and keep the best WCSS. K-means works best for compact, roughly spherical clusters and is sensitive to feature scaling; standardize features to equalize influence.

1. Tools/Libraries Used

• Although no specific coding libraries are required to understand these algorithms, common tools include: • Python + NumPy: For vectorized math and efficient array operations. • scikit-learn: Offers LinearRegression, LogisticRegression, and KMeans with reliable defaults and utilities like train/test splits and scaling. • Visualization (matplotlib): For scatter plots, best-fit lines, probability curves, and WCSS elbow plots.
• Installation basics: pip install numpy scikit-learn matplotlib. Usage examples: fit() to train, predict() to infer, score() or custom metrics to evaluate. Even if you implement from scratch, these libraries help validate your results.

1. Step-by-Step Implementation Guide A. Linear Regression (from scratch)

• Step 1: Prepare Data. Arrange inputs in a matrix X of shape (n, d) and targets y in a vector (n,). Optionally standardize columns of X.
• Step 2: Initialize Parameters. Set w (d,) and b (scalar) to zeros or small random values.
• Step 3: Define Prediction. y_hat = X @ w + b.
• Step 4: Compute Loss. mse = mean((y − y_hat)^2).
• Step 5: Compute Gradients. grad_w = −(2/n) X^T (y − y_hat); grad_b = −(2/n) sum(y − y_hat).
• Step 6: Update. w ← w − η grad_w; b ← b − η grad_b.
• Step 7: Repeat. Loop Steps 3–6 until mse changes by less than a tiny threshold or max epochs reached.
• Step 8: Evaluate and Visualize. Plot data and fitted line (for 1D); compute MSE on held-out data if available.

B. Logistic Regression (from scratch)

• Step 1: Prepare Data. X (n,d), y in {0,1}. Standardize X.
• Step 2: Initialize. w (d,), b scalar to zeros or small random values.
• Step 3: Prediction. z = X @ w + b; f = 1/(1+exp(−z)).
• Step 4: Loss. ce = −mean( y*log(f) + (1−y)*log(1−f) ). Use small eps to avoid log(0).
• Step 5: Gradients. grad_w = −(1/n) X^T (y − f); grad_b = −(1/n) sum(y − f).
• Step 6: Update. w ← w − η grad_w; b ← b − η grad_b.
• Step 7: Repeat. Until loss stabilizes.
• Step 8: Threshold & Evaluate. Predict class = (f ≥ 0.5). Measure accuracy and optionally precision/recall if classes are imbalanced.

C. K-Means (from scratch)

• Step 1: Choose k and Initialize. Randomly pick k points from X as initial centroids μ.
• Step 2: Assignment. For each x_i, compute distances to all μ_j and assign to argmin_j distance(x_i, μ_j).
• Step 3: Update. For each cluster j, set μ_j to the mean of its assigned points (if a cluster becomes empty, reinitialize its centroid to a random point).
• Step 4: Repeat Steps 2–3 until assignments no longer change or the maximum centroid shift is below a threshold.
• Step 5: Evaluate. Compute WCSS; try multiple initializations and select the best result; use elbow/silhouette to reconsider k.

1. Tips and Warnings

• Feature Scaling: Standardize features for faster, more stable convergence for both gradient descent and k-means. When features have different scales, distances and gradients can be dominated by large-scale features.
• Learning Rate Tuning: Start with a modest η; if loss increases or oscillates, reduce η; if progress is too slow, increase it slightly. Use learning curves to visualize loss vs. iteration.
• Initialization Sensitivity: w and b can start at zero for convex problems like linear/logistic regression; k-means centroids should be initialized carefully (k-means++ is popular) and run multiple times.
• Stopping Criteria: Set sensible tolerances for change in loss (regression/classification) or centroid movement (k-means). Overtraining isn’t typical for convex losses without regularization, but unnecessary iterations waste time.
• Data Quality: Outliers can skew MSE and centroids; consider robust scaling or trimming. Noisy labels harm logistic regression; verify label quality.
• Model Fit: If linear regression underfits, consider nonlinear features; if logistic regression struggles, check for overlapping classes and feature engineering opportunities. Always validate with a held-out set when possible.
• Interpretability: Linear and logistic models offer clear interpretations (weights as feature importance). Use them as baselines even when planning to try complex models later.

This lesson lays out the full machine learning loop using the simplest and most widely used models. It starts with the core building blocks—data, model, loss, and optimizer—and shows how they fit together to turn examples into a trained function f(x;θ). For regression, linear regression models a straight-line relationship and uses mean squared error as the objective, with gradient descent to find the best slope and intercept. For classification, logistic regression turns a linear score into a probability with the sigmoid, and cross-entropy pushes predictions to be both correct and appropriately confident. In unsupervised settings, k-means finds clusters by alternating assignment and update steps to minimize within-cluster squared distances.

Across all three, the same habits make learning effective: scale features, choose sensible hyperparameters (learning rate for gradient descent, k for k-means), initialize thoughtfully, and watch for convergence. The small, concrete examples—fitting a line to (1,1) and (2,2), separating labels for (1,0) and (2,1), and clustering 2D points with k=2—demonstrate the mechanics step by step. You also learned practical methods for model choice and evaluation: MSE for regression fit quality, cross-entropy for classification probabilities, and WCSS, elbow, and silhouette for clustering quality and k selection. If data cannot be captured by a straight line, consider nonlinear models like polynomial features, trees, or neural networks, which extend these same ideas.

To practice, implement linear and logistic regression with gradient descent on simple datasets, plot learning curves, and verify convergence. For k-means, try multiple k values, draw the elbow curve, and compute silhouette scores. These fundamentals will carry directly into more advanced methods like decision trees and neural networks, where you will again define a model, pick a loss, and use optimization to improve it. The core message is consistent: start simple, understand the basics deeply, and use these baselines to guide and benchmark more complex approaches.