Leslie G. Valiant：他用数学告诉我们"什么能学、什么能算"

图灵奖第四十五届（2010）| Leslie G. Valiant：他用数学告诉我们”什么能学、什么能算”

一句话概括：当机器学习还是炼金术时，Valiant给它建立了数学基础——PAC学习理论告诉我们”学习”为何可能；BSP模型让并行计算有了通用语言；他用理论之光照亮了AI和并行计算两座高山。

🏆 获奖简介

Leslie Gabriel Valiant（莱斯利·加布里埃尔·瓦利安特，1949-）是计算学习理论的奠基人，并行计算模型的先驱。

• 出生时间：1949年3月28日
• 出生地点：英国伦敦
• 主要成就：提出PAC学习理论、BSP并行计算模型、VC维理论、计数复杂性理论（#P完全性）
• 获奖年份：2010年
• 获奖原因：在计算学习理论和并行计算复杂性理论方面的开创性贡献

为什么他是第四十五位？ 1980年代，机器学习是一门经验科学——人们设计算法，在数据上试验，但没人能从理论上解释”为什么这个算法有效”或”需要多少数据才能学好”。1984年，Valiant发表了划时代的PAC（Probably Approximately Correct，概率近似正确）学习理论，第一次用严格的数学框架定义了”可学习性”。他证明：只要有足够多的样本，且计算复杂度可接受，某些概念是可以被高效学习的。这一理论成为现代机器学习的理论基石，从神经网络到深度学习，都可以用PAC框架分析。同时，Valiant还提出了BSP（Bulk Synchronous Parallel）模型，为并行计算提供了简洁的抽象，影响了从MapReduce到GPU编程的设计。他的工作横跨理论与实践，将数学的优雅和工程的务实完美结合。

🚀 重大贡献

1. PAC学习理论：机器学习的数学基础

时代背景（1980年代初）：

• 机器学习的困境：
  • 算法众多（感知器、决策树、神经网络等）
  • 但缺乏统一理论：“为什么这个算法有效？”
  • 没有量化标准：“需要多少训练数据？”
  • 无法预测泛化能力：“在新数据上表现如何？”

Valiant的突破（1984）： 发表论文《A Theory of the Learnable》，提出PAC学习框架。

PAC学习的核心思想

问题设定：

• 目标概念：我们想学习的真实函数 c（例如：“这张图片是猫还是狗”）
• 训练数据：从未知分布 D 中采样的样本 (x, c(x))
• 学习算法：输出假设 h，希望 h 近似 c

PAC可学习的定义： 如果存在算法 A，满足：

1. Probably（概率地）：至少以 1-δ 的概率（δ是失败概率）
2. Approximately（近似地）：误差不超过 ε（ε是误差界限）
3. Correct（正确）：h 在分布 D 上与 c 的差异小于 ε
4. 高效：算法运行时间是 1/ε、1/δ、样本复杂度的多项式

数学形式：

P[error(h) ≤ ε] ≥ 1 - δ
样本复杂度：m = poly(1/ε, 1/δ, n)
时间复杂度：t = poly(1/ε, 1/δ, n)

其中 n 是问题规模（如特征数量）

样本复杂度：需要多少数据？

Valiant的分析：

• 样本数量的下界：如果样本太少，学习器可能会”过拟合”（记住训练数据，但泛化不好）
• 样本数量的上界：对于很多概念类，O((1/ε)log(1/δ)) 个样本就足够了

例子：学习合取式（AND of literals）

• 概念：f(x) = x₁ ∧ ¬x₂ ∧ x₅（布尔变量的合取）
• 算法：开始假设所有变量都在合取中，看到反例就删除
• 样本复杂度：O(n/ε + log(1/δ))，其中 n 是变量数
• 关键：多项式样本即可学习

可学习性的层次

Valiant区分了：

1. 信息论可学习（Information-theoretically learnable）：

   • 不考虑计算复杂度，只考虑样本复杂度
   • 某些概念类可以用少量样本学习

2. 高效可学习（Efficiently learnable，即PAC可学习）：

   • 既要样本复杂度低，又要计算复杂度低（多项式时间）
   • 关键洞察：可学习性与计算复杂性相关！

不可学习的例子：

• 任意布尔函数：有 2^n 种可能，需要指数级样本才能区分
• NP难问题：如果学习算法能高效学习，可能破解密码学（如学习RSA密钥）

VC维理论

虽然VC（Vapnik-Chervonenkis）维由Vapnik和Chervonenkis提出，但Valiant的PAC框架与VC维紧密结合：

VC维的定义：

• 假设类 H 的VC维是最大的 d，使得存在 d 个点可以被 H 任意划分（shattered）

与PAC的关系（Blumer等人，1989）：

• 样本复杂度：m = O((d/ε)log(1/δ))，其中 d 是VC维
• 可学习性：有限VC维的概念类是PAC可学习的

例子：

• 线性分类器（2D平面）：VC维 = 3
  • 3个点可以任意划分（8种方式）
  • 4个点不行（XOR配置无法线性分离）
• n维线性分类器：VC维 = n+1

2. #P完全性与计数复杂性

动机（1979）：

• NP理论研究”决策问题”（是/否）：“这个图有汉密尔顿回路吗？”
• 但实际问题常常是”计数”：“有多少个汉密尔顿回路？”

Valiant的贡献： 定义了**#P复杂度类**（sharp-P），研究计数问题的困难性。

#P的定义

#P：计数NP问题的解的数量

• 例子：
  • #SAT：满足布尔公式的赋值有多少个？
  • #HC：图中有多少条汉密尔顿回路？
  • #Perfect Matching：二部图中有多少个完美匹配？

#P-完全：最难的#P问题（任何#P问题都可以归约到它）

经典结果

Valiant证明（1979）：

• #Perfect Matching在二部图上：可以在多项式时间内计算（使用矩阵行列式）
• #Perfect Matching在一般图上：#P-完全（非常困难！）

意义：

• 即使决策版本容易（NP），计数版本可能极难（#P-完全）
• 例子：
  • 2-SAT决策：多项式时间（P）
  • #2-SAT计数：#P-完全（困难得多！）

永久式（Permanent）vs. 行列式（Determinant）

Valiant的惊人发现：

• 行列式：可以高效计算（O(n³) 时间）
• 永久式：#P-完全（可能需要指数时间）

定义：

行列式：det(A) = Σ sgn(σ) Π A[i, σ(i)]
永久式：per(A) = Σ Π A[i, σ(i)]

（仅差一个符号项 sgn(σ)，但复杂度天差地别！）

应用：

• 永久式出现在组合优化、量子计算、图论中
• Valiant的结果说明：某些看似简单的代数问题极其困难

3. BSP模型：并行计算的桥梁

时代背景（1980年代末）：

• 并行计算机种类繁多：
  • 共享内存（PRAM模型）
  • 分布式内存（消息传递）
  • 向量处理器
  • SIMD/MIMD
• 问题：为某个架构写的程序，无法移植到其他架构
• 需求：一个”跨平台”的并行计算模型

Valiant的BSP模型（1990）： BSP = Bulk Synchronous Parallel

BSP的核心思想

系统组成：

1. 处理器：p个独立的计算单元
2. 网络：连接处理器，可以发送/接收消息
3. 同步机制：全局同步屏障（barrier）

执行模式： 计算分为若干”超步”（superstep）：

超步 1：
  - 各处理器本地计算
  - 发送消息
  - 同步（barrier）

超步 2：
  - 接收上一超步的消息
  - 本地计算
  - 发送新消息
  - 同步

...

性能模型：

• p：处理器数量
• L：同步延迟（latency）
• g：通信带宽的倒数（gap）

超步时间 = max(本地计算时间) + g × (最大消息数) + L

BSP的优势

1. 简单：

• 程序员不需要关心底层网络拓扑
• 同步点明确，避免复杂的同步协议

2. 可移植：

• 同一个BSP算法可以在不同硬件上运行
• 只需调整 p、L、g 参数

3. 可预测：

• 性能模型清晰，可以分析算法的通信成本

4. 可扩展：

• 适合大规模并行（如1000+处理器）

BSP的应用

Google的Pregel（2010）：

• 大规模图计算框架
• 直接基于BSP模型
• 用于PageRank、社交网络分析等

Apache Giraph：

• 开源的Pregel实现
• Facebook用于社交图分析

BSPlib：

• 标准化的BSP编程库
• 支持C/C++、Fortran

GPU编程：

• CUDA的线程同步（__syncthreads()）类似BSP的屏障
• 网格计算（grid computing）的超步模式

4. 神经计算理论

问题（1980-1990年代）：

• 大脑如何进行计算？
• 神经网络的学习能力有何理论限制？

Valiant的贡献：

神经元的布尔函数视角

Circuits of the Mind（1994）一书中，Valiant提出：

• 神经元可以看作计算布尔函数的单元
• 学习就是调整神经元的连接权重，逼近目标函数
• PAC学习框架可以分析神经网络的可学习性

关联记忆与PAC学习

记忆存储：

• 大脑如何存储和检索记忆？
• Valiant用PAC框架分析Hopfield网络等模型

泛化能力：

• 神经网络不只是”记住”训练数据，还能泛化
• PAC理论解释了为何泛化可能（样本复杂度）

生物可信的学习规则

Hebbian学习：

• “一起激活的神经元，连接增强”
• Valiant分析了这种局部学习规则的全局效果

关键问题：

• 大脑没有全局监督信号（没有”反向传播”），如何学习复杂功能？
• Valiant探索了无监督和强化学习的理论

5. 进化计算理论

Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World（2013）：

• Valiant将PAC理论应用于生物进化
• 问题：进化如何”学习”适应环境？

进化作为学习过程

类比：

• 训练数据：环境的选择压力
• 学习算法：遗传变异 + 自然选择
• 假设类：基因型空间
• 目标：适应度最大化

PAC框架下的进化：

• 进化需要多少代才能适应新环境？
• 样本复杂度 → 种群大小 × 代数
• 计算复杂度 → 基因组的复杂性

Evolvability（可演化性）

Valiant提出：

• 不是所有性状都易于进化
• 可演化性类似”可学习性”：
  • 如果性状的遗传基础复杂（如需要多个基因精确配合），难以演化
  • 如果性状有简单的遗传编码，易于演化

意义：

• 解释了为何某些性状快速进化（如抗药性），某些性状几乎不变（如基因调控网络）
• 连接了计算机科学和进化生物学

🌍 对世界的深远影响

对机器学习的影响

理论基础

PAC学习成为标准框架：

• 所有机器学习教科书都讲PAC理论
• 新算法的分析常常基于PAC框架

具体影响：

1. 样本复杂度分析：

   • “需要多少数据？“有了理论答案
   • 指导数据收集策略（如主动学习）

2. 泛化界（Generalization Bounds）：

   • 训练误差低 ≠ 测试误差低
   • PAC理论给出泛化误差的上界：

     测试误差 ≤ 训练误差 + O(√(VC维/样本数))
     

3. 正则化的理论依据：

   • 为何要限制模型复杂度？
   • PAC理论：复杂模型需要更多样本，否则过拟合

深度学习的理论挑战

悖论：

• 深度神经网络有数百万参数（高VC维）
• 按传统PAC理论，需要天文数字的样本
• 但实际上，深度学习在有限样本下表现很好

当前研究：

• 修正的PAC框架（如PAC-Bayes）
• 隐式正则化（如SGD的偏好）
• Valiant的工作启发了这些新理论方向

对并行计算的影响

MapReduce与大数据

Google MapReduce（2004）：

• 虽然没有直接引用BSP，但理念相似
• Map阶段：并行处理
• Shuffle：重新分配数据（类似BSP消息传递）
• Reduce阶段：并行聚合
• 同步：阶段间的屏障

Hadoop：

• 开源MapReduce实现
• 处理PB级数据（如Yahoo、Facebook的数据中心）

图计算

Pregel（Google，2010）：

• 明确基于BSP模型
• 用于处理万亿边的图（如网页链接图）
• 应用：PageRank、社区发现、推荐系统

GraphLab/PowerGraph：

• CMU的图并行框架
• 也受BSP启发

GPU通用计算

CUDA编程模型：

• 线程块：类似BSP的处理器组
• __syncthreads()：BSP的屏障同步
• 全局内存：BSP的消息传递

应用：

• 深度学习训练（TensorFlow、PyTorch）
• 科学计算（分子动力学、气候模拟）

对复杂性理论的影响

计数复杂性的广泛应用

量子计算：

• 某些量子算法（如玻色采样）与永久式的计算相关
• Valiant的#P完全性结果说明了量子优势的可能性

近似算法：

• 既然精确计数是#P-完全的，能否近似计数？
• FPRAS（Fully Polynomial Randomized Approximation Scheme）成为研究热点

统计物理：

• 配分函数（Partition Function）的计算是#P-完全
• 解释了为何某些物理系统的精确分析极难

🏆 获奖理由（通俗版）

ACM官方表彰：“在计算学习理论的贡献，包括PAC（概率近似正确）学习模型；在复杂性理论的贡献，包括#P完全性的理论；以及在并行和分布式计算理论的贡献，包括BSP模型。”

更通俗的理解：

PAC学习理论：

• 问题：机器如何学习？需要多少数据？
• Valiant的答案：如果概念”简单”（低VC维）且有足够样本，学习是可能的
• 类比：学开车需要多少次练习？PAC理论给出数学公式
• 影响：从垃圾邮件过滤到医疗诊断AI，都依赖这一理论

#P完全性：

• 问题：计数问题有多难？
• Valiant的答案：某些计数问题（如永久式）极其困难，可能需要指数时间
• 类比：数有多少条路径从A到B，比判断”是否存在路径”难得多
• 影响：密码学、量子计算、统计推断都依赖这一理论

BSP模型：

• 问题：如何设计可移植的并行算法？
• Valiant的答案：用超步+同步的抽象，隐藏底层硬件细节
• 类比：BSP是并行计算的”Java虚拟机”（跨平台）
• 影响：Google、Facebook的大规模数据处理都用BSP思想

👤 个人生平与传奇

早年（1949-1974）

童年：

• 1949年：出生于英国伦敦
• 家庭：父母是匈牙利犹太移民，经历了二战
• 兴趣：从小喜欢数学和逻辑谜题

教育：

• 1967-1970：剑桥大学国王学院数学学士
  • 成绩优异，获得一等荣誉学位
• 1974：伦敦帝国理工学院计算机科学博士
  • 导师：Mike Paterson
  • 论文：决策树与NP完全性相关

学术生涯（1974-现在）

早期职位：

• 1974-1977：卡内基梅隆大学助理教授
• 1977-1982：爱丁堡大学讲师
• 1982：加入哈佛大学，至今

哈佛时期：

• 1982-1988：助理教授
• 1988-1993：副教授
• 1993-现在：T. Jefferson Coolidge教授（哈佛最高荣誉教席之一）

重要学术成就时间线

• 1979：提出#P完全性理论（25岁博士后！）
• 1984：发表PAC学习理论（35岁，职业生涯最重要贡献）
• 1990：提出BSP并行计算模型
• 1994：出版《Circuits of the Mind》，探讨大脑的计算理论
• 2013：出版《Probably Approximately Correct》，将PAC理论应用于进化和认知

荣誉与奖项

• 1986：Nevanlinna奖（国际数学联盟，颁给计算机科学家）
• 1997：欧洲理论计算机科学协会（EATCS）奖
• 2008：ACM/AAAI Allen Newell奖（认知科学与AI的交叉）
• 2010：图灵奖
• 2021：美国国家科学奖章（由总统颁发）

性格与风格

深度思考者：

• 不追求发表数量，追求深度
• 每篇论文都是长期思考的结晶

跨学科视野：

• 从计算复杂性到机器学习
• 从并行计算到神经科学
• 从算法到进化生物学
• Valiant总是在寻找不同领域的共同原理

低调：

• 很少参加会议社交活动
• 更喜欢在办公室思考
• 同事形容他”极其谦逊，但洞察力惊人”

教学：

• 哈佛的学生评价Valiant的课”极其困难但收获巨大”
• 他要求学生真正理解证明，而非记忆结论

传奇故事

PAC理论的诞生：

• 1983年，Valiant在思考”学习的本质是什么”
• 他意识到：学习不需要完美，只需”概率上近似正确”
• 这一洞察来自对日常学习的观察：人类学习也不是完美的，但足够好
• 用数学形式化这一直觉，就诞生了PAC框架

Nevanlinna奖的突然性：

• 1986年，Valiant获Nevanlinna奖（相当于计算机界的菲尔兹奖）
• 当时他才37岁，已有#P完全性和PAC两项重大贡献
• 颁奖词：“以不可思议的创造力，重新定义了我们对计算的理解”

图灵奖获奖感言： Valiant说：“理论计算机科学最迷人的地方在于——它能揭示看似不同领域的深层联系。学习、计数、并行，表面上毫无关系，但数学告诉我们，它们都是关于’什么是可计算的’这一根本问题。”

💭 为什么他值得纪念？

1. 他为机器学习建立了理论基础

在Valiant之前：

• 机器学习是经验科学
• 算法的有效性凭试验和直觉

在Valiant之后：

• 有了严格的数学框架
• 可以证明算法的样本复杂度
• 可以分析泛化能力

类比：

• Valiant之于机器学习，就像牛顿之于力学
• 把经验规律提升为数学理论

2. 他统一了不同的计算问题

看似无关的问题：

• 学习布尔函数
• 计数完美匹配
• 并行矩阵乘法
• 大脑的联想记忆

Valiant的洞察：

• 它们都是”计算复杂性”的不同面向
• 用统一的数学工具（复杂性理论）分析

意义：

• 跨学科研究的典范
• 证明了理论计算机科学的普适性

3. 他的工作既有理论深度，又有实践影响

理论：

• PAC理论是纯粹的数学
• 优雅、严格、深刻

实践：

• 指导机器学习算法设计
• BSP模型用于工业系统（Google、Facebook）

罕见平衡：

• 大多数理论家的工作停留在论文
• Valiant的理论影响了数十亿人（通过搜索引擎、推荐系统等）

4. 他的远见仍在指引未来

当前热点：

• 深度学习的理论（PAC理论的延伸）
• 大模型的样本效率（样本复杂度分析）
• 分布式训练（BSP模型的现代实现）

未来方向：

• 进化算法的理论（Valiant已开始探索）
• 量子机器学习（结合#P复杂性和PAC）
• 生物计算（神经网络与大脑的连接）

🔍 技术深度：PAC学习的数学细节

形式化定义

设定：

• X：样本空间（如所有可能的图像）
• C：概念类（如”猫”的所有可能定义）
• H：假设类（算法可以输出的函数集合）
• D：X上的概率分布（未知）

PAC可学习： 概念类C相对于假设类H是PAC可学习的，如果存在算法A和多项式函数poly(·,·,·,·)，使得：

对于所有 c ∈ C，所有分布 D，所有 0 < ε, δ < 1：

• 算法A接收 m ≥ poly(1/ε, 1/δ, n, size(c)) 个样本
• 算法A在 t ≤ poly(1/ε, 1/δ, n, size(c)) 时间内输出 h ∈ H
• 满足：P[error_D(h) ≤ ε] ≥ 1 - δ

其中 error_D(h) = P_{x~D}[h(x) ≠ c(x)]

经典可学习概念类

1. 合取式（Conjunctions）

概念：f(x) = x₁ ∧ x₃ ∧ ¬x₅ ∧ x₇

算法：

初始化：h = x₁ ∧ ¬x₁ ∧ x₂ ∧ ¬x₂ ∧ ... ∧ xₙ ∧ ¬xₙ  # 全部变量
for each 正样本 (x, 1):
    for each literal in h:
        if literal(x) = False:
            从h中移除literal
输出 h

正确性证明：

• 正样本告诉我们”哪些literal不在目标中”（因为目标为真，但该literal为假）
• 负样本不给信息（目标为假，所有literal组合都可能）
• 最终h是目标的超集（可能包含多余literal），但随样本增多会收敛

样本复杂度：

• m = O((n/ε)log(1/δ))
• 证明：使用Chernoff界，分析”所有多余literal被样本覆盖”的概率

2. 决策树

概念：树的每个节点测试一个特征，叶子给出类别

算法：

• ID3、C4.5等（贪心构建树）
• 剪枝以控制复杂度

可学习性：

• 固定深度的决策树：PAC可学习
• 任意深度的决策树：不PAC可学习（可能需要指数样本）

3. 线性分类器

概念：f(x) = sign(w · x + b)

算法：

• 感知器、SVM等

可学习性：

• 如果数据线性可分且间隔为γ：PAC可学习
• 样本复杂度：O((1/γ²ε)log(1/δ))

不可学解的例子

任意布尔函数

概念类：所有n变量布尔函数

大小：2^(2^n)

问题：

• 需要至少 2^n 个样本才能区分不同函数
• 不满足多项式样本复杂度

密码学函数

例子：学习RSA加密函数

不可学习性：

• 如果可高效学习，就能破解加密
• 基于计算复杂性假设（如大数分解困难），不PAC可学习

PAC与其他学习模型的关系

1. 在线学习（Online Learning）

区别：

• PAC：批量学习（一次性获得所有样本）
• 在线：逐个样本，每次预测后看到真实标签

联系：

• Mistake Bound（错误次数界）与样本复杂度相关
• Littlestone维（在线学习的”VC维”）

2. 主动学习（Active Learning）

区别：

• PAC：样本随机采样
• 主动：算法选择要标注哪些样本

优势：

• 样本复杂度可以大幅降低（如从O(d/ε)到O(d·log(1/ε))）

3. PAC-Bayes

扩展：

• 引入先验分布
• 考虑假设的”随机化”
• 更适合分析深度学习（模型集成、dropout等）

🧪 实践意义：从理论到应用

PAC理论指导机器学习实践

1. 样本数量的选择

问题：我需要收集多少训练数据？

PAC的答案：

• 估计模型的VC维（或有效自由度）
• 使用公式：m ≈ (VC维/ε²) × log(1/δ)
• 例子：
  • 线性分类器（100维）：VC维≈100
  • 要达到1%误差（ε=0.01），99%置信度（δ=0.01）
  • 需要 m ≈ 100/0.0001 × log(100) ≈ 460万样本

实际考虑：

• 这是理论上界，实际可能需要更少（数据分布友好）
• 但给出了量级估计

2. 模型复杂度的权衡

过拟合vs.欠拟合：

• 简单模型（低VC维）：样本需求少，但表达能力弱
• 复杂模型（高VC维）：表达能力强，但需要更多样本

PAC的指导：

• 给定样本数m，选择VC维 ≈ εm 的模型
• 正则化的理论依据：限制有效VC维

3. 早停（Early Stopping）

训练神经网络时：

• 训练误差持续下降
• 但测试误差可能先降后升（过拟合）

PAC解释：

• 训练过程中，“有效VC维”在增加
• 当超过样本复杂度的支撑，泛化误差上升
• 早停相当于控制有效复杂度

BSP模型指导并行算法设计

矩阵乘法

任务：计算 C = A × B（n×n矩阵）

BSP算法：

输入：A、B分布在p个处理器上
超步1：
  - 每个处理器广播其拥有的A的行
超步2：
  - 每个处理器接收A的行
  - 本地计算其负责的C的块
输出：C

性能分析：

• 计算：O(n³/p)
• 通信：O(n²·g)（每个处理器发送O(n²/p)数据）
• 同步：O(L)
• 总时间：O(n³/p + n²·g + L)

优化：

• 如果 p ≤ n/g，通信不成为瓶颈
• 接近线性加速

PageRank

任务：计算网页的重要性分数

BSP算法（Pregel风格）：

初始化：每个节点的rank = 1/N
迭代若干超步：
  超步i：
    - 每个节点将rank/出度 发送给邻居
    - 每个节点接收消息，更新rank = 0.15 + 0.85·Σ(消息)
  直到收敛

优势：

• BSP的同步保证每轮迭代都基于上轮的完整结果
• 避免异步算法的收敛性问题

#P理论的应用

近似计数

既然精确计数是#P-完全的，如何近似计数？

随机算法：

• Markov Chain Monte Carlo (MCMC)：
  • 构造马尔可夫链，其平稳分布与目标计数相关
  • 采样足够多步，估计计数
• 例子：
  • 估计图中完美匹配的数量
  • 统计物理中的配分函数近似

理论保证：

• FPRAS（Fully Polynomial Randomized Approximation Scheme）：
  • 时间 poly(n, 1/ε)，输出(1±ε)倍的近似
• Valiant的#P完全性告诉我们：如果P≠NP，某些问题不存在FPRAS

📚 延伸阅读

书籍

• Valiant著《Probably Approximately Correct》(2013)

  • 面向大众，讲述PAC理论及其在进化、认知中的应用
  • 获得洛杉矶时报图书奖

• Kearns & Vazirani：《An Introduction to Computational Learning Theory》(1994)

  • 教科书，详细介绍PAC理论及后续发展

• Valiant著《Circuits of the Mind》(1994)

  • 神经计算的理论，连接大脑与计算

论文

• Valiant: “A Theory of the Learnable” (CACM 1984)

  • PAC理论的开创性论文，必读经典

• Valiant: “The Complexity of Computing the Permanent” (Theoretical Computer Science 1979)

  • #P完全性的奠基工作

• Valiant: “A Bridging Model for Parallel Computation” (CACM 1990)

  • BSP模型的提出

在线资源

• Valiant的哈佛主页：论文列表和最新研究
• Pregel论文（Google，2010）：BSP在大规模图计算中的应用
• VC维的可视化工具：理解样本复杂度

🌟 精神遗产

”理论应该解释现实”

Valiant从不追求”为理论而理论”。他的每个工作都源于对真实问题的深刻思考：

• PAC理论：为何机器学习在实践中有效？
• BSP模型：如何设计真正可用的并行算法？
• #P完全性：计数问题在实际中为何困难？

今天的启示：

• 好的理论应该能指导实践
• 不要害怕”实用的理论”矛盾——Valiant证明它们可以并存

”简单的抽象，深刻的洞察”

Valiant的理论都极其简洁：

• PAC：三个参数（ε、δ、n）
• BSP：三个参数（p、L、g）
• #P：一个定义（计数NP问题的解）

但这些简洁背后是深刻的洞察：

• PAC抓住了学习的本质（不需要完美）
• BSP抓住了并行的本质（同步的超步）
• #P抓住了计数的本质（指数爆炸）

今天的启示：

• 好的理论应该”简单但不简化”
• 寻找问题的核心抽象

”跨学科的勇气”

Valiant敢于跨越领域：

• 从复杂性理论到机器学习
• 从算法到神经科学
• 从计算到进化生物学

他不怕”外行”的质疑，因为他相信数学的普适性。

今天的启示：

• 最大的创新常常在学科交叉处
• 不要被领域边界限制思维

---

总结语：Leslie Valiant是理论计算机科学的巨人。他用数学的语言回答了三个根本问题：“什么能学？“（PAC理论）、“什么能数？”（#P完全性）、“什么能并行？“（BSP模型）。他的工作不只是象牙塔中的定理，而是影响了Google的搜索、Facebook的社交网络、医院的诊断AI——数十亿人每天都在受益于他的理论，尽管他们从未听说过他的名字。

从机器学习的教科书到数据中心的服务器，从量子计算到进化生物学，Valiant的思想如同种子，在不同土壤中生根发芽。他证明了理论的力量：当你真正理解问题的本质，你的洞察就能跨越时间、跨越领域，照亮未知的道路。在AI飞速发展的今天，Valiant在1984年提出的问题——“什么是可学习的”——仍然是我们理解智能的北极星。

---

最后更新: 2024年12月 本文为图灵奖系列文章,旨在以通俗方式介绍计算机科学先驱的贡献