Mathematical Foundations of Machine Learning

Last time

• Last class: Monday November 04, 2024
  • We proved the SVD
• Today: We will use the SVD to better understand regression problems

• To be effectively prepared for today's class, you should have:
  1. Gone over slides and read associated lecture notes here and there
  2. Planned to submit Homework 6 (due Thursday November 07, 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
  • Dr. Bloch office hours: Friday November 08, 2024 6pm-7pm online
• Homework 6: due Thursday November 7, 2024

What's next for this semester

• Lecture 21 - Monday November 4, 2024: SVD and least squares

• Lecture 22 - Wednesday November 6, 2024: Gradient descent
  • Homework 6 due on Thursday November 7, 2024
• Lecture 23 - Monday November 11, 2024: Estimation

• Lecture 24 - Wednesday November 13, 2024: Estimation
  • Homework 7 due on Friday November 15. 2024
• Lecture 25 - Monday November 18, 2024: Classification and Regression

• Lecture 26 - Wednesday November 20, 2024: Classification and Regression

• Lecture 27 - Monday November 25, 2024: Principal Component Analysis
  • Homework 8 due
• Lecture 28 - Monday December 2, 2024: Principal Component Analysis

Singular value decomposition

• What happens for non-square matrices?

• We say that $\mathbf{A}$ is full rank is $r=min(m,n)$

• We can write $\mathbf{A}=\sum _{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{⊺}$

SVD and least-squares

• When we cannot solve $\mathbf{y}=\mathbf{A}\mathbf{x}$, we solve instead $$\underset{\mathbf{x}\in {\mathbb{R}}^n}{min}{\Vert \mathbf{x}\Vert }_2^2\text{ such that }{\mathbf{A}}^{⊺}\mathbf{A}\mathbf{x}={\mathbf{A}}^{⊺}\mathbf{y}$$
  • This allows us to pick the minimum norm solution among potentially infinitely many solutions of the normal equations.
• Recall: when $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ is of rank $m$, then $\mathbf{x}={\mathbf{A}}^{⊺}(\mathbf{A}{\mathbf{A}}^{⊺}{)}^{-1}\mathbf{y}$

Pseudo inverse

• ${\mathbf{A}}^{+}=\mathbf{V}{\mathbf{\Sigma }}^{-1}{\mathbf{U}}^{⊺}$ is called the pseudo-inverse of $\mathbf{A}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T$
  • Also called Lanczos inverse, or Moore-Penrose inverse
• If $\mathbf{A}$ is square invertible then ${\mathbf{A}}^{+}=\mathbf{A}$

• If $m\ge n$ (tall and thin matrix) of rank $n$ then ${\mathbf{A}}^{+}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}$

• If $m\ge n$ (short and large matrix) of rank $m$ then ${\mathbf{A}}^{+}={\mathbf{A}}^{⊺}(\mathbf{A}{\mathbf{A}}^{⊺}{)}^{-1}$

• Note ${\mathbf{A}}^{+}$ is as "close" to an inverse of $\mathbf{A}$ as possible (see notes and Homework)

Stability of least squares

• What if we observe $\mathbf{y}=\mathbf{A}{\mathbf{x}}_0+\mathbf{e}$ and we apply the pseudo inverse? $\hat{\mathbf{x}}={\mathbf{A}}^{+}\mathbf{y}$

• We can separate the error analysis into two components $$\hat{\mathbf{x}}-{\mathbf{x}}_0=\underset{\text{null space error}}{\underbrace{{\mathbf{A}}^{+}\mathbf{A}{\mathbf{x}}_0-{\mathbf{x}}_0}}+\underset{\text{noise error}}{\underbrace{{\mathbf{A}}^{+}\mathbf{e}}}$$

• We will express the error in terms of the SVD $\mathbf{A}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{⊺}$ With

  • ${\{{\mathbf{v}}_i\}}_{i=1}^r$ orthobasis of $\text{row}(\mathbf{A})$, augmented by ${\{{\mathbf{v}}_i\}}_{i=1}^{r+1}\in \ker \mathbf{A}$ to form an orthobasis of ${\mathbb{R}}^n$
  • ${\{{\mathbf{u}}_i\}}_{i=1}^r$ orthobasis of $\text{col}(\mathbf{A})$, augmented by ${\{\mathbf{u}\}}_{i=1}^{r+1}\in \ker {\mathbf{A}}^{⊺}$ to form an orthobasis of ${\mathbb{R}}^m$

• The null space error is given by $${\Vert {\mathbf{A}}^{+}\mathbf{A}{\mathbf{x}}_0-{\mathbf{x}}_0\Vert }_2^2=\sum _{i=r+1}^n{\left|{⟨{\mathbf{v}}_i,x_0⟩}_{}\right|}^2$$

• The noise error is given by $${\Vert {\mathbf{A}}^{+}\mathbf{e}\Vert }_2^2=\sum _{i=1}^r\frac{1}{{\sigma }_i^2}{\left|{⟨\mathbf{e},{\mathbf{u}}_i⟩}_{}\right|}^2$$

Stable reconstruction by truncation

• How do we mitigate the effect of small singular values in reconstruction? $$\hat{\mathbf{x}}=\mathbf{V}{\mathbf{\Sigma }}^{-1}{\mathbf{U}}^{⊺}\mathbf{y}=\sum _{i=1}^r\frac{1}{{\sigma }_i}{⟨\mathbf{y},{\mathbf{u}}_i⟩}_{}{\mathbf{v}}_i$$

• Truncate the SVD to $r^{\prime }<r$ $${\mathbf{A}}_t\triangleq \sum _{i=1}^{r^{\prime }}{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{⊺}{\mathbf{A}}_t^{+}=\sum _{i=1}^{r^{\prime }}\frac{1}{{\sigma }_i}{\mathbf{u}}_i{\mathbf{v}}_i^{⊺}$$

• Reconstruct $\widehat{{\mathbf{x}}_t}=\sum _{i=1}^{r^{\prime }}\frac{1}{{\sigma }_i}{⟨\mathbf{y},{\mathbf{u}}_i⟩}_{}{\mathbf{v}}_i={\mathbf{A}}_t$

• Error analysis: $${\Vert {\hat{\mathbf{x}}}_t-{\mathbf{x}}_0\Vert }_2^2=\sum _{i=r+1}^n{\left|{⟨{\mathbf{x}}_0,{\mathbf{v}}_i⟩}_{}\right|}^2+\sum _{i=r^{\prime }+1}^r{\left|{⟨{\mathbf{x}}_0,{\mathbf{v}}_i⟩}_{}\right|}^2+\sum _{i=1}^{r^{\prime }}\frac{1}{{\sigma }_i^2}{\left|{⟨\mathbf{e},{\mathbf{u}}_i⟩}_{}\right|}^2$$

Stable reconstruction by regularization

• Regularization means changing the problem to solve $$\underset{\mathbf{x}\in {\mathbb{R}}^n}{min}{\Vert \mathbf{y}-\mathbf{A}\mathbf{x}\Vert }_2^2+\lambda {\Vert \mathbf{x}\Vert }_2^2\lambda >0$$

• The solution is $$\hat{\mathbf{x}}=({\mathbf{A}}^{⊺}\mathbf{A}+\lambda \mathbf{I}{)}^{-1}{\mathbf{A}}^{⊺}\mathbf{y}=\mathbf{V}({\mathbf{\Sigma }}^2+\lambda \mathbf{I}{)}^{-1}\mathbf{\Sigma }{\mathbf{U}}^{⊺}\mathbf{y}$$

Next time

• Next class: Monday November 11, 2024

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