Question

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 树一样，都是一种分割 $ MathJax-Element-897 $ 维数据空间的数据结构。

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

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

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

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

   • 将数据集 $ MathJax-Element-778 $ 中的所有点放入根节点。

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

     • 将 $ MathJax-Element-1041 $ 左侧的点划分到左子树。 $ MathJax-Element-1042 $ 左侧的点是满足 $ MathJax-Element-1040 $ 的点。
     • 将 $ MathJax-Element-1041 $ 右侧的点划分到右子树。 $ MathJax-Element-1042 $ 右侧的点是满足 $ MathJax-Element-1043 $ 的点。

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

9.1.2 构建kNN 图

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

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

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

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

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

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

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

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

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

9.2 LargeVis 概率模型

1. LargeVis 根据kNN 图来定义图 $ MathJax-Element-1420 $ ：

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

   • 边集 $ MathJax-Element-1423 $ ：它就是kNN 中所有边的集合。

     其中边的权重 $ MathJax-Element-1442 $ 。

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

   • 定义低维数据点 $ MathJax-Element-937 $ 和 $ MathJax-Element-932 $ 存在边的概率为： $ MathJax-Element-1463 $ 。

     其中：

     • $ MathJax-Element-1474 $ 表示点 $ MathJax-Element-937 $ 和 $ MathJax-Element-932 $ 存在边。
     • $ MathJax-Element-1477 $ 为函数，可以为： $ MathJax-Element-1479 $ 、或者 $ MathJax-Element-1480 $ 。

   • 定义数据点 $ MathJax-Element-937 $ 和 $ MathJax-Element-932 $ 存在边、且其权重为 $ MathJax-Element-383 $ 的概率为： $ MathJax-Element-1485 $ 。

   • 考虑数据集 $ MathJax-Element-1503 $ ，则对数似然函数为：

     $ \mathcal L = \sum_{(i,j) \in E} w_{i,j}\log P(e_{i,j}=1) + \sum_{(i,j) \in \bar E} \gamma\log (1-P(e_{i,j}=1)) $

     其中：

     • $ MathJax-Element-1514 $ 表示 $ MathJax-Element-1423 $ 中的边代表的顶点对。这些顶点对也称作正边 。
     • $ MathJax-Element-1521 $ 表示不存在边的那些顶点对的集合。这些顶点对也称作负边 。
     • $ MathJax-Element-1523 $ 是所有负边的权重。负边的权重是统一的。

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

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

   对图 $ MathJax-Element-731 $ 中的每个顶点 $ MathJax-Element-874 $ ，LargeVis 仅仅从以 $ MathJax-Element-874 $ 为一个端点的负边中随机采样 $ MathJax-Element-1229 $ 个顶点 $ MathJax-Element-1708 $ 来计算 $ MathJax-Element-844 $ 。其中采样概率 $ MathJax-Element-1722 $ ， $ MathJax-Element-1724 $ 为顶点 $ MathJax-Element-875 $ 的度（与它相连的边的数量）。

   则对数似然函数为：

   $ \mathcal L = \sum_{(i,j) \in E} w_{i,j}\left[\log P(e_{i,j}=1) + \sum_{m=1}^M\mathbb E_{j_m\sim P_n(j)} [\gamma\log (1-P(e_{i,j_m}=1))] \right] $

   其中： $ MathJax-Element-1741 $ 表示随机采样的 $ MathJax-Element-1229 $ 个顶点。

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

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

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

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

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

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

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