机器学习基础---降维方法---T分布随机近邻嵌入(TSNE)推导

T-SNE（T-Stochastic Neighbor Embedding）

核心思想：

• 对无监督聚类问题：

  • PCA目的是在样本空间内找到子空间，以变换矩阵W对样本矩阵$X$实现原空间到子空间的映射，属于线性聚类方法；其方法核心在于最小化投影后方差
  • LPP方法，本身结合了非线性流形学习方法LE（拉普拉斯特征映射）的思想，引入线性变换的假设，虽然从本质上说属于线性方法，但有效地保留原始高维数据内部的非线性结构，对非线性流形数据聚类也有较好的效果；其核心在于使投影前后距离近的点相似关系保持
  • 上述两种方法中，样本相似性都是通过欧氏空间中的距离表示的，欧式距离越近相似度越高

• 不同于上述方法中以欧氏距离为衡量标准，SNE方法将欧式距离转化成条件概率来表示相似性：

  • 即对样本点$x_i$，$x_j$，不使用两者间距离作为相似度衡量，而是基于距离计算$x_i$选择$x_j$作为近邻的概率$p_{j|i}$

    同样，对降维后的$y_i$，$y_j$，同样使用条件概率$q_{j|i}$表示$y_i$选择$y_j$作为近邻的概率

  • 考虑点i与其他所有点之间的关系，则构成条件概率分布$P_i$与$Q_i$

    SNE方法的核心思路即为高维下的条件概率分布$Q_i$且应该与$P_i$一致

    使用K-L散度计算两个分布之间的相似程度

  • 使用梯度下降算法进行训练

• SNE方法的问题：

  • 概率的不对称性：$P_{j|i}\ne P_{i|j}$导致梯度计算较为复杂
  • K-L散度的不对称性，具体见下文K-L散度部分，导致SNE能保留数据中的局部特征，对全局特征刻画不足
  • 存在拥挤问题（具体见下文）

• 改进方案T-SNE

  • 改进点：
    • 使用联合概率分布来替换条件概率分布，保证对于任意i，有$p_{ij}=p_{ji},q_{ij}=q_{ji}$
    • 在低维目的空间，使用t-分布替代高斯分布

相关概念

• 高斯分布构建条件概率

  • 构建样本点$x_i$的条件概率分布时，可以考虑高斯分布

  • 对高维空间中的$x_i$，$x_j$，定义$x_i$选择$x_j$作为近邻的概率$p_{j|i}$：
    $$p_{j|i}=\frac{exp(\frac{-||x_i-x_j|{|}^2}{2{\sigma }_i^2})}{{\sum }_{k\ne i}exp(\frac{-||x_i-x_k|{|}^2}{2{\sigma }_i^2}))}$$
    对高维空间中的$y_i$，$y_j$，定义$y_i$选择$y_j$作为近邻的概率$q_{j|i}$，指定方差$\sigma =\frac{1}{\sqrt{2}}$：
    $$q_{j|i}=\frac{exp(-||x_i-x_j|{|}^2)}{{\sum }_{k\ne i}exp(-||x_i-x_k|{|}^2))}$$

  • $\sigma$选取：

    • 可计算分布P的熵：$H(P_i)=-{\sum }_j{P}_{j|i}lo{g}_2{P}_{j|i}$
    • 定义困惑度：$Prep(P_i)=2^{H(P_i)}$，对不同样本点有不同的困惑度
      • 困惑度随$H(P_i)$增大而增大
      • 当样本$x_i$与其他m个有效样本点距离相同时，$P_{j|i}=\frac{1}{m}$，$H(P_i)=lo{g}_{2}m$，$Prep(P_i)=m$
      • 上式说明当维度足够大时，困惑度近似于附近的有效近邻点个数
    • 通常通过指定困惑度（近邻数量）的方法，对$P_{j|i}$中的${\sigma }_i$进行求解，同时由于$Prep(P_i)随\sigma$增大而增大，可以使用二分方法搜索${\sigma }_i$

• K-L散度

  • KL 散度是一个用来衡量两个概率分布的相似性的度量指标

  • 引入 信息熵：表示一个概率分布需要的平均信息量
    $$H=-\sum _{i=1}^{N}p(x_i)log(p(x_i))$$

  • 定义K-L散度：
    $$D_{KL(p||q)}=\sum _{i=1}^{N}p(x_i)(log(p(x_i)-log(q(x_i)))=\sum _{i=1}^{N}p(x_i)log\frac{p(x_i)}{q(x_i)}$$
    K-L散度值越小，分布p与分布q之间越接近

• 拥挤问题:

  • 在m维球中随机分布的样本点与指定样本点$x_i$的距离分布情况如下图所示：

• 即，随着样本维度增大，随机样本点与$x_i$点的距离分布极不平衡，其更倾向于分布在m维球的球面区域

• 在降维过程中，需要尽可能地将样本分布保留，会将高维空间下球面上的点集中到低维空间的球面，但低维下球面积远远小于高维，因此出现“拥挤”

• “拥挤”问题会导致高维数据在降维到低维后过于集中，无法得到可信映射

• t分布构建条件概率

  • 以t分布将距离转换为条件概率公式为：
    $$q_{j|i}=\frac{(1+||y_i-y_j|{|}^2{)}^{-1}}{{\sum }_{k\ne l}(1+||y_k-y_l|{|}^2{)}^{-1}}$$

  • t-分布与高斯分布对比：

  

  就上图（距离-概率分布）而言，对$p_{ij}=q_{ij}$，在相似度较高的情况下（上虚线）t-分布的距离小于高斯分布；相似度较高的情况下（下虚线）t-分布的距离大于高斯分布。

  t分布可以有效地将高维空间集中在球面附近的点，在低维空间中一定程度上分开。同时，也满足需求：同类样本尽可能集中，不同类样本尽可能分开。

方法推导

• SNE方法（Stochastic Neighbor Embedding 随机近邻嵌入）：

  • 采用高斯分布构建原空间与目标空间下的条件概率$P_i,Q_i$
    $$p_{ij}=p_{j|i}=\frac{exp(\frac{-||x_i-x_j|{|}^2}{2{\sigma }_i^2})}{{\sum }_{k\ne i}exp(\frac{-||x_i-x_k|{|}^2}{2{\sigma }_i^2}))}$$

    $$q_{ij}=q_{j|i}=\frac{exp(-||y_i-y_j|{|}^2)}{{\sum }_{k\ne i}exp(-||y_i-y_k|{|}^2))}$$

  • 使用所有样本点降维前后条件概率K-L散度之和作为优化目标函数：
    $$C=\sum _{i=1}^N{D}_{KL(P_i||Q_i)}=\sum _{i=1}^N\sum _{j=1}^N{q}_{ij}log(\frac{p_{ij}}{q_{ij}})$$

  • 优化目标为寻找到能使函数C取最小值的低维样本集$Y=[y_1,y_2,...,y_n]$

  • 考虑通过动量梯度下降法对Y进行迭代更新：
    $$y_i^t=y_i^{t-1}+\eta \frac{\partial C}{\partial y_i}+\alpha (t)(y_i^{t-1}-y_i^{t-2})$$

  • 求导过程：

    • 定义中间变量：

      • $$q_{ij}=\frac{w_{ij}}{{\sum }_k{w}_{i}k}$$

      • $w_{ij}$：$y_i,y_j$之间相似度
        $$w_{ij}=exp(-||y_i-y_j|{|}^2)=exp(-f_{ij})$$

      • $f_{ij}$：$y_i,y_j$之间距离度量
        $$f_{ij}=||y_i-y_j|{|}^2=d_{ij}^2$$

      • $d_{ij}$：$y_i,y_j$之间欧氏距离
        $$d_{ij}=||y_i-y_j||$$

    • 通过求导链式法则,可得：
      $$\frac{\partial C}{\partial y_h}=\sum _{ij}\frac{\partial C}{\partial q_{ij}}\sum _{kl}\frac{\partial q_{ij}}{\partial w_{kl}}\sum _{mn}\frac{\partial w_{kl}}{\partial f_{mn}}\sum _{pq}\frac{\partial f_{mn}}{\partial d_{pq}}\frac{\partial d_{pq}}{\partial y_h}$$
      由于$w,f,d$交叉项为0，除非$p=m=k$且$q=n=l$，故：
      $$\frac{\partial C}{\partial y_h}=\sum _{ij}\frac{\partial C}{\partial q_{ij}}\sum _{kl}\frac{\partial q_{ij}}{\partial w_{kl}}\frac{\partial w_{kl}}{\partial f_{kl}}\frac{\partial f_{kl}}{\partial d_{kl}}\frac{\partial d_{kl}}{\partial y_h}$$
      再，仅当$k=i$时，$\frac{\partial C}{\partial q_{ij}}\ne 0$，故：
      $$\frac{\partial C}{\partial y_h}=\sum _{ij}\frac{\partial C}{\partial q_{ij}}\sum _l\frac{\partial q_{ij}}{\partial w_{il}}\frac{\partial w_{il}}{\partial f_{il}}\frac{\partial f_{il}}{\partial d_{il}}\frac{\partial d_{il}}{\partial y_h}$$
      对$\frac{\partial d_{il}}{\partial y_h}$，仅当$i=h或l=h$时非零，故：
      $$\frac{\partial C}{\partial y_h}=\sum _{ij}\frac{\partial C}{\partial q_{ij}}\frac{\partial q_{ij}}{\partial w_{ih}}\frac{\partial w_{ih}}{\partial f_{ih}}\frac{\partial f_{ih}}{\partial d_{ih}}\frac{\partial d_{ih}}{\partial y_h}+\sum _{jl}\frac{\partial C}{\partial q_{hj}}\frac{\partial q_{hj}}{\partial w_{hl}}\frac{\partial w_{hl}}{\partial f_{hl}}\frac{\partial f_{hl}}{\partial d_{hl}}\frac{\partial d_{hl}}{\partial y_h}$$
      在此进行下标替换（由于前后两式独立计算，所以中间变量下标可以进行任意计算）:

      前式中进行替换：j->l ; i->j；后式进行替换：j->l ; l->j；再将两式中h替换为i，有：
      $$\frac{\partial C}{\partial y_i}=\sum _{jl}\frac{\partial C}{\partial q_{jl}}\frac{\partial q_{jl}}{\partial w_{ji}}\frac{\partial w_{ji}}{\partial f_{ji}}\frac{\partial f_{ji}}{\partial d_{ji}}\frac{\partial d_{ji}}{\partial y_i}+\sum _{jl}\frac{\partial C}{\partial q_{il}}\frac{\partial q_{il}}{\partial w_{il}}\frac{\partial w_{ij}}{\partial f_{ij}}\frac{\partial f_{ij}}{\partial d_{ij}}\frac{\partial d_{ij}}{\partial y_i}$$
      d与f时对称的，有$d_{ij}=d_{ji},f_{ij}=f_{ji}$，故：
      $$\frac{\partial C}{\partial y_i}=\sum _j(\sum _l\frac{\partial C}{\partial q_{jl}}\frac{\partial q_{jl}}{\partial w_{ji}}\frac{\partial w_{ji}}{\partial f_{ji}}+\sum _l\frac{\partial C}{\partial q_{il}}\frac{\partial q_{il}}{\partial w_{ij}}\frac{\partial w_{ij}}{\partial f_{ij}})\frac{\partial f_{ij}}{\partial d_{ij}}\frac{\partial d_{ij}}{\partial y_i}$$
      令：
      $$\frac{\partial C}{\partial y_i}=\sum _j(k_{ji}+k_{ij})\frac{\partial f_{ij}}{\partial d_{ij}}\frac{\partial d_{ij}}{\partial y_i}$$

      $$k_{ij}=\sum _l\left[\frac{\partial C}{\partial q_{il}}\frac{\partial q_{il}}{\partial w_{ij}}\right]\frac{\partial w_{ij}}{\partial f_{ij}}$$

      接下来求解$k_{ij}，\frac{\partial q_{il}}{\partial w_{il}}\frac{\partial w_{ij}}{\partial f_{ij}}$：

      由于f,d表达式已知，直接求导得：
      $$\frac{\partial f_{ij}}{\partial d_{ij}}\frac{\partial d_{ij}}{\partial y_i}=2(y_i-y_j)$$
      求$k_{ij}$过程：

      • 已知
        $$q_{ij}=\frac{w_{ij}}{{\sum }_k{w}_{ik}}=\frac{w_{ij}}{S_i}$$

        $$\frac{\partial q_{ij}}{\partial w_{ij}}=\frac{S_i-w_{ij}}{S_i^2}=\frac{1}{S_i}-\frac{w_{ij}}{S_i^2}=\frac{1}{S_i}-\frac{q_{ij}}{S_i}$$

        $$\frac{\partial q_{ik}}{\partial w_{ij}}=-\frac{w_{ik}}{S_i^2}=-\frac{q_{ik}}{S_i}(l\ne j)$$

        带入$k_{ij}$（i,j固定）得：
        k i j = ∑ l [ ∂ C ∂ q i l ∂ q i l ∂ w i j ] ∂ w i j ∂ f i j = [ ∂ C ∂ q i j ∂ q i j ∂ w i j + ∑ l ≠ j ∂ C ∂ q i l ∂ q i l ∂ w i j ] ∂ w i j ∂ f i j = [ ∂ C ∂ q i j ( 1 S i − q i j S i ) − ∑ l ≠ j ∂ C ∂ q i l q i k S i ] ∂ w i j ∂ f i j = 1 S i [ ∂ C ∂ q i j − ∑ l ∂ C ∂ q i l q i l ] ∂ w i j ∂ f i j

        $$\begin{aligned} k_{ij}&=\sum_{l}\left[\frac{\partial C}{\partial q_{il}}\frac{\partial q_{il}}{\partial w_{ij}}\right]\frac{\partial w_{ij}}{\partial f_{ij}}\\ &=\left[\frac{\partial C}{\partial q_{ij}}\frac{\partial q_{ij}}{\partial w_{ij}}+\sum_{l\neq j}\frac{\partial C}{\partial q_{il}}\frac{\partial q_{il}}{\partial w_{ij}}\right]\frac{\partial w_{ij}}{\partial f_{ij}}\\ &=\left[ \frac{\partial C}{\partial q_{ij}}(\frac1{S_i}-\frac{q_{ij}}{S_i}) - \sum_{l\neq j}\frac{\partial C}{\partial q_{il}}\frac{q_{ik}}{S_i} \right]\frac{\partial w_{ij}}{\partial f_{ij}}\\ &=\frac1{S_i}\left[ \frac{\partial C}{\partial q_{ij}}- \sum_{l}\frac{\partial C}{\partial q_{il}}q_{il}\right]\frac{\partial w_{ij}}{\partial f_{ij}} \end{aligned}$$ kij​​=l∑​[∂qil​∂C​∂wij​∂qil​​]∂fij​∂wij​​=⎣⎡​∂qij​∂C​∂wij​∂qij​​+l​=j∑​∂qil​∂C​∂wij​∂qil​​⎦⎤​∂fij​∂wij​​=⎣⎡​∂qij​∂C​(Si​1​−Si​qij​​)−l​=j∑​∂qil​∂C​Si​qik​​⎦⎤​∂fij​∂wij​​=Si​1​[∂qij​∂C​−l∑​∂qil​∂C​qil​]∂fij​∂wij​​​

      • 求$\frac{\partial C}{\partial q_{ij}}$
        $$\begin{gathered} C=\sum _{i=1}^N{D}_{KL(P_i||Q_i)}=\sum _{i=1}^N\sum _{j=1}^N{q}_{ij}log(\frac{p_{ij}}{q_{ij}}) \\ \frac{\partial C}{\partial q_{ij}}=-\frac{p_{ij}}{q_{ij}} \end{gathered}$$

      • 求$\frac{\partial w_{ij}}{\partial f_{ij}}$
        $$\begin{gathered} f_{ij}=||y_i-y_j|{|}^2=d_{ij}^2 \\ \frac{\partial w_{ij}}{\partial f_{ij}}=-w_{ij} \end{gathered}$$

      • k i j = 1 S i ( − p i j q i j − ∑ l ( − p i l q i l ) q i l ) ( − w i j ) = q i j ( p i j q i j − 1 ) = q i j − p i j

        $$\begin{aligned} k_{ij} &=\frac1{S_i}(-\frac{p_{ij}}{q_{ij}}-\sum_l(-\frac{p_{il}}{q_{il}})q_{il})(-w_{ij})\\ &=q_{ij}(\frac{p_{ij}}{q_{ij}}-1)\\ &=q_{ij}-p_{ij} \end{aligned}$$ kij​​=Si​1​(−qij​pij​​−l∑​(−qil​pil​​)qil​)(−wij​)=qij​(qij​pij​​−1)=qij​−pij​​

    • 综上所述，得：
      ∂ C ∂ y i = ∑ j ( k j i + k i j ) ∂ f i j ∂ d i j ∂ d i j ∂ y i = 2 ∑ j ( p i j − q i j + p j i − q j i ) ( y i − y j )

      $$\begin{aligned} \frac{\partial C}{\partial y_i}&=\sum_j(k_{ji}+k_{ij})\frac{\partial f_{ij}}{\partial d_{ij}}\frac{\partial d_{ij}}{\partial y_i}\\ &=2\sum_j(p_{ij}-q_{ij}+p_{ji}-q_{ji})(y_i-y_j) \end{aligned}$$ ∂yi​∂C​​=j∑​(kji​+kij​)∂dij​∂fij​​∂yi​∂dij​​=2j∑​(pij​−qij​+pji​−qji​)(yi​−yj​)​

• T-SNE方法

  • T-SNE方法与SNE方法的不同之处在于分布概率的计算：

    • 低维下采用t分布

    $$p_{j|i}=\frac{exp(\frac{-||x_i-x_j|{|}^2}{2{\sigma }_i^2})}{{\sum }_{k\ne i}exp(\frac{-||x_i-x_k|{|}^2}{2{\sigma }_i^2}))}$$

    $$q_{j|i}=\frac{(1+||y_i-y_j|{|}^2{)}^{-1}}{{\sum }_{k\ne l}(1+||y_k-y_l|{|}^2{)}^{-1}}$$

    • 采用对称概率，使用联合概率分布来替换条件概率分布

    $$\begin{gathered} p_{ij}=p_{ji}=\frac{p_{ij}+p_{ji}}{2} \\ {q}_{ij}=q_{ji}=\frac{q_{ij}+q_{ji}}{2} \end{gathered}$$

  • 目标依然是：
    $$C=\sum _{i=1}^N{D}_{KL(P_i||Q_i)}=\sum _{i=1}^N\sum _{j=1}^N{q}_{ij}log(\frac{p_{ij}}{q_{ij}})$$

  • 对于$y_i$的求导过程与SNE过程类似，最终求得：
    ∂ C ∂ y i = 4 ∑ j ( p i j − q i j ) ( 1 + ∣ ∣ y i − y j ∣ ∣ 2 ) − 1

    $$\begin{aligned} \frac{\partial C}{\partial y_i}=4\sum_j(p_{ij}-q_{ij})(1+||y_i-y_j||^2)^{-1} \end{aligned}$$ ∂yi​∂C​=4j∑​(pij​−qij​)(1+∣∣yi​−yj​∣∣2)−1​

  • 更新公式：
    $$y_i^t=y_i^{t-1}+\eta \frac{\partial C}{\partial y_i}+\alpha (t)(y_i^{t-1}-y_i^{t-2})$$

方法流程

• T-SNE方法：
  • 输入样本矩阵$X=[x_1,x_2,...x_n]$
  • 指定困惑度Prep，迭代次数T， 学习速率$\eta$, 动量$\alpha (t)$
  • 使用正态分布随机化目标矩阵$Y=[y_1,y_2,...,y_n]$
  • 计算Prep下的原始条件概率P
  • 迭代，$t=1,2,...,T$
    • 计算低维分布条件概率Q
    • 计算目标C与梯度$\frac{\partial C}{\partial y_i}$
    • 更新：$Y^t=Y{i}^{t-1}+\eta \frac{\partial C}{\partial Y}+\alpha (t)(Y^{t-1}-Y^{t-2})$
  • 结束，输出$Y^T$

参考资料

【1】[从SNE到t-SNE再到LargeVis][http://bindog.github.io/blog/2016/06/04/from-sne-to-tsne-to-largevis/]

【2】[机器学习：Kullback-Leibler Divergence （KL 散度）][https://blog.csdn.net/matrix_space/article/details/80550561]

【3】[SNE与t-SNE梯度的推导][https://zhuanlan.zhihu.com/p/384698107]

【4】[t-SNE原理与推导][https://blog.csdn.net/scott198510/article/details/76099700]