《机器学习》笔记-计算学习理论（12）

刘才权

写在最前面

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

• 基础知识
• PAC学习
• 有限假设空间
• VC维
• Rademacher复杂度
• 稳定性

（一）基础知识

顾名思义，计算学习理论(computation learning theory)研究的是关于通过“计算”来进行“学习”的理论。即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

（二）PAC学习

计算学习理论中最基本的是概率近似正确(Probably Approximately Correct，简称PAC)学习理论。
给定训练集D，我们希望基于学习算法ξ学得的模型所对应的假设h尽可能接近目标概念c。
PAC学习中一个关键因素是假设空间H的复杂度。H包含了学习算法ξ所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即H=C，这称为“恰PAC可学习”（properly PAC learnable）；直观地看，这意味着学习的能力与学习任务“恰好匹配”。然而，这种让所有候选假设都来自概念类的要求看似合理，但却并不实际，因为在现实应用中我们对概念类C通常一无所知，更别说获得一个假设空间与概念类恰好相同的学习算法。显然，更重要的研究假设空间与概念类不同的情形，即H≠C。一般而言，H越大，其包含任意目标概念的可能性越大，但从中找到某个具体目标概念的难道也越大。|H|有限时，我们称H为“有限假设空间”，否则称为“无限假设空间”。

（三）有限假设空间

• 可分情形
  可分情形意味着目标概念c属于假设空间H，即c∈H；
• 不可分情形
  对较为困难的学习问题，目标概念c往往不存在与假设空间H中；

（四）VC维

现实学习任务所面临的通常是无限假设空间。欲对此种情形的学习性进行研究，需度量假设空间的复杂度。最常见的办法是考虑假设空间的“VC维”（Vapnik-Chervonenkis dimension）。

（五）Rademacher复杂度

基于VC维的泛化误差界是分布无关、数据独立的，也就是说，对任何数据分布都成立。这使得基于VC维的学习性分析结果具有一定的“普适性”；但从另一个方面来说，由于没考虑数据自身，基于VC维得到的泛化误差界通常比较“松”，对那些与学习问题的典型情况相差甚远的较“坏”分布来说尤其如此。
Rademacher复杂度（Rademacher complexity）是另一种刻画假设空间复杂度的途径，与VC维不同的是，它在一定程度上考虑了数据分布。

（六）稳定性

无论是基于VC维还是Rademacher复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关。对所有学习算法都适用。这使得人们能够脱离具体学习算法的设计来考虑学习问题本身的性质。但在另一方面，若希望获得与算法有关的分析结果，则需另辟蹊径。稳定性（stability）分析是这方面一个值得关注的方向。
顾名思义，算法的“稳定性”考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。