@frank-shaw 2015-10-19T11:09:09.000000Z 字数 7419 阅读 3477

网易《机器学习》第9课--机器学习理论01

机器学习理论 网易机器学习

写在前面

码在线机器学习班的笔记博客，初衷之一就是将自己之前写在本子上的网易公开课《机器学习》笔记搬到网络上来。在线学习班的内容更广，基本上涵盖了网易公开课的内容，但是也有一小部分是网易公开课所独有的。机器学习理论这一块就是这独有的一块。在此特别写下来记录。

在接下来的3节课当中，我们将会重点讲解不同的机器学习算法的属性，这样就可以知道每个算法都使用于怎样的情景。真正能够将那些深刻理解机器学习的人和那些仅仅读过课本仅仅了解数学公式的人区分开来的，就是接下来我们要学习的内容。

偏差和方差

偏差和方差对应着欠拟合与过拟合的问题，此次课想要解决的问题是构建一个模型，对何时出现过拟合与欠拟合进行说明。
以之前提及过得房屋价格估计的例子为例，我们可以使用线性模型、二次模型或者高阶模型来拟合这组数据，对应的图像如下：
偏差和方差
看图可以知道，对于左图，用一个线性模型去拟合一个二次模型，即使在一个有很多训练样本的情况下训练，仍然会有很大的泛化误差，这种情况称之为欠拟合，对应着高偏差。同样的，右图高阶模型表示的并不是好的模型，此模型结构可能恰巧对训练样本几何能够很好拟合，但是对于一个新来的测试样本，效果就可能很差。这种模型仍然有很大的泛化误差，这种情况称之为过拟合。中图是二者的折中处理，我们认为该模型能够较好地拟合这组数据。
实际上，机器学习关注的是通过训练集训练过后的模型对测试样本的分类效果，我们称之为泛化能力。左右两图的泛化能力就不好。在机器学习中，对偏差和方差的权衡是机器学习理论着重解决的问题。

经验风险最小化（ERM, Empirical risk minimization）

我们以二分类问题，对ERM问题加以说明。定义训练集为： $S = \{x^{(i)},y^{(i)}\}，i=1,2,...,m$ 。其中，每对 $（x^{(i)},y^{(i)}） \sim D$ 属于独立同分布变量（IID）；其中 $y$ 取值 $\{0,1\}$ 。
针对线性分类问题，假设函数（hypothesis function）为：

h θ (x) = g (θ T x)

$h_{\theta}(x) = g(\theta^Tx)$
其中

g(z)={0,z<01,z≥0 $g(z) = \left\{ \begin{array}{l} 0, {\kern 1pt} z <0\\ 1,{\kern 1pt} z \geq 0 \end{array} \right.$

定义训练风险为：

ε^(h)=1m∑i=1m1{hθ(x(i))≠y(i)}

$\hat \varepsilon(h) = \frac{1}{m}\sum_{i=1}^m \mathbf{1}\{h_{\theta}(x^{(i)}) \neq y^{(i)}\}$
在机器学习理论中，

ε^(h) $\hat \varepsilon(h)$ 也被称为经验风险。我们可以看到，

ε^(h) $\hat \varepsilon(h)$ 表示的就是在训练集中被模型错分的概率（频率表示概率）。

ε^(h) $\hat \varepsilon(h)$ 依赖于训练集

S $S$ ,我们也可以表示成

ε^S(h) $\hat \varepsilon_S(h)$ 。

与之形成对比，定义生成风险为：

ε (h) = P (x, y) \sim D 1 {h θ (x) \neq y}

$\varepsilon(h) = P_{(x,y) \sim D} \mathbf{1}\{h_{\theta}(x) \neq y\}$
生成风险表示的是对于所有属于同一个独立同分布

D $D$ 的

（x(i),y(i)） $（x^{(i)},y^{(i)}）$ 被模型错分的概率，它不局限于训练样本集，也就是我们提到的"泛化能力"。

我们本来应该直接求解的是这个生成风险的大小的，但是无奈的是我们并不知道分布 $D$ 的具体分布情况（如果已经知道了，那么我们就不需要机器学习啦，直接从分布 $D$ 中提取信息就可以啦），由此，只能够从训练样本中的分布能够得到的训练风险来间接推断出生成风险了。

那么经验风险最小化（ERM）可表示为：

θ^= argmin ε^(h)

$\hat \theta = \operatorname*{argmin} \hat \varepsilon(h)$
即选择一个使得训练风险最小化的参数

θ $\theta$ 。由于上述表达式是非凸的，而且是一个NP难问题，我们无法对它进行优化。让我们尝试另一种表达方式以更好地服务于我们的问题。

定义假设函数集合 $\mathcal{H}$ :

H = {h θ : h θ (x) = 1 {θ T x \geq 0}, θ \in R n + 1}

$\mathcal{H} = \{h_{\theta}:h_{\theta}(x) = \mathbf{1}\{\theta^Tx \geq 0\},\theta \in \mathbb{R}^{n+1}\}$
值得注意的是，我们这里需要解决的是线性问题，因此使用的线性分类器的假设函数集合。其他分类器会有不同的表示形式。
此时，ERM算法可以看成是从

H $\mathcal{H}$ 中选择一个合适的

h $h$ ，使得经验风险最小化，即：

h^= argmin h \in H ε^(h)

$\hat h = \operatorname*{argmin}_{h \in \mathcal{H}} \hat \varepsilon(h)$

这节课，我们主要想解决当假设函数集 $\mathcal{H}$ 是有限集合的时候，ERM算法的解的表示形式。下节课再来对 $\mathcal{H}$ 为无限集合时做相应推导。为了得到想要的结论，我们还需要两个引理，铺垫可能有点长，但非常必要。

引理

引理1——联合界引理：
假设 $A_1,A_2,...,A_k$ 为 $k$ 个事件，可以相互独立也可有所关联，有下面式子成立：

P (A 1 \cup A 2 \cup . . . \cup A k) \leq P (A 1) + . . . + P (A k)

$P(A_1\cup A_2\cup...\cup A_k) \leq P(A_1)+...+P(A_k)$
可以从下图获得相应理解：
联合界引理

引理2——Hoffding不等式
假设 $Z_1,...,Z_m$ 为 $m$ 个属于bernoulli分布 $\phi$ 的独立同分布变量，即 $\left\{ \begin{array}{l} p(z_i = 1)= \phi\\ p(z_i = 0)= 1 - \phi \end{array} \right.$ 假设这 $m$ 个数的均值 $\hat \phi = \frac{1}{m} \sum_{i=1}^m z_i$ ，那么对于任意常数 $\gamma$ ，有以下不等式成立：

P (| ϕ - ϕ^| > γ) \leq 2 e x p (- 2 γ 2 m)

$P(|\phi - \hat \phi| > \gamma) \leq 2 exp(-2\gamma^2m)$
Hoffding不等式本质上说明一组独立同分布的随机变量的均值离开它的期望的可能性以指数形式衰减。我们使用

ϕ^ $\hat \phi$ 来估计

ϕ $\phi$ ，可知当训练样本数量

m $m$ 很大时，

ϕ^ $\hat \phi$ 远离

ϕ $\phi$ 的可能性是很小的。

ERM的证明

有了以上基础，回到我们的问题。对于有限的假设集合 $\mathcal{H}=\{h_1,...,h_k\}$ ，我们的策略是：

首先我们证明：对集合 $\mathcal{H}$ 的所有 $h$ ，经验风险 $\hat \varepsilon(h)$ 是对生成风险 $\varepsilon(h)$ 的很好估计。

其次我们证明：由ERM方法得到的 $\hat h$ （训练集经ERM得到的最优的假设函数）的生成风险是有上界的。

从集合 $\mathcal{H}$ 中随意选择一个特定的 $h_j \in \mathcal{H}$ ，定义属于bernoulli分布 $\phi$ 的变量 $z_i = \mathbf{1}\{h_j(x^{(i)}) \neq y^{(i)}\}$ ，也就是说 $p(z_i = 1)=p(h_j(x^{(i)}) \neq y^{(i)}) = \phi$ 。其中每个样本 $(x^{(i)},y^{(i)})$ 属于独立同分布 $D$ 中随机产生的样本，训练样本集合大小为 $m$ 。那么，经验风险为：

ε^(h j) = 1 m \sum i = 1 m z i

$\hat \varepsilon(h_j) = \frac{1}{m}\sum_{i=1}^mz_i$
其实，经验风险即为

m $m$ 个变量

z $z$ 的均值，那么根据Hoffding不等式，对于任意常数

γ $\gamma$ ，可得：

P (| ε (h j) - ε^(h j) | > γ) \leq 2 e x p (- 2 γ 2 m)

$P(|\varepsilon(h_j) - \hat \varepsilon(h_j)| > \gamma) \leq 2 exp(-2\gamma^2m)$
此式可证明，对于一个特定的

hj $h_j$ ，经验风险

ε^(hj) $\hat \varepsilon(h_j)$ 都是对生成风险

ε(hj) $\varepsilon(h_j)$ 的很好估计。但是，我们不仅仅期望对于某一个

h $h$ 有这一性质，更期望对于集合

H $\mathcal{H}$ 的每一个元素都成立：经验风险

ε^(hj) $\hat \varepsilon(h_j)$ 都是对生成风险

ε(hj) $\varepsilon(h_j)$ 的很好估计。下面我们来证明之。

定义事件 $A_i = |\varepsilon(h_i) - \hat \varepsilon(h_i)| > \gamma$ ，那么有：

p (A i) \leq 2 e x p (- 2 γ 2 m)

$p(A_i) \leq 2 exp(-2\gamma^2m)$
那么

P(∃hi∈H,|ε(hi)−ε^(hi)|>γ) $P(\exists h_i \in \mathcal{H},|\varepsilon(h_i) - \hat \varepsilon(h_i)| > \gamma)$ 表示的是在假设集合

H $\mathcal{H}$ 中，至少存在一个假设函数

hi $h_i$ 满足

|ε(hi)−ε^(hi)|>γ $|\varepsilon(h_i) - \hat \varepsilon(h_i)| > \gamma$ 的概率。根据概率论中的和事件的表达式，有：

P (\exists h i \in H, | ε (h i) - ε^(h i) | > γ) = P (A 1 \cup A 2 \cup . . . \cup A k)

$P(\exists h_i \in \mathcal{H},|\varepsilon(h_i) - \hat \varepsilon(h_i)| > \gamma) = P(A_1\cup A_2\cup...\cup A_k)$

使用联合界定理可得：

P (\exists h \in H, | ε (h i) - ε^(h i) | > γ) = P (A 1 \cup A 2 \cup . . . \cup A k) \leq \sum i = 1 k P (A i) \leq \sum i = 1 k 2 e x p (- 2 γ 2 m) = 2 k \cdot e x p (- 2 γ 2 m)

$P(\exists h \in \mathcal{H},|\varepsilon(h_i) - \hat \varepsilon(h_i)| > \gamma) = P(A_1\cup A_2\cup...\cup A_k) \\ \leq \sum_{i=1}^kP(A_i) \leq \sum_{i=1}^k 2 exp(-2\gamma^2m) = 2k · exp(-2\gamma^2m)$
用1减去两边，不等号方向改变，可得：

P (\neg \exists h \in H, | ε (h i) - ε^(h i) | > γ) = P (\forall h \in H, | ε (h i) - ε^(h i) | < γ) \geq 1 - 2 k \cdot e x p (- 2 γ 2 m)

$P(\neg \exists h \in \mathcal{H},|\varepsilon(h_i) - \hat \varepsilon(h_i)| \color{red}> \gamma) = P(\forall h \in \mathcal{H},|\varepsilon(h_i) - \hat \varepsilon(h_i)| \color{red}< \gamma) \\ \geq 1-2k · exp(-2\gamma^2m)$
从上式可以看出，对所有（任意一个）

h∈H $h \in \mathcal{H}$ ，至少有

1−2k⋅exp(−2γ2m) $1-2k · exp(-2\gamma^2m)$ 的概率，经验风险

ε^(hj) $\hat \varepsilon(h_j)$ 在生成风险

ε(hj) $\varepsilon(h_j)$ 的

γ $\gamma$ 范围内。这叫一致收敛性。同时，值得注意的是，这里的

k $k$ 指的是集合

H $\mathcal{H}$ 中

h $h$ 的个数。这就是生成风险可以用经验风险来表示的上界。这也就是我们经常在书本上看到“以

1−δ $1-\delta$ 的概率，作如下推断”的由来（其中

δ=2k⋅exp(−2γ2m) $\delta=2k · exp(-2\gamma^2m)$ 表示错误率）。

一致收敛的不同表示形式

我们可以看到，在上面的一致收敛表达式中，有3个参数： $m$ (训练样本数)、 $\gamma$ (表示 $\hat \varepsilon(h_j)$ 与 $\varepsilon(h_j)$ 的距离)、 $\delta$ (错误率， $\delta=2k · exp(-2\gamma^2m)$ )。我们可以尝试固定其中两个，改变其中一个来看看一致收敛的不同表述形式。上面的表达式就是在固定 $m,\gamma$ 的情况下，求 $\delta$ 的表达式。
形式二：
那么我就可以问：假如固定 $\gamma,\delta$ ，样本数量 $m$ 的表达式是怎样的？其实际意义是：至少需要多少训练样本，在选择一个固定常数 $\gamma$ 的前提下，可以保证有至少 $1-\delta$ 的概率，使得生成风险在经验风险的 $\gamma$ 范围内？
从 $\delta=2k · exp(-2\gamma^2m)$ 中可得：

m = 1 2 γ 2 l o g 2 k δ

$m = \frac{1}{2\gamma^2}log\frac{2k}{\delta}$
也就是说，实际需要的样本数至少要大于等于

12γ2log2kδ $\frac{1}{2\gamma^2}log\frac{2k}{\delta}$ 方可。该表达式让我们知道，一个模型或者算法要达到一个确定的性能时（达到特定的概率保证），需要的训练样本数。该表达式也被称为"样本复杂度"。
细细观察，可发现训练样本数量

m $m$ 与集合

H $\mathcal{H}$ 中元素总数

k $k$ 成

log k $log~k$ 的正比关系。我们知道实际上

log k $log~k$ 是增长很慢的一类函数。回忆一下，我们一开始的前提是集合

H $\mathcal{H}$ 中元素总数

k $k$ 是有限的，当我们将约束条件由有限推广到无限的时候，这个"样本复杂度"将会发挥更大的作用。先记着吧。
形式三：
同样的，我们可以固定

δ,m $\delta,m$ ，

γ $\gamma$ 的关系式又是怎样的呢？也就是：生成风险会落在经验风险的哪个范围呢？我们可以解得：

γ \leq 1 2 m l o g 2 k δ - - - - - - - - - \sqrt

$\gamma \leq \sqrt{\frac{1}{2m}log\frac{2k}{\delta}}$

$\hat h$ 的生成风险的上界

这个标题的表述可能会引发疑惑。我们通过查看 $\hat h$ 的定义，可以知道：

h^= argmin h \in H ε^(h)

$\hat h = \operatorname*{argmin}_{h \in \mathcal{H}} \hat \varepsilon(h)$
它表示的是集合

H $\mathcal{H}$ 中使得经验风险最小的那个假设函数。实际上，每一个假设函数 $h_i$ 都有经验风险与生成风险的说法，如果针对的是训练样本，那么得到的就是经验风险，如果针对的是无限样本分布 $D$ ，那么得到的就是生成风险。
理解了这个之后，让我们来定义：

h * = argmin h \in H ε (h)

$h^* = \operatorname*{argmin}_{h \in \mathcal{H}} \varepsilon(h)$
即

h∗ $h^*$ 为集合

H $\mathcal{H}$ 中生成风险最小的那一个假设函数。与之对比的是

h^ $\hat h$ ，表示的是集合

H $\mathcal{H}$ 中使得经验风险最小的那个假设函数。
在一致收敛定理成立的前提下，我们可以推导出如下结论：

ε (h^) \leq ε^(h^) + γ \leq ε^(h *) + γ \leq ε (h *) + γ + γ = ε (h *) + 2 γ

$\varepsilon(\hat h) \leq \hat\varepsilon(\hat h)+\gamma \leq \hat\varepsilon( h^*)+\gamma \leq \varepsilon( h^*)+\gamma +\gamma = \varepsilon( h^*)+2\gamma$
第一个不等式和第三个不等式都是一致收敛定理的直接应用。第二个不等式，因为计算的是经验风险，所以任何一个

h $h$ 生成的经验风险都要比最小的

h^ $\hat h$ 的

ε^(h^) $\hat\varepsilon(\hat h)$ 要大。
于是我们得出结论：在生成风险的判断上，由ERM算法得出来的生成风险的上界是最优假设函数 $h^*$ 的生成风险的加上 $2\gamma$ 。

综合理解

定理：令 $\mathcal{H}$ 是一个有限的假设函数集合， $|\mathcal{H}|=k$ ，给定训练样本数 $m$ 和错误率 $\delta$ ，我们有 $1-\delta$ 的概率，以下公式成立：

ε (h^) \leq min h \in H ε (h) + 2 1 2 m l o g 2 k δ - - - - - - - - - \sqrt

$\varepsilon(\hat h) \leq \operatorname*{min}_{h \in \mathcal{H} }\varepsilon(h) +2\sqrt{\frac{1}{2m}log\frac{2k}{\delta}}$
其中，不等式右边第一项就是

ε(h∗) $\varepsilon(h^*)$ ，第二项就是一致收敛定理中的第三种表现形式(

γ $\gamma$ ）。可将不等式右边第一项看成是偏差（bias），第二项看成是方差(variance)。该定理反映了偏差与方差之间的权衡。当我们选择一个更加复杂的模型集合

H $\mathcal{H}$ 时（比如由一次线性模型转变为二次模型），集合元素的个数

k $k$ 会增加（使用一个复杂模型集合表面可选择的假设函数变多了），不等式第二项会增大。与此同时，第一项

ε(h∗) $\varepsilon(h^*)$ 有可能会减小（由一次线性模型转变为二次模型，拟合曲线更加接近样本点，因此减小）。于是，如何调节偏差和方差成为了一个很重要的问题。选择一个最优值，使得偏差与方差之和最小，才能得到一个好的模型。