Mathematical Foundations of Machine Learning

Prof. Matthieu Bloch

Monday August 26, 2024 (v1.2)

Logistics

  • ECE 7750 in numbers
    • 138 students (including Q and QSZ sections)
    • 29 lectures left
    • 8 Homework assignments left
    • 2 GTAs who will have a lot of grading to do
    • 1 Instructor who is looking forward to a fun semester
  • Action items
    • Submit your Homework 0
      • due date: Monday August 26, 2024
      • hard cut-off on Wednesday August 28, 2024
    • Please complete the Verification of Participation poll on Piazza

Last time

  • Last class: Wednesday August 21, 2024
    • We talked about vector spaces
    • We talked about how to approach mathematical statements and proofs
      • Take-away 1: inspect statements and make sure you appreciate details
      • Take-away 2: doodle the statements by using special cases to comfort your understanding
Image
(c) xkcd
  • To be effectively prepared for today's class, you should have:
    1. Gone over the previous slides and read associated lecture notes
    2. Made sure you have access to Canvas, Piazza, Gradescope
    3. Spent time on Homework 0 (due date: Monday August 26, 2024)

Linear independence

  • Let \(\set{v_i}_{i=1}^n\) be a set of vectors in a vector space \(\calV\)

\(\set{v_i}_{i=1}^n\) is linearly independent (or the vectors \(\set{v_i}_{i=1}^n\) are linearly independent ) if (and only if) \[ \sum_{i=1}^na_iv_i = 0\Rightarrow \forall i\in\intseq{1}{n}\,a_i=0 \] Otherwise the set is (or the vectors are) linearly dependent.

\[ \calV\eqdef\bbR^3\quad \bfv_1=\mat{ccc}{2&1&0}^\intercal, \bfv_2=\mat{ccc}{1&1&0}^\intercal, \bfv_3=\mat{ccc}{1&2&0}^\intercal \]

\[ \calV\eqdef\calC([0;1])\quad v_1=\cos(2\pi t), v_2=\sin(2\pi t), v_3=2\cos(2\pi t +\frac{\pi}{3}) \]

Any finite set of linearly dependent vectors contains a subset of linearly independent vectors with the same span.

Bases

A basis of vector subspace \(\calW\) of a vector space \(\calV\) is a countable set of vectors \(\calB\) such that:

  1. \(\text{span}(\calB)=\calW\)
  2. \(\calB\) is linearly independent

If a vector space \(\calV\neq \set{0}\) has a finite basis with \(n\in\bbN^*\) elements, \(n\) is called the dimension of \(\calV\), denoted \(\dim{\calV}\). If the basis has an infinite number of elements, the dimension is infinite

Any two bases for the same finite dimensional vector space contain the same number of elements.

  • You should be somewhat familiar with bases (at least in \(\bbR^n\)):
    • the representation of a vector on a basis is unique
    • every subspace has a basis
    • having a basis reduces the operations on vectors to operations on their components
  • Things sort of work in infinite dimensions, but we have to be bit more careful

Norm

  • The properties of vector space seen thus far provide an algebraic structure

  • We are missing a topological structure to measure length and distance

A norm on a vector space \(\calV\) over \(\bbR\) is a function \(\norm{\cdot}:\calV\to\bbR\) that satisfies:

  • Positive definiteness: \(\forall x\in\calV\) \(\norm{x}\geq 0\) with equality iff \(x=0\)
  • Homogeneity: \(\forall x\in\calV\) \(\forall\alpha\in\bbR\) \(\norm{\alpha x}=\abs{\alpha}\norm{x}\)
  • Subadditivity: \(\forall x,y\in\calV\) \(\norm{x+y}\leq \norm{x}+\norm{y}\)
  • \(\norm{x}\) measures a length, \(\norm{x-y}\) measures a distance

\(\bfx\in\bbR^d\qquad\norm[0]{\bfx}\eqdef\card{\set{i:x_i\neq 0}}\quad\norm[1]{\bfx}\eqdef\sum_{i=1}^d\abs{x_i}\quad \norm[2]{\bfx}\eqdef\sqrt{\sum_{i=1}^d x_i^2}\)

Inner product

  • In addition to a topological and algebraic strucure, what if we want to do geometry?

An inner product space over \(\bbR\) is a vector space \(\calV\) equipped with a positive definite symmetric bilinear form \(\dotp{\cdot}{\cdot}:\calV\times\calV\to\bbR\) called an inner product

  • An inner product space is also called a pre-Hilbert space

An inner product satisfies \(\forall x,y\in\calV\) \(\dotp{x}{y}^2\leq\dotp{x}{x}\dotp{y}{y}\)

Equality holds if and only if \(x\) and \(y\) are colinear, i.e., \(\exists\alpha\in\bbR\) such that \(y=\alpha x\)

  • Unless stated otherwise, we will only deal with vector spaces on \(\bbR\)
    • Things don't change too much on \(\bbC\) but one should be a bit more careful
    • One has to deal with a conjugate

Induced norm

In an inner product space, an inner product induces a norm \(\norm{x} \eqdef \sqrt{\dotp{x}{x}}\)

A norm \(\norm{\cdot}\) induces an inner product on \(\calV\) iff \(\forall x,y\in\calV\) \(\norm{x}^2+\norm{y}^2 = \frac{1}{2}\left(\norm{x+y}^2+\norm{x-y}^2\right)\)

If this is the case, the inner product is given by the polarization identity \[\dotp{x}{y}=\frac{1}{2}\left(\norm{x}^2+\norm{y}^2-\norm{x-y}^2\right)\]

Orthogonality

  • In the following \(\calV\) is always an inner product space with induced norm \(\norm{\cdot}\)

The angle between two non-zero vectors \(x,y\in\calV\) is \(\cos\theta \eqdef \frac{\dotp{x}{y}}{\norm{x}\norm{y}}\)

Two vectors \(x,y\in\calV\) are orthogonal if \(\dotp{x}{y}=0\). We write \(x\perp y\) for simplicity.

A vector \(x\in\calV\) is orthogonal to a set \(\calS\subset\calV\) if \(\forall s\in\calS\) \(\dotp{x}{s}=0\). We write \(x\perp \calS\) for simplicity.

If \(x\perp y\) then \(\norm{x+y}^2=\norm{x}^2+\norm{y}^2\)

Let \(\calW\) be a vector subspace of \(\calV\). The orthogonal subspace of \(\calW\) is \[ \calW^\perp\eqdef\set{v\in\calV:\forall w\in\calW \dotp{w}{v}=0}. \]

\(\calW^\perp\) is a subspace of \(\calV\) and \((\calW^\perp)^\perp=\calW\)

Infinite dimensions

  • In infinite dimensions, things are a little bit tricky. What does the following mean? \[ x(t) = \sum_{n=1}^\infty \alpha_n\psi_n(t) \]

  • We need to define a notion of convergence, e.g., \[ \lim_{N\to\infty}\norm{x(t)-\sum_{n=1}^N \alpha_n\psi_n(t)}=0 \]

  • Problems can still arise if "points are missing"

  • We avoid this by introducing the notion of completeness

Hilbert space

A sequence \(\set{x_n}_{n\geq 0}\) in \(\calV\) is Cauchy if \(\forall\epsilon>0\) \(\exists N\in\bbN^*\) such that \(\forall n,m>N\) \(\norm{x_n-x_m}\leq \epsilon\)

A Hilbert space \(\calH\) is a complete inner product space, i.e., an inner product space in which every Cauchy sequence in \(\calH\) converges to a point in \(\calH\)

  • Intuition: a Hilbert space has no "missing point"
  • A finite dimensional inner product space is complete (many Hilbert spaces are infinite dimensional!)
  • We won't worry too much about proving that spaces are complete
  • A complete normed vector space is a Banach space; a lot of things are still possible without an inner product

Next time

  • Next class: Wednesday August 28, 2024
    • We will talk about linear approximations
    • We will prove a very fundamental result called the orthogonality principle
  • To be effectively prepared for next class, you should:
    1. Go over today's slides and read associated lecture notes
    2. Make sure you have access to Canvas, Piazza, Gradescope
    3. Work on Homework 1 (due date: Monday September 2, 2024)
  • Optional
    • Export slides for next lecture as PDF (be on the lookout for an announcement when they're ready)