降维算法 - SNE

SNE是一种数据降维算法，最早出现在2002年，它改变了MDS和ISOMAP中基于距离不变的思想，将高维映射到低维的同时，尽量保证相互之间的分布概率不变，SNE将高维和低维中的样本分布都看作高斯分布，而Tsne将低维中的坐标当做T分布，这样做的好处是为了让距离大的簇之间距离拉大，从而解决了拥挤问题。

SNE

• 高维数据用 $x$ 表示，$x_i$表示第 $i$ 个样本，低维数据用 $y$ 表示，则高维中的分布概率矩阵 $P$ 定义如下：

$$
p _ { j |i } = \frac { exp ( - || x _ { i } - x _ { j }|| ^ { 2 } ( 2 \sigma _ { i } ^ { 2 } ) } { \sum _ {
k \neq i } ( - || x _ { i } - x _ { k } ^ { 2 } || ^ { 2 } ( 2 \sigma _ { i } ^ { 2 } )}
$$

• $P(i,j)$表示第$i$个样本分布在样本$j$周围的概率。$\sigma$是依据最大熵原理来决定，以每个样本点作为中心的$\sigma$都需要使得最后分布的熵较小，通常以$log(k)$为上限，$k$为你所决定的邻域点的个数

• 低维中的分布概率矩阵计算如下：
  $$
  q_{j \mid i}=\frac{\exp \left(-\left|y_{i}-y_{j}\right|^{2}\right)}{\sum_{k \neq i} \exp \left(-\left|y_{i}-y_{k}\right|^{2}\right)}
  $$

• 这里我们把低维中的分布看作是均衡的，每个delta都是0.5，由此可以基本判断最后降维之后生成的分布也是一个相对均匀的分布。

• 随机给定一个初始化的Y，进行优化，使得Y的分布矩阵逼近X的分布矩阵。我们给定目的函数，用KL散度来定义两个不同分布之间的差距：

$$
C=\sum_{i} K L\left(P_{i} | Q_{i}\right)=\sum_{i} \sum_{j} p_{j \mid i} \log \frac{p_{j \mid i}}{q_{j \mid i}}
$$

• 则可以计算梯度为：

$$
\frac{\delta C}{\delta y_{i}}=2 \sum_{j}\left(p_{j \mid i}-q_{j \mid i}+p_{i \mid j}-q_{i \mid j}\right)\left(y_{i}-y_{j}\right)
$$

• 每次梯度下降的步长可设定固定或者自适应、随机等，也可以加上一个动量的梯度，初始值一般设为1e-4的随机正态分布。

$$
\mathcal{Y}^{{(t)}=\mathcal{Y}}{(t-1)}+\eta \frac{\delta C}{\delta \mathcal{Y}}+\alpha(t)\left(\gamma^{{(t-1)}-\mathcal{Y}}{(t-2)}\right)
$$

参考资料

• https://blog.csdn.net/zhangweiguo_717/article/details/70188517

文章链接：
https://www.zywvvd.com/notes/study/machine-learning/sne-alg/sne-alg/