泛化误差上界证明&《统计学习方法》第一章课后题

泛化误差

整体思路

• 基本假设：

数据集的样本容量$N$，损失函数的值域范围，假设空间的样本容量大小$d$。

• 列出对于一个假设空间中的$f$的经验风险和期望风险。
• 利用Hoeffding不等式将对于$f$的期望风险与经验风险的差值大于$\epsilon$的概率列出。
• 写出对于假设空间$\cal{F}$中任何函数的期望风险与经验风险差值小于$\epsilon$的概率：

1. 通过有限假设空间的Hypothesis，写出“假设空间里 至少存在一个函数$f$ 的期望风险与经验风险差值 大于等于$\epsilon$”的概率。
2. 上述命题的否定即为“假设空间里 任意一个函数$f$ 的期望风险与经验风险差值 都 小于$\epsilon$”。该事件的概率即为1-上述事件的概率。

• 而对于假设空间中的 任何一个函数$f$ “其期望风险与经验风险差值小于$\epsilon$”事件的概率肯定大于“假设空间里 任意一个函数$f$ 的期望风险与经验风险差值 都 小于$\epsilon$”事件的概率。
• 变量代换和拆开概率表达的形式。

霍夫丁不等式（Hoeffding）

设$X_1,X_2,\cdots,X_N$是独立随机变量，且$X_i\in[a_i,b_i],i=1,2,\cdots,N;\bar{X}$是$X_1,X_2,\cdots,X_N$的经验均值，即$\bar{X}=\frac1N\sum_{i=1}^NX_i$,则对任意$t>0$,以下不等式成立：

$$P[\bar{X}-E(\bar{X})\geqslant t]\leqslant\exp\left(-\frac{2N^2\boldsymbol{t}^2}{\sum_{i=1}^N(b_i-a_i)^2}\right)$$

或者反过来：

$$P[E(\bar{X})-\bar{X}\geqslant t]\leqslant\exp\left(-\frac{2N^2t^2}{\sum_{i=1}^N{(b_i-a_i)^2}}\right)$$

也就是，样本均值与样本均值的期望相差大于$t$的概率上界与$N$和$t$成反比（$N$和$t$越大，上述两项的差值越大概率能在$t$的范围内，分散性弱），与$b_i-a_i$成正比（随机变量的范围越大，上述两项的差值越小概率能在$t$的范围内，分散性强）

基本假设

考虑二类分类问题。已知训练数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,是样本容量，$T$是从联合概率分布$P(X,Y)$独立同分布产生的，$X\in\mathbf{R}^n,Y\in\{-1,+1\}$。假设空间是函数的有限集合$\mathcal{F}=\{f_1,f_2,\cdots,f_d\},d$是函数个数。设$f$是从$\mathcal{F}$中选取的函数。损失函数是 0-1 损失。关于$f$的期望风险和经验风险分别是：

$$R(f)=E[L(Y,f(X))]\\\hat{R}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_{i},f(x_{i}))$$

对于$f$的期望风险与经验风险的差值大于$\epsilon$的概率

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

事件：“假设空间里 至少存在一个函数$f$ 的期望风险与经验风险差值 大于等于$\epsilon$”的概率

$$\begin{aligned} P(\exists f\in\mathcal{F}:R(f)-\hat{R}(f)\geqslant\varepsilon)& =P\Big(\bigcup_{f\in\mathcal{F}}\{R(f)-\hat{R}(f)\geqslant\varepsilon\}\Big) \\ &\leqslant\sum_{f\in\mathcal{F}}P(R(f)-\hat{R}(f)\geqslant\varepsilon) \\ &\leqslant d\exp(-2N\varepsilon^2) \end{aligned}$$

第一个不等式：Venn图，连并小于概率之和。第二个不等式：d次霍夫丁不等式

对于任何$f \in \cal{F}$，事件：“其期望风险与经验风险差值小于$\epsilon$”的概率

$$P(R(f)-\hat{R}(f)<\varepsilon)\geqslant P\Big(\bigcap_{f\in\mathcal{F}}\{R(f)-\hat{R}(f) < \varepsilon\}\Big) \geqslant 1-d\exp(-2N\varepsilon^2)$$

第一个不等式：多个事件同时发生的概率小于其中一个事件发生的概率

变量代换与最终结果

$$\begin{aligned}\delta&=d\exp(-2N\varepsilon^2)\\\\\\P(R(f)&<\hat{R}(f)+\varepsilon)\geqslant1-\delta\end{aligned}$$

并且，由第一个等式可以得到：

$$\varepsilon(d,N,\delta)=\sqrt{\frac1{2N}\left(\log d+\log\frac1\delta\right)}$$

由第二个式子得到：

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

即最终的泛化误差上界：

在满足开始所提及的假设时，至少有$1-\delta$的概率以下不等式成立，$\delta \in [0,1]$，$\varepsilon$定义如上。不等式左侧即为泛化误差上界。

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

《统计学习方法》第一章课后题

$\mathbf{1. 1}$ 说明伯努利模型的极大似然估计以及贝叶斯估计中的统计学习方法三要素。伯努利模型是定义在取值为0与 1 的随机变量上的概率分布。假设观测到伯努利模型$n$次独立的数据生成结果，其中$k$次的结果为 1,这时可以用极大似然估计或贝叶斯估计来估计结果为 1 的概率。

$\mathbf{1. 2}$ 通过经验风险最小化推导极大似然估计。证明模型是条件概率分布，当损失函数是对数损失函数时，经验风险最小化等价于极大似然估计。