基于流形学习的维数约简算法

介绍线性维数约简的主成分分析和多维尺度算法,描述几种经典的能发现嵌入在高维数据空间的低维光滑流形非线性维数约简算法,包括等距映射、局部线性嵌入、拉普拉斯特征映射、局部切空间排列、最大方差展开。与线性维数约简算法相比,非线性维数约简算法通过维数约简能够发现不同类型非线性高维数据的本质特征。     

Feature extraction using orthogonal discriminant local tangent space alignment

A novel algorithm called orthogonal discriminant local tangent space alignment (O-DLTSA) is proposed for supervised feature extraction. Derived from local tangent space alignment (LTSA), O-DLTSA not only inherits the advantages of LTSA which uses local tangent space as a representation of the local geometry so as to preserve the local structure, but also makes full use of class information and orthogonal subspace to improve discriminant power. The experimental results of applying O-DLTSA to standard face databases demonstrate the effectiveness of the proposed method.     

基于几何距离摄动的局部切空间排列算法

局部切空间排列算法（Local Tangent Space Alignment）是一种具有严格数学推理的流形学习算法,能有效地学习出高维数据的低维嵌入坐标,但也存在一些不足,如对近邻点的选取依赖性较强、不适应处理高曲率分布、稀疏分布数据源。针对这些缺点,提出了一种基于几何距离摄动的局部切空间排列算法。利用几何摄动条件把样本空间划分为一组线性分块的组合,在每一个线性块上应用LTSA算法完成降维。实验结果表明了该算法的有效性。     

Tensor distance based multilinear globality preserving embedding: A unified tensor based dimensionality reduction framework for image and video classification

Image and video classification tasks often suffer from the problem of high-dimensional feature space. How to discover the meaningful, low-dimensional representations of such high-order, high-dimensional observations remains a fundamental challenge. In this paper, we present a unified framework for tensor based dimensionality reduction including a new tensor distance (TD) metric and a novel multilinear globality preserving embedding (MGPE) strategy. Different with the traditional Euclidean distance, which is constrained by orthogonality assumption, TD measures the distance between data points by considering the relationships among different coordinates of high-order data. To preserve the natural tensor structure in low-dimensional space, MGPE directly works on the high-order form of input data and employs an iterative strategy to learn the transformation matrices. To provide faithful global representation for datasets, MGPE intends to preserve the distances between all pairs of data points. According to the proposed TD metric and MGPE strategy, we further derive two algorithms dubbed tensor distance based multilinear multidimensional scaling (TD-MMDS) and tensor distance based multilinear isometric embedding (TD-MIE). TD-MMDS finds the transformation matrices by keeping the TDs between all pairs of input data in the embedded space, while TD-MIE intends to preserve all pairwise distances calculated according to TDs along shortest paths in the neighborhood graph. By integrating tensor distance into tensor based embedding, TD-MMDS and TD-MIE perform tensor based dimensionality reduction through the whole learning procedure and achieve obvious performance improvement on various standard datasets.     

Robust local tangent space alignment via iterative weighted PCA

Recently manifold learning has attracted extensive interest in machine learning and related communities. This paper investigates the noise manifold learning problem, which is a key issue in applying manifold learning algorithm to practical problems. We propose a robust version of LTSA algorithm called RLTSA. The proposed RLTSA algorithm makes LTSA more robust from three aspects: firstly robust PCA algorithm based on iterative weighted PCA is employed instead of the standard SVD to reduce the influence of noise on local tangent space coordinates; secondly RLTSA chooses neighborhoods that are well approximated by the local coordinates to align with the global coordinates; thirdly in the alignment step, the influence of noise on embedding result is further reduced by endowing clean data points and noise data points with different weights into the local alignment errors. Experiments on both synthetic data sets and real data sets demonstrate the effectiveness of our RLTSA when dealing with noise manifold.     

基于流形学习的正交稀疏保留投影

稀疏保留投影通过保留样本之间的全局稀疏重构关系来进行特征提取,获得了良好的分类效果。但是,稀疏保留投影得到的投影变换通常不是正交的,而且在实际应用中,正交性一直被认为有利于提高鉴别能力。另外,根据流形学习理论,局部流形结构比全局欧式结构更重要。因此,文中在稀疏保留投影中引入了流形结构保留和正交投影,提出了整体正交流形稀疏保留投影（HOMSPP）和迭代正交流形稀疏保留投影（IOMSPP）两种实现算法来实现人脸和掌纹图像的特征提取。     

一种新的基于MMC和LSE的监督流形学习算法

针对局部样条嵌入算法 （Local spline embedding,LSE） 存在样本外点学习和无监督模式学习问题,本文提出了一种新颖的正交局部样条判别投影算法 （O-LSDP）.该算法通过引入明确的线性映射关系,构建平移缩放模型,以及正交化特征子空间,从而使该算法能够应用于模式分类问题并显著改善了算法的分类识别能力.在标准人 脸数据库和植物叶片数据库上的实验结果验证了该算法的有效性与可行性.     

基于局部与全局保持的半监督维数约减方法

在很多机器学习和数据挖掘任务中,仅仅利用边信息(side-information)并不能得到最好的半监督学习(semi-supervised learning)效果,因此,提出一种基于局部与全局保持的半监督维数约减(local and global preserving based semi-supervised dimensionality reduction,简称LGSSDR)方法.该算法不仅能够保持正、负约束信息而且能够保持数据集所在低维流形的全局以及局部信息.另外,该算法能够计算出变换矩阵并较容易地处理未见样本.实验结果验证了该算法的有效性.     

局部保持的流形学习算法对比研究

局部保持的流形学习通过从局部到整体的思想保持观测空间和内在嵌入空间的局部几何共性,发现嵌入在高维欧氏空间中的内在低维流形。分析了局部保持的流形学习算法的基本实现框架,详细比较了一些局部保持的流形学习算法的特点,提出了几个有益的研究主题。     

Stable local dimensionality reduction approaches

Dimensionality reduction is a big challenge in many areas. A large number of local approaches, stemming from statistics or geometry, have been developed. However, in practice these local approaches are often in lack of robustness, since in contrast to maximum variance unfolding (MVU), which explicitly unfolds the manifold, they merely characterize local geometry structure. Moreover, the eigenproblems that they encounter, are hard to solve. We propose a unified framework that explicitly unfolds the manifold and reformulate local approaches as the semi-definite programs instead of the above-mentioned eigenproblems. Three well-known algorithms, locally linear embedding (LLE), laplacian eigenmaps (LE) and local tangent space alignment (LTSA) are reinterpreted and improved within this framework. Several experiments are presented to demonstrate the potential of our framework and the improvements of these local algorithms.     

最大方差展开的快速松弛算法

最大方差展开(maximum variance unfolding,MVU)是在流形局部等距概念基础上提出的一种新的非线性维数约减算法,能有效学习出隐含在高维数据集中的低维流形结构.但MVU的优化需要解决一个半定规划(semidefinite programming,SDP)问题,巨大的计算和存储复杂度限制了它在大规模数据集上的可行性.提出了MVU的一种快速算法--松弛最大方差展开(relaxed maximum varianceunfolding,RMVU),算法基于Laplacian特征映射(Laplacian eigenmap)近似保留数据集局部结构的思想,对MVU中严格的局部距离保留约束进行松弛;算法求解转变为一个广义特征分解问题,大大降低了运算强度和存储需求.为了适应更大规模数据集的处理需求,同时提出了RMVU的一种改进算法--基于基准点的松弛最大方差展开(landmark-based relaxed MVU,LRMVU).在模拟数据集和COLT-20数据库上的实验验证了算法的有效性.     

基于流形学习的整体正交稀疏保留鉴别分析

稀疏保留投影是一种有效的特征提取方法,但是其主要关注样本间的全局稀疏重构关系,并且得到的投影变换通常不是正交的。在实际应用中,图像数据往往处于高维空间中的一种低维流形中,正交性一直被认为有利于提高鉴别能力。文中以有监督学习的方式在稀疏保留投影中引入了流形结构保留,并使得投影空间正交,从而提出了一种新的特征提取方法,即基于流形学习的整体正交稀疏保留鉴别分析（MLHOSDA）。在人脸和掌纹图像数据库的实验结果表明此方法具有较好的识别效果。     

Extended local tangent space alignment for classification

The local tangent space alignment (LTSA) has demonstrated promising results in finding meaningful low-dimensional structures hidden in high-dimensional data. However, LTSA may have a limited effectiveness on the data which are organized in multiple classes or contain noisy points. In this paper, the distances between the samples and their neighbors are rescaled by using the reconstruction weights to overcome the limitation. An extension of LTSA is proposed based on the local rescaled distance matrix. Numerical experiments on both synthetic and real-world data sets are used to show the improvement of our extension for classification and the robustness to noisy data.     

Face recognition using second-order discriminant tensor subspace analysis

Discriminant information (DI) plays a critical role in face recognition. In this paper, we proposed a second-order discriminant tensor subspace analysis (DTSA) algorithm to extract discriminant features from the intrinsic manifold structure of the tensor data. DTSA combines the advantages of previous methods with DI, the tensor methods preserving the spatial structure information of the original image matrices, and the manifold methods preserving the local structure of the samples distribution. DTSA defines two similarity matrices, namely within-class similarity matrix and between-class similarity matrix. The within-class similarity matrix is determined by the distances of point pairs in the same class, while the between-class similarity matrix is determined by the distances between the means of each pair of classes. Using these two matrices, the proposed method preserves the local structure of the samples to fit the manifold structure of facial images in high dimensional space better than other methods. Moreover, compared to the 2D methods, the tensor based method employs two-sided transformations rather than single-sided one, and yields higher compression ratio. As a tensor method, DTSA uses an iterative procedure to calculate the optimal solution of two transformation matrices. In this paper, we analyzed DTSA's connections to 2D-DLPP and TSA, theoretically. The experiments on the ORL, Yale and YaleB facial databases show the effectiveness of the proposed method.     

局部切空间对齐算法的核主成分分析解释

基于核方法的降维技术和流形学习是两类有效而广泛应用的非线性降维技术,它们有着各自不同的出发点和理论基础,在以往的研究中很少有研究关注两者的联系。LTSA算法利用数据的局部结构构造一种特殊的核矩阵,然后利用该核矩阵进行核主成分分析。本文针对局部切空间对齐这种流形学习算法,重点研究了LTSA算法与核PCA的内在联系。研究表明,LTSA在本质上是一种基于核方法的主成分分析技术。     

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.     

核正交判别局部正切空间对齐算法

针对现有的局部正切空间算法中存在的问题,文中提出一种基于核变换的特征提取方法——核正交判别局部正切空间对齐算法(KOTSDA)。该算法首先利用核方法将人脸图像投影到一个高维非线性空间,提取其非线性信息;然后在目标函数中利用正切空间判别分析算法在保持样本的类内局部几何结构的同时最大化类间差异;最后添加正交约束,得到核正交判别局部正切空间对齐算法。该算法不需要经过PCA降维,有效避免判别信息的丢失,在ORL和Yale人脸库上的实验验证算法有效性。     

基于局部重构与全局保持的半监督维数约减算法

针对基于局部与全局保持的半监督维数约减算法(LGSSDR)对部域参数选择比较敏感以及对部域图边权值设定不够准确的问题,提出一种基于局部重构与全局保持的半监督维数约减算法(工RGPSSDR)。该算法通过最小化局部重构误差来确定部域图的边权值,在保持数据集局部结构的同时能够保持其全局结构。在Extended YaleB和 CMU PIE标准人脸库上的实验结果表明LRGPSSDR算法的分类性能要优于其它半监督维数约减算法。     

Max-margin non-negative matrix factorization with flexible spatial constraints based on factor analysis

Non-negative matrix factorization (NMF) is a popular feature encoding method for image understanding due to its non-negative properties in representation, but the learnt basis images are not always local due to the lack of explicit constraints in its objective. Various algebraic or geometric local constraints are hence proposed to shape the behaviour of the original NMF. Such constraints are usually rigid in the sense that they have to be specified beforehand instead of learning from the data. In this paper, we propose a flexible spatial constraint method for NMF learning based on factor analysis. Particularly, to learn the local spatial structure of the images, we apply a series of transformations such as orthogonal rotation and thresholding to the factor loading matrix obtained through factor analysis. Then we map the transformed loading matrix into a Laplacian matrix and incorporate this into a max-margin non-negative matrix factorization framework as a penalty term, aiming to learn a representation space which is non-negative, discriminative and localstructure- preserving. We verify the feasibility and effectiveness of the proposed method on several real world datasets with encouraging results.     

New multiresolution modeling techniques in CAD

To apply wavelet transformation to CAD surface model composed of multiple surface patches, an algorithm called wavelet signal separation to preserve geometric constraints during wavelet transformation is proposed. The algorithm divides the B-spline control points into those associated and those unassociated with the geometric constraints. Through preserving the signal information associated with the constraint control points, the geometric constraints can be automatically preserved after wavelet transformation. This paper also briefly investigates two types of the detail feature propagation technique in wavelet-based multiresolution CAD system. One is detail feature motion. The other is detail feature repetition. Finally, a comprehensive example is presented to illustrate the effects of the combination of those techniques.