随机邻域嵌入

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

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

SNE 即 Stochastic Neighbor Embedding，是一种非常高效的非线性降维算法。SNE 算法利用了每一个数据点的邻近数据点的分布来做降维。给定一个高维的数据集 X={x1,x2,...xn}, 需要将这个高维的数据集映射到一个低维的数据集 Y={y1,y2,...yn}，为了数据便于显示，Y 的维度一般是二维或者三维。为了衡量高维数据的相似性，SNE算法设置了一个条件概率：

对于每一个目标i,选取邻居J的概率是，使用非对称概率 (asymmetric probability)：

pj|i衡量的是数据点 j 作为数据点 i 的邻域的概率，这个分布类似一个高斯分布，很显然，离xi 越近的点，pj|i的值越大，而离得越远的点，那么概率就会越小，利用这个条件概率来表示每一对数据点的相似性，因为我们考虑的是数据点与数据点之间的关系，不考虑数据点自身与自身的关系，所以 pi|i=0，σi是方差，后面会介绍如何设置这个方差。接下来，要考虑映射后的低维空间 Y 的数据分布，同样可以用条件概率来表示:

在低纬度的空间中，这里在没有失去通用性的情况下，将方差设置为一个固定值1/2，所以高斯函数的分母变为1，如果空间 Y的数据分布可以很好地拟合数据在空间 X的分布，那么两者的条件概率应该是一样的，即 pj|i 和 qj|i 是相等的。基于这一点，SNE算法就是想找到这样一个低维空间Y，使得数据集在两个空间的条件概率尽可能接近，可以用 KL散度，Kullback-Leibler divergence 来衡量：

Pi 表示数据集X 中所有其他数据点相对xi的条件概率，Qi 表示数据集Y 中所有其他数据点相对yi 的条件概率。从上面的表达式可以看出，SNE算法侧重于保持数据的局部结构。为了设置 σi，可以定义一个复杂度 perplexity:

H(Pi)s是信息熵

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

为了加速收敛以及增加鲁棒性，可以引入动量项 (momentum term):

上图是Hinton等在2003年的论文中的实验结果，使用SNE算法对3000个256个维度的数据进行降维。

【出处：http://papers.nips.cc/paper/2276-stochastic-neighbor-embedding.pdf]

发展历史

降维方法

降维方法分为线性和非线性降维，非线性降维又分为基于核函数和基于特征值的方法。

1、线性降维方法：PCA 、ICA LDA、LFA、LPP(LE的线性表示)

2、非线性降维方法：

（1）基于核函数的非线性降维方法：KPCA 、KICA、KDA

（2）基于特征值的非线性降维方法（流型学习）：ISOMAP、LLE、LE、LPP、LTSA、MVU

典型降维方法介绍

1、LLE（Locally Linear Embedding）算法（局部线性嵌入）：

每一个数据点都可以由其近邻点的线性加权组合构造得到。

算法的主要步骤分为三步：

（1）寻找每个样本点的k个近邻点（k是一个预先给定的值）；

（2）由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；

（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值，定义一个误差函数。

Wold, S., Esbensen, K., & Geladi, P提出了PCA算法。Principal Component Analysis(PCA)是最常用的线性降维方法，它的目标是通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。

Mika, S., Ratsch, G., Weston, J., Scholkopf, B., & Mullers, K. R.在1999年提出Linear Discriminant Analysis算法。Linear Discriminant Analysis(也有叫做Fisher Linear Discriminant)是一种有监督的（supervised）线性降维算法。与PCA保持数据信息不同，LDA是为了使得降维后的数据点尽可能地容易被区分！

2000年。Roweis, S. T., & Saul, L. K.使用LLE进行非线性降维。Locally linear embedding（LLE） 是一种非线性降维算法，它能够使降维后的数据较好地保持原有 流形结构 。LLE可以说是流形学习方法最经典的工作之一。很多后续的流形学习、降维方法都与LLE有密切联系。

2003年，Hinton, G. E., & Roweis, S. T.提出SNE算法进行降维。2008年，Maaten, L. V. D., & Hinton, G.提出T-SNE，是一个强大的降维算法。t-SNE 就是利用一个 student-distribution 来表示低维空间的概率分布。

PCA,LDA，LLE，这里讲一讲Laplacian Eigenmaps。每一个算法都是从不同角度去看问题，因此解决问题的思路是不一样的。这些降维算法的思想都很 简单，却在有些方面很有效。这些方法事实上是后面一些新的算法的思路来源。Laplacian Eigenmaps看问题的角度和LLE有些相似，也是用局部的角度去构建数据之间的关系

主要事件

发展分析

瓶颈

PCA追求的是在降维之后能够最大化保持数据的内在信息，并通过衡量在投影方向上的数据方差的大小来衡量该方向的重要性。但是这样投影以后对数据的区分作用并不大，反而可能使得数据点揉杂在一起无法区分。这也是PCA存在的最大一个问题，这导致使用PCA在很多情况下的分类效果并不好。

如果数据分布在整个封闭的球面上，Locally linear embedding 则不能将它映射到二维空间，且不能保持原有的数据流形。

t-SNE 唯一的不足在于它的时间复杂度比较高，对于上十万的数据规模可能需要一台工作站要运行数分钟。

未来发展方向

在今后的工作中，计划研究在T-SNE，Student-t distribution 的自由度数量的优化。当低维表示有多个维度时，这可能有助于降维。T-SNE扩展模型中，每个高维数据点是仿照由若干低维地图分为Cook。可以开发一个参数化版本的T-SNE，可以推广到了试验数据利用T-SNE目标函数训练多层神经网络的低维空间提供了一个明确的定位。

[来源：Visualizing Data using t-SNE ; 链接：http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf ]

Contributor：Ruiying Cai