周志华新作《机器学习理论导引》阅读攻略( 三 ) _理论

接下来讲的是复杂度。这一章承接上一章，可学性关注的是问题是否有解，而复杂度关注的是有多难解。在PAC理论中，可学性与假设空间的复杂程度密切相关，假设空间越复杂，搜索解的难度越大。当假设空间是有限的时候，可以通过层层筛选搜索解，但这就有了一个限制条件：假设空间必须有限。数学不喜欢局限，同时，很多模型的假设空间并非是有限的，那这时应该怎样刻画复杂度呢？这就是本章的主要内容。
本章同样有一个非常重要的概念， VC维。一般机器学习的教材如果选择放入一点学习理论的内容，通常至少会包括两个知识点，一个是前一章的PAC理论，另二个就着本章的VC维。VC维是一种刻画假设空间复杂度常用的方法，当然这不是唯一一种，本章同时也介绍了另一种，名为复杂度。
也许大家第一次看，会觉得PAC理论、VC维这些知识太过抽象，也不知道学来能有什么用。这些知识确实不太容易学懂，但都是学习理论的基础，也是最常用的研究工具，绝不是为学而学，学完就扔了的，后续的章节会反复使用这些基础和工具来研究更具体的问题。书里接下来安排的三章，包括第4章的泛化界、第5章的稳定性和第6章的一致性，可以看作是同一个大问题的三个大块，这个大问题就是模型效果评价。在机器学习中，模型效果毫无疑问是最需要关注的问题之一。
机器学习模型效果好不好，一般业内会用泛化能力强不强来评价。什么叫“泛化”呢？泛化指的是模型在不同数据集中的预测效果。为什么要考虑这个问题呢？如果看过我写的那本面向初学者的《机器学习算法的数学解析和实现》知道，所谓机器学习，就是拟合数据。要使用机器学习模型，首先是需要经过训练的，模型训练需要数据，这部分数据称为训练数据，或者叫训练集。
这里有一个隐含的知识点，每个数据集都有自己的分布特征，使用训练集训练模型，模型拟合的其实是训练集的特征，这就可能导致一个问题，过拟合问题。过拟合直白来说，就是模型学得太好了，这是初学者很费解的一个词，学得太好怎么能叫问题呢？这个问题我在《机器学习算法的数学解析和实现》也专门进行了介绍，学得太好当然不是问题，问题是不同的数据集可能会有不同的分布特征，模型在训练集上学得太好，在其它数据集上，具体来说，是在其它分布特征上，模型的预测性能反而可能下降，也就是过拟合使得模型的泛化能力下降了。这可能就会产生一个现象，泛化能力差的模型在训练时看起来效果不错，可是一部署到生产环境就变成了笑话，完全不可用了。这就是为什么无论是学术界还是工业界，都非常关心模型的泛化能力。
为了具体研究这个问题，《机器学习理论导引》首先介绍了泛化界，包括泛化误差上界和泛化误差下界。泛化界主要是基于不同的假设空间复杂度度量，这里就用到了前面譬如VC维等的知识，与具体的学习算法无关，但有一个局限，这些泛化误差界只能用于有限VC维学习算法的泛化性，而对无限VC维的学习算法无能为力。要解决这个问题，书里接着介绍了稳定性，用来刻画训练集的扰动对算法效果产生的影响。