在计算机视觉及机器学习领域,数据的可视化是非常重要的一个应用,一般我们处理的数据都是成百上千维的,但是我们知道,目前我们可以感知的数据维度最多只有三维,超出三维的数据是没有办法直接显示出来的,所以需要做降维的处理,数据的降维,简单来说就是将高维度的数据映射到较低的维度,如果要能达到数据可视化的目的,就要将数据映射到二维或者三维空间。数据的降维是一种无监督的学习过程,我们可以看成是一种聚类。数据在空间的分布主要有两个特性,一个是相似性,我们可以用类内距离衡量;一个是差异性,可以用类间距离衡量。降维算法,在将数据从高维空间映射到低维空间的时候,需要考虑数据的这两个分布特性,也就是要保持数据在高维空间的分布特性。
降维的算法有很多,最经典的就是PCA了,也就是我们常说的主分量分析,PCA是基于数据集的协方差矩阵,考虑的更多是数据的差异性,而对于数据的相似性,或者说数据的局部分布,类似PCA的线性降维算法是无能为力的。
今天,我们介绍一种非常高效的非线性降维算法: t-SNE,t-SNE 算法可以非常有效地把高维的数据映射到低维的空间,并且保持数据在高维空间的局部结构。t-SNE 算法是 SNE 算法的一个延伸,SNE 即 Stochastic Neighbor Embedding 的简称,SNE 算法利用了每一个数据点的邻近数据点的分布来做降维。在介绍 t-SNE 之前,我们先来看看 SNE 算法。
给定一个高维的数据集 ={x1,x2,...xn} , 我们需要将这个高维的数据集映射到一个低维的数据集 ={y1,y2,...yn} ,为了数据便于显示, 的维度一般是二维或者三维。为了衡量高维数据的相似性,SNE算法设置了一个条件概率:
pj|i=exp(−∥xi−xj∥2/(2σ2i))∑k≠iexp(−∥xi−xk∥2/(2σ2i))
pj|i 衡量的是数据点 j 作为数据点 i 的邻域的概率,这个分布类似一个高斯分布,很显然,离 xi 越近的点, pj|i 的值越大,而离得越远的点,那么概率就会越小,利用这个条件概率来表示每一对数据点的相似性,因为我们考虑的是数据点与数据点之间的关系,不考虑数据点自身与自身的关系,所以 pi|i=0 , σi 是方差,后面会介绍如何设置这个方差。
接下来,我们要考虑映射后的低维空间 的数据分布,同样可以用条件概率来表示:
qj|i=exp(−∥yi−yj∥2)∑k≠iexp(−∥yi−yk∥2)
这里将方差设置为 12√ ,所以高斯函数的分母变为1,如果空间 的数据分布可以很好地拟合数据在空间 的分布,那么两者的条件概率应该是一样的,即 pj|i 和 qj|i 是相等的,基于这一点,SNE算法就是想找到这样一个低维空间 ,使得数据集在两个空间的条件概率尽可能接近,可以用 Kullback-Leibler divergence 来衡量:
C=∑iKL(Pi∥Qi)=∑i∑jpj|ilogpj|iqj|i
Pi 表示数据集 中所有其他数据点相对 xi 的条件概率, Qi 表示数据集 中所有其他数据点相对 yi 的条件概率。从上面的表达式可以看出,SNE算法侧重于保持数据的局部结构。为了设置 σi ,可以定义一个 perplexity:
Perp(Pi)=2H(Pi)
H(Pi) 就是我们所说的信息熵
H(Pi)=−∑jpj|ilog2pj|i
利用梯度下降算法,我们可以得到如下的表达式:
∂C∂yi=2∑j(pj|i−qj|i+pi|j−qi|j)(yi−yj)
为了加速收敛以及增加鲁棒性,可以引入 momentum term
(t)=(t−1)+η∂C∂+α(t)((t−1)−(t−2))