知识卡片
LLE 先求权重再求坐标
LLE 把降维拆成两个前后依赖的子问题,两次都用到同一组权重,只是”已知”和”未知”互换。
第一步:在原空间求权重 W。 对每个样本 x_i,用欧氏距离找 K 个最近邻,然后解一个带约束的回归:最小化 ‖x_i − Σ_j w_ij x_j‖²,约束 Σ_j w_ij = 1。约束必不可少——否则所有 w 取 0 就是平凡最优解。用拉格朗日乘子法可得闭式解
w_i = Z_i⁻¹ 1 / (1ᵀ Z_i⁻¹ 1)
其中 Z_i 是由近邻差向量构成的局部协方差矩阵,(x_i − x_j)ᵀ(x_i − x_j) 为其元素。这一步只用到局部信息,每个样本独立求解。
第二步:固定 W,求低维坐标 Y。 现在把 w 当作常数,最小化同一形式的损失 ‖y_i − Σ_j w_ij y_j‖²,再加上标准化约束 YᵀY = I(防止解退化成全 0 或任意缩放)。整理后损失可写成 tr(YᵀMY),其中
M = (I − W)ᵀ(I − W)
对 Y 求导得 MY = λY,于是 Y 就是 M 最小的若干特征值对应的特征向量。注意 M 最小的特征值恒为 0,对应特征向量为全 1——它只代表”整体平移”这个自由度,不含任何结构信息,所以实际取第 2 到第 N′+1 个特征向量。
这两步的结构值得留意:第一步是”用邻居表示自己”,第二步是”在新空间里保持同样的表示关系”,中间传递的只有权重矩阵 W。所以 LLE 不关心全局距离,只搬运局部关系——这是它能展开弯曲流形的原因,也是它在采样稀疏时失效的原因。
结构图:
flowchart LR
A[为每个样本找 K 个近邻] --> B[解约束回归得权重 W]
B --> C[构造 M=(I-W)ᵀ(I-W)]
C --> D[求 M 最小的 N'+1 个特征向量]
D --> E[丢弃全 1 向量, 取第 2~N'+1 个]
E --> F[得到低维坐标 Y]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第13章 降维
原书出处 · 1 处
- 第13章 降维 13.4.2 局部线性嵌入过程和原理 · 查看原书依据
一般,M最小的特征值为0,此时对应的特征向量为全1,不能反映数据特征,因此实际情况中往往选择M的第2~N'+1个最小的特征值对应的特征向量