CS229 Lecture 9

---

课程要点

学习理论

---

偏差与方差

就上面的三幅函数与数据的拟合图像来说，左图明数据呈现出二次函数形式而拟合函数却是一次函数$\theta_0+\theta_1x$θ0​+θ1​x,未能拟合出数据的特征，因此会造成训练误差很大，进而泛化误差就更不可靠。处于欠拟合状态，有较高的偏差 (high bais)。而右图使用了$y=\theta_0+\theta_1x+\cdots+\theta_5x$y=θ0​+θ1​x+⋯+θ5​x来拟合数据，可以看到数据点全都在函数图像上，但是单单看数据点呈现出的却是明显不是这么复杂的，因此右图明显过拟合了，会造成泛化无法较大。其实质为算法拟合输了数据中一些奇怪的特征，这些奇怪的特征仅仅存在于这批数据中，而非整个数据空间的分布状态。因此如果再抽取一批数据可能会拟合出于5次多项式不同的函数，泛化误差过大。被称为高方差(high variance)。而中间的图恰恰处于两者之间，可能会拥有更好的泛化能力。

---

对于线性分类问题，有算法：
$h_{\theta}(x)=g(\theta^Tx)$hθ​(x)=g(θTx)

$g(z)=1\{x\ge0\}$g(z)=1{x≥0}    $y\in\{0,1\}$y∈{0,1}

$S=\{(x^{(i)},y^{(i)})\}_{i=1}^{m}$S={(x(i),y(i))}i=1m​     $(x^{(i)},y^{(i)})\stackrel{IID}\sim \mathcal{D}$(x(i),y(i))∼IIDD

$h_\theta(x)$hθ​(x)的训练误差被定义为：
$\hat\varepsilon(h) = \sum_{i=1}^{m} 1\{h_{\theta}(x^{(i)})\neq y^{(i)}\}$ε^(h)=i=1∑m​1{hθ​(x(i))̸​=y(i)}

---

ERM(empirical risk minimization)

对于函数的参数可行解的范围有很多，怎么选取一个最好的，其中一个方法就是最小化训练误差：

$\hat\theta=arg\,\,min\hat\varepsilon(h_{\theta})$θ^=argminε^(hθ​)

这个过程就被称为经验风险最小化$(ERM)$(ERM),最后得出的结果$\hat h =h_{\hat\theta}$h^=hθ^​,经验风险最小化是一种最基础的学习算法。其实我们学习了一组参数$\theta$θ,其实也就相当于学习到了一个$h$h。

现在定义假设类 (hypothesis class) $\mathcal{H}$H为一系列分类器:
$\mathcal{H}=\{h_{\theta_0}:h_{\theta}(x)=1\{\theta^T x\ge0\},\theta\in R^{n+1}\}$H={hθ0​​:hθ​(x)=1{θTx≥0},θ∈Rn+1}

ERM被定义为：

$\hat h =arg\,\,\mathop {\min }\limits_{h\in\mathcal{H}}\hat\varepsilon(h)$h^=argh∈Hmin​ε^(h)

$h$h的泛化误差被定义为:

$\varepsilon(h)=p(x,y)\sim\mathcal{D}(h(x)\neq y)$ε(h)=p(x,y)∼D(h(x)̸​=y)

---

为何最小化训练误差就可以保证泛化误差也很小，为了后续的证明引入两个定理：

定理一：Union Bound

有$A_1,A_1,\cdots A_k$A1​,A1​,⋯Ak​ 共$k$k个事件，这$k$k个事件并不一定是独立的，那么这$k$k个事件任何一个发生的概率为:

$p(A_1UA_2U\cdots UA_k)\le p(A_1)+p(A_2)+\cdots+p(A_k)$p(A1​UA2​U⋯UAk​)≤p(A1​)+p(A2​)+⋯+p(Ak​)

定理二：Hoeffding inequality

假设$Z_1,Z_2,\cdots,Z_m$Z1​,Z2​,⋯,Zm​是$m$m个独立同分布$(IID)$(IID)的属于伯努利$(Bernoulli)$(Bernoulli)分布的随机变量,即$p(Z_{i}=1)=\phi$p(Zi​=1)=ϕ,$p(Z_{i}=0)=1-\phi$p(Zi​=0)=1−ϕ,定义$\hat\phi=\frac{1}{m}\sum_{i=1}^{m}Z_{i}$ϕ^​=m1​∑i=1m​Zi​为随机变量的均值，存在$\gamma>0$γ>0，那么有：

$p(|\phi-\hat\phi|>\gamma)\le 2exp(-2\gamma^{2}m)$p(∣ϕ−ϕ^​∣>γ)≤2exp(−2γ2m)

上面定理中使用均值来估计$\phi$ϕ就类似于以频率估计概率。上面式子说明只要$m$m很大，那么$\hat\phi$ϕ^​于真实的$\phi$ϕ的具体就不会相差太远。

上图大概是$\hat\phi$ϕ^​的分布(不要在意坐标轴)，当增加训练样本时$\hat\phi$ϕ^​的分布会由灰色变为黑色线。可以看到样本越多那么$|\phi-\hat\phi|\le\gamma$∣ϕ−ϕ^​∣≤γ的概率越大。

---

有限$\mathcal{H}$H的情形：

假设$\mathcal{H}=\{h_1,h_2,\cdots,h_k\}$H={h1​,h2​,⋯,hk​}共$k$k的假设，$\mathcal{H}$H中的每个函数将$\mathcal{X}$X映射到$\{0,1\}。${0,1}。定义$\hat h=arg\,\,\mathop {\min }\limits_{h_i\in\mathcal{H}}\hat\varepsilon_{S}(h_i)$h^=arghi​∈Hmin​ε^S​(hi​),为了达到证明如果训练误差很小，那么泛化误差也很小的目的，我们的证明策略为：

1. 证明$\hat\varepsilon\approx\varepsilon$ε^≈ε
2. 证明$\hat\varepsilon$ε^有上界

对于一个固定$h_j\in\mathcal{H}$hj​∈H,定义$Z_j=1\{h_j(x^{(i)})\neq y^{(i)}\}$Zj​=1{hj​(x(i))̸​=y(i)}。其中样本$Z_j$Zj​都是独立同分布的随机变量。对于一个样本$Z_i$Zi​,那么$p(Z_i=1)=\varepsilon(h)$p(Zi​=1)=ε(h),训练误差可以被写为：

$\hat\varepsilon(h_i)=\frac{1}{m}\sum_{j=1}^{m}Z_j$ε^(hi​)=m1​∑j=1m​Zj​

根据前面提到的Hoeffding不等式有：

$p(|\hat\varepsilon(h_i)-\varepsilon(h_i)|>\gamma)\le 2exp(-2\gamma^{2}m)$p(∣ε^(hi​)−ε(hi​)∣>γ)≤2exp(−2γ2m)

通过上式可知，如果m很大，那么训练误差和泛化误差会很接近。当然这只是对$h_i$hi​的一个保证，我们要证明对于所有的$h\in\mathcal{H}$h∈H都成立。

现在定义事件$A_i$Ai​为$|\hat\varepsilon(h_i)-\varepsilon(h_i)|>\gamma$∣ε^(hi​)−ε(hi​)∣>γ。我们已经知道对于任意的一个事件$A_i$Ai​有$p(A_i)\le 2exp(-2\gamma^2m)$p(Ai​)≤2exp(−2γ2m),因此使用联合边界定理有：

$p(\exists h_j\in\mathcal{H}\,\,|\hat\varepsilon(h_i)-\varepsilon(h_i)|>\gamma)=p(A_1UA_2U\cdots UA_k)\le p(A_1)+p(A_2)+\cdots+p(A_k)\le 2kexp(-2\gamma^2m)$p(∃hj​∈H∣ε^(hi​)−ε(hi​)∣>γ)=p(A1​UA2​U⋯UAk​)≤p(A1​)+p(A2​)+⋯+p(Ak​)≤2kexp(−2γ2m)

上式两侧用1减有：

$p(\lnot\exists h_j\in\mathcal{H}\,\,|\hat\varepsilon(h_i)-\varepsilon(h_i)|>\gamma)=p(\forall h_i\in\mathcal{H}\,\,|\hat\varepsilon(h_i)-\varepsilon(h_i)|\le \gamma)\ge1-2kexp(-2\gamma^2m)$p(¬∃hj​∈H∣ε^(hi​)−ε(hi​)∣>γ)=p(∀hi​∈H∣ε^(hi​)−ε(hi​)∣≤γ)≥1−2kexp(−2γ2m)

因此有$1-2kexp(-2\gamma^2m)$1−2kexp(−2γ2m)的概率说对于所有的$h\in\mathcal{H}$h∈H,$\hat\varepsilon(h)$ε^(h)在$\varepsilon(h)$ε(h)的$\gamma$γ领域内。因为这个边界对于所有的$h\in\mathcal{H}$h∈H都成立，因此被称为一致性收敛。

根据$m,\gamma,$m,γ,误差三者之间的关系，如果知道$\gamma,\sigma$γ,σ就可以求解需要的样本数$m$m。其中$\sigma=2kexp(-2\gamma^2m)$σ=2kexp(−2γ2m)。经推导有：

$m\ge\frac{1}{2\gamma^2}log{\frac{2k}{\sigma}}$m≥2γ21​logσ2k​

即只要$m$m超过$\frac{1}{2\gamma^2}log{\frac{2k}{\sigma}}$2γ21​logσ2k​对于所有的$h\in \mathcal{H}$h∈H就有大于$1-\sigma$1−σ的概率有$|\hat\varepsilon(h_i)-\varepsilon(h_i)|\le\gamma$∣ε^(hi​)−ε(hi​)∣≤γ。

上面的$m$m被称为样本复杂度边界

同理可以根据$m,\sigma$m,σ求解$\gamma$γ。固定$m,\sigma$m,σ在$1-\sigma$1−σ的概率下，可以得到$\forall h\in \mathcal{H}$∀h∈H有$|\hat\varepsilon(h_i)-\varepsilon(h_i)|\le\sqrt{\frac{1}{2m}log\frac{2k}{\sigma}}$∣ε^(hi​)−ε(hi​)∣≤2m1​logσ2k​​。

---

假设$\forall h\in\mathcal{H}\,\,|\hat\varepsilon(h_i)-\varepsilon(h_i)|\le \gamma$∀h∈H∣ε^(hi​)−ε(hi​)∣≤γ,令$\hat h=arg\,\,\mathop {\min }\limits_{h\in\mathcal{H}}\hat\varepsilon(h)$h^=argh∈Hmin​ε^(h),我们能得到什么？

定义$h^{*}=arg\,\,\mathop {\min }\limits_{h\in\mathcal{H}}\varepsilon(h)$h∗=argh∈Hmin​ε(h),是在$\mathcal{H}$H中最好的假设。有：

$\varepsilon(\hat{h})\le\hat\varepsilon(\hat{h})+\gamma\le\hat\varepsilon(h^*)+\gamma\le\varepsilon(h^*)+2\gamma$ε(h^)≤ε^(h^)+γ≤ε^(h∗)+γ≤ε(h∗)+2γ

不等式1，3成立在于运用了统一收敛，不等式2成立是因为$\hat h$h^是训练误差最小的$h$h，而$h*$h∗是泛化误差最小的，因此对于任意的$h$h有$\hat\varepsilon(\hat h)\le\hat\varepsilon(h)$ε^(h^)≤ε^(h)。

---

定理：

$|\mathcal{H}|=k$∣H∣=k,将$m,\sigma$m,σ固定至少有$1-\sigma$1−σ的概率有：

$\varepsilon(\hat h)\le(\mathop {\min }\limits_{h\in\mathcal{H}}\varepsilon(h))+2\sqrt{\frac{1}{2m}log\frac{2k}{\sigma}}$ε(h^)≤(h∈Hmin​ε(h))+22m1​logσ2k​​

如果$\mathcal{H}\longrightarrow\mathcal{H^{'}}$H⟶H′并且$\mathcal{H^{'}}\supseteq\mathcal{H}$H′⊇H,由于函数变多了，那么上式第一项会减小，而第二项会变大。第一项对应于前面讲的偏差而后一项对应于前面说的方差。

上图横轴代表模型复杂度即(多项式的次数，或者说$\mathcal{H}$H的大小),纵轴代表误差，灰色的线表示训练误差，而黑色实线表示泛化误差，可以知道模型过于简单容易出现欠拟合，而模型过于复杂则会出现过拟合。

推论：

$|\mathcal{H}|=k$∣H∣=k,将$\gamma,\sigma$γ,σ固定,对于$\varepsilon(\hat h)\le \mathop {\min }\limits_{h\in\mathcal{H}} \epsilon(h)+2\gamma$ε(h^)≤h∈Hmin​ϵ(h)+2γ,在大于$1-\sigma$1−σ的概率下满足：

$m\ge\frac{1}{2\gamma^2}log{\frac{2k}{\sigma}}=O(\frac{1}{\gamma^2}log\frac{2k}{\sigma})$m≥2γ21​logσ2k​=O(γ21​logσ2k​)。