训练集上误差小，往往测试集上误差也小。这是为什么呢？
瞧瞧上节课证明的：
也就是说，当样本数趋向于无穷，用MLE估计得到的、使得训练损失最小的参数，在真实分布中的损失也差不离。
这个大样本渐进性质美中不足的是得有个假设，要求给定真实的话，数据的分布是well-specified的。不过，即便没有这个假设，我们也能给出更一般的性质：
美中不足其二是，（1）忽略了n的高阶项，可能也忽略了p不能被忽略的高阶项，比如。这要求
才能小于1。
那么在这节课中认识有限样本的性质吧。
1 符号
这节略过吧，除了大O记号、之外没有新朋友要介绍给大家认识。作者特别提示，
不是一个随机数，它代表着真实值，而
是随机数，它是由
学出来的，
又是又带随机性的数据估计的。所以
也是个随机数咯。
2 目标
渐进性质是关于经验损失和真实损失之间的差，那么有限样本性质也得整个类似的：
也就是有至少的概率使得
。
根据定义我们已经知道了，要证这个类似
的东西，得找个
或者
来过桥。
那其实后面那个近似好证啊，不是个随机变量，
是各个期望为
的样本的算术平均，很容易能得到一个concentration inequality：
这个不等式对任何常数都成立。
难就难在上。concentration inequality只对特定的参数有效，由于
是个随机数，我们得用一个更强的concentration property，来说明这个近似对于
的每一个假设都成立。于是我们的一致收敛性质登场了。
3 一致收敛
刚才说了，一致收敛就是对于集合内的所有可能都收敛：
这样一来，对于所有的参数值，就能保证训练损失和实际的期望损失非常接近了。
如图(a)，一致收敛只要保证误差依概率在范围内波动，当然更好的情况如(b)连形状都相似
过桥证明打算这么写：
假设一致收敛能证，那么训练参数和真实参数的期望损失之差就有了上界。
一般这种概率不等式都会用到Hoeffding's inequality：
独立随机变量，满足
a.s.，那么对于任意
有：
套用在的
上就是：
再给一个很松的放缩：
令，反求一下能得到
。也就是说，至少
的概率
回到最初想要证明的过桥式，替换掉可得至少
的概率满足：
定理3
如果且
有限，那么就有式子(2)(3)(4)。
(4)也可以看做是中心极限定理的量化版本。
4 PAC 学习
定义4（Valiant提出的PAC学习算法）
是一个关于
的PAC学习算法，如果对于任何
的分布
、
和
：
满足
并且在size(
)、
、
上以多项式时间运行。
评论5
非正式地，size()是
的比特数，比如如果
有限的话，取
。那更通常的情况呢，
被实数参数化的话，那么这个定义要求
先离散化。
评论6
定义4暗示了样本量也是size()、
、
的多项式数量级上，不然
读完所有数据的时间都不够。
上述Valiant框架有一个局限性，它得对每一个分布都管用，这其实有点太激进，不现实。近年来提出的学习理论往往都对分布要求一些特定的假设，比如正态啦、可实现啦（意思就是
包含了你要学的函数）。
所以学习理论经常会cue一些假设，大都这么写：
- 理论A P说明了Q
- 理论B 在特定假设下，P说明了Q
- 理论C 在特定假设下，P说明了Q'，Q'强于Q。
理论B是三个里最弱的，A和C没法比较。
深度学习里Q经常是没意义的，这样的话我们会用理论C，加个假设得到有意义的结论Q'，然后告诉大家这个假设什么时候可以弱化、什么时候可以消除。
网友评论