534
简单自学机器学习理论—— 泛化界限 (Part II )
首发地址：https://yq.aliyun.com/articles/67168
本文由北邮@爱可可-爱生活 老师推荐，阿里云云栖社区组织翻译。
以下为译文
part II- 泛化界限（第I部分内容点此；第III部分内容点此）
上节总结到最小化经验风险不是学习问题的解决方案，并且判断学习问题可解的条件是求：
在本节中将深度调查研究该概率，看其是否可以真的很小。
独立同分布
为了使理论分析向前发展，作出一些假设以简化遇到的情况，并能使用从假设得到的理论推理出实际情况。
我们对学习问题作出的合理假设是训练样本的采样是独立同分布的，这意味着所有的样本是相同的分布，并且每个样本之间相互独立。
大数法则
m
hoeffding
将其应用到泛化概率上，假设错误限定在0和1之间，则对于假设h有
这意味着训练与泛化误差之间的差大于
的概率是随着数据集的大小成指数衰减。
泛化界限：第一次尝试
为了针对整个假设空间都有泛化差距大于，表示如下：
使用布尔不等式，可以得到
使用
置信度1-δ有
使用基本代数知识，用δ表示得到：
上式就是第一次泛化界限，该式表明泛化错误是受到训练误差加上以假设空间大小和数据集大小的函数的限定。
检验独立性假设
首先需要问自己是否每一个可能的假设都需要考虑？答案是简单的，由于学习算法需要搜索整个假设空间以得到最优的解决方案，尽管这个答案是正确的，我们需要更正式化的答案：
泛化不等式的公式化揭示了主要的原因，需要处理现存的上确界，上确界保证了存在最大泛化差距大于“的假设上。
从上图可以看出是二分类问题，很明显彩色线产生的是相同的分类，它们有着相同的经验风险。如果只对经验风险感兴趣，但是需要考虑样本外的风险，表示如下：
为了确保上确界要求，需要考虑所有可能的假设。现在可以问自己，每一个有大泛化差距的假设事件可能是互相独立的吗？如果上图红线假设有大的泛化差距大于，那么可以肯定的是在该区域的每个假设也都会有。
这对我们的数学分析是没有帮助的，由于区域之间看起来取决于样本点的分布，因此没有方法在数学上精确获取这些依赖性，于是这些统一的界限和独立假设看起来像是我们能够做的最佳近似，但它高估了概率并使得这些界限非常接近，性能不好。
对称引理
’
（1）
该式意味着最大泛化差距大于’之间的经验风险差概率大于
的两倍，这被称作对称引理。
生长函数
如果我们有许多假设有着相同的经验风险，可以放心地选择其中一个作为整个群的代表，将其称作有效假设并抛弃其它的假设。
假设在
H
（2）
但由于是指数形式，随着m
VC
2D
从图中的判定边界，可清晰知道没有线性分类器能产生这样的标签，因为没有线性分类器能够以这样的方式划分空间，这一事实能够用来获得更好的限定，这使用
K是空间。
维数作为其替身，
将会是复杂度或者假设空间丰富度的测量。
VC
或者使用表示生长函数上的界限得到：
该式清晰并间接表示了学习问题是否可解，并针对无限假设空间，对其泛化误差有着有限的界限。
基于分布的界限
事实上，ρ，可以证明得到针对假设分类器有：
这就是支持向量机（SVM）背后的理论依据。
一个不等式去管理所有的它们
上面的所有分析是针对二元分类问题，然而
δ的函数，这个不等式基本说明泛化误差能够分解为两部分：经验训练误差和学习模型的复杂度。该不等式的形式对于任何学习问题、不管多么准确界限而言都是适用的。
参考文献：
l Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2012.
l Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
l Abu-Mostafa, Y. S., Magdon-Ismail, M., & Lin, H. (2012). Learning from data: a short course.
文章原标题《Machine Learning Theory - Part II》，作者：Mostafa Samir，译者：海棠
文章为简译，更为详细的内容，请查看原文
最后更新：2017-07-12 22:08:44