本文与前面不同，主要内容不是算法，而是机器学习的另一部分内容——学习理论。主要包括偏差/方差(Bias/Variance)、经验风险最小化(Empirical Risk Minimization,ERM)、联合界(Union bound)、一致收敛(Uniform Convergence)。
偏差/方差权衡
回顾一下，当我们讨论线性回归时，我们尝试过使用简单的线性方法，如\(y=\theta_0 + \theta_1 x\),也尝试使用更复杂的模型，如多项式\(y=\theta_0+\theta_1 x+…+\theta_5 x^5\)。观察下图：
以上述回归问题为例，机器学习的目标是从训练集中得到一个模型，使之能对测试集进行分类。这里训练集和测试集都是分布\(\mathcal{D}\)的样本。机器学习的关注点在于模型在测试集上的分类效果，这也称作泛化能力(generalization ability)。如上图，最左边的图用一个线性模型进行拟合，显然即使拥有很多的训练集，该模型在测试集上进行预测的话，仍然存在着很大的误差，这种情况称为欠拟合，对应着高偏差。对于最右边的图，用一个高阶(五阶)去拟合，从数据中得到的模型结构很可能碰巧是该训练集特有的，即尽管五次多项式模型对训练集的拟合不错，但并非是一个好的模型，因为对于训练集以外的数据，该模型不一定能很好得进行预测，即泛化能力不够好，因此仍然存在着很大的泛化误差，这种情况称作过拟合，对应高方差。
在机器学习中，对偏差和方差的权衡是学习理论重点解决的问题。如果我们的模型太过于简单，只有少量的参数要学习，那么就可能存在高偏差(large bias but small variance)。如果我们的模型太过于复杂，拥有大量的参数，那么就可能存在高方差(large variance but small bias)。在上面的例子中，训练一个二次型的模型(对应中间那幅图)，比训练一个过于简单的一次型模型或过于复杂的五次型模型都好。
经验风险最小化
在这部分我们开始对学习理论进行研究。这部分的研究可以磨练我们的直觉，并学到在不同情况下，更好得应用学习算法的经验法则。我们也会尝试回答一些问题，例如是否可以将偏差/方差的权衡进行形式化表述?这有助于后面对于特征选择方法的学习，也有助于为训练数据选择合适的多项式拟合阶数。其次，在机器学习中，我们对泛化误差格外关注，然而我们的模型是对训练集进行拟合的，训练集拟合表现对泛化误差有什么影响？是否可以将训练集的误差和泛化误差联系在一起。最后一个问题，证明学习算法表现良好是否需要一些条件作为基础？
引理
首先讨论两条引理。
联合界定理(The union bound):令\(A_1,A_2,…,A_k\)是k个事件，这k个时间可以相互独立也可以不相互独立，我们有:
$$P(A_1 \cup A_2 … \cup A_k) \leq P(A_1)+P(A_2)+…+P(A_k)$$
在概率论中，上述是一个公理。任意事件发生的概率显然小于所有事件各自发生的概率之和。该定理可以使用文氏图(韦恩图)进行非正式的证明。
Hoeffding不等式：令\(Z_1,Z_2,…,Z_m\)为m个独立同分布变量(\(i.i.d\)),它们都服从伯努利分布，即\(P(Z_i=1)=\phi,P(Z_i=0)=1-\phi\),我们使用m个服从\(i.i.d的Z_i\)变量的平均值来估计\(\phi\)，得到:
$$\hat{\phi}=\frac{1}{m}\sum_{i=1}^m Z_i$$
那么Hoeffding不等式的定义即，对于任意的固定数值\(\gamma>0\)，满足：
$$P(|\phi-\hat{\phi}|>\gamma) \leq 2exp(-2\gamma^2 m)$$
这个引理是指,如果我们使用m个满足伯努利分布的随机变量的平均值\(\hat{\phi}\)来估计\(\phi\),那么随着样本数目m的增大，我们对参数的估计\(\hat{\phi}\)会越来越接近真实的\(\phi\)值。上式的概率实际上代表犯错误的概率，即犯错误概率会随样本数目的增大而减小。
运用上述两条引理，我们可以得出一些重要的学习理论结论。
经验风险
为了简化我们的讨论，我们将注意力集中在二分类问题上，即\(y \in \{0,1\}\)。所有关于二分类问题的讨论同样适用于其它的回归问题或者多分类问题。
假设给定一个训练集\(S=\{(x^{(i)},y^{(i)});i=1,…,m\}\),样本数量为m，每一个样本都满足独立同分布，且服从分布\(D\),即假设每个样本都是通过该分布生成的。对于一个特定的假设h,我们定义训练误差training error（在学习理论中称作经验风险或经验误差）为：
$$\hat{\epsilon}(h)=\frac{1}{m} \sum_{i=1}^m I\{h(x^{(i)}) \not= y^{(i)}\}$$
\(\hat{\epsilon}(h)\)代表对于特定训练集S得到的估计值，也可以写作\(\hat{\epsilon}_S(h)\)。我们定义泛化误差generalization error为：
$$\epsilon(h)=E_{P(x,y)}[I(h(x) \not= y)]$$
泛化误差是针对满足分布的新样本而言，指的是对于满足分布\(P(x,y)\)的新样本(x,y),会被h误分类的期望，即0-1损失关于\(P(x,y)\)的期望。注意，我们假设训练数据是根据分布\(P(x,y)\)得到的，同时，\(P(x,y)\)也是测试数据的分布，也就是上式泛化误差中的\(P(x,y)\)。这也是PAC假设之一，PAC全称probably approximately correct,是学习理论得以证明所依赖的一个框架和一系列假设，训练集和测试集同分布是其中最重要的一个假设。
考虑一个线性分类问题，令\(h_\theta(x)=I\{\theta^T x \geq 0\}\),即当\(\theta^T x \geq 0\)时，分类结果为1。一种拟合参数\(\theta\)的方法是最小化训练误差:
$$\hat{\theta}=\mathop{argmin}_\limits{\theta} \hat{\epsilon}(h_\theta)$$
我们称这个过程为经验风险最小化(empirical risk minimization,ERM),根据该学习算法，可以得到假设h的估计，即\(\hat{h}=h_{\hat{\theta}}\)。我们认为ERM是最基本的学习算法，其他算法如逻辑回归等也可以被近似当作ERM。
在研究学习理论中，我们暂且不考虑假设具体的参数和具体使用的分类器是什么。我们定义一个学习算法的假设空间\(\mathcal{H}\)由所有的决策函数或模型的集合构成。例如对于线性分类问题，有：\(\mathcal{H}=\{h_\theta:h_\theta(x)=I\{\theta^Tx \geq 0\},\theta \in {\mathbb{R}}^{n+1}\}\)。拓展来说，如果我们在学习神经网络，那么\(\mathcal{H}\)就代表一系列可以代表神经网络的决策函数组成。
在这里，ERM可以认为是在假设空间\(\mathcal{H}\)中寻找使得训练误差最小化的某个假设h.即：
$$\hat{h}=\mathop{argmin}_\limits{h \in H} \hat{\epsilon}(h)$$
一致收敛
我们首先考虑有限的假设空间\(\mathcal{H}=\{h_1,…,h_k\}\),假设空间由k个假设组成。因此\(\mathcal{H}\)只是k个由映射函数组成，该映射函数负责从输入空间\(\mathcal{X}\)映射到\(\{0,1\}\)。经验风险最小化就是从这k个函数中选择使得训练误差最小的假设\(\hat{h}\)。
我们关注的是\(\hat{h}\)在泛化误差上表现,即\(\epsilon(\hat{h})\)。我们的策略包含两个步骤，首先证明，对所有的h，\(\hat{\epsilon}(h)\)都是\(\epsilon(h)\)的可靠估计。接着证明\(\hat{h}\)的泛化误差\(\epsilon(\hat{h})\)存在着一个上界。
先证明第一个，对所有的h，\(\hat{\epsilon}(h)\)都是\(\epsilon(h)\)的可靠估计。
从假设空间选取某个特定的\(h_i \in \mathcal{H}\)。考虑伯努利随机变量Z，我们根据分布\(\mathcal{D}\)生成新样本(x,y),即\((x,y) \sim \mathcal{D}\)，再令\(Z=I\{h_i(x) \not= y\}\)，即判断\(h_i\)能否正确分类新样本。同样我们定义\(Z_j=I\{h_i(x^{(j)}) \not= y^{(j)}\}\)，即判断训练集中的样本是否被正确分类。因为训练样本也是根据分布\(\mathcal{D}\)获得的，则Z和\(Z_j\)属于同分布。
训练误差重写为：
$$\hat{\epsilon}(h_i)=\frac{1}{m}\sum_{j=1}^m Z_j$$
\(\hat{\epsilon}(h_i)\)实际上就是m个服从伯努利分布的随机变量\(Z_j\)的平均值。而\(\epsilon(h_i)\)代表伯努利分布Z的均值。根据Hoeffding不等式，有：
$$P(|\epsilon(h_i)-\hat{\epsilon}(h_i)|>\gamma) \leq 2exp(-2\gamma^2 m)$$
这意味着，对于给定的\(h_i\),当m非常大时，泛化误差和训练误差接近的概率很大，即训练误差\(\hat{\epsilon}(h_i)\)能够很好的估计泛化误差\(\epsilon(h_i)\)。更进一步，我们想证明对于任意的\(h \in \mathcal{H}\),都存在上述结果。为了证明这个结论，我们令\(A_i\)代表\(|\epsilon(h_i)-\hat{\epsilon}(h_i)|>\gamma\)，对于任意给定的\(A_i\),都有：\(P(A_i) \leq 2exp(-2\gamma^2 m)\)。因此使用联合界定义，有：
$$P(\exists h \in \mathcal{H}.|\epsilon(h_i)-\hat{\epsilon}(h_i)|>\gamma) = P(A_1 \cup A_2 … \cup A_k) \leq \sum_{i=1}^k P(A_i) \\\\
\leq \sum_{i=1}^k 2exp(-2\gamma^2 m) \\\\
= 2kexp(-2\gamma^2 m)
$$
同时使用1减去不等式两边有，
$$P(\nexists h \in \mathcal{H}.|\epsilon(h_i)-\hat{\epsilon}(h_i)|>\gamma)=P(\forall h \in \mathcal{H}.|\epsilon(h_i)-\hat{\epsilon}(h_i)| \leq \gamma) \geq 1-2kexp(-2\gamma^2m)$$
上式代表，至少以概率\(1-2kexp(-2\gamma^2m)\)保证,对所有的\(h \in \mathcal{H}\)，都有泛化误差和训练误差的差值不大于\(\gamma\).称作一致收敛定理。
在一致收敛中，有三个参数,\(m,\gamma\),误差的概率(或称作犯错误的概率),这三个参数是互相关联的，我们可以固定其中两个，来推出第三个，其中固定\(m,\gamma\)求概率上式已经得出。下面依次对另外两种参数关联进行说明。
第一个，对于给定\(\gamma,\delta > 0\)，需要多少样本，才可以保证至少有\(1-\delta\)的概率，使得泛化误差和训练误差相差在\(\gamma\)的范围内.令\(1-2kexp(-2\gamma^2m) \geq 1-\delta \)可以求出m:
$$m \geq \frac{1}{2\gamma^2}log\frac{2k}{\delta}$$
即当m满足上式时，对任意的\(h \in \mathcal{H}\),都至少有\(1-\delta\)的概率保证\(|\epsilon(h_i)-\hat{\epsilon}(h_i)| \leq \gamma\)，也即犯错误(\(|\epsilon(h_i)-\hat{\epsilon}(h_i)| > \gamma\))的概率至多为\(\delta\)
这个推论的意义在于，一个模型或算法要达到一个确定的性能时，需要的样本数目为多少。这也称作算法的样本复杂度。上式也表明，达到好的性能，对k的限制只需要对数级别就行，k是假设空间的大小。这个很关键。
同样的，我们也可以固定m和\(\delta>0\),泛化误差会落在训练误差的什么范围内呢？
$$|\hat{\epsilon}(h)-\epsilon(h)| \leq \sqrt{\frac{1}{2m} log \frac{2k}{\delta}}$$
接着证明\(\hat{h}\)的泛化误差\(\epsilon(\hat{h})\)存在着一个上界。也就是考察在一致收敛成立的情况下，我们通过ERM方法得到的假设\(\hat{h}\)的泛化能力到底如何?
首先定义：
$$\hat{h}=\mathop{argmin}_\limits{h \in \mathcal{H}} \hat{\epsilon}(h)$$
$$h^{*}=\mathop{argmin}_\limits{h \in \mathcal{H}} \epsilon(h)$$
\(\hat{h}\)可以理解为在假设空间中，寻找使得训练误差最小的那个假设。\(h^{*}\)可以理解为在假设空间\(\mathcal{H}\)中，寻找使得泛化误差最小的假设。\(h^{*}\)是我们能找到的最好的假设。我们可以将使得训练误差最小的那个假设\(\hat{h}\)和其进行对比,\(\epsilon(\hat{h})\)可以表示训练集上选择使训练误差最小的假设\(\hat{h}\)在泛化误差上的表现。
$$\epsilon(\hat{h}) \leq \hat{\epsilon}(\hat{h})+\gamma \\\\
\leq \hat{\epsilon}(h^{*}) + \gamma \\\\
\leq \epsilon(h^{*}) + 2\gamma
$$
首先是第一个不等式，\(\epsilon(\hat{h})\)是指对于某个特定的假设\(\hat{h}\)的泛化误差,\( \hat{\epsilon}(\hat{h})\)代表对于某个特定的假设\(\hat{h}\)的训练误差。根据一致收敛定理, 在\(1-\delta\)的概率下能保证泛化误差和训练误差相差在\(\gamma\)的范围内时, 即：
$$|\epsilon(h_i)-\hat{\epsilon}(h_i)| \leq \gamma$$
展开不等式：
$$-\gamma \leq \epsilon(h_i)-\hat{\epsilon}(h_i) \leq \gamma$$
根据右半边部分可以得到,\(\epsilon(h_i)\leq \hat{\epsilon}(h_i)+\gamma\),进而推出第一个不等式,这里的\(\hat{h}\)相当于上面的\(h_i\),因为\(h_i\)可以是任意属于假设空间的假设。
第二个不等式是因为根据上述定义的\(\hat{h}=\mathop{argmin}_\limits{h \in \mathcal{H}} \hat{\epsilon}(h)\),即在训练误差表现上，\(\hat{h}\)是表现最好的，没有任何其他的假设在训练误差上表现会更好，因此\(\hat{\epsilon}(\hat{h}) \leq \hat{\epsilon}(h^{*})\)。
最后一个不等式，仍然是根据一致收敛定理，根据上述绝对值不等式展开后的左半边部分，有:
$$\hat{\epsilon}(h_i) \leq \epsilon(h_i) + \gamma$$
使用\(h^{*}\)替换\(h_i\),则有：
$$\hat{\epsilon}(h^{*}) \leq \epsilon(h^{*}) + \gamma$$
进而可以推出第三个不等式。
下面将这些推论综合一下，我们得到一个定理：
令\(|\mathcal{H}|=k\),给定m和\(\delta>0\),那么至少有\(1-\delta\)的概率能否使下面公式成立:
$$\epsilon(\hat{h}) \leq \min_{h \in \mathcal{H}} \epsilon(h) + 2\sqrt{\frac{1}{2m} log \frac{2k}{\delta}}$$
该定理反映了在训练集上选择使训练误差最小的假设\(\hat{h}\)在泛化误差上的表现(\(\epsilon(\hat{h})\))受模型精确度和复杂度的影响，也就是反映了偏差和方差之间的权衡。可以想象，当选择一个复杂的模型假设时,\(|\mathcal{H}|=k\)会变大 ，导致不等式后的第二项变大，意味着方差变大；但是第一项也会相应的变小，因为使用一个更大的假设空间\(\mathcal{H}\)意味着可供选择的假设变多了，在多的那部分假设中可能存在使误差更小的假设，因此偏差就会变小。故应该选择一个最优值，使得偏差和方差之和最小，才能得到一个好的模型。
同样，该定理还有另外形式的推论：
令\(|\mathcal{H}|=k\)，给定\(\gamma,\delta>0\)，那么至少有\(1-\delta\)概率使得\(\epsilon(\hat{h}) \leq \min_\limits{h \in \mathcal{H}} \epsilon(h) + 2\gamma\)成立的前提是：
$$m \geq \frac{1}{2\gamma^2} log \frac{2k}{\delta}=O(\frac{1}{\gamma^2}log\frac{k}{\delta})$$
推广无限假设空间
上述讨论的是有限假设空间的情况。我们将其拓展到无限空间。
直观理解
先从一个简单的例子说起。假设我们的假设空间\(\mathcal{H}\)由d个实数参数表示。例如对于逻辑回归，如果有n个特征的话,就有d=n+1(多的一个是截距)个参数。因为计算机通常使用双精度64bit来表示double型数据。因此对于每个参数都有\(2^64\)种不同可能的取值，那么d个参数的话，不同排列组合有，\(2^{64} \times 2^{64} \times …\times 2^{64}\)种，共d个式子，即\(k=2^{64d}\)种不同的假设。为了满足在\(1-\sigma\)概率下，有\(\epsilon(\hat{h}) \leq \epsilon(h^{*})+2\gamma\),则：
$$m \geq \frac{1}{2\gamma^2} log \frac{2k}{\delta}=O(\frac{1}{\gamma^2}log\frac{2^{64d}}{\delta})=O(\frac{d}{\gamma^2} log \frac{1}{\gamma})=O_{\gamma,\delta}(d)$$
最后一个O代表对于给定的\(\gamma,\delta\)，即认为为常数的时候，所需要的样本个数应该和参数个数呈线性关系。
上述证明不够严格，下面进行更正式的表述。(具体证明不给出)
VC维
首先引入VC(Vapnik-Chervonenkis)维的概念。VC维是为了研究学习过程一致收敛的速度和推广性，由统计学理论定义的有关函数集学习性能的一个重要指标。
具体定义，对一个指示函数集，如果存在H个样本能够被函数集中的函数按所有可能的\(2^H\)种形式分开，则称函数集能够把H个样本打散(分开)；函数集的VC维就是它能打散的最大样本数目H。若对任意数目的样本都有函数能将它们打散,则函数集的VC维是无穷大，它可以将任意多样本的任意标注情况精确分开，即在训练集上达到100%的分类正确率。
我们可以看一下2维空间，对于3个样本而言：
共用8种可能(\(2^3\),任意一个样本可以在直线任意一侧)。可以发现都可以很好的分开，只要存在一种放置该8种可能的方式即可(例如如果选择同一直线的方式就不能打散，但是存在其他种不在同一直线上的8种方式可以进行打散)。我们再观察4个样本，都不能同时对\(2^4=16\)种标注进行打散，即不是所有的标注形式，都能找到一个假设来分散，因此VC维在二维线性分类器上等于3。推广至多维线性分类器上，VC维d=n+1(n为线性分类器参数个数,d为VC维)。
实际上对于无限假设空间，我们令该假设空间的VC维为d，即\(d=VC(\mathcal{H})\)。我们可以得到如下结论，在\(1-\delta\)概率下,对于所有的\(h \in \mathcal{H}\),都有：
$$|\epsilon(h)-\hat{\epsilon}(h)| \leq O\left(\sqrt{\frac{d}{m} log \frac{m}{d} + \frac{1}{m} log \frac{1}{\delta}}\right)$$
同样，我们可以推出，在\(1-\delta\)概率下：
$$\epsilon(\hat{h}) \leq \epsilon(h^{*}) + O\left(\sqrt{\frac{d}{m} log \frac{m}{d} + \frac{1}{m} log \frac{1}{\delta}}\right)$$
换句话说，如果某个假设空间有有限的VC维，那么当m变大的时候，一致收敛会发生。
进而得出m大小的推论，对于给定的\(\gamma,\delta>0\),在\(1-\delta\)概率下保证\(\epsilon(\hat{h}) \leq \epsilon(h^{*})+2\gamma\)，则:
$$m=O_{\gamma,\delta}(d)$$
最后得出结论，对于一个目标是使训练误差最小的算法而言，需要的样本数量和假设空间的VC维大小呈线性关系，实际上VC维可以理解为假设空间参数的数目,即对大多数模型而言，VC维和模型参数的数目呈正比关系。
拓展：VC维解释SVM
根据上一篇文章我们知道，SVM通过核函数将数据映射到高维空间，模型复杂度增加，那么相应的，其VC维应该变大，要达到较好的效果所需的数据应该增大才对。但SVM只在原数据上就达到了比其他模型更优的结果，为什么呢？
虽然SVM将数据映射到高维空间，但是其仍然有最大间隔分类器的假设，而对于最大间隔分类器来说，其VC维并不依赖X的维度.对于最小间隔为\(\gamma\)的分类器而言，令\(||x^{(i)}||_2 \leq R\),即采样点在半径为R的圆内。那么:
$$VC(H) \leq \left \lceil \frac{R^2}{4\gamma^2} \right\rceil + 1$$
SVM算法会自动寻找一个具有较小VC维的假设，这样反而降低了VC维，使得原来的数据量就相对足够充分(\(m \propto O(d)\))，因此不影响模型的效果。
ERM的直观意义
ERM即经验风险最小化，有公式：
$$\hat{\epsilon}(h)=\frac{1}{m} \sum_{i=1}^m I\{h(x^{(i)}) \not= y^{(i)}\}$$
我们以单个样本为例，其误差函数为\(I\{h(x^{(i)}) \not= y^{(i)}\}\),很显然，这是一个非凸函数，使用机器学习的方法并不能很好的对其进行优化。因而产生了一些算法对该误差函数进行凸性近似，以期能够更好的优化，以svm和logistic为例，如图2所示：
如上图，logistic模型采用极大似然估计方法，它尝试令负的对数似然最小，即，\(-log P(y^{(i)}|x^{(i)};\theta)\),因而如图2中的曲线所示。SVM使用的是大间隔概念，即不仅仅考虑\(\theta^T x\)大于0,更严格的跟1或者-1比较。可以根据下图理解：
上图可以令负样本的\(y^{(i)}=-1\),这样就可以利用函数间隔概念统一化。
因此虽然logistic和svm都不是直接的ERM算法，但基于对ERM的近似而产生，因而可见，ERM的一致性定理在实际中的威力。
