ece7750-2024-08-19-representations.tmpnPVVlX

Today's class

Objective 1: ease into vector spaces of functions
- Why it matters to ML
- Why you might have seen it already in some form
- Why we'll need linear algebra!
Objective 2: write a few proofs together
- How to write clean proofs

Representation and approximation in ML

Regression and classification in machine learning
- Many problems reduce to fitting a function $f : R^{d} \to R$ to data ${(x_{i}, y_{i})}_{i = 1}^{n}$
- $f$ is the unknown quantity, and we want $f (x_{i}) \approx y_{i}$ so that we can predict $f (x)$ for every $x \in R^{d}$
- Classification: predict a label
- Regression: predict a real number

Fundamental question: how do we represent a function in a computer?
- A computer only stores a sequence of (quantized) real values
- What does it mean to "store"a function, say $f (x) = \sin x$
Solution: use a basis expansion $f (x) \approx \sum_{i = 1}^{m} α_{i} h_{i} (x)$
- ${h_{i}}_{i = 1}^{m}$ are called basis functions (how do we choose them?)
- The approximation is called a linear basis expansion
- Representing $f$ amounts to finding ${α_{i}}_{i = 1}^{M}$ - we'll try to formalize this later

Example: Polynomials

There is a natural "basis" for representing polynomials of degree $i$ $p (x) = \sum_{i = 0}^{m} α_{i} x^{i}$
- The monomials ${x^{i}}_{i = 1}^{m}$ can be combined to describe any polynomial of degree less than or equal to $m$
- The degree $m$ controls the "richness" or "complexity" the functions we can describe
Question: which functions can be described as such?
- Analytic functions on open set $D$ : $f (x) = \sum_{i = 0}^{\infty} α_{i} (x - x_{0})^{i}$ for every $x \in D$ . $e^{x} = \sum_{i = 0}^{\infty} \frac{1}{i!} x^{i} \log (1 + x) = \sum_{i = 0}^{\infty} \frac{(- 1)^{i + 1}}{k} x^{k} \sin x = \sum_{i = 0}^{\infty} \frac{(- 1)^{i}}{(2 i + 1)!} x^{2 i + 1}$
- Taylor series

Let $k \geq 1$ and let $f : R \to R$ be in $k$ times differentiable at a point $a \in R$ . There exists $h_{k} : R \to R$ such that $lim_{x \to a} h_{k} (x) = 0$ and $f (x) = \sum_{i = 0}^{k} \frac{f^{(i)} (a)}{i!} (x - a)^{i} + h_{k} (x) (x - a)^{k} .$

Example: Lagrange Polynomials

Question: How do we find a basis expansion given ${(x_{i}, y_{i})}_{i = 1}^{n}$ ?
Lagrange polynomials $p (x) = \sum_{j = 1}^{n} α_{j} L_{j} (x) L_{j} (x) ≜ \prod_{1 \leq i \leq n, i \neq j} \frac{x - x_{i}}{x_{j} - x_{i}}$

Given $n \geq 1$ distinct points ${(x_{i}, y_{i})}_{i = 1}^{n}$ , there exists a unique degree $n - 1$ interpolating polynomial.

Example: Polynomial splines

Given $n \geq 1$ distinct points ${(x_{i}, y_{i})}_{i = 1}^{n}$ a polynomial spline $p$ of order $ℓ$ is such that

$p (x_{i}) = y_{i}$ for $i \in [1; n]$
$p$ is an $ℓ$ th order polynomial between consecutive points $x_{i}$ and $x_{i + 1}$
$p (x)$ has $ℓ - 1$ continuous derivatives at the points ${x_{i}}_{i = 1}^{n}$

B-splines: the splines can be viewed as linear basis expansion on a basis called B-splines
- What are the B-splines for $ℓ = 0$ ?
- What are the B-splines for $ℓ = 1$ ?
- What are the B-splines for $ℓ = 2$ ?
Moving forward, we will need linear algebra to describe this precisely and systematically
- How do we compute a linear basis expansion?
- What is a good basis for machine learning?
- How do we measure the quality of approximation?

Next time

Next class: Wednesday August 21, 2024 3:30pm
- We will review vector spaces
- We will work towards infinite dimensional spaces of functions
To be effectively prepared for next class, you should:
1. Read the syllabus in details
2. Go over today's slides and read associated lecture notes
3. Make sure you have access to Canvas, Piazza, Gradescope
4. Start Homework 0 (due date: Monday August 26, 2024)
Optional
- Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)

Mathematical Foundations of Machine Learning