Project 56: Functional Analysis and RKHS Kernel Lab

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Level 5: Master
  • Time: 3 weeks
  • Language: Python
  • Prerequisites: Projects 20, 24, 51-52, and 55
  • Source: ML-Math P28

What You Will Build

Create a kernel-method workbench that turns Hilbert-space language into testable computations. Implement linear, polynomial, and RBF Gram matrices; verify symmetry and positive semidefiniteness numerically; and show how kernels define similarity without explicitly constructing high-dimensional features. Build dual kernel ridge regression, compare it with an explicit primal feature map where one exists, and sweep regularization to plot prediction error against the RKHS norm proxy. Include ill-conditioned and intentionally invalid kernels, scaling diagnostics, and at least one approximation such as Nyström or random Fourier features.

Real World Outcome

Given a small nonlinear dataset, the lab reports kernel eigenvalues/PSD status, condition number, selected regularization, train/test error, RKHS norm, and primal-versus-dual prediction difference. It plots fitted functions or decision surfaces and demonstrates how kernel width and regularization control smoothness and generalization.

Core Question

How can learning in an infinite-dimensional function space reduce to a finite kernel matrix computation?

Concepts You Must Understand First

  • Normed, inner-product, and Hilbert spaces; bounded linear operators.
  • Positive semidefinite kernels and Gram matrices — Schölkopf and Smola, Learning with Kernels.
  • Reproducing property and the representer theorem.
  • Ridge regularization as control of function-space norm.
  • Eigenvalues, conditioning, duality, and stable solves — Projects 24, 30, and 51.

Build Milestones

  1. Implement kernel interfaces and PSD/symmetry/conditioning diagnostics.
  2. Implement dual kernel ridge fitting and prediction with stable linear solves.
  3. Verify primal/dual equivalence for linear and finite polynomial features.
  4. Sweep kernel hyperparameters and lambda; plot norm, error, smoothness, and conditioning.
  5. Add an invalid-kernel test and one scalable approximation with quality/runtime comparison.

Hints in Layers

  1. Never compute a matrix inverse explicitly; solve the regularized linear system.
  2. Tiny negative eigenvalues may be roundoff, while substantial negatives indicate an invalid kernel—use scale-aware tolerances.
  3. Fit feature scaling only on training data; RBF distance is extremely scale-sensitive.

Common Pitfalls and Debugging

  • Solver becomes unstable as lambda approaches zero: Gram matrix is ill-conditioned. Report condition number and use Cholesky/robust solves with regularization.
  • RBF predicts almost a constant or memorizes every point: kernel width is at an extreme. Visualize the Gram matrix and sweep width on a log scale.
  • Kernel declared valid despite negative eigenvalues: PSD tolerance ignores matrix scale. Normalize the tolerance to the largest eigenvalue/norm.

Definition of Done

  • Linear, polynomial, and RBF kernels pass symmetry and PSD diagnostics.
  • Dual kernel ridge regression works without explicit inversion.
  • Explicit-feature primal and kernel dual predictions agree where comparable.
  • Regularization/kernel sweeps report error, norm, smoothness, and conditioning.
  • Invalid and near-PSD numerical cases are distinguished responsibly.
  • One approximation method includes accuracy, runtime, and memory tradeoffs.

Previous: Project 55 · Complete learning path · Next: Project 57