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$个不同事件，那么

$$P(A_1 \bigcup... \bigcup A_k) \le P(A_1) +...+P(A_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$，有

$$P(|\hat \phi - \phi| > \gamma) \le 2 \exp(-2\gamma^2m)$$

这里老师没给出证明，我自己之前写过一个初等证明——传送门，后面会整理老师给的补充材料里的证明，这里先使用这个结论。

为了简化讨论，这里将问题限制在二元分类问题中，即$y\in \{0,1\}$，假设训练集$S=\{(x^{(i)},y^{(i)});i=1,…,m\}$，$(x^{(i)},y^{(i)})$是来自同一分布$\mathcal D$的样本，对于一个假设$h$，定义训练误差（或经验风险，经验误差）：

$$\hat \epsilon(h) =\frac 1m \sum_{i=1}^m1\{h(x^{(i)})\ne y^{(i)}\}$$

不难看出，上述量即为$h$在训练集中误分类的比例。如果我们想明确表明$\hat \epsilon(h)$和某个训练集$S$的关系，我们可以写为$\hat \epsilon_S(h)$。此外，我们还定义泛化误差为：

$$\epsilon(h) = P_{(x,y)\sim \mathcal D}(h(x)\neq y)$$

即为从分布$\mathcal D$中抽取一个样本$(x,y)$，$h$分类错误的概率。我们的学习算法实际上是在做经验风险最小化（ERM)，即找到

$$\hat h =\arg \min_{h\in \mathcal H} \hat \epsilon(h)$$

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) =\frac 1m \sum_{j=1}^m Z_j$$

因此，$\hat \epsilon(h_i)$是$m$个随机变量的均值，这些随机变量独立同分布，都来自均值为$\epsilon(h)​$的伯努利分布，所以我们可以使用Hoeffding不等式，得到

$$P(| \epsilon(h_i) -\hat \epsilon(h_i)| > \gamma ) \le 2\exp(-2\gamma^2 m)$$

这说明对于某个特定的$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)​$，因此使用第一个引理可得

$$\begin{aligned} P(\exists h_i\in \mathcal H,| \epsilon(h_i) -\hat \epsilon(h_i)|>\gamma ) &=P(A_1\bigcup ...\bigcup A_k) \\ &\le \sum_{i=1}^k P(A_i)\\ &\le \sum_{i=1}^k 2\exp(-2\gamma^2 m)\\ &\le 2k\exp(-2\gamma^2 m) \end{aligned}$$

两边同时减$1​$可得

$$\begin{aligned} P(\neg \exists h_i\in \mathcal H,| \epsilon(h_i) -\hat \epsilon(h_i)|>\gamma ) &=P(\forall h\in \mathcal H.| \epsilon(h_i) -\hat \epsilon(h_i)|\le \gamma)\\ &\ge 1- 2k\exp(-2\gamma^2 m) \end{aligned}$$

上述不等式的含义为，有至少$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$范围内，我们令

$$1- 2k\exp(-2\gamma^2 m) \ge 1-\delta$$

可得

$$2k\exp(-2\gamma^2 m)\le \delta\\ \exp(2\gamma^2 m) \ge \frac{2k}{\delta}\\ m \ge \frac{1}{2\gamma^2} \log \frac{2k}{\delta}$$

这说明当$m \ge \frac{1}{2\gamma^2} \log \frac{2k}{\delta}$时，我们有$1-\delta$概率使得训练误差在泛化误差$\gamma$范围内。

类似的，我们可以固定$m$和$\delta$，在之前的问题中解出$\gamma$，令

$$1- 2k\exp(-2\gamma^2 m) \ge 1-\delta$$

可得

$$2k\exp(-2\gamma^2 m)\le \delta\\ \exp(2\gamma^2 m) \ge \frac{2k}{\delta}\\ r \ge \sqrt{\frac{1}{2m} \log \frac{2k}{\delta}}$$

取$r= \sqrt{\frac{1}{2m} \log \frac{2k}{\delta}}$，我们有$1-\delta$的概率使得

$$| \epsilon(h) -\hat \epsilon(h)| \le \sqrt{\frac{1}{2m} \log \frac{2k}{\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​$中最佳假设，那么

$$\begin{aligned} \epsilon(\hat h) &\le \hat\epsilon(\hat h) + \gamma \\ &\le \hat\epsilon(h') + \gamma \\ &\le \epsilon(h') + 2\gamma \end{aligned}$$

第一个和第三个不等号是因为$| \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$的概率，我们有：

$$\epsilon(\hat h) \le \Big(\min_{h\in\mathcal H}\epsilon(h)\Big) + 2 \sqrt{\frac{1}{2m} \log \frac{2k}{\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}$时，一致收敛成立，因此：

$$\epsilon(\hat h) \le \Big(\min_{h\in\mathcal H}\epsilon(h)\Big) + 2 \gamma$$

所以可以给出如下推论：

推论

令$|\mathcal H|=k$，$\gamma $和$\delta$为任意的固定值，那么要使$\epsilon(\hat h) \le \Big(\min_{h\in\mathcal H}\epsilon(h)\Big) +
2 \gamma$有大于等于$1-\delta$的概率发生，只要有

$$\begin{aligned} m &\ge \frac{1}{2\gamma^2} \log \frac{2k}{\delta} \\ &=O\Big(\frac{1}{\gamma^2} \log \frac{k}{\delta}\Big) \end{aligned}$$