SNE与t-SNE降维算法理解

1. SNE概要

数据降维,大体分为线性方法和非线性方法。其中线性方法例如PCA和LDA,而非线性方法又有保留局部特征、基于全局特征等方法。有人整理了一张分类图,下面这张图从网上引用而来:

相比于其他降维方法,t-SNE是近年比较火热的一种高维数据可视化技术,能够通过降维,将高维数据降维并给出二维或三维的坐标点,从而可以在人能够轻易理解的平面或立体空间内将数据可视化出来。这个方法是SNE的变种,SNE是Hinton在2002年提出来的方法。Stochastic Neighbor Embedding,好吧,又是embedding。目标是将高维数据映射到低维后,尽量保持数据点之间的空间结构,这样在高维空间里距离较远的点,在低维空间中依然保持较远的距离。在传统的方法中,PCA和MDS是线性技术,用于保持相距较远的数据点之间的低维表示。Maaten将t-SNE的降维结果与其他7种降维方法的结果,在5种不同的数据集中作了对比。

1.1 高维数据的相似度概率分布

SNE将数据点之间高维的欧氏距离转换为表示相似度的条件概率,即用条件概率\(p(j|i)\)表示点\(x_j\)到点\(x_i\)的相似度,这个含义可以理解为:若以\(x_i\)为中心的高斯分布来选取邻居,则\(x_i\)选择\(x_j\)作为自己邻居的概率是\(p(j|i)\)。若数据点相距较近,则\(p(j|i)\)较大,相反若数据点相距非常远,\(p(j|i)\)则可以接近无穷小。条件概率\(p(j|i)\)定义如下:

\[
p(j|i)= {exp({-\Vert x_i-x_j\Vert^2 \over 2\sigma_i^2}) \over \sum_{k\neq i}exp({-\Vert x_i-x_k\Vert^2 \over 2\sigma_i^2})}
\]

高斯模型的方差选择

上面的公式中,\(\sigma_i\)是以\(x_i\)为中心的高斯分布的方差。因为数据点的稠密程度不同,因此这个方差选用单个固定值是不合理的,例如在密度高的区域适合选用较小的方差值。可以认为任意一个特定的方差\(\sigma_i\)代表了一个一个数据点对于其他所有数据点的概率分布\(P_i\)。论文引入了一个固定值,困惑度(perplexity),用来二分搜索这个合适的\(\sigma_i\)。而perplexity本身是由用户指定的,其定义为:

\[Perp(P_i)=2^{H(P_i)}\]

其中,\(H(P_i)\)是概率分布\(P_i\)的熵:

\[H(P_i)=-\sum_j{p_{j|i}log_2{p_{j|i}}}\]

perplexity可以理解为一个选择有效邻居数目的平滑方法。论文给出了典型的取值范围是5到50。

1.2 映射到低维后的相似度概率分布

考虑到目标是衡量点对间的相似度,因此令\(p(i|i)\)为0。同样,对于低维点\(y_i\)(对应高维\(x_i\))和\(y_j\)(对应高维\(x_j\)),也可以估算类似的条件概率,一下表示为\(q(j|i)\),在这里,我们将高斯分布的所有方差\(\sigma_i\)设为\(1 \over \sqrt{2}\)。这样,下面的\(q(j|i)\)公式就被定义为用来描述图上的点\(y_j\)和点\(y_i\)之间的相似度:

\[
q(j|i)={exp({-\Vert y_i-y_j\Vert^2}) \over \sum_{k\neq i}exp({-\Vert y_i-y_k\Vert^2})}
\]

这就是\(y_i\)和\(y_j\)之间的相似概率,并同样设置\(q(i|i)=0\)。这个时候,理论上,如果低维点正确地表示了高维点,那\(p(j|i)\)和\(q(j|i)\)这两个概率应当相等。至于说用\(q(j|i)\)代表\(p(j|i)\)是否靠谱,论文中选择用KL散度(Kullback-Leibler divergence)来衡量。SNE使用梯度下降法在所有的数据点上最小化KL散度之和。损失函数如下:
\[
C = \sum_iKL(P_i\Vert Q_i)=\sum_i \sum_j p(j|i)log{p(j|i)\over q(j|i)}
\]

\(P_i\)表示在给定数据点\(x_i\)基础上,其他所以数据点的条件概率分布。
\(Q_i\)表示在给定低维映射数据点\(y_i\)基础上所有其他低维映射数据点的条件概率分布。

由于KL散度并不具有对称性,所以数据点对距离之间的不同类型的错误在权重上是不均匀的。简单来说,从\(P\)到\(Q\)的度量通常并不等于从\(Q\)到\(P\)的度量。在这里的场景下,可以理解为,当使用较分散的低维点来表示较聚集的高维数据点时(例如用较小的\(q(j|i)\)来表示一个较大的\(p(j|i)\)),损失值较大;而使用较聚集的低维点来表示分布较分散的高维数据点,则损失值较小(因为只损失了概率分布Q中的一部分概率质量)。因此,最小化SNE损失函数的意义,在于通过取得高维空间高斯分布的合理的方差值,在低维中尽可能多地保留数据的局部结构。没错,是局部结构。这意味着当高维数据数据点之间距离较远时,从损失函数看,若映射所得的低维点距离很近,损失反倒很小,是明显不合理的。

对损失函数对\(y_i\)求梯度后可以得到:
\[
\frac{\delta C}{\delta y_i}=2\sum_{j}(p(j|i)-q(j|i)+p(i|j)-q(i|j))(y_i-y_j)
\]

作者将这个梯度的物理意义理解为是一种合力,这个合力是由低维点\(y_i\)和其他所有点\(y_j\)之间的各种力共同构成的,且所有的力的方向是沿着\((y_i-y_j)\)。用\(y_i\)和\(y_j\)距离表示高维数据点之间,两两数据对可以看做一个弹簧,若这个距离太近了,则这种力表现为斥力;若距离太远,便表现为引力。弹簧的力量与长度和刚度成正比,而\((p(j|i)-q(j|i)+p(i|j)-q(i|j))\)所表征的偏差值与此有关。

2. t-SNE的改进

t-SNE重点解决了两个问题,一个是SNE的不对称问题(用联合概率分布替代条件概率分布),另一个是不同类别之间簇的拥挤问题(引入\(t\)分布)。

2.1 不对称问题

Maaten采用的方法是用联合概率分布来替代条件概率分布。高维数据下的联合概率分布为\(P\),低维环境下的联合概率分布为\(Q\),使得\(\forall i,j\),\(p_{ij}=p_{ji}\),\(q_{ij}=q_{ji}\)。

定义低维空间的联合概率:
\[
q_{ij}=\frac{\exp (-\left \| y_i-y_j \right \|^2)}{\sum_{k \neq l}\exp (-\left \| y_k-y_l \right \|^2)}
\]

按理说高维空间的概率应定义为:

\[
p_{ij}=\frac{\exp (-\left \| x_i-x_j \right \|^2/2\sigma^2)}{\sum_{k \neq l}\exp (-\left \| x_k-x_l \right \|^2/2\sigma^2)}
\]

然而这种情况下,一旦数据点\(x_i\)在距离群簇非常远,则\({\Vert x_i-x_j \Vert}^2\)的值会很大,而\(p_{ij}\)会相应变得非常小,也就是说\(x_i\)的位置很远这件事情对损失函数影响很小(没有足够的惩罚),那这个点在低维空间中将无法从其他点中区分出来。因此Maaten提出了对称的条件概率来重新定义上述联合概率\(p_{ij}\),对于数量为\(n\)的数据点,新的概率公式是:

\[
p_{ij}=\frac{p_{j|i}+p_{i|j}}{2n}
\]

至此,损失函数可修改为:
\[
C=KL(P||Q)=\sum_i \sum_j p_{ij}\log \frac{p_{ij}}{q_{ij}}
\]

对\(y_i\)的梯度也一下子简化了不少:

\[
\frac{\delta C}{\delta y_i}=4\sum_{j}(p_{ij}-q_{ij})(y_i-y_j)
\]

2.2 拥挤问题

拥挤问题,就是从高维空间映射到低维空间后,不同类别的簇容易挤在一起,无法较好地区分开。名字就表明了意图,t-sne解决这个问题的方式是t分布,准确地说是自由度为1的\(t\)分布,也就是柯西分布。\(t\)分布具有长尾特性,相比于正太分布,柯西分布在尾部趋向于0的速度更慢。因此t-sne在低为空间中引入这种分布,既能解决拥挤问题,又能解决优化问题。

因此,使用柯西分布重新定义\(q_{ij}\):

\[
q_{ij}=\frac{ (1 + \left \| y_i-y_j \right \|^2)^{-1}}{\sum_{k \neq l} (1 + \left \| y_k-y_l \right \|^2)^{-1}}
\]

同样的,梯度变为:

\[
\frac{\delta C}{\delta y_i}=4\sum_{j}(p_{ij}-q_{ij})(y_i-y_j)(1 + \left \| y_i-y_j \right \|^2)^{-1}
\]

至于为什么要选择这样的分布,由于柯西分布尾部更厚的特性特性,因此,\((1-{\Vert y_i-y_j \Vert}^2)^{-1}\)几乎就是与\(\Vert y_i-y_j \Vert\)直接成反比,而后者能表示在低维空间中相距较大的点对,接近平方反比定律,也就是说,能够使得相似度低的对象能够更好地拉开距离。

总而言之,可以看出t-SNE的终极目标是通过最小化数据点在高维空间和低维空间中的KL距离,来保持相邻的点在两个不同空间中的分布是相似性。在高维空间中,使用高斯分布来刻划两个点之间的相似度,而在低维空间中,使用t分布来计算。
论文提供了较多实验分析,很详细,在此略过,下图是其中MNIST数据集的实验效果。

3. 应用与误读

降维和探索数据,是比较常讲的两个词,我认为本质上说,是一种降维思想的技术方法,但实际用途,目前来说更多的是辅助探索数据。原因么,很难可视化的数据被可以用二维或三维的点来表示,所有的团簇和距离关系被拉到了人眼所能理解的笛卡尔坐标系下面,这种状态下,相比于机器模式识别,更是人眼的强项。

对于模型的不同参数作用于不同数据的理解,强烈推荐distill.pub上的这篇文章:How to Use t-SNE Effectively,另外,云栖社区上有个翻译版。这篇文章里罗列了大量的动态可视化的效果,来说明不同数据、不同参数对可视化效果的影响,也感叹随着模型灵活度的提高,分析结果的理解难度也随之加大。

具体,作者有如下有学习意义的结论或部分猜测:
1. Those hyperparameters really matter
2. Cluster sizes in a t-SNE plot mean nothing
3. Distances between clusters might not mean anything
4. Random noise doesn’t always look random
5. You can see some shapes, sometimes
6. For topology, you may need more than one plot

这篇文章对于理解模型各部件对数据具体可能带来什么影响,以及减少对数据的误读,有非常直观的实验意义。正如作者对文章url的命名:misread-tsne。