在世界上第一台计算机 ENIAC 刚刚制造出来不久，科学家们就开始关心如何利用计算机实现人工智能的问题。然而，关于智能和学习的定义方式以及人工智能的实现方式在当时却是众说纷纭。理论学者们尝试从更加抽象的角度去理解“机器学习”甚至“学习”的概念。在上一篇节气推送（立春 | 机器学习中的学习理论）中，小编提到了 Leslie Valiant 在上述研究中做出的奠基性贡献。
Leslie Gabriel Valiant
人们一般认为关于机器学习数学理论的开山之作是1984年 Leslie Gabriel Valiant 的文章“A Theory of the Learnable”。Valiant 因为机器学习理论和并行计算理论的卓越成就并授予了2010年的图灵奖，而在这篇工作中他正式初次提出了为机器学习理论奠基的 PAC（Probably Approximately Correct）学习理论。这篇文章中，我们将围绕 Valiant 的这篇经典文献展开具体介绍。
文章的第一部分是关于学习（learning）概念的抽象理解。在1984年，可计算性的理论已经被图灵等计算机科学家通过数学进行了严谨的定义，而在 Valiant 认为可学习性应当是与可计算性同等重要的概念，而关键的问题就是寻找一个合适的模型：这个模型需要既能够解释人类等动物的学习经验，又能够帮助制造可以学习的机器。
文章中指出，学习是除去显式编程外其他完成任务的方式。人类所掌握的技能中一部分是可以被显式表述出来的（例如依照菜谱做菜），而另一部分技能则没有办法被显式的描述出来（如何判断一张照片里有没有猫咪出现）。我们关注的则是这些不能被显式编程的完成任务方式。因此，文章的目标就是设计一种这样的学习机器，使得它被证明能够在多项式时间内学习到一个不平凡的、由概念构成的类。事实上，这里提出的“概念”“类”和“多项式时间”等共同形成了现在广为采用的标准的 PAC 学习理论的雏形。
作者认为一个学习机器应该包含两部分：学习协议（learning protocol）和演绎过程（deduction procedure）。其中前者是从世界获取信息的方式，这在现在的理解即为收集数据的方式；而后者指的是如何从信息中获取概念，这也就是我们现在理解的学习算法。
在第三部分里，作者开始讨论可学习性（learnability）的问题，即我们在知道什么是学习之后，又该如何判断一个问题是不是能够被学习的呢？由此，作者给出了可学习性的定义，而这个定义最终被完善为 PAC learnable 的定义。通俗地讲，可学习就是存在算法能够在很短的时间（多项式时间）内以很高的概率出现很少的错误。这个概念从直觉上并不难理解。没有人愿意学一辈子习，所以当然要限定时间；由于获取知识的概率我们并不能保证在学习后成为一个不会犯错的完人，所以只能希望自己在学习后以很高的概率犯很少的错误（考试经常考高分）。当然，学习的效果（学习成功以及犯错的概率）肯定要是同学习时间正相关的，毕竟我们都知道：“一分耕耘，一分收获”嘛。
上述概念看着或许并不困难，我们也许会说“这我也能想到”，但其实却是非常深刻且有开创性的。Valiant 给出了自己对于学习和可学习性的独到理解，而从那时起机器学习算法的数学讨论基本都是在后者的框架中进行。
在文章之后的几个部分，作者则给出了具体的类以及学习机器的定义，举了三种例子并证明了它们都是可学习的。实际上，当时的计算机科学家对于机器学习、人工智能的可实现性还并没有太多的信心，因为无论从理论或者实践上都存在很多消极的证据（有人称那个年代为人工智能的寒冬），从理论上一些看上去并不十分复杂的类已经被证明是不可被有效学习的，从实践上也没有人知道诸如现在大家习以为常的人脸识别技术到底有没有希望实现。Valiant 的这些小尝试也被他认为是对可学习类范围的一种探索，从这篇文章中我们也可以看到一门学科和技术还在萌芽时从探索中成长的过程。
Valiant 最终被评授予图灵奖有这篇文章的很大功劳。但他对学习、智能的探索却从没停止，也不只局限于计算机学科之内，他对于神经科学以及生物的进化也有着浓厚的兴趣，就像“A Theory of the Learnable”中一样，他认为三者在一定程度上具有相似的范式。2013年他出版的书籍《Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World》中，Valiant 讲述了他最新的研究和思考。
伟大的理论和实践常常会被人忽视它的伟大，因为人们初次了解时往往就是在教科书中自然而然地接触这些概念。例如我们在学习图灵机的概念时，往往会默认它就是最自然的计算模型和定义方法，而忽视了它广泛而又深邃的意义。因此，结合其历史背景，从科学史或学科史的视角出发能够加深我们对知识本身的理解，也会让我们在面对未知问题时有更多的想法和勇气——阅读经典文献的意义可能就在于此。
参考文献：
[1] Valiant L G. A theory of the learnable [J]. Communications of the ACM, 1984, 27(11): 1134-1142.
[2] Mohri M, Rostamizadeh A, Talwalkar A. Foundations of machine learning [M]. MIT press, 2018.
[3] Shalev-Shwartz S, Ben-David S. Understanding machine learning: From theory to algorithms [M]. Cambridge university press, 2014.
[4] Valiant L. Probably approximately correct: nature's algorithms for learning and prospering in a complex world [M]. Basic Books (AZ), 2013.
文字 | 唐静吾
文中图片除署名外源自网络
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： lzxmw777
