# SNE 算法

在基本的 SNE 算法中，采用一个条件概率$p_{j|i}$ 衡量$x_i,\ x_j$ 两数据点的相似性，其表达式为

$$p_{j|i} = \frac{\exp(-\|x_i-x_j\|^2/2\sigma_i^2)}{\sum_{k\neq i}\exp(-\|x_i-x_k\|^2/2\sigma_i^2)}$$

其中，$\sigma_i$ 是以$x_i$ 为中心的高斯分布的方差。在此基础上，补充定义$p_{i|i} = 0$.

数据点$x_i,x_j$ 映射到$y_i,y_j$，采用条件概率$q_{j|i}$ 衡量两映射点的相似性，其表达式为

$$q_{j|i} = \frac{\exp(-\|y_i-y_j\|^2)}{\sum_{k \neq i}\exp(-\|y_i-y_k\|^2)}$$

该式是与$p_{j|i}$ 类似的定义，为计算方便，假设其方差$\sigma_i' = 1/\sqrt 2, \forall i$. 同样，也补充定义$q_{i|i} = 0$.

为衡量映射的相似性，我们采用 KL 散度衡量两分布的相似性。代价函数为

$$C = \sum_{i}\mathrm{KL}(P_i\|Q_i) = \sum_{i}\sum_{j}p_{j|i}\log \frac{p_{j|i}}{q_{j|i}}$$

在该式中，超参数为各$p_{j|i}$ 中的高斯分布方差$\sigma_i$.

定义困惑度$\mathrm{Perp}(P_i) = 2^{\mathrm H(P_i)}$，其中$\mathrm H(P_i) = -\sum_j p_{j|i}\log_2p_{j|i}$ 是$P_i$ 的熵，其具体含义是$i$ 的有效邻居的度量。