Mathematical Foundations of Machine Learning

Last time

• Last class: Wednesday, September 18, 2024
  • We talked about regularized least square regression and the solution
• Today: representer theorem and RKHS

• To be effectively prepared for today's class, you should have:
  1. Come to class last week
  2. Gone over slides and read associated lecture notes
  3. Started 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

Ridge regression

• We can adapt the regularization approach to the situation of a finite dimension Hilbert space $\mathcal{F}$ $$\underset{f\in \mathcal{F}}{min}\sum _{i=1}^n(y_i-f({\mathbf{x}}_i){)}^2+\lambda {\Vert f\Vert }_{\mathcal{F}}^2$$

  • We are penalizing the norm of the entire function $f$

• Using a basis for the space ${\{{\psi }_i\}}_{i=1}^d$ , and constructing $\mathbf{\Psi }$ as earlier, we obtain $$\underset{\mathit{\theta }\in {\mathbb{R}}^d}{min}{\Vert \mathbf{y}-\mathbf{\Psi }\mathit{\theta }\Vert }_2^2+\lambda {\mathit{\theta }}^{⊺}\mathbf{G}\mathit{\theta }$$ with $\mathbf{G}$ the Gram matrix for the basis.

• Since ${\mathbf{\Psi }}^{⊺}\mathbf{\Psi }+\lambda \mathbf{G}$ is invertible, we find the solution as $${\mathit{\theta }}^{\ast }=({\mathbf{\Psi }}^{⊺}\mathbf{\Psi }+\lambda \mathbf{G}{)}^{-1}{\mathbf{\Psi }}^{⊺}\mathbf{y}$$ and we can reconstruct the function as $f(\mathbf{x})=\sum _{i=1}^d{\theta }_i^{\ast }{\psi }_i(\mathbf{x})$.

• If $\mathbf{G}$ is well conditioned, the resulting function is not too sensitive to the choice of the basis

Least-Squares in infinite dimension Hilbert spaces

• In ${\mathbb{R}}^d$, the problem $\underset{\mathit{\theta }\in {\mathbb{R}}^d}{min}{\Vert \mathbf{y}-\mathbf{X}\mathit{\theta }\Vert }_2^2+\lambda {\Vert \mathit{\theta }\Vert }_2^2$ has a solution

  • ${\mathit{\theta }}^{\ast }={\mathbf{X}}^{⊺}\mathit{\alpha }$ with $\mathit{\alpha }=(\mathbf{X}{\mathbf{X}}^{⊺}+\lambda \mathbf{I}{)}^{-1}\mathbf{y}$
  • $\mathbf{X}{\mathbf{X}}^{⊺}\in {\mathbb{R}}^{n\times n}$ is dimension independent!
  • We will be able to extend this to infinite dimensional Hilbert spaces!

• Let $\mathcal{F}$ be a Hilbert space and let $f\in \mathcal{F}$ be the function we are trying to estimate

  • We will estimate $f\in \mathcal{F}$ using noisy observations ${⟨f,x_i⟩}_{}$ with ${\{x_i\}}_{i=1}^n$ elements of $\mathcal{F}$

  • This is the equivalent of saying $\mathbf{y}=\mathbf{A}\mathbf{x}+\mathbf{n}$ in finite dimension, where $\mathbf{n}$ is additive noise

The big picture

• For a Hilbert space $\mathcal{F}$ and $n$ pairs $(x_i,y_i)\in \mathcal{F}\times \mathbb{R}$, we know how to solve the following problem: $$\underset{f\in \mathcal{F}}{min}\sum _{i=1}^n{\left|y_i-{{⟨f,x_i⟩}_{}}_{\mathcal{F}}\right|}^2+\lambda {\Vert f\Vert }_{\mathcal{F}}^2$$

• We would really like to solve the following problem for $n$ pairs $({\mathbf{x}}_i,y_i)\in {\mathbb{R}}^d\times \mathbb{R}$ $$\underset{f\in \mathcal{F}}{min}\sum _{i=1}^n{\left|y_i-f({\mathbf{x}}_i)\right|}^2+\lambda {\Vert f\Vert }_{\mathcal{F}}^2$$

• The question whether $f({\mathbf{x}}_i)={{⟨f,x_i⟩}_{}}_{\mathcal{F}}$ for some $x_i\in \mathcal{F}$ function of ${\mathbf{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, $\mathcal{F}$ is a Hilbert space with scalar field $\mathbb{R}$

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

Continuous linear functionals on Hilbert spaces

• Continuous linear functions are much more constrained than one would imagine

Representation of (continuous) linear functionals

• Linear functional over finite dimensional Hilbert spaces are continuous!

• This is not true in infinite dimension

Reproducing Kernel Hilbert Spaces

RKHS and non orthogonal basis

• If ${\{{\varphi }_n\}}_{n\ge 1}$ is a Riesz basis for $\mathcal{H}$, we know that every $x\in \mathcal{H}$ can be written $$x=\sum _{n\ge 1}{\alpha }_n{\varphi }_n\mathsf{\text{ with }}{\alpha }_n\triangleq {⟨x,{\tilde{\varphi }}_n⟩}_{}$$ where ${\{{\tilde{\varphi }}_n\}}_{n\ge 1}$ is the dual basis.

Kernel regression

• Regression problem: given $n$ pairs $({\mathbf{x}}_i,y_i)\in {\mathbb{R}}^d\times \mathbb{R}$, solve $$\underset{f\in \mathcal{F}}{min}\sum _{i=1}^n{\left|y_i-f({\mathbf{x}}_i)\right|}^2+\lambda {\Vert f\Vert }_{\mathcal{F}}^2$$

• If we restrict $\mathcal{F}$ to be an RKHS, the problem becomes $$\underset{f\in \mathcal{F}}{min}\sum _{i=1}^n{\left|y_i-{{⟨f,x_i⟩}_{}}_{\mathcal{F}}\right|}^2+\lambda {\Vert f\Vert }_{\mathcal{F}}^2$$

  where $x_i\triangleq k_{{\mathbf{x}}_i}$ provides the mapping between ${\mathbb{R}}^d$ and $\mathcal{F}$ $$x_i:{\mathbf{R}}^d\to \mathbb{R}:\mathbf{t}\mapsto k_{{\mathbf{x}}_i}(\mathbf{t})=k({\mathbf{x}}_i,\mathbf{t})$$

• The solution is given by $\hat{f}=\sum _{i=1}^n{\hat{\alpha }}_i{x}_i\mathsf{\text{ with }}\hat{\mathit{\alpha }}\triangleq (\mathbf{K}+\lambda \mathbf{I}{)}^{-1}\mathbf{y}$ and $\mathbf{K}\triangleq [K_{i,j}{]}_{1\le i,j\le n}$ with $K_{i,j}={⟨x_i,x_j⟩}_{}$

Kernel regression

• Kernel magic
  1. $K_{ij}={⟨x_i,x_j⟩}_{}={⟨k_{{\mathbf{x}}_i},k_{{\mathbf{x}}_j}⟩}_{}=k_{{\mathbf{x}}_i}({\mathbf{x}}_j)=k({\mathbf{x}}_i,{\mathbf{x}}_j)$
  2. $\hat{f}(\mathbf{x})={⟨\hat{f},k_{\mathbf{x}}⟩}_{}=\sum _{i=1}^n\widehat{{\alpha }_i}k({\mathbf{x}}_i,\mathbf{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 $\mathcal{F}$
• Question: can we skip $\mathcal{F}$ entirely? how do we find "good" kernels?

Aronszjan's theorem

Examples

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

Next time

• Next class: Wednesday September 25, 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)