数据降维和可视化:t分布随机近邻嵌入(t-SNE)学习

2019/02/27 Machine Learning

t-SNE(t-distributed Stochastic Neighbor Embedding)被称为是最好的降维方法,而在实际应用中,它更常见的用处是高维数据的可视化。在选择模型之前对数据有一个直观的先验了解是十分有必要的。

降维方法总结

在讲解t-SNE之前,先简单回忆一下有哪些其他常见的降维方法。首先教科书中最耳熟能详的方法当属PCA了,PCA是一个线性降维方法,是高维空间在低维空间中的线性映射,且尽量选择了保留原信息最多的低维空间。其他的线性方法还有LDA、MDS等。相对应的,AutoEncoder是一个非线性的降维方法,神经网络中非线性激活函数的存在使其可以挖掘出更多信息。这两种方法各自同时还都有生成式的版本,分别对应着概率PCA和VAE。VAE的介绍可以参见我之前的文章变分自编码器(VAE)学习,这几种方法的区别与联系可以参考这篇文章,我觉得写得非常有逻辑。

而t-SNE作为一个降维方法,其实更多的作用是把高维数据映射到人类可以理解的三维或者二维空间并可视化。它降维后得到的数据没有度量的意义,也就是说,它只是使同类别的数据离得尽可能近,同时不同类别的数据离得尽可能远,而直接度量降维后两个数据点之间的距离是没有意义的。因此,我们不能直接使用降维后的数据做下一步操作,如分类回归等。这是它与常见降维方法最大的区别。但是以数据可视化为目的,t-SNE是远好于其他方法的。

流形学习

t-SNE是流形学习(Manifold Learning)分支下的一种模型。其实不懂流形学习并不影响我们理解t-SNE,这里只是对其做一个简单的介绍,完全可以跳过。

流形(Manifold)是局部具有欧式空间性质的空间,包括各种纬度的曲线曲面,例如球体、弯曲的平面等。流形的局部和欧式空间是同构的。但是在全局尺度下不能简单的用欧式几何计算。一个好理解的例子就是地球,我们在几米的尺度下计算三角形的内角和是180度,但是在几百公里的尺度下会大于180度。因为地球上有意义的数据点是分布在球面上的,此时需要引入黎曼几何来描述问题。可见流形空间在真实世界中其实是大量存在的,所以我们对数据进行了一个假设,假设数据都是在高维欧式空间中的低维流形,如果我们能将其降维到低维,就能直观的发现其本质和一些内在规律。t-SNE就是基于这样的一个假设。

t分布

再来回顾一下t分布。学生t-分布(t-distribution)用于根据小样本来估计呈正态分布且方差未知的总体的均值。其曲线形态与自由度有关,自由度越小,t分布越平坦;自由度为无穷时,t分布等同于标准正态分布。本文主要目的是理解t-SNE,所以只需要知道t-分布的解析式和曲线形状(见下图)即可,更多的内容请自行Wiki。

SNE

t-SNE可以看做是SNE的改进,所以我们从SNE开始说起。SNE的核心思路可以概括如下:

在高维空间相似的数据点,映射到低维空间距离也是相似的。常规的做法是用欧式距离表示这种相似性,而SNE把这种距离关系转换为一种条件概率来表示相似性。并使高维和低维下每个数据点对于其他数据点的相似性分布尽量接近。

对于高维空间中每一个数据点 $x_i$来说,$x_j$是剩下的每个数据点,我们可以算出 $x_i$ 和每一个 $x_j$ 的欧式距离 $d_j$ 。但是不同维度下的欧式距离没有可比性,所以SNE的想法是构造一个概率来表征出这种距离的相似度来,一个合适易求导的分布就是高斯分布。构造一个 $\mu = x_i$ 的高斯分布,并假设 $\sigma=\sigma_i$ 是已知的(方差如何选择会在后面讨论)。那么每个 $x_j$ 和 $x_j$ 的距离对应的概率就可以作为相似度的度量。如下图,显然距离远的点相似度很底,距离近的点相似度很高。

那么这个“高斯相似度”可以定义如下

另外因为我们只考虑不同数据点之间的相似度,所以定义 $sim(x_i, x_i) = 0$

对 $x_i$ 和所有的 $x_j$ 计算相似度,我们就可以得到 $ x_i$ 的相似度分布了,这个分布每一点的概率可以写成条件概率的形式,为了保证概率和为1,需要做归一化。即:

相应的,在低维度我们做同样的处理,设 $x_i$ 在低维的映射是 $y_i$ ,则可以得到低维下拟合每对数据点相似度的条件概率 $q_{j \vert i}$ 。另外由于我们可以任意假设低维下数据点的分布,为了方便和好看就设置每个数据点的相似度分布(同样是高斯分布)的 $\sigma = \frac{1}{\sqrt 2}$ 。于是有

此时就很明朗了,如果 $y_i$ 和 $y_j$ 能真实反映 $x_i$ 和 $x_j$ 的关系,那么 $p_{j \vert i}$ 和 $q_{j \vert i}$ 就应该是完全相等的。我们对所有j计算条件概率,就能得到这个条件概率的完整分布 $P_i$ 。同理可以得到低维下的分布 $Q_i$ 。我们的目标就是使两个分布尽量接近,自然而然想到了KL散度。于是SNE的代价函数就可以写出来了,用梯度下降求解即可。

求梯度的过程参考softmax函数的梯度,这里不重要,省略过程。对 $y_i$ 求梯度得到

其实这个梯度是有一定物理意义的,可以把 $y_i$ 看做一个分子,它最终的受力方向是由所有其他分子对它的合力决定的。对其中一个分子j来说, $(p_{j \mid i} - q_{j \mid i} + p_{i \mid j} - q_{i \mid j})$ 决定了力的大小,$(y_i - y_j)$ 决定了力的方向。在初始化中,可以用较小的 $\sigma$ 下的高斯分布来进行初始化。为了加速优化过程和避免陷入局部最优解,梯度中需要使用一个相对较大的动量(momentum)。即参数更新中除了当前的梯度,还要引入之前的梯度累加的指数衰减项,如下:

这里的 $Y(t)$ 表示迭代t次的解,$\eta$ 表示学习速率, $\alpha(t)$ 表示迭代t次的动量。另外SNE在超参数的选择上需要做多次优化才可以。

困惑度(Perplexity)

刚才在构建 $q_{j \vert i}$ 时,我们假设已知了每个 $x_i$ 的高斯相似度分布的 $\sigma$ 。那 $\sigma$ 究竟应该怎么设置呢?SNE的唯一参数困惑度就是用来为每个数据点 $x_i$ 寻找合适的 $\sigma_i$ 的。困惑度可以定义为

其中 $H(P_i)$ 是 $P_i$ 的香农熵。从直观上是可以理解这个式子的,数据越混乱,熵越大,为了使每个数据点的困惑度都满足给定的困惑度,就需要一个很大的 $\sigma_i$使高斯分布尽量平坦,这样得到的每个 $p_{j \vert i}$ 就更接近一些。实际上我们经常将Perp设置为近邻数,因为增大 $\sigma$ 就相当于增加近邻数据点。困惑度通常会被设置为 5 - 50 之间,并且在这个范围内具有良好的鲁棒性。

因为 $\sigma_i$ 和 $Perp(P_i)$是线性相关的,所以当设置好Perp后,我们可以简单的用 Binary Search 去为每个高斯分布找一个对应的 $\sigma_i$ 。

Symmetric SNE

SNE设计出来之后,效果其实并没有想象的那么好。在人们尝试着去寻找优化方案时发现了这样一个问题, $p_{j \vert i}$ 和 $p_{i \vert j}$ 是不对称的。这违背了相似度这个概念的初衷,Symmetric SNE 就是来解决这个问题的。

Symmetric SNE 把条件概率转换为了联合概率去度量相似度,这样就确保了对称性。在实践中联合概率采用了一种简单直观的定义方式

其中n为数据点总数。这样定义既保证了对称性,又保证了每个点对总代价的贡献都不会太小(因为 $\sum_j p_{ij} \geq \frac{1}{2n}$ )。此外,由联合分布计算出的梯度拥有更简单的形式,计算效率更高了。

拥挤问题(The Crowding Problem)

虽然 Symmetric SNE 解决了不对称问题,但是其得到的结果类边界也还是有一些模糊。这里涉及到了一个从高维降到低维所面临的拥挤问题。举个例子,我们假设在10维空间中有11个点两两距离相等,但是其降到可以可视化的二维后,我们是没有办法保存它们距离两两相等的信息的,因为在二维空间中最多只有三个点的距离可以两两相等。

再假设在三维空间里有一个球体,数据点在球体内均匀分布。如果想把它降到二维,根据各个点到球心的距离,会得到一个圆形范围,且越靠近球面的数据点越密集。同理,越是高维的“球体”,降到低维后边缘越拥挤,因为高维球体的体积是呈 $r^d$ 增长的。这就是所谓的拥挤问题,降维后的簇会拥挤在一起无法区分,SNE 和 Symmetric SNE 都不能很好地解决这个问题。

t-SNE

终于等到t-SNE出场了,t-SNE在SNE的基础上做出了如下两个改进:

  1. 使用联合概率代替条件概率(同 Symmetric SNE)
  2. 在低维空间使用t分布代替高斯分布(高维空间不变)

其中第一个改进保证了对称性和代价函数的下限,第二个改进一定程度上解决了拥挤问题。那么t分布是怎么解决拥挤问题的呢?

t分布有一个重要的特点:属于长尾分布。我们看上图,高斯分布在3sigma后的概率密度就变得特别小,因此为了迎合长尾部分的数据,它会主动变得平坦,从而导致拟合不准确。或者可以说,高斯分布对异常值较为敏感。而t分布的长尾特性使其既能兼顾均值周围的数据点,又能兼顾边缘的数据点,更好的捕获了数据的特征。

除此之外,高斯分布和t分布的差异也有助于缓解拥挤问题。我们看上图,横轴表示距离,纵轴表示相似度, 可以看到,对于较大相似度的点,t分布在低维空间中的距离需要稍小一点;而对于低相似度的点,t分布在低维空间中的距离需要更远。这恰好满足了我们的需求,即同一簇内的点(距离较近)聚合的更紧密,不同簇之间的点(距离较远)更加疏远。

使用了自由度为1的t分布后, $q_{ij}$ 变成了:

可以看出公式里少了指数函数,计算上会方便很多。最终得到t-SNE的更新梯度(推导见原论文Appendix)是

然后再利用梯度下降求解 $y_i$ 即可。

效果

用论文里的图展示一下t-SNE降维后的效果,总体是完爆其他可视化降维方法的。与其他方法的对比图可以去原论文看一下。

局部最优解

需要理解的是,t-SNE得到的是局部最优解。因为KL散度是一个不对称的度量,从代价函数的公式中可以看出,当 $p_{j \vert i}$ 较大, $q_{j \vert i}$ 较小时,代价较高;而当 $q_{j \vert i}$ 较大, $p_{j \vert i}$ 较小时,代价较低。什么意思呢?就是当高维空间距离远,低维空间距离近的时候,代价函数会很高,模型会尽量避免这种事情发生,所以会加大低维的距离,这没问题。但是当高维近低维远的时候,代价会变低,模型也就不会在乎这个问题,导致低维空间距离较远的点始终拉不近。换句话说,t-SNE的代价函数更关注局部结构,而忽视了全局结构。所以假设数据集是在高维空间中的低维流形这一点是比较重要的,如果数据集的本征维度本身就很高,那么是不可能完整的映射到2-3维空间的。

参考

原论文 Visualizing data using t-SNE, Laurens van der Maaten and Geoffrey Hintton, Journel of machine learning research, 2008.

http://bindog.github.io/blog/2016/06/04/from-sne-to-tsne-to-largevis/

https://www.jiqizhixin.com/articles/2017-11-13-7

http://www.datakit.cn/blog/2017/02/05/t_sne_full.html

https://www.youtube.com/watch?v=NEaUSP4YerM&feature=youtu.be

Search

    Table of Contents