Mathematical Foundations of Machine Learning

Last time

• Last class: Wednesday, September 11, 2024
  • We wrapped up our discussion of infinite dimensional spaces
  • Take away: separable Hilbert spaces are like ${\ell }_2$
• 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. Have submitted Homework 2
• 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

Regression

• 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

Least square linear 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$$

Least square affine regression

• 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]$$

Nonlinear regression using a basis

• 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.

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\text{ 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}$$

Next time

• Next class: Wednesday September 18, 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 (due date: Wednesday September 25, 2024)
• Optional
  • Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)