机器学习: t-Stochastic Neighbor Embedding 降维算法 (一)

本文主要是介绍机器学习: t-Stochastic Neighbor Embedding 降维算法 (一)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Introduction

在计算机视觉及机器学习领域，数据的可视化是非常重要的一个应用，一般我们处理的数据都是成百上千维的，但是我们知道，目前我们可以感知的数据维度最多只有三维，超出三维的数据是没有办法直接显示出来的，所以需要做降维的处理，数据的降维，简单来说就是将高维度的数据映射到较低的维度，如果要能达到数据可视化的目的，就要将数据映射到二维或者三维空间。数据的降维是一种无监督的学习过程，我们可以看成是一种聚类。数据在空间的分布主要有两个特性，一个是相似性，我们可以用类内距离衡量；一个是差异性，可以用类间距离衡量。降维算法，在将数据从高维空间映射到低维空间的时候，需要考虑数据的这两个分布特性，也就是要保持数据在高维空间的分布特性。

降维的算法有很多，最经典的就是PCA了，也就是我们常说的主分量分析，PCA是基于数据集的协方差矩阵，考虑的更多是数据的差异性，而对于数据的相似性，或者说数据的局部分布，类似PCA的线性降维算法是无能为力的。

今天，我们介绍一种非常高效的非线性降维算法: t-SNE，t-SNE 算法可以非常有效地把高维的数据映射到低维的空间，并且保持数据在高维空间的局部结构。t-SNE 算法是 SNE 算法的一个延伸，SNE 即 Stochastic Neighbor Embedding 的简称，SNE 算法利用了每一个数据点的邻近数据点的分布来做降维。在介绍 t-SNE 之前，我们先来看看 SNE 算法。

Stochastic Neighbor Embedding

给定一个高维的数据集 $\mathcal{X}=\{x_{1}, x_{2}, ... x_{n}\}$, 我们需要将这个高维的数据集映射到一个低维的数据集 $\mathcal{Y}=\{y_{1}, y_{2}, ... y_{n}\}$，为了数据便于显示，$\mathcal{Y}$ 的维度一般是二维或者三维。为了衡量高维数据的相似性，SNE算法设置了一个条件概率：

$$p_{j|i} =\frac{\text{exp} ( -\| x_{i}-x_{j}\|^{2}/(2 \sigma_{i}^{2}) )}{\sum_{k \neq i}\text{exp}(-\| x_{i}-x_{k} \|^{2}/(2 \sigma_{i}^{2}))}$$

$p_{j|i}$ 衡量的是数据点 $j$ 作为数据点 $i$ 的邻域的概率，这个分布类似一个高斯分布，很显然，离$x_{i}$ 越近的点，$p_{j|i}$ 的值越大，而离得越远的点，那么概率就会越小，利用这个条件概率来表示每一对数据点的相似性，因为我们考虑的是数据点与数据点之间的关系，不考虑数据点自身与自身的关系，所以 $p_{i|i}=0$，$\sigma_{i}$ 是方差，后面会介绍如何设置这个方差。

接下来，我们要考虑映射后的低维空间 $\mathcal{Y}$ 的数据分布，同样可以用条件概率来表示:

$$q_{j|i} =\frac{\text{exp} ( -\| y_{i}-y_{j}\|^{2} )}{\sum_{k \neq i}\text{exp}(-\| y_{i}-y_{k} \|^{2})}$$

这里将方差设置为$\frac{1}{\sqrt{2}}$，所以高斯函数的分母变为1，如果空间 $\mathcal{Y}$ 的数据分布可以很好地拟合数据在空间 $\mathcal{X}$ 的分布，那么两者的条件概率应该是一样的，即 $p_{j|i}$ 和 $q_{j|i}$ 是相等的，基于这一点，SNE算法就是想找到这样一个低维空间$\mathcal{Y}$，使得数据集在两个空间的条件概率尽可能接近，可以用 Kullback-Leibler divergence 来衡量：

$$C=\sum_{i} KL(P_{i} \| Q_{i}) = \sum_{i}\sum_{j} p_{j|i} \text{log}\frac{p_{j|i}}{q_{j|i}}$$

$P_{i}$ 表示数据集$\mathcal{X}$ 中所有其他数据点相对$x_{i}$ 的条件概率，$Q_{i}$ 表示数据集$\mathcal{Y}$ 中所有其他数据点相对$y_{i}$ 的条件概率。从上面的表达式可以看出，SNE算法侧重于保持数据的局部结构。为了设置 $\sigma_{i}$，可以定义一个 perplexity:

$$Perp(P_{i}) = 2^{H(P_{i})}$$

$H(P_{i})$ 就是我们所说的信息熵

$$H(P_{i}) = - \sum_{j} p_{j| i} \text{log}_{2}p_{j | i}$$

利用梯度下降算法，我们可以得到如下的表达式:

$$\frac{\partial C}{\partial y_{i}} = 2 \sum_{j} (p_{j|i}-q_{j|i}+p_{i|j}-q_{i|j})(y_{i} - y_{j})$$

为了加速收敛以及增加鲁棒性，可以引入 momentum term

$$\mathcal{Y^{(t)}} = \mathcal{Y^{(t-1)}} + \eta \frac{\partial C}{\partial \mathcal{Y}} + \alpha(t) \left(\mathcal{Y^{(t-1)}} - \mathcal{Y^{(t-2)}} \right)$$

这篇关于机器学习: t-Stochastic Neighbor Embedding 降维算法 (一)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---