一、只给十个标签，怎么够用

先把设定摆清楚：有 n 个样本，其中只有一小部分带标签，其余全没有。 目标是利用全部 n 个样本的输入，学出一个对全部样本都准的分类器。 为什么没用标签的样本会有帮助？因为它们能告诉你一件事：数据不是均匀撒在空间里的。 它们挤在某些方向上，绕开另一些方向，形成一个低维的形状——这就是所谓的流形。 流形假设说：标签在这个形状上是缓慢变化的，挨得近的点大概率同类。 这个假设可以被量出来。 本节用的数据是 200 个点躺在 30 维空间里的一个二维流形上，每个点找最近的 8 个邻居， 看里面有多少和自己同类：0.9500。 九成半。 这意味着「谁挨着谁」这件事本身携带了大量标签信息——只要你能把邻接关系用起来， 就相当于凭空多出一批弱标签。 反过来，这个数如果接近 0.5，半监督一定没用。 因为那时候「挨着」和「同类」没关系，几何提供的全是噪声。 记住这个诊断指标，它比任何理论都实用： 上手半监督之前，先算一下近邻同类比例；低于 0.7 就别指望了。

二、光有标签会怎样

先看只有标签时的表现，作为对照。 每类挑 1 个、5 个、200 个（全部），用最小二乘直接解一个线性模型：

三、把无标签的点组织成图

现在把 190 个无标签的点的位置用起来。办法分两步：先建图，再把图变成一个惩罚项。 建图：每个点连到离它最近的 k 个点，边的权重按距离衰减：

W[i][j] = exp( - 距离(i, j) 的平方 / (2 * sigma 的平方) )
sigma 取所有近邻距离的中位数，这样不用手工调尺度

然后把图整理成两个矩阵：度矩阵 D（每一行权重之和放在对角线上）， 以及拉普拉斯矩阵 L 等于 D 减 W。 L 这个名字看着吓人，它其实就是一个「相邻程度的反面」：两个点连得越紧， L 里对应的项越能放大它们之间的差异。 第二步，把这个差异写成惩罚项加到目标函数里：

min  求和(有标签样本) ( y_i - w . x_i ) 的平方
     + lam * w 转置 * X 转置 * L * X * w

第二项就是拉普拉斯正则化。 它要求「图上相邻的两个点，预测值要接近」——因为差异大的话，这一项就会变大，而我们在最小化它。 lam 控制这条要求的力度：lam 等于 0 就退化成只用标签，lam 很大就几乎只看平滑。 注意这个惩罚项里没有任何标签。 它只知道「谁挨着谁」，不知道「谁是什么类」。 这就是半监督的全部秘密，也是它的全部局限——它提供的是几何，不是答案。

四、几何能补形状，补不了方向

同一个 200 点数据，两种标签量的结果摆在一起：

五、动手 Demo：200 个点只有 10 个标签：几何能补上，几何补不上就不行

这段代码先造 200 个躺在 30 维空间里的点，算一下「近邻同类比例」； 再比较每类 1 个、每类 5 个、全部标签三种情况下的准确率； 然后把无标签的点建成图，加上拉普拉斯正则化，看 k 和 lam 怎么影响结果。 重点看两处。第一段那个 0.9500 决定半监督有没有戏； 第三段里「每类 1 个标签」那一整片 0.625 到 0.655，和「每类 5 个标签」的三个数 0.9550、0.9850、 1.0000，差别就出来了。

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 rls(X, y, lab):
    """只用有标签样本的最小二乘，加一点数值兜底。"""
    Xl, yl = X[lab], y[lab]
    return np.linalg.solve(Xl.T @ Xl + 1e-8 * np.eye(X.shape[1]), Xl.T @ yl)


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())


X, Y, V = manifold_data(200, 30, 2)

print('[1] 数据长什么样')
print('  维度 %d，样本 %d，两类各 %d / %d'
      % (X.shape[1], len(X), int((Y > 0).sum()), int((Y < 0).sum())))
print('  每个点的 8 个近邻里，同类的比例 %.4f' % purity(X, Y, 8))
print('  也就是说：在图上挨着的点，九成半同类——几何确实携带标签信息')

print('')
print('[2] 标签越少，越只能靠几何')
for per in (1, 5):
    lab = pick_labels(Y, per, seed=0)
    print('  每类 %d 个标签（共 %2d 个）  只用这些标签 %.4f'
          % (per, len(lab), acc(rls(X, Y, lab), X, Y)))
print('  全部 %d 个标签（作弊上界）  %.4f' % (len(X), acc(rls(X, Y, np.arange(len(X))), X, Y)))
print('  真方向 V 本身              %.4f' % acc(V, X, Y))

print('')
print('[3] 把无标签的 190 个点用上之后')
print('  每类 1 个标签，共 2 个：换 k 和 lam 都没什么用')
for k in (5, 8, 12, 20):
    row = [acc(lap_rls(X, Y, pick_labels(Y, 1, 0), lam=lm, k=k), X, Y)
           for lm in (0.01, 0.1, 1.0, 10.0, 100.0)]
    print('    k=%-2d  ' % k + '  '.join('%.3f' % v for v in row))
print('    （五列对应 lam = 0.01、0.1、1、10、100）')
lab = pick_labels(Y, 5, seed=0)
print('  每类 5 个标签，共 10 个：')
for lm in (0.1, 1.0, 10.0):
    print('    lam=%-5.1f k=8  准确率 %.4f' % (lm, acc(lap_rls(X, Y, lab, lam=lm, k=8), X, Y)))

实跑输出：

--------------------------------------------------------------------
200 个点只有 10 个标签：几何能补上，几何补不上就不行
--------------------------------------------------------------------
[1] 数据长什么样
  维度 30，样本 200，两类各 103 / 97
  每个点的 8 个近邻里，同类的比例 0.9500
  也就是说：在图上挨着的点，九成半同类——几何确实携带标签信息

[2] 标签越少，越只能靠几何
  每类 1 个标签（共  2 个）  只用这些标签 0.5950
  每类 5 个标签（共 10 个）  只用这些标签 0.7200
  全部 200 个标签（作弊上界）  0.9600
  真方向 V 本身              1.0000

[3] 把无标签的 190 个点用上之后
  每类 1 个标签，共 2 个：换 k 和 lam 都没什么用
    k=5   0.630  0.640  0.650  0.655  0.655
    k=8   0.625  0.625  0.625  0.625  0.625
    k=12  0.635  0.635  0.635  0.635  0.635
    k=20  0.645  0.640  0.640  0.640  0.640
    （五列对应 lam = 0.01、0.1、1、10、100）
  每类 5 个标签，共 10 个：
    lam=0.1   k=8  准确率 0.9550
    lam=1.0   k=8  准确率 0.9850
    lam=10.0  k=8  准确率 1.0000

第一段的 0.9500 是整节的前提。 它的意思是：随便挑一个点，它最近的 8 个邻居里有 95% 跟它同类。 所以「把邻居的判断借过来」这个策略， 理论上限就是 95% 左右——这也是为什么后面的结果都在这条线附近或以上。 第二段是三条基线：每类 1 个 0.5950、每类 5 个 0.7200、全部 0.9600。 中间那条最值得注意：10 个标签只比 2 个标签好 12 个百分点。 在 30 维里，10 个约束和 2 个约束都属于「严重不足」。 第三段上半部分是 4 行 5 列共 20 个数字，全都落在 0.625 到 0.655 之间。 k 从 5 到 20、lam 从 0.01 到 100，怎么调都在原地打转。 这一段的意义不在于「得到多少」，而在于「证明调参救不回来」——问题出在标签量，不在超参数。 第三段下半部分换成每类 5 个标签，立刻不一样：0.9550、0.9850、1.0000。 lam 越大越好，到 10 就满分。 原因在 16.2 节会看到：标签项已经把方向定住，几何项越大，噪声方向的抖动被压得越干净。 代码里有一个细节值得学：sigma 没有手工给，而是取所有近邻距离的中位数。 这样换一份数据不用重新调尺度。 手工定 sigma 是半监督最常翻车的地方之一——数据缩放一变，图就全乱了。

30 秒实验

1. 把 manifold_data 里的 d 从 30 改成 5，重跑。 维度降到 5 之后，10 个标签已经接近够用，只用标签的准确率会明显上升， 半监督的优势也随之变小。
2. 把 noise 从 0.05 改成 0.6，重跑第一段。噪声一大，近邻同类比例会掉下来。 看它掉到多少时半监督开始失效——这就是「几何不可信」的临界点。
3. 把 purity 里的 k 从 8 改成 2 和 20 各跑一次。 k 小的时候纯度更高，但图会断成很多块；k 大的时候纯度下降。 这个权衡在 16.2 节的 k 扫描里会直接体现在准确率上。

常见误区

1. 「无标签数据越多越好，反正不要钱」。 无标签数据只在「近邻同类比例高」时有用。 本节数据是 0.9500，所以有效；如果换成两类完全混在一起的数据，这个比例接近 0.5， 加多少无标签数据都只会把模型往错的方向拉。
2. 「半监督是免费的午餐，标签少就能靠它补回来」。 实测每类只给 1 个标签时，二十种 k 与 lam 的组合全在 0.625 到 0.655， 而只用标签是 0.5950——涨了三个百分点，等于没涨。 标签太少时，几何连方向都定不住。
3. 「图连得越密，几何信息用得越充分」。 恰恰相反。k 从 8 加到 150，边数从 1994 涨到近三万，近邻同类比例从 0.9500 掉到 0.5845， 准确率也从满分掉到 0.7500。 边密到一定程度就开始跨类，图反而在骗你。
4. 「拉普拉斯正则化会让模型变复杂」。 它是正则化，做的是限制：要求相邻点预测接近，等于压缩模型的自由度。 附加的好处是它顺手把矩阵从奇异变成可逆——实测条件数从 3.4e10 降到 1.3e3。

这一节把目标函数写出来了，但没解。 下一节就干一件事：把那个矩阵形式的解推出来， 顺便看看为什么加了这一项之后方程就从「解不唯一」变成「唯一」。

• ☐ （本节完，下一节 16.2 16.2）

相关笔记

• 拉普拉斯正则化最小二乘学习的求解方法
• 拉普拉斯正则化的解释
• 谱聚类
• 🤖 图解机器学习 · 索引