经验风险最小化
机器学习 斯坦福
符号及定义
训练集：S={(x(i),y(i));i=1,…,m}
训练误差：ε^S(h)=1m∑I{h(x(i))≠y(i)}
ERM：h^=argh∈Hminε^(h)
一般误差：ε(h)=P(h(x)≠y)
定理
定理：令|H|=k，对于任意m,δ，至少在1−δ的概率下有：
ε(h^)≤(minh∈Hε(h))+212mln2kδ−−−−−−−−√
我们可以非正式地认为右式的第一项对应假设类的偏差，第二项对应方差。
证明：
ε(h^)≤ε^(h^)+δ≤ε^(h∗)+δ≤ε(h∗)+2δ
推论：令|H|=k，对于任意δ,γ，则为了保证ε(h^)≤minh∈Hε(h)+2γ至少在1−δ的概率下成立，必须有：
m≥12γ2ln2kδ=O(1γ2lnkδ)
结论
此处偏差与方差权衡指的是选择合适大小的假设类，即：假设类过小导致偏差过大，即欠拟合；假设类过大导致方差过大，即过拟合。
逻辑回归和支持向量机是经验风险最小化这个非凸优化问题的凸性近似，它们实际上也是如经验风险最小化一样的工作。
思考
- ε^是在训练集上的偏差。
- ε是一般偏差。
- h^是我们能得到的。
- h∗是理想的，我们无法确定得到的。
- ε(h^)是我们真正关心的，关心它与ε(h∗)的近似程度。
实际上无论任何学习算法，我们衡量其好坏的依据都只是其在未知数据上的表现，而不是它对训练集拟合的好坏。
极大似然估计与经验风险最小有何区别？
训练误差也被称为经验风险。
定理的证明策略：step1)ε^≈ε，step2)ε(h^)存在上界
我们说，逻辑回归是经验风险最小化的凸近似，那么，近似体现在哪里？
《逻辑回归关于经验风险最小化的凸近似体现》
引理
引理（Hoeffding不等式）：若：zi∼Bernoulli(ϕ)，令：ϕ^=1m∑zi则：P(|ϕ^−ϕ|>δ)≤2exp(−2δm)。
值得注意的是该不等式对任意的m均成立。
证明
定理：p(|ε(h)−ε^(h)|>δ)≤2exp(−2δ2m)
证明：令：zi=I{h(x(i))≠y(i)}，则：P(zi=1)=ε(h)，由Hoeffding不等式即可得待证明不等式。
定理（依概率一致收敛）：P(∀h∈H.|ε(h)−ε^(h)|≤δ)≥1−2kexp(−2δ2m)
证明：令事件Aj为|ε(hj)−ε^(hj)|>δ。则
P(Aj)≤2exp(−2δ2m)
P(∃h∈H.|ε(h)−ε^(h)|>δ)=P(∪Aj)≤∑P(Aj)≤∑2exp(−2δ2m)=2kexp(−2δ2m)
同时用1减两边得：
=≥P(∄h∈H.|ε(h)−ε^(h)|>δ)P(∀h∈H.|ε(h)−ε^(h)|≤δ)1−2kexp(−2δ2m)
推论：令：γ=2kexp(−2δ2m)，则：
样本复杂度：
m≥12δ2ln2kγ
误差界：
δ=12mln2kγ−−−−−−−−√
ERM——empirical risk minimization——经验风险最小化
