机器学习中的主要的降维有PCA(无监督学习)和LDA(监督学习)。本文基于scikit的LFW数据集的降维技术。
假设样本矩阵 $X\in\mathbb{R}^{n\times{m}}$ . 这里都用列向量.
PCA
基变换
坐标$(a,b)$是一个类似于地址的概念, 这种地址需要和空间上某种表示进行结合才会有具体的意义. 这种结合就是"线性组合":
$$
\boldsymbol{x}=a\begin{bmatrix}1&0\end{bmatrix}^T + b\begin{bmatrix}0&1\end{bmatrix}^T
$$
假设有三个点$(1,1), (2,2), (3,3)$, 在直角坐标中很难用一个坐标将其表示, 但是如果将坐标轴"旋转"以使得新的基底变为:
$$
\begin{aligned}
\boldsymbol{e_1}&=\begin{bmatrix}1&1\end{bmatrix}^T \\
\boldsymbol{e_2}&=\begin{bmatrix}-1&1\end{bmatrix}^T
\end{aligned}
$$
由于这三点新的基底下关于向量$\boldsymbol{e_2}$的分量为0, 故而需要将其转换到新基底下就可以减少一个维度. 只要这个新的基底线性无关同时可以表达线性子空间任何线性组合.
想到向量的点乘:
$$
\boldsymbol{a}\cdot\boldsymbol{b}=|\boldsymbol{a}||\boldsymbol{b}|\cos\theta
$$
只要$\boldsymbol{b}$的模是1, 那么点乘就要可以表示为:
$$
\boldsymbol{a}\cdot\boldsymbol{b}=|\boldsymbol{a}|\cos\theta
$$
如果把$\boldsymbol{b}$视为标准正交基的一个基底, 那么通过把$\boldsymbol{a}$向$\boldsymbol{b}$投影就可以变成新基底下的坐标了.例如标准化后的$\boldsymbol{e_1}$和$\boldsymbol{e_2}$:
$$
\begin{aligned}
\boldsymbol{e_1}&=\begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix}^T \\
\boldsymbol{e_2}&=\begin{bmatrix}-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix}^T
\end{aligned}
$$
把三个点按照列堆叠:
$$
\text{变换后的坐标}=\begin{bmatrix}
\boldsymbol{e_1} & \boldsymbol{e_2}
\end{bmatrix}
\begin{bmatrix}
1&2&3\\
1&2&3
\end{bmatrix}
=\begin{bmatrix}
\sqrt{2}&2\sqrt{2}&3\sqrt{2}\\
0&0&0
\end{bmatrix}
$$
起始根据二维的逆时针的旋转矩阵$M=\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}$也可以把原基底$(1,0)$和$(0,1)$变成新的基底$\boldsymbol{e_1}$和$\boldsymbol{e_2}$(逆时针旋转$\frac{\pi}{4}$度):
$$
\begin{bmatrix}\frac{\sqrt{2}}{2}&-\frac{\sqrt{2}}{2}\\\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}\end{bmatrix}\begin{bmatrix}1&0\\0&1\end{bmatrix}=\begin{bmatrix}
\boldsymbol{e_1} & \boldsymbol{e_2}
\end{bmatrix}
$$
度量方法
但是我们要找到能够使投影之后将方差最大的方向这样就可以很好的区分数据. 假设投影之后的坐标为:
$$\begin{bmatrix}
w_1&w_2,\cdots,w_k
\end{bmatrix}$$
目标是投影将$n$个特征尽可能以较小的损失降为$k(k<<n)$. 数据为$\mathbb{R}^{n\times{m}}$以及投影矩阵$\mathbb{R}^{n\times{k}}$. 设投影矩阵:
$$W=\begin{bmatrix}
\boldsymbol{w_1}&\boldsymbol{w_2},\cdots,\boldsymbol{w_k}
\end{bmatrix}$$
$\boldsymbol{W}$必须是标准正交的. 这个投影后的坐标要和原来的数据之间距离最小:
$$\begin{aligned}
\min_{W}||X-X^*||_F^2&=\min_{W}||X-WW^TX||_F^2 \\
\text{s.t.}&\quad{W^TW=I}
\end{aligned}$$
其中$W^TX$就是投影后的坐标. $W^{-1}=W$, 也就是投影回去. $||\cdot||_F$就是矩阵元素的绝对值的平方和的根(算术?). 化简求解的公式:
$$
\begin{array}{l}{\min_{W}\left\|X-W W^{T} X\right\|_{F}^{2}=\min _{W} \operatorname{tr}\left(\left(X-W W^{T} X\right)^{T}\left(X-W W^{T} X\right)\right)} \\ {=\min _{W} \operatorname{tr}\left(X^{T} X-X^{T} W W^{T} X-X^{T} W W^{T} X-X^{T} W W^{T} W W^{T} X\right)}\end{array}
$$
与$W$无关的项目与优化的方向无关, 故进一步化简:
$$\begin{array}{l}{\min _{W}\left\|X-W W^{T} X\right\|_{F}^{2}=\min _{W} \operatorname{tr}\left(-2 X^{T} W W^{T} X+X^{T} W W^{T} X\right)} \\ {=\min _{W} \operatorname{tr}\left(-X^{T} W W^{T} X\right)} \\ {=\max _{W} \operatorname{tr}\left(X^{T} W W^{T} X\right)}\\
=\max_W\operatorname{tr}[\left(W^TX\right)^T\left(X^TW\right)^T]\\
=\max_W\operatorname{tr}(W^TXX^TW)
\end{array}$$
由于这是个等式约束问题, 用拉格朗日乘数法可以解决:
拉格朗日函数
$$L(W,\lambda)=\operatorname{tr}(W^TXX^TW^T)+\lambda(I-W^TW)
$$
两边求导, 令导数为0:
这里引入几个有用的公式:
$$
\frac{\partial}{\partial X} \operatorname{tr}\left(X^{T} B X\right)=B X+B^{T} X
$$
和
$$
\frac{\partial}{\partial X}\left(X^{T} B X\right)=B^T X+B X
$$
得到
$$
\begin{aligned}
\frac{\partial{L(W,\lambda)}}{\partial{W}}&=\frac{\partial\left(\operatorname{tr}(W^TXX^TW^T)+\lambda(I-W^TW)\right)}{\partial{W}}\\
&=2XX^TW-\lambda\frac{\partial}{\partial W}W^TW\\
&=2XX^TW-2\lambda{W}\quad\text{类似于公式2中的}B=I.
\end{aligned}
$$
最终得到:
$$XX^TW=\lambda{W}$$
当均一化的样本$X$, $XX^T$表示的就是协方差矩阵, 这个形式与特征值分解的形式相同. 求得非升序的特征值和对应的特征向量:
$$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_k$$
和
$$W^*=\begin{bmatrix}
\boldsymbol{w_1}, \boldsymbol{w_2},\cdots, \boldsymbol{w_k}
\end{bmatrix}$$
LDA
这个是线性判别分析, 是监督学习的降维方法. LDA 的核心思想就是投影后类间距离大, 类内距离小, 这个距离就是指的方差. 具体内容见周志华《机器学习》P60.
技术人都喜欢高数。