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$的概率发生,只要有

本文标题:CS229 Lesson 9 经验风险最小化

文章作者:Doraemonzzz

发布时间:2018年12月12日 - 22:11:00

最后更新:2019年03月01日 - 14:20:49

原始链接:http://doraemonzzz.com/2018/12/12/CS229 Lesson 9 经验风险最小化/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。