【课堂笔记】定理：样本越多，测量的经验损失越接近真实损失

定理描述

  给定一个模型$f:X\to Y$，设数据分布$\mathcal{D}$定义在$X\times Y$，表示数据真实分布，且假设训练集和测试集的样本均从$\mathcal{D}$中独立同分布(i.i.d)抽取。
  设损失函数为$l:Y\times Y\to \mathbb{R}$，假设$l$是有界的，$\forall y,\hat{y}，a\le l(y,\hat{y})\le b$
  模型的期望风险定义为：$L_{\mathcal{D}}(f)={\mathbb{E}}_{(x,y)\sim \mathcal{D}}[l(f(x),y)]$，是模型泛化能力的理论指标
  模型的经验分险定义为：$L_{S_{test}}=\frac{1}{|S_{test}|}\sum _{(x,y)\in S_{test}}l(f(x),y)$，是模型在测试集上平均损失，用于估计$L_{\mathcal{D}}(f)$
  给定置信参数$\delta \in (0,1)$
  有以下不等式成立：

$\mathrm{Pr}\left[\left|L_{\mathcal{D}}(f)-L_{S_{\text{test}}}(f)\right|\ge \sqrt{\frac{(b-a{)}^2\ln (2/\delta )}{2|S_{\text{test}}|}}\right]\le \delta$

含义

  定理提供了一个概率上界，保证模型$f$的真实风险$L_{\mathcal{D}}(f)$和测试集经验风险$L_{S_{test}}(f)$之间的差不超过某个阈值的概率至少为$1-\delta$
  界限随着测试集大小$|S_{test}|$的增加而减小（分母变大），表明更多测试数据能更准确地估计真实风险。
  界限随着损失函数范围$b-a$的增加而增大，反映了损失变异性对泛化误差的影响。
  界限随着置信参数$\delta$的减小而增大（因为$ln(2/\delta )$增大），反映了更高置信度需要更宽松的界。

证明

  令$Z_i=l(f(x_i),y_i)$，其中$(x_i,y_i)\in S_{test}$，$i=1,2,...,m,m=|S_{test}|$
  由于$(x_i,y_i)\sim \mathcal{D}$，$Z_i$是独立同分布的随机变量，且由假设，$Z_i\in [a,b]$。于是：

$\mathbb{E}[Z_i]={\mathbb{E}}_{(x,y)\sim \mathcal{D}}[l(f(x),y)]=L_{\mathcal{D}}(f)$

  经验分险为：

$L_{S_{test}}(f)=\frac{1}{m}\underset{i=1}{\sum ^m}{Z}_i$

  引入霍夫丁不等式，它表面对于$m$个独立随机变量$Z_1,...,Z_m$，每个$Z_i\in [a,b]$，有：

$\mathrm{Pr}\left[\left|\frac{1}{m}{\sum }_{i=1}^m{Z}_i-\mathbb{E}[Z_i]\right|\ge ϵ\right]\le 2\exp \left(-\frac{2m{ϵ}^2}{(b-a{)}^2}\right)$

  代入后则有：

$\mathrm{Pr}\left[\left|L_{S_{\text{test}}}(f)-L_{\mathcal{D}}(f)\right|\ge ϵ\right]\le 2\exp \left(-\frac{2m{ϵ}^2}{(b-a{)}^2}\right)$

  确定一个特定的$ϵ$，令：

$2exp(-\frac{2m{ϵ}^2}{(b-a{)}^2})=\frac{\delta }{2}$
$ϵ=\sqrt{\frac{(b-a{)}^{2}ln(2/\delta )}{2m}}=\sqrt{\frac{(b-a{)}^{2}ln(2/\delta )}{2|S_{test}|}}$

  最终得到：

$\mathrm{Pr}\left[\left|L_{\mathcal{D}}(f)-L_{S_{\text{test}}}(f)\right|\ge \sqrt{\frac{(b-a{)}^2\ln (2/\delta )}{2|S_{\text{test}}|}}\right]\le \delta$