一、它在算相邻点的预测差

先看两个定义。 图的邻接矩阵 W 里，W 的第 i 行第 j 列是点 i 和点 j 之间的边权，没连边就是 0。 度矩阵 D 是对角阵，对角线上放每一行的和。 拉普拉斯矩阵 L 等于 D 减 W。 现在把预测值 f 当成定义在点上的函数，算 f 转置乘 L 乘 f：

f' L f = 二分之一 * 求和(所有 i, j) W[i][j] * ( f[i] - f[j] ) 的平方

这个等式可以直接验证。 取 f 等于「用真方向算出来的预测值」，在 8 近邻图上算两遍：

二、三种读法

同一个式子有三种理解方式，各有各的用处。 读法一：扩散。 把有标签的点看成热源，标签值沿着图的边走，越走越淡。 拉普拉斯正则化等价于让这个扩散过程跑到平衡——没有标签的点最终拿到的是邻居的加权平均。 这个读法最直观，也最接近「半监督」三个字给人的印象。 读法二：弹簧。 每条边是一根弹簧，边权是弹簧的硬度，弹簧的自然长度是零——它希望两端的预测值相等。 有标签的点被钉子钉在标签值上。 最小化总弹性势能，就是让整张网在「钉子和弹簧」之间找平衡。 lam 控制弹簧整体有多硬：lam 大，网被拉得很平；lam 小，钉子说了算。 读法三：离散的梯度。 连续世界里，「函数变化有多剧烈」用梯度的平方积分衡量：积分 |梯度 f| 的平方。 把这个积分换成图上的求和，就得到 f 转置乘 L 乘 f。 所以 L 是「二阶差分算子」在图上的版本，和 13.5 节拉普拉斯特征映射里那个 L 是同一个东西。 三种读法指向同一个结论：它衡量的是「f 在图上有多不平滑」。 没有一个读法能说明「f 的方向对不对」。 这不是解释得不够，是这个量本身就不含方向信息。

三、它保证不了什么

这一节最重要的数字在这里：

四、反例：越平滑，越不准

把 k 从 3 加到 150，固定 lam 等于 10：

五、动手 Demo：这一项到底在惩罚什么：相邻点的预测值之差

这段代码先验证「f 转置乘 L 乘 f」与「逐边加权差平方和的一半」是同一个数； 再拿真方向和 200 个随机方向比平滑度； 最后把 k 从 3 加到 150，看平滑度和准确率怎么走向两个相反的方向。 重点看三处：第一段两个 66.243718；第二段那个「132 个更平滑」； 以及第三段里平滑度降五百倍、准确率却从满分掉到 0.7500。

import numpy as np


def manifold_data(n=200, d=30, seed=2, noise=0.05):
    """200 个点躺在 30 维空间里的一个二维流形上，标签由线性方向决定。"""
    rg = np.random.default_rng(seed)
    z = rg.normal(0.0, 1.0, (n, 2))
    A = rg.normal(0.0, 1.0, (d, 2))
    X = z @ A.T + rg.normal(0.0, noise, (n, d))
    v = rg.normal(0.0, 1.0, d)
    v = v / np.linalg.norm(v)
    y = np.where(X @ v > 0.0, 1.0, -1.0)
    return X, y, v


def pick_labels(y, per=5, seed=0):
    """每类随机挑 per 个下标当有标签样本。"""
    rg = np.random.default_rng(seed)
    lab = []
    for c in np.unique(y):
        idx = np.where(y == c)[0]
        lab.extend(rg.choice(idx, per, replace=False).tolist())
    return np.array(sorted(lab))


def graph(X, k=8):
    """k 近邻图：W 邻接矩阵，L 等于度矩阵减 W。"""
    n = len(X)
    D2 = np.maximum(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1), 0.0)
    np.fill_diagonal(D2, np.inf)
    idx = np.argsort(D2, axis=1)[:, :k]
    near = np.take_along_axis(D2, idx, axis=1)
    s2 = float(np.median(near))
    W = np.zeros((n, n))
    W[np.repeat(np.arange(n), k), idx.ravel()] = np.exp(-near.ravel() / (2.0 * s2))
    W = np.maximum(W, W.T)
    return W, np.diag(W.sum(axis=1)) - W


def lap_rls(X, y, lab, lam=1.0, k=8):
    """拉普拉斯正则化最小二乘：标签项加上图上相邻点要接近。"""
    W, L = graph(X, k)
    Xl, yl = X[lab], y[lab]
    return np.linalg.solve(Xl.T @ Xl + lam * (X.T @ L @ X), Xl.T @ yl)


def acc(w, X, y):
    return float(np.mean(np.sign(X @ w) == y))


def purity(X, y, k=8):
    """每个点的 k 个近邻里同类的比例，用来看流形假设成不成立。"""
    D2 = np.maximum(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1), 0.0)
    np.fill_diagonal(D2, np.inf)
    idx = np.argsort(D2, axis=1)[:, :k]
    return float((y[idx] == y[:, None]).mean())


def smooth(f, W):
    """二分之一乘上所有边上加权差的平方。"""
    d = f[:, None] - f[None, :]
    return 0.5 * float((W * d * d).sum())


X, Y, V = manifold_data(200, 30, 2)
LAB = pick_labels(Y, 5, seed=0)
W, L = graph(X, 8)
F = X @ V

print('[1] 正则项到底在算什么：两种算法必须给出同一个数')
print('  f 取真方向时，f 转置乘 L 乘 f      %.6f' % float(F @ L @ F))
print('  二分之一乘上逐边加权差平方        %.6f' % smooth(F, W))
print('  图为 %d 个点、%d 条有向边' % (len(X), int((W > 0).sum())))

print('')
print('[2] 标签方向并不是最平滑的方向')
print('  沿真方向的平滑度 %.4f' % smooth(F, W))
rg = np.random.default_rng(0)
vals = []
for _ in range(200):
    r = rg.normal(0.0, 1.0, 30)
    r = r / np.linalg.norm(r)
    vals.append(smooth(X @ r, W))
vals = np.array(vals)
print('  200 个随机方向：中位 %.4f  最小 %.4f  最大 %.4f'
      % (float(np.median(vals)), vals.min(), vals.max()))
print('  其中比真方向更平滑的有 %d 个，占 %.0f%%'
      % (int((vals < smooth(F, W)).sum()), 100.0 * (vals < smooth(F, W)).mean()))
print('  所以「最平滑」不等于「对标签」——正则项只能挑形状，挑不了方向')

print('')
print('[3] 反例：越平滑，反而越不准（lam=10）')
for k in (3, 8, 20, 80, 150):
    Wk, Lk = graph(X, k)
    w = lap_rls(X, Y, LAB, lam=10.0, k=k)
    print('  k=%-3d 准确率 %.4f  平滑度 %8.4f  近邻同类比例 %.4f'
          % (k, acc(w, X, Y), smooth(X @ w, Wk), purity(X, Y, k)))

实跑输出：

--------------------------------------------------------------------
这一项到底在惩罚什么：相邻点的预测值之差
--------------------------------------------------------------------
[1] 正则项到底在算什么：两种算法必须给出同一个数
  f 取真方向时，f 转置乘 L 乘 f      66.243718
  二分之一乘上逐边加权差平方        66.243718
  图为 200 个点、1994 条有向边

[2] 标签方向并不是最平滑的方向
  沿真方向的平滑度 66.2437
  200 个随机方向：中位 43.8687  最小 2.4559  最大 377.7483
  其中比真方向更平滑的有 132 个，占 66%
  所以「最平滑」不等于「对标签」——正则项只能挑形状，挑不了方向

[3] 反例：越平滑，反而越不准（lam=10）
  k=3   准确率 0.9800  平滑度   0.1042  近邻同类比例 0.9783
  k=8   准确率 1.0000  平滑度   0.0247  近邻同类比例 0.9500
  k=20  准确率 0.9750  平滑度   0.0046  近邻同类比例 0.9130
  k=80  准确率 0.8500  平滑度   0.0004  近邻同类比例 0.7454
  k=150 准确率 0.7500  平滑度   0.0002  近邻同类比例 0.5845

第一段只有三行，但它是整节的地基。 f 转置乘 L 乘 f 是 66.243718， 逐边加权差平方和也是 66.243718——两个完全独立的算法给出同一个数，说明这个恒等式成立。 1994 条有向边，每条都贡献一点点，加起来正好是这个数。 第二段是这一节最反直觉的地方。 真方向的平滑度 66.2437，看着挺小；但 200 个随机方向的中位数是 43.8687，比它更小。 数出来有 132 个更平滑，占 66%。 所以「平滑」这件事和「对标签」之间没有必然联系——这次是三分之一的吻合率。 想想这意味着什么：如果只有两个标签，模型基本就是在这 200 个方向里挑最平滑的， 那它有三分之二的概率挑错。 16.1 里那片 0.625 到 0.655 就是这么来的。 第三段五行，第三列和平滑度有关，第二列和准确率有关。 k 等于 3 时平滑度 0.1042，k 等于 150 时 0.0002——降了五百倍。 而准确率是 0.9800、1.0000、0.9750、0.8500、0.7500，先升后崩。 第四列的近邻同类比例 0.9783 到 0.5845 是解释。 k 等于 150 时大部分边都跨类，图在说谎，而正则项老老实实照着谎言平滑。 这也是半监督最常见的翻车方式：不是算法不收敛，是图建错了。

30 秒实验

1. 把 [2] 里的 200 改成 2000，重跑。 样本多了之后，「比真方向更平滑的比例」会更稳定地接近某个值。 看它是多少——这个比例就是「只按平滑度挑方向」的失败率。
2. 把 [3] 里的 lam 从 10 改成 1000，重跑。 lam 越大平滑项越强势，k 等于 150 那一行会更难看。 如果连 k 等于 3 都掉下来，说明 lam 已经压过标签项了。
3. 把 smooth 里的 f 换成 X @ w，其中 w 用 lap_rls 解出来的那个。 这算的是「最终解在图上有多平滑」。 和真方向的 66.2437 比一比——差多少，就是模型为了平滑牺牲掉的东西。

常见误区

1. 「拉普拉斯正则化会让预测更平滑，所以一定更准」。 反例就在本节：k 从 8 加到 150，平滑度从 0.0247 降到 0.0002， 准确率却从 1.0000 掉到 0.7500。 平滑是手段，不是目的。
2. 「平滑度最小的方向就是对标签的方向」。 实测 200 个随机方向里有 132 个比真方向更平滑。 真方向的平滑度 66.2437 甚至高于随机方向的中位数 43.8687。 这个正则项只含形状信息，不含方向信息。
3. 「这一项等价于核方法里的某个核，所以有同样的理论保证」。 确实可以写成核形式，但理论保证的前提是「图正确反映相似性」。 k 等于 150 时这个前提被破坏，理论上的保证一条都不成立。
4. 「f 转置乘 L 乘 f 是近似算法，逐边求和才是精确的」。 两个是恒等的，实测都是 66.243718，差在小数点后六位之后。 恒等式的证明只有一行：把 f 转置乘 D 乘 f 与 f 转置乘 W 乘 f 相减，凑成完全平方。

第 16 章三节讲完了「怎么用没标签的数据」。 下一章换一个方向：如果标签一直有，但维数太高、噪声维度太多，能不能让标签反过来帮你降维？

• ☐ （本章完，下一节 17.1 17.1）

相关笔记

• 灵活应用输入数据的流形构造
• 拉普拉斯正则化最小二乘学习的求解方法
• 拉普拉斯特征映射
• 🤖 图解机器学习 · 索引