本文主要参考wikipedia，介绍t-SNE算法，以及python下的一些实现可视化应用。
目录
1、概述
最开始接触t-SNE是在kaggle的比赛里，看到很多人提到t-SNE，用于降维和可视化。以前在可视化高维数据的时候，一般是降维到2维里可视化，降维的方法通常选择PCA，但是PCA是线性的，效果比较一般。这里介绍的t-SNE（t-distributed stochastic neighbor embedding）是用于降维的一种机器学习算法，是由 Laurens van der Maaten 和 Geoffrey Hinton在08年提出来的，论文参见JMLR-Visualizing High-Dimensional Data Using t-SNE。t-SNE 是一种非线性降维算法，非常适用于高维数据降维到2维或者3维，进行可视化。
2、原理
2.1基本原理
t-SNE主要包括两个步骤：第一、t-SNE构建一个高维对象之间的概率分布，使得相似的对象有更高的概率被选择，而不相似的对象有较低的概率被选择。第二，t-SNE在低维空间里在构建这些点的概率分布，使得这两个概率分布之间尽可能的相似（这里使用KL散度（Kullback–Leibler divergence）来度量两个分布之间的相似性）。
2.2详细过程
具体来说，给定一个N个高维的数据\(x_1, ... , x_N\)（注意N不是维度！）, t-SNE首先是计算概率\(p_{ij}\)，正比于\(x_i\)和\(x_j\)之间的相似度（这种概率是我们自主构建的），公式如下：
\[p_ {j \mid i} = \frac{exp(- \mid \mid x_i -x_j \mid \mid ^ 2 / (2 \sigma^2_i ))}{\sum_{k \neq i} exp(- \mid \mid x_i - x_k \mid \mid ^2 /(2 \sigma^2_i))}\] \[p_{ij} = \frac{p_{j \mid i} p_{i \mid j}}{2N}\]这里看到是用高斯核来构建了概率分布，那么怎么选择高斯核中的\(\sigma_i\)呢？使用二分搜索得到条件概率分布的perplexity（后面再提到）。
t-SNE的目标是学习一个d维度的映射\(y_i, ... , y_N, y_i \in R^d\), 这里定义\(y_i\)和\(y_j\)之间的相似度\(q_{ij}\)如下:
\[q_{ij} = \frac{(1 + \mid \mid y_i - y_j \mid \mid ^2)^{-1}}{\sum_{k \neq l} (1 + \mid \mid y_k - y_l \mid \mid ^2)^{-1}}\]这里使用了学生分布来衡量低维度下点之间的相似度。最后，我们使用KL散度来度量Q和P之间的相似度：
\[C = KL(P \mid \mid) = \sum_{i \neq j} p_{i,j} \log \frac{p_{ij}}{q_{ij}}\]之后使用梯度下降来最小化KL散度，梯度值如下：
\[\frac{dC}{dy_i} = 4 \sum_j (p_{ij} - q_{ij})(y_i - y_j)(1 + \mid \mid y_i - y_j \mid \mid^2)^{-1}\]t-SNE几乎在所有论文中的数据集上效果比 Sammon mapping, Isomap, and Locally Linear Embedding 要好。
2.4理由
- 为什么选择这样的分布 论文中，开始使用了高斯核，之后改用了heavy-tailed t分布，因为这种t分布中 \((1 + \mid \mid y_i - y_j \mid \mid ^2)^{-1}\)与低维空间里\(\mid \mid y_i - y_j\mid \mid\)的二次成反比，能够使得不相似的两个对象被更好的分割
- 高斯核中\(\sigma_i\)的选择 高斯核中\(\sigma_i\)的选择, 不同的i是对应了不同的\(\sigma_i\),取值是用perplexity，当然可以直接看wiki和论文了，这里简单的叙述下perplexity定义为： \(Perp(P_i) = 2^{H(P_i)}\) ,其中，\(H(P_i)\)是\(P_i\)的信息熵，即\(H(P_i) = -\sum_j p_{j \mid i} \log_2 p(j \mid i)\), 可以解释为实际有效近邻数。
3、算法流程
Simple version of t-Distributed Stochastic Neighbor Embedding
- Data: \(X = {x_1, ... , x_n}\)
- 计算cost function的参数： perplexity Perp
- 优化参数: 设置迭代次数T， 学习速率\(\eta\), 动量\(\alpha(t)\)
- 目标结果是低维数据表示 \(Y^T = {y_1, ... , y_n}\)
- 开始优化
- 计算在给定Perp下的条件概率\(p_{j \mid i}\)(参见上面公式)
- 令 \(p_{ij} = \frac{p_{j \mid i} + p_{i \mid j}}{2n}\)
- 用 \(N(0, 10^{-4}I)\) 随机初始化 Y
- 迭代，从 t = 1 到 T， 做如下操作:
- 计算低维度下的 \(q_{ij}\)(参见上面的公式)
- 计算梯度（参见上面的公式）
- 更新 \(Y^{t} = Y^{t-1} + \eta \frac{dC}{dY} + \alpha(t)(Y^{t-1} - Y^{t-2})\)
- 结束
- 结束
注:
完整版笔记参考:tsne完整版
附录：Manifold Learning 可以参考sklearn的文档