第21章:学习作为逆推断——泛化是压缩的另一种说法
模型"学到了东西"的形式含义是:它找到了更短的描述。
第20章结尾留下了一个问题:启发函数能否自动从数据中发现?PAC 学习保证了学习的可能性,但它没有说学习是什么——它只是描述了一个黑盒,告诉你这个黑盒的输出具有什么性质。
这一章要打开这个黑盒。
学习,在最抽象的意义上,是从一批观测——例子、数据、经验——中推断出一条可泛化的规律。这个推断过程若要有形式含义,就必须回答:相比观测本身,推断出的规律多了什么、少了什么?它为什么能从见过的例子,说出未见例子的事情?
答案的关键词是压缩。
21.0 压缩侦探游戏:从样本中找回规律
学习不是把数据背下来。背下来太容易,也太没用。真正的学习像侦探破案:桌上有一堆线索,你必须找出一条比线索本身更短的解释。
游戏开始时,自然交给你一串样本:
你可以提交一个假设
压缩侦探的评分规则是:
前一项是描述假设本身需要多少比特;后一项是在假设给定之后,描述数据还需要多少比特。最好的假设不是最复杂的,也不是最贴合训练集的,而是总描述长度最短的那个。
这个游戏的形式化骨架
- 状态空间:样本集
、假设类 、编码方案 。 - 合法动作:选择一个假设
,并用它压缩数据。 - 转移规则:从观测样本反推候选规律,比较
。 - 胜利条件:找到能压缩训练数据、并在未见样本上保持低误差的假设。
- 失败模式:死记硬背样本;或选择过强的归纳偏置,把世界压缩成错误的形状。
这个游戏把泛化的秘密说得很直白:你能泛化,是因为你找到了可压缩的结构。如果数据完全随机,就没有短规律可找;如果你找到了一条能解释大量样本的短规律,它很可能抓住了某种真实结构。
但这里也有危险。压缩需要编码方案,而编码方案就是归纳偏置。你以为自己在"从数据中学习"——其实你一直带着一把剃刀进场:什么算简单、什么算复杂,你的表示系统在你到来之前就决定了。
压缩侦探游戏冷酷的地方在于:没有偏置,就没有学习。完全中立的学习者只能背诵样本;要泛化,你就必须偏爱某些规律胜过另一些。机器学习课喜欢把这叫"模型选择"。说得太轻了。你实际上是在选择你愿意相信世界具有什么形状。
21.0.5 在代码中玩这个游戏
评分规则小到可以直接计算。下面的程序用最小二乘法把四条候选规律拟合到十个样本上,按
#!/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 欠定性的具体面孔
用同一个数据集,三个不同的学习者会给出三条不同的规律。这不是比喻——拿起笔算一算。
数据:
学习者 A(线性回归):它的假设空间是所有线性函数
学习者 B(二次回归):它的假设空间是所有二次函数
学习者 C(10 次多项式):它的假设空间是所有次数不超过 10 的多项式
谁是对的?如果真实规律确实是
关键点:三个学习者永远无法通过"看更多数据"来裁定谁对。给定任意有限点集,总存在一个 10 次多项式完美拟合它们。你可以在训练数据上完美、同时在测试数据上糟糕。数据本身不会告诉你——选择线性、二次还是 10 次多项式,是你的选择,不是数据的选择。
这就是归纳偏置的本质:它不是从数据中学来的;它是你在看数据之前就带进问题里的东西。像一副眼镜,你在看之前就戴上了。不同的眼镜,不同的规律。
很多人听到"欠定性"时会点头,然后又回去用默认超参数训练模型。欠定性不是一个需要你"理解"的理论事实——它是在每一次训练中都会发生的操作性问题。你选择模型架构的那一刻,欠定性已经被部分解决了——但你不一定知道自己选了哪种偏置,也不一定知道它是否适合当前的数据。知道自己有偏置,却不知道是哪种偏置,这比根本不知道有偏置更危险——因为你以为自己掌控着局面,其实并没有。
归纳偏置不是技术选项,而是形而上学承诺。你选择线性模型,就是在断言"规律是线性的";你选择深度网络,就是在断言某种关于特征层级的结构假设。大多数机器学习课程把这叫做"调超参数",把形而上学承诺埋进了工程操作里。这是在回避一个真实的问题,而不是解决它。
21.2 奥卡姆剃刀的形式化
最古老、最直观的归纳偏置是奥卡姆剃刀:偏爱更简单的解释。
但"简单"是什么意思?
Kolmogorov 复杂度给出了一个答案。
定义(Kolmogorov 复杂度):字符串
Kolmogorov 复杂度:用压缩程序的长度衡量复杂度(前人工作:Kolmogorov, 1965)
Kolmogorov 复杂度
直觉例子:
- "前一百万个自然数" -> 一段很短的程序就够了(
for i in range(1000000): print(i)),很小 - 随机生成的一百万位数字 -> 没有比"把数字本身列出来"更短的描述,
字符串长度
重要的不可计算性:
为什么仍然有用? 即使不可计算,Kolmogorov 复杂度也提供了一个理论标准——衡量"简单性"的绝对基准。实践中用 MDL 作为近似(用一个真实的压缩算法代替最短程序)。
在这个语言里,"简单"意味着"Kolmogorov 复杂度低","偏爱更简单的解释"意味着"选择
21.2.5 动手:手工估计 Kolmogorov 复杂度的上界
例 1:
- 程序:
for i in range(4): print("01") - 程序长度(采用某种合理的编码):约 20-30 个字符(Python 语法开销 + 循环体)
约 30
例 2:
- 程序:
for i in range(1000): print("01") - 程序长度:约 35 个字符(只改了循环次数)
约 35
注意:数据从 8 个字符增长到 2000 个字符,程序只从约 30 增长到约 35。这就是压缩的力量——规律越长,回报越大。
例 3:
- 程序:
mp.pi.n(digits=1000)(依赖数学库) - 程序长度:约 40 个字符
约 40(但这依赖于数学库;库本身也得计算在内。我们可以接受这一点—— 的定义相对于固定通用图灵机,而数学库可以作为这台机器的一部分)
例 4:
- 程序:你只能
print("the first 1000 characters of the random string, verbatim") - 程序长度
+ 一点开销 字符串本身的长度
这四个例子揭示了一个关键直觉:
但这里有一个微妙的点:
估计 Kolmogorov 复杂度的上界本身就是一堂速成课:你发现一个模式 -> 用你能写出的最短程序描述这个模式 -> 程序的长度就是你对"这个字符串有多复杂"的最大胆断言。但你也可能漏掉了某个模式——你找到的程序只是一个上界。
这就是最小描述长度(Minimum Description Length,MDL)原理的核心:
MDL 和贝叶斯推断是同一个想法的两种语言。若假设
奥卡姆剃刀,在贝叶斯语言里是先验对简单性的偏好;在 MDL 语言里是最短描述长度的选择。它们是同一个数学结构,穿着不同的衣服。
21.3 泛化就是压缩
MDL 原理揭示了一个深刻的等价:泛化能力等价于压缩能力。
为什么?
一个假设
反过来,一个完美记住训练数据的模型没有做任何压缩——它只是把数据原样存了起来。这样的模型在训练数据上表现完美,却对新数据没有预测能力,因为它没有找到规律,只是归档了例子。
这正是第 5 章(上卷)"过拟合"的形式化:过拟合是没有压缩的记忆;泛化是有效的压缩。
用 Kolmogorov 复杂度的语言,泛化的量可以被度量:假设训练数据从
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 的近似——但你必须知道它只是近似,不是真正的剃刀。
给定一个字符串
这意味着 MDL 在最纯粹的形式下本身不可计算。实践中的 MDL 是一种近似:用某个固定的编码方案代替通用图灵机,用可计算的描述长度代替不可计算的 Kolmogorov 复杂度。
不同的近似方案对应不同的归纳偏置:
- 决策树学习:假设空间是决策树;描述长度是树的深度或节点数。它偏爱小树,即简单的决策规则。
- 线性模型:假设空间是线性函数;描述长度是系数的范数。L1 正则化偏爱稀疏系数(大多数为零);L2 正则化偏爱小系数。
- 神经网络:假设空间是特定架构的网络;"描述长度"由参数值和网络结构共同决定。这个描述长度非常难以确定——理论与实践之间存在巨大的空白地带。
每一种学习算法都隐含地选择了一种归纳偏置——一种对"简单意味着什么"的特定理解。在大多数机器学习课程中,这个选择以"超参数调优"的名义被处理——但它实际上是一种关于"应该偏爱哪类规律"的形而上学承诺。
21.4.5 Rademacher 复杂度:另一把尺子
VC 维是一个组合量,对于许多现代假设空间(如深度神经网络),精确计算 VC 维非常困难。Rademacher 复杂度提供了另一种视角——它直接衡量一个假设类拟合随机噪声的能力。
考虑样本集
直觉:如果
与 VC 维的关系:VC 维给出最坏情况界;Rademacher 复杂度给出数据依赖的界——它在手头的具体样本集
把 VC 维与 Rademacher 复杂度并排看:VC 维问"你能打散多少个点"(纯组合的);Rademacher 复杂度问"在这个特定数据集上,你能多好地拟合随机噪声"(数据依赖的)。它们从不同角度量化同一件事:假设空间容纳随机模式的能力。容量越大,需要的样本越多;样本不足时,模型可能学到的是噪声而不是信号。
21.5 逆推断的两个困难
学习作为逆推断,面临两个根本困难,二者都不是数据本身能解决的。
第一个困难:欠定性。如前所述,有限数据与无穷多个假设相容,因此需要归纳偏置在其中做选择。归纳偏置是从外部输入的;它不是从数据中推断出来的。学习问题的解取决于假设空间的选择——而这个选择不在学习算法的管辖范围之内。
第二个困难:分布偏移。PAC 学习假设训练数据与测试数据来自同一分布
这两个困难是学习理论的根本限制,不是算法缺陷。它们意味着:每个学习系统都在某些假设下工作;一旦离开这些假设,保证就消失了。
这个结构与第 14 章的形式系统非常相似:形式系统在其公理之内是可靠的,越过公理就没有保证;学习系统在其假设之内是可靠的,越过假设就没有保证。两个系统的可靠性都依赖于一种无法从内部验证的外部承诺。
21.5.5 为什么这个困难无法被数据解决
用一个极端的例子把这个问题钉死。
假设你有一个学习器,任务是预测序列的下一个元素。训练数据是:
三个学习者各自学到不同的规律:
- 学习者 A:输出
(偶数) - 学习者 B:输出
(这个公式在前几项也给出 2, 4, 6, 8……不: , , ……等等,这不对: ,但序列的第 3 项是 6。所以这个不行。)
让我重写——正确的例子更重要:
序列:
- 学习者 A:
(自然数) - 学习者 B:
"第 个非负整数"(与 A 相同) - 学习者 C:当
时 ,此后
对前 5 个元素(0,1,2,3,4),三个学习者完全一致。你无法从数据中区分它们。但对第 1001 个元素的预测:A 和 B 预测 1000,C 预测 2000。
这个例子暴露了什么? 有限数据永远无法唯一确定规律——欠定性不是"数据还不够",而是"强到即使在数据极限下也依然存在的欠定性"。唯一的出路是引入归纳偏置——断言 C"更复杂",因而比 A 差。但这个断言不是从数据中来的;是你带进来的。
还要注意:如果真实规律确实是 C(比如序列在第 1000 个元素之后突然跳变),那么你的归纳偏置——对 A 的偏爱——会让你系统性地犯错。归纳偏置不是免费午餐:它在某些世界里帮你,在另一些世界里害你。而你无法从训练数据判断自己活在哪个世界。
回到压缩侦探游戏:侦探从不会空手进入现场。他们随身带着一套编码方案,一套关于"什么算短描述"的预设。于是同一堆线索,在不同的侦探眼中导向不同的规律:线性模型看见直线,决策树看见分叉,神经网络看见层级表示。所谓学习,不是数据自己开口说话,而是数据被迫在某种压缩语言里回答。
这句话令人不适,但必须保留:学习系统的失败,往往不是因为它没能找到规律——而是因为它在错误的游戏规则下,找到了一条过于漂亮的规律。
21.6 学习与推断的统一图景
把本章内容放进下卷的框架里。
第 14 章建立了推断的句法机器。第 15 章发现这台机器有内在限制——某些真命题无法从内部证明。第 16 章修改了一条结构规则,得到一种新的推断。第 17 章把真值扩展到
第 21 章所做的是把"学习"嵌入这个框架。学习是逆推断——从观测出发,反推规律。MDL 原理给出逆推断的基本规则:最短的解释。PAC 框架给出逆推断的质量保证:以高概率近似正确。
但这个统一图景还缺最后一块:一旦推断系统足够大、足够复杂,它的"推断"就开始包含关于自身的命题——关于它能学到什么、学不到什么,以及它自身的归纳偏置是什么。此时,第 15 章的哥德尔结构重新出现:一个足够强的推断系统无法完全推断自身。
21.6.5 平行结构:学习的不完备性
把第 14–15 章的逻辑不完备性与第 20–21 章的学习不完备性并排放在一起。这两个论证共享一种深层结构:
| 形式系统(第 14–15 章) | 学习系统(第 20–21 章) | |
|---|---|---|
| 起点 | 公理 + 推理规则 | 训练数据 + 归纳偏置 |
| 内部可做 | 生成所有定理(句法的) | 搜索假设空间(学习) |
| 外部必需 | 语义解释(模型论) | 泛化保证(PAC/MDL) |
| 无法内化 | 系统一致性的证明 | 归纳偏置的正当性 |
| 边界行为 | 存在为真但不可证的命题 | 存在可学习但需要外部偏置的概念 |
这不是"有点像"。这是同一个数学结构在两个领域中的实例化。在两种情况下:
- 系统内部的合法操作(证明 / 学习)可以无限进行
- 但系统无法从内部验证这些操作的正确性条件(一致性 / 泛化)
- 正确性条件需要一个外部视角——形式系统需要模型,学习系统需要分布假设
最深的问题:如果归纳偏置本身成为学习对象——元学习——这个限制能被打破吗?
元学习确实能在任务分布上学到一种偏置,使对新任务的适应更快。但元学习自身也有归纳偏置:它在评估"哪种偏置在任务分布上表现好"时,携带着关于任务分布的假设(如"任务共享结构")。如果你把元学习本身也变成学习对象(元元学习),这条链没有终点——每一层都需要自己的归纳偏置,而每一层的偏置都必须从外部输入。
这与哥德尔结构完全平行:把
这是第 22 章的入口。第 23 章接着把收敛速率变成涌现的对数曲线。
悬而未决
Kolmogorov 复杂度不可计算——那 MDL 还有意义吗? Kolmogorov 复杂度的不可计算性使它成为一个理想,而不是一个算法。但数学中充满了这样的理想:最优决策、完美信息、无穷精度。理想不需要可计算;它需要充当基准——告诉我们实际算法离最优有多远。MDL 的可计算近似是对这个理想的有限逼近;正是理想本身的存在,才赋予"近似"一词意义。
泛化真的等价于压缩吗? MDL 框架暗示:不能压缩训练数据的模型不会泛化;能压缩的模型则会泛化。但这个等价在深度学习实践中并不总是成立——一些大规模模型在"记住"数据的同时也能很好地泛化。这一张力指向一个未解的理论问题:深度学习的泛化机制究竟是什么?
归纳偏置能被学习吗? 如果学习是逆推断,那么"什么构成一个好的假设空间"本身能被学习吗?元学习试图在任务分布上学到一个好的归纳偏置,使模型更快适应新任务。但元学习本身也有自己的归纳偏置——这是一个无穷倒退,还是在某个层次上会停止?
思考题
★ 热身
下面两个字符串,哪一个的 Kolmogorov 复杂度更低?给出你的直觉和一句话理由——不需要计算具体数值。
0101010101010101010101010101010101010101(40 个字符,0 和 1 交替)1101001000011010110101010001010001000010(40 个随机字符)
再问一个问题:一个"完全随机"的字符串——它的 Kolmogorov 复杂度大致是多少?与字符串本身的长度相比如何?
★★ 推导
压缩与泛化:一个模型在训练集上误差为零,但在测试集上误差很大(过拟合);另一个模型在训练集上误差 5%,在测试集上也是 5%(良好泛化)。用 MDL 的语言描述二者的差异:哪一个压缩了数据?哪一个记住了数据?每个模型的"描述长度"由什么构成?
让归纳偏置显性化:线性回归、决策树、神经网络(带 L2 正则化)——每种学习算法隐含了什么归纳偏置?用"偏爱什么样的规律"来描述每一种。每种偏置在什么类型的数据上会系统性地失败?
★★★ 挑战
Kolmogorov 复杂度不可计算(因为它等价于停机问题)。这意味着:没有任何算法能在有限时间内判定任意两个假设中哪一个更简单。
但 MDL 在实践中被使用,用的是可计算的近似。试着列出至少两种可计算的"描述长度"近似方案,并分析:每种近似隐含地假设了什么样的归纳偏置?不同的近似方案在什么时候会给出不同的"最优假设"?
这道题的目的:把"超参数选择"翻译成"归纳偏置选择",再翻译成"关于简单意味着什么的隐含承诺"——三层翻译做完之后,你对机器学习"客观性"的看法会改变吗?
