2010年，哈佛大学计算机科学和应用数学教授莱斯利·瓦伦特（Leslie Valiant）获得ACM图灵奖。在ACM的颁奖词中，提到了莱斯利·瓦伦特对计算理论的变革性贡献，其中最著名的是PAC学习理论。

PAC（Probably Approximately Correct）可以译为“大概近似正确”，或“概率近似正确”。莱斯利·瓦伦特是在1984年首次提出PAC理论的（参考资料[1]）。2013年，瓦伦特在他的著作《大概近似正确》（参考资料[2]）中，讨论了PAC学习理论在人工智能中的应用。该书的第1章题为“Ecorithms” （生态算法），提到：“我希望本书最终能说服读者，在寻求理解生命的基本特征时，学习算法是一个很好的起点”。书中他引入了一个更专业的概念“进化学习”(“Evolvable learning”)，他声称，这是达尔文进化论的特征。

在计算学习理论中，PAC学习是机器学习的数学分析框架。在这个框架中，学习者接收样本，从某类可能的函数中选择一个泛化函数（称为假设），目标是在较高概率下（“大概”部分），所选函数具有较低的泛化误差（“近似正确”部分）。PAC学习框架已经成为机器学习的独特基础。例如，在梅尔亚·莫里（Mehryar Mohri）等著的《机器学习基础（Foundations of Machine Learning）》（参考资料[3]）中，就是从PAC（大概近似正确）理论出发，探讨机器学习的基础理论与典型算法。机器学习从根本上讲就是泛化（generalization）。作为一个例子，标准的监督学习场景包括使用有限的标记示例样本来对未知的示例进行准确的预测。这个问题通常被表述为从一个假设集合中选择一个函数，即所有函数族的子集。所选函数随后用于标记所有实例，包括未知的示例。

从数学分析的角度来看，PAC的一个吸引人的特点是，它提供了许多可以使用的数值参数。其中有：近似正确性1−ɛ，获得近似正确规则的概率1−δ，样本数量m等。参数ɛ和δ用于描述“近似正确”和“概率”：

其中，是泛化误差，表示概率。当然，给定的参数，PAC可学习的问题也必须要有足够多的训练样本m，而这个样本数m有一个理论边界M——如果m不小于M，那么就可在预期的泛化误差和概率显著性水平下用机器学习找到的最优解。

这里|H|表示假设空间的大小。（有关理论边界定理公式的证明，见参考资料[3]第2章。）

PAC学习是一个优雅的框架，用以实现某些类型的学习的目标和解决计算困难。在参考资料[4]中，举了这样一个例子：想象一下，一个人或一个计算机程序，试图通过观察动物的样本来确定哺乳动物的特征。每个动物都被正确地标记为是哺乳动物，或不是哺乳动物。假设训练样本中不包括鸭嘴兽或针鼹，那么学习者很可能会得出一个规则，比如“毛发，温血，哺乳幼儿，胎生“。这规则并非十分正确，因为鸭嘴兽和针鼹是卵生的、而不是胎生的哺乳动物。但它是大概正确的，因为它适合于除鸭嘴兽和针鼹以外的所有哺乳动物。我们能不能开发一种学习算法，在足够大的随机样本下，总会（而不是“大概”会）生成一个近似正确的答案？不能够。例如，如果随机抽取动物样本，样本中所有哺乳动物都是鸭嘴兽和针鼹的可能性很小，但不是零。如果是这样的话，学习者可能会合理地假设哺乳动物是卵生，而这个规则并不是近似正确的。所以我们所希望的是一个大概会是近似正确的算法，也就是说，对于给定随机样本，算法大概会得出一个近似正确的规则。

瓦伦特在他的书中讨论了达尔文主义的合理性问题，他写道：达尔文的物种起源是一部令人叹为观止的洞察力之作。一个半世纪前，他从对动植物的观察中推断出进化论，已成为生物学的中心理论。…通过自然选择进化的理论，就目前而言，与其他一些伟大的科学理论（如牛顿引力定律或爱因斯坦的广义相对论）并不相同。后者做出供验证的定量预测。相比之下，进化论目前没有提供可比的定量预测，甚至没有对过去的定量解释。也许这就是为什么在伟大的科学理论中，进化论引起了最多的怀疑和有组织的反对。世界各国相当一部分人拒绝接受它。没有证据表明，在地球上，即使是最奇怪的成功理论，量子力学，有任何这种程度的排斥。人们不得不考虑到进化论在这方面的独特处境可能是由于其现有理论的缺陷。如果有一个定量分析可用，那么对它的重大反对似乎就不太可能了（参考资料[2]第6章）。

瓦伦特将PAC学习理论应用于达尔文主义的合理性问题，物种在进化过程中的适应环境被概念化为执行一种学习算法（瓦伦特称之为“生态算法（Ecorithms）”）。然而，有评论（参考资料[4]）怀疑：实际上，陆地环境有一系列不同的问题，在多大程度上，可以将适应性视为一种算法的执行？特别是，这在多大程度上合理地处理生命出现的早期阶段，形成自我复制的生物化学物质？在多大程度上，生态算法能够解决环境潜在的一系列问题，这在多大程度上是合理的？

瓦伦特的书中还包括机器学习和人工智能的扩展讨论。然而，也有评论（参考资料[4]）指出：PAC学习以一种自然的方式只适用于一类相当狭窄但非常重要的学习问题：从标签数据中学习类别（所谓的“监督式”学习）。因此，如果要将PAC学习视为一个通用的学习框架，那么其他形式的学习要么被硬塞进这种形式，要么被宣布为无关紧要，要么被忽视。例如，瓦伦特明确否认无监督学习（从未标记的示例中学习，例如将示例分组到聚类中）是研究自然学习的有用概念，尽管他承认它在机器上可能有一些价值。

莱斯利·瓦伦特是当今杰出的计算机科学家和计算理论家，瓦伦特的PAC学习是一种优雅而有用的方法。但是，有人对于这种方法在描述进化的特征方面是否有用，以及是否适用于所有形式的自然学习有所怀疑，也许有其一定的合理性，也许PAC理论与某些其它理论一样，只是大概近似正确。

参考资料：

[1] Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134{1142, 1984.

[2] Leslie Valiant. Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World. BASIC BOOKS.2013

[3] Mehryar Mohri, Afshin Rostamizadeh, Ameet Talwalkar. The Foundations of Machine Learning. second edition.The MIT Press. 2018（此书有中文版，机械工业出版社2019年出版）

[4] Review of Probably Approximate Correct, by Leslie Valiant . https://cs.nyu.edu/davise/papers/Valiant.pdf