机器学习笔记——8 学习的一般理论

机器学习笔记——8 学习的一般理论

在第一章绪论中，我们曾经讲到，机器学习是关于学习算法的学问，在前面的文章中，我们主要介绍了一些具体的学习算法的例子，而本文将从更高和更抽象的角度，讨论学习算法的一般化的理论，主要涉及到泛化误差(generalization error) 和经验误差(empirical error) 之间的量化理论，以及我们为了获得有最小泛化误差的假设，但实际上却是通过最小化经验误差来获得$\hat{h}$，这样做的合理性和理论保证。

泛化误差的分解：偏差与方差的权衡(The Bias-Variance Tradeoff)

对于一个学习问题，我们可以选择不同的模型进行参数的学习，假设客观上的模型为$$y=f(x)+ϵ$$其中$$E(ϵ)=0$$$$Var(ϵ)={\sigma }^2$$而我们的从训练集$S$中学到的模型记之为$\widehat{f_S}(x)$，特别要注意，这里的$\widehat{f_S}(x)$区别于$f(x)$，后者是一个固定的数，前者是一个随机变量，因为模型$\widehat{f_S}$决定于训练集$S$，而训练集$S$是不确定的。 在接下的讨论中，我们将看到泛化误差可以被分解成三部分。 $$\begin{array}{rl}E((y-\widehat{f_S}(x){)}^2)=& E((f(x)+ϵ-\widehat{f_S}(x){)}^2)\\ =& {\sigma }^2+E((\widehat{f_S}(x)-f(x){)}^2)\\ =& {\sigma }^2+Var(\widehat{f_S}(x))+(E(\widehat{f_S}(x))-f(x){)}^2\\ =& {\sigma }^2+Var(\widehat{f_S}(x))+(Bias\widehat{f_S}(x){)}^2\end{array}$$因此我们来讨论模型选择是如何影响到泛化误差的。

欠拟合(Underfitting)：模型并没有充分地从训练集中获取到足够的信息，因此没有充分地建立属性值同便签值之间的关系。此时就会有$E(\widehat{f_S}(x))!=f(x)$就会导致泛化误差中的偏差项$(Bias\widehat{f_S}(x){)}^2$变大。过拟合(Overfitting)：模型对训练集中的数据有很好的拟合，但是对属性值和便签值之间建立的关系，无法泛化到训练集外广大的数据。这种情况往往模型会比较复杂，模型中包含的参数也会比较多。因此这就会导致泛化误差中的方差项$Var(\widehat{f_S}(x))$变大。本身噪音过多(noisy)：这种情况说明不是模型选择的问题，比如我们对属性和便签值进行建模，但是属性值和便签值本身并没有很强的联系，这种情况就会导致${\sigma }^2$变大。

上面我们看到泛化误差的分解情况，同时也看到，方差和偏差往往是不可兼得的， 当我们选择一个太简单的模型时，此时无法充分体现出联系；但选择一个太复杂的模型是，此时就会导致模型方差太大。因此需要根据实际的情况权衡利弊，具体情况具体分析。

关于泛化误差的学习理论

接下来我们抽象地来看学习的过程，实际上我们是通过最小化训练集上的误差来确定模型 $\widehat{f_S}$的，我们称该误差为经验误差(Empirical error)，与之相对应的是泛化误差，最小化泛化误差才是我们真正想要的。 这里有三个我们要解决的关键问题：

我们通过最小化经验误差(Empirical risk minimization,EMR) 得到的模型$\widehat{f_S}$，但是经验误差是否能够用来估计泛化误差？是否具有相合性？经验误差和泛化误差之间量化的理论是什么？通过EMR选出来的假设$\widehat{f_S}$和客观上最好的假设$f$，其泛化误差的差距可以被控制住吗？

为了说明上述问题，我们现在只考虑二分类问题，而对于多分类和回归的情况，本文所讨论的方法都是可以"泛化"到其上的。 假设样本数据是独立同分布的，即训练集为$S=\{(x^{(i)},y^{(i)});i=1,...,m\}$，其中$y\in \{0,1\}$，记我们关注的假设空间为$H$。则泛化误差为$$ϵ(h)=P_{(x,y)\in D}(h(x)!=y)$$经验误差为$$\widehat{{ϵ}_S}(h)=\frac{1}{m}\sum _{i=1}^{m}1\{h(x^{(i)})!=y^{(i)}\}$$这里，我们根据大数定律，即可发现，当样本量足够多时，经验误差与泛化误差的差异限制在某个差距的概率趋于一。根据切比雪夫不等式，有 $$P\{|\widehat{{ϵ}_S}(h)-ϵ(h)|>\gamma \}<\frac{\alpha }{m{\gamma }^2}$$这里我们不用切比雪夫不等式，利用霍夫丁不等式（Hoeffding’s inequality），有$$P\{|\widehat{{ϵ}_S}(h)-ϵ(h)|>\gamma \}<2exp(-2{\gamma }^{2}m)$$现在我们考虑假设空间$H$只有有限个假设，即$|H|=k$。则当我们考虑整个假设空间的泛化误差时，利用概率论中$P({\cup }_{i=1}^k{A}_i)<{\sum }_{i=1}^{k}P(A_i)$，我们有$$P(\exists h\in H,|\widehat{{ϵ}_S}(h)-ϵ(h)|>\gamma )<2kexp(-2{\gamma }^{2}m)$$至此，我们便回答了开始时提出的第一个问题。上述不等式意味着，当样本量足够大时，对于整个假设空间，经验误差都会依概率趋近于泛化误差，这就给我们利用最小化经验误差(ERM)来选择模型提供了理论依据，因为在样本量充足的情况下，经验误差确实可以来估计泛化误差，这种估计具有相合性，并且不只只针对特定的一个假设，对于一个有限假设的假设空间而言，整个假设空间也是具有这种相合性的。 接下来我们需要解决第二个问题，也就是与泛化误差有关的量化关系，具体地，问题可以被阐述为：

在有m个样本的训练集中，假设空间的假设有k个，我们能以$1-\delta$的概率保证的泛化误差和经验误差的差距上限是多少？假设空间有k个假设，我们想要以$1-\delta$的概率保证泛化误差和经验误差的差距上限为$\gamma$，那么至少需要多少样本？这个问题也称为样本复杂度。

对于第一个问题，我们利用上述式子，有$$\delta >2kexp(-2{\gamma }^{2}m)$$反解可以保证的差距上限$\gamma$为：$$\gamma <\sqrt{\frac{1}{2m}\log \frac{2k}{\delta }}$$对于第二个问题，我们同样可以反解出需要的样本数为：$$m>\frac{1}{2{\gamma }^2}\log \frac{2k}{\delta }$$从这里可以看出，假设空间的可能选择$k$越多，需要的样本数也就越多，但是其是对数增长的(logarithmic)。 最后，我们需要回答第三个问题，假设我们通过ERM选择出来的假设为$\hat{h}$，潜在的泛化误差最小的假设为记为$h^{\ast }$。那么，根据上述的不等式，在$1-\delta$的概率保证下，有$$\begin{array}{rl}ϵ(\hat{h})& <\widehat{ϵ}(\hat{h})+\gamma \\ & <\widehat{ϵ}(h^{\ast })+\gamma \\ & <ϵ(h^{\ast })+2\gamma \end{array}$$其中，$\gamma <\sqrt{\frac{1}{2m}\log \frac{2k}{\delta }}$ 上述表明，我们通过ERM选出来的假设$\hat{h}$，在$1-\delta$的概率保证下，$\hat{h}$的泛化误差比起客观上最好的假设$h$，最多不会超过$2\gamma$的差距。这从理论上保证我们利用ERM来选择假设$\hat{h}$的合理性。