Mathematical Foundations of Machine Learning

• We talked about separability
• This is a way to ensure that our understanding in finite dimensions carries over to infinite dimension
• We essentially guarantee the existence of a countable orthobasis
• Not every Hilbert space is separable!

1. Gone over slides and read associated lecture notes
2. Be considering submitting Homework 2 (due Friday September 13, 2024)

• Office hours
  • Jack Hill: 11:30am-12:30pm on Wednesdays in TSRB and hybrid
  • Anuvab: 12pm-1pm on Thursdays in TSRB and hybrid
  • Dr. Bloch: 6pm on Friday online
• Solutions of HW1 will be released shortly
• Grading of HW1 in progress

• $x=\sum _{i=1}^{\mathrm{\infty }}{⟨x,v_i⟩}_{}{v}_i$ is perfectly well defined for an orthonormal basis
• Parseval's identity tell us that ${\Vert x\Vert }_{}^2=\sum _{k\ge 1}{\left|{⟨x,v_k⟩}_{}\right|}^2$.
• We don't need to even worry about the nature of $\mathcal{H}$ and only think about coefficients ${⟨x,v_i⟩}_{}$

1. Abstract Hilbert spaces allow us to do geometry on objects that are functions $$\underset{\hat{x}\in \mathcal{T}}{min}{\Vert x-\hat{x}\Vert }_2$$
2. Machine Learning is about learning functions for classification, regression.
3. Interesting Hilbert spaces of functions are infinite dimensional
4. With proper concepts (completeness, separability), infinite dimension is not a problem
5. We can worry about coordinates instead of worrying about the vectors themselves
6. We can understand what is a good representation and approximation of a function

• No! We'll actually soon introduce the notion of Reproducing Kernel Hilbert Space (RKHS)
• We'll see that infinite dimension can be useful to introduce features in ML tasks
• We'll see that we do geometry even when it's not a priori clear (think tRNA strings)

• Inequality is tight on both sides
• For orthobases, $A=B=1$

• The values of $A$ and $B$ govern the stability of the representation

• Perfectly stable representation $A=B=1$
• Efficient computation of representations: ${\alpha }_i={⟨x,v_i⟩}_{}$

Computing expansion on Riesz basis not as simple in infinite dimension: Gram matrix is "infinite"

The Gramian is a linear operator $$\mathcal{G}:{\ell }_2(\mathbb{Z})\to {\ell }_2(\mathbb{Z}):\mathbf{x}\mapsto \mathbf{y}\text{ with }[\mathcal{G}(\mathbf{x}){]}_n\triangleq y_n=\sum _{\ell =-\mathrm{\infty }}^{\mathrm{\infty }}{⟨v_{\ell },v_n⟩}_{}{x}_{\ell }$$

Fact: there exists another linear operator $\mathcal{H}:{\ell }_2(\mathbb{Z})\to {\ell }_2(\mathbb{Z})$ such that $$\mathcal{H}(\mathcal{G}(\mathbf{x}))=\mathbf{x}$$ We can replicate what we did in finite dimension!

A fundamental problem in supervised machine learning can be cast as follows $$\mathsf{\text{Given dataset }}\mathcal{D}\triangleq \{({\mathbf{x}}_i,y_i){\}}_{i=1}^n\mathsf{\text{, how do we find }}f\mathsf{\text{ such that }}f({\mathbf{x}}_i)\approx y_i\mathsf{\text{ for all }}i?$$

• Often ${\mathbf{x}}_i\in {\mathbb{R}}^d$, but sometimes ${\mathbf{x}}_i$ is a weirder object (think tRNA string)
• if $y_i\in \mathcal{Y}\subseteq \mathbb{R}$ with $|\mathcal{Y}|<\mathrm{\infty }$, the problem is called classification
• if $y_i\in \mathcal{Y}=\mathbb{R}$, the problem is called regression

We need to introduce several ingredients to make the question well defined

1. We need a class $\mathcal{F}$ to which $f$ should belong
2. We need a loss function $\ell :\mathbb{R}\times \mathbb{R}\to {\mathbb{R}}^{+}$ to measure the quality of our approximation

We can then formulate the question as $$\underset{f\in \mathcal{F}}{min}\sum _{i=1}^n\ell (f({\mathbf{x}}_i),y_i)$$

We will focus quite a bit on the square loss $\ell (u,v)\triangleq (u-v{)}^2$, called least-square regression

A common choice of $\mathcal{F}$ is the set of continuous linear functions.

• $f:{\mathbb{R}}^d\to \mathbb{R}$ is linear iff $$\mathrm{\forall }\mathbf{x},\mathbf{y}\in {\mathbb{R}}^d,\lambda ,\mu \in \mathbb{R}f(\lambda \mathbf{x}+\mu \mathbf{y})=\lambda f(\mathbf{x})+\mu f(\mathbf{y})$$

• We will see that every continuous linear function on ${\mathbb{R}}^d$ is actually an inner product, i.e., $$\mathrm{\exists }{\mathit{\theta }}_f\in {\mathbb{R}}^d\mathsf{\text{ s.t. }}f(\mathbf{x})={\mathit{\theta }}_f^{⊺}\mathbf{x}\mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^d$$

Canonical form I

• Stack ${\mathbf{x}}_i$ as row vectors into a matrix $\mathbf{X}\in {\mathbb{R}}^{n\times d}$, stack $y_i$ as elements of column vector $\mathbf{y}\in {\mathbb{R}}^n$ $$\underset{\mathit{\theta }\in {\mathbb{R}}^d}{min}{\Vert \mathbf{y}-\mathbf{X}\mathit{\theta }\Vert }_2^2\mathsf{\text{ with }}\mathbf{X}\triangleq \left[\begin{array}{c}-{\mathbf{x}}_1^{⊺}-\\ ⋮\\ -{\mathbf{x}}_n^{⊺}-\end{array}\right]$$

Canonical form II

• Allow for affine functions (not just linear)

• Add a 1 to every ${\mathbf{x}}_i$ $$\underset{\mathit{\theta }\in {\mathbb{R}}^{d+1}}{min}{\Vert \mathbf{y}-\mathbf{X}\mathit{\theta }\Vert }_2^2\mathsf{\text{ with }}\mathbf{X}\triangleq \left[\begin{array}{c}1-{\mathbf{x}}_1^{⊺}-\\ ⋮\\ 1-{\mathbf{x}}_n^{⊺}-\end{array}\right]$$

Let $\mathcal{F}$ be an $d$-dimensional subspace of a vector space with basis ${\{{\psi }_i\}}_{i=1}^d$

• We model $f(\mathbf{x})=\sum _{i=1}^d{\theta }_i{\psi }_i(\mathbf{x})$

The problem becomes $$\underset{\mathit{\theta }\in {\mathbb{R}}^d}{min}{\Vert \mathbf{y}-\mathbf{\Psi }\mathit{\theta }\Vert }_2^2\mathsf{\text{ with }}\mathbf{\Psi }\triangleq \left[\begin{array}{c}-\psi ({\mathbf{x}}_1{)}^{⊺}-\\ ⋮\\ -\psi ({\mathbf{x}}_n{)}^{⊺}-\end{array}\right]\triangleq \left[\begin{array}{cccc}{\psi }_1({\mathbf{x}}_1)& {\psi }_2({\mathbf{x}}_1)& \cdots & {\psi }_d({\mathbf{x}}_1)\\ ⋮& ⋮& ⋮& ⋮\\ {\psi }_1({\mathbf{x}}_n)& {\psi }_2({\mathbf{x}}_n)& \cdots & {\psi }_d({\mathbf{x}}_n)\end{array}\right]$$

We are recovering a nonlinear function of a continuous variable

• This is the exact same computational framework as linear regression.

• We will talk about solving regression problems
• This will highlight why linear algebra concepts are relevant for machine learning

1. Go over today's slides and read associated lecture notes
2. Work on Homework 2 (due date: Friday September 13, 2024)

• Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)