Stanford CME295 Transformers & LLMs | Autumn 2025 | Lecture 2 - Transformer-Based Models & Tricks

This lecture teaches Principal Component Analysis (PCA), a fundamental technique in machine learning for reducing the number of features while keeping as much useful information as possible. The instructor presents PCA from three equivalent perspectives: finding the best low-dimensional representation that minimizes reconstruction error, finding directions in which the data varies the most (maximal variance), and finding directions that lead to the best reconstruction after projecting down and back up. Although these perspectives sound different, the lecture shows they lead to the exact same solution using linear algebra, specifically eigenvalues and eigenvectors of a matrix built from the data.

The lecture starts with a simple setup: you have n data points x1 through xn in d-dimensional space (for example, each xi could be a 100-dimensional vector). The goal is to find a lower-dimensional space, such as a line (1D) or a plane (kD), that captures the essence of the data. The instructor first handles the 1D case to build intuition. You pick a direction u with unit length and project each data point onto that direction, producing a single number u^T xi. Then you reconstruct back to the original space by multiplying that number by u, giving (u^T xi)u, which lies on the line defined by u. The key question is: which u gives the smallest total squared reconstruction error across all points?

By expanding the squared error ||xi − (u^T xi)u||^2, simplifying, and focusing on terms that involve u, the lecture shows that minimizing the reconstruction error is equivalent to maximizing the sum of squared projections ∑(u^T xi)^2. This objective can be written compactly as u^T C u, where C = ∑ xi xi^T. The problem becomes a constrained maximization: maximize u^T C u subject to u^T u = 1. Using Lagrange multipliers, you take the derivative, set it to zero, and find C u = λ u. This is the eigenvector equation, so the best u is an eigenvector of C, and the best one is the eigenvector with the largest eigenvalue.

Next, the instructor connects this to the variance view. If you project data onto u, the variance of the projected values u^T xi (assuming the data are zero-mean for simplicity) equals u^T C u. Therefore, the direction that maximizes variance is exactly the same direction that minimizes reconstruction error. In simple words, the line along which the data spreads out the most is also the line that gives you the least total squared distance when you drop perpendiculars from points to that line. This equality of goals makes PCA easy to reason about from different angles.

The lecture then generalizes from one dimension to k dimensions. Instead of one direction u, you now select k orthonormal directions u1, ..., uk. These are the eigenvectors of C associated with the k largest eigenvalues. Your low-dimensional code for a point x becomes [u1^T x, u2^T x, ..., uk^T x], and the reconstruction is the sum over j of (u_j^T x) u_j. This gives the best k-dimensional subspace in the sense of both variance captured and reconstruction accuracy.

Throughout, the instructor keeps the math clean and geometric: projection is like dropping a perpendicular to a line or plane; reconstruction is the foot of that perpendicular; and the best directions are those where the data varies most. The matrix C is like a covariance matrix when the data are zero-mean (the lecture uses C = ∑ xi xi^T without assuming zero mean to simplify setup). C is symmetric, so it has real eigenvalues and orthogonal eigenvectors, which guarantees a stable solution. The top eigenvector gives the first principal component; the next eigenvector gives the second principal component, and so on.

By the end, you understand how to compute PCA: build the matrix C, find its eigenvectors and eigenvalues, sort by eigenvalue size, and choose the top k eigenvectors as your principal components. You also understand why this works: these directions maximize variance, minimize reconstruction error, and provide the best possible reconstruction after projecting down and back up. The lecture is suitable for learners who know basic linear algebra (vectors, dot products, matrices, eigenvectors, eigenvalues) and basic optimization ideas (like Lagrange multipliers). After this lecture, you will be able to apply PCA to compress data, visualize high-dimensional datasets, denoise signals by keeping the most important directions, and create strong features for downstream machine learning tasks.

1. Overall architecture/structure of the PCA problem

Goal and data flow:

• Input: n data points x1, x2, …, xn in R^d (each is a column vector with d numbers).
• Choose a target dimension k (1 ≤ k ≤ d). For intuition, start with k = 1.
• Pick direction(s) u (for 1D) or U = [u1, …, uk] (for kD), where each u_j is a unit vector and the set is orthonormal (perpendicular and length 1).
• Project each x_i onto these directions to get low-dimensional coordinates: for 1D, z_i = u^T x_i; for kD, z_i = U^T x_i (a k-dimensional vector).
• Optionally reconstruct back to the original space: for 1D, x̂_i = (u^T x_i)u; for kD, x̂_i = U(U^T x_i).
• Objective: choose u or U that best preserves information. In this lecture, “best” is shown to be equivalent across three views: (a) minimum reconstruction error, (b) maximum variance, and (c) best reconstruction after down-and-up mapping.

Key matrix:

• Define C = ∑_{i=1}^n x_i x_i^T. If data are centered (mean zero), C is proportional to the covariance matrix, which directly measures spread.
• C is symmetric (C^T = C) and positive semidefinite (v^T C v ≥ 0 for any vector v). Thus, its eigenvalues are real and nonnegative, and it has an orthonormal basis of eigenvectors.

What PCA computes:

• PCA computes eigenvectors and eigenvalues of C and selects the top k eigenvectors (those with the largest eigenvalues). These eigenvectors are the principal components.
• The projection coordinates are obtained by dot products (u_j^T x for each component j). The reconstruction from k components is the sum of component contributions: x̂ = ∑_{j=1}^k (u_j^T x) u_j.

1. Derivation and implementation details for the 1D case

Step A: Define the reconstruction error

• For a single direction u with ||u|| = 1, the reconstructed version of x_i is x̂_i = (u^T x_i)u. The squared reconstruction error for x_i is ||x_i − x̂_i||^2.
• Total error across the dataset: E(u) = ∑_{i=1}^n ||x_i − (u^T x_i)u||^2.

Step B: Expand the squared error

• Expand ||x_i − (u^T x_i)u||^2 = (x_i − (u^T x_i)u)^T (x_i − (u^T x_i)u).
• Multiply out: x_i^T x_i + (u^T x_i)^2 u^T u − 2 x_i^T ((u^T x_i)u).
• Since ||u|| = 1, u^T u = 1, and u^T x_i is a scalar equal to its transpose. The middle term simplifies to (u^T x_i)^2. The third term simplifies to 2(u^T x_i)^2.
• Thus, per point: ||x_i − (u^T x_i)u||^2 = x_i^T x_i − (u^T x_i)^2.
• Summing over i: E(u) = ∑ x_i^T x_i − ∑ (u^T x_i)^2.

Step C: Turn minimization into maximization

• The term ∑ x_i^T x_i does not depend on u, so minimizing E(u) is equivalent to maximizing ∑ (u^T x_i)^2.
• Write ∑ (u^T x_i)^2 as u^T [∑ x_i x_i^T] u = u^T C u.
• The 1D PCA problem is: maximize u^T C u subject to u^T u = 1.

Step D: Solve with Lagrange multipliers

• Form the Lagrangian: L(u, λ) = u^T C u − λ(u^T u − 1).
• Take gradient with respect to u: ∇_u L = 2 C u − 2 λ u. Set to zero: C u = λ u.
• This is the eigenvalue equation. Valid solutions are eigenvectors u of C; λ is the corresponding eigenvalue.
• Evaluate objective at an eigenvector u with unit norm: u^T C u = u^T (λ u) = λ (u^T u) = λ. So to maximize u^T C u, pick the eigenvector with the largest eigenvalue.

Interpretation:

• The top eigenvector points along the direction where the dataset’s projected values have the largest sum of squares, i.e., the largest variance if the data are centered. Geometrically, it is the line that yields the smallest total squared perpendicular distances from points to that line (best 1D reconstruction).

1. Variance perspective in detail

Definition of variance of projections:

• For centered data (mean of x_i is zero), the variance of the projected values z_i = u^T x_i is Var(z) = (1/n) ∑ (u^T x_i)^2.
• Up to a constant factor 1/n, this is exactly u^T C u. Therefore, maximizing variance is equivalent to maximizing u^T C u.

Equivalence of goals:

• Because the reconstruction-error objective reduces (modulo a constant) to −u^T C u, minimizing error is equivalent to maximizing variance. Hence, both views choose the same direction u: the top eigenvector of C.

1. Extension to k dimensions

Set up:

• Choose k orthonormal vectors U = [u1, u2, …, uk] in R^d with U^T U = I_k. Project each x_i to z_i = U^T x_i (a k×1 vector). Reconstruct back as x̂_i = U z_i = U(U^T x_i).

Reconstruction error:

• Total error is E(U) = ∑ ||x_i − U(U^T x_i)||^2. This equals the sum of squared distances from points to the k-dimensional subspace spanned by the columns of U.

Optimal U:

• The optimal U that minimizes E(U) (equivalently, maximizes the sum of variances captured) is given by choosing u1,…,uk as the eigenvectors of C with the largest eigenvalues λ1 ≥ λ2 ≥ … ≥ λk.
• These eigenvectors are mutually orthogonal and define the principal subspace.

Variance captured and ordering:

• The value u_j^T C u_j equals λ_j. The total variance captured by the k-dimensional subspace is the sum of the top k eigenvalues ∑{j=1}^k λ_j (up to constant scaling if using covariance). The reconstruction error equals the sum of the remaining eigenvalues ∑{j=k+1}^d λ_j.

1. Tools/libraries and computation notes

Mathematical tools:

• Eigen-decomposition: For a symmetric matrix C, we compute eigenpairs (λ_j, u_j) satisfying C u_j = λ_j u_j, sorted by λ_j.
• Orthonormality: The eigenvectors of a symmetric C can be chosen orthonormal. This gives U^T U = I_k and simplifies projection and reconstruction.

Implementation approach (language-agnostic):

• Step 1: Arrange your data points x_i as column vectors in a matrix X of size d×n.
• Step 2: (Optional but common) Center the data by subtracting the mean vector μ = (1/n) ∑ x_i from each x_i to get X_centered.
• Step 3: Build C = ∑ x_i x_i^T. If using centered data, C = X_centered X_centered^T.
• Step 4: Compute the eigenvalues and eigenvectors of C. Many numerical libraries do this (e.g., NumPy’s linalg.eigh for symmetric matrices).
• Step 5: Sort eigenvalues in descending order and take the top k eigenvectors U_k = [u1,…,uk].
• Step 6: To project a new point x, compute z = U_k^T x. To reconstruct, compute x̂ = U_k z.

Important parameters and meanings:

• k: the target dimension. Larger k captures more variance but uses more numbers per data point. k = 1 gives a single best direction; k = d recovers the original data exactly.
• Unit norm constraints: Each u_j must have length 1 to make projections comparable and to ensure U^T U = I.

1. Step-by-step implementation guide (follow-along)

• Step 1: Collect data as a list of vectors x1,…,xn in R^d.
• Step 2: Compute the mean μ = (1/n) ∑ x_i (optional but recommended). Form centered data y_i = x_i − μ.
• Step 3: Build C = ∑ y_i y_i^T (or if skipping centering, use x_i instead, as in the lecture’s notation). In matrix form with centered data: C = Y Y^T, where Y = [y1 … yn].
• Step 4: Solve the eigenvalue problem C u = λ u. Use a symmetric eigen-solver. You get eigenvalues λ1 ≥ λ2 ≥ … ≥ λd and corresponding unit eigenvectors u1,…,ud.
• Step 5: Choose k. Pick principal components U_k = [u1,…,uk].
• Step 6: Encode each data point with z_i = U_k^T y_i (or U_k^T x_i if not centered). This gives k numbers per point.
• Step 7: Reconstruct if desired: ŷ_i = U_k z_i; add back μ to get x̂_i = ŷ_i + μ if you centered.
• Step 8: Evaluate quality: the total variance captured is ∑{j=1}^k λ_j, and the leftover variance is ∑{j=k+1}^d λ_j.

1. Tips and warnings

• Centering: While the lecture defined C without requiring zero mean, in practice center your data so that C describes pure variance. If you don’t, mean shifts can inflate directions unfairly.
• Scaling: If features have very different scales (like centimeters vs. kilometers), consider normalizing before PCA so one feature doesn’t dominate variance just due to units.
• Numerical stability: Use symmetric eigen-solvers (like eigh) on C. For very high dimensions with many fewer samples (d >> n), computing eigenvectors of the n×n matrix X^T X and back-transforming can be faster.
• Choosing k: Look at eigenvalues; keep components until the marginal gain becomes small. This balances compression and information retained.
• Interpretation: PCA finds directions of maximum variance, not necessarily directions that best separate classes. Use it as a preprocessing or visualization tool, not a classifier by itself.
• Orthogonality: Ensure the chosen eigenvectors are orthonormal. Most libraries return normalized, orthogonal vectors for symmetric matrices, but verify U^T U ≈ I numerically.
• Reconstruction check: After projection and reconstruction, errors should be perpendicular to the chosen subspace. If not, re-check your projection formula.

1. Why the approaches are equivalent (intuitive recap)

• Minimizing reconstruction error: You want the line/plane that hugs the data cloud most closely, so the perpendicular distances are as small as possible on average.
• Maximizing variance: You want the direction where the shadows of points (their projections) are as long as possible overall. Longer shadows imply the line runs along the cloud’s long axis.
• Algebra ties them together: Expanding the squared distance cancels constants and reveals the same u^T C u structure as the variance. The Lagrange multiplier trick lands on the eigenvector condition, sealing the equivalence.

1. Geometric properties and outcomes

• First principal component (PC1): Points along the axis of maximum spread. Captures the largest portion of total variance.
• Second principal component (PC2): Orthogonal to PC1 and captures the next most spread. In 2D, PC1 and PC2 form a rotated coordinate system aligned with the data’s ellipse.
• Higher components: Each new component is perpendicular to all previous ones and explains the next slice of variance. Stopping after k gives a k-dimensional subspace.
• Reconstruction: The PCA reconstruction is always the orthogonal projection of x onto the chosen subspace. The error x − x̂ is orthogonal to that subspace.

1. Practical example scaffolding (no code needed)

• Imagine data that form a cigar-shaped cloud in 3D. PC1 runs along the cigar’s length. Projecting onto PC1 collapses each point to a single coordinate along that length. Adding PC2 captures the cigar’s minor width, and reconstruction with PC1+PC2 gives a flat, near-cigar sheet approximation in 3D.

This technical walkthrough mirrors the lecture’s derivations: starting with reconstruction error, simplifying to a matrix quadratic form, solving with eigen-decomposition under a unit-length constraint, understanding projections as variance, and generalizing from 1D to kD. It also adds clear, stepwise guidance so you can implement PCA on your own data using the exact formulas discussed.

This lecture built a complete, unified understanding of Principal Component Analysis (PCA) by showing three perspectives that lead to the same answer. First, PCA as minimizing reconstruction error: choose a line or k-dimensional subspace so that the total squared perpendicular distance from points to that subspace is as small as possible. Second, PCA as maximizing variance: pick directions where the projections of points spread out the most. Third, PCA as best reconstruction after down-and-up mapping: the same directions also give the most faithful reconstructions when you compress to k numbers and then expand back.

The heart of the math uses a single matrix C = ∑ x_i x_i^T. The 1D problem reduces to maximizing u^T C u with u being a unit vector, which is solved by the eigenvector of C with the largest eigenvalue. The lecture’s derivation via Lagrange multipliers gives the eigenvector equation C u = λ u, and evaluating the objective at an eigenvector shows it equals λ, making the selection rule obvious. Extending to k dimensions, you take the top k eigenvectors, which are orthonormal, and use them to define the principal subspace. Your compressed code for a point is its dot products with those eigenvectors, and reconstruction is their weighted sum.

Practically, PCA is straightforward to implement and broadly useful. Arrange your data, center it if desired, build C, compute eigenpairs, sort, and select k. The principal components are the eigenvectors with the largest eigenvalues, and they capture the most structure in the data. The method is unsupervised and serves as a powerful tool for compression, denoising, visualization, and preprocessing. Orthogonality guarantees clean, non-overlapping contributions from each component, and the eigenvalues quantify how much information each component holds.

To practice, try PCA on a small 2D dataset and visualize the principal axes, or on image patches to see how a few components can describe complex patterns. Next steps include exploring how to choose k by examining eigenvalues and understanding extensions like whitening or probabilistic PCA. The core message to remember is simple and strong: the same directions that minimize reconstruction error also maximize variance, and you find them by taking the top eigenvectors of ∑ x_i x_i^T. With this, you can confidently apply PCA to real-world datasets and use it as a foundational building block in your machine learning toolkit.