医准智能基础知识系列读书讨论班笔记二

作者: 累了有你在旁 | 来源:发表于2018-10-26 12:02 被阅读0次

医准智能基础知识系列读书讨论班笔记二

线性代数（二）

矩阵的迹（trace）

矩阵的迹指的是一个矩阵（方阵）的主对角线上所有元素的和，用记号 $trace()$ 或者 $tr()$ 表示：
$trace(A) = \sum_i A_{ii} \ \ A \in \mathbb{R}^{n \times n}$
矩阵的迹，常用于矩阵函数的求导中。

一些常用的性质：
$\|A\|_F = \sqrt{tr(AA^T)} = \sqrt{tr(A^TA)}$
$tr(A) = tr(A^T)$
轮换不变： $tr(ABC) = tr(BCA) = tr(CAB)$ ，可以推广到一般的 $n$ 个矩阵相乘
常用的关于迹的求导[1]
- $\frac{\partial tr(X)}{\partial X} = I$
- $\frac{\partial tr(AX)}{X} = A^T$
- $\frac{\partial tr(X^2B)}{\partial X} = (XB+BX)^T$
- $\frac{\partial tr(X^TBX)}{\partial X} = BX + B^TX$
- $\frac{\partial tr(AXBX^TC)}{\partial X} = A^TC^TXB^T + CAXB$

行列式（determinant）

行列式的值为一个方阵所有特征值的乘积，其几何含义为二维有向面积或三维有向体积向一般高维空间的推广。
$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix}$

余子式： $M_{i,j}$ 为矩阵 $A$ 除去第 $i$ 行和第 $j$ 列的元素后，剩下的矩阵的行列式的值
代数余子式： $A_{i,j} = (-1)^{i+j}M_{i,j}$
行列式按行展开： $\det(A) = |A|= \sum_j a_{ij}A_{i,j}$
行列式按列展开： $\det(A) = |A|= \sum_i a_{ij}A_{i,j}$
$\sum_i a_{ij}A_{i^{'},j} = 0, if \quad i \neq i^{'}$

主成分分析（PCA）

问题描述：假定我们手中有 $m$ 个 $n$ 维空间中的数据点 $x_i\in\mathbb{R}^{n}, i\in[m]$ ，希望在一个维数较低为 $l(l<n)$ 的子空间中重建这些点，使得重建后的数据点与原始点的最接近，这个接近指的是丢失最小的关于数据点位置和分布关系的信息。书中将该问题分解为两个子问题：

任意给定低维子空间 $D\in\mathbb{R}^{n \times l}$ ，如何确定一个点的坐标
在知道如何计算每个点在低维空间坐标的基础上，如何寻找一个最优的子空间

对于子问题 1，我们希望在低维子空间中重建的数据点离原数据点尽可能的接近，于是在限制了子空间 $D$ 为一个列标准正交的矩阵的前提下，该问题表示为如下的优化问题：
$c^* = \arg\min_{c} \ \|x-Dc\|_2$
其中， $c$ 表示低维子空间 $D$ 中点的坐标， $c^*$ 是我们希望找到的最理想的坐标。容易看出该问题是一个二次函数求极值问题，问题的目标函数是凸函数，所以函数的稳定点即为问题的最优解：
$f(c)\triangleq \|x-Dc\|_2$
则由 $D$ 列标准正交，可得
$\begin{split} \nabla_c f(c) & = \nabla_c\left( tr(x^Tx - 2x^TDc + c^TD^TDc) \right) \\ & = -2D^Tx + 2D^TDc \\ & = -2(D^Tx-c) \end{split}$
故
$c^* = D^Tx$
直观来看，最优坐标可通过与子空间的正交基的内积来计算。

对于子问题2，我们需要选取最合适的子空间 $D$ 使得对于所有的数据点而言，重建误差的 2-范数平方和最小。可通过如下的优化问题描述：
$\begin{split} \min_{D}& \ \|X-DD^TX\|_F^2 \\ s.t.& \ D^TD = I \end{split}$
其中，矩阵 $X\in\mathbb{R}^{n\times m}$ ，每一列为一个原始数据点
$\begin{split} &\arg\min_D \ \|X-DD^TX\|_F^2 \\ =&\arg\min_D \ tr[(X-DD^TX)^T(X-DD^TX)] \\ =&\arg\min_D \ tr(X^TX - 2X^TDD^TX + X^TDD^TDD^TX) \\ =&\arg\min_D \ tr(X^TX - X^TDD^TX) \\ =&\arg\max_D \ tr(D^TXX^TD) \end{split}$
考虑矩阵 $XX^T$ 的特征分解 $XX^T=\sum_i \lambda_iu_iu_i^T$ ，并假设 $\lambda_1 > \lambda_2 > \lambda_3 > \cdots > \lambda_n$ . 当 $l=1$ 时， $D$ 退化为列向量 $d$ ，问题变为
$\begin{split} \arg\max_d& \ \sum_i\lambda_i|<d, u_i>|^2 \\ s.t.& \ \|d\|_2= 1 \end{split}$
容易求得该问题的最优解为 $d^* = u_1$ ，即最大特征值所对应的特征方向，对于 $l>1$ 的情况，可以通过数学归纳法得到，所求问题的最优解为前 $l$ 个最大特征值所对应的特征方向。