标题：大规模高维数据可视化
作者来自MSRA
代码开源好用:https://github.com/lferry007/LargeVis

编者的总结

1. 类似t-SNE，本文以KNN图捕捉原始数据分布，但目标函数没有采用KL散度，但含义是类似地，只是更好地帮助训练，达成更快的速度和更稳定的参数。
2. 对于相似度的度量主要是L2距离，无论在高维或者低维，不清楚在其他度量空间上是否有效。
3. 相比于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的稀疏度），所以并行训练随机采样边几乎不会发生冲突，所以就可以不加锁，同步训练。