t-SNE：最好的降维方法之一

引言

本期由来自哈工大的同样热爱科普的潮汐之子为我们带来t-SNE的全方位普及，作者的研究方向为自然语言处理

说明

本文目的是做成一个60分钟t-SNE闪电入门简介，可能无法详细讲解原理，学术帝还请阅读原论文，或请移步我的另一篇博文，里面多了一些论文笔记，相关链接：

https://psubnwell.github.io/2017/12/01/paper-note-t-sne/

基础篇

认识高维空间：维数灾难

维数灾难（curse of dimensionality）：描述的是高维空间中若干迥异于低维空间、甚至反直觉的现象。该现象的详细论述可以阅读参考文献[1] ，其中通过超立方体和其内切球的推导十分精彩，这里不再赘述。

★高维空间中数据样本极其稀疏。需要维度几何级数的数据才能满足在高维空间密采样（dense sample）。反过来，高维数据降维到低维空间也将发生“拥挤问题（Crowding Problem）[2]”

★高维单位空间中数据几乎全部位于超立方体的边缘。

几何学能给出高维空间中超几何体的体积，单位超立方体的体积为：

而其内切超球体的体积公式如下：

对两者商做极限可得：

因此可以说一个高维单元空间只有边角，而没有中心。数据也只能处于边缘上，而远离中心。这样就直接导致了下一个性质：

★欧氏距离失效（因此任何基于欧氏距离的算法也失效）。

上图描述的是高维空间中大距离和小距离的差异越来越不明显：

这是由上一性质自然推导出的结论。

降维

降维（dimension reduction）的基本作用：

★缓解维数灾难。即提高样本密度，以及使基于欧氏距离的算法重新生效。

★数据预处理。对数据去冗余、降低信噪比。

★方便可视化。

降维的概念中有两对直觉性的概念会反复出现：高维/低维空间、高维/低维数据。在文献中他们有若干别称[3]：

★高维空间（high-dimensional space），又叫原空间（original space）

★高维数据（low-dimensional data），也直接叫数据点（data points），用于和下述的映射点对应。

★低维空间（low-dimensional space），又叫嵌入空间（embedded space）、低维映射（low-dimensional map，map在此做名词用）等。

★低维数据（low-dimensional data），又叫低维嵌入（low-dimensional embeddings）、低维表示（low-dimensional representations）、映射点（map points）等

嵌入（embedding）：数学上，嵌入是指一个数学结构经映射包含在另一个结构中。

★NLP目前所使用的词嵌入（word embedding）一词的本意可能就是这个意思。最初所使用的词向量是one-hot向量，维度等于词表大小（约几十万）。后来采用分布式表示的词向量，维度一般取几百维。因此我们认为分布式表示的词向量是更高维度语义空间的低维嵌入（embedding）。

★"Embed Everything！" 嵌入的思想不仅可以用在词（word）上，还能用于许多其他技术上。如知识图谱中可以把原先的网络结构也做嵌入，有实体嵌入、关系嵌入等。

降维技术可以分为线性和非线性两大类：

★线性降维技术。侧重让不相似的点在低维表示中分开。

①PCA（Principle Components Analysis，主成分分析）

②MDS（Multiple Dimensional Scaling，多维缩放）等

★非线性降维技术（广义上“非线性降维技术”≈“流形学习”，狭义上后者是前者子集）。这类技术假设高维数据实际上处于一个比所处空间维度低的非线性流形上，因此侧重让相似的近邻点在低维表示中靠近。

①Sammon mapping

②SNE（Stochastic Neighbor Embedding，随机近邻嵌入），t-SNE是基于SNE的。

③Isomap（Isometric Mapping，等度量映射）

④MVU（Maximum Variance Unfolding）

⑤LLE（Locally Linear Embedding，局部线性嵌入）等

流形学习

流形（manifold）：

★机器学习中指的流形指本征维度较低但嵌入在高维空间中的空间（a manifold haslow intrinsic dimensions, and isembeddedwithin a space of much higher dimensionality[4] ）。比如上图中的S-curve数据集，本征维度=2（摊开来是一个二维空间），但被嵌在三维空间中。

★数学中提到流形，强调其具有局部欧式空间的性质，可以在局部应用欧几里得距离。但是在机器学习（流形学习）中，这个假设基本不成立。原因是高维空间由于维数灾难的存在，没有足够稠密的数据能在足够小的局部去近似该流形[5] 。

★但是流形概念中局部的思想仍可以借鉴。它为降维提供了另一个视角：从微观角度去探索高维数据结构。

距离[6] ：想象你是一只蚂蚁，在图中的二维曲面流形上行走。

★高维直线距离：左图黑线。这个距离没有意义！

★测地线距离：左图红线，右图红虚线。这个距离才有意义！

★近邻距离：右图黑折线。用近邻距离可以拟合测地线距离。

学习：流形学习之所以叫学习，因为它不像PCA一类的纯线性代数降维方法，而是更像一个类似神经网络的学习算法。

★神经网络大部分是有监督学习；流形学习大部分是无监督学习。

★神经网络拟合一个分类函数；流形学习（以t-SNE为例）拟合高维数据的分布。

★神经网络学习参数；流形学习（以t-SNE为例）直接学习低维数据的表达。

★两者均有损失函数、梯度下降、迭代轮数等学习算法的特点。

学术篇

SNE

SNE（Stochastic Neighbor Embedding，随机近邻嵌入）[7]

SNE两个主要思路/步骤：

★将欧氏距离转化为条件概率来表征点间相似度（pairwise similarity）。

★使用梯度下降算法来使低维分布学习/拟合高维分布。

给定高维空间的数据点：

是以x_i自己为中心，以高斯分布选择x_j作为近邻点的条件概率：

注意：

1）对除i外其他所有j都计算一个条件概率后，形成一个概率分布列，所以分母需要归一化；

2）默认p_(i|i)=0；

3；每不同数据点x_i有不同的σ_i，在此不展开。

同理，有低维空间的映射点：

分别对应：

q_(j|i)是y_i以自己为中心，以高斯分布选择y_j作为近邻点的条件概率：

注意：这里方差统一取σ_i=1/√2，若方差取其他值，对结果影响仅仅是缩放而已。

SNE的目标是让低维分布去拟合高维分布，则目标是令两个分布一致。两个分布的一致程度可以使用相对熵（Mutual entropy，也叫做KL散度，Kullback-Leibler divergences，KLD）来衡量，可以以此定义代价函数（cost function）：

其中P_i (k=j)=p_(j|i) 和Q_i (k=j)=q_(j|i)是两个分布列。

注意：KLD是不对称的！因为 KLD=plog(p/q)，p>q时为正，p

对C进行梯度下降即可以学习到合适的y_i。

梯度公式：

带动量的梯度更新公式：（这里给出单个y_i点的梯度下降公式，显然需要对所有：Y^(T)=进行统一迭代。）

t-SNE

t-DistributedStochastic Neighbor Embedding[8]

事实上SNE并没有解决维度灾难带来的若干问题：

★拥挤问题（Crowding Problem）：在二维映射空间中，能容纳（高维空间中的）中等距离间隔点的空间，不会比能容纳（高维空间中的）相近点的空间大太多[9]。

★换言之，哪怕高维空间中离得较远的点，在低维空间中留不出这么多空间来映射。于是到最后高维空间中的点，尤其是远距离和中等距离的点，在低维空间中统统被塞在了一起，这就叫做“拥挤问题（Crowding Problem）”。

★拥挤问题带来的一个直接后果，就是高维空间中分离的簇，在低维中被分的不明显（但是可以分成一个个区块）。比如用SNE去可视化MNIST数据集的结果如下：

如何解决？高维空间保持高斯分布不变，将低维空间的分布做调整，使得两边尾巴比高维空间的高斯分布更高，即可缓解拥挤问题。想一想为什么？（在下面t-分布中解释）

★UNI-SNE[10]：给低维空间的点给予一个均匀分布（uniform dist），使得对于高维空间中距离较远的点（p_ij较小），强制保证在低维空间中q_ij>p_ij （因为均匀分布的两边比高斯分布的两边高出太多了）。

t-分布（Student's t-distribution）

★t-分布的概率密度函数（probability density function，PDF）形式为：

其中 ν 是自由度。

figure of probability density function

★当 ν=1:

叫做柯西分布（Cauchy distribution），我们用到是这个简单形式。

★当 ν=∞:

叫做高斯/正态分布（Guassian/Normal distribution）。

我们在低维空间的分布中，把原先用的高斯分布改成自由度为1的分布（把尾巴抬高）。下图可以很好地说明为什么“把尾巴抬高”可以很好地缓解拥挤问题。绘图代码参考 [11]

假设我们的低维数据分布对高维数据分布已经拟合完毕，则可以认为对于高维数据点x_i、x_j和低维映射点y_i、y_j，有p_ij=q_ij。我们用图中两条红线表示两种情况：

①上面的红线表示：当两个点相距相对近的时候，低维空间中比高维空间中相对更近。

②下面的红线表示：当两个点相距相对远的时候，低维空间中比高维空间中相对更远。

可以对比一下采用t-SNE对MNIST数据集的降维可视化效果: