**局部线性嵌入(Locally Linear Embedding,LLE)**是一种用于降维的无监督学习算法。它将高维观测表示在较低维的空间中,同时近似保留相邻观测之间的局部线性关系。LLE 由 Sam T. Roweis 和 Lawrence K. Saul 于 2000 年提出,是流形学习的基础方法之一。其核心思想是将每个数据点表示为附近点的加权组合,然后寻找一组新坐标,使同一组重构权重在新坐标下仍然有效。
几何原理
许多数据集的测量变量数量多于其独立自由度。例如,从不同视角拍摄的同一物体的图像虽然处于高维像素空间中,其变化却可能仅由少量潜在参数决定。流形学习将这类观测建模为位于观测空间中某个嵌入的低维曲面(即流形)上,或位于其附近。
LLE 假定,足够小的邻域可以用局部线性片来近似,更准确地说,是用仿射片来近似。尽管弯曲流形可能不存在有效的全局线性投影,相邻观测仍然可能通过简单的加权和相互重构。
该算法将问题分为两项任务:
- 在原始空间中确定各邻域内的重构关系。
- 寻找低维坐标,尽可能保留这些关系。
算法所保留的是重构系数,而不是点对之间的距离本身。因此,LLE 并不显式保留所有欧氏距离、角度或沿流形测量的距离。
数学表述
设数据集包含 个观测,
期望的嵌入维数为 。输出由以下坐标组成:
标准 LLE 包含三个主要阶段。
邻域选择
对于每个观测 ,选择一个邻域 ,通常取欧氏距离下的 个最近邻。这是一项最近邻搜索操作,K近邻算法也使用这项操作,但此处并不是在进行有监督预测。
得到的邻域结构通常是有向的:如果 是 的最近邻之一,反过来却不一定成立。
邻域大小 是一个重要的超参数。较小的邻域更适合局部线性近似,但可能不稳定,或连通性不足。较大的邻域能为重构提供更多观测,但可能跨越弯曲区域,或将流形上不同的折叠部分连接起来。
局部重构权重
对于每个点,LLE 寻找使重构误差最小的权重 :
邻域以外的权重设为零。权重不必非负,因此这是一种仿射重构,而不一定是凸组合。
权重之和为一的约束,使所有点经过相同平移后,重构残差保持不变。未经正则化的重构问题对输入的旋转和均匀缩放也具有不变性,但通常对任意各向异性缩放或一般仿射变换不具有不变性。
计算权重时,先构造局部格拉姆矩阵
其中 。若 可逆,则解为
其中 为全一向量。实际实现通常求解线性方程组,而不显式计算逆矩阵。
局部矩阵可能奇异或病态,尤其是在邻居接近某个低维子空间或 时。一种常见的正则化方式是将 替换为
其中 是一个较小的正系数。对于迹为零的退化邻域,还需要额外处理。
低维坐标
固定权重后,LLE 最小化嵌入空间中的重构误差:
令 为 权重矩阵, 为以 为行的 矩阵。定义
则损失函数变为
若不加约束,将所有点的坐标设为相同值即可使误差为零。因此,LLE 施加中心化和归一化约束,例如
若改用 进行归一化,则只会改变整体尺度。
解由对称半正定矩阵 的特征向量得到。由于 的每一行之和均为一,常数向量是对应于零特征值的特征向量。当它是唯一的零模态时,嵌入使用其后 个最小特征值所对应的特征向量。额外的零模态表明存在退化,或数据各部分之间的耦合不足,需要特殊处理。
解释与数学性质
LLE 将局部拟合与全局谱计算结合起来。邻域和权重一旦固定,嵌入阶段就是一个具有全局解的带约束二次数学优化问题。与许多非线性嵌入方法不同,标准 LLE 不需要对输出坐标进行迭代梯度下降。
这并不意味着整个过程不受设计选择的影响。邻域图取决于距离度量、预处理、邻域大小和采样方式。改变这些选择可能显著改变结果。
输出也没有固有的朝向。改变嵌入坐标的符号或对其施加正交变换,不会改变目标函数值。即使多个坐标轴共同张成的子空间定义明确,重特征值仍可能使单个坐标轴不唯一。
重构误差较小本身并不能证明流形已被忠实地恢复。发生扭曲或部分塌缩的构型也可能保留局部重构关系,而且目标函数并不直接要求相距较远的区域在嵌入中保持分离。
计算需求
主要计算阶段包括邻居搜索、局部线性方程组求解和稀疏特征值问题求解。
直接计算所有点对之间的距离大约需要 次算术运算。KD树等空间索引在有利条件下能够加速搜索,不过其优势通常随维数增加而减弱。近似最近邻搜索可以降低成本,代价是可能改变邻域结构。
对于每个观测,构造局部格拉姆矩阵的成本约为 ,采用稠密方法求解局部线性方程组的成本为 。对整个数据集而言,这些阶段的成本约为
权重矩阵最多约有 个非零元素。虽然显式构造 可能引入更多非零元素,但迭代特征值求解器可以通过以下方式隐式计算其作用:
这样便可使用稀疏矩阵与向量运算,而无须存储稠密的 矩阵。特征值求解的成本取决于所需嵌入维数、谱隙、数值容差和求解器。完整的稠密特征分解具有立方量级的时间复杂度,但标准稀疏实现并不需要进行这种分解。
应用
LLE 用于数据可视化、探索性分析和特征提取。典型应用涉及那些被认为随少量连续因素变化的观测,包括图像集合、运动测量数据和其他高维传感器数据。
其低维坐标可以作为聚类或预测模型的输入。例如,在计算机视觉中,相邻图像可能反映姿态或外观的微小变化。LLE 有时能够在不需要标签的情况下揭示这些变化。
得到的坐标并不天然对应可解释的物理变量。可视化中的分离并不能确立类别结构,而表面上呈现的簇也可能取决于邻域图和嵌入维数。
局限性
邻域准确性与预处理
LLE 高度依赖能否识别真正的局部邻居。当特征采用不同单位、无关维度占主导地位,或观测中包含大量噪声时,欧氏距离可能产生误导。因此,特征缩放不仅会改变数值条件,还可能改变算法试图保留的几何结构。
如果一个邻域跨越流形上空间位置相近的不同折叠部分,就会建立错误连接。邻域过小则可能无法使样本充分连通。非均匀采样使这种权衡尤为困难。
噪声与权重不稳定
相邻点之间近似线性相关,可能使局部重构权重不稳定。即使观测点仅发生轻微移动,噪声也可能显著改变这些权重。正则化能够改善数值稳定性,但也会改变被保留的关系。
较大的正权重和负权重可能使重构对扰动敏感。基本算法并不明确保证对异常值的鲁棒性。
全局几何与拓扑
局部线性近似并不能保证得到全局上忠实的嵌入。边界、稀疏区域、孔洞、不连通分量,以及在所选输出维数下无法无重叠表示的流形,都可能使结果变得复杂。
即使邻域结构连通,也未必能产生唯一或有意义的低维构型。因此,连通性不足以作为判断嵌入质量的标准。
新观测
标准 LLE 为参与构建嵌入的观测生成坐标,并不直接学习从输入向量到输出向量的全局映射。一种扩展方法用附近的训练点重构新观测,再将这些权重应用于训练点已有的嵌入坐标。这种样本外插值是一个额外过程,并非对原始嵌入重新进行完整优化,而且在采样区域以外可能不可靠。
在预测流程中使用 LLE 时,必须区分其拟合过程与在测试集上的评估。若将训练观测与评估观测合在一起构建嵌入,评估输入就会影响所学表示,使实验不再属于严格的归纳式设定。
相关方法与变体
**主成分分析(PCA)**寻找使保留方差最大的全局线性子空间。相比之下,LLE 根据局部重构关系构建通常为非线性的表示。PCA 可为新观测提供直接的线性投影,标准 LLE 则不能。
**等距映射(Isomap)**估计沿邻域图的距离,并力求在低维表示中保留这些距离。LLE 不估计所有点对之间的流形距离,而是关注邻域重构系数。
**拉普拉斯特征映射**也使用邻域图并通过谱方法求解,但其目标函数惩罚强连接点之间的分离,而不是保留仿射重构权重。
**海森局部线性嵌入(Hessian LLE)**利用局部切空间坐标估计和基于海森矩阵的二次型来确定嵌入坐标。**改进局部线性嵌入(Modified LLE)**使用多个局部权重向量,处理与局部重构相关的不稳定性。**局部切空间对齐(Local Tangent Space Alignment)**估计局部切空间坐标,并在全局范围内将其对齐;它是一种相关方法,而不是原始 LLE 过程。
**自编码器**通过参数化模型(通常是神经网络)学习编码和解码函数。它们能够为新输入提供显式映射,但采用不同的目标函数和优化过程。
历史发展
Roweis 和 Saul 在 2000 年发表于《科学》的论文《通过局部线性嵌入实现非线性降维》(“Nonlinear Dimensionality Reduction by Locally Linear Embedding”)中提出了 LLE。它与 Isomap 的相继出现,推动基于邻域的非线性降维成为机器学习中的一个重要研究领域。
后续工作研究了其几何基础、对采样和正则化的敏感性、样本外扩展,以及其他局部约束。这些发展使原始的单权重向量算法,与围绕局部重构和全局对齐构建的更广泛方法族区分开来。