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.