一种基于边界约束的流形展开方法

A Manifold Unfolding Method Based on Boundary Constraints

在流形学习的谱方法中,流形展开被表述为优化问题.这些优化问题的解是退化的,即所有的样本将被嵌入到同一个点.为了避免退化解,谱方法对嵌入坐标人为地强加了一个单位协方差矩阵约束.然而,该约束往往导致流形展开的失真非常明显.本文提出一种新的流形学习方法,彻底抛弃了人为的单位协方差矩阵约束.主要思路是先对流形边界进行嵌入,然后再求流形内部的嵌入;流形边界的嵌入位置被确定后,流形内部样本的嵌入位置将被边界拉开,使得它们不会都收缩到一个点上,从而避免了退化解的出现.将流形边界的嵌入位置作为边界条件,求解一个线性方程组来得到内部样本的嵌入;该线性方程组反映了尽量保持邻近样本间距离不变的要求.流形边界的嵌入由简化流形的嵌入求出;为此,本文还设计了一种流形边界检测算法以及一种流形简化算法.与目前代表性的几种流形学习方法进行了比较实验,结果表明了本文方法的有效性,其展开失真比谱方法明显要小.

In the spectral methods of manifold learning, the manifold unfolding tasks are formulated as optimization problems. The optimal solutions to these problems will embed all samples into one point. To avoid the degenerate solutions, the spectral methods impose a unit covariance constraint to the embedding coordinates. However, this constraint usually causes highly distorted embeddings. A new manifold unfolding method is proposed in this paper, which discards the unit covariance constraint completely. The central idea is to embed the manifold boundary at first, then the inner regions. The embedding positions of inner samples will be pulled out by the embedded boundary to avoid collapsing into one point. The embedding of inner samples is obtained by solving a linear system that reflects local isometry requirement, using the embedding of boundary as a boundary condition. The embedding of boundary is determined by a simplified version of manifold, and a manifold boundary detection algorithm and a manifold graph simplification algorithm are thus also proposed. Experimental results on synthetic and real data sets demonstrate the effectiveness of our method, which results in less mapping distortion than spectral methods.