Shape Analysis课程笔记11-Structure Preserving Embedding

这个系列是MIT 6.838: Shape Analysis的同步课程笔记。本课程会介绍几何方法在图形学、机器学习、计算机视觉、医疗图像以及建筑设计等相关领域的原理和应用。本节主要介绍流形上的嵌入问题。

Intrinsic-to-Extrinsic Embedding

在上一节课中我们主要介绍了如何在欧式空间中通过度量来进行嵌入。在很多现实问题中我们并不关心全局的信息，而是主要考量每个样本和它邻域的局部关系。这样通过局部信息来进行嵌入的问题称为intrinsic embedding。

实际上这种局部嵌入和全局嵌入是相互联系的，人们已经在理论上证明流形可以嵌入到更高维的空间中。

ISOMAP

流形的嵌入是一个非常有研究价值的问题，比如在机器学习领域人们发现很多数据实际上是一个嵌入在高维空间中的流形。和直接在高维空间中进行处理相比，在流形上研究数据的分布往往会得到很多更本质的认识。计算高维数据在流形上分布的经典算法是ISOMAP，它与上一节介绍过的MDS几乎是完全一致的，只是在构造距离矩阵时需要使用图上的最短路径而不是直接使用高维空间中的距离。

在计算图上任意节点之间的最短路径时可以使用Dijkstra算法对所有节点进行遍历。不过这里更推荐使用Floyd-Warsahll算法，它可以直接计算出所有节点对的最短路径。

类似于Landmark MDS，只要对ISOMAP稍加改造就可以得到Landmark ISOMAP，它对于增量式的问题有更好的性能。

Locally-Linear Embedding

除了ISOMAP之外另一种处理流形嵌入的经典算法是locally-linear embedding(LLE)，它的思想是使用样本的邻域来进行嵌入并保证嵌入前后局部的权重是一样的。因此LLE的主要流程可以分为analysis step和embedding step两步：在analysis step中计算每个样本和它邻域的权重，而在embedding step则计算样本在给定权重下的嵌入。

Analysis Step

analysis step的目标是对于任意样本\(\mathbf{x}_i\)计算它和\(k\)个相邻样本的权重，它可以表述为如下的优化问题：

\[\begin{aligned} \min_{\omega^1, ..., \omega^k} \ &\Vert \mathbf{x}_i - \sum_j \omega^j \mathbf{n}_j \Vert_2^2 \\ \text{s.t.} \ & \sum_j \omega^j = 1 \end{aligned}\]

对于这样的约束优化问题，我们可以使用Lagrangian乘子法来转换成求解线性系统：

\[\begin{bmatrix} \mathbf{N}^T \mathbf{N} & \mathbf{1} \\ \mathbf{1}^T & \mathbf{0} \end{bmatrix} \begin{bmatrix} \omega \\ \lambda \end{bmatrix} = \begin{bmatrix} \mathbf{N}^T \mathbf{x}_i \\ 1 \end{bmatrix}\] \[\mathbf{N} = \begin{bmatrix} \mathbf{n}_1 & \mathbf{n}_2 & \dots & \mathbf{n}_k \end{bmatrix}\]

因此在analysis step中我们只需要对样本进行遍历，通过寻找它的\(k\)个邻居然后构造并求解线性系统即可。

Embedding Step

在embedding step中我们需要计算样本\(\mathbf{x}_i\)的一个低维嵌入\(\mathbf{y}_i\)同时保持它和邻域之间的局部权重。因此我们可以构造出优化问题：

\[\min_\mathbf{Y} \ \Vert \mathbf{Y} - \mathbf{Y} W^T \Vert_F^2\]

其中\(W\)是analysis step计算得到的样本权重矩阵。注意到上式的解包含平凡解\(\mathbf{Y} = \mathbf{0}\)，为了避免这种情况我们需要引入额外的约束条件：

\[\begin{aligned} \min_\mathbf{Y} \ & \Vert \mathbf{Y} - \mathbf{Y} W^T \Vert_F^2 \\ \text{s.t.} \ & \mathbf{Y} \mathbf{Y}^T = \mathbf{I} \\ & \mathbf{Y} \mathbb{1} = \mathbb{0} \end{aligned}\]

可以证明此时的优化问题等价于求解特征值问题：

\[\begin{aligned} \Vert \mathbf{Y} - \mathbf{Y} W^T \Vert_F^2 &= \Vert \mathbf{Y} (\mathbf{I} - W^T) \Vert_F^2 \\ &= \text{tr} \big( \mathbf{Y} (\mathbf{I} - W^T) (\mathbf{I} - W) \mathbf{Y}^T \big) \\ &= \text{tr} ( \mathbf{Y} ( \mathbf{I} - W - W^T + W^T W ) \mathbf{Y}^T ) \\ &= \text{tr} ( \mathbf{Y} \mathbf{M} \mathbf{Y}^T ) \end{aligned}\]

此时的优化问题可以表示为：

\[\begin{aligned} \min_\mathbf{Y} \ & \text{tr} ( \mathbf{Y} \mathbf{M} \mathbf{Y}^T ) \\ \text{s.t.} \ & \mathbf{Y} \mathbf{Y}^T = \mathbf{I} \\ & \mathbf{Y} \mathbb{1} = \mathbb{0} \end{aligned}\]

而它的解是取\(\mathbf{Y}\)为\(\mathbf{M}\)的\(p\)个最小非零特征值。