Mathematical Foundations of Machine Learning

Last time

• Last class: Wednesday September 25, 2024
  • We talked about the representer theorem
  • We talked about the need to create spaces of functions for which we could write $f(\mathbf{x})={⟨f,x⟩}_{}$
  • We introduced the notion of RKHS
• Today: more on Reproducing Kernel Hilbert Space

• 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 here and there and there and there
  3. Made progress on Homework 3 (due Sunday September 29, 2024, can submit until Tuesday October 01, 2024)
• Logistics
  • Jack Hill office hours: Wednesday 11:30am-12:30pm in TSRB and hybrid
  • Anuvab Sen office hours: Thursday 12pm-1pm in TSRB and hybrid
• Midterm: Wednesday October 9, 2024 3:30pm-4:45pm in usual classroom
  • Coverage up to and including Lecture 11 on Wednesday September 25, 2024
  • Will provide problems to work on your own or during office hours

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 October 02, 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. Submit Homework 3 if not already done
• Optional
  • Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)