Nonlinear Dimensionality Reduction by Topologically Constrained Isometric Embedding

Many manifold learning procedures try to embed a given feature data into a flat space of low dimensionality while preserving as much as possible the metric in the natural feature space. The embedding process usually relies on distances between neighboring features, mainly since distances between features that are far apart from each other often provide an unreliable estimation of the true distance on the feature manifold due to its non-convexity. Distortions resulting from using long geodesics indiscriminately lead to a known limitation of the Isomap algorithm when used to map non-convex manifolds. Presented is a framework for nonlinear dimensionality reduction that uses both local and global distances in order to learn the intrinsic geometry of flat manifolds with boundaries. The resulting algorithm filters out potentially problematic distances between distant feature points based on the properties of the geodesics connecting those points and their relative distance to the boundary of the feature manifold, thus avoiding an inherent limitation of the Isomap algorithm. Since the proposed algorithm matches non-local structures, it is robust to strong noise. We show experimental results demonstrating the advantages of the proposed approach over conventional dimensionality reduction techniques, both global and local in nature.     

Unsupervised manifold learning based on multiple feature spaces

Manifold learning is a well-known dimensionality reduction scheme which can detect intrinsic low-dimensional structures in non-linear high-dimensional data. It has been recently widely employed in data analysis, pattern recognition, and machine learning applications. Isomap is one of the most promising manifold learning algorithms, which extends metric multi-dimensional scaling by using approximate geodesic distance. However, when Isomap is conducted on real-world applications, it may have some difficulties in dealing with noisy data. Although many applications represent a special sample by multiple feature vectors in different spaces, Isomap employs samples in unique observation space. In this paper, two extended versions of Isomap to multiple feature spaces problem, namely fusion of dissimilarities and fusion of geodesic distances, are presented. We have employed the advantages of several spaces and depicted the Euclidean distance on learned manifold that is more compatible to the semantic distance. To show the effectiveness and validity of the proposed method, some experiments have been carried out on the application of shape analysis on MPEG7 CE Part B and Fish data sets.     

基于鲁棒的全局流形学习方法

非线性降维在数据挖掘、机器学习、图像分析和计算机视觉等领域应用广泛。等距映射算法(Isomap)是一种全局流形学习方法,能有效地学习等距流形的“低维嵌入”,但它对数据中的离群样本点缺乏鲁棒性。针对这种情况,该文提出一种离群点检测方法,基于Isomap的基本思想,给出一种鲁棒的全局流形学习方法,提高Isomap处理离群样本点的能力。数值实验表明了该方法的有效性。     

一种基于加权标志点的流形学习算法

近年来出现的一系列进行维数约简的非线性方法——流形学习中等距映射（Isomap）是其中的代表,该算法高效、简单,但计算复杂度较高。基于标志点（Landmark Points）的L-Isomap减少了计算复杂度,但对于标志点的选取,大都采用随机的方法,致使该算法不稳定。考虑到样本点和近邻点相对位置,将对嵌入流形影响较大的样本点赋予较高的权重。然后根据权重大小选择标志点,同时考虑标志点之间的相对位置,使得选出的标志点不会出现过度集中的现象,近似直线分布的概率也大大降低,从而保证了算法的稳定性。实验结果表明,该算法在标志点数量较少的情况下,比L-Isomap稳定,且对缺失数据的不完整流形,也能获取和Isomap相差不大的结果。     

1D representation of Isomap for united video coding

This paper proposes a 1D representation of isometric feature mapping (Isomap) based united video coding algorithms. First, 1D Isomap representations that maintain distances are generated which can achieve a very high compression ratio. Next, embedding and reconstruction algorithms for the 1D Isomap representation are presented that can transform samples from a high-dimensional space to a low-dimensional space and vice versa. Then, dictionary learning algorithms for training samples are proposed to compress the input samples. Finally, a unified coding framework for diverse videos based on a 1D Isomap representation is built. The proposed methods make full use of correlations between internal and external videos, which are not considered by classical methods. Simulation experiments have shown that the proposed methods can obtain higher peak signal-to-noise ratios than standard highly efficient video coding for similar bit per pixel levels in the low bit rate situation.     

Image Manifolds which are Isometric to Euclidean Space

Recently, the Isomap procedure [10] was proposed as a new way to recover a low-dimensional parametrization of data lying on a low-dimensional submanifold in high-dimensional space. The method assumes that the submanifold, viewed as a Riemannian submanifold of the ambient high-dimensional space, is isometric to a convex subset of Euclidean space. This naturally raises the question: what datasets can reasonably be modeled by this condition? In this paper, we consider a special kind of image data: families of images generated by articulation of one or several objects in a scene—for example, images of a black disk on a white background with center placed at a range of locations. The collection of all images in such an articulation family, as the parameters of the articulation vary, makes up an articulation manifold, a submanifold of L ². We study the properties of such articulation manifolds, in particular, their lack of differentiability when the images have edges. Under these conditions, we show that there exists a natural renormalization of geodesic distance which yields a well-defined metric. We exhibit a list of articulation models where the corresponding manifold equipped with this new metric is indeed isometric to a convex subset of Euclidean space. Examples include translations of a symmetric object, rotations of a closed set, articulations of a horizon, and expressions of a cartoon face. The theoretical predictions from our study are borne out by empirical experiments with published Isomap code. We also note that in the case where several components of the image articulate independently, isometry may fail; for example, with several disks in an image avoiding contact, the underlying Riemannian manifold is locally isometric to an open, connected, but not convex subset of Euclidean space. Such a situation matches the assumptions of our recently-proposed Hessian Eigenmaps procedure, but not the original Isomap procedure.     

基于集成的流形学习可视化

流形学习有助于发现数据的内在分布和几何结构.目前已有的流形学习算法对噪音和算法参数都比较敏感,噪音使得输入参数更加难以选择,参数较小的变化会导致差异显著的学习结果.针对Isomap这一流形学习算法,提出了一种新方法,通过引入集成学习技术,扩大了可以产生有效可视化结果的输入参数范围,并且降低了对噪音的敏感性.     

Human action segmentation and classification based on the Isomap algorithm

Visual analysis of human behavior has attracted a great deal of attention in the field of computer vision because of the wide variety of potential applications. Human behavior can be segmented into atomic actions, each of which indicates a single, basic movement. To reduce human intervention in the analysis of human behavior, unsupervised learning may be more suitable than supervised learning. However, the complex nature of human behavior analysis makes unsupervised learning a challenging task. In this paper, we propose a framework for the unsupervised analysis of human behavior based on manifold learning. First, a pairwise human posture distance matrix is derived from a training action sequence. Then, the isometric feature mapping (Isomap) algorithm is applied to construct a low-dimensional structure from the distance matrix. Consequently, the training action sequence is mapped into a manifold trajectory in the Isomap space. To identify the break points between the trajectories of any two successive atomic actions, we represent the manifold trajectory in the Isomap space as a time series of low-dimensional points. A temporal segmentation technique is then applied to segment the time series into sub series, each of which corresponds to an atomic action. Next, the dynamic time warping (DTW) approach is used to cluster atomic action sequences. Finally, we use the clustering results to learn and classify atomic actions according to the nearest neighbor rule. If the distance between the input sequence and the nearest mean sequence is greater than a given threshold, it is regarded as an unknown atomic action. Experiments conducted on real data demonstrate the effectiveness of the proposed method.     

一种新的有监督流形学习方法

提出了一种新的有监督流形学习方法,目的是提供将流形学习降维方法高效应用于有监督学习问题的全新策略.算法的核心思想是集成流形学习方法对高维流形结构数据的降维有效性与支撑向量机(SVM)在中小规模分类数据集上的优良特性实现高效有监督流形学习.算法具体实现步骤为:首先利用SVM在流形学习降维数据中选出对分类决策最重要的数据集,即支撑向量集;按标号返回可得到原空间的支撑向量集;在这个集合上再次使用SVM即可得到原空间的分类决策,从而完成有监督流形学习.在一系列人工与实际数据集上的实验验证了方法的有效性.     

高维数据流形的低维嵌入及嵌入维数研究

发现高维数据空间流形中有意义的低维嵌入是一个经典难题.Isomap是提出的一种有效的基于流形理论的非线性降维方法,它不仅能够揭示高维观察数据的内在结构,还能够发现潜在的低维参教空间.Isomap的理论基础是假设在高维数据空间和低维参数空间存在等距映射,但并没有进行证明.首先给出了高维数据的连续流形和低维参数空间之间的等距映射存在性证明,然后区分了嵌入空间维数、高维数据空间的固有维数和流形维数,并证明存在环状流形高维数据空间的参数空间维数小于嵌入空间维数.最后提出一种环状流形的发现算法,判断高维数据空间是否存在环状流形,进而估计其固有维教及潜在空间维数.在多姿态三维对象的实验中证明了算法的有效性,并得到正确的低维参数空间.     

Manifold learning based speaker dependent dimension reduction for robust text independent speaker verification

Speaker verification has been studied widely from different points of view, including accuracy, robustness and being real-time. Recent studies have turned toward better feature stability and robustness. In this paper we study the effect of nonlinear manifold based dimensionality reduction for feature robustness. Manifold learning is a popular recent approach for nonlinear dimensionality reduction. Algorithms for this task are based on the idea that each data point may be described as a function of only a few parameters. Manifold learning algorithms attempt to uncover these parameters in order to find a low-dimensional representation of the data. From the manifold based dimension reduction approaches, we applied the widely used Isometric mapping (Isomap) algorithm. Since in the problem of speaker verification, the input utterance is compared with the model of the claiming client, a speaker dependent feature transformation would be beneficial for deciding on the identity of the speaker. Therefore, our first contribution is to use Isomap dimension reduction approach in the speaker dependent context and compare its performance with two other widely used approaches, namely principle component analysis and factor analysis. The other contribution of our work is to perform the nonlinear transformation in a speaker-dependent framework. We evaluated this approach in a GMM based speaker verification framework using Tfarsdat Telephone speech dataset for different noises and SNRs and the evaluations have shown reliability and robustness even in low SNRs. The results also show better performance for the proposed Isomap approach compared to the other approaches.     

几种流形学习算法的比较研究

如何发现高维数据空间流形中有意义的低维嵌入信息是流形学习的主要目的。目前,大部分流形学习算法都是用于非线性维数约简或是数据可视化的,如等距映射（Isomap）,局部线性嵌入算法（LLE）,拉普拉斯特征映射算（laplacian Eigenmap）等等,文章对这三种流形学习算法进行实验分析与比较,目的在于了解这几种流形学习算法的特点,以便更好地进行数据的降维与分析。     

针对环状流形数据的非线性降维

近年来出现了多种新型的非线性降维方法,且在一些应用中体现出良好的效果.然而,当面对球体、柱体等环状流形产生的非线性流形数据时,这些方法往往会失效.针对这一问题,提出了针对环状流形数据的环结构检测算法与非线性降维方法.理论上,基于目前极受关注的Isomap降维方法的运行原理,给出了一个判断环状流形的充要条件;算法上利用所得的判断定理,制订了基于数据的环状流形检测算法:最后基于所找到的环结构,利用极坐标展开的思想设计了针对环状流形数据的非线性降维策略.针对一系列典型环状流形数据集的仿真实验结果表明,与其他流形学习降维方法相比,该方法对环状流形数据进行降维具有显著优势.     

一种快速映射Isomap算法

传统的Isomap算法仅侧重于当前数据的分析,不能提供由高维空间到低维空间的快速直接映射,因此无法用于特征提取和高维数据检索.针对这一问题,文中提出一种基于Isornap的快速数据检索算法.该算法能够快速得到新样本的低维嵌入坐标,并基于此坐标检索与输入样本最相似的参考样本.在典型测试集上的实验结果表明,该算法在实现新样本到低维流形快速映射的同时,能较好保留样本的近邻关系.     

基于拉普拉斯特征映射的启发式Q学习

在基于目标的强化学习任务中, 欧氏距离常作为启发式函数用于策略选择, 其用于状态空间在欧氏空间内不连续的任务效果不理想. 针对此问题, 引入流形学习中计算复杂度较低的拉普拉斯特征映射法, 提出一种基于谱图理论的启发式策略选择方法. 所提出的方法适用于状态空间在某个内在维数易于估计的流形上连续, 且相邻状态间的连接关系为无向图的任务. 格子世界的仿真结果验证了所提出方法的有效性.

     

Categorical structural optimization using discrete manifold learning approach and custom-built evolutionary operators

In present work, we address the non-ordinal categorical design variables, such as different beam/bar cross-section types, various materials or components available within a catalog. We interpret the admissible values of categorical variables as discrete points in multi-dimensional space of physical attributes, which allows computing distances but has no ordering property. Then we propose to use the Isomap manifold learning approach to eliminate the possibly redundant dimensionality and obtain a reduced-order design space in which the geodesic distances are preserved in a low-dimensional graph. Then, taking advantage of the shortest path and the neighbors provided by Dijkstra algorithm, we propose graph-based crossover and mutation operators to be used in evolutionary optimization. The method is applied to the optimal design of truss and frame structures.     

Kernel ridge regression for out-of-sample mapping in supervised manifold learning

Manifold learning methods for unsupervised nonlinear dimensionality reduction have proven effective in the visualization of high dimensional data sets. When dealing with classification tasks, supervised extensions of manifold learning techniques, in which class labels are used to improve the embedding of the training points, require an appropriate method for out-of-sample mapping.In this paper we propose multi-output kernel ridge regression (KRR) for out-of-sample mapping in supervised manifold learning, in place of general regression neural networks (GRNN) that have been adopted by previous studies on the subject. Specifically, we consider a supervised agglomerative variant of Isomap and compare the performance of classification methods when the out-of-sample embedding is based on KRR and GRNN, respectively. Extensive computational experiments, using support vector machines and k-nearest neighbors as base classifiers, provide statistical evidence that out-of-sample mapping based on KRR consistently dominates its GRNN counterpart, and that supervised agglomerative Isomap with KRR achieves a higher accuracy than direct classification methods on most data sets.     

流形学习概述

流形学习是一种新的非监督学习方法,近年来引起越来越多机器学习和认知科学工作者的重视.为了加深对流形学习的认识和理解,该文由流形学习的拓扑学概念入手,追溯它的发展过程.在明确流形学习的不同表示方法后,针对几种主要的流形算法,分析它们各自的优势和不足,然后分别引用Isomap和LLE的应用示例.结果表明,流形学习较之于传统的线性降维方法,能够有效地发现非线性高维数据的本质维数,利于进行维数约简和数据分析.最后对流形学习未来的研究方向做出展望,以期进一步拓展流形学习的应用领域.     

Dimensionality reduction-based spoken emotion recognition

To improve effectively the performance on spoken emotion recognition, it is needed to perform nonlinear dimensionality reduction for speech data lying on a nonlinear manifold embedded in a high-dimensional acoustic space. In this paper, a new supervised manifold learning algorithm for nonlinear dimensionality reduction, called modified supervised locally linear embedding algorithm (MSLLE) is proposed for spoken emotion recognition. MSLLE aims at enlarging the interclass distance while shrinking the intraclass distance in an effort to promote the discriminating power and generalization ability of low-dimensional embedded data representations. To compare the performance of MSLLE, not only three unsupervised dimensionality reduction methods, i.e., principal component analysis (PCA), locally linear embedding (LLE) and isometric mapping (Isomap), but also five supervised dimensionality reduction methods, i.e., linear discriminant analysis (LDA), supervised locally linear embedding (SLLE), local Fisher discriminant analysis (LFDA), neighborhood component analysis (NCA) and maximally collapsing metric learning (MCML), are used to perform dimensionality reduction on spoken emotion recognition tasks. Experimental results on two emotional speech databases, i.e. the spontaneous Chinese database and the acted Berlin database, confirm the validity and promising performance of the proposed method.     

有监督S-kv-Isomap在入侵检测中的应用

入侵检测是计算机安全研究方面的热点领域,在入侵检测数据可视化和分类方面面临的问题是其高维特性。流形学习算法Isomap是有效的非线性降维工具。但是Isomap算法在实际应用中存在不能保证构造连通的邻接图和没有利用样本已知类别标记的缺点,针对上述缺陷提出了健壮的有监督S-kv-Isomap算法。该算法利用类别标记来指导降维,并且利用k-variable算法构造联通的邻接图。实验选用KDDCUP1999数据集,对四类入侵数据即Dos、R2L、Probe、U2R进行了可视化和分类研究。可视化中比较了S-kv-Isomap算法与kv-Isomap算法,前者具有更好的可视化效果。在分类研究中比较了S-kv-Isomap、kv-Isomap、SVM和k-NN算法,实验结果表明,S-kv-Isomap方法在入侵检测中不仅保持较高的入侵检测率,而且误警率很低。