t-SNE(t-distributed stochastic neighbor embedding)是用于降维的一种机器学习算法,是由 Laurens van der Maaten 和 Geoffrey Hinton在08年提出来。此外,t-SNE 是一种非线性降维算法,非常适用于高维数据降维到2维或者3维,进行可视化。相对于PCA来说,t-SNE更适合高维数据可视化.

image.png

SNE 通过将数据点间的欧几里德距离转化为条件概率而表征相似性:

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

如果以数据点在 x_i 为中心的高斯分布所占的概率密度为标准选择近邻,那么 p_j|i 就代表 x_i 将选择 x_j 作为它的近邻。对于相近的数据点,条件概率 p_j|i 是相对较高的,然而对于分离的数据点,p_j|i 几乎是无穷小量(若高斯分布的方差σ_i 选择合理)。

其中σ_i 是以数据点 x_i 为均值的高斯分布标准差,决定σ_i 值的方法将在本章后一部分讨论。因为我们只对成对相似性的建模感兴趣,所以可以令 p_i|i 的值为零。

现在引入矩阵 Y,Y 是 N*2 阶矩阵,即输入矩阵 X 的 2 维表征。基于矩阵 Y,我们可以构建一个分布 q,其形式与 p 类似。

对于高维数据点 x_ix_j 在低维空间中的映射点 y_iy_j,计算一个相似的条件概率 q_j|i 是可以实现的。我们将计算条件概率 q_i|j 中用到的高斯分布的方差设置为 1/2。因此我们可以对映射的低维数据点 y_jy_i 之间的相似度进行建模:

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

我们的总体目标是选择 Y 中的一个数据点,然后其令条件概率分布 q 近似于 p。这一步可以通过最小化两个分布之间的 KL 散度(损失函数)而实现,这一过程可以定义为:

C = \sum_i KL(P_i || Q_i) = \sum_i \sum_j p_{j|i} \log \frac {p_{j|i}} {q_{j|i}}

因为我们希望能最小化该损失函数,所以我们可以使用梯度下降进行迭代更新,我们可能对如何迭代感兴趣,但我们会在后文讨论与实现。


参考:
https://nlml.github.io/in-raw-numpy/in-raw-numpy-t-sne/
http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf

posted @ 2018-12-19 14:08:31
评论加载中...

发表评论