CS229 Note4 Learning Theory

这一部分的内容：

引入偏差和方差(泛化误差)
引入训练误差、经验风险最小化(ERM)
在有限假设类以及无限假设类中进行ERM时，需要考虑的问题(样本复杂度以及假设类大小对总体训练误差的影响)

偏差/方差平衡(bias/variance)

泛化误差

模型假设对于不一定在训练集内的样本进行预测的误差

偏差(bias)

即使使用大量数据进行训练，模型也不能很好的捕捉到数据的规律，存在很大的泛化误差。(对训练集中的样本和非训练集样本都不能很好预测，欠拟合)

方差(variance)

方差是泛化误差的另一种表现形式，即模型可能只是碰巧与当前有限的训练集的规律相符合，但是对于更大的训练集中的数据，可能存在相应的预测误差。(对训练集中的样本能够很好预测，对于非训练集样本不能很好预测，过拟合)

一个好的模型，需要在以上两种泛化误差之间寻求一个平衡

引理

union bound

设$A_1$,$A_2$,$A_3$,$…$,$A_k$是K个不相同事件(不一定互相独立)，那么

$P(A_1\cup...\cup A_k)\leq P(A_1)+...+P(A_k)$

Hoeffding inequality

设$Z_1$,$…$,$Z_m$是从伯努利分布$\phi$中抽取的m个独立同分布的随机变量，即$P(Z_i=1)=\phi$,$p(Z_i=0)=1-\phi$。令$\hat\phi=(1/m)\sum_{i=1}^mZ_i$,即随机变量的平均值，当m很大时，$\hat\phi$可以很好的估计真实的$\phi$值，令$\gamma>0$，那么有

$P(|\phi-\hat\phi|>\gamma)\leq2exp(-2\gamma^2m)$

该引理也被称作Chernoff bound。

training error(empirical error)

给定训练集$S$，大小为m,训练样本$(x^{(i)},y^{(i)})$遵从某种独立同分布的概率分布$\mathcal{D}$，对于一个假设$h$,定义训练误差或者经验风险(empirical risk)为：

$\hat{\mathcal{E}}(h)=\frac{1}{m}\sum_{i=1}^m1\{h{x^{(i)}}\neq y^{(i)}\}$

上式表示：如果从分布$\mathcal{D}$中取出一个新样本$(x,y)$，$h$预测失误的概率。

如果有一个线性分类器$h_\theta(x)=1\{\theta^Tx\geq0\}$，如何去拟合参数$\theta$？一种方式就是最小化训练误差，选择使训练误差最小那个参数$\hat\theta$

$\hat\theta = arg \quad \min_\theta \hat{\mathcal{E}}(h_\theta)$

这个过程就是经验风险最小化，empirical risk minmization(ERM)，学习算法输出的假设是$\hat{h}=h_{\hat{\theta}}$,ERM算法是最“基础”的算法，逻辑回归算法也可以看作是ERM算法的近似。

我们把学习算法的所有假设的集合记作假设类$\mathcal{H}$,$\mathcal{X}$是所有输入特征的取值域，ERM现在是在假设类$\mathcal{H}$上进行最小化，学习算法将会选取风险最小那个假设$\hat{h}$：

$\hat{h}=arg\quad min_{h \in \mathcal{H}}\hat{\mathcal{E}}(h)$

有限假设类$\mathcal{H}$

设假设类$\mathcal{H}=\{h_1,…,h_k\}$包含$k$个假设。假设函数$h$是将输入$x$到${0,1}$的映射。EMR将要选取具有最小风险的$\hat{h}$

设伯努利所及变量$Z$的分布如下，样本点$(x,y)$服从分布$\mathcal{D}$，设$Z=1\{h_i(x)\neq y\}$，$Z_j = 1\{h_i(x^{(j)})\neq y^{(j)}\}$,因为训练集是独立同分布的，因此$Z$和$Z_j$也是一样的分布。

误分类概率$\mathcal{E}(h)$恰好是$Z$(和$Z_j$)的期望，训练误差写作如下：

$\hat{\mathcal{E}}(h_i)=\frac{1}{m}\sum_{i=1}^mZ_j$

现在对这个概率应用Hoeffding inequality

$P(|\mathcal{E}(h_i)-\hat{\mathcal{E}}(h_i)|>\gamma)\leq 2exp(-2\gamma^2m)$

从上式可以可以得到，假如m足够大，那么对于特定的$h_i$，训练误差与泛化误差有很大概率接近。要证明其对于所有$h$的一般性，令$A_i$代表事件$|\mathcal{E}(h_i)-\hat{\mathcal{E}}(h_i)|>\gamma$，由于已经有了不等式$P(A_i)\leq2exp(-2\gamma^2m)$，那么使用union bound。

$\begin{align} P(\exists h\in \mathcal{H}.|\mathcal{E}(h_i)-\hat{\mathcal{E}(h_i)}|>\gamma) &= P(A_1 \cup ... \cup A_k)\\ &\leq \sum_{i=1}^{k}P(A_i) \\ &\leq\sum_{i=1}^k2exp(-2\gamma^2m) \\ &= 2kexp(-2\gamma^2m) \end{align}$

如果上式两边同时被1所减

$\begin{align} P(\neg h \in \mathcal{H}.|\mathcal{E}(h_i)-\hat{\mathcal{E}}(h_i)|>\gamma) &= P(\forall h \in \mathcal{H}.|\mathcal{E}(h_i)-\hat{\mathcal{E}}(h_i)|\leq\gamma|) \\ \geq 1-2kexp(-2\gamma^2m) \end{align}$

上式表示，对于所有假设$h$,$\mathcal{E}(h)$比$\hat{\mathcal{E}}(h)$小$\gamma$的概率至少是$1-2kexp(-2\gamma^2m)$,这叫做一致收敛(union convergence)

在上式中，给定$m$,$\gamma$和误差概率(即所有泛化误差-训练误差小于等于$\gamma$的概率)，可以对剩余的一个变量进行边界限定。

令$\delta = 2kexp(-2\gamma^2m)$，解以上不等式可以得到：

$m \geq \frac{1}{2\gamma^2}log\frac{2k}{\delta}$

$m$被称为样本复杂度，这个边界表示已知误差概率和$\gamma$时，至少需要多少个训练样本。

当$m$和误差概率固定时，可以解得

$|\hat{\mathcal{E}}(h)-\mathcal{E}(h)| \leq \sqrt{\frac{1}{2m}log\frac{2k}{\delta}}$

那么，如何最去最小化训练误差并选取合适的$\hat{h}$呢？
设$h^{\ast}$是使泛化误差最小的假设，$\hat{h}$是使训练误差最小的$h$，有：

$\begin{align} \mathcal{E}(\hat{h})&\leq\hat{\mathcal{E}}(\hat{h}) + \gamma \\ &\leq \hat{\mathcal{E}}(h^{\ast}) + \gamma \\ &\leq {\mathcal{E}}(h^{\ast}) + 2\gamma \end{align}$

第一行使用了一致收敛假设$|\mathcal{E}(\hat{h})-\hat{\mathcal{E}}(\hat{h})| \leq \gamma$

对于第二行，因为对于所有$h$，有$\hat{\mathcal{E}}(\hat{h}) \leq \hat{\mathcal{E}}(h)$。

对于第三行，再一次使用了一致收敛假设。

现在，有以下定理：
给定$|\mathcal{H}|=k$,以及$m$,$\delta$，误差概率至少是$1-\delta$,于是有：

$\mathcal{E}(\hat{h})\leq (min_{h\in \mathcal{H}}\mathcal{E}(h))+2\sqrt{\frac{1}{2m}log\frac{2k}{\delta}}$

当假设类的假设变多，上式的第一项代表偏差只会变小，但是第二项代表方差，k会变大,整体也会变大，因此在需要在这两者之间寻求平衡。

无穷假设类$\mathcal{H}$

在无穷假设类中，我们能够得到类似于有限假设类中的结论吗？
首先来看一个看似不那么“正确”的论证。
假如假设有d个参数，在电脑中，每个参数采用双精度浮点数存储，每个双精度浮点数的大小为64bit，那么参数的总共大小为64dbit,每个bit可以取值0或者1，那么总共有$k=2^{64d}$种假设。根据上一节的推论有

$m\geq O(\frac{1}{\gamma^2}log\frac{2^{64d}}{\delta})=O(\frac{d}{\gamma^2}log\frac{1}{\delta})=O_{\gamma,\delta}(d)$

所以，m至少与参数个数是线性关系。

上述论点存在缺陷，为了得到更令人满意的论点，引入以下概念

VC维

给定一个集合$S=\{x^{(1)},…,x^{(i)}\}$,$x^{(i)} \in \mathcal{X}$,如果在假设类中存在假设$h$，使S中的点具有的标签$y^{(i)}$都能被$h(x^{(i)})=y^{(i)}$正确预测，那么表述为$\mathcal{H}$能够分散$S$。
VC维就是，假设类$\mathcal{H}$能分散的集合$S$中,具有最大的size。
具体的,如果$\mathcal{X}$是n维空间，那么对于能够分散$S$的假设类$\mathcal{H}$,$VC(\mathcal{H})=n+1$。

下面是学习理论中最重要的定理(待证明)

给定假设类$\mathcal{H}$,$VC(\mathcal{H})=d$,当误差概率至少为$1-\delta$时，对于所有假设$h$有

$||\mathcal{E}(h)-\hat{\mathcal{E}}(h)||\leq O(\sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta}})$

同时还有：

$\mathcal{E}(\hat{h})\leq \mathcal{E}(h^{\ast}) +O(\sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta}})$

换句话说，当一个假设类具有有限的假设维时，随着m变大，一致收敛就会发生。
同时还有，当所有假设满足$|\mathcal{E}(h)-\hat{\mathcal{E}}(h)|\leq\gamma$，概率误差至少为$1-\delta$,那么$m=O_{\gamma,\delta}(d)$

换句话说，一个好的学习过程中，训练样本的数量与假设类的VC维线性相关，而VC维又与参数个数线性相关，所以可以得到试图最小化训练误差的算法，训练集的数目与假设的参数的数目线性相关。