Data visualization with t-SNE

今天我们讨论数据可视化(data visualization)算法t-SNE (t-distributed Stochastic Neighbor Embedding)，该方法的目的是映射高维数据向量到低维，并保留向量的相似性或者距离。通常我们描述距离会使用类似欧式距离或黎曼距离等概念，映射的方法也多为线性，如PCA。而t-SNE不同，它是用联合概率来描述样本点的相似程度，是非线性的。

SNE算法最早由 Hinton & Roweis 在2002年提出。他们定义高维空间两个点 $\bf{x_i}$ 和 $\bf{x_j}$ 相似度的联合概率分布 $P = p_{ij}$ ，和要映射到的低维空间对应两点 $\bf{y_i}$ 和 $\bf{y_j}$ 的联合概率 $Q = q_{ij}$ . 利用Kullback-Leibler divergence衡量分布$P$和$Q$的相似性，进而最小化这一距离来确定低维空间的映射点 $\bf{y_i}$ .

考虑到SNE算法存在三个缺陷,

KL-divergence 不是对称的;
从高维空间映射到低维空间，距离会发生变化;
高斯分布不是长尾的，对小概率的异常点描述能力较差;

为了解决这一问题，Van der Maaten & Hinton 在2008年提出了改进算法，利用自由度为1的t分布替换高斯分布来定义低维空间的距离，避免异常点，保留高维空间两点的距离关系；设计了具有对称性的概率分布函数。最后，分布$P$和$Q$，KL-divergence $\mathrm{KL}$ 以及对应的梯度公式 $\partial{\mathrm{KL}}/\partial{y_i}$ 如下，

高维空间分布$P$

$\begin{equation} p_{j|i} = \frac{\exp{(-\lVert{\bf{x_{i}} - \bf{x_{j}}}\rVert}^2 / 2\sigma^2_{i})}{\sum_{k\neq i }{\exp{(-\lVert{\bf{x_{i}} - \bf{x_{k}}}\rVert}^2 / 2\sigma^2_{i})}}, \end{equation}$

其中， $p_{j|i}$ 表示 $\bf{x_i}$ 接受 $\bf{x_j}$ 为其同类点的条件概率，相应的 $p_{ij}$ 由下式给出，

$\begin{equation} p_{ij} = \frac{p_{j|i} + p_{i|j}} {2N}. \end{equation}$

其中$N$表示样本点的个数。

低维空间分布$Q$

$\begin{equation} q_{ij} = \frac{(1 + {\lVert {\bf{y_{i}} - \bf{y_{j}}} \rVert}^2)^{-1}}{\sum_{k\neq m}{(1 + {\lVert {\bf{y_{k}} - \bf{y_{m}}} \rVert}^2)^{-1}}}. \end{equation}$

KL-divergence

$\begin{equation} \mathrm{KL}(P||Q) = \sum_{i\neq j}{p_{ij}\log{\frac{p_{ij}}{q_{ij}}}}. \end{equation}$

partial difference of KL over $\bf{y_i}$

$\begin{equation} \frac{\partial{\mathrm{KL}}}{\partial{\bf{y_{i}}}} = 4\sum_{j}{(p_{ij}-q_{ij})(y_{i}-y_{j})(1+(\lVert{y_{i} - y_{j}})^{2})^{-1}}, \end{equation}$

基于以上公式，利用梯度进行优化，求解局部最优，即可对$\bf{y_i}$进行定位。

t-SNE的python实现

python的Scikit-learn提供了TSNE类，用于自动化实现数据可视化，代码样例如下，

from sklearn.manifold import TSNE
def dimension_reduction_tSNE(code,params=None):
	tsne = TSNE()
    for key in params.keys():
        try:
            setattr(tsne, key, params['key'])
        except:
            continue
    code_dim = tsne.fit_transform(code)
    
    return code_dim
code = xxx
params={'n_components': 2, 'learning_rate': 100}
code_dim = dimension_reduction_tSNE(code, params)

其中code表示高维空间的样本矩阵，每行对应一个样本。参数params里的n_components表示低维空间的维数。