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{array}{rl}\underset{{\omega }^1,...,{\omega }^k}{min}& \Vert {\mathbf{x}}_i-\sum _j{\omega }^j{\mathbf{n}}_j{\Vert }_2^2\\ \text{s.t.}& \sum _j{\omega }^j=1\end{array}$$

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

$$\left[\begin{array}{cc}{\mathbf{N}}^T\mathbf{N}& \mathbf{1}\\ {\mathbf{1}}^T& \mathbf{0}\end{array}\right]\left[\begin{array}{c}\omega \\ \lambda \end{array}\right]=\left[\begin{array}{c}{\mathbf{N}}^T{\mathbf{x}}_i\\ 1\end{array}\right]$$ $$\mathbf{N}=\left[\begin{array}{cccc}{\mathbf{n}}_1& {\mathbf{n}}_2& \dots & {\mathbf{n}}_k\end{array}\right]$$

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

Embedding Step

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

$$\underset{\mathbf{Y}}{min}\Vert \mathbf{Y}-\mathbf{Y}{W}^T{\Vert }_F^2$$

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

$$\begin{array}{rl}\underset{\mathbf{Y}}{min}& \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{array}$$

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

$$\begin{array}{rl}\Vert \mathbf{Y}-\mathbf{Y}{W}^T{\Vert }_F^2& =\Vert \mathbf{Y}(\mathbf{I}-W^T){\Vert }_F^2\\ & =\text{tr}(\mathbf{Y}(\mathbf{I}-W^T)(\mathbf{I}-W){\mathbf{Y}}^T)\\ & =\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{array}$$

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

$$\begin{array}{rl}\underset{\mathbf{Y}}{min}& \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{array}$$

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

ISOMAP vs. LLE

ISOMAP和LLE最主要的区别在于ISOMAP需要利用全局信息来构建图，这导致它容易受到样本在高维空间分布形式以及噪声的影响。相对地LLE更多地利用了样本的局部信息，因此LLE会更稳定一些。

Other Options

除了上面介绍的两种方法外还可以使用diffusion map来计算样本嵌入。关于diffusion map的细节我们会等到Laplace算子以及heat equation中再进行介绍。

而在几何处理中样本嵌入的一个重要应用是计算网格参数化(mesh parameterization)。简单来说，网格参数化的目的是把一个三维的曲面映射到二维平面上同时维持曲面在三维空间中的一些性质。

还有一些研究考虑使用测地距离而不是欧氏距离来计算样本嵌入。

最后需要说明的是目前人们已经开发出了非常多的嵌入技术，在使用时可以根据实际问题的需要来进行选择。

Other Problems Involving Metrics

Metric Nearness

除了对样本进行嵌入外在度量空间上还有一些其它的问题。比如说对于任意方阵我们可以把它投影到度量空间上，这样的问题称为metric nearness。

Euclidean Matrix Completion

有时我们无法计算任意样本之间的距离，此时可以利用一些凸优化的技术来补全距离矩阵。

Theoretical Challenges

当然对于度量空间还有非常多的理论问题尚待解决。

同时需要说明的是绝大多数的嵌入问题都是NP-hard。

从样本中来学习度量函数的过程称为度量学习(metric learning)。

Reference

• Lecture 11: Structure-preserving embedding (ISOMAP, LLE); manifold learning
• Structure-Preserving Embedding
• Chapter 7: Inverse distance problems