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

第20章:启发式的形式合同——"差不多对"的精确数学定义 ​

可采纳性不是一个工程妥协。它是一个数学承诺。


第19章的结论令人沮丧:许多推理问题在计算意义上是根本困难的。不是算法不够好,而是问题本身的几何形状决定了没有捷径。

但人类和机器一直在解决这些"困难"问题。不精确,不总是最优,但通常足够好,足够快。

这里藏着一个问题:"足够好"是什么意思? 如果答案是任意的,那么任何不崩溃的算法都可以自称"启发式"。但如果"足够好"有精确的数学含义,那么启发式就不是工程妥协,而是一份带合同的承诺:承诺什么,以什么为代价,在什么条件下兑现。

这正是本章要做的事:把这份合同写清楚。


20.0 乐观制图师游戏:启发式必须签合同 ​

第19章告诉我们,很多迷宫太大,不能指望蛮力穷举。于是我们雇一位制图师。制图师不能告诉你完整路线;在每个路口,他只能给出一个估计:从这里到终点大概还有多远。

这就是启发函数 h(n)。

但这位制图师必须签合同。第一份合同叫可采纳性:你可以乐观,但不能夸大困难。也就是说,估计距离不能超过真实最短距离:

h(n)≤h∗(n)

如果制图师低估了距离,搜索只是多走几步。如果制图师高估了距离,搜索可能完全放弃真正的最优路径。第二份合同叫一致性:相邻路口之间的估计必须满足三角不等式——制图师不能今天说"我们快到了",走一步之后突然又说"还远得很"。

这个游戏的形式化骨架

  • 状态空间:搜索图中的节点、已知代价 g(n)、启发估计 h(n),以及一个优先队列。
  • 合法动作:展开 f(n)=g(n)+h(n) 最小的节点,然后更新它的后继。
  • 转移规则:从开放列表取出节点 n,把每个后继 n′ 加入或更新,代价为 g(n′)=g(n)+c(n,n′)。
  • 胜利条件:在可证明的保证下找到最优路径,或者得到近似比 / PAC 式的质量界。
  • 失败模式:启发式没有合同——它只是"看起来不错",最终给出最快的错误答案。

这个游戏把"足够好"变得精确。没有合同的启发式只是运气;有合同的启发式才是数学对象。可采纳性、一致性、近似比、PAC 保证——这些都是不同合同的不同条款。

启发式的尊严不在于它总能给出最优答案,而在于它诚实地说明:我承诺什么,不承诺什么;在哪些条件下我可靠,在哪些条件下我会失败。

乐观可以是美德,也可以是诈骗。A* 允许启发函数乐观,因为乐观让你继续探索;它不允许启发函数自大,因为自大让你过早放弃一条真正的路。启发式的全部伦理,就藏在这条不等式里。

20.0.5 用代码玩这个游戏 ​

20.2.5 节在一个六节点图上手工追踪了一次 A* 搜索。下面的程序用同一个算法把同一个图跑了两遍——一遍用书里的可采纳启发式,一遍在节点 A 处加一个高估。同样的迷宫,同样的算法:一个返回最优路线,另一个给出最快的错误答案。

python
#!/usr/bin/env python3
"""
optimistic_cartographer.py -- the Optimistic Cartographer Game of Ch. 20.
Book reference: The Reasoning Kingdom, Volume 2, Chapter 20, Section 20.0
"The Optimistic Cartographer Game: Heuristics Must Sign a Contract."

The maze is too big for brute force, so we hire a cartographer who, at
every intersection, estimates how far the goal still is: the heuristic
h(n). This program runs A* on the exact six-node graph the book traces
by hand in Section 20.2.5, with two cartographers:
  * the honest one, whose estimates never exceed the true distance
    (admissible: h <= h*) -- the contract of Section 20.0;
  * the arrogant one, who overestimates at node A -- no contract.
Same maze, same algorithm: one returns the optimal route, the other
delivers the fastest wrong answer. That is the whole ethics of
heuristics, hiding inside one inequality.
Run:  python3 optimistic_cartographer.py
"""
import heapq

# The book's graph, Section 20.2.5: S (start), A, B, C, D, G (goal).
EDGES = {
    "S": (("A", 1), ("B", 4)),
    "A": (("C", 3), ("D", 2)),
    "B": (("D", 2),),
    "C": (("G", 2),),
    "D": (("G", 4),),
    "G": (),
}

HONEST_H = {"S": 5, "A": 4, "B": 4, "C": 2, "D": 2, "G": 0}
ARROGANT_H = {"S": 5, "A": 10, "B": 1, "C": 2, "D": 2, "G": 0}

START, GOAL = "S", "G"

def astar(edges, h, start, goal):
    """A* on a graph; returns (path, cost, expanded_in_order)."""
    heap = [(h[start], 0, start, [start])]
    best_g = {start: 0}
    expanded = []
    while heap:
        _, g, node, path = heapq.heappop(heap)
        if g > best_g.get(node, float("inf")):
            continue
        expanded.append(node)
        if node == goal:
            return path, g, expanded
        for nxt, cost in edges.get(node, ()):
            ng = g + cost
            if ng < best_g.get(nxt, float("inf")):
                best_g[nxt] = ng
                heapq.heappush(heap, (ng + h[nxt], ng, nxt, path + [nxt]))
    return None, None, expanded

def trace(name, h, expected):
    path, cost, expanded = astar(EDGES, h, START, GOAL)
    print(f"\n{name}:")
    print(f"  route found:  {' -> '.join(path)}")
    print(f"  total cost:   {cost}")
    print(f"  nodes expanded in order: {' -> '.join(expanded)}")
    assert path == expected["path"] and cost == expected["cost"]

def demo():
    print("=" * 70)
    print(" THE OPTIMISTIC CARTOGRAPHER GAME -- two cartographers, one maze")
    print(" The Reasoning Kingdom, Volume 2, Chapter 20 (Sec. 20.0, 20.2.5)")
    print("=" * 70)
    print("\nThe maze (the same six nodes the book traces by hand):")
    print("  S->A:1  S->B:4  A->C:3  A->D:2  B->D:2  C->G:2  D->G:4")
    print("\nThe honest cartographer -- h never exceeds the true distance:")
    print("  h: S=5, A=4, B=4, C=2, D=2, G=0   (h(n) <= h*(n) everywhere)")
    trace("honest cartographer (admissible)", HONEST_H,
          {"path": ["S", "A", "C", "G"], "cost": 6})
    print("  optimal route S->A->C->G, cost 6 -- exactly what the hand")
    print("  trace in the book found.")
    print("\nThe arrogant cartographer -- one lie, at node A:")
    print("  h: S=5, A=10, B=1, C=2, D=2, G=0   (h(A)=10 > h*(A)=5: contract broken)")
    trace("arrogant cartographer (inadmissible)", ARROGANT_H,
          {"path": ["S", "B", "D", "G"], "cost": 10})
    print("  route S->B->D->G, cost 10. The overestimate at A made the")
    print("  search abandon the truly optimal path. Optimism keeps you")
    print("  exploring; arrogance makes you give up on a real path early.")
    print("  Same maze, same algorithm -- one inequality of difference.")
    print("=" * 70)

if __name__ == "__main__":
    demo()

20.1 两种近似如何失败 ​

先看两种近似方案。它们听起来都符合直觉,也都会在某些情况下出错。

方案一:贪心算法。 每一步都做局部看起来最好的选择,绝不回头。在旅行商问题里,总是走向最近的未访问城市;在图着色问题里,总是给当前顶点分配与邻居不冲突的最小颜色编号。

贪心算法通常很快(多项式时间),但结果可能很糟——有时比最优解差一个指数因子。贪心没有承诺,它只是"看起来不错"。

方案二:随机搜索。 在解空间里随机采样,报告找到的最好结果。足够随机,跑足够多次,也许就能找到一个好解。

随机搜索也没有承诺——"也许"不是合同。在最坏情况下,好的解极其稀疏,随机搜索可能永远找不到。

现实世界中有很大一部分系统靠的就是"也许"——随机重启、反复采样、保留最好结果。这些方法在实践中有时有效,但你不知道它们什么时候会失效,也不知道失败的概率。没有合同,就没有失败条件——你甚至无法判断算法是否在工作。"有时候有效"不是保证,是运气。

这两种方案的共同问题:它们都没有给出"差多远"的可证明界。而这个界,正是启发式合同所要求的。

一个具体的失败现场 ​

拿一个极其简单的旅行商问题——4 个城市,边权如下——你就能亲眼看到贪心和随机的区别:

Cities: A, B, C, D
Edge weights (distances):
  A-B: 10, A-C: 15, A-D: 20
  B-C: 35, B-D: 25
  C-D: 30
Optimal Hamiltonian cycle: A->B->D->C->A, total cost = 10+25+30+15 = 80

贪心(最近邻)从 A 出发:A 到 B(10,最短)-> B 到 D(25,从 B 出发除 A 外最短,因为 B 到 C 是 35)-> D 到 C(30)-> 被迫回到 A(15)。路线:A->B->D->C->A,代价 = 10+25+30+15 = 80。这次碰巧对了,因为图太小。

但换一个起点:从 B 出发 -> B 到 A(10)-> A 到 C(15)-> C 到 D(30)-> 被迫回 B(35)。路线:B->A->C->D->B,代价 = 10+15+30+35 = 90。次优。而这只是 4 个城市;城市多起来,贪心的误差可以指数级膨胀。

随机搜索:随机采样 100 条回路;最好的可能是 85,也可能是 110——没有承诺。再跑一次,每次答案都不同。

两者都没有合同。贪心在某些图上对,随机永远不确定。缺的正是那条不等式:h(n)≤h∗(n)。有了它,你才知道乐观的边界在哪里。

看到了吗?贪心在这个小图上从 A 出发是对的,从 B 出发就错了。你不能用"它在 A 上对了"来证明算法有效——没有合同的算法不是"大致有效",而是"你不知道它什么时候失效"。这是会致命的。


20.2 可采纳性:永远不高估 ​

搜索中最经典的启发式框架是 A* 算法。它的核心是一个启发函数 h(n),估计从当前状态 n 到目标的代价。

A* 维护一个优先队列,每一步展开估计总代价 f(n)=g(n)+h(n) 最小的节点,其中 g(n) 是从起点到 n 的已知实际代价,h(n) 是从 n 到目标的估计代价。

这个算法能找到最优解的条件,精确地落在 h 的一个性质上:

定义(可采纳性):启发函数 h 是可采纳的,如果对每个节点 n,

h(n)≤h∗(n)

其中 h∗(n) 是从 n 到目标的真实最优代价。

可采纳性的含义:h 永远不高估。它可以低估——低估就是乐观,而乐观意味着这条路径会继续被探索。但如果 h 高估,算法可能过早放弃一条实际上最优的路径。

定理(A 完备性)*:如果启发函数 h 可采纳,那么只要最优解存在,A* 就保证能找到它。

这是启发式合同的第一种形式:给我一个永远不高估的估计,我保证给你最优解。代价是你必须花时间构造这个估计,而且算法可能需要探索更大的搜索空间。

一个常见错误是把真实代价的粗略上界当作启发式——这自然会高估,从而破坏可采纳性。例如,在地图搜索中,如果用直线距离作为 h,这是可采纳的(直线距离永远不会超过实际路线距离)。但如果在弯曲道路上某个估计会高估,它就不可采纳。可采纳性的违反通常并不明显——它取决于问题的具体结构。

20.2.5 实操:追踪一次完整的 A* 搜索 ​

光看定义不够。下面是一个 6 节点有向图;让我们逐步追踪 A* 的每一步。拿张纸,跟着画。

Nodes: S (start), A, B, C, D, G (goal)
Edges (S->node, cost):
  S->A: 1,  S->B: 4
  A->C: 3,  A->D: 2
  B->D: 2
  C->G: 2
  D->G: 4

Heuristic function h (estimated cost to G):
  h(S)=5, h(A)=4, h(B)=4, h(C)=2, h(D)=2, h(G)=0

True optimal cost h* (verifiable via reverse Dijkstra):
  Actual: S->A->D->G: 1+2+4=7; S->B->D->G: 4+2+4=10; S->A->C->G: 1+3+2=6
  Shortest: S->A->C->G = 6, so h*(S)=6, h(S)=5 ≤ 6 ✓ admissible
  h*(A)=5 (A->C->G=3+2=5), h(A)=4 ≤ 5 ✓
  h*(B)=6 (B->D->G=2+4=6), h(B)=4 ≤ 6 ✓
  h*(C)=2, h(C)=2 ✓ (exactly precise)
  h*(D)=4, h(D)=2 ≤ 4 ✓
  h*(G)=0, h(G)=0 ✓

For every node, h(n) ≤ h*(n) holds, so h is admissible.

追踪 A*:

初始:优先队列 = [(S, f=0+5=5)]。g(S)=0。

第 1 步:展开 S(f=5 最小)。后继:

  • A:g=1,f=1+4=5 -> 加入队列
  • B:g=4,f=4+4=8 -> 加入队列 队列:[(A,5), (B,8)]

第 2 步:展开 A(f=5 最小)。后继:

  • C:g=1+3=4,f=4+2=6 -> 加入
  • D:g=1+2=3,f=3+2=5 -> 加入 队列:[(D,5), (C,6), (B,8)]

第 3 步:展开 D(f=5 最小)。后继:

  • G:g=3+4=7,f=7+0=7 -> 加入 队列:[(C,6), (G,7), (B,8)]

第 4 步:展开 C(f=6 最小)。后继:

  • G:g=4+2=6,f=6+0=6 -> 更新 G(已经有一个 f=7 的版本;新的 f=6 更好,替换掉它) 队列:[(G,6), (B,8)]

第 5 步:展开 G(f=6 最小)。G 是目标;找到路径 S->A->C->G,总代价 6。

注意:在第 3 步,A* 没有走 S->A->D->G(总代价 = 7),因为 D 被展开后,G 的 f 是 7,而队列中 C 的 f=6 优先级更高。A* 正确地跳过了次优路径。

现在,如果我们把 h 改成不可采纳的呢?设 h′(A)=6(一个高估,因为真实 h∗(A)=5)。那么:

  • 展开 S 后,A 的 f=1+6=7,B 的 f=4+4=8
  • 队列:[(A,7), (B,8)]
  • 展开 A(f=7),D 的 f=5,C 的 f=6
  • 队列:[(C,6), (D,5), (B,8)]
  • 展开 C,G 的 f=6……最终仍然找到了最优解,但这只是因为图太小。

在更复杂的图上,高估会让 A* 过早判定某条路径"不值得探索"——而那条路径恰好是最优的。可采纳性不保证效率;可采纳性保证你不会错过最优解。丢掉它,最优解就可能从你手中溜走,而你甚至永远不知道。

仔细看第 3 步:展开 D 时,队列里有 C(f=6) 和 D(f=5)。A* 选了 D,因为 D 更乐观。乐观让 A* 愿意冒险,但也让它在看到更好的路径时能及时掉头——因为乐观只会向下修正,绝不会向上。如果 h 是自大的(高估),A* 会过早丢弃某些节点,再也不回头看。乐观是探索的燃料;自大是错过的原因。


20.3 一致性:三角不等式的约束 ​

可采纳性保证了最终结果的质量,但 A* 的效率取决于 h 的另一个性质。

定义(一致性):启发函数 h 是一致的,如果对每个节点 n 及其每个后继 n′,

h(n)≤c(n,n′)+h(n′)

其中 c(n,n′) 是从 n 到 n′ 的实际边代价。

这是一个三角不等式:从 n 到目标的估计代价,不超过先走到 n′、再从 n′ 走到目标的代价。直观上,一致性说的是:你对每个节点的估计是"连贯的"——不会出现走一步之后,估计值突然暴涨的情况。

一致性蕴含可采纳性(你可以验证这一点),但反过来不成立。一致性是更强的条件。

在一致性下,A 展开的每个节点上 f 都是非递减的。* 这保证了:当 A* 第一次到达目标节点时,它找到的路径就是最优路径——无需再搜索下去。一致性把 A* 从"最终找到最优"推进到"尽可能早地找到最优"。

这两个性质——可采纳性和一致性——就是启发式合同的精确数学内容。有了它们,"启发式"就不再是随机猜测,而是在可证明界内工作的估计机制。

回到乐观制图师游戏:可采纳性要求制图师不能把近路说成远路;一致性要求制图师不能在相邻路口之间来回改口。A* 的聪明之处不是"相信直觉",而是只相信签过合同的直觉。没有合同,启发式只是一个油嘴滑舌的向导;有了合同,启发式才成为形式系统里的合法动作。

20.3.5 一致性被违反时:A* 的困惑 ​

用 20.2.5 的同一个图,构造一个可采纳但不一致的 h:

设 h″(S)=5,h″(A)=4,h″(B)=5,h″(C)=2,h″(D)=1,h″(G)=0。

检查可采纳性:对每个节点,h″(n)≤h∗(n) 吗?

  • h″(B)=5≤6 ✓,h″(D)=1≤4 ✓。是的,可采纳。

检查一致性:对每条边 (n,n′),h″(n)≤c(n,n′)+h″(n′) 吗?

  • 边 B->D:h″(B)=5,c(B,D)+h″(D)=2+1=3。5≤3 吗?否。

发生了什么?从 B 看,到 G 的估计是 5;但从 D(B 的下一步)看,估计突然变成了 1。制图师在 B 说"还远",走一步到 D 后又说"快到了"。这种反复让 A* 困惑:

从 S 出发:A(f=5),B(f=4+5=9)。选 A。然后 D 的 f=1+2+1=4。选 D。然后 G 的 f=3+4+0=7。选 C(f=6)。C->G(f=6)。找到了最优路径 S->A->C->G,代价 6。

看起来没问题?但问题藏在这个细节里:D 被展开后,队列里是 C(f=6) 和 G(f=7,经由 D 得到)。如果我们之后又发现另一条到 D 的更短路线(比如 S->B->D 代价更小?不——S->B->D 是 4+2=6,比 S->A->D 的 3 更差),而 h″ 又不一致,我们可能就需要重新展开已经展开过的节点。一致性保证 f 非递减,所以第一次到达目标就是最优;而不一致时,A* 可能不得不在目标节点上继续搜索,直到 f 超过当前最优代价。

在更大规模的搜索中,不一致的代价是巨大的:A* 可能需要重新展开节点,算法退化为接近 Dijkstra 的效率。一致性不是装饰——它是支撑 A* 效率的合同。

不一致的启发式就像一个反复无常的导游。他在 B 告诉你还剩 5 公里;你走到 D,他却说其实只剩 1 公里。加在一起,B->D 这一段他只算了 2 公里(5 -> 1),而实际距离也恰好是 2 公里——"刚好对上"。但如果到了 D,他突然又说还剩 4 公里(到下一个路口),你就会开始怀疑:他到底知不知道自己在说什么?A* 的怀疑是数学层面的:不一致时,f 可能下降,算法不再保证第一个解就是最优。


20.4 近似比:最坏情况的保证 ​

当最优性作为一个目标讲得通时,A* 工作得很好。但对许多 NP 完全问题来说,即使允许近似,最优解本身也很难找到。这时就需要另一种合同:近似比。

定义(近似算法):对于一个最小化问题,如果算法 A 在任意实例上总是返回一个代价至多为最优解代价 ρ 倍的解,那么称 A 为 ρ-近似算法,ρ 称为它的近似比。

近似比是启发式合同的最坏情况版本:无论输入是什么,输出的质量都保持在最优解的 ρ 倍以内。ρ=1 是精确解;ρ=2 意味着"至多是最优的两倍"。

一些著名的结果:

  • 顶点覆盖:存在 2-近似算法(找一个极大匹配,取两端点)。
  • 旅行商问题(度量版本):存在 1.5-近似算法(Christofides 算法,1976 年)。这个结果保持了近半个世纪,直到 2020 年才被略微改进。
  • 旅行商问题(一般版本,不满足三角不等式):若 P ≠ NP,则对任意常数 ρ,都不存在多项式时间的 ρ-近似算法。

最后一个结果是关键:对某些问题,近似本身就是 NP 难的。允许误差并不总是让问题变简单。近似比有自己的信息论下界,这个下界来自问题的内在结构,与任何具体算法无关。

一般 TSP 的不可能性证明用的是归约:如果存在一个多项式时间的 ρ-近似算法,我们就可以用它来判定哈密顿回路是否存在——而哈密顿回路问题是 NP 完全的。这个归约说明,任何足够好的近似都会蕴含精确求解的能力。问题的内在结构,在近似层面也留下了指纹。

20.4.5 实操:顶点覆盖的 2-近似——极大匹配的力量 ​

顶点覆盖问题:给定图 G=(V,E),找出最小的顶点集合 C⊆V,使得每条边至少有一个端点在 C 中。这是 NP 完全问题。但存在一个简单的 2-近似算法——记住,2 意味着你找到的集合最多是最优集合的 2 倍大。

算法(极大匹配法):

  1. 找图的一个极大匹配 M(无法再加入任何边的匹配)
  2. 输出 M 中每条边的两个端点

为什么这是 2-近似?

设 M 是找到的极大匹配,有 k 条边。输出集合 C 包含这 k 条边的 2k 个端点。

  • 下界:最优顶点覆盖至少需要 k 个顶点。因为 M 中的 k 条边互不共享端点(这正是匹配的定义),覆盖这 k 条边至少需要 k 个顶点——每条边至少要选一个端点,而不同边的端点不能共享。所以 OPT≥k。
  • 上界:我们输出了 2k 个顶点,|C|=2k≤2⋅OPT。✓

为什么极大(而不是最大)就够了? 一个简单的贪心构造极大匹配:遍历所有边;如果当前边的两个端点都还没有被匹配覆盖,就把这条边加入匹配。结果不一定是最大匹配(边数最多的匹配),但一定是极大的(无法再加入边)。对于 2-近似,极大就够了。

一个具体例子:

Graph: vertices {1,2,3,4,5}
Edges: (1,2), (2,3), (3,4), (4,5), (1,5)

贪心极大匹配(按顺序遍历边):

  • 遇到 (1,2):1 和 2 都未匹配 -> 加入 M。M=
  • 遇到 (2,3):2 已匹配 -> 跳过
  • 遇到 (3,4):3 和 4 都未匹配 -> 加入 M。M=
  • 遇到 (4,5):4 已匹配 -> 跳过
  • 遇到 (1,5):1 已匹配 -> 跳过

输出 C = {1,2,3,4},大小为 4。

最优解是什么?这个图是一个 5-环。覆盖全部 5 条边至少需要 3 个顶点(每隔一个取一个;{2,4,5} 覆盖每条边)。所以 OPT=3。我们的解是 4,近似比 4/3 ≈ 1.33 ≤ 2。✓

如果改变遍历顺序呢?如果你先遇到 (2,3),然后遇到 (1,2) 和 (3,4),M 可能变成 {(2,3),(4,5)} 或 {(2,3),(1,5)},输出大小仍然是 4。不同的极大匹配给出不同的解,但都在 2 倍以内。

注意这个算法之美:它并不试图"聪明地"挑选顶点。它依赖一个极其简单的事实——匹配的大小天然是 OPT 的下界。这个界不是算出来的,而是图的结构本身提供的。好的近似算法往往不是"聪明地逼近最优",而是"找到了一个必然接近最优的简单结构"。这与李雅普诺夫函数一脉相承——两者都是找到一个自然递减(或自然有界)的量。


20.5 PAC 学习:"差不多对"的概率版本 ​

近似比关心的是解的质量;PAC 框架把同样的精神应用到学习问题上。

定义(PAC 学习):概念类 C 是 PAC 可学习的(Probably Approximately Correct),如果存在一个算法 L,使得:对任意目标概念 c∈C、任意数据分布 D,以及任意参数 ε>0(误差容忍)和 δ>0(失败概率),当样本量 m 足够大(关于 ε,δ 的多项式)时,L 以至少 1−δ 的概率输出一个假设 h,使得

Px∼D[h(x)≠c(x)]≤ε

用大白话说:它以高概率(至少 1−δ)输出一个近似正确的假设(错误率至多 ε)。PAC 是"Probably Approximately Correct"的缩写——这不是自谦,而是一个精确的数学承诺。

很多人把"以高概率近似正确"读成降低标准。恰恰相反——ε 和 δ 不是模糊的词语,而是你可以计算出来的数字。这比许多声称"准确"的方法更诚实:它确切地知道自己承诺了什么,也确切地知道承诺在哪里失效。知道自己的边界,比假装没有边界要诚实得多。

PAC 框架的核心结论:样本量 m 只需要按 1/ε 和 1/δ 的多项式增长,学习就能完成。这意味着:你不需要无限的数据——有限个、多项式多的样本,就足以以高概率学到一个近似正确的概念。

在 PAC 框架中,所需的样本量还取决于另一个量:假设空间 H 的 VC 维(Vapnik-Chervonenkis dimension)。VC 维衡量的是 H 能"打散"的最大点集的大小——能打散一个大小为 d 的点集,意味着对这些点的任意标注,H 中都有某个假设能完美拟合它。VC 维越高,假设空间越复杂,就需要越多的样本来约束它。基本的 PAC 样本复杂度定理:m=O(1ε(dln⁡1ε+ln⁡1δ)),其中 d 是 VC 维。这把第 1 卷第 5 章的"过拟合"直觉——假设空间太复杂就需要更多数据——变成了一个可计算的界。

20.5.5 实操:VC 维的三道练习题 ​

练习 1:实数轴上的区间。 设假设空间 H1 为实数轴上的闭区间 [a,b]:对点 x,若 x∈[a,b] 则预测 +1,否则预测 -1。它能打散的最大点集是多大?

2 个点:把它们放在 x1=0、x2=1。4 种标注都能产生吗?

  • (+,+):区间 [0,1] ✓
  • (-,-):区间 [2,3](不覆盖任何点)✓
  • (+,-):区间 [0,0] ✓
  • (-,+):不可能。因为如果一个区间覆盖了右边的点(x2=1),它必然也覆盖两者之间的任何点。要覆盖 x2 而不覆盖 x1?如果 x1=0<x2=1,任何包含 x2 以及它和 x1 之间所有点的区间都必须……等等——区间是连续的,但 x1 和 x2 是离散的点。区间 [0.5,1.5] 包含 x2,但不包含 x1=0。所以 (-,+) 是可能的!区间 [0.5,1.5] 把 x1 标为 -1,把 x2 标为 +1。✓

4 种标注都能产生。所以 VC 维 ≥ 2。

3 个点:令 x1=0、x2=1、x3=2,我们能产生 (+,-,+) 吗?我们需要覆盖 x1 和 x3,但不覆盖 x2。但区间是连续的——任何覆盖 0 和 2 的区间必然覆盖 1。所以 (+,-,+) 不可能。VC 维 = 2。

练习 2:平面上的线性分类器(过原点的直线)。 H2:sign(w⋅x),w∈R2。它能打散平面上 3 个不共线的点吗?可以——全部 8 种标注都能实现。4 个点呢?不能——存在一些 4 点集合,任何过原点的直线都无法打散它们。VC 维 = 2(因为直线必须过原点,损失了一个自由度;如果不要求过原点,VC 维是 3)。

练习 3:神经网络与 VC 维之间的张力。 一个有 W 个权重的神经网络,其 VC 维约为 O(Wlog⁡W) 量级。但现代深度网络动辄有数十亿参数——按 PAC 理论,它们需要天文数字般的样本。而在实践中,这些网络用远少于理论要求的样本就能泛化。这种张力正是第 21 章"泛化 = 压缩"视角的起点:VC 维衡量的是最坏情况下的复杂度,但实际网络的有效复杂度远低于它的参数数量——很大一部分参数被结构约束(权重衰减、架构设计、SGD 的隐式正则化)压缩进一个小得多的有效空间。

把三道练习并排放在一起,你看到了什么?VC 维不是什么模糊的"复杂度";它是一个你可以手算出来的具体数字。2、2(或 3)、数十亿——这些数字告诉你为什么有些假设类容易学,有些需要更多数据,有些让理论家困惑。可计算性是最好的清醒剂。


20.6 三种合同的统一 ​

把本章的内容放在一起:

合同承诺条件代价
可采纳性 + A*找到最优解h 永远不高估可能探索更大的空间
近似比 ρ解至多是最优的 ρ 倍最坏情况保证放弃最优性
PAC 学习以高概率近似正确足够的样本允许失败概率 δ

三种合同,三种不同的"足够好"——各有自己的代价结构和保证类型。它们的共同点在于:每一种都把"近似"从一种直觉变成了一个数学量。合同可以被违反,但违反是可检测的。这完全符合第 14 章形式系统的精神:精确定义允许精确批评。

启发式不是因为我们请不起精确推理而被迫接受的三流妥协。它是在计算约束下对推断质量的理性承诺——知道自己承诺什么,也知道承诺的边界在哪里。


20.7 合同签订之后:谁来写合同? ​

本章建立了一个令人安心的框架:只要签了合同,启发式的行为就有数学保证。但有一个我们一直回避的问题:合同是谁写的?

一个可采纳的启发式 h 必须由人设计。PAC 学习的假设空间 H 必须由人选择。近似算法的近似比必须由人证明。这些"合同"中的每一份,都来自系统外部的设计者。

回到第 15 章的语言:在形式系统中,公理必须从外部输入;系统不能自己选择公理。在启发式合同中,合同的条款(h 的形式、H 的结构、近似比的证明)同样来自系统外部。

这意味着:今天所有的"有保证的推理"都依赖一个外部承诺——你相信设计者所选的启发式是合理的,相信所选的假设空间是恰当的。但如果这个外部承诺本身就是错的呢?如果在某个场景中,你的启发式系统性地高估,而你不知道呢?

这个问题引出一个更深的问题:合同能否自动地从数据中写出来? 我们能否让系统观察自己的行为,从成功和失败中推断出合适的启发式?如果设计启发式本身就是一个推断问题——从问题实例的历史中推断出哪种估计策略在未来实例上有效——那么启发式设计就是元学习。

而元学习,正是第 21 章打开的那扇门:学习能否被理解为从数据中推断出最短描述?如果学习是逆推断,那么"学到一个好的启发式"这件事本身,能否被理解为一种逆推断?

这三个问题——谁写合同、合同能否自动写出、写合同本身算不算学习——把我们从"启发式的形式化"推向"学习的逆推断结构"。合同的形式化是本章的工作;合同从何而来是下一章的工作。最终的答案在第 21 章。


悬而未决 ​

近似的边界能被打破吗? 对某些问题,近似比存在不可逾越的下界(假设 P ≠ NP)。但近似算法理论仍然有大量未解问题:旅行商问题的最优近似比是多少?唯一博弈猜想(Unique Games Conjecture)是否成立——它为大量问题钉下了近似下界。这个方向的问题往往比 P ≠ NP 本身更容易陈述,也同样深刻。

PAC 学习的计算版本:PAC 框架保证的是样本复杂度,而不是计算复杂度。有些概念类在样本意义上是可学习的,但学习算法本身可能需要指数时间。区分"信息论上可学习"和"计算上可学习",是学习理论的核心张力——前者问你需要多少数据,后者问你需要多少时间。

启发式能被自动发现吗? A* 需要手工设计的 h,PAC 学习需要手工选择的假设空间 H。好的启发函数能否从数据中自动发现,或者合适的假设空间能否从问题结构中自动推断?这把启发式设计本身变成了一个推断问题——而推断问题正是第 21 章的主题:学习能否被理解为从数据中推断出最短描述?


思考题 ​

★ 热身

在地图上的 A* 寻路中,直线距离常被用作启发式 h。判断以下 h 中哪些是可采纳的、哪些不是,并各给一句话的理由。

  1. h(n)=0(零启发式;A* 退化为 Dijkstra 算法)
  2. h(n)= 从 n 到目标的直线(欧几里得)距离
  3. h(n)= 从 n 到目标的直线距离 ×2
  4. h(n)= 从 n 到目标的实际最短路径长度(假设你已经知道它)
  5. h(n)= 从 n 到目标的曼哈顿距离(只允许上下左右移动时)

★★ 推导

  1. 可采纳性的代价:设计一个简单的搜索问题(画一个带边权的 5 节点图),使得可采纳的启发式 h1 必须展开更多节点才能找到最优解,而不可采纳的 h2 用更少的节点就找到了同一个解。给出两个 h 的具体数值,并追踪两种情况下的 A* 展开顺序。可采纳性保证什么,不保证什么?

  2. PAC vs. 贝叶斯:第 17 章的贝叶斯推断和本章的 PAC 学习都处理"从有限数据中泛化"。PAC 的保证对最坏情况分布成立;贝叶斯的保证依赖先验。哪种保证假设更少?在先验完全错误的情形下,哪个框架会先崩溃?


★★★ 挑战

一般旅行商问题(TSP,不满足三角不等式时)已被证明:若 P ≠ NP,则对任意常数 ρ,都不存在多项式时间的 ρ-近似算法。

这个"不可近似性"的证明用的是归约:如果存在 ρ-近似算法,它就能解决哈密顿回路问题(NP 完全)。试着用平实的语言勾勒这个归约的大致思路——你会如何把哈密顿回路判定问题的一个实例转化为 TSP 的一个实例,使得"找到近似解"等价于"判定哈密顿回路是否存在"?

这道练习的目标不是完整的证明;而是理解为什么允许误差并不总是让问题变简单——在某些情况下,近似和精确求解一样难。