标题：大规模高维数据可视化
作者来自MSRA
代码开源好用:https://github.com/lferry007/LargeVis
编者的总结
- 类似t-SNE，本文以KNN图捕捉原始数据分布，但目标函数没有采用KL散度，但含义是类似地，只是更好地帮助训练，达成更快的速度和更稳定的参数。
- 对于相似度的度量主要是L2距离，无论在高维或者低维，不清楚在其他度量空间上是否有效。
- 相比于t-SNE，降维速度和参数稳定性有很大提升，但是仍然比较慢，测试1M，8线程要2-3个小时左右。
ABSTRACT
- 本文是t-SNE的进阶版本，有两个主要贡献，一个是原始数据的KNN图构建加速，另一个是KNN图投影到低维空间时的优化目标和训练方法更好更快了。
- 而且超参数更少更稳定，也是一个主要优点。
1. INTRODUCTION
- 降维/可视化的目的是在低维空间保持数据点之间的近邻性，原来近的降维之后也近，原来远的降维之后也远。
- 主要方法有线性（PCA，multi-dimension scaling），和非线性的（local linear embedding, laplacian eigenmaps），按照t-SNE作者的说法，高维数据通常躺在低维空间的非线性流形上，所以线性方法有效性有限。
- 非线性方法也没有在保持局部和全局结构。
- 目前最有效的就是t-SNE，基本策略是用一个KNN图来代表原始数据的分布特征，然后将KNN图投影到二维或低维空间。
image.png
3. LARGEVIS
3.1 Efficient KNN Graph Construction
这一部分没什么好说的，KNN-graph用最新的技术去做就可以了。
本文采用的是用树来初始化knn-graph，用nn-descent来refine的过程，和effana比较像。树的分裂是随机选两个点，取中间平面进行分割。
3.2 A Probabilistic Model for Graph Visualization
首先KNN图边的权重和t-SNE的设计一样：
image.png
- 含义是当前i,j边的长度和i所有的出边的长度和的比值，相当于一种归一化。
- 然后准备投影到低维空间，基本思路是首先随机初始化每个点的坐标，然后根据一个目标函数，每次sample一条边对它的起点进行refine，refine是一个梯度下降的训练过程。
- 目标函数：对于在KNN图中的边，在二维空间上越近越好；反之亦然。KNN图上的边的权重在目标函数上也是一个权重项。
-
表示的是在二维空间上的两点之间相似度，可以用欧氏距离的一些变种来替代。
image.png
- 实际情况1：因为负边实在太多，不可能全用，所以可以采用一些负采样技术，按照一个噪声分布和一个正负边的比例去采样一些边来训练。
- 实际情况2：权重
有时不好控制范围，可以通过权重大的边多采样几次，权重小的边少采样的方式，将权重抹除。
- 优化器：异步随机梯度下降，简单点来说，如果图很稀疏，边很少（比如KNN图K/N的稀疏度），所以并行训练随机采样边几乎不会发生冲突，所以就可以不加锁，同步训练。
网友评论