欢迎大家提Issue反馈问题或建议,建设推理王国!
Skip to content

第21章:学习作为逆推断——泛化是压缩的另一种说法 ​

模型"学到了东西"的形式含义是:它找到了更短的描述。


第20章结尾留下了一个问题:启发函数能否自动从数据中发现?PAC 学习保证了学习的可能性,但它没有说学习是什么——它只是描述了一个黑盒,告诉你这个黑盒的输出具有什么性质。

这一章要打开这个黑盒。

学习,在最抽象的意义上,是从一批观测——例子、数据、经验——中推断出一条可泛化的规律。这个推断过程若要有形式含义,就必须回答:相比观测本身,推断出的规律多了什么、少了什么?它为什么能从见过的例子,说出未见例子的事情?

答案的关键词是压缩。


21.0 压缩侦探游戏:从样本中找回规律 ​

学习不是把数据背下来。背下来太容易,也太没用。真正的学习像侦探破案:桌上有一堆线索,你必须找出一条比线索本身更短的解释。

游戏开始时,自然交给你一串样本:

S={(x1,y1),(x2,y2),…,(xn,yn)}

你可以提交一个假设 h。这个假设必须做两件事:第一,解释你已经看到的数据;第二,它本身不能太长。因为最愚蠢的"规律"永远存在:把每个样本逐条背下来。这样的规律训练误差为零,却没有任何泛化能力。

压缩侦探的评分规则是:

L(h)+L(S∣h)

前一项是描述假设本身需要多少比特;后一项是在假设给定之后,描述数据还需要多少比特。最好的假设不是最复杂的,也不是最贴合训练集的,而是总描述长度最短的那个。

这个游戏的形式化骨架

  • 状态空间:样本集 S、假设类 H、编码方案 L。
  • 合法动作:选择一个假设 h∈H,并用它压缩数据。
  • 转移规则:从观测样本反推候选规律,比较 L(h)+L(S∣h)。
  • 胜利条件:找到能压缩训练数据、并在未见样本上保持低误差的假设。
  • 失败模式:死记硬背样本;或选择过强的归纳偏置,把世界压缩成错误的形状。

这个游戏把泛化的秘密说得很直白:你能泛化,是因为你找到了可压缩的结构。如果数据完全随机,就没有短规律可找;如果你找到了一条能解释大量样本的短规律,它很可能抓住了某种真实结构。

但这里也有危险。压缩需要编码方案,而编码方案就是归纳偏置。你以为自己在"从数据中学习"——其实你一直带着一把剃刀进场:什么算简单、什么算复杂,你的表示系统在你到来之前就决定了。

压缩侦探游戏冷酷的地方在于:没有偏置,就没有学习。完全中立的学习者只能背诵样本;要泛化,你就必须偏爱某些规律胜过另一些。机器学习课喜欢把这叫"模型选择"。说得太轻了。你实际上是在选择你愿意相信世界具有什么形状。

21.0.5 在代码中玩这个游戏 ​

评分规则小到可以直接计算。下面的程序用最小二乘法把四条候选规律拟合到十个样本上,按 L(h)+L(S∣h) 给它们打分,然后让每条规律去预测一个谁也没见过的样本。插值多项式在训练集上得到完美拟合——然后预测出一堆胡话。

python
#!/usr/bin/env python3
"""
compression_detective.py -- the Compression Detective Game of Chapter 21.
Book reference: The Reasoning Kingdom, Volume 2, Chapter 21, Section 21.0
"The Compression Detective Game: Recovering the Law from Samples."

Nature hands over ten samples; one of them is noisy. You may submit a
hypothesis h. The scoring rule is the one the book writes on the table:

    L(h) + L(S | h)

the bits for the hypothesis itself, plus the bits left over to describe
the data given the hypothesis. This program fits four candidate laws
(constant, linear, quadratic, a degree-9 polynomial that memorizes
everything, and a literal look-up table), scores them all by the rule,
and then tests generalization on a sample nobody has seen.
All fits are computed here (least squares via Gaussian elimination); all
scores and predictions are real.
Honest scope: the bit-costs are toy constants, not an optimal code. The
mechanism -- total description length picks the law that compresses --
is the point, not the coding theorem.
Run:  python3 compression_detective.py
"""
# The hidden law is y = 2x + 1, plus ONE noisy sample at x=5 (20 instead
# of 11). The detective does not know which sample is the noisy one.
XS = tuple(range(10))
YS = (1, 3, 5, 7, 9, 20, 13, 15, 17, 19)
BITS_PER_PARAMETER = 20     # toy cost of writing one parameter down
MEMORY_COST_PER_SAMPLE = 40  # toy cost of memorizing one (x, y) pair


def polyfit(xs, ys, degree):
    """Least-squares polynomial fit of the given degree.
    Normal equations solved by Gaussian elimination with partial
    pivoting. Returns the coefficient tuple (lowest power first)."""
    n = degree + 1
    a = [[0.0] * (n + 1) for _ in range(n)]
    for x, y in zip(xs, ys):
        powers = [x ** k for k in range(2 * degree + 1)]
        for i in range(n):
            for j in range(n):
                a[i][j] += powers[i + j]
            a[i][n] += y * powers[i]
    # Gaussian elimination
    for col in range(n):
        pivot = max(range(col, n), key=lambda r: abs(a[r][col]))
        a[col], a[pivot] = a[pivot], a[col]
        for r in range(col + 1, n):
            factor = a[r][col] / a[col][col]
            for c in range(col, n + 1):
                a[r][c] -= factor * a[col][c]
    coeffs = [0.0] * n
    for r in range(n - 1, -1, -1):
        coeffs[r] = (a[r][n] - sum(
            a[r][c] * coeffs[c] for c in range(r + 1, n)
        )) / a[r][r]
    return tuple(coeffs)


def evaluate(coeffs, x):
    return sum(c * x ** k for k, c in enumerate(coeffs))


def score(coeffs):
    """L(h) + L(S|h) for a polynomial law, in toy bits."""
    lh = len(coeffs) * BITS_PER_PARAMETER
    residuals = (evaluate(coeffs, x) - y for x, y in zip(XS, YS))
    ls = sum(r * r for r in residuals)
    return lh + ls


def demo():
    print("=" * 70)
    print(" THE COMPRESSION DETECTIVE GAME -- the razor, scored for real")
    print(" The Reasoning Kingdom, Volume 2, Chapter 21 (Sec. 21.0)")
    print("=" * 70)
    print("\nThe samples on the table:")
    print("  x:", XS)
    print("  y:", YS)
    print("  (one of these is noise; the detective is not told which)")
    print("\nCandidate laws, scored by L(h) + L(S|h):")
    print(f"  {'law':<38}{'params':>6}{'L(h)':>7}{'L(S|h)':>10}{'total':>9}")
    candidates = []
    for degree in (0, 1, 2, 9):
        coeffs = polyfit(XS, YS, degree)
        name = {0: "constant", 1: "linear", 2: "quadratic", 9: "degree-9 (interpolate)"}[degree]
        total = score(coeffs)
        lh = len(coeffs) * BITS_PER_PARAMETER
        ls = total - lh
        candidates.append((name, coeffs, total))
        print(f"  {name:<38}{degree + 1:>6}{lh:>7.0f}{ls:>10.0f}{total:>9.0f}")
    # The look-up table: memorize every sample. Zero error, huge law.
    lookup = dict(zip(XS, YS))
    lh = len(lookup) * MEMORY_COST_PER_SAMPLE
    candidates.append(("memorize every sample", lookup, lh))
    print(f"  {'memorize every sample':<38}{len(lookup):>6}{lh:>7.0f}"
          f"{0:>10.0f}{lh:>9.0f}")
    winner = min(candidates, key=lambda c: c[2])
    print(f"\nWinner by total description length: {winner[0]}")
    print("  The interpolating polynomial has zero training error, and the")
    print("  look-up table is error-free by construction -- but both must")
    print("  carry their own weight in bits. The simplest law that")
    print("  explains the pile wins.")
    # Generalization: a sample nobody has seen yet, x = 10.
    print("\nThe unseen sample: x = 10. What does each law predict?")
    for name, law, _ in candidates:
        if name == "memorize every sample":
            print(f"  {name:<28} no prediction at all (x=10 was never memorized)")
        else:
            print(f"  {name:<28} y = {evaluate(law, 10):>10.1f}")
    print("  The hidden law was y = 2x + 1; its true answer is 21. The")
    print("  interpolator's wild guess is what 'zero training error' buys")
    print("  you: nothing on samples you have not seen.")
    print("=" * 70)


if __name__ == "__main__":
    demo()

21.1 学习的逆问题结构 ​

在形式逻辑中,推断的方向是从公理到定理:给定前提,推出结论。这是正向推断。

学习的方向恰好相反:给定一批定理(你观测到的事实),反推最可能的公理集合(规律)。这是逆推断——从结果倒推原因。

这种逆向结构有一个根本困难:它是欠定的。一批有限的观测通常与无穷多条不同的规律相容。你看到太阳每天升起;这与"太阳每天升起"相容,也与"太阳每天升起,但 2035 年 3 月 17 日除外"相容,还与无数其他规律相容。

这个困难没有纯粹逻辑上的解法。你无法从观测中演绎出唯一正确的规律。你需要某种归纳偏置——一种对规律的先验偏好,在所有与观测相容的规律中偏向某一类。

归纳偏置是什么,决定了学习是什么。

21.1.5 欠定性的具体面孔 ​

用同一个数据集,三个不同的学习者会给出三条不同的规律。这不是比喻——拿起笔算一算。

数据:(x,y)={(0,0),(1,1),(2,4),(3,9)},四个点。

学习者 A(线性回归):它的假设空间是所有线性函数 y=ax+b。看这四个点,它找到的最优解是 y=3x−0.5(最小二乘)。这个函数在训练点上并不精确——在 (2,4) 处它预测 5.5,误差 1.5——但它"相信"规律是线性的。

学习者 B(二次回归):它的假设空间是所有二次函数 y=ax2+bx+c。看这四个点,它找到精确解 y=x2——在所有训练点上完美拟合。它"相信"规律是二次的。

学习者 C(10 次多项式):它的假设空间是所有次数不超过 10 的多项式 y=∑i=010aixi。经过这四个点的 10 次多项式有无穷多个——这就是欠定性的面孔。若不加约束,学到的规律可能是一条剧烈振荡的曲线,在训练点之间疯狂抖动。

谁是对的?如果真实规律确实是 y=x2,那么学习者 B 最好。如果真实规律是 y=3x(加上噪声),那么学习者 A 更好。学习者 C 几乎肯定是错的——它太灵活,会把噪声当成规律。

关键点:三个学习者永远无法通过"看更多数据"来裁定谁对。给定任意有限点集,总存在一个 10 次多项式完美拟合它们。你可以在训练数据上完美、同时在测试数据上糟糕。数据本身不会告诉你——选择线性、二次还是 10 次多项式,是你的选择,不是数据的选择。

这就是归纳偏置的本质:它不是从数据中学来的;它是你在看数据之前就带进问题里的东西。像一副眼镜,你在看之前就戴上了。不同的眼镜,不同的规律。

很多人听到"欠定性"时会点头,然后又回去用默认超参数训练模型。欠定性不是一个需要你"理解"的理论事实——它是在每一次训练中都会发生的操作性问题。你选择模型架构的那一刻,欠定性已经被部分解决了——但你不一定知道自己选了哪种偏置,也不一定知道它是否适合当前的数据。知道自己有偏置,却不知道是哪种偏置,这比根本不知道有偏置更危险——因为你以为自己掌控着局面,其实并没有。

归纳偏置不是技术选项,而是形而上学承诺。你选择线性模型,就是在断言"规律是线性的";你选择深度网络,就是在断言某种关于特征层级的结构假设。大多数机器学习课程把这叫做"调超参数",把形而上学承诺埋进了工程操作里。这是在回避一个真实的问题,而不是解决它。


21.2 奥卡姆剃刀的形式化 ​

最古老、最直观的归纳偏置是奥卡姆剃刀:偏爱更简单的解释。

但"简单"是什么意思?

Kolmogorov 复杂度给出了一个答案。

定义(Kolmogorov 复杂度):字符串 x 的 Kolmogorov 复杂度 K(x),是生成 x 的最短程序的长度(相对于某个固定通用图灵机)。

K(x) 衡量的是 x 的内在复杂度——不是 x 有多长,而是 x 有多难描述。一个全零字符串"000...0"(一百万个零)的 K 很小——有一段很短的生成程序("打印一百万个零")。一个随机字符串的 K 大致等于它自身的长度——没有任何描述比"把字符串本身列出来"更短。

Kolmogorov 复杂度:用压缩程序的长度衡量复杂度(前人工作:Kolmogorov, 1965)

Kolmogorov 复杂度 K(x) 是对"这个对象有多复杂"的数学定义——复杂度等于描述它所需的最短程序的长度。

直觉例子:

  • "前一百万个自然数" -> 一段很短的程序就够了(for i in range(1000000): print(i)),K 很小
  • 随机生成的一百万位数字 -> 没有比"把数字本身列出来"更短的描述,K≈ 字符串长度

重要的不可计算性:K(x) 是不可计算的——没有任何算法能对任意给定的 x 计算出 K(x) 的精确值(这是停机问题的推论)。你只能计算它的上界(找到一个生成 x 的程序,其长度就是上界)。

为什么仍然有用? 即使不可计算,Kolmogorov 复杂度也提供了一个理论标准——衡量"简单性"的绝对基准。实践中用 MDL 作为近似(用一个真实的压缩算法代替最短程序)。

在这个语言里,"简单"意味着"Kolmogorov 复杂度低","偏爱更简单的解释"意味着"选择 K 更小的规律"。

21.2.5 动手:手工估计 Kolmogorov 复杂度的上界 ​

K(x) 无法精确计算,但上界可以:找到一个生成 x 的程序,它的长度就是上界。

例 1:x= "01010101"("01"重复 4 次,共 8 个字符)。

  • 程序:for i in range(4): print("01")
  • 程序长度(采用某种合理的编码):约 20-30 个字符(Python 语法开销 + 循环体)
  • K(x)≤ 约 30

例 2:x= "01010101"重复 1000 次(2000 个字符)。

  • 程序:for i in range(1000): print("01")
  • 程序长度:约 35 个字符(只改了循环次数)
  • K(x)≤ 约 35

注意:数据从 8 个字符增长到 2000 个字符,程序只从约 30 增长到约 35。这就是压缩的力量——规律越长,回报越大。

例 3:x= π 的前 1000 位数字。

  • 程序:mp.pi.n(digits=1000)(依赖数学库)
  • 程序长度:约 40 个字符
  • K(x)≤ 约 40(但这依赖于数学库;库本身也得计算在内。我们可以接受这一点——K 的定义相对于固定通用图灵机,而数学库可以作为这台机器的一部分)

例 4:x= 一个真正的随机字符串(1000 位数字)。

  • 程序:你只能 print("the first 1000 characters of the random string, verbatim")
  • 程序长度 ≈1000 + 一点开销
  • K(x)≈ 字符串本身的长度

这四个例子揭示了一个关键直觉:K(x) 衡量的是 x 有多容易被压缩。高度规律的字符串有紧凑的描述,接近 K(x)≪|x|;完全随机的字符串无法压缩,K(x)≈|x|。

但这里有一个微妙的点:K(x) 的具体值依赖于参考图灵机的选择。不同的机器可能给同一个 x 不同的 K 值,相差一个常数(模拟另一台机器的程序长度)。这就是为什么 K(x) 是渐近意义下的复杂度度量,而不是绝对精确的量。但相差一个常数对大多数理论讨论来说没问题——我们关心的是数量级,不是精确值。

估计 Kolmogorov 复杂度的上界本身就是一堂速成课:你发现一个模式 -> 用你能写出的最短程序描述这个模式 -> 程序的长度就是你对"这个字符串有多复杂"的最大胆断言。但你也可能漏掉了某个模式——你找到的程序只是一个上界。K(x) 的真实值,是你与所有可能程序中最短那个之间的距离——而你无法确定自己找到的是不是最短的那个。

这就是最小描述长度(Minimum Description Length,MDL)原理的核心:

最优假设=arg⁡minh[L(h)+L(数据∣h)]

L(h) 是描述假设 h 本身所需的比特数;L(数据∣h) 是在假设 h 下描述数据所需的额外比特数。最优假设,是让"假设 + 在假设下编码的数据"总长度最短的那个。

MDL 和贝叶斯推断是同一个想法的两种语言。若假设 h 的先验概率为 P(h)∝2−L(h)(越短的假设先验越高——这是 Shannon 编码的标准形式),那么最大后验估计(MAP)恰好就是 MDL:

arg⁡maxhP(h∣数据)=arg⁡maxh[P(数据∣h)⋅P(h)]=arg⁡minh[L(数据∣h)+L(h)]

奥卡姆剃刀,在贝叶斯语言里是先验对简单性的偏好;在 MDL 语言里是最短描述长度的选择。它们是同一个数学结构,穿着不同的衣服。


21.3 泛化就是压缩 ​

MDL 原理揭示了一个深刻的等价:泛化能力等价于压缩能力。

为什么?

一个假设 h 能泛化,意味着它捕捉到了数据中的规律,而不是记住了噪声。规律是能被紧凑描述的结构;噪声是无法压缩的随机成分。如果 h 能用比数据本身更短的描述"解释"数据,那么 h 就真正压缩了数据——它找到了数据中可被紧凑捕捉的部分。

反过来,一个完美记住训练数据的模型没有做任何压缩——它只是把数据原样存了起来。这样的模型在训练数据上表现完美,却对新数据没有预测能力,因为它没有找到规律,只是归档了例子。

这正是第 5 章(上卷)"过拟合"的形式化:过拟合是没有压缩的记忆;泛化是有效的压缩。

用 Kolmogorov 复杂度的语言,泛化的量可以被度量:假设训练数据从 n 比特压缩到 k 比特(k<n),那么压缩比 n/k 在某种意义上衡量了假设的"泛化潜力"——找到了多少可泛化的规律,而不是记住了多少具体案例。

21.3.5 双重下降:当"更多参数 = 更好泛化"动摇了经典理论 ​

经典学习理论(包括 PAC 和 VC 维)预测了一条 U 形曲线:模型太简单 -> 欠拟合;模型恰好 -> 泛化良好;模型太复杂 -> 过拟合。但 2018 年之后,研究者在大规模深度学习中观察到一个反直觉现象:双重下降(double descent)。

当参数数量超过训练数据量——进入"过参数化"区域——测试误差不会继续上升,而是再次下降。一个大到足以完美记住训练数据的模型,反而开始泛化得更好。

这意味着什么?VC 维和 PAC 的最坏情况保证仍然正确——它们没有"错"。但它们描述的是所有可能数据分布中最坏的那个。真实深度学习在自然数据上,似乎具有某种隐式的简单性偏好:即使模型有足够自由度记住每一个训练样本,优化算法(SGD)与架构选择(卷积、注意力、层归一化)的相互作用,仍然偏向更简单的解。

过度训练的视角:2023 年之后,实践社区逐渐接受了另一个违背经典直觉的事实:对于参数量固定的模型,灌入数百甚至数千倍的数据——所谓"过度训练"——通常仍会持续提升泛化能力,远超经典理论的预测。当数据量达到参数量的数百倍时,模型仍在学习可泛化的规律。

这两个现象——双重下降与过度训练——指向同一个方向:深度学习的泛化机制无法用纯统计学习理论完全解释。MDL 视角(泛化 = 压缩)提供了一种更灵活的语言:关键不是参数数量,而是模型内部实际使用的"有效描述长度"。一个千亿参数的模型,如果其有效自由度被 SGD 隐式压缩到百万量级,那么它在 MDL 框架里就是"简单"的——尽管参数量巨大。

这个视角仍在发展,尚无定论。但它清楚说明了一个重要事实:理论工具需要随着实践的发展而重新审视。PAC 和 VC 维不会"过时"——它们给出最坏情况下的精确保证。但自然数据的分布不是最坏情况,所以实际行为可以远好于最坏界。分清"理论在什么假设下成立"与"实践在什么条件下突破这些假设",是理解泛化的关键。

双重下降打了经典理论一记耳光,但经典理论没有死。经典理论说:"存在某个可怕的数据分布,会让你的模型翻船。"双重下降说:"幸运的是,自然数据不是那个分布。"两句话同时为真,并不矛盾。一个好的理论家,不是用理论解释一切的人,而是知道理论在何处开始不够用——并开始寻找新理论的人。

这个问题曾在理论界是个谜:深度神经网络的参数数量往往超过训练数据量,按照传统学习理论,这样的模型应该严重过拟合。但在实践中,它们通常泛化良好。MDL 视角给出了一个方向:衡量泛化的不是参数数量,而是模型实际使用的"有效描述长度"——一个有一百亿参数、但参数之间高度结构化的模型,其有效描述长度可能远小于参数数量。压缩才是关键,不是规模。但正如深度学习研究社区所发现的——值得一提的是,上面的描述主要是经典的深度表示学习图景,在大语言模型和现代神经网络训练中,它未必是黄金标准——2023 年之后,深度学习的数据与参数配比开始强调过度训练:在参数量固定的情况下,我们灌入数百甚至数千倍的数据来训练同等规模的网络。近期研究表明,过度训练是深度学习和大型语言模型有效泛化的一种形式。


21.4 归纳偏置的选择 ​

MDL 和 Kolmogorov 复杂度给出了一个优雅的框架,但有一个实际问题:Kolmogorov 复杂度是不可计算的。

所以奥卡姆剃刀在最严格的形式下,本身是不可判定的。你无法写一个算法,对任意两个假设,总能在有限时间内找出哪个更简单。"简单"这个词背后藏着一个停机问题。这并不妨碍你使用 MDL 的近似——但你必须知道它只是近似,不是真正的剃刀。

给定一个字符串 x,计算 K(x) 需要找到生成 x 的最短程序——这等价于求解停机问题,而第 19 章已经证明停机问题不可判定。你无法写出一个在有限时间内计算任意输入 Kolmogorov 复杂度的算法。

这意味着 MDL 在最纯粹的形式下本身不可计算。实践中的 MDL 是一种近似:用某个固定的编码方案代替通用图灵机,用可计算的描述长度代替不可计算的 Kolmogorov 复杂度。

不同的近似方案对应不同的归纳偏置:

  • 决策树学习:假设空间是决策树;描述长度是树的深度或节点数。它偏爱小树,即简单的决策规则。
  • 线性模型:假设空间是线性函数;描述长度是系数的范数。L1 正则化偏爱稀疏系数(大多数为零);L2 正则化偏爱小系数。
  • 神经网络:假设空间是特定架构的网络;"描述长度"由参数值和网络结构共同决定。这个描述长度非常难以确定——理论与实践之间存在巨大的空白地带。

每一种学习算法都隐含地选择了一种归纳偏置——一种对"简单意味着什么"的特定理解。在大多数机器学习课程中,这个选择以"超参数调优"的名义被处理——但它实际上是一种关于"应该偏爱哪类规律"的形而上学承诺。

21.4.5 Rademacher 复杂度:另一把尺子 ​

VC 维是一个组合量,对于许多现代假设空间(如深度神经网络),精确计算 VC 维非常困难。Rademacher 复杂度提供了另一种视角——它直接衡量一个假设类拟合随机噪声的能力。

考虑样本集 S={z1,…,zm},给每个样本独立地分配一个 Rademacher 变量 σi∈{−1,+1}(均匀随机选取)。假设类 H 的经验 Rademacher 复杂度为:

R^S(H)=Eσ[suph∈H1m∑i=1mσih(zi)]

直觉:如果 H 能很好地拟合纯随机噪声(σi 是随机的 ±1),那么 H 就很复杂。因为拟合噪声不需要"学到规律",只需要足够的自由度。Rademacher 复杂度越高,H 越容易过拟合。

与 VC 维的关系:VC 维给出最坏情况界;Rademacher 复杂度给出数据依赖的界——它在手头的具体样本集 S 上衡量复杂度。在某些情况下,这使它比 VC 维更紧(界更接近实际性能)。

把 VC 维与 Rademacher 复杂度并排看:VC 维问"你能打散多少个点"(纯组合的);Rademacher 复杂度问"在这个特定数据集上,你能多好地拟合随机噪声"(数据依赖的)。它们从不同角度量化同一件事:假设空间容纳随机模式的能力。容量越大,需要的样本越多;样本不足时,模型可能学到的是噪声而不是信号。


21.5 逆推断的两个困难 ​

学习作为逆推断,面临两个根本困难,二者都不是数据本身能解决的。

第一个困难:欠定性。如前所述,有限数据与无穷多个假设相容,因此需要归纳偏置在其中做选择。归纳偏置是从外部输入的;它不是从数据中推断出来的。学习问题的解取决于假设空间的选择——而这个选择不在学习算法的管辖范围之内。

第二个困难:分布偏移。PAC 学习假设训练数据与测试数据来自同一分布 D。在实践中,这个假设经常被违反——训练时的分布与部署时的分布可能不同。一旦发生分布偏移,任何建立在训练数据之上的泛化保证都可能失效。

这两个困难是学习理论的根本限制,不是算法缺陷。它们意味着:每个学习系统都在某些假设下工作;一旦离开这些假设,保证就消失了。

这个结构与第 14 章的形式系统非常相似:形式系统在其公理之内是可靠的,越过公理就没有保证;学习系统在其假设之内是可靠的,越过假设就没有保证。两个系统的可靠性都依赖于一种无法从内部验证的外部承诺。

21.5.5 为什么这个困难无法被数据解决 ​

用一个极端的例子把这个问题钉死。

假设你有一个学习器,任务是预测序列的下一个元素。训练数据是:

2,4,6,8,10,12,…

三个学习者各自学到不同的规律:

  • 学习者 A:输出 2n(偶数)
  • 学习者 B:输出 n2−n+2(这个公式在前几项也给出 2, 4, 6, 8……不:12−1+2=2,22−2+2=4,32−3+2=8……等等,这不对:32−3+2=8,但序列的第 3 项是 6。所以这个不行。)

让我重写——正确的例子更重要:

序列:0,1,2,3,4,5,…

  • 学习者 A:f(n)=n(自然数)
  • 学习者 B:f(n)= "第 n 个非负整数"(与 A 相同)
  • 学习者 C:当 n≤1000 时 f(n)=n,此后 f(n)=n+1000

对前 5 个元素(0,1,2,3,4),三个学习者完全一致。你无法从数据中区分它们。但对第 1001 个元素的预测:A 和 B 预测 1000,C 预测 2000。

这个例子暴露了什么? 有限数据永远无法唯一确定规律——欠定性不是"数据还不够",而是"强到即使在数据极限下也依然存在的欠定性"。唯一的出路是引入归纳偏置——断言 C"更复杂",因而比 A 差。但这个断言不是从数据中来的;是你带进来的。

还要注意:如果真实规律确实是 C(比如序列在第 1000 个元素之后突然跳变),那么你的归纳偏置——对 A 的偏爱——会让你系统性地犯错。归纳偏置不是免费午餐:它在某些世界里帮你,在另一些世界里害你。而你无法从训练数据判断自己活在哪个世界。

回到压缩侦探游戏:侦探从不会空手进入现场。他们随身带着一套编码方案,一套关于"什么算短描述"的预设。于是同一堆线索,在不同的侦探眼中导向不同的规律:线性模型看见直线,决策树看见分叉,神经网络看见层级表示。所谓学习,不是数据自己开口说话,而是数据被迫在某种压缩语言里回答。

这句话令人不适,但必须保留:学习系统的失败,往往不是因为它没能找到规律——而是因为它在错误的游戏规则下,找到了一条过于漂亮的规律。


21.6 学习与推断的统一图景 ​

把本章内容放进下卷的框架里。

第 14 章建立了推断的句法机器。第 15 章发现这台机器有内在限制——某些真命题无法从内部证明。第 16 章修改了一条结构规则,得到一种新的推断。第 17 章把真值扩展到 [0,1],得到概率推断。第 18 章引入 do 算子,得到因果推断。第 19 章发现这些推断具有根本的计算下界。第 20 章在代价约束下精确地定义了"足够好"。

第 21 章所做的是把"学习"嵌入这个框架。学习是逆推断——从观测出发,反推规律。MDL 原理给出逆推断的基本规则:最短的解释。PAC 框架给出逆推断的质量保证:以高概率近似正确。

但这个统一图景还缺最后一块:一旦推断系统足够大、足够复杂,它的"推断"就开始包含关于自身的命题——关于它能学到什么、学不到什么,以及它自身的归纳偏置是什么。此时,第 15 章的哥德尔结构重新出现:一个足够强的推断系统无法完全推断自身。

21.6.5 平行结构:学习的不完备性 ​

把第 14–15 章的逻辑不完备性与第 20–21 章的学习不完备性并排放在一起。这两个论证共享一种深层结构:

形式系统(第 14–15 章)学习系统(第 20–21 章)
起点公理 + 推理规则训练数据 + 归纳偏置
内部可做生成所有定理(句法的)搜索假设空间(学习)
外部必需语义解释(模型论)泛化保证(PAC/MDL)
无法内化系统一致性的证明归纳偏置的正当性
边界行为存在为真但不可证的命题存在可学习但需要外部偏置的概念

这不是"有点像"。这是同一个数学结构在两个领域中的实例化。在两种情况下:

  1. 系统内部的合法操作(证明 / 学习)可以无限进行
  2. 但系统无法从内部验证这些操作的正确性条件(一致性 / 泛化)
  3. 正确性条件需要一个外部视角——形式系统需要模型,学习系统需要分布假设

最深的问题:如果归纳偏置本身成为学习对象——元学习——这个限制能被打破吗?

元学习确实能在任务分布上学到一种偏置,使对新任务的适应更快。但元学习自身也有归纳偏置:它在评估"哪种偏置在任务分布上表现好"时,携带着关于任务分布的假设(如"任务共享结构")。如果你把元学习本身也变成学习对象(元元学习),这条链没有终点——每一层都需要自己的归纳偏置,而每一层的偏置都必须从外部输入。

这与哥德尔结构完全平行:把 G 加入公理 -> 新系统有自己的 G′ -> 永远赢不了。把归纳偏置变成学习对象 -> 元学习有自己的元偏置 -> 永远无法自举。

这是第 22 章的入口。第 23 章接着把收敛速率变成涌现的对数曲线。


悬而未决 ​

Kolmogorov 复杂度不可计算——那 MDL 还有意义吗? Kolmogorov 复杂度的不可计算性使它成为一个理想,而不是一个算法。但数学中充满了这样的理想:最优决策、完美信息、无穷精度。理想不需要可计算;它需要充当基准——告诉我们实际算法离最优有多远。MDL 的可计算近似是对这个理想的有限逼近;正是理想本身的存在,才赋予"近似"一词意义。

泛化真的等价于压缩吗? MDL 框架暗示:不能压缩训练数据的模型不会泛化;能压缩的模型则会泛化。但这个等价在深度学习实践中并不总是成立——一些大规模模型在"记住"数据的同时也能很好地泛化。这一张力指向一个未解的理论问题:深度学习的泛化机制究竟是什么?

归纳偏置能被学习吗? 如果学习是逆推断,那么"什么构成一个好的假设空间"本身能被学习吗?元学习试图在任务分布上学到一个好的归纳偏置,使模型更快适应新任务。但元学习本身也有自己的归纳偏置——这是一个无穷倒退,还是在某个层次上会停止?


思考题 ​

★ 热身

下面两个字符串,哪一个的 Kolmogorov 复杂度更低?给出你的直觉和一句话理由——不需要计算具体数值。

  1. 0101010101010101010101010101010101010101(40 个字符,0 和 1 交替)
  2. 1101001000011010110101010001010001000010(40 个随机字符)

再问一个问题:一个"完全随机"的字符串——它的 Kolmogorov 复杂度大致是多少?与字符串本身的长度相比如何?


★★ 推导

  1. 压缩与泛化:一个模型在训练集上误差为零,但在测试集上误差很大(过拟合);另一个模型在训练集上误差 5%,在测试集上也是 5%(良好泛化)。用 MDL 的语言描述二者的差异:哪一个压缩了数据?哪一个记住了数据?每个模型的"描述长度"由什么构成?

  2. 让归纳偏置显性化:线性回归、决策树、神经网络(带 L2 正则化)——每种学习算法隐含了什么归纳偏置?用"偏爱什么样的规律"来描述每一种。每种偏置在什么类型的数据上会系统性地失败?


★★★ 挑战

Kolmogorov 复杂度不可计算(因为它等价于停机问题)。这意味着:没有任何算法能在有限时间内判定任意两个假设中哪一个更简单。

但 MDL 在实践中被使用,用的是可计算的近似。试着列出至少两种可计算的"描述长度"近似方案,并分析:每种近似隐含地假设了什么样的归纳偏置?不同的近似方案在什么时候会给出不同的"最优假设"?

这道题的目的:把"超参数选择"翻译成"归纳偏置选择",再翻译成"关于简单意味着什么的隐含承诺"——三层翻译做完之后,你对机器学习"客观性"的看法会改变吗?