机器学习降维方法 t-SNE 详解（一）

本文主要介绍一种用于降维和可视化的算法t-SNE，并且对其原理与使用进行讲解，本篇为第一部分

t-SNE与SNE

SNE

t-SNE的全称是t-Distributed Stochastic Neighbor Embedding，SNE就是 Stochastic Neighbor Embedding，所以要想了解t-SNE势必要先对SNE有所了解

SNE algorithm：
在高维空间中，我们如何考虑两个点之间的相似性呢，SNE选取的方法是使用一个条件概率来表示，首先选取一个中心点 $x_i$ ，假设以 $x_i$ 为中心存在一个高斯分布，样本集中任意一点 $x_j$ 所在之处的相对概率密度的高低就是该点与 $x_i$ 的相似性，即 $p_{j|i} = \frac{exp(-||x_i-x_j||^2/2\sigma_i^2)}{\Sigma_{k\neq i}exp(-||x_i-x_k||^2/2\sigma_i^2)}$ ，规定 $p_{i|i}=0$ .

当降维之后， $x_i$ 与 $x_j$ 在低维空间内对应的点是 $y_i$ 与 $y_j$ ，在低维空间内两个点之间的相似性用 $q_{j|i}$ 来表示，具体表示为 $q_{j|i} = \frac{exp(-||y_i-y_j||^2)}{\Sigma_{k\neq i}exp(-||y_i-y_k||^2)}$ ，相当于设定了 $\sigma$ 为 $1/\sqrt2$ ，和上面一样，规定 $q_{i|i}=0$

SNE认为如果我是一个比较好的降维方法，那我就应该做到能够在降维之后比较好的保留两个点之间的相似性，也就是应该让 $p_{j|i}$ 和 $q_{j|i}$ 尽可能相近。那么对于整个样本集而言，SNE就是希望能够找个一个好的数据的低维表示，使任意两点之间的相似性保持降维前后尽可能相近，所以SNE设置了如下的 $cost \ function$ ，然后用梯度下降去优化
$C = \Sigma_{i}KL(P_i||Q_i) = \Sigma_i\Sigma_jp_{j|i}log\frac{p_{j|i}}{q_{j|i}}$

$KL$ 表示KL散度，上面式子的意义是，对于每一个 $i$ ，都有一个降维前的相似性分布后降维后的相似性分布，所以我要做的是对每个 $i$ 的前后分布的KL散度求和，然后最小化这个式子。

那么接下来的问题就是 $p_{j|i}$ 里面的 $\sigma_i$ 怎么搞呢？对于不同的 $x_i$ 最适合的 $\sigma_i$ 显然不同，以一维高斯分布为例，大部分周围的点都集中在 $x_i$ 附近的话， $\sigma_i$ 应该比较小，如果分布较分散则相反。SNE就把决定权交给了我们，由使用者指定一个数值 $Perp$ （一般取5-50），SNE通过调整 $\sigma_i$ 的值，使得 $2^{-\Sigma_{j}p_{j|i}log_2p_{j|i}} = Perp$ ，指数上的式子大家熟悉决策树的应该会感觉熟悉，可以用来描述混乱度或者纯度。

确定了损失函数的表示之后，接着使用梯度下降优化，
$\frac{\partial C}{\partial y_i} = 2\Sigma_{j}(p_{j|i}-q_{j|i}-p_{i|j}-q_{i|j})(y_i-y_j)$

t-SNE

由于SNE的 $cost \ function$ 不好优化，并且降维后的点有可能会聚集，为改善这些缺点，t-SNE出现了。那么t-SNE具体做了哪些改进呢？

对称SNE
首先，因为SNE的 $KL$ 散度使用的 $p$ 不对称，即 $p_{i|j} \neq p_{j|i}$ ，对称SNE提出了一种对称的形式，
$C = \Sigma_{i}KL(P_i||Q_i) = \Sigma_i\Sigma_jp_{ij}log\frac{p_{ij}}{q_{ij}}$

$p_{ij} = \frac{exp(-||x_i-x_j||^2/2\sigma^2)}{\Sigma_{k\neq l}exp(-||x_l-x_k||^2/2\sigma^2)}$ ， $q_{ij} = \frac{exp(-||y_i-y_j||^2)}{\Sigma_{k\neq l}exp(-||y_l-y_k||^2)}$ ，同时规定 $p_{ii}$ 和 $q_{ii}$ 为0，在原文中提到，如果 $x_i$ 是离群值，导致所有的 $||x_i-x_j||^2$ 都很大，那么所有的 $p_{ij}$ 就都很小，那么可能会导致 $y_i$ 对 $cost \ function$ 影响很小，导致 $x_i$ 无法被很好的降维，所以最终采取的方式是 $p_{ij}=\frac{p_{i|j}+p_{j|i}}{2n}$ ，这样可以保证 $\Sigma_{j}p_{ij}=\frac{\Sigma_jp_{i|j}+\Sigma_jp_{j|i}}{2n}=\frac{1+\Sigma_jp_{j|i}}{2n}>\frac{1}{2n}$ ，所以保证了 $x_i$ 对于损失函数的贡献是有一席之地的。

在低维空间使用 $t$ 分布(具体是标准柯西分布)代替高斯分布
此时， $q_{ij} = \frac{(1 + ||y_i-y_j||^2)^{-1}}{\Sigma_{k\neq l}(1+||y_l-y_k||^2)^{-1}}$

在这两点的改动下，此时
$\frac{\partial C}{\partial y_i} = 4\Sigma_{j}(p_{ij}-q_{ij})(y_i-y_j)(1+||y_i-y_j||^2)^{-1}$
（具体推导过程可以看原文的附录）

t-SNE伪代码
机器学习降维方法 t-SNE 详解（一）
下篇文章将会具体介绍t-SNE算法的代码实现细节

参考资料：Visualizing Data using t-SNE

机器学习降维方法 t-SNE 详解（一）

相关推荐