特征抽取 t-SNE | 彩潭有鲤的札记

type

status

date

slug

summary

原理

SNE

SNE是先将欧几里得距离转换为条件概率来表达点与点之间的相似度。

给定一个个高维的数据，t-SNE首先是计算概率，正比于数据点与之间的相似度（具体的概率密度函数由算法设计人员自主构建），常用的pdf有高维欧几里得距离转换为表示相似性的条件概率，即：

这里的有一个参数是，对于不同的点取值不一样，通常取值为以数据点为中心的高斯均方差。此外设置，因为关注的是两两之间的相似度。

那对于低维度下的，可以指定高斯分布的均方差为，因此它们之间的相似度如下:

如果降维的效果比较好，局部特征保留完整，那么。因此优化两个概率分布之间的距离即KL散度(Kullback-Leibler divergences)，目标函数如下：

这里的表示了给定点下，其他所有数据点的条件概率分布。需要注意的是KL散度具有不对称性，在低维映射中不同的距离对应的惩罚权重是不同的，具体来说：

当也就是说是邻域点的概率很高，表现为两点距离很近，如果映射到低维空间的也即是映射后的距离很远（属于邻域的概率很低），即用距离较远的两个点来表达距离较近的两个点会产生更大的cost：

与之相反，用较近的两个点 (属于邻域的概率很高) 来表达较远的两个点产生的 cost相对较小 (注意: 类似于回归容易受异常值影响，但效果相反)。因此，SNE会倾向于保留数据中的局部特征。

推导SNE

不同的点具有不同的，的嫡(entropy)会随着的增加而增加。SNE使用困惑度(perplexity)的概念，用二分搜索的方式来寻找一个最佳的。其中困惑度指: 这里的是的熵: 困惑度可以解释为一个点附近的有效近邻点个数。SNE对困惑度的调整比较有鲁棒性，通常选择5-50之间，给定之后，使用二分搜索的方式寻找合适的。

那么核心问题是如何求解梯度了，目标函数等价于这个式子与非常的类似，的目标函数是，对应的梯度是 (注: 这里的中表示label，表示预估值)。

同样可以推导SNE的目标函数中的在下的条件概率情况的梯度是，同样在下的条件概率的梯度是，最后得到完整的梯度公式如下:

在初始化中，可以用较小的下的高斯分布来进行初始化。为了加速优化过程和避免陷入局部最优解，梯度中需要使用一个相对较大的动量(momentum)。即参数更新中除了当前的梯度，还要引入之前的梯度男加的指数衰减项，如下: 这里的表示迭代次的解，表示学习速率，表示迭代次的动量。此外，在初始优化的阶段，每次迭代中可以引入一些高斯噪声，之后像模拟退火一样逐渐减小该噪声，可以用来避免陷入局部最优解。因此，SNE在选择高斯噪声，以及学习速率，什么时候开始衰减，动量选择等等超参数上，需要跑多次优化才可以。

Symmetric SNE(对称SNE)

尽管SNE提供了很好的可视化方法，但是很难优化，而且存在”crowding problem”(拥挤问题)。后续中，Hinton等人又提出了t-SNE的方法。与SNE不同，主要如下:

使用对称版的SNE，简化梯度公式

低维空间下，使用分布替代高斯分布表达两点之间的相似度

t-SNE在低维空间下使用更重长尾分布的t分布来避免crowding问题和优化问题。

优化和的散度的一种替换思路是，使用联合概率分布来替换条件概率分布，即是高维空间里各个点的联合概率分布，是低维空间下的，目标函数为：这里的与为0，将这种称之为（对称），因为他假设了对于任意 , ，因此概率分布可以改写为：这种表达方式，使得整体简洁了很多，但会引入异常值的问题。比如是异常值，那么会很大，对应的所有的都会很小(之前是仅在下很小)，导致低维映射下的对cos t 影响很小。

为了解决这个问题，将联合概率分布定义修正为: 这避免了异常值的过大影响, 使得每个点对于cost都会有一定的贡献。对称SNE的最大优点是梯度计算变得简单了:

实验中，发现对称SNE能够产生和SNE一样好的结果，有时甚至略好一点。

Crowding问题

拥挤问题就是说各个簇聚集在一起，无法区分。比如有一种情况，高维度数据在降维到10维下，可以有很好的表达，但是降维到两维后无法得到可信映射，比如降维如10维中有11个点之间两两等距离的，在二维下就无法得到可信的映射结果(最多3个点)。进一步的说明，假设一个以数据点为中心，半径为的维球(三维空间就是球)，其体积是按增长的，假设数据点是在维球中均匀分布的，看看其他数据点与的距离随维度增大而产生的变化。

从上图可以看到，随着维度的增大，大部分数据点都聚集在维球的表面附近，与点的距离分布极不均衡。如果直接将这种距离关系保留到低维，就会出现拥挤问题。

Cook et al.(2007) 提出一种slight repulsion的方式，在基线概率分布(uniform background)中引入一个较小的混合因子，这样就永远不会小于 (因为一共了个pairs)，这样在高维空间中比较远的两个点之间的总是会比大一点。这种称之为UNI-SNE，效果通常比标准的SNE要好。优化UNI-SNE的方法是先让为 0 ，使用标准的SNE优化，之后用模拟退火的方法的时候，再慢慢增 . 直接优化UNI-SNE是不行的(即一开始不为 0 )，因为距离较远的两个点基本是一样的 (等于基线分布), 即使很大，一些距离变化很难在中产生作用。也就是说优化中刚开始距离较远的两个聚类点，后续就无法再把他们拉近了。

t-SNE

对称SNE实际上在高维度下另外一种减轻”拥挤问题”的方法：在高维空间下，使用高斯分布将距离转换为概率分布，在低维空间下，使用更加偏重长尾分布的方式来将距离转换为概率分布，使得高维度下中低等的距离在映射后能够有一个较大的距离。

对比一下高斯分布和分布(如上图，code见probability/distribution.md), 分布受异常值影响更小，拟合结果更为合理，较好的捕获了数据的整体特征。

使用了分布之后的变化，如下: 此外，分布是无限多个高斯分布的鴯加，计算上不是指数的，会方便很多。优化的梯度如下:

t-SNE的有效性，也可以从上图中看到：横轴表示距离，纵轴表示相似度, 可以看到，对于较大相似度的点，t分布在低维空间中的距离需要稍小一点；而对于低相似度的点，t分布在低维空间中的距离需要更远。这恰好满足了我们的需求，即同一簇内的点(距离较近)聚合的更紧密，不同簇之间的点(距离较远)更加疏远。

总结一下，t-SNE的梯度更新有两大优势：

对于不相似的点，用一个较小的距离会产生较大的梯度来让这些点排斥开来

这种排斥又不会无限大(梯度中分母)，避免不相似的点距离太远

算法详细过程如下:

Data:

计算cost function的参数：困惑度Perp

优化参数: 设置迭代次数 , 学习速率 , 动量

目标结果是低维数据表示

开始优化

计算在给定Perp下的条件概率参见上面公式

令

用随机初始化

迭代，从到, 做如下操作:

计算低维度下的（参见上面的公式）

计算梯度 (参见上面的公式)

更新

结束

结束

优化过程中可以尝试的两个trick:

提前压缩(early compression)：开始初始化的时候，各个点要离得近一点。这样小的距离，方便各个聚类中心的移动。可以通过引入L2正则项(距离的平方和)来实现。

提前夸大(early exaggeration)：在开始优化阶段，乘以一个大于1的数进行扩大，来避免因为太小导致优化太慢的问题。比如前50次迭代，乘以4

主要不足有四个:

主要用于可视化，很难用于其他目的。比如测试集合降维，因为他没有显式的预估部分，不能在测试集合直接降维；比如降维到10维，因为分布偏重长尾，1个自由度的分布很难保存好局部特征，可能需要设置成更高的自由度。

t-SNE倾向于保存局部特征，对于本征维数(intrinsic dimensionality)本身就很高的数据集，不可能完整的映射到2-3维的空间

t-SNE没有唯一最优解，且没有预估部分。如果想要做预估，可以考虑降维之后，再构建一个回归方程之类的模型去做。但是要注意，t-SNE中距离本身是没有意义，都是概率分布问题。

训练太慢，有很多基于树的算法在t-SNE上做一些改进

代码

在优化t-SNE方面，有很多技巧。下面5个参数会影响t-SNE的可视化效果：

perplexity 混乱度。混乱度越高，t-SNE将考虑越多的邻近点，更关注全局。因此，对于大数据应该使用较高混乱度，较高混乱度也可以帮助t-SNE拜托噪声的影响。相对而言，该参数对可视化效果影响不大。

early exaggeration factor 该值表示你期望的簇间距大小，如果太大的话（大于实际簇的间距），将导致目标函数无法收敛。相对而言，该参数对可视化效果影响较小，默认就行。

learning rate 学习率。

maximum number of iterations 迭代次数。迭代次数不能太低，建议1000以上。

angle (not used in exact method) 角度。相对而言，该参数对效果影响不大。