Mathematical Foundations of Machine Learning

Last time

• Last class: Monday September 16, 2024
  • We talked about least square regression
• 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
• Logistics
  • Office hours
    • Jack Hill: 11:30am-12:30pm on Wednesdays in TSRB and hybrid
    • Anuvab: 12pm-1pm on Thursdays in TSRB and hybrid
  • Gradescope
    • Make sure you assign each solution to each question
    • Make sure you do some quality control on your submission

Solving the least-squares problem

• Facts: for any matrix $\mathbf{A}\in {\mathbb{R}}^{m\times n}$

  • $\ker {\mathbf{A}}^{⊺}\mathbf{A}=\ker \mathbf{A}$

  • $\text{col}({\mathbf{A}}^{⊺}\mathbf{A})=\text{row}(\mathbf{A})$

  • $\text{row}(\mathbf{A})$ and $\ker \mathbf{A}$ are orthogonal complements

• We can say a lot more about the normal equations

  1. There is always a solution
  2. If $\mathsf{\text{rank}}(\mathbf{X})=d$, there is a unique solution: $({\mathbf{X}}^{⊺}\mathbf{X}{)}^{-1}{\mathbf{X}}^{⊺}\mathbf{y}$
  3. if $\mathsf{\text{rank}}(\mathbf{X})<d$ there are infinitely many non-trivial solution
  4. if $\mathsf{\text{rank}}(\mathbf{X})=n$, there exists a solution ${\mathit{\theta }}^{\ast }$ for which $\mathbf{y}=\mathbf{X}{\mathit{\theta }}^{\ast }$

• In machine learning, there are often infinitely many solutions

Minimum norm 2 solutions

• Reasonable approach: choose a solution among infinitely many with the minimum energy principle $$\underset{\mathit{\theta }\in {\mathbb{R}}^d}{min}{\Vert \mathit{\theta }\Vert }_2^2\text{ such that }{\mathbf{X}}^{⊺}\mathbf{X}\mathit{\theta }={\mathbf{X}}^{⊺}\mathbf{y}$$

  • We will see the solution is always unique using the SVD

• For now, assume that $\mathsf{\text{rank}}(\mathbf{X})=n$, so that the problem becomes $$\underset{\mathit{\theta }\in {\mathbb{R}}^d}{min}{\Vert \mathit{\theta }\Vert }_2^2\text{ such that }\mathbf{X}\mathit{\theta }=\mathbf{y}$$

Regularization

• Recall the problem $\underset{\mathit{\theta }\in {\mathbb{R}}^d}{min}{\Vert \mathit{\theta }\Vert }_2^2$ such that ${\mathbf{X}}^{⊺}\mathbf{X}\mathit{\theta }={\mathbf{X}}^{⊺}\mathbf{y}$
  • There are infinitely many solution if $\ker \mathbf{X}$ is non trivial
  • The space of solution is unbounded!
  • Even if $\ker \mathbf{X}=\{0\}$, the system can be poorly conditioned
• Regularization with $\lambda >0$ consists in solving $$\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$$
  • This problem always has a unique solution

• Note that ${\mathit{\theta }}^{\ast }$ is in the row space of $\mathbf{X}$ $${\mathit{\theta }}^{\ast }={\mathbf{X}}^{⊺}\mathit{\alpha }\mathsf{\text{ with }}\mathit{\alpha }=(\mathbf{X}{\mathbf{X}}^{⊺}+\lambda \mathbf{I}{)}^{-1}\mathbf{y}$$

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.

• If ${\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

• This happens in Reproducing Kernel Hilber Space (RKHS)

Next time

• Next class: Monday September 23, 2024

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