通过简单的泛化误差上界的证明，说明机器能进行学习和预测的基本原理。

直观的理解

---

在有限的训练数据中得到一个规律，认为总体也是近似这个规律的，那么就能用这个规律进行预测。比如一个大罐子里装满了红球和白球，各一半，我随手抓了一把，然后根据这些红球白球的比例预测整个罐子也是这样的比例，这样做不一定很准确，但结果总是近似的，而且如果抓出的球越多，预测结果也就越可信。

上面的例子可以简单直观地理解一下预测的原理，其实还可以通过统计的方法对这个近似（用局部的规律近似总体的规律）的可信度进行概率分析。

将问题描述成更数学的形式：

---

• 损失函数（loss function）或者代价函数（cost function）度量预测错误的程度，记作\(L(Y,f(x))\)。
• 期望损失（expected loss），即平均意义下的损失：
  \[R_{exp}(f)=E_p[L(Y,f(X))]=\int_{\mathcal{X}\times \mathcal{Y}}L(y,f(x))P(x,y)dxdy\]
• 经验损失（empirical loss），是关于训练数据集的平均损失：
  \[R_{emp}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_i,f(x_i))\]
• 根据大数定理，样本容量\(N\)趋近无穷时，经验风险趋近于期望风险：\(R_{emp}(f)\approx R_{exp}(f)\)，也就是说：如果模型在训练样本中的期望风险很小，那么它也能使得期望风险很小。
• 但是当样本容量\(N\)不是无穷大的时候怎么办？

泛化误差上界（定理）：

---

对二分类问题，当假设空间是有限个函数集合\(\mathcal F=\left \\{ f_1,f_2,\cdot \cdot \cdot ,f_d \right \\}\)时，对任意一个函数\(f\in \mathcal F\)，至少以概率\(1-\sigma\)，以下不等式成立：

\[R(f)\leqslant \hat{R}(f)+\varepsilon (d,N,\delta )\]

其中，

\[\varepsilon (d,N,\delta )=\sqrt{\frac{1}{2N}\left ( \log d+\log\frac{1}{\delta } \right )}\]

不等式左端\(R(f)\)是泛化误差，右端为泛化误差上界。泛化误差上界中，第一项是训练误差，训练误差越小，泛化误差也越小。第二项\(\varepsilon (d,N,\delta )\)，\(N\)越大，值越小，假设空间\(\mathcal F\) 包含的函数越多，值越大。

这个定理可以从概率上说明使用经验风险近似期望风险的可信度，它与样本数量以及假设空间的复杂度有关。

上述定理可通过Hoeffding不等式来证明:

---

Hoeffding不等式：

Hoeffding不等式适用于有界的随机变量。设有两两独立的一系列随机变量\(X_1,...,X_n\)。假设对所有的\(1\leqslant i\leqslant n\)，\(X_i\)都是几乎有界的变量，即满足\(\mathbb{P}(X_i\in\left [ a_i,b_i \right ])=1\)，那么这\(n\)个随机变量的经验期望：\(\bar{X}=\frac{X_1+\cdot \cdot \cdot +X_n}{n}\)满足以下不等式：

$$\mathbb{P}(\bar{X}-\mathbb{E}\left [ \bar{X} \right ]\geq t)\leq\exp (-\frac{2t^2n^2}{\sum _{i=1}^n(b_i-a_i)^2})$$

$$\mathbb{P}(\left |\bar{X}-\mathbb{E}\left [ \bar{X} \right ] \right |\geq t)\leq 2\, exp (-\frac{2t^2n^2}{\sum _{i=1}^n(b_i-a_i)^2})$$

---

对任意函数\(f\in \mathcal F\)，\(\hat {R}(f)\) 是\(N\)个独立随机变量\(L(Y,f(X))\)的样本均值（经验期望），\(R(f)\)是期望，如果损失函数取之区间为[0, 1]，则根据上述Hoeffding不等式，得到：

\[P(R(f)-\hat{R}(f)\geqslant \varepsilon )\leqslant \exp (-2N \epsilon ^2)\]

由于$\mathcal F =\left \{ f_1,f_2,...,f_d \right \} $是一个有限集合，容易得到：

\[P(R(f)-\hat{R}(f)\geqslant \varepsilon )\leqslant d \exp (-2N \epsilon ^2)\]

令

\[\delta =d \exp(-2N\varepsilon ^2)\]

然后就得到了：

\[P(R(f)< \hat{R}(f)+ \varepsilon )\geqslant 1-\delta\]

上面的讨论只是假设空间包含有限个函数的情况下的泛化误差上界，对于一般的假设空间要找到泛化误差界应该就没这么简单了。

(注：本文为读书笔记与总结，侧重算法原理，来源为一书第一章)

作者：

出处：

关于作者：目前主要研究领域为机器学习与无线定位技术，欢迎讨论与指正！