Robust kernel Isomap

Isomap is one of widely used low-dimensional embedding methods, where geodesic distances on a weighted graph are incorporated with the classical scaling (metric multidimensional scaling). In this paper we pay our attention to two critical issues that were not considered in Isomap, such as: (1) generalization property (projection property); (2) topological stability. Then we present a robust kernel Isomap method, armed with such two properties. We present a method which relates the Isomap to Mercer kernel machines, so that the generalization property naturally emerges, through kernel principal component analysis. For topological stability, we investigate the network flow in a graph, providing a method for eliminating critical outliers. The useful behavior of the robust kernel Isomap is confirmed through numerical experiments with several data sets.     

基于Nyström 低阶近似的半监督流形排序图像检索

实际图像检索过程中,用户提供的相关反馈有限,但存在大量未标记图像数据. 本文在前期半监督流形图像检索工作的基础上,提出一种基于Nystrm低阶 近似的半监督流形排序图像检索方法.通过采用半监督的流形正则化框架, 将图像数据嵌入到低维流形结构中进行分类排序,以充分利用大量未标记数据, 并兼顾分类误差、数据分布的几何结构以及分类函数的复杂性.针对半监督学习速度缓慢的问题, 基于Nystrm低阶近似对学习过程进行加速.在较大规模的Corel图像数据集上进行了检索实验, 实验结果表明该方法能获得较好的效果.     

基于认知的流形学习方法概要

流形学习是一种新出现的机器学习方法,近年来引起越来越多的计算机科学工作者和认知科学工作者的重视.为了加深对流形学习的认识和理解,从流形与流形学习的基本概念入手,追溯它的发展历程.针对目前的几种主要的流形算法,分析它们各自的优势和不足,然后引用LLE的应用示例.说明流形学习较之于传统的线性降维方法如PCA等,能够有效地发现非线性高维数据的本质维数,可以有效地进行维数约简和数据分析.最后对流形学习未来的研究方向做出展望,以期进一步拓展流形学习的应用领域.     

Finding representative landmarks of data on manifolds

Data-driven non-parametric models, such as manifold learning algorithms, are promising data analysis tools. However, to fit an off-training-set data point in a learned model, one must first “locate” the point in the training set. This query has a time cost proportional to the problem size, which limits the model's scalability. In this paper, we address the problem of selecting a subset of data points as the landmarks helping locate the novel points on the data manifolds. We propose a new category of landmarks defined with the following property: the way the landmarks represent the data in the ambient Euclidean space should resemble the way they represent the data on the manifold. Given the data points and the subset of landmarks, we provide procedures to test whether the proposed property presents for the choice of landmarks. If the data points are organized with a neighbourhood graph, as it is often conducted in practice, we interpret the proposed property in terms of the graph topology. We also discuss the extent to which the topology is preserved for landmark set passing our test procedure. Another contribution of this work is to develop an optimization based scheme to adjust an existing landmark set, which can improve the reliability for representing the manifold data. Experiments on the synthetic data and the natural data have been done. The results support the proposed properties and algorithms.     

A visualization metric for dimensionality reduction

Data visualization of high-dimensional data is possible through the use of dimensionality reduction techniques. However, in deciding which dimensionality reduction techniques to use in practice, quantitative metrics are necessary for evaluating the results of the transformation and visualization of the lower dimensional embedding. In this paper, we propose a manifold visualization metric based on the pairwise correlation of the geodesic distance in a data manifold. This metric is compared with other metrics based on the Euclidean distance, Mahalanobis distance, City Block metric, Minkowski metric, cosine distance, Chebychev distance, and Spearman distance. The results of applying different dimensionality reduction techniques on various types of nonlinear manifolds are compared and discussed. Our experiments show that our proposed metric is suitable for quantitatively evaluating the results of the dimensionality reduction techniques if the data lies on an open planar nonlinear manifold. This has practical significance in the implementation of knowledge-based visualization systems and the application of knowledge-based dimensionality reduction methods.     

Inductive manifold learning using structured support vector machine

Most manifold learning techniques are used to transform high-dimensional data sets into low-dimensional space. In the use of such techniques, after unseen data samples are added to the data set, retraining is usually necessary. However, retraining is a time-consuming process and no guarantee of the transformation into the exactly same coordinates, thus presenting a barrier to the application of manifold learning as a preprocessing step in predictive modeling. To solve this problem, learning a mapping from high-dimensional representations to low-dimensional coordinates is proposed via structured support vector machine. After training a mapping, low-dimensional representations of unobserved data samples can be easily predicted. Experiments on several datasets show that the proposed method outperforms the existing out-of-sample extension methods.     

基于 Nyström 低阶近似和谱特征的图像非刚性配准

图像非刚性配准在计算机视觉和医学图像有着重要的作用.然而存在的非刚性配准算法对严重扭曲变形的图像配准精度和效率都比较低.针对该问题,提出基于Nystrm低阶近似和谱特征的图像非刚性配准算法.算法首先提取像素的谱特征,并将谱特征与空间特征、灰度特征融合形成具有扭曲不变性的全局谱特征; 然后在微分同胚配准的框架内使用全局谱匹配,确保算法产生的变形场具有光滑性、可逆性、可微性,以提高配准的精度;其次采用Nystrm抽样方法,随机抽取拉普拉斯矩阵的行与列,低阶逼近该矩阵,降低高维矩阵谱分解的时间,从而提高配准的效率;最后提出基于小波分解的多分辨率图像配准方法,进一步提高配准的精度和效率.理论分析和实验结果均表明,该算法的配准精度和配准效率都有明显的提高.     

Stochastic neighbor projection on manifold for feature extraction

This paper develops a manifold-oriented stochastic neighbor projection (MSNP) technique for feature extraction. MSNP is designed to find a linear projection for the purpose of capturing the underlying pattern structure of observations that actually lie on a nonlinear manifold. In MSNP, the similarity information of observations is encoded with stochastic neighbor distribution based on geodesic distance metric, then the same distribution is required to be hold in feature space. This learning criterion not only empowers MSNP to extract nonlinear feature through a linear projection, but makes MSNP competitive as well by reason that distribution preservation is more workable and flexible than rigid distance preservation. MSNP is evaluated in three applications: data visualization for faces image, face recognition and palmprint recognition. Experimental results on several benchmark databases suggest that the proposed MSNP provides a unsupervised feature extraction approach with powerful pattern revealing capability for complex manifold data.     

Nonlinear embedding preserving multiple local-linearities

Locally linear embedding (LLE) is one of the effective and efficient algorithms for nonlinear dimensionality reduction. This paper discusses the stability of LLE, focusing on the optimal weights for extracting local linearity behind the considered manifold. It is proven that there are multiple sets of weights that are approximately optimal and can be used to improve the stability of LLE. A new algorithm using multiple weights is then proposed, together with techniques for constructing multiple weights. This algorithm is called as nonlinear embedding preserving multiple local-linearities (NEML). NEML improves the preservation of local linearity and is more stable than LLE. A short analysis for NEML is also given for isometric manifolds. NEML is compared with the local tangent space alignment (LTSA) in methodology since both of them adopt multiple local constraints. Numerical examples are given to show the improvement and efficiency of NEML.     

一种邻域竞争线性嵌入的降维方法

针对局部线性嵌入算法处理稀疏数据失效的问题,提出一种基于邻域竞争线性嵌入的降维方法。利用数据的统计信息动态确定局部线性化范围,并采用cam分布寻找数据点的近邻,避免了近邻选取方向的缺失。在数据集稀疏的情况下,通过对数据点近邻做局部结构的提取,该算法能够很好地把握数据的局部信息和整体信息。为了验证算法的有效性,将该算法应用于手工流形降维和对Corel数据库进行图像检索等,结果表明该算法不仅有较好的降维效果,而且具有很好的实用价值。     

EROS: Ensemble rough subspaces

Ensemble learning is attracting much attention from pattern recognition and machine learning domains for good generalization. Both theoretical and experimental researches show that combining a set of accurate and diverse classifiers will lead to a powerful classification system. An algorithm, called FS-PP-EROS, for selective ensemble of rough subspaces is proposed in this paper. Rough set-based attribute reduction is introduced to generate a set of reducts, and then each reduct is used to train a base classifier. We introduce an accuracy-guided forward search and post-pruning strategy to select part of the base classifiers for constructing an efficient and effective ensemble system. The experiments show that classification accuracies of ensemble systems with accuracy-guided forward search strategy will increase at first, arrive at a maximal value, then decrease in sequentially adding the base classifiers. We delete the base classifiers added after the maximal accuracy. The experimental results show that the proposed ensemble systems outperform bagging and random subspace methods in terms of accuracy and size of ensemble systems. FS-PP-EROS can keep or improve the classification accuracy with very few base classifiers, which leads to a powerful and compact classification system.     

Continuum Isomap for manifold learnings

Recently, the Isomap algorithm has been proposed for learning a parameterized manifold from a set of unorganized samples from the manifold. It is based on extending the classical multidimensional scaling method for dimension reduction, replacing pairwise Euclidean distances by the geodesic distances on the manifold. A continuous version of Isomap called continuum Isomap is proposed. Manifold learning in the continuous framework is then reduced to an eigenvalue problem of an integral operator. It is shown that the continuum Isomap can perfectly recover the underlying parameterization if the mapping associated with the parameterized manifold is an isometry and its domain is convex. The continuum Isomap also provides a natural way to compute low-dimensional embeddings for out-of-sample data points. Some error bounds are given for the case when the isometry condition is violated. Several illustrative numerical examples are also provided.     

基于密度缩放因子的ISOMAP算法

等度量映射(ISOMAP)算法是一种被广泛应用的非线性无监督降维算法,通过保持各个观测样本间的测地距离进行等距嵌入,从而实现高维空间向低维空间的坐标转换。但在实际应用中,观测数据无可避免地会存在噪声,由于测地距离的计算对噪声比较敏感,并且也没有考虑数据集的密度分布,导致ISOMAP算法降维后低维坐标表示存在几何变形。针对这一缺点,根据局部密度的思想,提出一种基于密度缩放因子的ISOMAP(Density Scaling Factor Based ISOMAP,D-ISOMAP)算法。在传统的ISOMAP算法框架下,首先,针对每个观测样本计算一个局部密度缩放因子;然后,在测地距离的计算过程中,将直接相邻的两个样本之间的测地距离除以这两个样本密度缩放因子的乘积;最后,通过最短路径算法求得改进后的距离矩阵,并对其进行降维处理。改进的测地距离在密度较大的区域被缩小,而在密度较小的区域被放大,这样可以减小噪声对降维效果的影响,提升可视化和聚类效果。人工数据集和UCI数据集上的实验结果表明,在数据集的可视化和聚类效果方面, D-ISOMAP算法较经典的无监督降维算法具有一定的优势。     

基于局部线性逼近的流形学习算法

流形学习方法是根据流形的定义提出的一种非线性数据降维方法,主要思想是发现嵌入在高维数据空间的低维光滑流形.局部线性嵌入算法是应用比较广泛的一种流形学习方法,传统的局部线性嵌入算法的一个主要缺点就是在处理稀疏源数据时会失效,而实际应用中很多情况还要面对处理源数据稀疏的问题.在分析局部线性嵌入算法的基础上提出了基于局部线性逼近思想的流形学习算法,其通过采用直接估计梯度值的方法达到局部线性逼近的目的,从而实现高维非线性数据的维数约简,最后在S-曲线上进行稀疏采样测试取得良好降维效果.     

Linear discriminant projection embedding based on patches alignment

Dimensionality reduction is often required as a preliminary stage in many data analysis applications. In this paper, we propose a novel supervised dimensionality reduction method, called linear discriminant projection embedding (LDPE), for pattern recognition. LDPE first chooses a set of overlapping patches which cover all data points using a minimum set cover algorithm with geodesic distance constraint. Then, principal component analysis (PCA) is applied on each patch to obtain the data's local representations. Finally, patches alignment technique combined with modified maximum margin criterion (MMC) is used to yield the discriminant global embedding. LDPE takes both label information and structure of manifold into account, thus it can maximize the dissimilarities between different classes and preserve data's intrinsic structures simultaneously. The efficiency of the proposed algorithm is demonstrated by extensive experiments using three standard face databases (ORL, YALE and CMU PIE). Experimental results show that LDPE outperforms other classical and state of art algorithms.     

Locally linear discriminant embedding: An efficient method for face recognition

In this paper an efficient feature extraction method named as locally linear discriminant embedding (LLDE) is proposed for face recognition. It is well known that a point can be linearly reconstructed by its neighbors and the reconstruction weights are under the sum-to-one constraint in the classical locally linear embedding (LLE). So the constrained weights obey an important symmetry: for any particular data point, they are invariant to rotations, rescalings and translations. The latter two are introduced to the proposed method to strengthen the classification ability of the original LLE. The data with different class labels are translated by the corresponding vectors and those belonging to the same class are translated by the same vector. In order to cluster the data with the same label closer, they are also rescaled to some extent. So after translation and rescaling, the discriminability of the data will be improved significantly. The proposed method is compared with some related feature extraction methods such as maximum margin criterion (MMC), as well as other supervised manifold learning-based approaches, for example ensemble unified LLE and linear discriminant analysis (En-ULLELDA), locally linear discriminant analysis (LLDA). Experimental results on Yale and CMU PIE face databases convince us that the proposed method provides a better representation of the class information and obtains much higher recognition accuracies.     

Distinguishing variance embedding

Nonlinear dimensionality reduction is a challenging problem encountered in a variety of high dimensional data analysis. Based on the different geometric intuitions of manifolds, maximum variance unfolding (MVU) and Laplacian eigenmaps are designed for detecting the different aspects of data set. In this paper, combining the ideas of MVU and Laplacian eigenmaps, we propose a new nonlinear dimensionality reduction method called distinguishing variance embedding (DVE), which unfolds the data manifold by maximizing the global variance subject to the proximity relation preservation constraint originated in Laplacian eigenmaps. We illustrate the algorithm on easily visualized examples of curves and surfaces, as well as on actual images of faces, handwritten digits, and rotating objects.