Preface

从一篇博客开始的学习理论部分主要是介绍面对实际问题时我们应该选择什么模型，以及当我们使用的模型不能达到预期成果时应该怎么办。
主要内容：
Bias/Variance Trade-off（偏差/方差权衡）
Empirical Risk Minimization (ERM，经验风险最小化)
The case of finite H（H集合有限的情况）
The case of infinite H（H集合无限的情况）

Bias/Variance Trade-off

在上述三图中，第一幅图表示的是欠拟合状态，第二幅图表示的是较好的拟合状态，第三幅图表示的是过拟合状态。
第三幅图使用线性回归 y=θ0+θ1x+θ2x+θ3x+θ4x+θ5x$y={\theta }_0+{\theta }_{1}x+{\theta }_{2}x+{\theta }_{3}x+{\theta }_{4}x+{\theta }_{5}x$ 建立的模型，在训练集中可以准确的预测 y$y$ 。但是，无法使用线性回归 y=θ0+θ1x+θ2x+θ3x+θ4x+θ5x$y={\theta }_0+{\theta }_{1}x+{\theta }_{2}x+{\theta }_{3}x+{\theta }_{4}x+{\theta }_{5}x$ 来准确预测训练集之外的数据。换句话说，这个模型没有很好的泛化能力。因此，模型的泛化误差(generalization error)不仅包括其在样本上的期望误差，还包括在训练集上的误差。

通常，在偏倚和方差之间，这样一种规律：如果模型过于简单，其具有大的偏倚，而如果模型过于复杂，它就有大的方差。调整模型的复杂度，建立适当的误差模型，就变得极其重要了。

Empirical Risk Minimization

Step1：两个定理

首先我们介绍两个定理：

定理一：一致限(The union bound)：假设 A1,A2...Ak$A_1,A_2...A_k$ 是 k$k$ 个不同的事件，那么 P(A1∪A2∪...∪Ak)≤P(A1)+P(A2)+...+P(Ak)$P(A_1\cup A_2\cup ...\cup A_k)\le P(A_1)+P(A_2)+...+P(A_k)$ 。你可以画一个文氏图去理解他。

定理二：Hoeffding 不等式(Hoeffding inequality)：假设 Z1,Z2...Zm$Z_1,Z_2...Z_m$是 m$m$ 个独立同分布（IID）服从伯努利分布的变量，参数为 ϕ$\varphi$。即 ϕ^=(1/m)∑mi=1Zi$\hat{\varphi }=(1/m)\sum _{i=1}^m{Z}_i$ ，ϕ^$\hat{\varphi }$ 也是随机变量，对于任意的 γ>0$\gamma >0$ ，则有 P(|ϕ−ϕ^|>γ)≤2exp(−2γ2m)$P(|\varphi -\hat{\varphi }|>\gamma )\le 2exp(-2{\gamma }^{2}m)$ 。

Step2：假设条件

这里我们讨论线性回归中二分类问题 hθ(x)=g(θTx),g=1{z≥0},y={0,1}$h_{\theta }(x)=g({\theta }^{T}x),g=1\{z\ge 0\},y=\{0,1\}$ ，同时对于样本集 S={(x(i),y(i))}mi=1$S=\{(x^{(i)},y^{(i)}){\}}_{i=1}^m$ 中的任意样本 {(x(i),y(i))}$\{(x^{(i)},y^{(i)})\}$ 满足IID（独立同分布）。
注：g=1{z≥0}$g=1\{z\ge 0\}$ 为指示器函数，当 z≥0$z\ge 0$ 时，g=1$g=1$ ；当 z<0$z<0$ 时，g=0$g=0$ 。

Step3：Training Error（训练误差）

对于一个假设函数 hθ(x)=g(θTx)$h_{\theta }(x)=g({\theta }^{T}x)$ ，定义训练误差（training error）（也称为经验风险（empirical risk）或经验误差(empiriacal error)）为：

ε^(hθ)=ε(hθ)S=1m∑i=1n1{h(x(i))≠y(i)}(1)$\begin{array}{}\text{(1)}& \hat{\epsilon }(h_{\theta })=\epsilon (h_{\theta }{)}_S=\frac{1}{m}\sum _{i=1}^{n}1\{h(x^{(i)})\ne y^{(i)}\}\end{array}$

上述公式 ε(hθ)S$\epsilon (h_{\theta }{)}_S$ 表示为依赖于训练集 S 的训练误差为假设错误分类的训练样本数之和与训练样本集总数的比值。

所有我们定义经验风险最小化（empirical risk mininmization，ERM）为：

θ^=argminθε(hθ)S(2)$\begin{array}{}\text{(2)}& \hat{\theta }=\text{arg}{\text{min}}_{\theta }\epsilon (h_{\theta }{)}_S\end{array}$

Step4：Generalization Error（泛化误差）

ε(hθ)=P(x,y)∼D(h(x)≠y)(3)$\begin{array}{}\text{(3)}& \epsilon (h_{\theta })=P_{(x,y)\sim D}(h(x)\ne y)\end{array}$

这里得到的是一个概率，表示通过特定的分布D生成的样本（x，y）中的y与通过预测函数h(x)生成的结果不同的概率。

这个误差是我们理论上计算出来的误差，一般的在统计中带有“ ^”表示的估计量，估计的意思就是我们通过样本来计算这个变量的值。反之，一般理论值就不带“ ^ ”。
这样一来我们就可以将

Step5：假设类H$\mathcal{H}$

定义假设类 H$\mathcal{H}$ 为 ：由所有假设构成的集合，或者说由所有线性分类器构成的集合。即，
H={hθ:hθ=1{θTx≥0},θ∈Rn+1}(4)$\begin{array}{}\text{(4)}& \mathcal{H}=\{h_{\theta }:h_{\theta }=1\{{\theta }^{T}x\ge 0\},\theta \in {\mathbb{R}}^{n+1}\}\end{array}$

Step6：经验风险最小化ERM

所以我们将ERM从原来的对于参数的选取重新定义为从假设类 H$\mathcal{H}$ 中选取一个假设函数：
h^=argminh∈Hε^(hθ)S(5)$\begin{array}{}\text{(5)}& \hat{h}=\text{arg}\underset{h\in \mathcal{H}}{\text{min}}\hat{\epsilon }(h_{\theta }{)}_S\end{array}$

The case of finite H

定义假设集 H$\mathcal{H}$ 为 H={h1,h2,...,hm}$\mathcal{H}=\{h_1,h_2,...,h_m\}$ 。
所以ERM会选择最小训练误差集的假设：h^=argminh∈Hε^(hθ)S$\hat{h}=\text{arg}\underset{h\in \mathcal{H}}{\text{min}}\hat{\epsilon }(h_{\theta }{)}_S$ 。

为了最小训练误差和泛化误差的差值是有上界的，即如果训练误差很小，那么泛化误差也不会太大，我们需要完成两个步骤：
首先，证明训练误差 ε^$\hat{\epsilon }$ 是对泛化误差 ε$\epsilon$ 的一个很好的估计，ε^≈ε$\hat{\epsilon }\approx \epsilon$。
其次，证明泛化误差存在上界。

最小训练误差和泛化误差的差值是有上界

证明训练误差是对泛化误差的一个很好的估计

• Step1：从假设集 H={h1,h2,...,hm}$\mathcal{H}=\{h_1,h_2,...,h_m\}$ 中选取 hj$h_j$ ，且暂时只考虑
  hj$h_j$ 。
• Step2：定义 Zi=1{hj(x(i))≠y(i)}$Z_i=1\{h_j(x^{(i)})\ne y^{(i)}\}$ ，表示第 i$i$ 个样本是否被错误分类。因为 Zi∈{0,1}$Z_i\in \{0,1\}$ ，所以 Zi$Z_i$ 明显满足贝努利分布。
  所以由定义可知 P(Zi=1)=ε(hj)$P(Z_i=1)=\epsilon (h_j)$ 。同时，由于样本集满足IID，所以 Zi$Z_i$ 也满足IID。
  所以训练误差可以表示为：
  ε^(hj)=1m∑i=1n1{h(x(i))≠y(i)}=1m∑i=1nZi(6)$\begin{array}{}\text{(6)}& \hat{\epsilon }(h_j)=\frac{1}{m}\sum _{i=1}^{n}1\{h(x^{(i)})\ne y^{(i)}\}=\frac{1}{m}\sum _{i=1}^n{Z}_i\end{array}$
• Z$Z$ 是服从伯努利分布的，他的期望是 ε(hi)$\epsilon (h_i)$，利用Hoeffding不等式就可以得到下面的式子：

P(|ε(hj)−ε^(hj)|>γ)≤2e−2γ2m(7)$\begin{array}{}\text{(7)}& P(|\epsilon (h_j)-\hat{\epsilon }(h_j)|>\gamma )\le 2e^{-2{\gamma }^{2}m}\end{array}$

从上式可以看出，对于特定的的，当m很大时，训练误差 ε^(hj)$\hat{\epsilon }(h_j)$ 和泛化误差 ε(hj)$\epsilon (h_j)$ 很接近的概率很大。

证明泛化误差存在上界

• 定义随机事件 Aj$A_j$ 为 |ε(hj)−ε^(hj)|>γ$|\epsilon (h_j)-\hat{\epsilon }(h_j)|>\gamma$ ，所以有 P(Aj)≤2e−2γ2m$P(A_j)\le 2e^{-2{\gamma }^{2}m}$ 。
• 所以由一致限(The union bound)，可以证明 P(∃hj∈H,|ε(hj)−ε^(hj)|>γ)$P(\mathrm{\exists }{h}_j\in \mathcal{H},|\epsilon (h_j)-\hat{\epsilon }(h_j)|>\gamma )$ 。
  
  用1减去上式的两边可得：
  
  所以，得到一致收敛性（a uniform conversions result）：
  对假设集 H$\mathcal{H}$ 中任意一个假设函数 h$h$ 在不小于 1−2e−2γ2m$1-2e^{-2{\gamma }^{2}m}$ 的概率下，训练误差 ε^$\hat{\epsilon }$ 与泛化误差 ε$\epsilon$ 之间的差距将在 γ$\gamma$ 之内。
  所以随着训练集大小m的增大，理论误差和训练误差在接近，并且是依一定的概率。我们也想知道给了一定的误差概率之后，我们的m到底取多大是合适的。

选择合适的m——样本复杂度

现在我们首先给定 γ$\gamma$ 和令 δ=2e−2γ2m$\delta =2e^{-2{\gamma }^{2}m}$ 。所以我们可以得到一致收敛性的另外一种形式：

m≥12γ2log2kδ(8)$\begin{array}{}\text{(8)}& m\ge \frac{1}{2{\gamma }^2}\log \frac{2k}{\delta }\end{array}$

所以，得到样本复杂度（algorithm’s sample complex）：
当训练集总数 m≥12γ2log2kδ$m\ge \frac{1}{2{\gamma }^2}\log \frac{2k}{\delta }$ ，至少在概率 1−δ$1-\delta$ 下，∀hi∈H$\mathrm{\forall }{h}_i\in H$ , |ε(hi)−ε^(hi)|≤γ$|\epsilon (h_i)-\hat{\epsilon }(h_i)|\le \gamma$ 成立。也就是说，如果我们想通过样本对总体有个较为准确的估计，我们需要采集最小的样本量是多少。

注：∀k,logk≤30$\mathrm{\forall }k,\log k\le 30$ 。

选择合适的 γ ——误差界限

现在我们首先给定 m$m$ 和令 δ=2e−2γ2m$\delta =2e^{-2{\gamma }^{2}m}$ 。所以我们可以得到：
在至少在概率 1−δ$1-\delta$ 下，∀hi∈H$\mathrm{\forall }{h}_i\in \mathcal{H}$ , |ε^(h)−ε(h)|≤12mlog2kδ−−−−−−−√=γ$|\hat{\epsilon }(h)-\epsilon (h)|\le \sqrt{\frac{1}{2m}log\frac{2k}{\delta }}=\gamma$ 成立。

假设一致收敛成立，那么∀hi∈H$\mathrm{\forall }{h}_i\in H$ , |ε(hi)−ε^(hi)|≤γ$|\epsilon (h_i)-\hat{\epsilon }(h_i)|\le \gamma$ ，可以得到训练误差 ε^$\hat{\epsilon }$ 与泛化误差 ε$\epsilon$ 之间的差距：
使用ERM假设训练误差最小值：h^=argminh∈Hε^(h)$\hat{h}=\text{arg}\underset{h\in \mathcal{H}}{\text{min}}\hat{\epsilon }(h)$
定义泛化误差最小值： h∗=argminh∈Hε(h)$h^{\ast }=\text{arg}\underset{h\in \mathcal{H}}{\text{min}}\epsilon (h)$ 。
同时，由定义ERM可以得到 h^≤h∗$\hat{h}\le h^{\ast }$
所以：

根据上面的推导我们得出以下结论：
定理 1：
假设有一个有限假设集 H={h1,h2,...,hk}$\mathcal{H}=\{h_1,h_2,...,h_k\}$ ， |H|=k$|\mathcal{H}|=k$ 。固定 m$m$ 和 δ$\delta$ ，在至少在概率 1−δ$1-\delta$ 时，ε(h^)≤minh∈Hε(h)+212mlog2kδ−−−−−−−√$\epsilon (\hat{h})\le \underset{h\in \mathcal{H}}{\text{min}}\epsilon (h)+2\sqrt{\frac{1}{2m}log\frac{2k}{\delta }}$。

由定理1得出以下推论：
如果我们扩充假设类集合的范围，即由原来的假设类 H$\mathcal{H}$ 扩充为即 H′${\mathcal{H}}^{\prime }$ （例如由我们最初假设的线性函数改变为二次函数），则定理1结论第一项 minh∈Hε(h)$\underset{h\in \mathcal{H}}{\text{min}}\epsilon (h)$（可视为偏差）的值会变小，因为扩充假设类集，可能有更好的假设函数使得最小泛化误差下降；第二项（可视为方差）的值会增大，因为k的值增加了。
因此，如果假设类过小，则第一项过大，会造成欠拟合，通过扩充假设类，可以使得第一项的值下降，但是第二项值上升，如果扩充过大，会造成过拟合，同样会增加泛化误差。因此要想得到最小的泛化误差，需要在选择合适的，即在方差和偏差之间进行权衡。

推论1：
假设有一个有限假设集 H={h1,h2,...,hk}$\mathcal{H}=\{h_1,h_2,...,h_k\}$ ， |H|=k$|\mathcal{H}|=k$ 。固定 γ$\gamma$ 和 δ$\delta$ ，在至少在概率 1−δ$1-\delta$ 时，满足 ε(h^)≤minh∈Hε(h)+2γ$\epsilon (\hat{h})\le \underset{h\in \mathcal{H}}{\text{min}}\epsilon (h)+2\gamma$ ，m$m$ 应该满足： m≥12γ2log2kδ=O(1γ2logkδ)$m\ge \frac{1}{2{\gamma }^2}log\frac{2k}{\delta }=O(\frac{1}{{\gamma }^2}log\frac{k}{\delta })$ 。

The case of infinite H

在这里我们将介绍关于假设类 H$\mathcal{H}$ 为无先限集的情况。首先我们先给出一种非正式的直观表达，接着在正式的通过公式推导证明。

Informal

我们还是以线性分类为例，现在假设 H$\mathcal{H}$ 中的假设函数 hi$h_i$ 由d个参数构成。同时由于在计算机中实数我们使用 double 类型表示，那么，这d个实数需要用64d个2进制位表示。所以 k=|H|=264d$k=|\mathcal{H}|=2^{64d}$ 。所以由推论1我们可以得到：
假设有一个有限假设集 H={h1,h2,...,hk}$\mathcal{H}=\{h_1,h_2,...,h_k\}$ ， |H|=k$|\mathcal{H}|=k$ 。固定 γ$\gamma$ 和 δ$\delta$ ，在至少在概率 1−δ$1-\delta$ 时，满足 ε(h^)≤minh∈Hε(h)+2γ$\epsilon (\hat{h})\le \underset{h\in \mathcal{H}}{\text{min}}\epsilon (h)+2\gamma$ ，m$m$ 应该满足： m≤O(1γ2log264dδ)=O(dγ2log1δ)=Oγ,δ(d)$m\le O(\frac{1}{{\gamma }^2}log\frac{2^{64d}}{\delta })=O(\frac{d}{{\gamma }^2}log\frac{1}{\delta })=O_{\gamma ,\delta }(d)$ 。

Formal

分散：集合 S={x(i),...,x(d)}$S=\{x^{(i)},...,x^{(d)}\}$ ，如果假设集 H$\mathcal{H}$ 中存在 hi$h_i$ 可以将S中的所有点按标签分开 ({y(1),...,y(d)}$(\{y(1),...,y(d)\}$，我们就说 H$\mathcal{H}$ 可以分散S。
解释：
例如对于一个集合 S={x(1),x(2),x(3)}$S=\{x^{(1)},x^{(2)},x^{(3)}\}$ ，如果对于假设集 H$\mathcal{H}$ 中存在 hi$h_i$ 可以将S完美分开（训练误差为0）。如下图所示：

我们就称 H$\mathcal{H}$ 可以分散S。

Vapnik-Chervonenkis dimension（VC维）：给定一个假设集合 H$\mathcal{H}$ ，这个 H$\mathcal{H}$ 可以分散集合S的最大个数为VC维，记为 VC(H)=d$VC(\mathcal{H})=d$，如果H可以将任意的S分散，我们就说这个H的VC为无穷大，记为 VC(H)=∞$VC(\mathcal{H})=\infty$ 。
对于上面的例子，其VC维 VC(H)=3$VC(\mathcal{H})=3$ 。（更一般的，n维线性分类器最多只能给n+1个点进行无误差分类，其VC维 VC(H)=n+1$VC(\mathcal{H})=n+1$ ）

下面有两个非常著名且重要的定理：
定理2：给定一个假设集 H$\mathcal{H}$ ，并且 VC(H)=d$VC(\mathcal{H})=d$ ，在至少满足 1−δ$1-\delta$ 这个概率的情况下，我们可以在 H$\mathcal{H}$ 中找到一个 h$h$ 满足下面这个不等式：

|ε(h)−ε^(h)|≤O(dmlogmd+1mlog1δ−−−−−−−−−−−−−−√)(9)$\begin{array}{}\text{(9)}& |\epsilon (h)-\hat{\epsilon }(h)|\le O(\sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta }})\end{array}$

所以：

ε(h^)≤ε(h∗)+O(dmlogmd+1mlog1δ−−−−−−−−−−−−−−√)(10)$\begin{array}{}\text{(10)}& \epsilon (\hat{h})\le \epsilon (h^{\ast })+O(\sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta }})\end{array}$

所以在VC维确定的情况下，且训练集m足够大时，训练误差 ε^$\hat{\epsilon }$ 和泛化误差 ε$\epsilon$ 收敛。

推论2：对于 H$\mathcal{H}$ 中的所有h，|ε(h)−ε(h)|≤γ$|\epsilon (h)-{\epsilon }^{(}h)|\le \gamma$ 至少以 1−δ$1-\delta$ 的概率成立，所以 m=Oγ,δ(d)$m=O_{\gamma ,\delta }(d)$ 。

直观理解：如果需要确保训练误差和泛化误差的差值在一个给定的范围内，并且发生的概率不低于 1−δ$1-\delta$ ，需要的样本数量m和假设集的VC维大小d呈线性相关。

深入理解：
样本的复杂度的上界由VC维确定（一般而言，VC维和模型参数数量呈线性正相关，样本数量m和模型参数数量呈线性正相关。主流如此，但依然存在一些特例）；
样本的复杂度的下界由VC维确定（训练样本的数目的阶和VC维相同，在最坏情况下，样本的复杂度的下界也是VC维）；
对于推论2的深入理解我还有些疑问，这只是记下了老师的话，望哪位大佬可以解释一下。