Regression reformulations of LLE and LTSA with locally linear transformation

Locally linear embedding (LLE) and local tangent space alignment (LTSA) are two fundamental algorithms in manifold learning. Both LLE and LTSA employ linear methods to achieve their goals but with different motivations and formulations. LLE is developed by locally linear reconstructions in both high- and low-dimensional spaces, while LTSA is developed with the combinations of tangent space projections and locally linear alignments. This paper gives the regression reformulations of the LLE and LTSA algorithms in terms of locally linear transformations. The reformulations can help us to bridge them together, with which both of them can be addressed into a unified framework. Under this framework, the connections and differences between LLE and LTSA are explained. Illuminated by the connections and differences, an improved LLE algorithm is presented in this paper. Our algorithm learns the manifold in way of LLE but can significantly improve the performance. Experiments are conducted to illustrate this fact.     

Motion learning-based framework for unarticulated shape animation

This paper presents a framework for generating animation sequences while maintaining desirable physical properties in a deformable shape. The framework consists of three important processes. Firstly, considering the given key pose configurations in the form of unarticulated meshes in high dimensional space, we cast our motion in low dimensional space using the unsupervised learning method of locally linear embedding (LLE). Corresponding to each point in LLE space, we can reconstruct the in-between pose using generalized radial basis functions. Next we create a map in the LLE space of the values for the different physical properties of the mesh, for example area, volume, etc. Finally, a probability distribution function in LLE space helps us rapidly choose the required number of in-between poses with desired physical properties. A significant advantage of this framework is that it relieves the animator the tedium of having to carefully provide key poses to suit the interpolant.     

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.     

保持局部邻域关系的增量Hessian LLE算法

Hessian LLE算法是一种经典的流形学习算法,但该方法是以批处理的方式进行的,当新的数据点加入时,必须重新运行整个算法,计算所有数据点低维嵌入,原来的运算结果被全部丢弃。鉴于此,提出了一种保持局部邻域关系的增量Hessian LLE(LIHLLE)算法,该方法通过保证流形新增样本点在原空间和嵌入空间局部邻域的线性关系不变,用其已有邻域点的低维坐标线性表示新增样本点,来得到新增点的低维嵌入,实现增量学习。在Swiss roll withhole和frey_rawface数据集上的实验表明,该方法简便、有效可行。     

Reliability analysis of distributed systems based on a fastreliability algorithm

The reliability of a distributed processing system (DPS) can be expressed by the analysis of distributed program reliability (DPR) and distributed system reliability (DSR). One of the good approaches to formulate these reliability performance indexes is to generate all disjoint file spanning trees (FSTs) in the DPS graph such that the DPR and DSR can be expressed by the probability that at least one of these FSTs is working. In the paper, a unified algorithm to efficiently generate disjoint FSTs by cutting different links is presented, and the DPR and DSR are computed based on a simple and consistent union operation on the probability space of the FSTs. The DPS reliability related problems are also discussed. For speeding up the reliability evaluation, nodes merged, series, and parallel reduction concepts are incorporated in the algorithm. Based on the comparison of number of subgraphs (or FSTs) generated by the proposed algorithm and by existing evaluation algorithms, it is concluded that the proposed algorithm is much more economic in terms of time and space than the existing algorithms     

一种在源数据稀疏情况下的数据降维算法

流形学习方法是根据流形的定义提出的一种非线性数据降维方法,主要思想是发现嵌入在高维数据空间的低维光滑流形。从分析基于流形学习理论的局部线性嵌入算法入手,针对传统的局部线性嵌入算法在源数据稀疏时会失效的缺点,提出了基于局部线性逼近思想的流形学习算法,并在S-曲线上采样测试取得良好降维效果。     

Guided Locally Linear Embedding

Nonlinear dimensionality reduction is the problem of retrieving a low-dimensional representation of a manifold that is embedded in a high-dimensional observation space. Locally Linear Embedding (LLE), a prominent dimensionality reduction technique is an unsupervised algorithm; as such, it is not possible to guide it toward modes of variability that may be of particular interest. This paper proposes a supervised variation of LLE. Similar to LLE, it retrieves a low-dimensional global coordinate system that faithfully represents the embedded manifold. Unlike LLE, however, it produces an embedding in which predefined modes of variation are preserved. This can improve several supervised learning tasks including pattern recognition, regression, and data visualization.     

流形距离与压缩感知核稀疏投影的局部线性嵌入算法

流形学习算法的目的是发现嵌入在高维数据空间中的低维表示,现有的流形学习算法对邻域参数k和噪声比较敏感。针对此问题,文中提出一种流形距离与压缩感知核稀疏投影的局部线性嵌入算法,其核心思想是集成局部线性嵌入算法对高维流形结构数据的降维有效性与压缩感知核稀疏投影的强鉴别性,以实现高效有降噪流形学习。首先,在选择各样本点的近邻域时,采用流形距离代替欧氏距离度量数据间相似度的方法,创建能够正确反映流形内部结构的邻域图,解决以欧氏距离作为相似性度量时对邻域参数的敏感。其次,利用压缩感知核稀疏投影作为从高维观测空间到低维嵌入空间的映射,增强算法的鉴别性。最后,利用Matlab工具对实验数据集进行仿真,进一步验证所提算法的有效性。     

A new least-squares approximation of affine mappings for sweep algorithms

This paper presents a new algorithm to generate hexahedral meshes in extrusion geometries. Several algorithms have been devised to generate hexahedral meshes by projecting the cap surfaces along a sweep path. In all of these algorithms the crucial step is the placement of the inner layer of nodes. That is, the projection of the source surface mesh along the sweep path. From the computational point of view, sweep methods based on a least-squares approximation of an affine mapping are the fastest alternative to compute these projections. Several functionals have been introduced to perform the least-squares approximation. However, for very simple and typical geometrical configurations they may generate low-quality projected meshes. For instance, they may induce skewness and flattening effects on the projected discretizations. In addition, for these configurations the minimization of these functionals may lead to a set of normal equations with singular system matrix. In this work we analyze previously defined functionals. Based on this analysis we propose a new functional and show that its minimization overcomes these drawbacks. Finally, we present several examples to assess the properties of the proposed functional.     

基于放大因子和延伸方向研究流形学习算法

流形学习是一种新的非监督学习方法,可以有效地发现高维非线性数据集的内在维数和进行维数约简,近年来越来越受到机器学习和认知科学领域研究者的重视．虽然目前已经出现了很多有效的流形学习算法,如等度规映射（ISOMAP）、局部线性嵌套（Locally Linear Embedding,LLE）等,然而,对观测空间的高维数据与降维后的低维数据之间的定量关系,尚难以直观地进行分析．这一方面不利于对数据内在规律的深入探察,一方面也不利于对不同流形学习算法的降维效果进行直观比较．文中提出了一种方法,可以从放大因子和延伸方向这两个方面显示出观测空间的高维数据与降维后的低维数据之间的联系;比较了两种著名的流形学习算法（ISOMAP和LLE）的性能,得出了一些有意义的结论;提出了相应的算法从而实现了以上理论．对几组数据的实验表明了研究的有效性和意义．     

Phoneme recognition using an adaptive supervised manifold learning algorithm

To effectively handle speech data lying on a nonlinear manifold embedded in a high-dimensional acoustic space, in this paper, an adaptive supervised manifold learning algorithm based on locally linear embedding (LLE) for nonlinear dimensionality reduction is proposed to extract the low-dimensional embedded data representations for phoneme recognition. The proposed method aims to make the interclass dissimilarity maximized, while the intraclass dissimilarity minimized in order to promote the discriminating power and generalization ability of the low-dimensional embedded data representations. The performance of the proposed method is compared with five well-known dimensionality reduction methods, i.e., principal component analysis, linear discriminant analysis, isometric mapping (Isomap), LLE as well as the original supervised LLE. Experimental results on three benchmarking speech databases, i.e., the Deterding database, the DARPA TIMIT database, and the ISOLET E-set database, demonstrate that the proposed method obtains promising performance on the phoneme recognition task, outperforming the other used methods.     

基于密度刻画的降维算法

针对LLE算法在数据密度变化较大时很难降维的问题,提出一种基于密度刻画的降维算法。采用cam分布寻找数据点的近邻,并在低维局部重建时对数据点加入密度信息。对手写体数字图像进行字符特征的降维,再对降维后的特征进行分类识别。实验结果表明,该方法能区分字符,具有较好的识别率,能够发现高维空间的低维嵌入流形。     

一种改进的局部线性嵌入算法

局部线性嵌入算法(Local Linear Embedding,简称LLE)是一种非线性流形学习算法,能有效地学习出高维采样数据的低维嵌入坐标,但也存在一些不足,如不能处理稀疏的样本数据.针对这些缺点,提出了一种基于局部映射的线性嵌入算法(Local Project Linear Embedding,简称LPLE).通过假定目标空间的整体嵌入函数,重新构造样本点的局部邻域特征向量,最后将问题归结为损失矩阵的特征向量问题从而构造出目标空间的全局坐标.LPLE算法解决了传统LLE算法在源数据稀疏情况下的不能有效进行降维的问题,这也是其他传统的流形学习算法没有解决的.通过实验说明了LPLE算法研究的有效性和意义.     

基于局部线性嵌入算法的汉语数字语音识别

语音信号转换到频域后维数较高,流行学习方法可以自主发现高维数据中潜在低维结构的规律性,提出采用流形学习的方法对高维数据降维来进行汉语数字语音识别。采用流形学习中的局部线性嵌入算法提取语音频域上高维数据的低维流形结构特征,再将低维数据输入动态时间规整识别器进行识别。仿真实验结果表明,采用局部线性嵌入算法的汉语数字语音识别相较于常用声学特征MFCC维数要少,识别率提高了1.2%,有效提高了识别速度。     

Explicit cylindrical maps for general tubular shapes

A solid cylindrical parameterization is a volumetric map between a tubular shape and a right cylinder embedded in the polar coordinate reference system. This paper introduces a novel approach to derive smooth (i.e., harmonic) cylindrical parameterizations for solids with arbitrary topology. Differently from previous approaches our mappings are both fully explicit and bi-directional, meaning that the three polar coordinates are encoded for both internal and boundary points, and that for any point within the solid we can efficiently move from the object space to the parameter space and vice-versa. To represent the discrete mapping, we calculate a tetrahedral mesh that conforms with the solid’s boundary and accounts for the periodic and singular structure of the parametric domain. To deal with arbitrary topologies, we introduce a novel approach to exhaustively partition the solid into a set of tubular parts based on a curve-skeleton. Such a skeleton can be either computed by an algorithm or provided by the user. Being fully explicit, our mappings can be readily exploited by off-the-shelf algorithms (e.g., for iso-contouring). Furthermore, when the input shape is made of tubular parts, our method produces low-distortion parameterizations whose iso-surfaces fairly follow the geometry in a natural way. We show how to exploit this characteristic to produce high-quality hexahedral and shell meshes.     

Least-squares approximation of affine mappings for sweep mesh generation: functional analysis and applications

Sweep methods are one of the most robust techniques to generate hexahedral meshes in extrusion volumes. The main issue in sweep algorithms is the projection of cap surface meshes along the sweep path. The most competitive technique to determine this projection is to find a least-squares approximation of an affine mapping. Several functional formulations have been defined to carry out this least-squares approximation. However, these functionals generate unacceptable meshes for several common geometries in CAD models. In this paper we present a new comparative analysis between these classical functional formulations and a new functional presented by the authors. In particular, we prove under which conditions the minimization of the analyzed functionals leads to a full rank linear system. Moreover, we also prove the equivalences between these formulations. These allow us to point out the advantages of the proposed functional. Finally, from this analysis we outline an automatic algorithm to compute the nodes location in the inner layers.     

Finite element mesh deformation with the skeleton-section template

To develop fast finite element (FE) adaptation methods for simulation-driven design optimization, we propose a radial basis functions (RBF) method with a skeleton-section template to globally and locally deform FE meshes of thin-walled beam structures.The skeleton-section template is automatically formulated from the input mesh and serves as a hierarchical parameterization for the FE meshes. With this hierarchical parameterization, both the global and the local geometries of a thin-walled beam can be processed in the same framework, which is of importance for designing engineering components. The curve skeleton of the mesh is constructed with Voronoi decomposition, while the cross-sections are extracted from the mesh based on the curve skeleton.The RBF method is employed to locally and globally deform the mesh model with the cross-sections and the skeleton, respectively. The RBF method solves the spatial deformation field given prescribed deformations at the cross-sections. At the local scale, the user modifies the cross-sections to deform a region of the surface mesh. At the global level, the skeleton is manipulated and its deformation is transferred to all cross-sections to induce the mesh deformation.In order to handle curved mesh models and attain flexible local deformations, the input mesh is embedded into its skeleton frame field using an anisotropic distance metric. In this way, even strip-like features along arbitrary directions can be created on the mesh model using only a few cross-sections as the deformation handles. In addition, form features can be rigidly preserved at both deformation levels.Numerical examples demonstrate that intuitive and qualified FE mesh deformations can be obtained with manipulation of the skeleton-section template.     

STL rapid prototyping bio-CAD model for CT medical image segmentation

This paper presents a simple process to construct 3D rapid prototyping (RP) physical models for computer tomography (CT) medical images segmentation. The use of stereolithography (STL) triangular meshes as a basis for RP construction facilitates the simplification of the process of converting CT images to an RP model. This is achieved by constructing the STL triangular meshes directly from data points without having to draw the curve model first. The grey prediction algorithm is used to sort contour point data in each layer of the medical image. The contour difference detection operation is used to sequence the points for each layer. The 3D STL meshes are then constructed by this proposed layer-by-layer sequence meshes algorithm to build the STL file. Once this STL file is saved, a 3D physical model of the medical image can be fabricated by RP manufacturing, and its virtual reality model can also be presented for visualization. CT images of a human skull and femur bone were used as the case studies for the construction of the 3D solid model with medical images. The STL models generated using this new methodology were compared to commercial computer-aided design (CAD) models. The results of this comparative analysis show that this new methodology is statistically comparable to that of the CAD software. The results of this research are therefore clinically reliable in reconstructing 3D bio-CAD models for CT medical images.     

Efficiently computing exact geodesic loops within finite steps

Closed geodesics, or geodesic loops, are crucial to the study of differential topology and differential geometry. Although the existence and properties of closed geodesics on smooth surfaces have been widely studied in mathematics community, relatively little progress has been made on how to compute them on polygonal surfaces. Most existing algorithms simply consider the mesh as a graph and so the resultant loops are restricted only on mesh edges, which are far from the actual geodesics. This paper is the first to prove the existence and uniqueness of geodesic loop restricted on a closed face sequence; it contributes also with an efficient algorithm to iteratively evolve an initial closed path on a given mesh into an exact geodesic loop within finite steps. Our proposed algorithm takes only an O(k) space complexity and an O(mk) time complexity (experimentally), where m is the number of vertices in the region bounded by the initial loop and the resultant geodesic loop, and k is the average number of edges in the edge sequences that the evolving loop passes through. In contrast to the existing geodesic curvature flow methods which compute an approximate geodesic loop within a predefined threshold, our method is exact and can apply directly to triangular meshes without needing to solve any differential equation with a numerical solver; it can run at interactive speed, e.g., in the order of milliseconds, for a mesh with around 50K vertices, and hence, significantly outperforms existing algorithms. Actually, our algorithm could run at interactive speed even for larger meshes. Besides the complexity of the input mesh, the geometric shape could also affect the number of evolving steps, i.e., the performance. We motivate our algorithm with an interactive shape segmentation example shown later in the paper.