aiwiki.page
中文
计算机 / 人工智能 / locally-linear-embedding

局部线性嵌入

局部线性嵌入是一种非线性降维算法,通过保留各数据点由其邻居重构时所用的权重来构建低维坐标。

22 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
降维无监督学习流形学习K近邻算法超参数矩阵(数学)正则化损失函数局部线性嵌…

**局部线性嵌入(Locally Linear Embedding,LLE)**是一种用于降维的无监督学习算法。它将高维观测表示在较低维的空间中,同时近似保留相邻观测之间的局部线性关系。LLE 由 Sam T. Roweis 和 Lawrence K. Saul 于 2000 年提出,是流形学习的基础方法之一。其核心思想是将每个数据点表示为附近点的加权组合,然后寻找一组新坐标,使同一组重构权重在新坐标下仍然有效。

几何原理

许多数据集的测量变量数量多于其独立自由度。例如,从不同视角拍摄的同一物体的图像虽然处于高维像素空间中,其变化却可能仅由少量潜在参数决定。流形学习将这类观测建模为位于观测空间中某个嵌入的低维曲面(即流形)上,或位于其附近。

LLE 假定,足够小的邻域可以用局部线性片来近似,更准确地说,是用仿射片来近似。尽管弯曲流形可能不存在有效的全局线性投影,相邻观测仍然可能通过简单的加权和相互重构。

该算法将问题分为两项任务:

  1. 在原始空间中确定各邻域内的重构关系。
  2. 寻找低维坐标,尽可能保留这些关系。

算法所保留的是重构系数,而不是点对之间的距离本身。因此,LLE 并不显式保留所有欧氏距离、角度或沿流形测量的距离。

数学表述

设数据集包含 nn 个观测,

x1,…,xn∈RD,x_1,\ldots,x_n\in\mathbb{R}^{D},

期望的嵌入维数为 d<Dd<D。输出由以下坐标组成:

y1,…,yn∈Rd.y_1,\ldots,y_n\in\mathbb{R}^{d}.

标准 LLE 包含三个主要阶段。

邻域选择

对于每个观测 xix_i,选择一个邻域 Ni\mathcal{N}_i,通常取欧氏距离下的 kk 个最近邻。这是一项最近邻搜索操作,K近邻算法也使用这项操作,但此处并不是在进行有监督预测。

得到的邻域结构通常是有向的:如果 xjx_j 是 xix_i 的最近邻之一,反过来却不一定成立。

邻域大小 kk 是一个重要的超参数。较小的邻域更适合局部线性近似,但可能不稳定,或连通性不足。较大的邻域能为重构提供更多观测,但可能跨越弯曲区域,或将流形上不同的折叠部分连接起来。

局部重构权重

对于每个点,LLE 寻找使重构误差最小的权重 wijw_{ij}:

min⁡{wij}∥xi−∑j∈Niwijxj∥2,∑j∈Niwij=1.\min_{\{w_{ij}\}} \left\| x_i-\sum_{j\in\mathcal{N}_i}w_{ij}x_j \right\|^2, \qquad \sum_{j\in\mathcal{N}_i}w_{ij}=1.

邻域以外的权重设为零。权重不必非负,因此这是一种仿射重构,而不一定是凸组合。

权重之和为一的约束,使所有点经过相同平移后,重构残差保持不变。未经正则化的重构问题对输入的旋转和均匀缩放也具有不变性,但通常对任意各向异性缩放或一般仿射变换不具有不变性。

计算权重时,先构造局部格拉姆矩阵

(Ci)ab=(xi−xja)T(xi−xjb),(C_i)_{ab} = (x_i-x_{j_a})^{\mathsf T}(x_i-x_{j_b}),

其中 ja,jb∈Nij_a,j_b\in\mathcal{N}_i。若 CiC_i 可逆,则解为

wi=Ci−111TCi−11,w_i= \frac{C_i^{-1}\mathbf{1}} {\mathbf{1}^{\mathsf T}C_i^{-1}\mathbf{1}},

其中 1\mathbf{1} 为全一向量。实际实现通常求解线性方程组,而不显式计算逆矩阵。

局部矩阵可能奇异或病态,尤其是在邻居接近某个低维子空间或 k>Dk>D 时。一种常见的正则化方式是将 CiC_i 替换为

Ci+ϵ tr⁡(Ci)I,C_i+\epsilon\,\operatorname{tr}(C_i)I,

其中 ϵ\epsilon 是一个较小的正系数。对于迹为零的退化邻域,还需要额外处理。

低维坐标

固定权重后,LLE 最小化嵌入空间中的重构误差:

Φ(Y)=∑i=1n∥yi−∑j=1nwijyj∥2.\Phi(Y)= \sum_{i=1}^{n} \left\| y_i-\sum_{j=1}^{n}w_{ij}y_j \right\|^2.

令 WW 为 n×nn\times n 权重矩阵,YY 为以 yiTy_i^{\mathsf T} 为行的 n×dn\times d 矩阵。定义

M=(I−W)T(I−W).M=(I-W)^{\mathsf T}(I-W).

则损失函数变为

Φ(Y)=tr⁡(YTMY).\Phi(Y)=\operatorname{tr}(Y^{\mathsf T}MY).

若不加约束,将所有点的坐标设为相同值即可使误差为零。因此,LLE 施加中心化和归一化约束,例如

YT1=0,YTY=Id.Y^{\mathsf T}\mathbf{1}=0, \qquad Y^{\mathsf T}Y=I_d.

若改用 nIdnI_d 进行归一化,则只会改变整体尺度。

解由对称半正定矩阵 MM 的特征向量得到。由于 WW 的每一行之和均为一,常数向量是对应于零特征值的特征向量。当它是唯一的零模态时,嵌入使用其后 dd 个最小特征值所对应的特征向量。额外的零模态表明存在退化,或数据各部分之间的耦合不足,需要特殊处理。

解释与数学性质

LLE 将局部拟合与全局谱计算结合起来。邻域和权重一旦固定,嵌入阶段就是一个具有全局解的带约束二次数学优化问题。与许多非线性嵌入方法不同,标准 LLE 不需要对输出坐标进行迭代梯度下降。

这并不意味着整个过程不受设计选择的影响。邻域图取决于距离度量、预处理、邻域大小和采样方式。改变这些选择可能显著改变结果。

输出也没有固有的朝向。改变嵌入坐标的符号或对其施加正交变换,不会改变目标函数值。即使多个坐标轴共同张成的子空间定义明确,重特征值仍可能使单个坐标轴不唯一。

重构误差较小本身并不能证明流形已被忠实地恢复。发生扭曲或部分塌缩的构型也可能保留局部重构关系,而且目标函数并不直接要求相距较远的区域在嵌入中保持分离。

计算需求

主要计算阶段包括邻居搜索、局部线性方程组求解和稀疏特征值问题求解。

直接计算所有点对之间的距离大约需要 O(n2D)O(n^2D) 次算术运算。KD树等空间索引在有利条件下能够加速搜索,不过其优势通常随维数增加而减弱。近似最近邻搜索可以降低成本,代价是可能改变邻域结构。

对于每个观测,构造局部格拉姆矩阵的成本约为 O(Dk2)O(Dk^2),采用稠密方法求解局部线性方程组的成本为 O(k3)O(k^3)。对整个数据集而言,这些阶段的成本约为

O(nDk2+nk3).O(nDk^2+nk^3).

权重矩阵最多约有 nknk 个非零元素。虽然显式构造 MM 可能引入更多非零元素,但迭代特征值求解器可以通过以下方式隐式计算其作用:

Mv=(I−W)T((I−W)v).Mv=(I-W)^{\mathsf T}\bigl((I-W)v\bigr).

这样便可使用稀疏矩阵与向量运算,而无须存储稠密的 n×nn\times n 矩阵。特征值求解的成本取决于所需嵌入维数、谱隙、数值容差和求解器。完整的稠密特征分解具有立方量级的时间复杂度,但标准稀疏实现并不需要进行这种分解。

应用

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 的相继出现,推动基于邻域的非线性降维成为机器学习中的一个重要研究领域。

后续工作研究了其几何基础、对采样和正则化的敏感性、样本外扩展,以及其他局部约束。这些发展使原始的单权重向量算法,与围绕局部重构和全局对齐构建的更广泛方法族区分开来。