Mathematics for Machine Learning

Machine Learning is about desinging general-purpose methodologies that can be applied to many datasets and extract valuable patterns from data.

机器学习的核心概念：

数据 data
模型 model: 描述数据生成的过程，捕捉与建模相关的方面并从中提取模式
学习 learning: 训练一个模型是利用现有数据来最优化模型中的参数，使得该模型能在未知数据中表现良好 (在已知数据中表现良好仅仅代表着能够很好地记忆数据，而并非可以很好地泛化到位置数据中)

为了理解复杂机器学习系统中的基础原理，学习数学基础可以促进我们创造新的解决方案，理解并调试现有的解决方案，了解每种方法的假设前提和局限性。(下图简单展示了学习框架)

1. 线性代数

线性代数（Linear Algebra）旨在研究向量.一般地，向量常用字母表示（e.g. x, y）。

什么样的对象可以表示成向量？
当一个对象满足可以相加 & 可以与标量相乘的条件时，可以将其表示为向量，例如：

几何向量（geometric vectors）
多项式（polynomials）
音频信号（audio signals）
实数元组 $\mathrm R^n$：编程语言中可以用数组直观表示，便于算法实现，是本文探讨重点 $\mathbf a=\begin{bmatrix} 1 \\ 2 \\ 3 \\ \end{bmatrix} \in \mathrm R^3$

1.1 矩阵

矩阵（matrices）是常见的数学工具，它可以用来表示线性方程组也可以用来表示线性函数。

几种特殊的矩阵：

列向量（column vectors）：通常写为$x\in R^{n\times 1}或R^n$
行向量（row vectors）：通常写为$x^T\in R^{1\times n}或R^n$
方阵（square matrix）：$A\in R^{n\times n}$
单位矩阵（identity matrix）：正对角线上的元素为1，其余位置为0的方阵$I_n$

矩阵加法运算

矩阵求和等于对应位置上的元素相加。

$A + B := \begin{bmatrix} a_{11}+b_{11} & \cdots & a_{1n}+b_{1n} \\ \vdots & & \vdots \\ a_{m1}+b_{m1} & \cdots & a_{mn}+b{mn} \\ \end{bmatrix} \in R^{m\times n}$

矩阵乘法运算

乘积矩阵C中的元素$c_{ij}$是矩阵A的第i行和矩阵B的第j列对应乘积和。

为了使i行和j列能够一一对应相乘，必须保证A的列数和B的行数相同，这也是只有在矩阵相邻维度相同时才可以做乘法的原因。

$\begin{equation}\begin{split} & C = A\cdot B \quad A\in R^{m\times n}, B\in R^{n\times k}, C\in R^{m\times k}\\ &c_{ij} = \sum_{n}^{i=1}a_{il}b_{lj} \quad i=1,...m, j=1,...k \end{split}\end{equation}$

在编程语言中，两个多维数组相乘并不是计算矩阵乘积，而是对应位置元素相乘，这种乘法称为哈达玛积（Hadamard product）。

Example 矩阵乘法

$$AB = \begin{bmatrix} 1&2&3\\3&2&1\\\end{bmatrix}\begin{bmatrix} 0&2\\1&-1\\0&1\\\end{bmatrix}=\begin{bmatrix} 2&3\\2&5\\\end{bmatrix}\in R^{2\times 2}$$

矩阵转置运算

对于$A\in R^{m\times n}$，当$B\in R^{n\times m}$中所有元素满足$b_{ij}=a_{ji}$时，B称为A的转置（transpose）写作$A^T$。特别地，当$A=A^T$时，A称为对称方阵（symmetric matrix）。　

矩阵逆运算

对于方阵$A\in R^{m\times n}$，满足$AB=BA=I_n$的方阵B称为A的逆（inverse）写作$A^{-1}$。

只有方阵才有逆，一个方阵仅可能不存在逆或存在唯一逆。

存在唯一逆的方阵称为可逆的，正则的，非奇异的（invertible/regular/nonsingular）
不存在逆的方阵称为不可逆的，奇异的（noninvertible/singular）
可逆矩阵的转置也是可逆的

矩阵运算的性质

$I_mA=AI_n=A$
$AB\neq BA$
$(AB)^T=B^TA^T$
$(AB)^{-1}=B^{-1}A^{-1}$
$(AB)C=A(BC)$
$(A+B)C=AC+BC$
$(A+B)^T=A^T+B^T$
$(A^T)^T = A$
$(A^{-1})^T=(A^T)^{-1}=:A^{-T}$

1.2 线性方程组

现实生活中的许多问题可以抽象成线性方程组（Systems of Linear Equations），其一般的形式为：

$\begin{matrix} a_{11}x_1 & + ··· + & a_{1n}x_n & = & b_1 \\ & & & \vdots & \\ a_{m1}x_1 & + ··· + & a_{mn}x_n & = & b_m \\ \end{matrix}$

当$b_1,…b_m$均为0时，称为齐次线性方程组（homogeneous system of linear equations）。

二元线性方程组可以在平面坐标系中表示；类似的，三元线性方程组可以在空间坐标系中表示，每个方程代表一条直线，这些直线可能：

重合（无穷解）
相交（唯一解）
平行（无解）

Example 线性方程组的几何意义

$4x_1+4x_2=5$
$2x_1-4x_2=1$

在本例中两线性方程的交点为(1,0.25)，因此该方程组有唯一解(1,0.25)。

为了规范线性方程组的求解过程，通常将线性方程组压缩表达成：

向量式： $\sum_{n}^{i=1}x_ic_i=b$
矩阵式：$Ax=b $
增广矩阵（agumented matrix）：$[A|b]$ 省略变量x，合并矩阵A和b

Example 线性方程的三种表示方法

$$\begin{matrix}x_1 & + & 8x_3 & - & 4x_4 = & 42 & \;(1)\\x_2 & + & 2x_3 & + & 12x_4 = & 8 & \;(2)\\\end{matrix}$$向量式：$$\begin{bmatrix}1\\0\\\end{bmatrix} x_1 +\begin{bmatrix}0\\1\\\end{bmatrix} x_2 +\begin{bmatrix}8\\2\\\end{bmatrix} x_3 +\begin{bmatrix}-4\\12\\\end{bmatrix} x_4 =\begin{bmatrix}42\\8\\\end{bmatrix}$$矩阵式：$$\begin{bmatrix} 1&0&8&-4\\0&1&2&12\\\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\\x_4\\\end{bmatrix}=\begin{bmatrix}42\\8\\\end{bmatrix}$$增广矩阵：$$\left[ \begin{array}{cccc|c} 1&0&8&-4&42\\ 0&1&2&12&8 \end{array}\right]$$

1.3 求解线性方程组

从矩阵的角度看待线性方程组，我们只需要解Ax=b：

$Ax=b \to A^TAx=A^Tb \to x=(A^TA)^{-1}A^Tb$

显然这种方法涉及的计算量是非常大的。
求解线性方程组的一般方法是高斯消元法（Gaussian elimination）。

Step1
利用初等变换（elementary transformation）将增广矩阵简化成梯形矩阵（row-echelon form）。
初等变换涉及到的操作有：两行互换，行与行之间的加减乘除运算；

简化后得到的梯形矩阵需要满足：

全部为0的行在矩阵最底部，其余非0行在顶部；
从左侧开始的第一个非0数称为这一行的轴（pivot），对于任意非0行，它的轴总是在上一行的轴的右侧；

梯形矩阵中轴所对应的变量称为基本变量（basic variable），其余变量称为自由变量（free variable）。

Step2
为了求得方程组的一个特解（particular solution），我们需要取轴所在的列（也称为枢列），使得这些列与基本变量的乘积和等于b，求出基本变量的特解，并取自由变量的特解为0，最终得到一个特解。

Step3
最后，为了求方程组的通解（general solution），我们需要将将梯形矩阵转化为阶梯型矩阵进而求Ax=0的通解。

当一个梯形矩阵满足以下两个条件时，称为阶梯型矩阵（REF: reduced row-echelon form）

所有的轴均为1
所有枢列中，除了轴外其他数字均为0
转化成功后，将所有非枢列表示成其左侧的枢列的倍数，最后在特解的基础上添加包含自由变量的条件表达式；

计算通解的简便方法 The Minus 1 Trick

对于REF，通过添加n行来使其成为一个对角线上的元素均为1或-1的方阵，每个添加的行中仅有一个元素为-1，其余均为0；
在特殊方阵中，-1所在的列即是Ax=0的通解；

Example 利用高斯消元法求解线性方程组

$$\begin{equation}\begin{split}&\left[ \begin{array}{ccccc|c} -2&4&-2&-1&4&-3\\ 4&-8&3&-3&1&2\\ 1&-2&1&-1&1&0\\ 1&-2&0&-3&4&a \end{array}\right]&\begin{array}{ccccc|c}swap with R_3\\\\swap with R_1\\\\\end{array} &\to \\\\&\left[ \begin{array}{ccccc|c} 1&-2&1&-1&1&0\\ 4&-8&3&-3&1&2\\ -2&4&-2&-1&4&-3\\ 1&-2&0&-3&4&a \end{array}\right]&\begin{array}{ccccc|c}\\-4R_1\\+2R_1\\-R_1\\\end{array} &\to\\\\&\left[ \begin{array}{ccccc|c} 1&-2&1&-1&1&0\\ 0&0&-1&1&-3&2\\ 0&0&0&-3&6&-3\\ 0&0&-1&-2&3&a \end{array}\right]&\begin{array}{ccccc|c}\\\\\\-R_2-R_3\\\end{array} &\to\\\\&\left[ \begin{array}{ccccc|c} 1&-2&1&-1&1&0\\ 0&0&-1&1&-3&2\\ 0&0&0&-3&6&-3\\ 0&0&0&0&0&a+1 \end{array}\right]&\begin{array}{ccccc|c}\\\\·(-1)\\·(-\frac {1}{3})\\\end{array} &\to\\\\&\left[ \begin{array}{ccccc|c} 1&-2&1&-1&1&0\\ 0&0&1&-1&3&-2\\ 0&0&0&1&-2&1\\ 0&0&0&0&0&a+1 \end{array}\right]\end{split}\end{equation}$$到此为止，增广矩阵已经变换成为梯形矩阵，且基本变量为$x_1,x_3,x_4$，自由变量为$x_2,x_5$。不难发现，只有当a=-1时，此方程组才有解。下面求解该方程组的一个特解：$$x_1\begin{bmatrix}1\\0\\0\\0\end{bmatrix}+x_3\begin{bmatrix}1\\1\\0\\0\end{bmatrix}+x_4\begin{bmatrix}-1\\-1\\1\\0\end{bmatrix}=\begin{bmatrix}0\\-2\\1\\0\end{bmatrix}$$很容易找到一组特解$x=[2,0,-1,1,0]^T$。为了求得通解，需要将其进一步变换为阶梯型矩阵：$$\begin{equation}\begin{split}&\left[ \begin{array}{ccccc} 1&-2&1&-1&1\\ 0&0&1&-1&3\\ 0&0&0&1&-2\\ 0&0&0&0&0 \end{array}\right]&\begin{array}{ccccc}-R_2\\\\\\\\\end{array} &\quad\to \\\\&\left[ \begin{array}{ccccc} 1&-2&0&0&-2\\ 0&0&1&-1&3\\ 0&0&0&1&-2\\ 0&0&0&0&0 \end{array}\right]&\begin{array}{ccccc}\\+R_3\\\\\\\end{array} &\quad\to \\\\&\left[ \begin{array}{ccccc} 1&-2&0&0&-2\\ 0&0&1&0&1\\ 0&0&0&1&-2\\ 0&0&0&0&0 \end{array}\right]\end{split}\end{equation}$$进而，对于非枢列C2,C5而言： $$\begin{equation}\begin{split}&C_2=-2C_1 \quad &\Rightarrow \quad 0 = 2C_1+C_2+0C_3+0C_4+0C_5 \\\\&C_5=-2C_1+C_3-2C_4 \quad &\Rightarrow \quad 0 = 2C_1+0C_2-C_3+2C_4+C_5\end{split}\end{equation}$$或者通过简便算法将REF补充为5x5的特殊方阵：$$\left[ \begin{array}{ccccc} 1&-2&0&0&-2\\ 0&-1&0&0&0\\ 0&0&1&0&1\\ 0&0&0&1&-2\\ 0&0&0&0&-1 \end{array}\right]$$因此，该线性方程组的通解为：$$x \in R^5:\quad x= \begin{bmatrix}2\\0\\-1\\1\\0 \end{bmatrix} +\lambda_1 \begin{bmatrix}-2\\-1\\0\\0\\0 \end{bmatrix}+\lambda_2\begin{bmatrix}-2\\0\\1\\-2\\-1 \end{bmatrix}, \quad \lambda_1,\lambda_2 \in R$$

此外，高斯消元法还可以求解逆矩阵中：

为了求$AX=I=XA^{-1}$, 我们可以将其写成增广矩阵的形式即$[A|I]$，通过消元将其变为$[I|A^{-1}]$，进而得到逆矩阵。

Example 利用高斯消元法求解逆矩阵

$$A=\begin{bmatrix}1&0&2&0\\1&1&0&0\\1&2&0&1\\1&1&1&1\end{bmatrix}$$$$\left[ \begin{array}{cccc|cccc} 1&0&2&0&1&0&0&0\\ 1&1&0&0&0&1&0&0\\ 1&2&0&1&0&0&1&0\\ 1&1&1&1&0&0&0&1 \end{array}\right] \quad \to \quad\left[ \begin{array}{cccc|cccc} 1&0&0&0&-1&2&-2&2\\ 0&1&0&0&1&-1&2&-2\\ 0&0&1&0&1&-1&1&-1\\ 0&0&0&1&-1&0&-1&2 \end{array}\right]$$

然而，在实践中，高斯消元法并非是求解线性方程组的最优解（当变量数非常庞大时，计算量会随着方程数量的增加按立方倍递增）；
有两类方法可以间接的解决这个问题：

平稳迭代法（stationary iterative methods）
子空间法（Krylov subspace methods）

1.4 向量空间

开始时我们介绍了向量，为了规范向量的定义，我们需要引入群和向量空间的定义：
当一个集合$\mathscr G$ 和一个二元运算$\oplus$ 满足以下4条性质时，称$G:=(\mathscr G,\oplus)$为一个群（group）：

封闭性（closure）：$\forall x,y \in \mathscr G,\; x\oplus y \in \mathscr G$
结合性（associativity）：$\forall x,y,z\in \mathscr G,\; (x\oplus y)\oplus z = x(y \oplus z)$
中性元素（neutral element）：$\exists e \in \mathscr G,\forall x \in \mathscr G \; e\oplus x = x\oplus e = x$
逆元素（inverse element）：$\forall x \in \mathscr G, \exists x^{-1}\in \mathscr G \; x\oplus x^{-1}=x^{-1}\oplus x = e$

特别的，当一个群还满足交换性（commutative）时，称为阿贝尔群（Abelian group）：

$\forall x,y \in \mathscr G, \; x\oplus y = y\oplus x$

特别的，当集合A是所有可逆方阵的集合时，称为一般线性群（General Linear Group），记为GL(n,R)；

	封闭性	结合性	中性元素	逆元素	交换性	群
$(Z,+)$	✔	✔	0	✔	✔	Abelian
$(Z,·)$	✔	✔	1	✖	✔	✖
$(R,·)$	✔	✔	1	✖	✔	✖
$(R^n,+)$	✔	✔	$(0,…,0)^T$	✔	✔	Abelian
$(R^{m\times n},+)$	✔	✔	m×n的零矩阵	✔	✔	Abelian
$(R^{n\times n},·)$	✔	✔	$I_n$	✖	✖	✖
$GL(n,R) $	✔	✔	$I_n$	✔	✖	✔

向量空间由集合$\mathscr V$，加法运算和乘法运算组成的：

$+: \mathscr V \times \mathscr V \to \mathscr V$ $·: R \times \mathscr V \to \mathscr V$

$(\mathscr V,+)$是一个阿贝尔群
这里的乘法可以看做一个外部运算，即来自内部集合的向量与来自外部实数集合的标量相乘，如果是两个向量相乘，那么$a^Tb\in R$称为内积或点积（inner/dot product），而$ab^T\in R^{n\times n}$称为外积（outer product）
满足分配律： $\forall \lambda \in R, x,y\in \mathscr V: \lambda(x+y)=\lambda x+\lambda y$
满足结合律： $\forall \lambda,\phi \in R, x\in \mathscr V: \lambda(\phi x)=(\lambda\phi) x$

子空间向量

当集合$\mathscr U$是$\mathscr V$的非空子集且仍然满足以下条件时，称$(\mathscr U,+,·)是一个子空间向量$：

$0\in U$
仍满足封闭性： $+: \mathscr U \times \mathscr U \to \mathscr U$ $·: R \times \mathscr U \to \mathscr U$

Example 子空间向量的定义

1. V和{0}一定是V的子空间2. 任意子空间的交集也一定是子空间3. 齐次线性方程组Ax=0的解空间$[x_1,...,x_n]^T是R^n$的子空间，而非齐次线性方程组的解空间并不是$R^n$的子空间4. 任何的子空间都一定是某个齐次线性方程组的解5. 下列集合中，只有D可以看做$R^2$的子空间，A,C不满足封闭性，B中不包含0 （二元齐次线性方程组的解空间实际上是由若干条经过原点的直线组成的）

1.5 线性独立

一个向量v可以由多个向量组成的，比如：

$v = \lambda_1 x_1 + ... + \lambda_k x_k \in V$

则v是这些向量$x_1,x_k$的线性组合；
显然，零向量可以是任何向量的线性组合（令标量均为0），但是如果存在一组标量，使得这些标量中至少有一个不为0且它们仍然能线性组合为0向量，那么则称$x_1,…,x_k$是线性依赖的（linear dependent），否则他们是先行独立的（linear independent）。

线性独立的向量集中是没有冗余的，其中的每一个向量是不可或缺的。

Example 线性独立的意义

在地图中，我们可以用两种方法描述Kigali在Nairobi的位置： 1. 向西北走506km再向西南走374km2. 向西走751km在第一种描述中，这两个向量是线性独立的，缺少任何一个都无法描述清楚，而在第二种描述中，这个向量是线性依赖于前两个向量的。

那么当给定一个向量集，如何判断他们是否先行独立呢？

如果向量集中存在0向量或两个相同的向量，那么一定是线性依赖的；
如果向量集中的某个向量可以写成其他向量的线性组合，那么一定是线性依赖的；
如果1，2都不满足，那么需要将向量写成矩阵A，用高斯消元法将其转换为梯形矩阵：对于非枢列，该向量可以被表示为其左侧向量的倍数，因此只有当梯形矩阵中仅存在枢列时，他们才是先行独立的；

Example 线性独立的判断

对于向量集：$$x_1=\begin{bmatrix}1\\2\\-3\\4\end{bmatrix} \quad x_2=\begin{bmatrix}1\\1\\0\\2\end{bmatrix} \quad x_3=\begin{bmatrix}-1\\-2\\1\\1\end{bmatrix}$$ 将其写为矩阵式，在转换为梯形矩阵：$$\begin{bmatrix}1&1&-1\\2&1&-2\\-3&0&1\\4&2&1\end{bmatrix} \to\begin{bmatrix}1&1&-1\\0&1&0\\0&0&1\\0&0&0\end{bmatrix}$$由此可见，三列均为枢列（轴所在的列），因此他们是线性独立的。对于由上面三个线性独立向量通过线性组合形成的向量集：$$\begin{equation}\begin{split}&a_1 = x_1 - 2x_2 + x_3 \\&a_2 = -4x_1 -2x_2 \\&a_3 = 2x_1+3x_2 -x_3 \\&a_4 = 17x_1 - 10x_2 + 11x_3\end{split}\end{equation}$$同理，也是将其转换为梯形矩阵：$$\begin{bmatrix}1&-4&2&17\\-2&-2&3&-10\\1&0&-1&11\end{bmatrix} \to\begin{bmatrix}1&0&-1&11\\0&2&-1&-12\\0&0&1&-18\end{bmatrix}$$显然，该向量集是线性依赖的，因为$a_4=-(7a_1+15a_2+18a_3)$

1.6 基与秩

向量空间中是否有一组向量集可以通过线性组合成其他任意向量呢？
答案是肯定的，这组向量集称为生成集（generating sets），记为$V=span[x_1,…,x_n]$。
为了缩小这些项量范围，当生成集最小时（即生成集是线性独立的），称为向量空间的基（basis）。

由此可见，基并不是唯一的，但是对于一个向量空间而言，任何基中的向量数量都是确定的，我们称之为该空间的维度，记为dim(V)；V的子空间U的维度一定是小于V的（设U≠V）。在图形中，空间维度的定义与其相吻合，即独立的方向。

例如，在$R^3$中，标准基（standard basis）是：

$\mathscr B = \begin{Bmatrix} \begin{bmatrix}1\\0\\0\end{bmatrix},\; \begin{bmatrix}0\\1\\0\end{bmatrix},\; \begin{bmatrix}0\\0\\1\end{bmatrix} \end{Bmatrix}$

其他的基例如：

$\mathscr B_1 = \begin{Bmatrix} \begin{bmatrix}1\\0\\0\end{bmatrix},\; \begin{bmatrix}1\\1\\0\end{bmatrix},\; \begin{bmatrix}1\\1\\1\end{bmatrix} \end{Bmatrix}\quad \mathscr B_2 = \begin{Bmatrix} \begin{bmatrix}0.5\\0.8\\0.4\end{bmatrix},\; \begin{bmatrix}1.8\\0.3\\0.3\end{bmatrix},\; \begin{bmatrix}-2.2\\-1.3\\3.5\end{bmatrix} \end{Bmatrix}$

Example 计算生成集的基

$$x_1=\begin{bmatrix}1\\2\\-1\\-1\\-1\end{bmatrix}\quad x_2=\begin{bmatrix}2\\-1\\1\\2\\-2\end{bmatrix}\quad x_3=\begin{bmatrix}3\\-4\\3\\5\\-3\end{bmatrix}\quad x_4=\begin{bmatrix}-1\\8\\-5\\-6\\1\end{bmatrix}$$给定一个生成集，要缩小到最小，那么只需判断集合中是否存在某种线性依赖，利用高斯消元法判断：$$[x_1,x_2,x_3,x_4]=\begin{bmatrix}1&2&3&-1\\2&-1&-4&8\\-1&1&3&-5\\-1&2&5&-6\\-1&-2&-3&1\end{bmatrix} \to\begin{bmatrix}1&2&3&-1\\0&1&2&-2\\0&0&0&1\\0&0&0&0\\0&0&0&0\end{bmatrix}$$显然，$x_1,x_2,x_4$是线性独立的，因此该集合的基为{$x_1,x_2,x_4$}

矩阵中线性独立的行和列的数量是相等的，称为矩阵的秩（rank），记为rk(A)，秩还伴随着许多有趣的性质：

$rk(A) = rk(A^T)$
由矩阵中的列所生成的向量空间$U：dim(U)=rk(A)$, 且该空间的基=$A$的基
由矩阵中的行所生成的向量空间$W：dim(W)=rk(A)$, 且该空间的基=$A^T$的基
iff rk(A^{n\times n})=n, A是正则的（可逆的）
线性方程组Ax=b有解当且仅当$rk(A)=rk(A|b)$, 线性方程组Ax=0的解空间的子空间的秩为n-rk(A)
当rk(A)=min(m,n)，A是满秩的（full rank），否则称为不满秩的（rank deficient）

Example 计算矩阵的秩

$$A = \begin{bmatrix}1&2&1\\-2&-3&1\\3&5&0\end{bmatrix} \to\quad \begin{bmatrix}1&2&1\\0&1&3\\0&0&0\end{bmatrix}\quad rk(A)=2$$

To be continued...