线性代数

标量、向量、矩阵和张量

  • 标量：一个单独的数
  • 向量：一列数
  • 矩阵：二维数组
  • 张量：维数超过二维的数组
  • 转置：矩阵的行列互换

矩阵与向量相乘

单位矩阵和逆矩阵

  • 单位矩阵：主对角线元素都是1
  • 逆矩阵：$\boldsymbol{A}^{-1}\boldsymbol{A}=\boldsymbol{I}$

线性相关与生成子空间

  • 将 $\boldsymbol{A}$ 的列向量看作是从原点出发的向量，则 $\boldsymbol{A}\boldsymbol{x} = \sum_{i} x_{i}\boldsymbol{A}_{:,i}$（称为线性组合），一组向量的线性组合所能及的点的集合就是这组向量的生成子空间
  • 线性相关：向量组某向量能用组内其他向量线性表示
  • 线性无关：向量组的每个向量都是组内其他向量无法线性组合表示的
  • 列向量线性相关的方阵被称为是 奇异的

范数

  • 范数是满足下列性质的函数：
    • $f(\boldsymbol{x})=0 \Rightarrow \boldsymbol{x = 0} $
    • $f(\boldsymbol{x+y}) \le f(\boldsymbol{x}) + f(\boldsymbol{y}) $
    • $\forall \alpha \in \mathbb{R}, f(\alpha \boldsymbol{x})=|\alpha|f(\boldsymbol{x})$
  • $L^p$范数：
    • $||\boldsymbol{x}||_p=\left(\sum_i|x_i|^p\right)^{\frac{1}{p}}\quad p \in \mathbb{R},p \ge 1$
  • $L^0$范数：向量中非零元素的个数
  • $L^\infty$范数：向量中最大幅值元素的绝对值
    • $||\boldsymbol{x}||_\infty=\text{max}_i|x_i|$
  • 矩阵的F范数：
    • $ ||\boldsymbol{A}||_{F} = \sqrt{ \sum _{i,j} A ^2 _{i,j} }$
  • 两个向量的点积用范数表示：
    • $\boldsymbol{x}^T\boldsymbol{y}=||\boldsymbol{x}||_2||\boldsymbol{y}||_2\text{cos}\theta$

特殊类型的矩阵和向量

  • 对角矩阵：只有主对角线上含有非零元素
  • 对称矩阵：转置和自己相等的矩阵
  • 单位向量：具有单位范数的向量
  • 正交：$\boldsymbol{x}^T\boldsymbol{y}=0$
  • 标准正交：不但正交，且范数都为1
  • 正交矩阵：行向量和列向量是分别标准正交的方阵
    • $\boldsymbol{A}^{-1}=\boldsymbol{A}^T$

特征分解

  • 将矩阵分解成一组特征向量和特征值
    • $\boldsymbol{Av}=\lambda\boldsymbol{v}$
      • 特征向量：与A相乘后相当于对该向量进行缩放的非零向量$\boldsymbol{v}$
      • 特征值：标量$\lambda$
  • 矩阵 $\boldsymbol{A}$ 有 $n$ 个线性无关的特征向量 ${\boldsymbol{v^{(1)}, …, v^{(n)}}}$，对应着特征值 ${\lambda_1, …, \lambda_n}$ ，将特征向量连接成一个矩阵，每一列是一个特征向量即 $\boldsymbol{V}=[\boldsymbol{v^{(1)}, …, v^{(n)}}]$ ，则 $\boldsymbol{A}$ 的特征分解可以记作：$\boldsymbol{A}=\boldsymbol{V}\text{diag}(\boldsymbol{\lambda})\boldsymbol{V}^{-1}$
  • 所有特征值都是非负数的矩阵被称为半正定
    • 保证 $\forall \boldsymbol{x}, \boldsymbol{x}^T\boldsymbol{Ax} \ge 0$
  • 所有特征值都是正数的矩阵被称为正定
    • 除保证大于等于0，还保证 $\forall \boldsymbol{x}, \boldsymbol{x}^T\boldsymbol{Ax} = 0 \Rightarrow \boldsymbol{x} = \boldsymbol{0}$
  • 所有特征值都是非正数的矩阵称为半负定

奇异值分解

  • 将矩阵（扩展到非方阵）分解为奇异向量和奇异值
    • $\boldsymbol{A}=\boldsymbol{UDV}^T$
    • $\boldsymbol{A}$ 是一个 $m \times n$ 的矩阵，$\boldsymbol{U}$是一个 $m \times m$ 的矩阵，$\boldsymbol{V}$ 是一个 $n \times n$ 的矩阵
    • $\boldsymbol{U}$ 和 $\boldsymbol{V}$ 都定义为正交矩阵，$\boldsymbol{D}$ 定义为对角矩阵（注意其不一定为方阵）
    • $\boldsymbol{D}$ 对角线上的元素被称为矩阵 $\boldsymbol{A}$ 的奇异值，矩阵 $\boldsymbol{U}$ 的列向量称为左奇异向量，矩阵 $\boldsymbol{V}$ 的列向量称为右奇异向量
  • SVD 最有用的一个性质可能是拓展矩阵求逆到非方矩阵

Moore-Penrose伪逆

  • $\boldsymbol{A}^+=\boldsymbol{V}\boldsymbol{D}^+\boldsymbol{U}^T$
    • $\boldsymbol{U\text{, }D\text{ 和 }V}$ 是矩阵 $\boldsymbol{A}$ 奇异值分解得到的矩阵
    • $\boldsymbol{D}^+$ 是 $\boldsymbol{D}$ 的非零元素取倒数后转置得到的

迹运算

  • 返回的是对角元素的和
    • $\text{Tr}(\boldsymbol{A}) = \sum_{i} \boldsymbol{A}_{i,i}$
  • 用迹描述F范数
    • $||\boldsymbol{A}_F||=\sqrt{\text{Tr}(\boldsymbol{AA}^T)}$
  • 迹运算在转置下是不变的
    • $\text{Tr}(\boldsymbol{A}) = \text{Tr}(\boldsymbol{A}^T)$
  • 多个矩阵相乘得到的方阵的迹
    • $\text{Tr}(\boldsymbol{ABC}) = \text{Tr}(\boldsymbol{CAB}) = \text{Tr}(\boldsymbol{BCA})$
  • 矩阵相乘后形状变了，迹运算的结果依然不变
    • $\text{Tr}(\boldsymbol{AB}) = \text{Tr}(\boldsymbol{BA}) \quad \boldsymbol{A} \in \mathbb{R}^{m \times n}\text{, }\boldsymbol{B} \in \mathbb{R}^{n \times m}$
  • 标量的迹是它自己
  • 行列式 $\text{det}(\boldsymbol{A})$
    • 等于矩阵特征值的乘积
    • 衡量矩阵参与矩阵乘法后空间扩大缩小了多少
      • 如果是0,说明空间沿某一维完全收缩了,失去了所有体积
      • 如果是1,说明转换保持空间体积不变

主成分分析(Principal Components Analysis, PCA)

  • 假设在 $\mathbb{R}^n$ 空间中有 $m$ 个点 ${\boldsymbol{x^{(1)}, …, x^{(n)}}}$, 用低维表示编码这些点, 即对每个点 $\boldsymbol{x}^{(i)} \in \mathbb{R}^n$ , 会有一个对应的编码向量 $\boldsymbol{c}^{(i)} \in \mathbb{R}^l$ , 其中 $l < n$ ;
  • 找到一个编码函数 $f$ 使得 $f(\boldsymbol{x})=\boldsymbol{c}$ ,也希望找到一个解码函数 $g$ 使得 $\boldsymbol{x} \approx g\left( f(\boldsymbol{x}) \right)$;
  • 为了简化解码器，使用矩阵乘法将编码映射回 $\mathbb{R}^n$ ，即 $g(\boldsymbol{c}) = \boldsymbol{Dc}$，其中 $\boldsymbol{D} \in \mathbb{R}^{n \times l}$ 是定义解码的矩阵,其限制列向量具有单位范数且彼此正交;
  • 计算最优编码 $ \boldsymbol{c}^{*} $ , 可将问题化为最小化原始输入向量与重构向量之间的距离, 使用$L^2$范数描述问题:
    $$\boldsymbol{c}^{*} = \arg \min _c | \boldsymbol{x}-g(\boldsymbol{c}) | _2 $$
  • 使用$L^2$范数的平方代替,并化简得到:
    $$\boldsymbol{c}^*=\arg \min _c -2\boldsymbol{x}^T\boldsymbol{Dc}+\boldsymbol{c}^T\boldsymbol{c}$$
  • 通过向量微积分求解得:
    $$\boldsymbol{c}=\boldsymbol{D}^T\boldsymbol{x}$$
  • 即编码函数为:
    $$f(\boldsymbol{x})=\boldsymbol{D}^T\boldsymbol{x}$$
  • 重构操作为:
    $$r(\boldsymbol{x})=g\left(f(\boldsymbol{x})\right)=\boldsymbol{DD}^T\boldsymbol{x}$$

推导过程: 最小化投影造成的损失

  • 求解编码矩阵$\boldsymbol{D}$
    最小化所有维数和所有点上的误差矩阵的 Frobenius 范数,即
    $$\boldsymbol{D}^*=\arg \min _c \sqrt{ \sum _{i,j} \left (\boldsymbol{x}_j^{(i)} -r(\boldsymbol{x}^{(i)})_j \right)^2 } \text{ subject to }\boldsymbol{DD}^T=\boldsymbol{I}_l$$
  • …

另一种推导过程: 最大化数据投影后的的方差

  • 理论依据补充->拉格朗日乘子法
    • 假设存在一个函数 $f(x,y)$ , 求该函数在 $g(x, y)=c$ 下的极值
    • 则在极值点的时候两个函数必然相切,此时各自的导数成正比,从而
      $$\cfrac{\partial f}{\partial x} = \lambda\cfrac{\partial g}{\partial x} \quad;\quad
      \cfrac{\partial f}{\partial y} = \lambda\cfrac{\partial g}{\partial y}
      \quad;\quad g(x,y)=c$$
    • 可假设一个新的函数
      $$F(x,y,\lambda)=f(x,y)+\lambda[c-g(x,y)]$$
      分解求:
      $$ \cfrac{\partial F}{\partial x} = 0 \quad;\quad
      \cfrac{\partial F}{\partial y} = 0 \quad;\quad
      \cfrac{\partial F}{\partial \lambda} = 0 $$
  • 推导过程:
    • $\boldsymbol{D}$ 中基向量为 ${\boldsymbol{u}_1, \boldsymbol{u}_2, …, \boldsymbol{u}_l}$ （从 n 维降到 l 维）
    • 数据点 $\boldsymbol{x}_i$ 在该基底上的投影为 $\boldsymbol{x}_i^T \cdot \boldsymbol{u}_j$
    • 所有数据在该基底上的投影的方差为（m为样本数量）
      • $$ \boldsymbol{J}_{j} = \frac{1}{m} \sum_{i=1}^m (x_i^T u_j - x_{center}^T u_j)^2 $$
    • 在运算之前对数据x进行0均值初始化，即 $x_{center}=0$，从而有
      $$\begin{aligned} \boldsymbol{J}_j & = \frac{1}{m} \sum _{i=1} ^m (x_i^Tu_j)^2 \\
      & = \frac{1}{m} \sum _{i=1} ^m (u_j^Tx_i \cdot x_i^Tu_j) \\
      & = u_j^T \cdot \frac{1}{m} \sum _{i=1} ^m (x_i x_i^T) \cdot u_j \\
      & = u_j^T \cdot \frac{1}{m} (\begin{bmatrix}x_1 \cdots x_m \end{bmatrix} \cdot \begin{bmatrix}x_1 \ \cdots \ x_m \end{bmatrix}) \cdot u_j \\
      & == \frac{1}{m} u_j^T \boldsymbol{XX}^T u_j \\
      & = u_j^T \boldsymbol{S} u_j \quad u.t. \text{ } u_j^T u_j \end{aligned} $$
    • 构造函数
      $$F(u_j) = u_j^T \boldsymbol{S} u_j + \lambda_j(1-u_j^T u_j)$$
    • 求解$\frac{\partial F}{\partial u_j}=0$，得：
      $$2\boldsymbol{S} \cdot u_j - 2\lambda_j \cdot u_j = 0 \Rightarrow \boldsymbol{S} u_j = \lambda_j u_j $$
    • 当 $u_j$ 、$\lambda_j$ 分别为 $\boldsymbol{S}$ 矩阵的特征向量、特征值时， $\boldsymbol{J}_j$ 有极值，上述结果回代得
      $$u_j^T \boldsymbol{S} u_j = u_j^T \lambda_j u_j = \lambda _j$$
    • 所以对于任意满足条件的正交基，对应的数据在上面投影后的方差值为$\boldsymbol{S}$矩阵的特征向量，从而
      $$\boldsymbol{J}_{max}=\sum^k_{j=1}\lambda_j, \text{ $\lambda$从大到小排序}$$
    • 所以投影正交基为
      • $\boldsymbol{S}$的特征向量中的前k个最大特征值对应的特征向量
    • 对$\boldsymbol{S}$进行特征分解
      $$ \boldsymbol{D} = \boldsymbol{D} \text{ } of \text{ } svd(\boldsymbol{S}) = \boldsymbol{D} \text{ } of \text{ } svd( \frac{1}{m}\boldsymbol{XX}^T ) $$
    • 因此
      $$ \boldsymbol{X} _{new_{l \times m}} = \begin{bmatrix} u^T_1 \\ u^T_2 \\ \vdots \\ u^T_l \end{bmatrix} _{l \times n} \cdot \boldsymbol{X} _{n \times m} $$

PCA使用过程

  1. 初始化 $\boldsymbol{X}$ ，使得所有样本之间的特征值均值为0，同时应用feature scaling，缩放到$-0.5 \sim 0.5$
  2. 计算 $\boldsymbol{X}$ 的协方差矩阵 $\boldsymbol{S}$
  3. 对 $\boldsymbol{S}$ 进行SVD分解，$\boldsymbol{U}$ 即我们要求的新坐标系集合， $\boldsymbol{D}$ 为特征值集合（计算时特征值都会大于0，且结果会从小到大排列）
  4. 按照特征值从大到小排序，要降低为 $l$ 维，那么取前 $l$ 个特征值对应的特征向量，就是新的 $l$ 个坐标轴
  5. 把X映射到新的坐标系中，完整降维操作