S 流形学习

• 流形 (manifold)：高维空间中嵌入的低维曲面称为流形。
  • 流形在局部与欧式空间同胚，在局部具有欧式空间的性质。
  • 因而可以在局部建立降维映射关系，再推广到全局。

• 流形学习想要有效进行邻域的保持，就需要样本密采样，然而高维下其实挺难做到的。

A 等度量映射 (Isometric Mapping)

A1 等度量映射

• 思路：低维流形嵌入高维空间之后，直接计算直线距离具有误导性，因为高维空间中的直线距离在低维流形上是不可达的。应该用**「测地线 (geodesic)」距离**表示本真距离。

• 等度量映射方法选择用「近邻距离」去近似「测地线距离」。
  • 具体而言，先得到近邻连接图。
    • 一种方法是确定每个点的 $k$ 近邻（$k$ 数值为超参），然后设置近邻之间的距离为欧氏距离。如果非近邻，距离则为无穷大。
    • 另一种方法是确定每个点的 $\epsilon$ 近邻（$\epsilon$ 数值为超参）。
      • 然而 $\epsilon$ 的选择很关键，过小会导致「断路」，过大会导致「短路」；
    • 是不是可以用抛物或者指数函数确立一个完全连接图？
  • 再通过 Dijkstra 或者 Floyd 算法获得近邻连接图间任意两点的「近邻距离」。
  • 最后就可以作为 MDS 算法的输入进行低维投影的求解。

A2 等度量映射实例

• 之前提到的例子（「20230926 embedding」）的 k=5 近邻降维结果如下，非常好。

• 如果使用指数函数距离，看起来就比较迷了。

B 局部线性嵌入 (Locally Linear Embedding, LLE)

• 在降维的基础之上，尽量保持邻域内样本之间的线性关系。
• 对于样本集合 $X = \{ \boldsymbol x^{(1)}, \boldsymbol x^{(2)}, \cdots, \boldsymbol x^{(|X|)} \}$ 中的每个样本 $\boldsymbol x^{(m)}$，通过某种邻域定义可得到一个邻域集合 $Q^{(m)} = \{ \boldsymbol q^{(m)}_1, \boldsymbol q^{(m)}2, \cdots, \boldsymbol q^{(m)}{|Q^{(m)}|} \}$（各个邻域集合可能不同长度）。

B1 求解权重

• 邻域中样本的数目 $|Q^{(m)}|$ 一般要小于样本的原始维度 $D$，因而对于每个样本 $\boldsymbol x^{(m)}$ 而言，只能近似地用这些邻域样本 $\boldsymbol q^{(m)}_1, \boldsymbol q^{(m)}2, \cdots, \boldsymbol q^{(m)}{|Q^{(m)}|}$ 进行拟合，其中 $w^{(m)}_1, w^{(m)}2, \cdots, w^{(m)}{|Q^{(m)}|}$ 为待求的权重：

  $$ \boldsymbol x^{(m)} \approx \sum_{j=1}^{|Q^{(m)}|} w^{(m)}_j\boldsymbol q^{(m)}_j $$

  • 那么就可以定义拟合误差 $E^{(m)}(\boldsymbol w^{(m)})$ 。

  $$ E^{(m)}(\boldsymbol w^{(m)}) = \left\|\boldsymbol x^{(m)} - \sum_{j=1}^{|Q^{(m)}|} w^{(m)}_j\boldsymbol q^{(m)}_j \right\|^2_2 $$