经验风险最小化

机器学习 斯坦福

---

符号及定义

训练集：$S=\lbrace (x^{(i)},y^{(i)});i=1,\dots,m\rbrace$
训练误差：$\hat\varepsilon_S(h)=\frac1m\sum I\lbrace h(x^{(i)})\ne y^{(i)}\rbrace$
ERM：$\hat h=\underset{h\in H}\arg\min\hat\varepsilon(h)$
一般误差：$\varepsilon(h)=P(h(x)\ne y)$

定理

定理：令$|H|=k$，对于任意$m,\delta$，至少在$1-\delta$的概率下有：

$$\varepsilon(\hat h)\le \left(\underset{h\in H}\min\varepsilon(h)\right)+2\sqrt{\frac{1}{2m}\ln\frac{2k}{\delta}}$$ 我们可以非正式地认为右式的第一项对应假设类的偏差，第二项对应方差。
证明：
$$\begin{array}\\ \varepsilon(\hat h) & \le\hat\varepsilon(\hat h)+\delta\\ & \le\hat\varepsilon(h^*)+\delta\\ & \le\varepsilon(h^*)+2\delta \end{array}$$

推论：令$|H|=k$，对于任意$\delta,\gamma$，则为了保证$\varepsilon(\hat h)\le \underset{h\in H}\min\varepsilon(h)+2\gamma$至少在$1-\delta$的概率下成立，必须有：

$$\begin{array}\\ m &\ge\frac{1}{2\gamma^2}\ln\frac{2k}{\delta}\\ &=O\left(\frac{1}{\gamma^2}\ln\frac{k}{\delta}\right)\end{array}$$

结论

此处偏差与方差权衡指的是选择合适大小的假设类，即：假设类过小导致偏差过大，即欠拟合；假设类过大导致方差过大，即过拟合。

逻辑回归和支持向量机是经验风险最小化这个非凸优化问题的凸性近似，它们实际上也是如经验风险最小化一样的工作。

思考

1. $\hat\varepsilon$是在训练集上的偏差。
2. $\varepsilon$是一般偏差。
3. $\hat h$是我们能得到的。
4. $h^*$是理想的，我们无法确定得到的。
5. $\varepsilon(\hat h)$是我们真正关心的，关心它与$\varepsilon(h^*)$的近似程度。

实际上无论任何学习算法，我们衡量其好坏的依据都只是其在未知数据上的表现，而不是它对训练集拟合的好坏。

极大似然估计与经验风险最小有何区别？

训练误差也被称为经验风险。

定理的证明策略：step1)$\hat\varepsilon\approx\varepsilon$，step2)$\varepsilon(\hat h)$存在上界

我们说，逻辑回归是经验风险最小化的凸近似，那么，近似体现在哪里？
《逻辑回归关于经验风险最小化的凸近似体现》

引理

引理（Hoeffding不等式）：若：$z_i\sim Bernoulli(\phi)$，令：$\hat\phi=\frac 1m\sum z_i$则：$P(|\hat\phi-\phi|>\delta)\le 2\exp(-2\delta m)$。
值得注意的是该不等式对任意的$m$均成立。

证明

定理：$p(|\varepsilon(h)-\hat\varepsilon(h)|>\delta)\le2\exp(-2\delta^2 m)$
证明：令：$z_i=I\lbrace h(x^{(i)})\ne y^{(i)}\rbrace$，则：$P(z_i=1)=\varepsilon(h)$，由Hoeffding不等式即可得待证明不等式。

定理（依概率一致收敛）：$P(\forall h\in H.|\varepsilon(h)-\hat\varepsilon(h)|\le \delta)\ge 1-2k\exp(-2\delta^2 m)$
证明：令事件$A_j$为$|\varepsilon(h_j)-\hat\varepsilon(h_j)|>\delta$。则
$P(A_j)\le 2\exp(-2\delta^2m)$

$$P(\exists h\in H.|\varepsilon(h)-\hat\varepsilon(h)|>\delta)\\ =P(\cup A_j)\le\sum P(A_j)\\ \le\sum 2\exp(-2\delta^2m)=2k\exp(-2\delta^2m)$$ 同时用1减两边得：
$$\begin{array}\\ & P(\not\exists h\in H.|\varepsilon(h)-\hat\varepsilon(h)|>\delta)\\ =& P(\forall h\in H.|\varepsilon(h)-\hat\varepsilon(h)|\le\delta)\\ \ge& 1-2k\exp(-2\delta^2m) \end{array}$$

推论：令：$\gamma=2k\exp(-2\delta^2m)$，则：
样本复杂度：

$$m\ge \frac{1}{2\delta^2}\ln\frac{2k}{\gamma}$$ 误差界：
$$\delta=\sqrt{\frac{1}{2m}\ln\frac{2k}{\gamma}}$$
ERM——empirical risk minimization——经验风险最小化