Skip to content

Lecture 2: 数学基础

一些机器学习需要用到的前置数学知识（并非非常基础，特别是凸优化）

符号定义

  • \([n]\)：从 \(1\) 到 \(n\) 的正整数集合 \(\lbrace1, \cdots, n\rbrace\)
  • \(\mathbf{x}, \mathbf{y}, \mathbf{v}\)：向量 vector
  • \(A, B\)：矩阵 matrix
  • \(\mathcal{X}, \mathcal{Y}, \mathcal{K}\)：域 domain
  • \(d, m, n\)：维度 dimension
  • \(I\)：单位矩阵 identity matrix
  • \(X, Y\)：随机变量 random variable
  • \(p, q\)：概率分布 probability distribution

微积分

Definition：连续函数

函数 $ f : \mathbb{R}^n \to \mathbb{R}^m $ 在 $ x \in \text{dom } f $ 处连续，如果对于所有 $ \epsilon > 0 $，存在一个 $ \delta > 0 $，使得对于任意 $ y \in \text{dom } f $，有 $$ \lVert y - x \rVert_2 \leq \delta \quad \implies \quad \lVert f(y) - f(x) \rVert_2 \leq \epsilon. $$ 其中 \(\lVert \cdot \rVert_{2}\) 被称为欧几里得范数（Euclidean norm），几何上表示“两点间距离”。很快会提到其他范数

一阶概念：梯度与导数

如果 \(f:\mathbb{R} \to \mathbb{R}\)，那么梯度（Gradient）和导数（Derivatives）等价

如果 \(f:\mathbb{R}^d \to \mathbb{R}\)，即输入是 \(d\) 维向量，则定义梯度：

Definition：梯度

设 $ f : \mathcal{X} \subseteq \mathbb{R}^d \to \mathbb{R} $ 是一个一阶可导函数。令 \(\mathbf{x} = [x_1, \cdots, x_d]^{\top} \in \mathcal{X}\)。那么，$ f $ 在 $ \mathbf{x} $ 处的梯度是一个 $ \mathbb{R}^d $ 中的列向量，记作 $ \nabla f(\mathbf{x}) $，其定义为
$$ \nabla f(\mathbf{x}) = \begin{bmatrix} \frac{\partial f}{\partial x_1}(\mathbf{x}) \\ \vdots \\ \frac{\partial f}{\partial x_d}(\mathbf{x}) \end{bmatrix} $$

Example: \(f(x) = \lVert\mathbf{x}\rVert_{2}^{2} \overset{\triangle}{=} \sum_{i=1}^{d} x_{i}^{2}\)，则 $$ \nabla f(x) = \begin{bmatrix} 2x_{1} \\ \vdots \\ 2x_{n} \end{bmatrix} = 2\mathbf{x} $$

而导数为梯度的转置（行向量）。这门课关注的是梯度

二阶概念：Hessian 矩阵

Definition：Hessian 矩阵

设 $ f : \mathcal{X} \subseteq \mathbb{R}^d \to \mathbb{R} $ 是一个二阶可导函数。令 \(\mathbf{x} = [x_1, \cdots, x_d]^{\top} \in \mathcal{X}\)。那么，$ f $ 在 $ \mathbf{x} $ 处的 Hessian 矩阵是一个 $ \mathbb{R}^{d \times d} $ 中的方阵，记作 $ \nabla ^{2} f(\mathbf{x}) $，其定义为
$$ \nabla^{2} f(\mathbf{x}) = \begin{bmatrix} \frac{\partial ^{2} f}{\partial x_{i}, x_{j}}(\mathbf{x}) \end{bmatrix} _{1 \le i, j \le d} $$

Example: 信息论中的负熵函数 \(f(x) = -\sum_{i=1}^{d} x_{i} \ln x_{i},\; x_{i} > 0\)，则 $$ \nabla^{2} f(x) = \text{diag} \left( -\dfrac{1}{x_{1}}, \cdots, -\dfrac{1}{x_{d}} \right) $$

对于二阶偏导数连续的函数（称为 \(C^2\) 函数），得到的 Hessian 矩阵是对称矩阵

链式法则

Rule：链式法则

对于 \(h(x) = f \circ g (x)\)，有： $$ \begin{align} h'(x) &= f'(g(x)) \cdot g'(x) \\ h''(x) &= f''(g(x)) (g'(x))^{2} + f'(g(x)) g''(x) \end{align} $$ 对于 \(n\) 阶可导函数 \(h_{n}(x) = f_{n} \circ f_{n-1} \circ \cdots \circ f_{1} (x)\)，有： $$ \dfrac{\text{d}h_{n}}{\text{d}x} = \dfrac{\text{d}h_{n}}{\text{d}h_{n-1}} \cdot \dfrac{\text{d}h_{n-1}}{\text{d}h_{n-2}} \cdots \dfrac{\text{d}h_{1}}{\text{d}x} $$

链式法则解释了如何对复合函数求导，在机器学习中的一个应用是实现反向传播算法（Backpropagation）

《The Matrix Cookbook》

一本关于矩阵运算、矩阵微积分以及相关统计分布的公式速查手册，电子版可以看这里

线性代数

最基础的矩阵运算和性质这里从略

（半）正定矩阵

Definition：（半）正定矩阵

对于一个实对称方阵 \(A \in \mathbb{R}^{d\times d}\)：

  • 如果取任意 \(d\) 维非零向量 \(\mathbf{x} \ne 0\)，都有 \(\mathbf{x}^{T}A\mathbf{x} > 0\)，则 \(A\) 是正定矩阵（Positive Definite Matrix），记为 \(A \succ 0\)
  • 如果取任意 \(d\) 维向量 \(\mathbf{x} \in \mathbf{R}^{d}\)，都有 \(\mathbf{x}^{T}A\mathbf{x} \ge 0\)，则 \(A\) 是半正定矩阵（Positive Semi-Definite Matrix），记为 \(A \succeq 0\)

如果一个函数的 Hessian 矩阵是半正定矩阵，则该函数为凸函数（很快说明）

秩

对于一个矩阵 \(A \in \mathbb{R}^{m \times n}\)，将每一列视为一个 \(m\) 维向量，这 \(n\) 个向量可以组成一个线性空间，称为列空间 \(\text{Col}(A)\)，它是 \(\mathbb{R}^{m}\) 的一个子空间，这个子空间的实际维度就是秩（Rank）

从线性独立的角度理解，矩阵的秩就是最大线性无关列的数量，即：在 \(n\) 个 \(m\) 维向量中，去除可被其他向量线性表示的重复向量后，得到的向量集合的大小

从历史悠久的线代笔记上抄下来的常用秩不等式，感觉对这门课没什么大用

💠 对于\(n\)阶方阵 \(A,B\)，\(AB=O\)，则 \(r(A)+r(B) \leqslant n\)

证明：\(Ax=θ\)，方程的基础解系所含向量的个数是 \(n-r(A)\)，而矩阵 \(B\) 的各个列向量就对应了 \(x\)，故 \(B\) 的列秩 \(r(B)\leqslant n - r(A)\)（\(B\) 的列向量组的秩不可能超过方程基础解系的个数）

（下面的右侧不等式是其更一般的结论）

💠 \(min\lbracer(A),r(B)\rbrace \geqslant r(AB) \geqslant r(A)+r(B) - n\)（矩阵乘法 \(AB\) 存在，\(n\) 是 \(A\) 的列 / \(B\) 的行数）

先证左侧不等式：

易知 \(Ax=0\) 的解一定是 \(ABx=0\) 的解，\(ABx=0\) 的解向量个数 \(\geqslant\) \(Ax=0\) 的解向量个数

\(n-r(AB) \geqslant n-r(A)\)，即 \(r(AB) \leqslant r(A)\)

同理 \(r(AB) \leqslant r(B)\)，故 \(r(AB) \leqslant min\lbracer(A),r(B)\rbrace\)

再证右侧不等式：

\(r(A) + r(B) = r \begin{pmatrix}B & O\\O &A\end{pmatrix} \leqslant r\begin{pmatrix}B & E\\O &A\end{pmatrix} =r\begin{pmatrix}B & E\\-AB &O\end{pmatrix} \leqslant r(AB) + r(E)\)

（行变换有 \(\begin{pmatrix}E & O\\-A &E\end{pmatrix} \begin{pmatrix}B & E\\O &A\end{pmatrix} =\begin{pmatrix}B & E\\-AB &O\end{pmatrix}\)）

（\(r\begin{pmatrix}B & E\\-AB &O\end{pmatrix} \leqslant r(AB) + r(E)\) 可以从列向量的相关性证明）

（\(r(A) + r(B) = r \begin{pmatrix}B & O\\O &A\end{pmatrix}\leqslant r\begin{pmatrix}B & E\\O &A\end{pmatrix}\) 本身就是个很好的不等式）

💠 对于 \(n\) 阶方阵 \(A\) ，有 \(r(A^{\ast})=\begin{cases} n,\, & r(A)=n \\ 1,\, & r(A)=n-1 \\ 0,\, & r(A) \leqslant n-2 \end{cases}\)

证明：易知 \(|A^{\ast}|=||A|A^{-1}|=|A|^n|A^{-1}|=|A|^{n-1}\)

\(r(A)=n\) 时，\(|A| ≠0\)，所以 \(|A^{\ast}|=|A|^{n-1}≠0\)，因此 \(A^{\ast}\) 满秩，\(r(A^{\ast})=n\)

\(r(A)=n-1\) 时，\(AA^{\ast}=|A|E=0\)

由上一个结论可得：\(r(A)+r(A^{\ast}) \leqslant n\)，故 r\((A^{\ast}) \leqslant n - r(A) = 1\)

又因为 \(A\) 不是零矩阵（秩不为 \(0\)），故 \(A^{\ast}\) 也不是零矩阵，\(r(A^{\ast}) \geqslant 1\)

故\(r(A^{\ast}) = 1\)

\(r(A) \leqslant n-2\) 时，\(A\) 的 \((n-1)\) 阶子式的值也全部为 \(0\)，这意味着\(A\) 的代数余子式 \(A_{ij} = 0\)

因此 \(A^{\ast}\) 的所有项全部为 \(0\)，\(A^{\ast}\) 是零矩阵，\(r(A^{\ast}) = 0\)

💠 \(r(A±B) \leqslant r(A)+r(B)\)

（考虑 \(A\) 与 \(B\) 的列空间可能有重合，直接得出不等关系）

💠\(max\lbracer(A),r(B)\rbrace\leqslant r(A\quad B)\leqslant r(A)+r(B)\)

（依旧是考虑 \(A\) 与 \(B\) 的列空间可能有重合，直接得出不等关系）

💠 \(r(A)=r(PAQ)\)，其中 \(P、Q\) 满秩

（初等变换不改变矩阵的秩）

💠 \(r(A)=r(AA^T)=r(A^TA)\)（其中 \(A\) 是实矩阵）

（证明 \(Ax=0\) 与 \(A^TAx=0\) 与 \(AA^Tx=0\) 同解即可）

💠\(r(A)=r\begin{pmatrix}A &AB\end{pmatrix} = r\begin{pmatrix}A \\B A\end{pmatrix}\)

（左乘矩阵进行行变换，对列向量的线性相关性没有任何影响，有 \(r(A)= r\begin{pmatrix}A \\B A\end{pmatrix}\)）

（右乘矩阵进行列变换，对行向量的线性相关性没有任何影响，有 \(r(A)=r\begin{pmatrix}A &AB\end{pmatrix}\)）

（考虑线性方程组的基础解系也可以解决问题）

内积 && 向量范数

内积（Inner Product）是一个输入为两个向量，输出为一个标量的函数。

分为向量内积和矩阵内积，其中对于向量空间下的内积，采用点积的计算方式；对于矩阵空间下的内积，采用”将矩阵拉长为长向量进行点积计算“的处理方式，称为 Frobenius 内积，本质上都是对向量的计算

Definition：内积

对于向量 \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^d\)，定义内积运算： $$ \left \langle \mathbf{x}, \mathbf{y} \right \rangle = \mathbf{x}^{T} \mathbf{y} = \sum_{i=1}^{d} x_i y_i $$ 另一种写法是 \(\left \langle \mathbf{x}, \mathbf{y} \right \rangle = \lVert x \rVert \lVert y \rVert \cos \theta\)，其中 \(\theta\) 是向量角

对于矩阵 \(A, B \in \mathbb{R}^{m \times n}\)，定义内积运算： $$ \left \langle A, B \right \rangle = \text{Tr}\left( A^{T}B \right) = \sum_{i=1}^{m} \sum_{j=1}^{n} A_{ij} B_{ij} $$

向量内积反映两个向量的对齐程度：考虑 \(\left \langle \mathbf{x}, \mathbf{y} \right \rangle = \lVert x \rVert \lVert y \rVert \cos \theta\) 这种写法，内积的大小与向量长度成正比，和 \(\theta\) 成反比

同理，Frobenius 内积的计算结果衡量两个矩阵的相似性，常用于矩阵优化和分解问题中

给定一种内积运算，可以诱导出对应的范数（Norm）计算。给出向量的 \(p\)-范数的定义：

Definition：向量范数

对于向量 \(\mathbf{x}\)，我们定义： $$ \lVert \mathbf{x} \rVert_{p} = (|x_1|^{p} + |x_2|^{p} + \cdots + |x_d|^{p})^{1/p} $$ 为向量的 \(p\)-范数，其中：

  • \(ℓ_1\)-范数 \(\lVert \mathbf{x} \rVert_{1} = |x_1| + |x_2| + \cdots + |x_d|\)，又称之为曼哈顿范数，表示向量各分量绝对值的和
  • \(ℓ_2\)-范数 \(\lVert \mathbf{x} \rVert_{2} = \sqrt{x_1^2 + x_2^2 + \cdots + x_d^2}\)，又称之为欧几里得范数，表示向量长度
  • \(ℓ_{\infty}\)-范数 \(\lVert \mathbf{x} \rVert_{\infty} = \max\lbrace|x_1|, |x_2|, \cdots , |x_d|\rbrace\)，又称之为无穷范数，表示向量在所有维度中的最大偏差

额外的，给定半正定矩阵 \(A \in \mathbb{R}^{d\times d}\)，我们定义 \(\lVert x \rVert_{A} = \sqrt{x^{T} A x}\) 为二次范数（Quadratic norm），也称为马氏距离

范数可以表示一个向量的“大小”；内积可以表示两个向量的几何对齐程度。每种内积运算都可诱导出对应的范数（一个向量和自己进行内积运算后取根号 \(\sqrt{\langle \mathbf{x}, \mathbf{x} \rangle}\) 就是对应的范数计算 \(\lVert \mathbf{x} \rVert\)），但并不是每种范数都来自于一个内积

对偶范数

Definition：对偶范数

给定一种 \(\mathbb{R}^{d}\) 上的向量范数 \(\lVert \cdot \rVert\)，我们定义对应的对偶范数 \(\lVert \cdot \rVert_{\ast}\)： $$ \lVert \mathbf{y} \rVert_{\ast} = \max_{\lVert \mathbf{x} \rVert} \langle \mathbf{y}, \mathbf{x} \rangle = \text{sup} \lbrace\mathbf{y}^{T}\mathbf{x} | \lVert \mathbf{x} \rVert \leq 1\rbrace $$

// TBD