1. 从 SNE(Stochastic Neighbor Embedding)讲起
对要进行降维的数据点，先将两点在高维上的欧氏距离转化为条件分布。方法如下：
对于原数据集上的点 \({x_i}\)，以其为中心建立高斯分布，将点 \(x_j\)与\(x_i\)的相似度转化为\(x_j|x_i\)的条件概率\(p_{j|i}\)： \(p_{j|i} = \frac{exp(-||x_i - x_j||^2 / 2 \sigma_i^2)}{\sum_{k \ne i} exp(-||x_i - x_k||^2 / 2 \sigma_i^2)}\)
对于每个数据点上分布方差\(\sigma\)的选取，对于不同的点\(x_i\)不存在一个唯一的值（例如较为密集的点需选取较小的\(\sigma\)，而稀疏的点则需要较大的\(\sigma\)）。分布P的熵随着\(\sigma\)的增大而增大。在用户确定困惑度的情况下，SNE对\(\sigma\)进行二分法搜索，困惑度定义为：\(Perp(P_i) = 2^{H(P_i)}\)其中\(H(P_i)\)是\(P_i\)以2为底的香农熵： \(H(P_i) = - \sum_j p_{j|i} log_{2}p_{j|i}\)。困惑度可被视为对邻居的有效数量的平滑测量。(个人见解：规定上下界，使用二分对sigma进行搜索，用困惑度衡量每次sigma取值后，所获得的高斯与样本的契合程度，逼近最优sigma)
将数据\(x\)映射到低维上后得到\(y\)，并以上式相似的方式定义了在低维空间上的相似性 \(q_{j|i}\):\(q_{j|i} = \frac{exp(-||y_i - y_j||^2)}{\sum_{k \ne i} exp(-||y_i - y_k||^2)}\)（注意，所有标准差项都被设置为\(\frac{1}{\sqrt{2}}\)）
目标就是让低维空间的分布q尽量接近高维上的分布p，其中衡量两个分布相似性使用KL散度： \(C = \sum_i KL(P_i||Q_i) = \sum_i \sum_j p_{j|i} log \frac{p_{j|i}}{q_{j|i}}\) （注意，KL散度的定义可知，低维空间上的不同错影响并不一致，例如，高维空间的相近两点在低维空间上被拉开时所产生的影响较大，而高维中远离的两点在低维中被拉近时所产生的影响较小。所以SNE的损失函数较为关注于局部结构）
SNE中，目标即使两个分布相近，即KL散度最小。使用梯度下降法获得最优模型。其中式子\(C\)对\(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)\)的方向上，根据两点之间过于接近或远离给出斥力或引力， 力的大小与两点之间的距离相关，亦与数据在高维与低维上的失配有关\((p_{j|i} - q_{j|i} +p_{i|j} - q_{i|j} )(y_i - y_j)\) ?????.
SNE有各种各样的问题。。。比如目标函数难以优化（要加许多项，比如精细调整的的高斯噪音，比如大的动量以加快优化），和拥挤问题
2. t-SNE(SNE with Student-t distribution)
为了解决SNE的上述问题，作者提出了t-SNE。t-SNE的目标函数与SNE有两大不同：1. 使用对称的目标函数，2.低维空间中，不再使用高斯分布表达两点的相似度，而使用学生t分布。
2.1 对称的SNE
SNE中的目标函数采用了一个非对称的条件概率密度函数，而高低维上的联合概率密度函数其实也可以作为KL优化的目标分布。于是采用了新的目标函数: \(C = KL(P||Q)=\sum_i \sum_j p_{ij} log\frac{p_{ij}}{q_{ij}}\). 在新的目标函数中，为了使其对称分布，简化运算，定义低维空间上的分布为\(q_{ij} = \frac{exp(-||y_i-y_j||^2)}{\sum_{k \ne l}exp(-||y_k-y_l||^2)}\). 显然可以类似的定义\(p_{ij} = \frac{exp(-||x_i-x_j||^2/2\sigma^2)}{\sum_{k \ne l}exp(-||x_k-x_l||^2/2\sigma^2)}\)，但在\(x_i\)为离群点时，该点对于其他所有点的相似度都极其小，则不能对损失函数产生影响，于是将\(p_{ij} = \frac{p_{j|i}+p_{i|j}}{2n}\)，在其为对称的情况下保持有\(\sum_j p_{ij} \gt \frac{1}{2n}\)，使其所有的点都能对损失函数有所影响。高低维空间上两个对称的概率定义使得目标函数有对称性并且其梯度的表达更加简单，更易计算，\(\frac{\delta C}{\delta y_i} = 4 \sum_j (p_{ij} - q_{ij}) (y_i - y_j)\)
2.2 拥挤问题
在高维上的，我们可以实现多个点的等距分布，比如10维空间上可以分布11个相互等距的点，但在二维空间上无法表征。因此，如果数据点在十维流形上的i周围的区域中近似均匀分布，并且我们尝试对二维图中从i到其他数据点的距离建模，将得到以下“拥挤问题”：与可用于容纳相邻数据点的区域相比，可用于容纳远距离数据点的二维图的面积将不够大。因此，如果我们在低维上精确的表征相近的局部特征时，绝大多数与该点有些距离的点将被放置得太远。SNE中，对于较远点，每个点都会对它产生一个极小的引力，但多个点的引力累积，将会使许多点拥挤在图的中心，这会让不同类的点群之间的间隙减小，失去了全局特征。（拥挤问题在许多保持局部结构的算法中都会遇到）
Cook et al.提出了一种称为UNI-SNE的方法来缓解拥挤问题。即在所有力中加入一些斥力。虽然UNI-SNE经常获得比SNE好的效果，但其损失函数的优化是较难的。且会产生其他问题。
2.3 长尾可补偿不匹配的维度（？）
高维中，SNE使用高斯分布来描述点之间的相似性，低维中，本文将采用比高斯尾巴更重的分布来描述点的相似性。这就可以使高维中的一般距离点可以在低维中有较远的距离，因此可缓解多点累积带来的较大的引力。
t-SNE中，本文采取了自由度为1的t分布（柯西分布），作为低维空间上的长尾分布（柯西分布具有长尾，在尾部趋于0的速度更慢，既能缓解拥挤问题，又更利于优化），得到新的联合概率密度 \(q_{ij} = \frac{(1+||y_i - y_j||^2)^{-1}}{\sum_{k \ne l}(1 + ||y_k - y_l||^2)^{-1}}\)。于使用1自由度的t分布，是由于\((1-||y_i - y_j||^2)^{-1}\)非常接近低维上两点距离\(||y_i -y_j||\)的平方反比，这就使得相距较远点的联合概率分布基本不随低维图的尺度变化而变化。同时也意味着，相距较远的点群之间交互方式与两点交互的方式相同，所以除了最优的尺度，所有的优化都以相同的方式进行。从理论上，选择学生t分布，是由于无限个高斯形成的混合，所以与高斯较为类似。t分布的另一个好处就是计算较为简单，不需计算指数。将新的\(q_{ij}\)带入KL 散度并计算得到新的梯度为: \(\frac{\delta C}{\delta y_i} = 4 \sum_j (p_{ij} - q_{ij}) ( y_i - y_j)(1+||y_i-y_j||^2)^{-1}\)
然后对SNE，UNI-SNE与t-SNE的在高低维上的梯度进行图像化，得到图。
通过图可看到t-SNE的两点优越性：
-
t-SNE对于在高维中远但低维中近的点产生了强斥力，SNE也产生了斥力，但相比于其他点的吸引力还是过小（图中引力最大时为19，而最大斥力为1）。UNI-SNE虽能产生较大斥力，但仅在低维两点之间距离够大时其斥力才较大。
-
虽然t-SNE产生了斥力，但斥力并未向上走向无穷。这点与UNI-SNE较为不同，其中两不相似点之间的斥力与在低维上两者间的距离成比例，因此会使两个点相距过远。
综合来说，t-SNE强调(1)通过大的成对距离对不相似的数据点进行建模，(2)通过小的成对距离对小的数据点进行建模。并且，t-SNE在低维中引入了长距离力，使两个相似但在优化初期被分离的群可以被拉回。由于这些性质，t-SNE损失函数的优化比SNE与UNI-SNE来说更为简单。