九、LargeVis

1. 数据可视化的本质任务是：在低维空间中保存高维数据的内在结构。即：

   • 如果高维空间中两个点相似，则低维空间中它们距离较近。
   • 如果高维空间中两个点不相似，则低维空间中它们距离较远。

2. t-SNE 及其变体的核心思想：

   • 从高维数据中提取数据之间的内在结构。这是通过相似度、条件概率分布来实现的。
   • 将该结构投影到低维空间。这是通过KL 散度来实现的。

3. t-SNE 的重要缺陷：

   • 计算kNN 图存在计算瓶颈。t-SNE 构建kNN 图时采用Vantage-Point 树，其性能在数据维度增加时明显恶化。
   • 当数据量变大时，可视化效率明显恶化。
   • t-SNE 的参数对于不同数据集非常敏感，需要花费较多的时间在调参上。

4. LargeVis 是一种不同的可视化技术，可以支持百万级别的数据点可视化。

   与t-SNE 相比，它主要在以下方面进行了改进：

   • 通过随机投影树来构建近似kNN 图。
   • 提出一个概率模型，该模型的目标函数可以通过异步随机梯度得到优化。

9.1 近似 kNN 图

9.1.1 随机投影树

1. 随机投影树和kd 树一样，都是一种分割 维数据空间的数据结构。

   • kd 树严格按照坐标轴来划分空间，树的深度正比于空间的维度 。

     当 的数值很大（即数据空间维度很高）时，kd 树的深度会非常深。

   • 随机投影树划分空间的方式比较灵活，其深度为 ，其中 为样本的数量。

2. 随机投影树建立过程：

   • 将数据集 中的所有点放入根节点。

   • 随机选取一个从原点出发的向量 ，与这个向量垂直的空间 将根节点划分为两部分。

     • 将 左侧的点划分到左子树。 左侧的点是满足 的点。
     • 将 右侧的点划分到右子树。 右侧的点是满足 的点。
   • 重复划分左子树和右子树，使得每个子树包含的点的数量符合要求。

9.1.2 构建kNN 图

1. LargeVis 通过随机投影树来构建近似 kNN 图。

   首先建立随机投影树。对于数据点 ，找到树中对应的叶节点 。然后将叶节点 对应的子空间中的所有数据点都作为数据点 的候选邻居。

2. 单棵随机投影树构建的 kNN 图精度不高。为了提高kNN图的精度，通常需要建立多个随机投影树 。

   对于数据点 ，对每颗树 ，找到树 中对应的叶节点 。然后将叶节点 对应的子空间中的所有数据点都作为数据点 的候选邻居。

   这种做法的缺点是：为了得到足够高的精度，需要大量的随机投影树，这导致计算量较大。

3. LargeVis 使用邻居探索技术来构建高精度的 kNN 图。

   其基本思路是：邻居的邻居也可能是我的邻居。

   • 首先建立多个随机投影树 ，这里 比较小。
   • 对于数据点 ，在所有这些随机投影树中寻找其候选邻居。
   • 将这些候选邻居的候选邻居都作为 的候选邻居。

   这种方法只需要构建少量的随机投影树，就可以得到足够高精度的kNN 树。

9.2 LargeVis 概率模型

1. LargeVis 根据kNN 图来定义图 ：

   • 顶点集 ：它就是所有高维空间中的数据点的集合。

   • 边集 ：它就是kNN 中所有边的集合。

     其中边的权重 。

2. 将该图 的结构投影到低维空间保持不变。

   • 定义低维数据点 和 存在边的概率为： 。

     其中：

     • 表示点 和 存在边。
     • 为函数，可以为： 、或者 。

   • 定义数据点 和 存在边、且其权重为 的概率为： 。

   • 考虑数据集 ，则对数似然函数为：

     

     其中：

     • 表示 中的边代表的顶点对。这些顶点对也称作正边 。
     • 表示不存在边的那些顶点对的集合。这些顶点对也称作负边 。
     • 是所有负边的权重。负边的权重是统一的。

3. 事实上在kNN 图中，正边的数量较少，负边的数量非常庞大，因此计算 的代价较高。

   LargeVis 利用负采样技术进行优化。

   对图 中的每个顶点 ，LargeVis 仅仅从以 为一个端点的负边中随机采样 个顶点 来计算 。其中采样概率 ， 为顶点 的度（与它相连的边的数量）。

   则对数似然函数为：

   

   其中： 表示随机采样的 个顶点。

4. 由于 中 作为乘积项出现的，而网络中边的权重 变化范围很大，因此梯度变化会较大。这对训练不利，也就是所谓的梯度剧增和消失问题 gradient explosion and vanishing problem 。

   为了解决这个问题，LargeVis 对正边也采用随机采样：若正边的权重为 ，则将其转换为 个权重为 1 的二元边，再随机从这些二元边中进行采样。

   • 每条边的权重都是 1 ，这解决了梯度变化范围大的问题。
   • 因为权重较大的边转换得到的二元边更多，被采样的概率越大，所以保证了正确性和合理性。

5. Largevis 使用异步随机梯度下降来进行训练。

   这在稀疏图上非常有效，因为不同线程采样的边所连接的两个节点很少有重复的，不同线程之间几乎不会产生冲突。

6. Largevis每一轮随机梯度下降的时间复杂度为 ，其中 为负样本个数， 为低维空间的维度。

   随机梯度下降的步数和样本数量 成正比，因此总的时间复杂度为 ，与样本数量呈线性关系。