葫芦书第四章——降维

作者: 单调不减 | 来源:发表于2019-08-09 20:30 被阅读0次

在机器学习中，数据通常需要被表示为向量形式以输入模型进行训练。但众所周知，对高维向量进行处理和分析时，会极大地消耗系统资源，甚至产生维度灾难（相关笔记记录于这里）。因此，用一个低维度的向量表示原始高维度的特征就显得尤为重要。

1、PCA最大方差理论

在机器学习领域中，我们对原始数据进行特征提取，有时会得到比较高维的特征向量。在这些向量所处的高维空间中，包含很多的冗余和噪声。我们希望通过降维的方式来寻找数据内部的特性，从而提升特征表达能力，降低训练复杂度。主成分分析（PCA）作为降维中最经典的方法，属于一种线性、非监督、全局的降维算法。

1.1、如何定义主成分？从这种定义出发，如何设计目标函数使得降维达到提取主成份的目的？针对这个目标函数，如何对PCA问题进行求解？

我的回答：

1、所谓主成分，就是把原特征进行线性组合后得到新的特征，此特征尽可能多地保留了原特征的方差。

2、设一组参数 $\theta$ ，记原特征为 $x$ ，新特征为 $\theta^T x$ ，根据定义，我们要让 $\theta^T x$ 的方差尽可能大，即 $\max var[\theta^T x]$ 这就是我们的目标函数。

3、具体的求解过程要借助特征值分解。

参考答案：

（a）是二维空间中经过中心化的一组数据，我们很容易看出主成分所在的轴（以下称为主轴）的大致方向，即（b）中黄线所处的轴。因为在黄线所处的轴上，数据分布得更为分散，这也意味着数据在这个方向上方差更大。

我们不难引出PCA的目标，即最大化投影方差，也就是让数据在主轴上投影的方差最大。对于给定的一组数据点 $\{v_1,\dots,v_n\}$ ，其中所有向量均为列向量，中心化后的表示为 $\{x_1,\dots,x_n\}=\{v_1-\mu,\dots,v_n-\mu\}$ ，其中 $\mu=\frac{1}{n}\sum_{i=1}^n v_i$ 。我们知道，向量内积在几何上表示为第一个向量投影到第二个向量上的长度，因此向量 $X$ 在 $ω$ （单位方向向量）上的投影坐标可以表示为 $(x_i,w)=x_i^T w$ 。所以目标是找到一个投影方向 $ω$ ，使得 $x_1,\dots,x_n$ 在 $w$ 上的投影方差尽可能大。易知，投影之后均值为0（ $\mu^{'}=\frac{1}{n}\sum_{i=1}^n x_i^T w=(\frac{1}{n}\sum_{i=1}^n x_i^T )w=0$ ），因此投影后方差可以表示为：

$\begin{aligned} D(\boldsymbol{x})=\frac{1}{n} \sum_{i=1}^{n}\left(\boldsymbol{x}_{i}^{\mathrm{T}} \omega\right)^{2} &=\frac{1}{n} \sum_{i=1}^{n}\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{\omega}\right)^{\mathrm{T}}\left(\boldsymbol{x}_{i}^{\mathrm{T}} \omega\right) \\ &=\frac{1}{n} \sum_{i=1}^{n} \omega^{\mathrm{T}} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \omega \\ &=\boldsymbol{\omega}^{\mathrm{T}}\left(\frac{1}{n} \sum_{i=1}^{n} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}}\right) \boldsymbol{\omega} \end{aligned}$

其中 $\frac{1}{n}\sum_{i=1}^n x_i x_i^T$ 其实就是协方差矩阵，我们将其写为 $\Sigma$ ，另外，由于 $w$ 是单位向量，因此 $w^T w=1$ ，因此我们要求解一个最大化问题：

$\left\{\begin{array}{l}{\max \left\{\omega^{\mathrm{T}} \Sigma \omega\right\}} \\ {\text {s.t.} \quad \omega^{\mathrm{T}} \omega=1}\end{array}\right.$

引入拉格朗日乘子并对 $ω$ 求导令其等于0，便可以推出 $\Sigma w=\lambda w$ ，此时：

$D(x)=w^T \Sigma w=\lambda w^T w=\lambda$

不难看出， $x$ 投影后的方差就是协方差矩阵的特征值。我们要找到最大的方差也就是协方差矩阵最大的特征值，最佳投影方向就是最大特征值所对应的特征向量。次佳投影方向位于最佳投影方向的正交空间中，是第二大特征值对应的特征向量，以此类推。至此，我们得到了PCA的求解方法：

1）对样本数据进行中心化处理。

2）求样本协方差矩阵。

3）对协方差矩阵进行特征值分解，将特征值从大到小排列。

4）取特征值前 $d$ 大对应的特征向量 $w_1,\dots,w_d$ 通过以下映射将 $n$ 维样本映射到 $d$ 维：

$\boldsymbol{x}_{i}^{\prime}=\left[\begin{array}{c}{\omega_{1}^{\mathrm{T}} \boldsymbol{x}_{i}} \\ {\omega_{2}^{\mathrm{T}} \boldsymbol{x}_{i}} \\ {\vdots} \\ {\omega_{d}^{\mathrm{T}} \boldsymbol{x}_{i}}\end{array}\right]$

定义降维后的信息占比为：

$\eta=\sqrt{\frac{\sum_{i=1}^{d} \lambda_{i}^{2}}{\sum_{i=1}^{n} \lambda_{i}^{2}}}$

2、PCA最小平方误差理论

2.1、PCA求解的真实是最佳投影方向，即一条直线，这与数学中线性回归问题的目标不谋而合，能否从回归的角度定义PCA的目标并相应地求解问题呢？

我的回答：

可以。从线性回归的角度切入，最佳投影方向对应的直线应该使得各点到此直线的距离的平方和最小。关于这个目标和最大方差目标的等价性，我在这里已经说明过了。

参考答案：

从求解直线的思路出发，很容易联想到数学中的线性回归问题，其目标也是求解一个线性函数使得对应直线能够更好地拟合样本点集合。如果我们从这个角度定义PCA的目标，那么问题就会转化为一个回归问题。

数据集中每个点 $x_k$ 到 $d$ 维超平面 $D$ 的距离为：

$distance(x_k,D)=||x_k-\widetilde{x_{k}}||_2$

其中 $\widetilde{x_{k}}$ 表示 $x_k$ 在超平面 $D$ 上的投影向量。若该超平面 $D$ 由 $d$ 个标准正交基 $W=\{w_1,\dots,w_d\}$ 构成，则有线代知识可知， $\widetilde{x_k}$ 可由这组基线性表示：

$\widetilde{x_k}=\sum_{i=1}^d (w_i^T x_k)w_i$

其中 $w_i^T x_k$ 表示 $x_k$ 在 $w_i$ 方向上投影的长度。因此 $\widetilde{x_k}$ 实际上就是 $x_k$ 在 $W$ 这组标准正交基下的坐标。而PCA要优化的目标是：

$\left\{\begin{array}{l}{\arg \min _{\omega_{1}, \ldots, \omega_{d}} \sum_{k=1}^{n}\left\|x_{k}-\widetilde{x_{k}}\right\|_{2}^{2}} \\ {\text { s.t. } \quad \omega_{i}^{\mathrm{T}} \omega_{j}=\delta_{i j}=\left\{\begin{array}{l}{1, i=j} \\ {0, i \neq j}\end{array}\right.}\end{array}\right.$

将上式中每个距离展开：

$\begin{aligned}\left\|x_{k}-\widetilde{x_{k}}\right\|_{2}^{2} &=\left(x_{k}-\widetilde{x_{k}}\right)^{\mathrm{T}}\left(x_{k}-\widetilde{x_{k}}\right) \\ &=x_{k}^{\mathrm{T}} x_{k}-x_{k}^{\mathrm{T}} \widetilde{x_{k}}-\widetilde{x_{k}}^{\mathrm{T}} x_{k}+\widetilde{x_{k}}^{\mathrm{T}} \widetilde{x_{k}} \\ &=x_{k}^{\mathrm{T}} x_{k}-2 x_{k}^{\mathrm{T}} \widetilde{x_{k}}+\widetilde{x_{k}}^{\mathrm{T}} \widetilde{x_{k}} \end{aligned}$

可以看到，第一项与选取的 $W$ 无关，是一个常数，将 $\widetilde{x_k}=\sum_{i=1}^d (w_i^T x_k)w_i$ 代入第二项第三项得到：

$\begin{aligned} x_k^T \widetilde{x_k}&=x_k^T \sum_{i=1}^d (w_i^T x_k)w_i\\ &=\sum_{i=1}^d w_i^T x_k x_k^T w_i\\ \end{aligned}$

$\begin{aligned} \widetilde{x_{k}}^{\mathrm{T}} \widetilde{x_{k}} &=\left(\sum_{i=1}^{d}\left(\omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k}\right) \omega_{i}\right)^{\mathrm{T}}\left(\sum_{j=1}^{d}\left(\omega_{j}^{\mathrm{T}} \boldsymbol{x}_{k}\right) \omega_{j}\right) \\ &=\sum_{i=1}^{d} \sum_{j=1}^{d}\left(\left(\omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k}\right) \omega_{i}\right)^{\mathrm{T}}\left(\left(\omega_{j}^{\mathrm{T}} \boldsymbol{x}_{k}\right) \omega_{j}\right) \end{aligned}$

因为当 $i\neq j$ 时， $w_i^T w_j=0$ ，因此上式可写为：

$\begin{aligned} \widetilde{x_{k}}^{\mathrm{T}} \widetilde{\boldsymbol{x}_{k}} &=\sum_{i=1}^{d}\left(\left(\omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k}\right) \omega_{i}\right)^{\mathrm{T}}\left(\left(\omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k}\right) \omega_{i}\right)=\sum_{i=1}^{d}\left(\omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k}\right)\left(\omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k}\right) \\ &=\sum_{i=1}^{d}\left(\omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k}\right)\left(\boldsymbol{x}_{k}^{\mathrm{T}} \omega_{i}\right)=\sum_{i=1}^{d} \omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k} \boldsymbol{x}_{k}^{\mathrm{T}} \boldsymbol{\omega}_{i} \end{aligned}$

于是：

$\begin{aligned} ||x_{k}-\widetilde{x_{k}}||_{2}^{2} &=-\sum_{i=1}^{d} \omega_{i}^{\mathrm{T}} \boldsymbol{x}_{k} \boldsymbol{x}_{k}^{\mathrm{T}}\omega_{i}+\boldsymbol{x}_{k}^{\mathrm{T}} \boldsymbol{x}_{k}\\ &=-\operatorname{tr}\left(W^{\mathrm{T}} \boldsymbol{x}_{k} \boldsymbol{x}_{k}^{\mathrm{T}} \boldsymbol{W}\right)+\boldsymbol{x}_{k}^{\mathrm{T}} \boldsymbol{x}_{k}\\ \end{aligned}$

这等价于求解带约束的优化问题：

$\left\{\begin{array}{l}{\arg \max _{W} \operatorname{tr}\left(W^{\mathrm{T}} \boldsymbol{X} \boldsymbol{X}^{\mathrm{T}} \boldsymbol{W}\right)} \\ {\text { s.t. } \quad W^{\mathrm{T}} \boldsymbol{W}=I}\end{array}\right.$

如果我们对 $W$ 中的 $d$ 个基 $w_1,\dots,w_d$ 依次求解，就会发现和最大方差理论的方法完全等价。

3、线性判别分析

线性判别分析（Linear Discriminant Analysis, LDA）是一种有监督学习算法，同时经常被用来对数据进行降维。

相比于PCA，LDA可以作为一种有监督的降维算法。在PCA中没有考虑数据的标签（类别），只是把原数据映射到一些方差比较大的方向上而已。

假设用不同的颜色标注 $C_1,C_2$ 两个不同类别的数据，如图所示。根据PCA算法，数据应该映射到方差最大的那个方向，亦即 $y$ 轴方向。但是， $C_1,C_2$ 两个不同类别的数据就会完全混合在一起，很难区分开。所以，使用PCA算法进行降维后再进行分类的效果会非常差。但是如果使用LDA算法，数据会映射到 $x$ 轴方向。

3.1、对于具有类别标签的数据，应当如何设计目标函数使得降维的过程中不损失类别信息？在这种目标下，应当如何进行求解？

我的回答：

1、要想降维过程中不损失类别信息，一个简单的想法就是降维后两类样本点之间的距离越远越好，这样才能将两类样本区分开来。

2、在这样的目标下，假设样本在目标超平面上的投影，并考察两类样本投影的均值点，求解一个超平面，使得这两个均值点之间的距离最大。

参考答案：

LDA首先是为了分类服务的，因此只要找到一个投影方向 $w$ ，使得投影后的样本尽可能按照原始类别分开。我仍不妨从一个简单的二分类问题出发，有 $C_1,C_2$ 两个类别的样本，两类的均值分别为 $\mu_{1}=\frac{1}{N_{1}} \sum_{x \in C_{1}} x, \mu_{2}=\frac{1}{N_{2}} \sum_{x \in C_{2}} x$ ，我们希望投影之后两类之间的距离尽可能大，距离表示为：

$D(C_1,C_2)=||\widetilde{\mu_1}-\widetilde{\mu_2}||_2^2$

$\widetilde{\mu_1}$ 和 $\widetilde{\mu_2}$ 表示两类中心在 $w$ 方向上的投影向量，即 $\widetilde{\mu_1}=w^T \mu_1,\widetilde{\mu_2}=w^T \mu_2$ ，因此需要优化的问题为：

$\left\{\begin{array}{ll}{\max _{\omega}\left\|\omega^{\mathrm{T}}\left(\mu_{1}-\mu_{2}\right)\right\|_{2}^{2}} \\ {\text {s.t.} \quad \omega^{\mathrm{T}} \omega=1}\end{array}\right.$

容易发现当 $ω$ 方向与 $\mu_1-\mu_2$ 一致的时候，该距离达到最大值，例如对图（a）的黄棕两种类别的样本点进行降维时，若按照最大化两类投影中心距离的准则，会将样本点投影到下方的黑线上。但是原本可以被线性划分的两类样本经过投影后有了一定程度的重叠，这显然不能使我们满意。我们希望得到的投影结果如图（b）所示，虽然两类的中心在投影之后的距离有所减小，但确使投影之后样本的可区分性提高了。

仔细观察两种投影方式的区别，可以发现，在图（b）中，投影后的样本点似乎在每一类中分布得更为集中了，用数学化的语言描述就是每类内部的方差比（a）中更小。这就引出了LDA的中心思想一一最大化类间距离和最小化类内距离。

在前文中我们已经找到了使得类间距离尽可能大的投影方式，现在只需要同时优化类内方差，使其尽可能小。我们将整个数据集的类内方差定义为各个类分别的方差之和，将目标函数定义为类间距离和类内距离的比值，于是引出我们需要最大化的目标：

$\max_{w} J(w)=\frac{||w^T(\mu_1-\mu_2)||_2^2}{D_1+D_2}$

真中 $ω$ 为单位向量， $D_1,D_2$ 分别表示两类投影后的方差：

$\begin{array}{c}{D_{1}=\sum_{x \in C_{1}}\left(\omega^{\mathrm{T}} x-\omega^{\mathrm{T}} \mu_{1}\right)^{2}=\sum_{x \in C_{1}} \omega^{\mathrm{T}}\left(x-\mu_{1}\right)\left(x-\mu_{1}\right)^{\mathrm{T}} \omega} \\ {D_{2}=\sum_{x \in C_{2}} \omega^{\mathrm{T}}\left(x-\mu_{2}\right)\left(x-\mu_{2}\right)^{\mathrm{T}} \omega}\end{array}$

因此 $J(w)$ 可以写成：

$J(\omega)=\frac{\omega^{\mathrm{T}}\left(\mu_{1}-\mu_{2}\right)\left(\mu_{1}-\mu_{2}\right)^{\mathrm{T}} \omega}{\sum_{x \in C_{i}} \omega^{\mathrm{T}}\left(x-\mu_{i}\right)\left(x-\mu_{i}\right)^{\mathrm{T}} \omega}$

定义类间散度矩阵为：

$S_B=(\mu_{1}-\mu_{2})(\mu_{1}-\mu_{2})^{\mathrm{T}}$

类内散度矩阵为：

$S_w=\sum_{x\in C_i}(x-\mu_i)(x-\mu_i)^T$

则有：

$J(w)=\frac{w^T S_B w}{w^T S_w w}$

我们要最大化 $J(w)$ ，只需对 $ω$ 求偏导，并令导数等于零：

$\frac{\partial J(\omega)}{\partial \omega}=\frac{\left(\frac{\partial \omega^{\mathrm{T}} S_{B} \omega}{\partial \omega} \omega^{\mathrm{T}} S_{w} \omega-\frac{\partial \omega^{\mathrm{T}} \mathcal{S}_{w} \omega}{\partial \omega} \omega^{\mathrm{T}} S_{B} \omega\right)}{\left(\omega^{\mathrm{T}} S_{w} \omega\right)^{2}}=0$

于是得出：

$(w^T S_w w)S_B w=(w^T S_B w)S_w w$

在二分类中 $w^T S_w w$ 和 $w^T S_B w$ 是两个数，令 $\lambda=J(w)=\frac{w^T S_B w}{w^T S_w w}$ ，于是：

$S_B w=\lambda S_w w$

即：

$S_w^{-1}S_Bw=\lambda w$

从这里我们可以看出，我们最大化的目标对应了一个矩阵的特征值。于是LDA降维变成了一个求矩阵特征向量的问题。 $J(w)$ 就对应矩阵 $S_w^{-1}S_B$ 最大的特征值，而投影方向就是这个特征值对应的特征向量。

对于二分类这一问题，由于 $S_B=(\mu_{1}-\mu_{2})(\mu_{1}-\mu_{2})^{\mathrm{T}}$ ，因此 $S_B w$ 的方向始终与 $\mu_1-\mu_2$ 一致，若只考虑 $ω$ 的方向而不考虑长度，可得 $w=S_w^{-1}(\mu_1-\mu_2)$ 。

4、线性判别分析与主成分分析

4.1、LDA和PCA作为经典的降维算法，如何从应用的角度分析其原理的异同？从数学推导的角度，两种降维算法在目标函数上有何区别与联系？

我的回答：

1、LDA和PCA最显著的区别就是前者是有监督方法而后者是无监督方法，因此在应用中，对于数据中有标签的应该使用LDA，对于数据中无标签的则使用PCA。

2、数学推导上，两者的区别在于，PCA并未考虑类之间的距离（因为PCA并未用到标签信息），而是仅仅考虑了降维后数据的方差，从这个角度来说，PCA相当于在LDA中将所有数据当成一类去处理的特殊情形。因此我们可以看到两者的数学推导也十分相似，最终目标都归为求解一个矩阵的特征值分解。

参考答案：

首先将LDA拓展到多类高维的情况以和问题PCA的求解对应。假设有 $N$ 个类别，并需要最终将特征降维至 $d$ 维。我们要找到一个 $d$ 维投影超平面 $W = \{w_1,\dots,w_d\}$ 使得投影后的样本点满足LDA的目标一一最大化类间距菌和最小化类内距离。

回顾两个散度矩阵，类内散度矩阵 $S_w=\sum_{x\in C_i}(x-\mu_i)(x-\mu_i)^T$ 在类别数增加时仍满足定义。而之前两类问题的类间散度矩阵 $S_B=(\mu_{1}-\mu_{2})(\mu_{1}-\mu_{2})^{\mathrm{T}}$ 在类别增加后就无法按照原始定义。

考虑三类样本的情况， $\mu_1,\mu_2,\mu_3$ 分别表示棕绿黄三类样本的中心， $μ$ 表示这三个中心的均值（也即全部样本的中心）， $S_{wi}$ 表示第 $i$ 类的类内散度。我们可以定义一个新的矩阵 $S_t$ 表示全局整体的散度，称为全局散度矩阵：

$S_t=\sum_{i=1}^n(x_i-\mu)(x_i-\mu)^T$

如果把全局散度定义为类内散度与类间散度之和，即 $S_t=S_b+S_w$ ，那么类间散度矩阵可表示为：

$\begin{aligned} S_{b} &=S_{t}-S_{w} \\ &=\sum_{i=1}^{n}\left(x_{i}-\mu\right)\left(x_{i}-\mu\right)^{\mathrm{T}}-\sum_{x \in C_{i}}\left(x-\mu_{i}\right)\left(x-\mu_{i}\right)^{\mathrm{T}} \\ &=\sum_{j=1}^{N}\left(\sum_{x \in C_{j}}(x-\mu)(x-\mu)^{\mathrm{T}}-\sum_{x \in C_{j}}\left(x-\mu_{j}\right)\left(x-\mu_{j}\right)^{\mathrm{T}}\right) \\ &=\sum_{j=1}^{N} m_{j}\left(\mu_{j}-\mu\right)\left(\mu_{j}-\mu\right)^{\mathrm{T}} \end{aligned}$

其中 $m_j$ 是第 $j$ 个类别中的样本个数， $N$ 是总的类别个数。根据LDA的原理，可以将最大化的目标定义为：

$J(W)=\frac{\operatorname{tr}\left(W^{\mathrm{T}} S_{b} W\right)}{\operatorname{tr}\left(W^{\mathrm{T}} S_{w} W\right)}$

剩下的求解过程与之前二分类LDA相同。

至此我们得到了与PCA步骤类似，但具有多个类别标签高维数据的LDA求解方法：

1）计算数据集中每个类别样本的均值向量 $\mu_j$ ，及总体均值向量 $μ$ 。
2）计算类内散度矩阵 $S_w$ 和全局散度矩阵 $S_t$ ，得到类间散度矩阵 $S_b=S_t-S_w$ 。
3）对矩阵 $S_w^{-1}S_b$ 进行特征值分解，将特征值从大到小排列。
4）取特征值前 $d$ 大的特征值对应的特征向量 $w_1,\dots,w_d$ ，通过以下映
射将 $n$ 维样本映射到 $d$ 维：

从PCA和LDA两种降维方法的求解过程来看，它们确实有着很大的相似性，但对应的原理却有所区别。首先从目标出发，PCA选择的是投影后数据方差最大的方向。由于它是无监督的，因此PCA假设方差越大，信息量越多，用主成分来表示原始数据可以去除冗余的维度，达到降维。而LDA选择的是投影后类内方差小、类间方差大的方向，其用到了类别标签信息。为了找到数据中具有判别性的维度，使得原始数据在这些方向上投影后，不同类别尽可能区分开。

举一个简单的例子，在语音识别中，我们想从一段音频中提取出人的语音信号，这时可以使用PCA先进行降维，过滤掉一些固定频率（方差较小）的背景噪声。但如果我们的需求是从这段音频中区分出声音属于哪个人，那么我们应该使用LDA对数据进行降维，使每个人的语音信号具有区分性。

从应用的角度，我们可以掌握一个基本的原则一一对无监督的任务使用PCA进行降维，对有监督的则应用LDA。

葫芦书第四章——降维

1、PCA最大方差理论

1.1、如何定义主成分？从这种定义出发，如何设计目标函数使得降维达到提取主成份的目的？针对这个目标函数，如何对PCA问题进行求解？

2、PCA最小平方误差理论

2.1、PCA求解的真实是最佳投影方向，即一条直线，这与数学中线性回归问题的目标不谋而合，能否从回归的角度定义PCA的目标并相应地求解问题呢？

3、线性判别分析

3.1、对于具有类别标签的数据，应当如何设计目标函数使得降维的过程中不损失类别信息？在这种目标下，应当如何进行求解？

4、线性判别分析与主成分分析

4.1、LDA和PCA作为经典的降维算法，如何从应用的角度分析其原理的异同？从数学推导的角度，两种降维算法在目标函数上有何区别与联系？

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读