Mathematical Foundations of Machine Learning

Last time

Last class: Monday September 23, 2024
- We talked about ridge regression
- We introduced a version of regularized least squares in infinite dimension
- We started proving the representer theorem
Today: Reproducing Kernel Hilbert Space

To be effectively prepared for today's class, you should have:
1. Come to class on Monday
2. Gone over slides and read associated lecture notes here and there and there and there
3. Made progress on Homework 3 (due Sunday September 29, 2024)
Logistics
- Office hours
  - Jack Hill: Wednesday 11:30am-12:30pm in TSRB and hybrid
  - Anuvab Sen: Thursday 12pm-1pm in TSRB and hybrid
- Gradescope: make sure you perform a quality check of your submission
Midterm: Wednesday October 9, 2024 3:30pm-4:45pm in usual classroom

Least-Squares in infinite dimension Hilbert spaces

In $R^{d}$ , the problem $min_{θ \in R^{d}} {‖ y - X θ ‖}_{2}^{2} + λ {‖ θ ‖}_{2}^{2}$ has a solution
- $θ^{*} = X^{⊺} α$ with $α = (X X^{⊺} + λ I)^{- 1} y$
- $X X^{⊺} \in R^{n \times n}$ does not explicitly depend on the dimension of the data!
- We will be able to extend this to infinite dimensional Hilbert spaces!
Let $F$ be a Hilbert space and let $f \in F$ be the function we are trying to estimate
- We will estimate $f \in F$ using noisy observations ${⟨ f, x_{i} ⟩}_{}$ with ${x_{i}}_{i = 1}^{n}$ elements of $F$
- This is the equivalent of saying $y = A x + n$ in finite dimension, where $n$ is additive noise

$min_{f \in F} \sum_{i = 1}^{n} {| y_{i} - {⟨ f, x_{i} ⟩}_{}_{F} |}^{2} + λ {‖ f ‖}_{F}$ has solution $f = \sum_{i = 1}^{n} α_{i} x_{i} with α = (K + λ I)^{- 1} y K = {[\begin{matrix} {⟨ x_{i}, x_{j} ⟩}_{} \end{matrix}]}_{1 \leq i, j \leq n}$

The big picture

For a Hilbert space $F$ and $n$ pairs $(x_{i}, y_{i}) \in F \times R$ , we know how to solve the following problem: $min_{f \in F} \sum_{i = 1}^{n} {| y_{i} - {⟨ f, x_{i} ⟩}_{}_{F} |}^{2} + λ {‖ f ‖}_{F}^{2}$
We would really like to solve the following problem for $n$ pairs $(x_{i}, y_{i}) \in R^{d} \times R$ $min_{f \in F} \sum_{i = 1}^{n} {| y_{i} - f (x_{i}) |}^{2} + λ {‖ f ‖}_{F}^{2}$
The question whether $f (x_{i}) = {⟨ f, x_{i} ⟩}_{}_{F}$ for some $x_{i} \in F$ function of $x_{i}$ : can this be done?

Reproducing Kernel Hilbert Spaces (RKHSs) are specific Hilbert spaces where this happens to be true
- Hilbert space of functions where the sampling linear operation is a continuous linear functional
As usual, we're throwing definitions at our problem to make progress

Linear functionals on Hilbert spaces

In what follows, $F$ is a Hilbert space with scalar field $R$

A functional $F : F \to R$ associates a real number to an element of a Hilbert space $F$

Notation can be tricky when the Hilbert space is a space of functions: $F$ can act on a function $f \in F$

A functional $F : F \to R$ is continuous at $x \in F$ if $\forall ϵ > 0 \exists δ > 0 such that {‖ x - y ‖}_{F} \leq δ \Rightarrow | F (x) - F (y) | \leq ϵ$ If this is true for every $x \in F$ , $F$ is continuous.

All norms are continuous functionals
For $c \in F$ $F_{c} : F \to R : x \mapsto {⟨ x, c ⟩}_{}$ is continuous

Continuous linear functionals on Hilbert spaces

A functional $F$ is linear if $\forall a, b \in R$ $\forall x, y \in F$ $F (a x + b y) = a F (x) + b F (y)$ .

Continuous linear functions are much more constrained than one would imagine

A linear functional $F : F \to R$ is bounded if there exists $M > 0$ such that $\forall x \in F | F (x) | \leq M {‖ x ‖}_{F}$

A linear functional on a Hilbert space that is continuous at $0$ is bounded.

For a linear functional $F : F \to R$ , the following statements are equivalent:

$F$ is continuous at 0
$F$ is continuous at some point $x \in F$
$F$ is continuous everywhere on $F$
$F$ is uniformly continuous everywhere on $F$

Representation of (continuous) linear functionals

Let $F : F \to R$ be a linear functional on an $n$ -dimensional Hilbert space $F$ .

There exists $c \in F$ such that $F (x) = {⟨ x, c ⟩}_{}$ for every $x \in F$

Linear functional over finite dimensional Hilbert spaces are continuous!
This is not true in infinite dimension

Let $F : F \to R$ be a continuous linear functional on a (possible infinite dimensional) separable Hilbert space $F$ .

There exists $c \in F$ such that $F (x) = {⟨ x, c ⟩}_{}$ for every $x \in F$

If ${ψ_{n}}_{n \geq 1}$ is an orthobasis for $H$ , then we can construct $c$ above as $c ≜ \sum_{n = 1}^{\infty} F (ψ_{n}) ψ_{n}$

Reproducing Kernel Hilbert Spaces

An RKHS is a Hilbert space $H$ of real-valued functions $f : R^{d} \to R$ in which the sampling operation $S_{τ} : H \to R : f \mapsto f (τ)$ is continuous for every $τ \in R^{d}$ .

In other words, for each $τ \in R^{d}$ , there exists $k_{τ} \in H$ s.t. $f (τ) = {⟨ f, k_{τ} ⟩}_{}_{H} for all f \in H$

The kernel of an RKHS is $k : R^{d} \times R^{d} \to R : (t, τ) \mapsto k_{τ} (t)$ where $k_{τ}$ is the element of $H$ that defines the sampling at $τ$ .

A (separable) Hilbert space with orthobasis ${ψ_{n}}_{n \geq 1}$ is an RKHS iff $\forall τ \in R^{d}$ $\sum_{n = 1}^{\infty} {| ψ_{n} (τ) |}^{2} < \infty$

RKHS and non orthogonal basis

If ${ϕ_{n}}_{n \geq 1}$ is a Riesz basis for $H$ , we know that every $x \in H$ can be written $x = \sum_{n \geq 1} α_{n} ϕ_{n} with α_{n} ≜ {⟨ x, {\tilde{ϕ}}_{n} ⟩}_{}$ where ${{\tilde{ϕ}}_{n}}_{n \geq 1}$ is the dual basis.

A (separable) Hilbert space with Riesz basis ${ϕ_{n}}_{n \geq 1}$ is an RKHS with kernel $k (t, τ) = \sum_{n = 1}^{\infty} ϕ_{n} (τ) {\tilde{ϕ}}_{n} (t)$ iff $\forall τ \in R^{d}$ $\sum_{n = 1}^{\infty} {| ϕ_{n} (τ) |}^{2} < \infty$

Kernel regression

Regression problem: given $n$ pairs $(x_{i}, y_{i}) \in R^{d} \times R$ , solve $min_{f \in F} \sum_{i = 1}^{n} {| y_{i} - f (x_{i}) |}^{2} + λ {‖ f ‖}_{F}^{2}$
If we restrict $F$ to be an RKHS, the problem becomes $min_{f \in F} \sum_{i = 1}^{n} {| y_{i} - {⟨ f, x_{i} ⟩}_{}_{F} |}^{2} + λ {‖ f ‖}_{F}^{2}$

where $x_{i} ≜ k_{x_{i}}$ provides the mapping between $R^{d}$ and $F$ $x_{i} : R^{d} \to R : t \mapsto k_{x_{i}} (t) = k (x_{i}, t)$
The solution is given by $\hat{f} = \sum_{i = 1}^{n} {\hat{α}}_{i} x_{i} with \hat{α} ≜ (K + λ I)^{- 1} y$ and $K ≜ [K_{i, j}]_{1 \leq i, j \leq n}$ with $K_{i, j} = {⟨ x_{i}, x_{j} ⟩}_{}$

Kernel regression

Kernel magic
1. $K_{i j} = {⟨ x_{i}, x_{j} ⟩}_{} = {⟨ k_{x_{i}}, k_{x_{j}} ⟩}_{} = k_{x_{i}} (x_{j}) = k (x_{i}, x_{j})$
2. $\hat{f} (x) = {⟨ \hat{f}, k_{x} ⟩}_{} = \sum_{i = 1}^{n} \hat{α_{i}} k (x_{i}, x)$
Remarks
- We solved an infinite dimensional problem using an $n \times n$ system of equations and linear algebra
- Our solution and the evaluation only depend on the kernel; we never need to work directly in $F$
Question: can we skip $F$ entirely? how do we find "good" kernels?

Aronszjan's theorem

An inner product kernel is a mapping $k : R^{d} \times R^{d} \to R$ for which there exists a Hilbert space $H$ and a mapping $Φ : R^{d} \to H$ such that $\forall u, v \in R^{d} k (u, v) = ⟨ Φ (u), Φ (v) ⟩_{H}$

A function $k : R^{d} \times R^{d} \to R$ is a positive semidefinite kernel if

$k$ is symmetric, i.e., $k (u, v) = k (v, u)$
for all ${x_{i}}_{i = 1}^{N}$ , the Gram matrix $K$ is positive semidefinite, i.e., $x^{⊺} K x \geq 0 with K = [K_{i, j}] and K_{i, j} ≜ k (x_{i}, x_{j})$

A function $k : R^{d} \times R^{d} \to R$ is an inner product kernel if and only if $k$ is a positive semidefinite kernel.

Examples

Regression using linear and quadratic functions in $R^{d}$

Regression using Radial Basis Functions

Examples of kernels
- Homogeneous polynomial kernel: $k (u, v) = (u^{⊺} v)^{m}$ with $m \in N^{*}$
- Inhomogenous polynomial kernel: $k (u, v) = (u^{⊺} v + c)^{m}$ with $c > 0$ , $m \in N^{*}$
- Radial basis function (RBF) kernel: $k (u, v) = \exp (- \frac{{‖ u - v ‖}_{}^{2}}{2 σ^{2}})$ with $σ^{2} > 0$

Next time

Next class: Monday September 30, 2024

To be effectively prepared for next class, you should:
1. Go over today's slides and read associated lecture notes here and there and there and there
2. Work on Homework 3
Optional
- Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)