图解机器学习/第十三章 无监督降维

高维数据的处理是相当困难的，一般称为维数灾难。为了使机器学习算法从维数灾难中解放出来，一般采取的有效方法是尽量保持输入数据中包含的所有信息，并对其维数进行削减。

线性降维的原理

无监督降维的目的，是把高维的训练输入样本$\lbrace x_i \rbrace_{i=1}^n$变换为低维的训练样本$\lbrace z_i \rbrace_{i=1}^n$，并在降维后还能尽可能地保持其原本包含的所有信息。

通过$x_i$的线性变换求解$z_i$的时候，即使用维数为$m \times d$的投影矩阵$T$根据下式

$$z_i = Tx_i$$

来求解$z_i$的时候，称为线性降维。

中心化：

$x_i \leftarrow x_i \frac{1}{n} \sum_{i’=1}^n x_{i’}$

主成分分析

主成分分析法，是尽可能地忠实再现原始数据地所有信息地降维方法。具体而言，就是在降维后地输入$z_i$是原始训练输入样本$x_i$地正投影这一约束条件下，设计投影矩阵$T$，让$z_i$和$x_i$尽可能相似。

$z_i$是$x_i$的正投影这一假设，与投影矩阵$T$满足$TT^{\intercal}=I_m$是等价的。其中$I_m$表示的是$m \times m$的单位矩阵。

当$z_i$和$x_i$的维度不一样的时候，并不能直接计算其平方误差。因此，一般先把$m$次维的$z_i$通过$T^{\intercal}$变换到$d$次维空间，再计算其与$x_i$的距离。所有训练样本的$T^{\intercal}z_i$与$x_i$的平方距离的和，可以通过下式表示

$$\sum_{i=1}^n ||T^{\intercal}Tx_i - x_i||^2 = -tr(TCT^{\intercal}) + tr(C)$$

其中，$C$为训练输入样本的协方差矩阵

$$C=\sum_{i=1}^n x_ix_i^{\intercal}$$

主成分学习的过程可以用下式表示

$$\mathop{max}_{T\in \mathbb{R}^{m \times d}} tr(TCT^{\intercal}) \quad 约束条件 TT^{\intercal}=I_m$$

考虑到矩阵$C$的特征值问题

$$C\xi = \lambda \xi$$

将特征值和相对应的特征向量分别表示为$\lambda_1 \ge \dots \ge \lambda_d \ge 0$和$\xi_1,\dots,\xi_d$，这样主成分分析的解就可以通过下式求得

$$T=(\xi_1,\dots,\xi_m)^{\intercal}$$

主成分分析的投影矩阵，是通过向训练输入样本的协方差矩阵$C$中的较大的$m$个特征值所对应的特征向量张成的局部空间正投影而得到的。与此相反，通过把较小的特征值所对应的特征向量进行削减，与原始样本的偏离就可以达到最小。另外，主成分分析中求得的低维$\lbrace z_i \rbrace_{i=1}^n$，其各个元素之间是无关联的，相互独立的，即协方差矩阵为对角矩阵

$$\sum_{i=1}^n z_i z_i^{\intercal} = diag(\lambda_1,\dots,\lambda_m)$$

局部投影保持

局部保持投影利用了训练输入样本间的相似度信息。训练输入样本$x_i$和$x_{i’}$的相似度用$W_{i,i’} \ge 0$来表示。当$x_i$和$x_{i’}$较为相似的时候，$W_{i,i’}$为较大的值；当$x_i$和$x_{i’}$不那么相似的时候，$W_{i,i’}$为较小的值。相似度是对称的，即可以假设$W_{i,i’}=W_{i’,i}$

训练输入样本$\lbrace x_i \rbrace_{i=1}^n$间的相似度的实例：

高斯相似度：

$$W_{i,i'}=exp(- \frac{||x_i - x_{i'}||^2}{2t^2})$$

其中，$t>0$是调整相似度衰减值的参数

$k$近邻相似度：

$$W_{i,i'} = \begin{cases}1 &\text{$(x_i \in \mathcal{N}_k(x_{i'})或x_{i'}\in \mathcal{N}_k(x_i))$} \\ 0 &\text{(其他)} \end{cases}$$

其中，$\mathcal{N}_k(x)$为$\lbrace x_i \rbrace_{i=1}^n$中的$x$近邻的$k$个样本的集合。$k\in [1,\dots,n]$是调整相似度局部性的参数。$k$近邻相似度的优点是，以$W_{i,i’}$为第$(i,i’)$个元素的矩阵$W$是稀疏矩阵。

局部尺度相似度：

$$W_{i,i'}=exp(- \frac{||x_i - x_{i'}||^2}{2t_it_{i'}})$$

其中，$t_i$为局部尺度，定义为$t_i=||x_i - x_i^{(k)}||$。$x_i^{(k)}$是$\lbrace x_i \rbrace_{i=1}^n$中与$x_i$的距离为第$k$近的样本。把局部尺度相似度和$k$近邻相似度组合在一起的$k$近邻局部相似度，有着广泛的实际应用。

在局部保持投影中，认为相似度较高的样本对的投影也较为相似，以此来决定投影矩阵$T$。具体而言，就是计算下式的值最小时所对应的$T$

$$\frac{1}{2}\sum_{i,i'=1}^n W_{i,i'}||Tx_i - Tx_{i'}||^2$$

为了避免得到$T=O$这样不证自明的结果，加入约束条件

$$TXDX^{\intercal}T^{\intercal}=I_m$$

上式中，$X=(x_1,\dots,x_n)\in \mathbb{R}^{d \times n}$是训练输入样本的矩阵，$D$是以矩阵$W$的各行元素之和为对角元素的对角矩阵

$$D_{i,i'} = \begin{cases} \sum_{i''=1}^n W_{i,i'} &\text{$(i=i')$} \\ 0 &\text{($i \not= i'$)} \end{cases}$$

令$L=D-W$，综上，局部投影保持的学习规则可以用下式表示

$$\mathop{min}_{T\in \mathbb{R}^{m \times n}} tr(TXLX^{\intercal}T^{\intercal}) \quad 约束条件 \quad TXDX^{\intercal}T^{\intercal}=I_m$$

考虑到关于矩阵对$(XLX^{\intercal},XDX^{\intercal})$的一般化特征值问题

$$XLX^{\intercal}\xi = \lambda XDX^{\intercal}\xi$$

将一般化特征值及与其对应的一般化特征向量，分别用$\lambda_1 \ge \dots \ge \lambda_d \ge 0$和$\xi_1,\dots,\xi_d$来表示。局部保持投影就可以用下式来求解

$$T=(\xi_d,\xi_{d-1}, \dots,\xi_{d-m+1})^{\intercal}$$

局部保持投影的投影矩阵，是通过矩阵对$(XLX^{\intercal},XDX^{\intercal})$的较小的$m$个一般化特征值对应的一般化特征向量来求解的。

核函数主成分分析

把训练样本$\lbrace x_i \rbrace_{i=1}^n$通过非线性函数$\psi$进行变换，在变换后的特征空间里进行主成分分析。通过这样的方法，就可以在原始训练样本的特征空间中进行非线性降维操作。

协方差矩阵$C$的大小往往依赖于特征空间的维度，但是核矩阵$K$的大小则只与样本数有关。因此，当特征空间的维数比样本数大的时候，使用与核矩阵$K$相关的特征值问题，可以得到更高效的求解。

拉普拉斯特征映射

将核函数方法应用在局部保持投影的非线性降维方法，称为拉普拉斯特征映射。

与$(XLX^{\intercal},XDX^{\intercal})$相关的一般化特征值问题就可以变换为

$$L\alpha=\lambda D \alpha$$

上式中一般化特征值及与其对应的一般化特征向量，分别可以用$\lambda_1 \ge \dots \ge \lambda_n \ge 0$和$\alpha_1,\dots,\alpha_n$来表示。这里因为$L1_n=0_n$是成立的，显然与最小的一般化特征值$\lambda_n=0$相对应的一般化特征向量为$\alpha_n = 1_n$，这里去掉$\alpha_n$变为

$$(z_1,\dots,z_n)=(\alpha_{n-1},\alpha_{n-2},\dots,\alpha_{n-m})^{\intercal}$$

上式即为拉普拉斯特征映射的最终结果。

如果相似度矩阵$W$为稀疏矩阵，$L=D-W$也为稀疏矩阵，这样就变成了稀疏的一般化特征值问题，可以进行高效的求解。