SNE与t-SNE

来源

本文是对 从SNE到t-SNE再到LargeVis 的阅读笔记。

SNE

SNE原理是希望尽可能保存原数据的空间结构。

它利用条件概率来描述两个点之间的距离,距离越近,概率越大。之所以如此是因为直接使用欧式距离并不合适。[TBC]
\begin{split} p_{j|i} = \frac{\exp ((- \Vert x_i - x_j \Vert)^2)/2 \sigma^2}{\sum_{k \neq i} \exp ((- \Vert x_i - x_k \Vert)^2)/2 \sigma^2}\end{split}
其中 \(\sigma_i\) 是以 $x_i$ 为中心点的高斯分布的方差。设定 $p_{i|i} = 0$ 。
降维后对应 \( y_i\) 点的条件分布相似定义,但是方差直接定为 \(\frac{1}{\sqrt{2}}\) ,有:
\begin{split} q_{j|i} = \frac{\exp ((- \Vert y_i - y_j \Vert)^2)}{\sum_{k \neq i} \exp ((- \Vert y_i - y_k \Vert)^2)}\end{split}

我们希望降维后点的条件概率分布应当尽可能与原数据条件概率一致。故而选择KL散度作为代价函数。
\begin{split} C = \sum_i KL(P_i \Vert Q_i) = \sum_i \sum_j p_{j|i} \log \frac{p_{j|i}}{q_{j|i}}\end{split}
但是由于KL的不对称性,会出现一个问题:当p大q小时,代价较高,反之,则代价较低。因此代价函数更关注局部结构而忽视了全局结构。

t-SNE

t-SNE解决了SNE的两个问题:对称性和拥挤问题。

先看对称性。(我并没有理解它是如何解决KL不对称带来的代价函数不对称性的[TBC])
在SNE中,$p_{i|j}$ 和 $p_{j|i}$ 是不对等的,降维后的空间中也是如此。因此现在我们寻找一个满足对称性的联合概率分布:
\begin{split} q_{ij} = \frac{\exp ((- \Vert y_i - y_j \Vert)^2)}{\sum_{k \neq l} \exp ((- \Vert y_l - y_k \Vert)^2)}\end{split}

那么,在原空间是否也可以这样定义呢?如果这样,考虑一个离群点 $x_i$ ,那么对任意j, $p_{ij}$ 都会较小,从而不管降维后处于什么位置,代价都不会太大。
故而采用更简单直观的方式进行定义:
\begin{split} p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}\end{split}
代价函数为:
\begin{split} C = \sum_i KL(P_i \Vert Q_i) = \sum_i \sum_j p_{ij} \log \frac{p_{ij}}{q_{ij}}\end{split}

在来看拥挤问题的解决。
在SNE时,虽然可以区分出不同类,但是类间边界并不明显,不同类依旧簇拥在一起,这就是拥挤问题。

通过对降维数据使用自由度为1的t分布描述条件概率,就可以解决这个问题。
\begin{split} q_{ij} = \frac{(1 + (\Vert y_i - y_j \Vert)^2)^{-1}}{\sum_{k \neq l} (1 + (\Vert y_k - y_l \Vert)^2)^{-1}}\end{split}
原数据空间依旧使用高斯分布。

我们通过以下两幅图来描述使用t分布的好处。

首先,t分布是长尾分布,对于边缘异常值不敏感,因此可以更好的捕捉全局特征。

其次,高斯分布转t分布,可以使得邻近点间距离更近,距离大的点间距离更大,从而有效分离不同类。