Search

Active learning algorithms aim at selecting important samples to label for subsequent machine learning tasks. Many active learning algorithms make use of the reproducing kernel Hilbert space (RKHS) induced by a Gaussian radial basis function (RBF) kernel and leverage the geometrical structure of the data for query-sample selection. Parameters for the kernel function and the k -nearest-neighborhood graph must be properly set beforehand. As a tool exploring the structure of data, active learning algorithms with automatic tuning of those parameters are desirable. In this paper, local linear embedding (LLE) with convex constraints on neighbor weights is used to learn the geometrical structure of the data in the RKHS induced by a Gaussian RBF kernel. Automatic tuning of the kernel parameter is based on the assumption that the geometrical structure of the data in the RKHS is sparse and local. With the Markov matrix established based on the learned LLE weight matrix, the total expected path-length of the random walks from all samples to selected samples is proposed to be a criterion for query-sample selection. A greedy algorithm having a guaranteed solution bound is developed to select query samples and a two-phase scheme is also proposed for scaling the proposed active learning algorithm. Experimental results on data sets including hundreds to tens of thousands of samples have shown the feasibility of the proposed approach. [ABSTRACT FROM AUTHOR]

• Linear approximation of LLE. Our model takes the linear mapping into consideration, making it more suitable to handle both linear and non-linear data. Also, outliers can be well dealt with during the linear projection procedure. • Global and local structure. Instead of only consider the local geometry properties, we also consider the global data point relationship to preserve the intrinsic structure. And our model shows robustness to noise and uneven distribution data. • Adaptive neighbor selection. In our model, weight between data and neighbors are updated in order to adjust each data into its optimal neighborhood. Using adaptive neighbor strategy, manifold structure can be kept and then structure learning and feature extraction could be accomplished simultaneously. Dimensionality reduction is one of the most important techniques in the field of data mining. It embeds high-dimensional data into a low-dimensional vector space while keeping the main information as much as possible. Locally Linear Embedding (LLE) as a typical manifold learning algorithm computes neighborhood preserving embeddings of high-dimensional inputs. Based on the thought of LLE, we propose a novel unsupervised dimensionality reduction model called Local Linear Embedding with Adaptive Neighbors (LLEAN). To achieve a desirable dimensionality reduction result, we impose adaptive neighbor strategy and adopt a projection matrix to project data into an optimal subspace. The relationship between every pair-wise data is investigated to help reveal the data structure. Augmented Lagrangian Multiplier (ALM) is devised in optimization procedure to effectively solve the proposed objective function. Comprehensive experiments on toy data and benchmark datasets have been done and the results show that LLEAN outperforms other state-of-the-art dimensionality reduction methods. [ABSTRACT FROM AUTHOR]

Abstract: At present, dictionary based models have been widely used in image classification. The image features are approximated as a linear combination of bases selected from the dictionary in a sparse space, resulting in compact patterns. The features applied to image classification usually reside on low dimensional manifolds embedded in a high dimensional ambient space; traditional sparse coding algorithm, however, does not consider this topological structure. It can be characterized naturally by linear coefficients that reconstruct each data point from its neighbors. One of the central issues here is how to determine the neighbors and learn the coefficients. In this paper, the geometrical structures are encoded in two situations. In simple cases when data points distribute on a single manifold, it is explicitly modeled by locally linear embedding algorithm combined with k-nearest neighbors. Nevertheless, in real-world scenarios, complex data points often lie on multiple manifolds. Sparse representation algorithm combined with k-nearest neighbors is instead utilized to construct the topological structures, because it is capable of approximating the data point by selecting its homogenous neighbors adaptively to guarantee the smoothness of each manifold. After obtaining the local fitting relationship, these two topological structures are then embedded into sparse coding algorithm as regularization terms to formulate the corresponding objective functions of dictionary learning on single manifold (DLSM) and dictionary learning on multiple manifolds (DLMM), respectively. Upon this, a coordinate descent scheme is proposed to solve the unified optimization problems. Experimental results on several benchmark data sets, such as Caltech-256, Caltech-101, Scene 15, and UIUC-Sports, show that our proposed algorithms equal or outperform other state-of-the-art image classification algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, two significant weaknesses of locally linear embedding (LLE) applied to computer vision are addressed: “intrinsic dimension” and “eigenvector meanings”. “Topological embedding” and “multi-resolution nonlinearity capture” are introduced based on mathematical analysis of topological manifolds and LLE. The manifold topological analysis (MTA) method is described and is based on “topological embedding”. MTA is a more robust method to determine the “intrinsic dimension” of a manifold with typical topology, which is important for tracking and perception understanding. The manifold multi-resolution analysis (MMA) method is based on “multi-resolution nonlinearity capture”. MMA defines LLE eigenvectors as features for pattern recognition and dimension reduction. Both MTA and MMA are proved mathematically, and several examples are provided. Applications in 3D object recognition and 3D object viewpoint space partitioning are also described. [Copyright &y& Elsevier]

Abstract: Neighborhood preserving embedding (NPE) is a linear approximation to the locally linear embedding algorithm which can preserve the local neighborhood structure on the data manifold. However, in typical face recognition where the number of data samples is smaller than the dimension of data space, it is difficult to directly apply NPE to high dimensional matrices because of computational complexity. Moreover, in such case, NPE often suffers from the singularity problem of eigenmatrix, which makes the direct implementation of the NPE algorithm almost impossible. In practice, principal component analysis or singular value decomposition is applied as a preprocessing step to attack these problems. Nevertheless, this strategy may discard dimensions that contain important discriminative information and the eigensystem computation of NPE could be unstable. Towards a practical dimensionality reduction method for face data, we develop a new scheme in this paper, namely, the complete neighborhood preserving embedding (CNPE). CNPE transforms the singular generalized eigensystem computation of NPE into two eigenvalue decomposition problems. Moreover, a feasible and effective procedure is proposed to alleviate the computational burden of high dimensional matrix for typical face image data. Experimental results on the ORL face database and the Yale face database show that the proposed CNPE algorithm achieves better performance than other feature extraction methods, such as Eigenfaces, Fisherfaces and NPE, etc. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: The low-dimensional representation of high-dimensional data and the concise description of its intrinsic structures are central problems in data analysis. In this paper, an unsupervised learning algorithm called weighted locally linear embedding (WLLE) is presented to discover the intrinsic structures of data, such as neighborhood relationships, global distributions and clustering. The WLLE algorithm is motivated by locally linear embedding (LLE) algorithm and cam weighted distance, a novel distance measure which usually gives a deflective cam contours for equal-distance contour in classification for an improved classification. It is a major advantage of the WLLE to optimize the process of intrinsic structure discovery by avoiding unreasonable neighbor searching, and at the same time, allow the discovery adapt to the characteristics of input data set. Furthermore, the algorithm discovers intrinsic structures which can be used to compute manipulative embedding for potential classification and recognition purposes, thus can work as a feature extraction algorithm. Simulation studies demonstrate that the WLLE can give better results in manifold learning and dimension reduction than LLE and neighborhood linear embedding (NLE), and is more robust to parameter changes. Experiments on face images data sets and comparison to other famous face recognition methods such as kernel-PCA (KPCA) and kernel direct discriminant analysis (KDDA) are done to show the potential of WLLE for real world problem. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new 3D triangular mesh parameterization method that is computationally efficient and yields minimized distance errors. The method has four steps. Firstly, multidimensional scaling (MDS) is used to flatten each submesh consisting of one vertex and its direct neighbours on the 3D triangular mesh. Secondly, an optimal method is used to compute the linear reconstructing weights of each vertex with respect to its neighbours. Thirdly, a spectral decomposition method is used to obtain initial 2D parameterization coordinates. Fourthly, the initial coordinates are rotated and scaled to minimize the distance errors. It is demonstrated that this method can be used for texture mapping. Analyses and examples show the effectiveness of this parameterization method compared with alternatives. [Copyright &y& Elsevier]

Abstract: In the past few years, some nonlinear dimensionality reduction (NLDR) or nonlinear manifold learning methods have aroused a great deal of interest in the machine learning community. These methods are promising in that they can automatically discover the low-dimensional nonlinear manifold in a high-dimensional data space and then embed the data points into a low-dimensional embedding space, using tractable linear algebraic techniques that are easy to implement and are not prone to local minima. Despite their appealing properties, these NLDR methods are not robust against outliers in the data, yet so far very little has been done to address the robustness problem. In this paper, we address this problem in the context of an NLDR method called locally linear embedding (LLE). Based on robust estimation techniques, we propose an approach to make LLE more robust. We refer to this approach as robust locally linear embedding (RLLE). We also present several specific methods for realizing this general RLLE approach. Experimental results on both synthetic and real-world data show that RLLE is very robust against outliers. [Copyright &y& Elsevier]

Locally linear embedding (LLE) is a nonlinear dimensionality reduction method proposed recently. It can reveal the intrinsic distribution of data, which cannot be provided by classical linear dimensionality reduction methods. The application of LLE, however, is limited because of its lack of a parametric mapping between the observation and the low-dimensional output. And the large data set to be reduced is necessary. In this paper, we propose methods to establish the process of mapping from low-dimensional embedded space to high-dimensional space for LLE and validate their efficiency with the application of reconstruction of multi-pose face images. Furthermore, we propose that the high-dimensional structure of multi-pose face images is similar for the same kind of pose change mode of different persons. So given the structure information of data distribution which is obtained by leaning large numbers of multi-pose images in a training set, the support vector regression (SVR) method of statistical learning theory is used to learn the high-dimensional structure of someone based on small sets. The detailed learning method and algorithm are given and applied to reconstruct and synthesize face images in small set cases. The experiments prove that our idea and method is correct. [Copyright &y& Elsevier]