CS229 Lesson 9 经验风险最小化
课程视频地址:http://open.163.com/special/opencourse/machinelearning.html
课程主页:http://cs229.stanford.edu/
更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a
笔记参考自中文翻译版:https://github.com/Kivy-CN/Stanford-CS-229-CN
CS229是吴恩达老师在斯坦福教授的课程,内容比coursera更加深入,非常值得学习,之前学的时候没有仔细做笔记,感觉效果不是很好,决定从第九讲开始做一个详细的笔记,之前的部分后续补上。
Part V 学习理论(Learning Theory)
1 偏差/方差的权衡(Bias/variance tradeoff )
首先看下下图:
我们的目标函数是二次的,第一张图采用一次函数拟合,第三张图采用五次函数拟合,这两种情况的泛化误差都很大,但是产生的原因是不同的。第一张图在训练集上误差就很大,并且无论训练集有多少数据,得到的效果都不会太好,因为一次函数很难捕捉二次函数的特点,这种情形称为欠拟合,偏差很大;第三张图中训练集上的误差为$0$,这种情形往往是只捕捉到训练数据的模式,但是没有捕捉到$x,y$更广泛的模式,如果我们计算不在训练集中数据的损失函数,会发现损失往往非常大,这种情形称为过拟合,方差很大。在实际操作过程中,我们需要对偏差,方差进行权衡,既不能使用太简单的模型(欠拟合),也不能使用太复杂的模型(过拟合)。
2 预先准备(Preliminaries)
这里介绍两个后续讨论需要用到的引理:
引理(The union bound)
$A_1, A_2,…,A_k$是$k$个不同事件,那么
这个是概率论公理体系中的假设,不需要证明。
引理 (Hoeffding inequality)
设$Z_1,…,Z_m$是$m$个独立同分布,服从伯努利分布$b(1,\phi)$,即$P(Z_i=1)= \phi,P(Z_i=0)= 1-\phi$,令$\hat \phi =\frac 1m \sum_{i=1}^m Z_i$,那么对任意固定$\gamma>0$,有
这里老师没给出证明,我自己之前写过一个初等证明——传送门,后面会整理老师给的补充材料里的证明,这里先使用这个结论。
为了简化讨论,这里将问题限制在二元分类问题中,即$y\in \{0,1\}$,假设训练集$S=\{(x^{(i)},y^{(i)});i=1,…,m\}$,$(x^{(i)},y^{(i)})$是来自同一分布$\mathcal D$的样本,对于一个假设$h$,定义训练误差(或经验风险,经验误差):
不难看出,上述量即为$h$在训练集中误分类的比例。如果我们想明确表明$\hat \epsilon(h)$和某个训练集$S$的关系,我们可以写为$\hat \epsilon_S(h)$。此外,我们还定义泛化误差为:
即为从分布$\mathcal D$中抽取一个样本$(x,y)$,$h$分类错误的概率。我们的学习算法实际上是在做经验风险最小化(ERM),即找到
3 有限个假设(finite $\mathcal H$)的情况
我们先开始考虑假设类有限的学习问题,假设类$\mathcal H = \{h_1,…,h_k\}$有$k$个将$\mathcal X$映射到$\{0,1\}$的函数,经验风险最小化即为从$k$个假设中选择训练误差最小的函数。
现在任取$h_i\in \mathcal H$,对于$\mathcal D$中样本$(x,y)$,考虑伯努利随机变量$Z= 1\{h_i(x)\ne y\}$,类似地定义$Z_j= 1\{h_i(x^{(j)})\ne y^{(j)}\}$,
由于我们的样本是从$\mathcal D$获得的独立同分布随机变量,所以$Z,Z_j$同分布,此外,训练误差可以写为
因此,$\hat \epsilon(h_i)$是$m$个随机变量的均值,这些随机变量独立同分布,都来自均值为$\epsilon(h)$的伯努利分布,所以我们可以使用Hoeffding不等式,得到
这说明对于某个特定的$h_i$,当$m$很大时,其训练误差和泛化误差非常接近。但是我们不仅仅希望$\epsilon(h_i)$和$\hat \epsilon(h_i)$很接近,我们希望对每个$h\in \mathcal H$上述事实都成立。令$A_i$表示事件$| \epsilon(h_i) -\hat \epsilon(h_i)| > \gamma$,我们已经证明了$P(A_i)\le 2\exp(-2\gamma^2 m)$,因此使用第一个引理可得
两边同时减$1$可得
上述不等式的含义为,有至少$1- 2k\exp(-2\gamma^2 m)$的概率,对任意$h\in \mathcal H$,$\epsilon(h)$落在$\hat \epsilon(h)$附近的$\gamma$范围内,这被称为一致收敛,因为上界对每个$h\in \mathcal H$成立。注意上述结论中有$3$个重要的量——$m,\gamma$以及概率,其中一个量可以用另外两个量来约束。
例如考虑如下问题,给定$\gamma$,$\delta$,$m$需要多大,才能保证至少有$1-\delta$概率使得训练误差在泛化误差$\gamma$范围内,我们令
可得
这说明当$m \ge \frac{1}{2\gamma^2} \log \frac{2k}{\delta}$时,我们有$1-\delta$概率使得训练误差在泛化误差$\gamma$范围内。
类似的,我们可以固定$m$和$\delta$,在之前的问题中解出$\gamma$,令
可得
取$r= \sqrt{\frac{1}{2m} \log \frac{2k}{\delta}}$,我们有$1-\delta$的概率使得
现在假设一致收敛成立,即$| \epsilon(h) -\hat \epsilon(h)| \le \gamma$对每个$h\in \mathcal H$,接下来证明$\hat h =\arg \min_{h\in \mathcal H} \hat \epsilon(h)$的泛化误差上界。定义$h’=\arg \min_{h\in \mathcal H} \epsilon(h) $,注意$h’$为$\mathcal H$中最佳假设,那么
第一个和第三个不等号是因为$| \epsilon(h) -\hat \epsilon(h)| \le \gamma$对每个$h\in \mathcal H$都成立,第二个不等号是因为$\hat h =\arg \min_{h\in \mathcal H} \hat \epsilon(h)$,所以如果一致收敛成立,那么$\hat h $的泛化误差最多和$\mathcal H$中最佳假设相差$2\gamma$。
将以上内容总结为定理:
定理
令$|\mathcal H|=k$,$m$和$\delta$为任意的固定值,那么至少有$1-\delta$的概率,我们有:
这里的$\sqrt{\frac{1}{2m} \log \frac{2k}{\delta}}$是由$2k\exp(-2\gamma^2 m)=\delta$解得,之前已讨论过。如果我们我们假设集更复杂,即$k$更大,那么我们实际上在减少第一项,增加第二项。
结合之前的讨论,固定$\gamma, \delta$,当$m \ge \frac{1}{2\gamma^2} \log \frac{2k}{\delta}$时,一致收敛成立,因此:
所以可以给出如下推论:
推论
令$|\mathcal H|=k$,$\gamma $和$\delta$为任意的固定值,那么要使$\epsilon(\hat h) \le \Big(\min_{h\in\mathcal H}\epsilon(h)\Big) +
2 \gamma$有大于等于$1-\delta$的概率发生,只要有