M.KEARNS和COLT

       本文以Michael Kearns和Umesh Vazirani的经典书An introduction to Computational learning theory, MIT 1994 为素材，说点计算学习理论中的一些话题。

前序

Pennsylvania大学Michael Kearns将作为北京ICML 2014的Keynote Speaker，题目是Algorithmic Trading and Machine Learning 。虽然Kearns兴趣目前重在社会网络、经济博弈的算法和机器学习研究（ICML 2014上有文章），但今天要讲的是他博士论文的主题：计算学习理论。

计算学习理论

计算学习理论Computational Learning Theory (COLT) 研究自适应算法的设计与分析，一面重在严格的数学分析，另一面又关心计算和样本的高效性。他想回答诸如这样的问题：学习问题是否有独立于学习算法的固有难度分类？在什么样的条件下成功的学习是可能的或者不可能的？ 成功学习的样本复杂度有何要求与保证？ （做个类比，计算理论中诸如上述的问题是P类问题与NP类问题，计算时间开销和空间开销）

PAC学习模型

提到计算学习理论，自然联想到probably approximately correct（PAC）学习模型，它为学习问题提供了统一的表示和框架，在此基础下，就可以定义什么是成功的学习。（做个类比，有了图灵机就可以定义什么是计算，有了计算模型就可以定义什么是P类问题与NP类问题） PAC模型（或distribution-free model）是Kearns的博导哈佛教授Leslie Valiant 在1984年提出来的：A theory of the learnable，这也是Valiant获2010年图灵奖的主要原因。这是一个被动学习的概率模型，用epsilon-delta语言刻画了概念类C、假设类H、样本分布D、样本维度n之间的关系 ，其中epsilon（错误参数Error parameter）界定了学到的假设在分布D下的错误，名曰“近似正确”，而delta（置信参数confidence parameter）描述了从H中学到好假设的概率，名曰“可能”，故整个叫做可能近似正确学习模型。有了PAC模型，就可以定义什么是成功的/高效的学习，粗略的说即学习算法的样本复杂度和计算复杂度关于1/epsilon和1/delta等参数是多项式级的。

Occam学习

PAC模型在任意给定分布的情况下定义学习为算法输出的假设的预测能力，反过来假如只给定部分的学习样本，而将学习定义为寻求简单的假设以解释这些可观察的样本，那么这样的定义就是Occam学习。如果我们将简单性当做假设表示的长度，那Occam原理/剃刀就是寻找可观察数据中的模式以有效的压缩该数据集。 Occam剃刀作为具有一般哲学意义的科学方法论，对他有多种角度的解释，反过来也可以用它解释其他方法的合理性，如贝叶斯模型推理惩罚复杂模型（一个例子是David Barber：A note on Occam's razor，2013）。 已经证明，PAC可学习与Occam学习是等价的。计算学习理论中另一个更著名的等价性是强弱PAC学习。

The strength of weak learnability（强弱PAC学习的等价性）

弱PAC学习即仅比随机猜测好那么一点点，强PAC学习就是原来定义的PAC学习，回顾PAC模型的定义有两个参数：epsilon错误参数和delta置信参数，将一个弱学习算法提升为一个强学习就是要提升这两个参数。其中提升置信参数delta比较容易，因为学习算法输出的假设有错误保证，为了提高正确性概率，可以生成一堆独立的假设池，从中选择一个好假设即可。而提升错误参数较有技巧一点，关键在于串行生成一些列假设，后续的假设要重点关注之前的假设犯错误的那些样本，最终采取投票策略降低整体错误风险。 ROBERT SCHAPIRE和Yoav Freund在九十年代初各自构造性地从弱学习算法提升到强学习，共同获得了2003年哥德尔奖（理论计算机科学最高奖），并合著书Boosting: Foundations and Algorithms, MIT 2012 Boosting/AdaBoost是机器学习中集成学习的一种重要方法，可归为串行集成学习方法，即它的基学习器（假设）的生成有前后依赖关系，因为后续基学习器将更加关注之前基学习器犯错误的那些样本。另外一种集成学习方法的范式就是并行集成，如Bagging/Random Forest。串行和并行的分类方法来自南京大学教授周志华书Ensemble methods: Foundations and Algorithms, CRC 2012

Vapnik–Chervonenkis维

VC维由于与统计学习理论更加密切，故这里就不在叙述。有机会的话把它与SVM一并再做介绍。

后序

细心一点会发现，Kearns的博士论文献给他的母亲（当然了还有父亲）Alice Chen，显然这是一个中国人的姓氏Chen。事实上，Kearns的外公就是Chen Shou-yi陈受颐（1899-1978），广东番禹（广州）人，历史学家和文学家，25年留学芝加哥，曾任国立中央研究院院士，中国比较文学和中西文化交流史研究先驱。相信这次Kearns来中国会有与Michael Jordan不一样的感受。

Notes和资料

1. Kearns 1989年博士论文The Computational Complexity of Machine Learning http://www.cis.upenn.edu/~mkearns/papers/thesis.pdf
2. Kearns在ICML 2014上的文章Pursuit-Evasion Without Regret, with an Application to Trading 和Learning from Contagion (Without Timestamps)
3. COLT的定义来自Freund and Schapire http://www.learningtheory.org/
4. COLT关注的问题来自Tom Michell机器学习1997
5. 贝叶斯模型推理惩罚复杂模型的例子David Barber ：A note on Occam's razor http://web4.cs.ucl.ac.uk/staff/D.Barber/publications/note_occam.pdf