简论机器学习基石

机器学习理论中关键词生硬难懂，因此对部分关键词进行解析。
假设空间：学习任务的设定决定假设空间，从而也决定了可学性、复杂度。
概念类：假设空间中一个可解决任务的模式，也可以理解为函数。
泛化误差是指全量数据的误差，而经验误差是指采样数据的误差。

机器学习本质上是在任务决定的假设空间内利用算法搜索概念类，从而学习出一个函数与概念类接近，函数的经验误差尽可能接近最小经验误差，最终导致学习出函数接近的概念类泛化误差尽可能小。
例如：目标检测任务是指从图片中检测出对象，不仅要框定对象，且要分类。最直接的方法是直接预测图片中对象的中心位置、对象的boxs宽与高、对象类别，那么这样会造成假设空间巨大，学习难度很大。因此，R-CNN利用区域提出方法降低了假设空间大小，从而降低了学习难度；YOLO对图片进行网格划分，预测每个网格是否包含对象、中心坐标，也降低了假设空间的大小。无论R-CNN，还是YOLO，都是通过引入先验的方式，降低学习难度，增加其可学性！
机器学习理论研究的主要内容是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

可学性

若存在算法$\zeta$对于任何样本数量大于等于特定多项式函数$poly$的样本集，都能从假设空间$H$中辨识概念类$C$，那么称概念类$C$对假设空间$H$而言是PAC可学。
然而，现实中概念类往往不可知，更不用说获得假设空间和概念类恰好相同的算法。因此，往往需要研究的是概念类与假设空间不同的情况。
根据Hoeffding不等式，随着样本数增多，假设空间的泛化误差与经验误差越来越接近，即经验误差与泛化误差有密切关系。
若存在算法$\zeta$和多项式函数$poly$，使得对任何样本数量大于等于多项式函数$poly$的样本集，算法$\zeta$能够从假设空间$H$中输出满足泛化误差与最优泛化误差尽可能接近，那么假设空间是不可知PAC可学的。
由以上可知，需要考虑的是学习算法输出假设的泛化误差与最优假设泛化误差之间的区别。 然而，真实分布$D$往往未知，通常无法直接计算。不过，由于经验误差与泛化误差有密切联系，我们可以借助经验误差来进行比较，于是有必要考虑经验误差与泛化误差之间的差距，这就是泛化界要讨论的问题。

复杂度

对于有限假设空间复杂度，只需根据包含假设的数目来刻画假设空间的复杂度；对于无限假设空间的复杂度，无法直接用假设的数目来刻画。无限假设空间复杂度刻画的方法有与数据分布无关的VC维、Natarajan复杂度，也包括与数据分布相关的Rademacher复杂度。

数据分布无关

首先，理解一下增长函数。增长函数是指假设空间$H$对m个样本所能赋予标记的最大可能的结果数。
VC维是指能被假设空间$H$打散的最大样本集大小，即假设空间$H$包含样本集中所有可能情况的最大样本集$d$。这并不意味着假设空间可以打散任意大小为$d$的样本集。因此，假设空间的VC维越小，则复杂度越低，从而学习难度越低。
与VC维适用于二分类问题相比，Natarajan复杂度适用于多分类问题，即VC维的扩展。

数据分布有关

与VC维相比，Rademancher复杂度考虑数据分布。因此对于特定数据分布，该复杂度的上界小于等于VC维的常数倍。

若VC维无穷大，那么该算法考虑的假设空间无穷大，从而复杂度最高，算法的表达能力也更强。

泛化界

稳定性主要基于可学性和复杂度理论研究算法泛化误差的上下界。泛化误差的上界表明只要数据集足够的多，那么算法在假设空间内一定能找到最优贝叶斯分类器的近似；泛化误差的下界表明，任何学习算法都存在某一种数据分布，当样本数目有限时，学习算法都不能以较大概率输出目标概念的近似，即No free launch!
因此，数据量与特征的构造对算法设计很重要。

稳定性

稳定性研究的内容是数据集的扰动对算法表现的影响，证明了经验风险与留一风险可看作泛化风险的经验估计，留一风险为泛化风险的无偏估计。若替换样本或删除样本，算法的泛化风险变化是有界的，那么算法具有稳定性。进一步的，算法的泛化风险就能被经验风险所限定，即泛化风险小于经验风险与样本数量开方倒数线性和的关系，即可根据经验风险知泛化风险。
同时，若算法对于替换样本具有稳定性，那么算法在数据集上也就不会过拟合。
稳定性与可学性之间的关系是：若算法在数据集上具有经验风险最小化，且算法具有稳定性，那么函数空间是不可知PAC可学的。稳定性与函数空间的复杂度无关，而可学性与函数空间的复杂度有关，经验风险最小化建立了稳定性与可学性之间的关系。

一致性

可学性、复杂度、泛化界、一致性都是基于分类问题讨论的，只有稳定性适用于所有问题。在一致性的讨论中，利用实值函数作为分类器，可见一定不是寻找的概念，即不可知的。一致性的研究，是希望找到一个充分条件。该充分条件能够使算法随着数据不断的增多，替代风函数无限接近最优替代风险函数。与此同时，真正风险函数也无限接近最优风险函数，即有效优化。

收敛率

收敛率研究的是随着目标函数的优化，收敛到最优值的速度。对于收敛率，相关的引理和定理只适用于凸优化问题，且部分定理需要满足Lipschtiz条件。

遗憾界

遗憾界研究的是在线学习的收敛率，根据相关定理可知在线学习的难度较离线学习难度高。其中，遗憾是指在线学习的风险与最优离线风险之差。