Mathematical Foundations of Machine Learning

Last time

Last class: Wednesday October 02, 2024
- We talked about the kernel trick and how we can solve regression without ever seeing the RKHS
- We talked about Aronszjan's theorem and how it helps identify kernels
- Homework 4 will help clarify ideas around this
Today: We will start working towards the SVD.

To be effectively prepared for today's class, you should have:
1. Come to class on Wednesday October 02, 2024
2. Gone over slides and read associated lecture notes here and there and there and there
3. Started reviewing your notes for the midterm
Logistics: use office hours to review for the midterm!
- 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: Monday, October 07, 2024 6pm - online
Homework 4: posted, due Sunday October 20.
- We agreed to give you room to breathe, prepare for the midterm and enjoy Fall break
- However, the pace of subsequent homework will be faster (~1/week)

Midterm

Date: Wednesday October 9, 2024 3:30pm-4:45pm in usual classroom
- Please be on time and plan to finish when asked
- Open notes (slides, annotations, lecture notes, your notes)
- no Internet, no AI, no textbook
Coverage
- Everything up to and including Lecture 11 on Wednesday September 25, 2024
- Representer theorem is in scope (functionals and RKHS are not in scope)
- Remember what $B$ -splines are but don't worry about proving the detailed properties proved in Homework 1
My expectations
- You have worked on all the homework
- You have read the lecture notes
What I am thinking about testing (this is not meant to be a hint as to what will be on the test)
- Abstract Hilbert spaces: can you manipulate functions as if they were vectors?
- Orthogonality principle: can you apply it properly to solve an optimization problem?
- Least square regression: are you able to characterize the solution?

Aronszjan's theorem

An inner product kernel is a mapping $k : R^{d} \times R^{d} \to R$ for which there exists a Hilbert space $H$ and a mapping $Φ : R^{d} \to H$ such that $\forall u, v \in R^{d} k (u, v) = ⟨ Φ (u), Φ (v) ⟩_{H}$

A function $k : R^{d} \times R^{d} \to R$ is a positive semidefinite kernel if

$k$ is symmetric, i.e., $k (u, v) = k (v, u)$
for all ${x_{i}}_{i = 1}^{N}$ , the Gram matrix $K$ is positive semidefinite, i.e., $x^{⊺} K x \geq 0 with K = [K_{i, j}] and K_{i, j} ≜ k (x_{i}, x_{j})$

A function $k : R^{d} \times R^{d} \to R$ is an inner product kernel if and only if $k$ is a positive semidefinite kernel.

Examples

Regression using linear and quadratic functions in $R^{d}$

Regression using Radial Basis Functions

Examples of kernels
- Homogeneous polynomial kernel: $k (u, v) = (u^{⊺} v)^{m}$ with $m \in N^{*}$
- Inhomogenous polynomial kernel: $k (u, v) = (u^{⊺} v + c)^{m}$ with $c > 0$ , $m \in N^{*}$
- Radial basis function (RBF) kernel: $k (u, v) = \exp (- \frac{{‖ u - v ‖}_{}^{2}}{2 σ^{2}})$ with $σ^{2} > 0$

Systems of symmetric equations

Least square problems involved the normal equations $X^{⊺} X θ = X^{⊺} y$
This is a system of symmetric equations $A x = y$ with $A^{⊺} = A$
- Ultimately we will talk about the non-symmetric/non square case

A real-valued matrix $A$ is symmetric if $A^{⊺} = A$

A complex-valued matrix $A$ is Hermitian if $A^{†} = A$ (also written $A^{H} = A$ )

Given a matrix $A \in C^{n \times n}$ , if a vector $v \in C^{n}$ satisfies $A v = λ v$ for some $λ \in C$ , then $λ$ is an eigenvalue associated to the eigenvector $v$ .

If $λ$ is an eigenvalue, there are infinitely many eigenvectors associated to it

Change of basis

Consider the canonical basis ${e_{i}}_{i = 1}^{n}$ for $R^{n}$ ; every vector can be viewed as coefficients ${α_{i}}_{i = 1}^{n}$ , $x = \sum_{i = 1}^{n} α_{i} e_{i} = {[\begin{array}{cccc} α_{1} & α_{2} & \dots & α_{n} \end{array}]}^{⊺}$
How do we find the representation of $x$ in another basis ${v_{i}}_{i = 1}^{n}$ ? Write $e_{i} = \sum_{j = 1}^{n} β_{i j} v_{j}$
Regroup the coefficients $x = \dots + (\sum_{i = 1}^{n} β_{i j} α_{i}) v_{j} + \dots$
In matrix form $x_{new} = [\begin{array}{cccc} β_{11} & β_{21} & \dots & β_{n 1} \\ β_{12} & β_{22} & \dots & β_{n 2} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ β_{1 n} & β_{2 n} & \dots & β_{n n} \end{array}] x$

Similarity

A change of basis matrix $P$ is full rank (basis vectors are linearly independent)

Any full rank matrix $P$ can be viewed as a change of basis

$P^{- 1}$ takes you back to the original basis

Warning: the columns of $P$ describe the old coordinates as a function of the new ones

If $A, B \in R^{n \times n}$ then $B$ is similar to $A$ if there exists an invertible matrix $S \in R^{n \times n}$ such that $B = P^{- 1} A P$

Intuition: similar matrices are the same up to a change of basis

$A \in R^{n \times n}$ is diagonalizable if it is similar to a diagonal matrix, i.e., there exists an invertible matrix $P \in R^{n \times n}$ such that $D = P^{- 1} A P$ with $D$ diagonal

Not all matrices are diagonalizable!

Spectral theorem

Every complex matrix $A$ has at least one complex eigenvector and every real symmetrix matrix has real eigenvalues and at least one real eigenvector.

Every matrix $A \in C^{n \times n}$ is unitarily similar to an upper triangular matrix, i.e., $A = V Δ V^{†}$ with $Δ$ upper triangular and $V^{†} = V^{- 1}$ .

Every hermitian matrix is unitarily similar to a real-valued diagonal matrix.

Note that if $A = V D V^{†}$ then $A = \sum_{i = 1}^{n} λ_{i} v_{i} v_{i}^{†}$

How about real-valued matrices $A \in R^{n \times n}$

Symmetric positive definite matrices

A symmetric matrice $A$ is positive definite if it has positive eigenvalues, i.e., $\forall i \in {1, \dots, n} λ_{i} > 0$ .

A symmetric matrice $A$ is positive semidefinite if it has nonnegative eigenvalues, i.e., $\forall i \in {1, \dots, n} λ_{i} \geq 0$ .

Convention: $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$

Variational form of extreme eigenvalues for symmetric positive definite matrices $A$ $λ_{1} = max_{x \in R^{n} : {‖ x ‖}_{2} = 1} x^{⊺} A x = max_{x \in R^{n}} \frac{x^{⊺} A x}{{‖ x ‖}_{2}^{2}} λ_{n} = min_{x \in R^{n} : {‖ x ‖}_{2} = 1} x^{⊺} A x = min_{x \in R^{n}} \frac{x^{⊺} A x}{{‖ x ‖}_{2}^{2}}$

For any analytic function $f$ , we have $f (A) = \sum_{i = 1}^{n} f (λ_{i}) v_{i} v_{i}^{⊺}$

System of symmetric definite equations

Consider the system $y = A x$ with $A$ symmetric positive definite

Let ${v_{i}}$ be the eigenvectors of $A$ . $x = \sum_{i = 1}^{n} \frac{1}{λ_{i}} {⟨ y, v_{i} ⟩}_{} v_{i}$

Assume that there exists some observation error $y = A x + e$
- $e$ is unknown
- we try to reconstruct $x$ as $\tilde{x}$ by applying $A^{- 1}$

$\frac{1}{λ_{1}^{2}} {‖ e ‖}_{}^{2} \leq {‖ x - \tilde{x} ‖}_{2} \leq \frac{1}{λ_{n}^{2}} {‖ e ‖}_{}^{2} .$

Next time

Next class: Wednesday October 09, 2024

To be effectively prepared for the midterm, you should:
1. Not panic
2. Not start reviewing your notes the night before
3. Continue reviewing your notes
4. Post questions on Piazza
5. Come to office hours with questions
Optional
- Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)