Stanford CME295 Transformers & LLMs | Autumn 2025 | Lecture 8 - LLM Evaluation

This lecture explains kernel methods, a family of techniques that transform simple linear learning algorithms into powerful non-linear ones. The central idea is to map inputs into a higher-dimensional feature space where linear models can create curved decision boundaries when viewed back in the original space. This mapping is called a feature map and is typically written as φ(x). Although feature maps can be explicit, the lecture’s core insight is the kernel trick: rather than compute φ(x) directly, we use a kernel function k(x, x') that equals the dot product of φ(x) and φ(x') in the feature space. With this substitution, many linear algorithms can operate as if they had rich non-linear features, without ever building them explicitly.

The lecture starts with motivation: many real-world relationships are non-linear, so linear models are often too simple. Non-linear models can be powerful but are sometimes hard to train and can involve many parameters. Kernel methods bridge this gap: they allow the use of well-understood linear optimization techniques while achieving non-linear behavior through feature maps and kernels. The instructor demonstrates this with a 2D classification example: a straight line cannot separate two classes, but a circle can. By mapping (x1, x2) to a higher-dimensional set of features, and then learning a linear separator in that space, the model can produce a circular boundary in the original space.

Next, the instructor shows specific feature maps and their properties. One quadratic map φ(x) = [x1^2, x2^2, √2 x1 x2] has a special property: the dot product of feature vectors equals (x^T x')^2. This illustrates how some feature maps correspond to simple kernel functions like the degree-2 polynomial kernel. However, not all feature maps are equally helpful: with certain weights, the first map produced degenerate boundaries. Adding original linear terms to the map (φ(x) = [x1^2, x2^2, x1, x2]) allowed a circular decision boundary centered at (1/2, 1/2), showing the importance of expressiveness.

The lecture then formalizes the kernel trick. A kernel is any function k(x, x') that acts as an inner product in some (possibly infinite) feature space: k(x, x') = φ(x)^T φ(x'). By replacing every occurrence of a dot product in a linear algorithm with k(x, x'), we can run that algorithm in the implicit feature space. The polynomial kernel k(x, x') = (x^T x' + c)^d is a standard example that corresponds to including all polynomial terms up to degree d without explicitly constructing them. This avoids the computational blow-up that happens when enumerating all polynomial features at high degrees.

Next, the lecture covers when a function is a valid kernel. Mercer’s theorem provides the condition: k must be symmetric and positive semi-definite (PSD). In practical terms, given any set of inputs, the resulting kernel (Gram) matrix K with entries K_ij = k(x_i, x_j) must be PSD. The instructor also explains how to check PSD: ensure all eigenvalues are non-negative, or (for a symmetric matrix) check that all leading principal minors (determinants of upper-left submatrices) are non-negative.

The lecture then surveys common kernels. The Gaussian or radial basis function (RBF) kernel k(x, x') = exp(-||x - x'||^2 / (2σ^2)) depends only on the distance between points and corresponds to an infinite-dimensional feature map. The sigmoid kernel k(x, x') = tanh(α x^T x' + c) behaves like a two-layer neural network. Each kernel has parameters (e.g., σ for RBF, degree d for polynomial) that control model flexibility. Choice of kernel and parameters is guided by domain knowledge and experimentation.

Finally, the lecture introduces the representer theorem, a foundational result that explains why kernel methods work so broadly. For a large class of regularized learning problems, the solution can be written as f(x) = Σ_i α_i k(x, x_i). This reduces the problem of searching over an enormous space of functions to solving for a finite set of coefficients attached to training examples. It also justifies the kernel trick and shows how learning reduces to working with the kernel matrix.

The lecture targets students with some basic machine learning background—familiarity with linear models, dot products, and classification. By the end, learners should understand how to construct non-linear models by swapping dot products for kernels, how to choose and validate kernels, and how the representer theorem structures solutions. The session lays the groundwork for upcoming topics like kernel PCA and Gaussian processes, which build directly on the ideas introduced here.

1. Overall Architecture/Structure

• Goal: Convert a linear algorithm into a non-linear one by operating in an implicit feature space. The standard linear algorithm (e.g., a linear classifier) computes predictions like sign(w^T x). In kernel methods, we first map x to φ(x) in a higher-dimensional space H; then use a linear model there: sign(w^T φ(x)). When viewed in input space, this linear boundary becomes a non-linear boundary.
• Kernel Trick: Many linear algorithms depend on dot products between examples (x_i^T x_j). If we can compute an inner product in H without constructing φ(x), we can use a kernel function k(x, x') = φ(x)^T φ(x'). This replacement allows training and prediction using only kernel evaluations.
• Data Flow: Inputs x_1,...,x_n → compute K_ij = k(x_i, x_j) → solve the linear algorithm’s dual or kernelized form using K → obtain coefficients α (and possibly bias b) → predict on a new x by computing f(x) = Σ_i α_i k(x, x_i) (+ b if present). No explicit φ(x) is required.

1. Concrete Example: From Lines to Circles in 2D

• Linear failure: In 2D (x1, x2), a straight line might not separate classes (blue vs orange). Non-linear decision boundaries like circles succeed.
• First feature map: φ(x) = [x1^2, x2^2, √2 x1 x2]. Property: φ(x)^T φ(x') = x1^2 x1'^2 + x2^2 x2'^2 + 2 x1 x2 x1' x2' = (x^T x')^2. This map corresponds to the degree-2 polynomial kernel with c=0.
• Degenerate weights: With w = [1, 1, -1] or w = [1, 1, 1], the decision boundary derived from w^T φ(x) = 0 simplifies such that only (x1, x2) = (0, 0) satisfies it, giving a trivial boundary at the origin. This shows that even with a non-linear φ, some weight choices can be unhelpful.
• Improved feature map: φ(x) = [x1^2, x2^2, x1, x2]. With w = [-1, -1, 1, 1], w^T φ(x) = -x1^2 - x2^2 + x1 + x2 = 0, which rearranges to (x1 - 1/2)^2 + (x2 - 1/2)^2 = 1/2. This is a circle centered at (1/2, 1/2) with radius √(1/2). The added linear terms increases expressiveness so a useful non-linear boundary emerges.

1. Kernel Trick in Detail

• Core substitution: If an algorithm uses dot products, replace x^T x' with k(x, x') = φ(x)^T φ(x'). Training and prediction now rely on kernel evaluations. Example: In SVM dual, the objective involves x_i^T x_j; swapping in k(x_i, x_j) yields the kernel SVM.
• Why it helps: Explicitly constructing polynomial features up to degree d in D dimensions leads to O(D^d) features. This can be huge. The kernel trick computes the same effect with one function call to k, keeping complexity manageable.
• Polynomial kernel: k(x, x') = (x^T x' + c)^d. Interpretation: It includes all monomials of x and x' up to degree d with specific weighting determined by the binomial/multinomial expansions. Special case: c=0, d=2 gives (x^T x')^2, which corresponds to φ(x) = [x1^2, x2^2, √2 x1 x2] in 2D (and analogous terms in higher dimensions). Adding c introduces lower-order terms, effectively augmenting features with biases.

1. Valid Kernels and Mercer’s Theorem

• Mercer’s condition: A function k is a valid kernel if it is symmetric (k(x, x') = k(x', x)) and for any dataset {x_1,...,x_n}, the Gram matrix K with K_ij = k(x_i, x_j) is positive semi-definite (PSD). PSD means v^T K v ≥ 0 for all vectors v (equivalently all eigenvalues of K are ≥ 0).
• Intuition: PSD ensures k behaves like an inner product in some space H. Thus there exists a (possibly infinite-dimensional) φ such that k(x, x') = φ(x)^T φ(x').
• Checking PSD: (1) Eigenvalue test—compute eigenvalues of K; all must be ≥ 0 (numerically small negatives may appear due to rounding and can often be corrected by slight regularization). (2) Leading principal minors—if K is symmetric, check that determinants of top-left k×k submatrices are non-negative for all k. Either method verifies PSD in practice.

1. Common Kernels and Their Behavior

• Polynomial kernel: k(x, x') = (x^T x' + c)^d. Parameters: degree d (controls complexity) and constant c (shifts/augments features). Higher d increases flexibility but risks overfitting and numerical instability. Useful when interactions among features matter globally.
• Gaussian (RBF) kernel: k(x, x') = exp(-||x - x'||^2 / (2σ^2)). Parameter σ (width) controls locality. Small σ makes similarity drop off quickly, focusing on very local patterns (risk: overfitting). Large σ smooths similarity broadly, capturing global trends (risk: underfitting). RBF corresponds to infinite-dimensional φ and typically yields smooth decision boundaries.
• Sigmoid kernel: k(x, x') = tanh(α x^T x' + c). Parameters α and c influence the shape and PSD behavior. It resembles the activation of a two-layer neural network. While not universally PSD for all α, c, it can be effective with proper tuning.

1. Representer Theorem: Structure of Solutions

• Problem setup: Consider minimizing an objective of the form ||w||^2 + λ Σ_i L(y_i, f(x_i)), where ||w||^2 is a regularization term (model complexity penalty), L is a loss function comparing predictions to targets, and λ controls the strength of regularization. Many standard problems fit this pattern (e.g., ridge regression, SVM-like losses, logistic-like losses with appropriate regularization forms).
• The theorem: The minimizer f* can be written as f*(x) = Σ_i α_i k(x, x_i). That is, the optimal function lies in the span of kernel functions centered on the training points. This collapses the search from an infinite function class to solving for a finite number of coefficients α.
• Implications: Training reduces to working with the kernel matrix K and solving for α (and possibly a bias term). Prediction for a new x requires computing k(x, x_i) for all training points used in the expansion (often many α_i will be zero or small, depending on the problem and regularization). This representation justifies why kernelized versions of many algorithms are both feasible and powerful.

1. Step-by-Step Implementation Guide (Conceptual)

• Step 1: Choose a kernel family and parameters (e.g., polynomial with degree d, or RBF with width σ). Use domain knowledge or simple cross-validation to guide choices.
• Step 2: Build the kernel matrix K where K_ij = k(x_i, x_j). Ensure K is symmetric; check PSD if needed (eigenvalues ≥ 0). If numerical issues arise, add a small diagonal jitter (εI) to K.
• Step 3: Formulate the learning objective in terms of K. For example, in an SVM dual or kernel ridge regression, the objective depends on K and labels y. Regularization (e.g., λ) controls complexity.
• Step 4: Solve for coefficients α (and bias b if present) using the chosen algorithm’s kernelized form. Numerical solvers or quadratic programming tools are commonly used for SVM-like problems; closed forms exist for kernel ridge regression.
• Step 5: Predict for new inputs x_new by computing f(x_new) = Σ_i α_i k(x_new, x_i) (+ b). Decision rules (e.g., sign for classification) turn scores into labels.
• Step 6: Tune parameters (σ, d, c, regularization λ) via validation. Monitor under/overfitting behavior.

1. Tips and Warnings

• Feature map pitfalls: An explicit φ that seems reasonable may still yield poor or degenerate decision boundaries for some weights. Evaluate expressiveness and consider adding lower-order terms (e.g., include linear terms alongside higher-order ones) as shown by the circle example.
• Kernel choice: RBF is a strong default for many problems; polynomial kernels can be better when interactions among features are inherently polynomial-like. The sigmoid kernel needs parameter care to remain effective and PSD in practice.
• Parameter tuning: For RBF, σ too small → overfit; too large → underfit. For polynomial, high degree → risk of overfitting and numerical instability; c adjusts the balance between higher- and lower-order contributions.
• PSD checks: Numerical round-off can produce tiny negative eigenvalues even for valid kernels. Adding a small εI to K can stabilize computations. If PSD violations are large, reconsider kernel parameters or the kernel itself.
• Scalability: Kernel methods often require storing and manipulating the n×n Gram matrix, which can be expensive for very large n. For big datasets, consider approximate methods (e.g., random features) or sparse solutions (like SVMs) to reduce computational load.

1. How the 2D Circle Emerges (Algebra Details)

• Improved φ: Let φ(x) = [x1^2, x2^2, x1, x2], and choose w = [-1, -1, 1, 1]. The decision boundary is w^T φ(x) = -x1^2 - x2^2 + x1 + x2 = 0. Rearranging: x1^2 - x1 + x2^2 - x2 = 0. Completing the square: (x1 - 1/2)^2 - 1/4 + (x2 - 1/2)^2 - 1/4 = 0 ⇒ (x1 - 1/2)^2 + (x2 - 1/2)^2 = 1/2. This is a circle centered at (1/2, 1/2) with radius √(1/2), clearly non-linear in input space.

1. Why the Initial Quadratic Map Gave Degenerate Boundaries

• With φ(x) = [x1^2, x2^2, √2 x1 x2] and w chosen as [1, 1, -1] or [1, 1, 1], algebraic manipulation collapses the boundary to only the origin. This highlights that specific weight vectors, combined with a given φ, can fail to carve a meaningful separation. The lesson: expressiveness is not just about degree—coverage of the right terms matters (e.g., including linear components). Choosing or learning weights that reflect the target geometry is key.

1. Practical Q&A Insights

• How to choose a feature map? In practice, start with standard kernel families like polynomial and RBF, then tune parameters. Use validation to compare performance. Domain knowledge (e.g., expecting smoothness or periodicity) points to certain kernels and parameter ranges.
• How to check PSD? Compute eigenvalues of K and ensure they are non-negative; for symmetric matrices, check leading principal minors as well. Persistent violations mean reconsider kernel or parameters. Regularization and numeric stabilization (adding εI) can help.

1. Putting It All Together

• Kernel methods let you keep the training simplicity of linear algorithms while capturing non-linear patterns. The kernel trick sidesteps explicit feature construction. Mercer’s theorem ensures validity of the kernel. The representer theorem structures solutions as sums of kernel evaluations at training points. With careful kernel and parameter choices, you can build accurate, flexible models without complex non-linear learners.

This lecture established kernel methods as a powerful way to make linear algorithms solve non-linear problems. The key mechanism is the feature map φ(x), which lifts inputs into a (possibly huge) feature space where a simple linear boundary becomes a curve back in the original space. The kernel trick avoids explicitly constructing φ(x) by substituting dot products with a kernel function k(x, x') = φ(x)^T φ(x'), enabling efficient computation even for high-degree or infinite-dimensional feature spaces.

We explored how particular feature maps behave, using 2D toy examples to show successes and pitfalls. A quadratic map that seemed promising ended up producing degenerate boundaries for some weights, while adding linear terms yielded a clean circular boundary. This highlighted the importance of expressiveness in feature design. The polynomial kernel provided a canonical example of turning combinatorially many polynomial features into a single, fast kernel computation. Mercer’s theorem then gave us a formal test for valid kernels—symmetry and positive semi-definiteness—along with practical PSD checks using eigenvalues or leading principal minors.

The lecture also introduced common kernels: polynomial (controlling global interactions via degree), Gaussian/RBF (capturing smooth, locality-based similarity with a width σ), and sigmoid (connecting to two-layer neural network behavior with parameters α and c). Finally, the representer theorem revealed why kernel methods are so broadly applicable: for many norm-regularized losses, the solution lies in the span of training-point kernels, f(x) = Σ α_i k(x, x_i). This reduces an infinite-dimensional search to solving for a finite set of coefficients and justifies the kernel-based formulation.

To practice, start by choosing a kernel family (RBF or polynomial), build the Gram matrix, and solve a kernelized version of a familiar linear algorithm (like SVM or ridge regression). Tune parameters such as σ, degree d, and regularization λ via validation. As a next step, dive into kernel PCA and Gaussian processes, which apply the same kernel machinery to unsupervised learning and probabilistic modeling. The core message to carry forward is simple but profound: by replacing dot products with valid kernels, you can keep the convenience of linear methods while capturing the rich, curved structures found in real-world data.