论文题目：Nonlinear Dimensionality Reduction by Locally Linear Embedding
论文来源：http://science.sciencemag.org/

Nonlinear Dimensionality Reduction by Locally Linear Embedding

通过局部线性嵌入减少非线性维数

Sam T. Roweis1 and Lawrence K. Saul2

Abstract

Many areas of science depend on exploratory data analysis and visualization. The need to analyze large amounts of multivariate data raises the fundamental problem of dimensionality reduction: how to discover compact representations of high-dimensional data. Here, we introduce locally linear embedding (LLE), an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs. Unlike clustering methods for local dimensionality reduction, LLE maps its inputs into a single global coordinate system of lower dimensionality, and its optimizations do not involve local minima. By exploiting the local symmetries of linear reconstructions, LLE is able to learn the global structure of nonlinear manifolds, such as those generated by images of faces or documents of text.

摘要

科学的许多领域都依赖于探索性数据分析和可视化。 分析大量多元数据的需求提出了降维的根本问题：如何发现高维数据的紧凑表示。 在这里，我们介绍局部线性嵌入（LLE），这是一种无监督的学习算法，可计算高维输入的低维，邻域保留嵌入。 与用于减少局部维数的聚类方法不同，LLE将其输入映射到较低维的单个全局坐标系中，并且其优化不涉及局部极小值。 通过利用线性重构的局部对称性，LLE能够学习非线性流形的整体结构，例如由脸部图像或文本文档生成的那些。

正文

How do we judge similarity? Our mental representations of the world are formed by processing large numbers of sensory inputs—including, for example, the pixel intensities of images, the power spectra of sounds, and the joint angles of articulated bodies. While complex stimuli of this form can be represented by points in a high-dimensional vector space, they typically have a much more compact description. Coherent structure in the world leads to strong correlations between inputs (such as between neighboring pixels in images), generating observations that lie on or close to a smooth low-dimensional manifold. To compare and classify such observations—in effect, to reason about the world— depends crucially on modeling the nonlinear geometry of these low-dimensional manifolds.
我们如何判断相似性？我们对世界的心理表征是通过处理大量的感官输入而形成的，例如，图像的像素强度、声音的功率谱和关节体的关节角。尽管这种形式的复杂刺激可以由高维向量空间中的点表示，但它们通常具有更为紧凑的描述。 世界上的连贯结构导致输入之间（例如图像中相邻像素之间）的强相关性，从而产生位于平滑低维流形上或附近的观测值。 对这些观察结果进行比较和分类（实际上是为了推理世界），关键在于建模这些低维流形的非线性几何形状。

Scientists interested in exploratory analysis or visualization of multivariate data (1) face a similar problem in dimensionality reduction. The problem, as illustrated in Fig. 1, involves mapping high-dimensional inputs into a low-dimensional “description” space with as many coordinates as observed modes of variability. Previous approaches to this problem, based on multidimensional scaling (MDS) (2), have computed embeddings that attempt to preserve pairwise distances [or generalized disparities (3)] between data points; these distances are measured along straight lines or, in more sophisticated usages of MDS such as Isomap (4), along shortest paths confined to the manifold of observed inputs. Here, we take a different approach, called locally linear embedding (LLE), that eliminates the need to estimate pairwise distances between widely separated data points. Unlike previous methods, LLE recovers global nonlinear structure from locally linear fits.
对多元数据的探索性分析或可视化感兴趣的科学家在降维方面也面临类似的问题。如图1所示，该问题涉及到将高维输入映射到低维的“描述”空间，该空间具有与观察到的可变性模式一样多的坐标。基于多维缩放（MDS）的解决此问题的先前方法，已经计算出试图保留数据点之间的成对距离的嵌入[或广义视差]，这些距离是沿着直线测量的，或者在MDS的更复杂用法（例如Isomap）中，沿着限制在观察到的输入流形上的最短路径测量。 在这里，我们采用了另一种称为局部线性嵌入（LLE）的方法，该方法无需估计广泛分离的数据点之间的成对距离。 与以前的方法不同，LLE从局部线性拟合中恢复全局非线性结构。

The LLE algorithm, summarized in Fig. 2, is based on simple geometric intuitions. Suppose the data consist of N real-valued vectors $\vec{X_{i}}$Xi​​ , each of dimensionality D, sampled from some underlying manifold. Provided there is sufficient data (such that the manifold is well-sampled), we expect each data point and its neighbors to lie on or close to a locally linear patch of the manifold. We characterize the local geometry of these patches by linear coefficients that reconstruct each data point from its neighbors. Reconstruction errors are measured by the cost function
$\varepsilon \left ( W \right )=\sum_{i}^{}\left | \vec{x_{i}}{\rightarrow}- \sum _{j}W_{ij}\vec{x_{j}}\right |^{2}$ε(W)=∑i​∣∣∣​xi​​→−∑j​Wij​xj​​∣∣∣​2 (1)
which adds up the squared distances between all the data points and their reconstructions. The weights $W_{ij}$Wij​ summarize the contribution of the jth data point to the ith reconstruction. To compute the weights $W_{ij}$Wij​, we minimize the cost function subject to two constraints: first, that each data point $\vec{X_{i}}$Xi​​ is reconstructed only from its neighbors (5), enforcing $W_{ij}$Wij​=0 if $\vec{X_{ j}}$Xj​​ does not belong to the set of neighbors of $\vec{X_{i}}$Xi​​； second, that the rows of the weight matrix sum to one: $\sum _{j}W_{ij}=1$∑j​Wij​=1. The optimal weights $W_{ij}$Wij​ subject to these constraints (6) are found by solving a least-squares problem (7).
总结在图2中的LLE算法是基于简单的几何直觉。假设数据由N个从底层流形中采样的实值向量$\vec{X{i}}$Xi组成，每个向量的维数为D。如果有足够的数据（例如流形被很好的采样），我们期望每个数据点及其邻域都位于或接近于流形的局部线性面片上。我们用线性系数来描述这些小块的局部几何特征，这些系数从相邻的数据点重建每个数据点。重建误差用代价函数来度量
$\varepsilon \left ( W \right )=\sum_{i}^{}\left | \vec{x_{i}}{\rightarrow}- \sum _{j}W_{ij}\vec{x_{j}}\right |^{2}$ε(W)=∑i​∣∣∣​xi​​→−∑j​Wij​xj​​∣∣∣​2 (1)
这将所有数据点及其重构之间的平方距离相加。权重$W_ {ij}$Wij​总结了第j个数据点对第i个重构的贡献。为了计算权重$W_ {ij}$Wij​，我们将代价函数最小化，并遵循两个约束：首先，每个数据点$\vec {X_ {i}}$Xi​​仅从其邻居中重建，如果$\vec {X_ {i}}$Xi​​不属于$\vec{X_ {i}}$Xi​​的邻居集合，从而强制执行$W_ {ij}$Wij​ = 0；第二，权重矩阵的行总和为一：$\sum _ {j} W_ {ij} = 1$∑j​Wij​=1。 通过解决最小二乘问题可以找到受这些约束的最佳权重$W_ {ij}$Wij​。

The constrained weights that minimize these reconstruction errors obey an important symmetry: for any particular data point, they are invariant to rotations, rescalings, and translations of that data point and its neighbors. By symmetry, it follows that the reconstruction weights characterize intrinsic geometric properties of each neighborhood, as opposed to properties that depend on a particular frame of reference (8). Note that the invariance to translations is specifically enforced by the sum-to-one constraint on the rows of the weight matrix.
使这些重建误差最小化的约束权重服从一个重要的对称性：对于任何特定的数据点，它们对该数据点及其相邻点的旋转、重定位和平移都是不变性的。通过对称性可以得出，重构权值表征了每个邻域的固有几何特性，而不是依赖于特定参考系的特性。 请注意，平移的不变性是通过权重矩阵的行上的合到一约束专门实施的。

Suppose the data lie on or near a smooth nonlinear manifold of lower dimensionality d<< D. To a good approximation then, there exists a linear mapping— consisting of a translation, rotation, and rescaling—that maps the high-dimensional coordinates of each neighborhood to global internal coordinates on the manifold. By design, the reconstruction weights $W_{ij}$Wij​ reflect intrinsic geometric properties of the data that are invariant to exactly such transformations. We therefore expect their characterization of local geometry in the original data space to be equally valid for local patches on the manifold. In particular, the same weights $W_{ij}$Wij​ that reconstruct the ith data point in D dimensions should also reconstruct its embedded manifold coordinates in d dimensions.
假设数据位于低维d<<D的光滑非线性流形上或其附近。为了获得很好的近似值，就存在一个线性映射-包括平移、旋转和重缩放，将每个邻域的高维坐标映射到流形上的全局内部坐标。通过设计，重构权值 $W_{ij}$Wij​反映了数据内在的几何特性，这些特性对这种转换是不变的。因此，我们期望它们在原始数据空间中的局部几何特征对于流形上的局部小块同样有效。特别地，在D维中重建第i个数据点的相同权重$W_{ij}$Wij​也应该重建其在d维中嵌入的流形坐标。

LLE constructs a neighborhood-preserving mapping based on the above idea. In the final step of the algorithm, each high-dimensional observation $\vec{X_{i}}$Xi​​ is mapped to a low-dimensional vector $\vec{Y_{i}}$Yi​​representing global internal coordinates on the manifold. This is done by choosing d-dimensional coordinates $\vec{Y_{i}}$Yi​​ to minimize the embedding cost function
$\Phi \left ( Y \right )=\sum_{i}^{}\left | \vec{Y_{i}}-\sum_{_{j}}^{} W_{ij}\vec{Y_{j}}\right |^{2}$Φ(Y)=∑i​∣∣∣​Yi​​−∑j​​Wij​Yj​​∣∣∣​2 (2)
This cost function, like the previous one, is based on locally linear reconstruction errors, but here we fix the weights $W_{ij}$Wij​ while optimizing the coordinates $\vec{Y_{i}}$Yi​​. The embedding cost in Eq. 2 defines a quadratic form in the vectors $\vec{Y_{i}}$Yi​​. Subject to constraints that make the problem well-posed, it can be minimized by solving a sparse N X N eigenvalue problem (9), whose bottom d nonzero eigenvectors provide an ordered set of orthogonal coordinates centered on the origin.
基于上述思想，LLE构造了一个保持邻域的映射。在算法的最后一步，每个高维观测值$\vec{X_{i}}$Xi​​被映射到一个低维向量$\vec{Y_{i}}$Yi​​，表示流形上的全局内部坐标。这是通过选择d维坐标$\vec{Y_{i}}$Yi​​来最小化嵌入代价函数来实现的
$\Phi \left ( Y \right )=\sum_{i}^{}\left | \vec{Y_{i}}-\sum_{_{j}}^{} W_{ij}\vec{Y_{j}}\right |^{2}$Φ(Y)=∑i​∣∣∣​Yi​​−∑j​​Wij​Yj​​∣∣∣​2 (2)
与上一个函数一样，此成本函数基于局部线性重构误差，但是在此，我们在优化坐标$\vec {Y_ {i}}$Yi​​的同时修正了权重$W_ {ij}$Wij​。等式2中的嵌入代价在向量$\vec{Y_{i}}$Yi​​中定义了一个二次型。受限于使问题适定的约束条件，可以通过求解稀疏N X N特征值问题来最小化问题，该问题的底部d非零特征向量提供了一组以原点为中心的有序正交坐标。

Implementation of the algorithm is straightforward. In our experiments, data points were reconstructed from their K nearest neighbors, as measured by Euclidean distance or normalized dot products. For such implementations of LLE, the algorithm has only one free parameter: the number of neighbors, K. Once neighbors are chosen, the optimal weights $W_ {ij}$Wij​ and coordinates $\vec{Y_{i}}$Yi​​ are computed by standard methods in linear algebra. The algorithm involves a single pass through the three steps in Fig. 2 and finds global minima of the reconstruction and embedding costs in Eqs. 1 and 2.
该算法的实现很简单。 在我们的实验中，通过欧几里得距离或归一化的点积测量，数据点从它们的K个最近邻点被重建的。对于LLE的此类实现，该算法只有一个*参数：邻点数K。一旦选择了邻点，最优权重$W_ {ij}$Wij​和坐标$\vec {Y_ {i}}$Yi​​可以由线性代数的标准方法计算得出。该算法只需通过图2中的三个步骤，就可以在方程式1和方程式2中找到重构和嵌入代价的全局最小值。

In addition to the example in Fig. 1, for which the true manifold structure was known(10), we also applied LLE to images of faces(11) and vectors of word-document counts(12). Two-dimensional embeddings of faces and words are shown in Figs. 3 and 4. Note how the coordinates of these embedding spaces are related to meaningful attributes, such as the pose and expression of human faces and the semantic associations of words.
除了图1示例中已知的真实流形结构之外，我们还将LLE应用于人脸图像和单词文档计数向量。面部和词语的二维嵌入如图3和图4所示，请注意这些嵌入空间的坐标如何与有意义的属性关联，例如人脸的姿势和表情以及词语的语义关联。

Many popular learning algorithms for nonlinear dimensionality reduction do not share the favorable properties of LLE. Iterative hill-climbing methods for autoencoder neural networks (13, 14), self-organizing maps (15), and latent variable models (16) do not have the same guarantees of global optimality or convergence; they also tend to involve many more free parameters, such as learning rates, convergence criteria, and architectural specifications. Finally, whereas other nonlinear methods rely on deterministic annealing schemes (17) to avoid local minima, the optimizations of LLE are especially
tractable.
许多流行的用于非线性降维的学习算法并不具有LLE的良好特性。 用于自动编码器神经网络，自组织映射和潜变量模型的迭代爬山方法不能保证全局最优性或收敛性。 它们也倾向于包含更多*参数，例如学习率，收敛标准和体系结构规范。 最后，尽管其他非线性方法依靠确定性退火方案来避免局部极小值，但LLE的优化特别容易处理。

LLE scales well with the intrinsic manifold dimensionality, d, and does not require a discretized gridding of the embedding space. As more dimensions are added to the embedding space, the existing ones do not change, so that LLE does not have to be rerun to compute higher dimensional embeddings. Unlike methods such as principal curves and surfaces (18) or additive component models (19), LLE is not limited in practice to manifolds of extremely low dimensionality or codimensionality. Also, the intrinsic value of d can itself be estimated by analyzing a reciprocal cost function, in which reconstruction weights derived from the embedding vectors $\vec {Y_ {i}}$Yi​​ are applied to the data points $\vec {X_ {i}}$Xi​​ .
LLE能很好地利用其固有的流形维数d，且不需要对嵌入空间进行离散网格化。随着嵌入空间的维数增加，现有的维数不会改变，因此LLE不必重新运行来计算更高维数的嵌入。与主曲线和曲面或可加成分模型等方法不同，LLE在实践中并不局限于极低维数或多维度的流形。同样，d本身的内在价值可以通过分析一个倒代价函数来估计，在这个函数中，从嵌入向量$\vec {Y_ {i}}$Yi​​得到的重构权值被应用到数据点$\vec {X_ {i}}$Xi​​上。

LLE illustrates a general principle of manifold learning, elucidated by Martinetz and Schulten (20) and Tenenbaum (4), that over- lapping local neighborhoods—collectively analyzed— can provide information about global geometry. Many virtues of LLE are shared by Tenenbaum’s algorithm, Isomap, which has been successfully applied to similar problems in nonlinear dimensionality reduction. Isomap’s embeddings, however, are optimized to preserve geodesic distances between general pairs of data points, which can only be estimated by computing shortest paths through large sublattices of data. LLE takes a different approach, analyzing local symmetries, linear coefficients, and reconstruction errors instead of global constraints, pairwise distances, and stress functions. It thus avoids the need to solve large dynamic programming problems, and it also tends to accumulate very sparse matrices, whose structure can be exploited for savings in time and space.
LLE由Martinetz、Schulten和Tenenbaum阐明了流形学习的一般原理，即通过共同分析，重叠的局部邻居可以提供关于全局几何的信息。Tenenbaum的算法Isomap具有LLE的许多优点，该算法已成功应用于非线性降维中的类似问题。 但是，Isomap的嵌入已进行了优化，以保留通用数据点对之间的测地距离，这只能通过计算通过大数据子格的最短路径来估算。LLE采用不同的方法，分析局部对称性、线性系数和重构误差，而不是全局约束、成对距离和应力函数。因此，它避免了求解大型动态规划问题的需要，而且它还倾向于积累非常稀疏的矩阵，利用它们的结构可以节省时间和空间。

LLE is likely to be even more useful in combination with other methods in data analysis and statistical learning. For example, a parametric mapping between the observation and embedding spaces could be learned by supervised neural networks (21) whose target values are generated by LLE. LLE can also be generalized to harder settings, such as the case of disjoint data manifolds (22), and specialized to simpler ones, such as the case of time-ordered observations (23).
在数据分析和统计学习中，LLE与其他方法相结合可能会更加有用。例如，观察和嵌入空间之间的参数映射可以通过监督神经网络来学习，其目标值由LLE生成。LLE也可以推广到更困难的设置，例如不相交的数据流形，并专门用于更简单的设置，例如按时间顺序的观测。

Perhaps the greatest potential lies in applying LLE to diverse problems beyond those considered here. Given the broad appeal of traditional methods, such as PCA and MDS, the algorithm should find widespread use in many areas of science.
也许最大的潜力在于将LLE应用于此处未考虑的各种问题。 鉴于PCA和MDS等传统方法的广泛吸引力，该算法应在许多科学领域中得到广泛使用。