Machine Learning Math

Groups.

Def. A set $G$ of elements with an operation $+:G\to G$ is called a group if the following properties hold:

1. Associativity : $\forall a,b,c\in G(a+b)+c=a+(b+c)$
2. Identity : $\exists e\in G\forall g\in G$ s.t. $e+g=g+e=g$
3. Inverse : $\forall a\in G\exists b\in G$ s.t. $a+b=b+a=e$

The group is called a commutative (Abelian) group if we have additionally

$$\forall a,b\in Ga+b=b+a$$

Example: $S_n:=\{\pi :\{1,\dots ,n\}\to \{1,\dots ,n\}\mid \pi \text{ is bijective}\}$

Fields.

Def. A set $F$ with 2 operations $+,\ast :F\times F\to F$ is called a field if the following properties hold:

1. $(F,+)$ is a commutative group with identity element 0
2. $(F\setminus \{0\},\ast )$ is also a commutative group with identity element 1
3. Distributivity: $\forall a,b,c\in Fa\ast (b+c)=a\ast b+a\ast c$

Example: For a $n\in \mathbb{Z}$ consider ${\mathbb{Z}}_n:=\{0,1,\dots ,n-1\}$ such that $a{+}_{n}b:=(a+b)\mathrm{mod}n$, $a{\ast }_{n}b:=(a\ast b)\mathrm{mod}n$. Then $(\mathbb{Z},{+}_n,{\ast }_n)$ is a field iff $n$ is prime.

Vector Spaces.

Def. Let $F$ be a field with identity elements 0 and 1. A vector space over the field $F$ is a set $V$ with a mapping $+:V\times V\to V$ and $\ast :V\times V\to V$ then:

1. $(V,t)$ is a commutative group
2. Multiplicative identity : $\forall v\in Vi\ast v=v$
3. Distributive property : $\forall a,b\in F$ and $\forall u,v\in V$ such that $a(u+v)=au+av$ and $(a+b)u=au+bv$

Function Spaces:

${\mathbb{R}}^{\mathcal{X}}:=\{f:\mathcal{X}\to \mathbb{R}\}$ represents the space of all real valued functions on a set $\mathcal{X}$

$$\begin{array}{c}+:{\mathbb{R}}^{\mathcal{X}}\times {\mathbb{R}}^{\mathcal{X}}\to {\mathbb{R}}^{\mathcal{X}}\\ (f+g)(x):=f(x)+g(x)\\ \\ \ast :\mathbb{R}\times {\mathbb{R}}^{\mathcal{X}}\to {\mathbb{R}}^{\mathcal{X}}\\ (\lambda f)(x):=\lambda f(x)\end{array}$$

$\mathcal{C}(\mathcal{X}):=\{f:\mathcal{X}\to \mathbb{R}\mid f\text{ is constant}\}$

${\mathcal{C}}^r([a,b]):=\{f:[a,b]\to \mathbb{R}\mid f\text{ is r times continuous differentiable}\}$

Subspace.

Def. Let $V$ be a vector space, $U\subset V$ non-empty set, we call $U$ a subspace of $V$ if it is closed under linear combination:

$$\forall \lambda ,\mu \in F\forall u,v\in V\lambda u+\mu v\in U$$

Linear Combinations.

Def. $V$ vector space over $F$, $u_1,\dots ,u_n\in V$, ${\lambda }_1,\dots ,{\lambda }_n\in F$ then ${\sum }_{i=1}^n{\lambda }_i{v}_i$ is called a Linear Combination. The set of all linear combinations of $u_1,\dots ,u_n\in V$ is called the span (linear hull) of $u_1,\dots ,u_n\in V$.

$$\text{Span}(u_1,\dots ,u_n):=\left\{\sum _{i=1}^n{\lambda }_i{u}_i\mid {\lambda }_i\in F\right\}$$

The set $U:=\{u_1,\dots ,u_n\}$ is the generator of Span($u_1,\dots ,u_n$). To find good generators, we need to know what is linear independence and dependence.

Linear Independence.

Def. A set of vectors $v_1,\dots ,v_n$ is called linearly independent if ${\sum }_{i=1}^n{\lambda }_i{v}_i=0⟹{\lambda }_1={\lambda }_2=\cdots ={\lambda }_n=0$

Basis.

Def. A subset $B$ of a vector space $V$ is called a (Hamel) basis if:

1. $\text{Span}(B)=V$
2. $B$ is linearly independent

Proposition. If $U=\{u_1,\dots ,u_n\}$ spans a vector space $V$, then the set $U$ can be reduced to the basis of $V$.

Proof.

• If $U$ is already linearly independent : Done
• If $U$ is dependent : there exists $a\in U$ that is a linear combination of other vectors in $U$, we remove it.
• We keep removing all $a$ until the remaining set is linearly independent $■$

Def. A vector space is called finite dimensional if it contains a finite basis.

Prop. Let $U=\{u_1,\dots ,u_n\}\subset V$ be a set of linearly independent vectors and $V$ be a finite dimensional vector space, then $U$ can be extended to a basis of $V$.

Proof. (Sketch) Let $w_1,\dots ,w_n$ be basis of $V$. Consider the set $\{u_1,\dots ,u_n,w_1,\dots ,w_n\}$. Remove vectors from the set until remaining vectors are linearly independent.

Corollary. Let $V$ be a finite dimensional vector space then any two basis of $V$ have the same length.

Dimension.

Def. The length of the basis of a finite dimensional vector space is called the dimension of $V$.

Def. Assume that we have $U_1$, $U_2$ subspaces of $V$ , the sum of the two spaces is defined as :

$$U_1+U_2:=\{u_1+u_2\mid u_1\in U_1,u_2\in U_2\}$$

the sum is called the direct sum, if each element in the sum can be written in exactly one way.

$$U_1\oplus U_2\text{s.t.}{U}_1\cap U_2=\{0\}$$

This is a way of combining two (or more) subspaces into a larger vector space, in a way such that the decomposition of vectors is unique. For some vector space $V$ we can have have its unique $k$ constituents as follows:

$$\begin{array}{c}\forall v\in V,\exists u_1\in U_1,u_2\in U_2,\dots ,u_k\in U_k\text{ such that }v=\sum _{i=1}^k{u}_i\\ V=\underset{i=1}{\overset{k}{⨁}}{U}_i\end{array}$$

Prop. Suppose $V$ is finite dimensional and $U\subset V$ is a subspace the there exists a subspace $W\subset V$ such that $U\oplus W=V$.

Proof. (Sketch) Let $\{u_1,\dots ,u_n\}$ basis of $U$ extend it to a basis of $V$, say the resulting set is

$$\{\underset{U}{\underbrace{u_1,\dots ,u_n}},\underset{W}{\underbrace{v_1,\dots ,v_m}}\}$$

Define = $\text{Span}\{v_1,\dots ,v_m\}$

Linear Mapping.

Def. Let $U$, $V$ vector space over $F$, a mapping $T:U\to V$ is called a linear if $\forall v_1,v_2\in V$, $\forall \lambda \in F$

$$\begin{array}{c}f(u_1+u_2)=f(u_1)+f(u_2)\\ f(\lambda u_1)=\lambda f(u_1)\end{array}$$

the set of all linear mappings for $U\to V$ is denoted $\mathcal{L}(U,V)$. If $U\equiv V$ then $\mathcal{L}(U)$.

Def. $T\in \mathcal{L}(U,V)$ then kernel (nullspace) of $T$ is defined as $\text{ker}(T):=\text{null}(T):=\{u\in U\mid Tu=0\}$ (all points that the transformation $T$ maps to 0).

Prop.

• $\text{ker}(T)$ is a subspace of U.
• $T$ is injective iff $\text{ker}(T)=\{0\}$

Def. The range of $T$ is defined as $\text{range}(T):=\text{Im}(T):=\{Tu\mid u\in U\}$.

Prop. The range is always a subspace of $V$ ($T$ is surjective iff $\text{range}(T)=V$)

Def. For any set $V^{\prime }\subset V$, the pre-image of $V^{\prime }$ is defined as

$$T^{-1}(V^{\prime }):=\{u\in U\mid Tu\in V^{\prime }\}$$

Prop. If $V^{\prime }\subset V$ is a subspace of $V$, then $T^{-1}(V^{\prime })$ is a subspace of $U$

Theorem. Let $V$ be finite dimensional, $W$ any vector space, $T\in \mathcal{L}(V,W)$ Let $u_1,\dots ,u_n$ be a basis of $\text{ker}(T)\in V$ Let $w_1,\dots ,w_m$ be a basis of $\text{range}(T)\subset W$ Then $u_1,\dots ,u_n,T^{-1}(w_1),\dots ,T^{-1}(w_m)\subset V$ form a basis of $V$ In particular $\text{dim}(V)=\text{dim}(\text{ker}(T))+\text{dim}(\text{range}(T))$

Proof. Denote $z_1:=T^{-1}(w_1),\dots ,z_m:=T^{-1}(w_m)$ Step 1: $V\subset \text{Span}\{u_1,\dots ,u_n,z_1,\dots ,z_m\}$ let $v\in V$, consider $Tv\in \text{range}(T)$ $⟹\exists {\lambda }_1,\dots ,{\lambda }_m$ s.t. $Tv={\lambda }_1{w}_1+\cdots +{\lambda }_m{w}_m={\lambda }_{1}T(z_1)+\cdots +{\lambda }_{m}T(z_m)$ $⟹Tv=T({\lambda }_1{z}_1+\cdots +{\lambda }_m{z}_m)$ $⟹Tv-T({\lambda }_1{z}_1+\cdots +{\lambda }_m{z}_m)=0$ $⟹T(\underset{\in \text{ker}(T)}{\underbrace{v-({\lambda }_1{z}_1+\cdots +{\lambda }_m{z}_m)}})=0$ $\exists {\mu }_1,\dots {\mu }_n$ s.t. $v-({\lambda }_1{z}_1+\cdots +{\lambda }_m{z}_m)={\mu }_1{u}_1+\dots$ $⟹v=\underset{\text{range}}{\underbrace{{\lambda }_1{z}_1+\cdots +{\lambda }_m{z}_m}}+\underset{\text{ker}}{\underbrace{{\mu }_1{v}_1+\cdots +{\mu }_n{u}_n}}$ Step 2: $u_1,\dots ,u_n,z_1,\dots ,z_m$ are linearly independent Assume that ${\mu }_1{u}_1+\cdots +{\mu }_n{u}_n+{\lambda }_1{z}_1+\cdots +{\lambda }_m{z}_m=0$ —(i) ${\mu }_1{u}_1+\cdots +{\mu }_n{u}_n={\lambda }_{1}T(z_1)+\cdots +{\lambda }_{m}T(z_m)$ $={\lambda }_{1}T(z_1)+\cdots +{\lambda }_{m}T(z_m)+\underset{=0}{\underbrace{{\mu }_{1}T(u_1)+\cdots +{\mu }_{n}T(u_n)}}$ $T(\underset{=0\text{ by (i)}}{\underbrace{{\lambda }_1{z}_1+\cdots +{\lambda }_m{z}_m+{\mu }_1{u}_1+\cdots +{\mu }_n{u}_n}})=0$ ${\lambda }_1{w}_1+\cdots +{\lambda }_m{w}_m=0$ only if ${\lambda }_1=\cdots ={\lambda }_m=0$ since $w_1,\dots ,w_m$ are bases.

Prop. $T\in \mathcal{L}(V,W)$ where $V$, $W$ are finite dimensional. Then these following statements are equivalent

1. $T$ is injective
2. $T$ is surjective
3. $T$ is bijective

$$A=\left(\begin{array}{ccc}{a}_{11}& & a_{1n}\\ & & \\ a_{m1}& & a_{mn}\end{array}\right)=(a_{ij}{)}_{\begin{array}{c}\\ i=1,\dots ,m\\ j=1,\dots ,n\end{array}}$$

Consider $T\in \mathbb{L}(V,W)$, $V,W$ are finite dimensional

Let, $v_1,\dots ,v_n$ be a basis of $V$ $w_1,\dots ,w_m$ be a basis of $W$

• $V={\lambda }_1{v}_1+\cdots +{\lambda }_n{v}_n$ $T(v)=T({\lambda }_1{v}_1+\cdots +{\lambda }_n{v}_n)={\lambda }_{1}T(v_1)+\cdots +{\lambda }_{n}T(v_n)$

• Each image vector $T(v_j)$ can be expressed in basis $w_1,\dots ,w_m$ There exists coefficients $a_{1j},\dots ,a_{mj}$ such that $T(v_j)=a_{ij}{w}_1+\cdots +a_{mj}{w}_m$

• We may now stack these coefficients in a matrix: $m$ rows, one for each basis vector of $W$ $n$ columns, one for each basis vector of $V$ = matrix of mapping $T$ w.r.t. the basis $v_1,\dots ,v_n$ of $V$ and $w_1,\dots ,w_m$ of $W$

Notation: Let $T:V\to W$ be linear, let $B_V$ be a basis of $V$, $C_W$ basis of $W$. We denote by $M(T,B_V,C_W)$ the matrix corresponding to $T$ w.r.t bases $B_V$ and $C_W$.

Properties of Matrices.

Let $V$, $W$ vector spaces consider the basis fixed. Let $S,T\in \mathcal{L}(V,W)$

• $M(S+T)=M(S)+M(T)$
• $M(\lambda S)=\lambda M(S)$
• For $v={\lambda }_1{v}_1+\cdots +{\lambda }_n{v}_n$ we have that

$$\underset{\text{image of V under T}}{\underbrace{T(v)}}=\underset{matrixvectorproduct}{\underbrace{M(T)\left(\begin{array}{c}{\lambda }_1\\ \dots \\ {\lambda }_n\end{array}\right)}}$$

where $v_1,\dots ,v_n$ is basis of $V$.

• $T:U\to V$, $S:V\to W$ linear, then $M(S\circ T)=M(S)\cdot M(T)$