T-SNE算法介绍

所需积分/C币:17 2018-09-19 10:12:14 498KB PDF
收藏 收藏 1
举报

t-SNE(t-distributed stochastic neighbor embedding):t分布随机邻域嵌入是用于高维数据的降维算法,是由 Laurens van der Maaten 和 Geoffrey Hinton在08年提出来。此外,t-SNE 是一种非线性降维算法,非常适用于高维数据降到2维或者3维,进行可视化。
是的熵,即: 困惑度可以解释为:一个点附近的有效近邻点个数。SNE对困惑度的调整比较有鲁棒 性,通常选择550之间,给定之后,使用二分搜索的方式寻找合适的; 那么核心问题是如何求解梯度了,目标函数等价于∑∑ 这个式子与 softmax非 常的类似,我们知道 softmax的目标函数是∑-,对应的椭度是(注;这里的 softmax中y表示 label,p表示预估值)。同样我们可以推导SNE的日标函数中的i在j下的 条件概率情况的梯度是 ,同样j在讠下的条件桃率的梯度是 ,最后得到完整的梯度公式如卜: 在初始化中,可以用较小的σ下的高斯分布来进行初始化。为了加速优化过程和避免 陷入局部最优解,梯度中需要使用一个相对较大的动量( momentum)。即参数更新中除了当 前的梯度,还要引入之前的梯度累加的指数衰减项,如下: 这里的表小迭代t次的解,η表小学习速率,a()表小迭代t次的功量 此外,在初始优化的阶段,每次迭代中可以引入一些高斯噪声,之后像模拟退火一样逐 渐减小该噪声,可以用来遊免陷入局部最优解。因此,SNE在选择高斯噪声,以及学习速率 什么时候开始哀减,动量选择等超参数上,需要炮多次优化才叮以。 SNE不足:不对称和拥挤问题>>>>改进:TSNE 5.T-SNE 尽管SNE提供了很好的可视化方法,但是他很难优化,而且存在” crowding problem'(拥 挤问题)。后续中, Hinton等人又提出了tSNE的方法。与SNE不同是 ◆使用对称版的SNE,简化梯度公式; ◆低维空间下,使用t分布替代高斯分布表达两点之间的相似度; tSNE在低维空间下使用更重长尾分布的t分布来避免 crowding问题和伉化间题。在 这里,首先介绍下对称版的SNE,之后介绍 crowding问题,之后再介绍tSNE。 51对称SNE( Symmetric SNE) 优化和的KL散度的一种替换思路是:使用联合概率分布来替换条件概率分布, 即P是高维空间里各个点的联合概率分布,Q是低维空间下的,目标函数为 ∑ 这里的为0,我们将这种SNE称之为 symmetrIc SNE(对称SNE),因为他假设了 对于任意i ,因此概率分布可以改写为: 这神表达方式,使得整体简洁了很多。但是会引入异常值的问题。比如x是异常值, 那么 会很大,对应的所有的j,都会很小(之前是仅在x下很小),导致低维映射 下的v对cost影响很小 思考:对于异常值,你会做什么改进? 为了解决这个问题,我们将联合概率分布定义修正为 ,这保证了 ,使得每个点对于cost都会有一定的贡献。对称SNE的最大优点是梯度计算变 得简单了,如下 52拥挤问题 拥挤问题就是说各个簇聚集在一起,无法区分。比如有一种情况,高维度数据在降维到 10维下,还可以有很好的表达,但是降维到两维后无法得到可信映射,比如降维如10维中 有11个点之间两两等距离的,在二维卜就无法得到可信的映射结果(最多3个点 →因此, Cook et al.2007)提出一种 slight repulsion的方式,在基线概率分布( uniform background)中引入一个较小的混合因子p,这样就永远不会小于2(因为共有 n(n-1)个耦),这样在高维空间中比较远的两个点之间的总是会比大一点(代价小)。这 种称之为 UNI-SNE,效果通常比标准的SNE要好。优化UN-SNE的方法是先计ρ为0,使 用标准的SNE优化,之后用模拟退火算法的时候,再慢慢增加ρ。直接优化 UNI-SNE是 不行的(即一开始p不为0),因为距离较远的两个点基本是一样的(等于基线分布),即使 很大,一些距离变化很难在中产生作用。也就是说优化中刚开始距离较远的两个聚类 点,后续就无法再把他们拉近了。 53tSNE介绍 对称SNE实际上在高维度下另外一和减轻”拥挤问题”的方法:在高维空间下,我们使 用高斯分布将距离转换为概率分布;在低维空间下,我们使用更加偏重长尾分布的方式来将 距离转换为概率分布,使得高维度下中低等的盺离在映射后能够有一个较人的距离。 without outlier distribution with outlier distribution U.45 0.35 norma normal 0.40 t-dist t-dist 0.25 0 0.25 0.20 0.20- 0.15 0.15 0.10 0.10 0.05 0.05 0.00 我们对比一下高斯分布和t分布,t分布受异常值影响更小,拟合结果更为合理,较好 的捕获了数据的整体特征。 使用了t分布之后的q变化,如下 此外,t分布是无限多个高斯分布的叠加,计算上不是指数的,会方便很多。优化的娣 度如下 0.05 probability of distance norma -dist -dist 0.04 0.03 P 0.02 0.01 0.00 20 80 100 distance t-SNE的有效性,也可以从上图中看到:横轴表小距离,纵轴表示相似度。可以看到, 对于较大相似度的点,t分布在低维空间中的距离需要硝小一点;而对于低相似度的点,t分 布在低维空间中的距离需要更远,这恰好满足了我们的需求,即同一簇内的点(距离较近)聚 合的更紧密,不同簇之间的点(距离较远)更加疏远。 总结一下,t-SNE的梯度更新有两大优势: ◆对于不相似的点,用一个较小的距离会产生较大的梯度来让这些点排斥开来 ◆这种排斥又不会无限人(梯度中分母),避免不相似的点距离太 54算法过程 计算代价函数的参数:困惑度 优化参数:设置达代次数,学习速率η,动量 标结果是低维数据表示 开始优化 ◇计算在给定下的条件概率参见上面公式 用 随机初始化 ◇迭代,从到,做如下操作: 计算低维度下的参见上面的公式 计算梯度(参见上面的公式) 更新 +门—+c ◇结束 ●结束 5.5不足之处 ◆主要用于可视化,很难用于其他目的。比如测试集合降维,因为他没有显式的预估部 分,不能在测试集合直接降维;比如降维到10维,因为t分布偏重长尾,1个自由度 的t分布很难保存好局部特征,可能需要设置成更高的自由度; ◆tSNE倾向于保存局部特征,对于本征维数( intrinsic dimensionality本身就很高的数 据集,是不可能完整的映射到2-3维的空间; ◆t-SNE没有唯一最优解,且没有预估部分。如果想要做预估,可以考虑降维之后,再 构建一个回归方程之类的模型去做。但是要注意,t-sne中距离木身是没有意义,都 是概率分布问题 ◆训练太慢。有很多基于树的算法在t-sne上做些改进 OVER!!! 参考链接:htp:/www.doc8comp-0347697065843html

...展开详情
试读 6P T-SNE算法介绍
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    T-SNE算法介绍 17积分/C币 立即下载
    1/6
    T-SNE算法介绍第1页
    T-SNE算法介绍第2页

    试读已结束,剩余4页未读...

    17积分/C币 立即下载 >