Reference

统计学习方法（一）：泛化误差上界

关于Hoeffding不等式及泛化误差上界

偏差方差分解

偏置方差分解Bias-variance Decomposition

机器学习中的方差和偏差

【训练误差与测试误差】

对于任何一个模型来说，具体采用的损失函数，未必是评估模型时所用的损失函数

当损失函数给定时，基于损失函数的训练误差（Training Error）和测试误差（Test Error）就成为了评估标准

所谓误差，是指学习器的实际预测输出与样本的真实输出间的差值，训练误差常用于判定给定的问题是否为一个容易学习的问题，测试误差则反映了学习方法对未知的测试集的预测能力

假设学习到的模型是 $Y=f(X;\boldsymbol{\theta})$，训练误差是与模型相关的含有 $N$ 个样本的训练集的平均损失，即：

$R_{emp}(f)=\frac{1}{N}\sum_{i=1}^N L(\mathbf{y_i},f(\mathbf{x_i};\boldsymbol{\theta}))$

测试误差是与模型相关的含有 $N’$ 个样本的测试集的平均损失，即：

$e_{test}=\frac{1}{N'}\sum_{i=1}^{N'} L(\mathbf{y_i},f(\mathbf{x_i};\boldsymbol{\theta}))$

由于模型是针对一个问题设计的，这个问题会有一个数据总体，包含了所有可能的情况，模型都是先在训练集上进行训练，再在测试集上进行测试，但总体数据量往往很大，不可能用到所有的数据，一般都是在总体中进行抽样

也就是说，模型在训练数据上进行训练，得到的误差为训练误差；在测试数据上进行测试，得到的误差即测试误差

【泛化能力】

学习方法的泛化能力（Generalization Ability）是指由该学习方法学习到的模型对未知数据的预测能力

泛化误差

我们真正想要的是模型在总体上的误差，即模型在未知记录上的期望误差，也即泛化误差

在实际应用中，如果在样本集划分时，得到的训练集与测试集数据没有交集，可以将测试误差近似等同于泛化误差

具体来说，泛化误差是学习到的模型的期望风险，其反映了理论上的学习方法的泛化能力

假设学习到的模型为 $Y=f(X;\boldsymbol{\theta})$，用这个模型对未知数据预测的泛化误差为：

$R_{exp}(f)=E_P\big[L(Y,f(X;\boldsymbol{\theta})\big]=\int_{\mathcal{X}\times\mathcal{Y}}L(Y,f(X;\boldsymbol{\theta}))P(X,Y)dXdY$

简单来说，训练误差即经验风险 $R_{emp}(f)$，测试误差可近似等同于泛化误差，泛化误差即期望风险 $R_{exp}(f)$

泛化误差上界

由于实际应用中使用的测试误差与泛化误差之间存在一定的误差，因此对于学习方法的泛化能力分析是通过研究泛化误差的概率上界进行的，即泛化误差上界（Generalization Error Bound），两种学习方法的优劣，通常通过他们的泛化误差上界来进行比较

泛化误差上界具有以下性质：

样本容量的函数：当样本容量增加时，泛化误差上界趋于 $0$
假设空间容量的函数：容量越大模型越难以学习，泛化误差上界就越大

二分类问题的泛化误差上界

以简单的二分类问题为例，已知训练数据集 $T=\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),…,(\mathbf{x_N},y_N)\}$ 是由联合分布概率 $P(X,Y)$ 独立同分布产生的，且 $X\in \mathbb{R}^n$，$Y\in\{-1,+1\}$，假设空间为 $d$ 个函数 $f$ 的有限集合 $\mathcal{F}=\{f_1,f_2,…,f_d\}$，采用的损失函数为 0-1 损失函数，其取值为 $\{0,1\}$

关于 $f$ 的训练误差，即经验风险 $R_{emp}(f)$ 为：

$R_{emp}(f) = \frac{1}{N} \sum\limits_{i=1}^N L(y_i,f(\mathbf{x_i};\boldsymbol{\theta}))$

关于 $f$ 的泛化误差，即期望风险 $R_{exp}(f)$ 为：

$R_{exp}(f)=E\big[L(Y,f(X;\boldsymbol{\theta}))\big]$

那么，对任意 $f\in\mathcal{F}$，至少以 $1-\delta$ 的概率，使得下式成立：

$R_{exp}(f)\leq R_{emp}(f)+\varepsilon(d,N,\delta)$

不等式右端的 $R_{emp}(f)+\varepsilon(d,N,\delta)$ 即为泛化误差上界

其中，$\varepsilon(d,N,\delta)$ 为样本数量 $N$ 的单调递减函数，即：

$\varepsilon(d,N,\delta)=\sqrt{\frac{1}{2N}(log\:d+log\:\frac{1}{\delta})}$

当 $N$ 趋于无穷时其趋于 $0$，同时也是 $\sqrt{log\:d}$ 阶的函数，假设空间 $\mathcal{F}$ 包含的函数越多，其值越大

假设找到了经验风险最小化的函数：

$f_N=arg\:\min_{f\in\mathcal{F}}R_{emp}(f)$

那么根据上述不等式，只要加上 $\varepsilon(d,N,\delta)$ 项，即可控制住测试集上的期望风险 $R_{exp}(f)$

换句话来说，随着样本数量 $N$ 的增大，训练误差和泛化误差会越来越接近

关于该部分的详细证明见：证明1

【偏差-方差分解】

偏差、方差、噪声

泛化误差可分解为偏差、方差与噪声，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的

偏差（bias）：独立于训练样本的误差，度量了模型的期望预测与真实结果的偏差程度，刻画了模型本身的拟合能力，偏差越高，拟合能力越差
方差（variance）：度量了面对同样规模的训练集，在训练样本变动时导致的模型学习性能的变化，是关于观测样本的误差，刻画了数据扰动对学习算法的影响，方差越大，越不稳定
噪声（noise）：当前任务上任何模型能达到的期望泛化误差下界，是任何方法都无法克服的误差，刻画了学习问题本身的难度

以最简单的一元线性回归问题为例

对于在训练数据集 $T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$ 上习得的模型 $f_T$，当给定测试样本 $(x,y)$ 时，$x$ 为测试样本的输入，$y$ 为测试样本的输出，记 $\hat{y}$ 为实际测试时得到的输出，$f_T(x;\theta)$ 为对测试样本的输入 $x$ 的预测输出

采用平方损失函数：

$L(Y,f(X;\theta))=(Y-f(X;\theta))^2$

则学习算法的泛化误差为：

$\begin{align} R_{exp}(f) &= E_P\big[ L(Y,f(X;\theta)) \big] \notag \\ &= E_P\big[(y-\hat{y})^2\big] \notag \\ &= E_P\big[(y-f_T(x;\theta))^2\big] \notag \end{align}$

针对与数据集 $T$ 具有相同样本数的不同数据集所训练的模型 $f$ 对测试样本 $x$ 的预测值的期望，即平均预测值（average predicted）为：

$\overline{f}_T(x;\theta)=E_P\big[f_T(x;\theta)\big]$

依据离散型方差计算公式：

$D(X)=E\big[(X-E(X))^2\big]$

此时，使用样本数相同的不同训练集产生的方差（variance）为：

$D(x)=E_P\big[(f(x;\theta)-\overline{f}(x;\theta))^2\big]$

由于样本可能出现标记错误等情况，此时模型 $f_T$ 预测到的数据 $\hat{y}$ 可能与数据集中的样本输出 $y$ 不相符，两者间的差异即噪声（noise），即：

$\varepsilon^2=E_P\big[(\hat{y}-y)^2\big]$

而对于期望预测 $\overline{f}(x;\theta)$ 与预测输出 $y$ 的误差，称之为偏差（bias），为方便起见，直接取偏差的平方，即：

$bias^2(x)=(\overline{f}(x;\theta)-\hat{y})^2$

偏差-方差分解

偏差-方差分解（Bias-Variance Decomposition）是机器学习用于解释学习算法的泛化能力的分析技术，对于给定学习目标和训练集，其可以将一种学习算法的泛化误差分解为噪声（noise）、偏差（bias）和方差（variance）

为便于讨论，假定噪声期望为 $0$，即：$E_P(y-\hat{y})=0$

接上例，对学习算法的泛化误差 $R_{exp}(f)$ 进行分解：

$\begin{align} R_{exp}(f) &= E_P \big[ (y-f_T(x;\theta))^2 \big] \notag \\ &= bias^2(x) + \varepsilon^2 + D(x) \notag \end{align}$

关于该部分的详细证明见：证明2

偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性、学习任务本身的难度所共同决定的

偏差-方差窘境

对于给定的学习任务，若为了得到泛化性能好的模型，需要使偏差较小，以充分拟合数据，同时要使方差较小，使得数据扰动产生的影响小，但偏差与方差在一定程度上是有冲突的，即偏差-方差窘境（bias-variance dilemma）

如下图，在模型训练不足时，拟合能力不够强，训练数据的扰动不足以使得学习器产生显著的变化，此时偏差主导泛化误差，即欠拟合现象；当随着训练程度加深，模型的拟合能力增强，训练数据的扰动慢慢使得方差主导泛化误差；当训练充足时，模型的拟合能力非常强，数据轻微变化都能导致模型发生变化，如果过分学习训练数据的特点，则会发生过拟合现象

随着模型复杂度的提升，偏差逐渐减小，方差逐渐增大，最佳的模型复杂度是在泛化误差 $R_{exp}(f)$ 最小的时候，此时该点导数为 $0$

由于 $R_{exp}(f)= bias^2(x)+\varepsilon^2+D(x)$，因此，在拐点处有：

$\frac{d\:bias}{d\:complexity}=\frac{d\:D}{d\:complexity}$

其中，$complexity$ 代表模型复杂度

若模型复杂度大于平衡点，则模型的方差会偏高，模型倾向于过拟合；若模型复杂度小于平衡点，则模型的偏差会偏高，模型倾向于欠拟合

【附：证明】

证明1

霍夫丁不等式（Hoeffding’s inequality）给出了随机变量的均值与期望值的偏差的概率上限：

设 $\overline{X}=\frac{1}{N}\sum\limits_{i=1}^nX_i$ 是独立随机变量 $X_1,X_2,…,X_n$ 的经验均值，$X_i\in[a_i,b_i]$，则对任意的 $t>0$，以下两不等式成立：
$\left\{\begin{array}{rl} P(\overline{X}-E({\overline{X}}) \geq t) & \leq & exp \biggl(\frac{-2N^2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2} \biggr ) \\P(E(\overline{X})-{\overline{X}} \geq t) & \leq & exp \biggl(\frac{-2N^2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2} \biggr ) \end{array} \right.$

已知训练数据集 $T=\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),…,(\mathbf{x_N},y_N)\}$ 是由联合分布概率 $P(X,Y)$ 独立同分布产生的，且 $X\in \mathbb{R}^n$，$Y\in\{-1,+1\}$，假设空间为 $d$ 个函数 $f$ 的有限集合 $\mathcal{F}=\{f_1,f_2,…,f_d\}$，采用的损失函数 $L(y_i,f(\mathbf{x_i};\boldsymbol{\theta}))$ 为 0-1 损失函数，其取值为 $\{0,1\}$

损失函数的均值为：

$\overline{X} = \frac{1}{N} \sum\limits_{i=1}^N L(y_i,f(\mathbf{x_i};\boldsymbol{\theta}))$

损失函数的期望为：

$\begin{align} E(\overline{X}) &= E\bigg[\frac{1}{N} \sum\limits_{i=1}^N L(y_i,f(\mathbf{x_i};\boldsymbol{\theta}))\bigg] \notag \\ &= \frac{1}{N} \sum\limits_{i=1}^N E\bigg[L(y_i,f(\mathbf{x_i};\boldsymbol{\theta}))\bigg] \notag \\ &= E\big[L(Y,f(X;\boldsymbol{\theta}))\big]\notag \end{align}$

易知：

$\left\{\begin{array}{rl} \overline{X} &=& R_{emp}(f) \\ E(\overline{X}) &=& R_{exp}(f) \end{array} \right.$

根据霍夫丁不等式：

$P(E({\overline{X}})-\overline{X} \geq t) \leq \exp \bigl(\frac{-2N^2t^2}{\sum\limits_{i=1}^N(b_i-a_i)^2} \bigr )$

将 $\overline{X}=R_{emp}(f)$，$E(\overline{X})=R_{exp}(f)$ 代入，并取 $t=\varepsilon >0$

同时，由于是二分类问题，故有 $a_i,b_i\in\{0,1\}$，也就是说，对于 $a_i$ 与 $b_i$，当其中一个取值为 $1$ 时，另一个取值一定为 $0$

故有：

$P(R_{exp}(f)-R_{emp}(f) \geq \varepsilon) \leq \exp(\frac{-2N^2\varepsilon^2}{\sum\limits_{i=1}^N 1}),\quad \varepsilon>0$

也就是说，对于假设空间 $\mathcal{F}$，其中的任意一个函数 $f$ 作为模型时，其泛化误差的概率上限满足以下的不等式：

$P(R_{exp}(f)-R_{emp}(f) \geq \varepsilon) \leq exp(-2N\varepsilon^2),\quad \varepsilon>0$

而假设空间 $\mathcal{F}$ 是一个有限集合，如果要求 $\mathcal{F}$ 中存在某个函数 $f$ 作为模型时，根据概率的加和规则，其泛化误差的概率上限满足以下不等式：

$\begin{align} P(\exists f \in \mathcal{F}: R_{exp}(f)-R_{emp}(f)\geq \varepsilon) & = P(\cup_{f\in\mathcal{F}}\{R_{exp}(f)-R_{emp}(f)\geq \varepsilon \}) \notag \\ & \leq \sum_{f\in\mathcal{F}}P(R_{exp}(f)-R_{emp}(f) \geq \varepsilon) \notag \\ & \leq d\cdot exp(-2N\varepsilon^2) \notag \end{align}$

其中，$d$ 为假设空间 $\mathcal{F}$ 中函数 $f$ 的个数

相应地，对任意 $f\in \mathcal{F}$，有：

$P(R_{exp}(f)-R_{emp}(f)<\varepsilon)\geq 1-d\cdot exp(-2N\varepsilon^2)$

取 $\delta = d \cdot exp(-2N\varepsilon^2)$，进行变量替换，有：

$P(R_{exp}(f)<R_{emp}(f)+\varepsilon)\geq 1-\delta$

即至少以 $1-\delta$ 的概率，使得 $R_{exp}(f)<R_{emp}(f)+\varepsilon$ 成立

其中，$\varepsilon$ 是由 $\delta = d \cdot exp(-2N\varepsilon^2)$ 得到，即：

$\varepsilon(d,N,\delta)=\sqrt{\frac{1}{2N}(log\:d+log\:\frac{1}{\delta})}$

点击返回

证明2

对一元线性回归问题的学习算法的泛化误差 $R_{exp}(f)=E_P \big[ (y-f_T(x;\theta))^2 \big]$ 进行拆项，有：

$E_P \big[ (y-f_T(x;\theta))^2 \big] = E_P \Big[ \big[ (y - \overline{f}(x;\theta)) + (\overline{f}(x;\theta) - f(x;\theta)) \big]^2 \Big]$

根据期望公式：

$E\big[(X-Y)^2\big] = E(X^2)-2E(XY)+E(Y^2)$

易得：

$\begin{align} R_{exp}(f) &= E_P \Big[ \big( y - \overline{f}(x;\theta) \big)^2 \Big] \notag \\ &\quad + 2E_p \big[ (y - \overline{f}(x;\theta)) \cdot (\overline{f}(x;\theta) - f(x;\theta)) \big] \notag \notag \\ &\quad+ E_P \Big[ \big( \overline{f}(x;\theta) - f(x;\theta) \big)^2 \Big] \notag \\ \end{align}$

由于方差为：

$D(x)=E_P\big[(f(x;\theta)-\overline{f}(x;\theta))^2\big]$

故有：

对于第二项，有：

$\begin{align} &E_P\bigl[ (y-\overline{f}(x;\theta)) \cdot (\overline{f}(x;\theta)-f(x;\theta)) \bigr] \notag \\ &= E_P\bigl[ y\cdot\overline{f}(x;\theta) - y\cdot f(x;\theta) - \overline{f}(x;\theta)\overline{f}(x;\theta) + \overline{f}(x;\theta)f(x;\theta) \bigr] \notag \\ &= E_P\bigl[ y\cdot(\overline{f}(x;\theta)-f(x;\theta)) \bigr] - E_P\bigl[ \overline{f}(x;\theta)(\overline{f}(x;\theta)-f(x;\theta)) \bigr] \notag \end{align}$

而对于上式中的前半部分，有：

$\begin{align} & E_P\big[ y\cdot(\overline{f}(x;\theta) - f(x;\theta)) \big] \notag \\ &= \iint y\cdot(\overline{f}(x;\theta) - f(x;\theta))\cdot p(x,y)dxdy \notag \\ &= \iint (\overline{f}(x;\theta)-f(x;\theta)) \cdot y\cdot p(y|x)\cdot p(x)dxdy \notag \\ &= \int (\overline{f}(x;\theta)-f(x;\theta)) \cdot E_P(y|x) \cdot p(x)dx \notag \\ &= E_P \big[ E_P(y|x) \cdot (\overline{f}(x;\theta)-f(x;\theta)) \big] \notag \\ &= E_P \big[ \overline{f}(x;\theta)\cdot(\overline{f}(x;\theta)-f(x;\theta)) \big] \notag \end{align}$

显然与式子中的后半部分相同，两者相减为 $0$，故有：

$R_{exp}(f) = E_P \Big[ \big( y - \overline{f}(x;\theta) \big)^2 \Big] + D(x)$

对于 $E_P \Big[ \big( y - \overline{f}(x;\theta) \big)^2 \Big]$，同样进行拆项，有：

$E_P \Big[ \big( y - \overline{f}(x;\theta) \big)^2 \Big] = E_P \Big[ \big[ (y - \hat{y}) + (\hat{y} - \overline{f}(x;\theta)) \big]^2 \Big]$

同样利用期望公式，有：

$\begin{align} R_{exp}(f) &= E_P \big[ ( y - \hat{y} )^2 \big] \notag \\ &\quad + 2E_P(y - \hat{y}) \cdot E_P \big[ \hat{y} - \overline{f}(x;\theta) \big] \notag \\ &\quad+ E_P \Big[ \big( \hat{y} - \overline{f}(x;\theta) \big)^2 \Big] \notag \\ &\quad+ D(x) \notag \end{align}$

由于噪声的期望为 $0$，即 $E_P(y-\hat{y})=0$，故有：

$R_{exp}(f) = E_P \big[ ( y - \hat{y} )^2 \big] + E_P \Big[ \big( \hat{y} - \overline{f}(x;\theta) \big)^2 \Big] + D(x)$

又因为噪声为：