0 引论
0.1 什么是机器学习
机器学习是人工智能的一个分支。人工智能的研究是从以“推理”为重点到以“知识”为重点，再到以“学习”为重点，一条自然、清晰的脉络。显然，机器学习是实现人工智能的一个途径，即以机器学习为手段解决人工智能中的问题。机器学习在近30多年已发展为一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。机器学习算法是一类从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。因为学习算法中涉及了大量的统计学理论，机器学习与推断统计学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。很多推论问题属于无程序可循难度，所以部分的机器学习研究是开发容易处理的近似算法。 一种经常引用的英文定义是：
A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.
0.2 什么时候需要机器学习
什么时候需要机器学习，而不是直接手动编程完成任务？在指定的任务中，程序是否能在“经验”的基础上自我学习和提升，有两个方面的考量：问题本身的复杂性和对自适应性的需要。
- 过于复杂的编程任务
- 动物/人可执行的任务：虽然人类可以习惯性的执行很多任务，但是反思我们如何完成任务的内省机制还不够精细，无法从中提取一个定义良好的程序。汽车驾驶、图像识别、语音识别属于此类任务。面对此类任务，只要接触到足够多的训练样本，目前最先进的机器学习程序就能达到比较满意的效果。
- 超出人类能力的任务：受益于机器学习技术，另一大系列任务都涉及对庞大且复杂的数据集进行分析：天文数据，医疗档案，气象预报，基因组数据分析，搜索引擎，电子商务……随着越来越多的数据出现，显而易见的是，隐藏其中的信息变得过于庞大复杂，超出人类理解能力。学习在大量复杂数据中发现有意义的模式是一个有前途的领域，无限内存加上不断提高的处理速度，为此领域开辟新的视野。
- 自适应性 编程的局限之一是其刻板性——一旦程序编写安装完成，它将保持不变。但任务和用户都是岁时间不断变化的。机器学习方法为此提出解决方案。机器学习天生具备自适应于互动环境变化的性质。
0.3 学习的种类
机器学习根据学习任务分为不同子类，这里给出一个粗略分类。 
- 监督与无监督：学习涉及学习器与环境之间的互动，可据互动性质划分学习任务。首先关注有监督和无监督的区别。监督学习是这样的一种场景：经验是包含显著信息的训练数据，“测试数据”缺少这些显著信息，但可以从学到的“技能”中获取。此种情况下，获得的“技能”旨在预测测试数据的丢失信息，可将环境看做通过提供额外信息（标签）来“监督”学习器的老师。然而，无监督学习的训练数据和测试数据之间没有区别。学习器处理输入信息的目标是提取概括信息（浓缩数据）。类聚（相似数据归为一类）是执行这样任务的典型例子。还有一种中间情况，训练数据比测试数据包含更多的信息，也要求学习器预测更多的信息。例如，当学习数值函数判断国际象棋游戏中黑棋和白棋谁更有利时，训练过程中提供给学习器的唯一信息是，谁在整个实际的棋牌类游戏中最终赢得那场比赛的标签。这种学习叫做强化学习。
- 主动学习器与被动学习器：学习可以根据学习器扮演的不同角色分为“主动”和“被动”学习器。主动学习器在训练时通过提问过实验的方式和环境交互，而被动学习器只观察环境（老师）提供的信息而不去影响或引导它。例如，垃圾邮件过滤任务通常是被动学习——等待用户标记电子邮件。而在主动学习中，要求用户来标记学习器挑选的邮件，以提到学习器对“垃圾邮件是什么”的理解。
- 老师的帮助：人类的学习过程中往往会有一个良师，向学习者传输最有用的信息以实现学习的目标。相比之下，科学家研究自然时，环境起到了老师的作用。环境的作用是消极的——苹果坠落、星星闪烁、雨点下落从不考虑学习者的需求。在对这种学习情境建模时，我们假定训练数据是随机产生的，这是统计机器学习的一个基本构成单元。此外，学习也发生在学习者的输入是“对立老师”提供的。垃圾邮件过滤任务和欺诈学习任务就是这种情况。
- 在线与批量：在线响应还是处理大量数据之后才获得技能，是对学习器分类的另一个方法。举个例子，股票经纪人必须基于当时的经验信息做出日常决策。随着时间推移，他或许会成为专家，但是也会犯错误并付出高昂的代价。相比之下，在大量的数据挖掘任务中，学习器，也就是数据挖掘器，往往是在处理大量训练数据之后才输出结论。
1 简单入门
让我们从相对简单的设定开始，用数学分析展示如何取得成功的学习。加入你刚刚到达太平洋上的一个小岛，木瓜是当地主要的饮食，而你从来没有吃过木瓜。你必须学会判断市场上卖的瓜是否好吃。首先，你选择根据木瓜的哪些性质进行判断。基于你之前选择其他水果的经验，你决定利用以下两个特征：木瓜的颜色（范围从暗绿色、橘黄色、红色到深棕色）、木瓜的软硬程度（范围从岩石般坚硬到浆糊般柔软）。为了获得对木瓜的判断，你的输入样本由一下属性决定：a.观测得到木瓜颜色和软硬程度b.亲口品尝确定好不好吃。 
第一个步骤就是描述一个能够刻画类似任务的形式化模型。
1.1 一般模型——统计学习理论框架
1.1.1 学习器的输入
在基础的统计学设定中，学习器应该接触以下概念：
- 领域集(domain set)：一个任意的集合$\mathcal{X}$。这个集合中的实例是我们希望能够为其贴上标签的。例如，在木瓜学习问题中，领域集为所有木瓜的集合。这些集合中的元素通常用能够表征其特征的向量表示。我们也把领域集中的元素叫做实例，相应的，$\mathcal{X}$ 被称为实例空间。
- 标签集(label set)：就目前讨论的内容来说，我们将标签集限定为一个二元集合，通常为${0,1}$或者${-1,+1}$。令$\mathcal{Y}$为集合中可能的标签。对应于木瓜的例子，假定标签集$\mathcal{Y}$为${0,1}$，$其中$1$代表木瓜好吃，$0$代表木瓜难吃。
- 训练数据(training data)：$S={(x_1,y_1),\cdots,(x_m,y_m)}$为一个有限的序列，序列中元素以$\mathcal{X}\times\mathcal{Y}$形式成对出现。也就是说，训练集是一个由带标签的领域集元素组成的序列。这个输入数据是学习器能够接触到的。这些带标签的样本通常成为训练样本，有时称$S$为训练集。
-
1.1.2 学习器的输出
要求学习器输出一个预测规则(prediction rule)，$h:\mathcal{X}\to\mathcal{Y}$。该函数也被成为预测器(predictor)、假设(hypothesis)或分类器(classifier)。这个预测器可以预测一个新的领域的元素的标签。在木瓜的例子中学习器预测规则用来预测木瓜是否好吃。我们用$A(S)$来表示学习算法$A$在给定预测序列$S$的情况下返回的假设。
1.1.3 一个简单的数据生成模型
首先假设实例（对应于木瓜）根据某些概率分布$\mathcal{D}$（对应于岛上环境）采样获得。必须注意的是，我们并不需要学习器知道此概率分布的任何信息。对于我们的学习任务来说，$\mathcal{D}$可以为任意的概率分布。我们假设存在一些“正确的”标记函数$f:\mathcal{X}\to\mathcal{Y}$，使得对于任意的$i$，$y_i=f(x_i)$。对于学习器来说，该“正确”标记函数是未知的。实际上，指出每个样本的正确标签正是学习器需要完成的任务。综上，训练序列$S$中每一对训练数据的产生过程是：首先根据概率分布$\mathcal{D}$采集样本点$x_i$，然后利用“正确”标记函数$f$为其赋予标签。
1.1.4 衡量成功
分类器误差定义为：未能成功预测随机数据点正确标签的概率（随机数据点是从之前提到的潜在概率分布中生成的）。也就是说，$h$的误差是$h(x)\neq f(x)$的概率，其中$x$是根据分布$\mathcal{D}$采集的随机样本。
形式上，给定一个领域子集(domain subset)$A\subset\mathcal{X}$，概率分布$\mathcal{D}$，$D(A)$确定了能够观察到$x\in A$的概率。很多情况下，称$A$为一个事件，将其表达为一个函数$\pi:\mathcal{X}\to{0,1}$，也就是说，$A={x\in\mathcal:\pi(x)=1}$。这种情况下，也用$\mathbb{P}_{x\thicksim\mathcal{D}}[\pi(x)]$来表示$\mathcal{D}(A)$。 预测准则($h:\mathcal{X}\to\mathcal{Y}$)的错误率定义为：
\[L_{\mathcal{D},f}(h) \overset{\rm def}{=} \mathbb{P}_{x\thicksim\mathcal{D}}[h(x)\neq f(x)] \overset{\text{def}}{=}\mathcal{D}(\{x:h(x)\neq f(x)\})\tag{1.1}\]也就是说$h$的误差是随机选择一个样本$x$，使得$h(x)\neq f(x)$的概率。下标$(\mathcal{D},f)$说明误差的测量基于概率分布$\mathcal{D}$和正确的标记函数$f$。$L_{\mathcal{D},f}(h)$也称为泛化误差、损失或者$h$的真实误差。
1.1.5 学习器可能接触到的信息
对于分布$\mathcal{D}$和标记函数$f$，学习器是未知的。
1.2 经验风险最小化
学习算法的目标是求出一个最小的预测器$h_S:\mathcal{X}\to\mathcal{Y}$（下标$S$说明输出的预测器是基于训练集$S$的）使得关于未知分布$\mathcal{D}$和$f$的预测误差最小化。 由于学习器不知道分布$\mathcal{D}$和标记函数$f$，所以无法直接获得真实误差。学习器能够计算出来的一个有用的概念是训练误差——分类器在训练样本中的误差：
\[L_S(h) \overset{\rm def}{=}\frac{|\{i\in[m]:h(x_i)\neq y_i\}|}{m} \tag{1.2}\]其中$[m]={1,\cdots,m}$。 术语经验误差或经验风险对于该误差通常可以互换使用。
对于学习者来说，训练样本是真实世界的一个缩影，故利用训练集来寻找一个对于数据的可行解是合理的。这些学习范例——从预测器$h$出发到最小化$L_S(h)$——称为经验风险最小化，简称ERM。
1.2.1 可能出现的失误——过拟合
尽管ERM规则看起来顺理成章，但是如果不小心，这种方法可能遭遇惨败。 如下图，基于软硬程度和颜色预测味道的学习问题： 
假设概率分布$\mathcal{D}$使得实例（木瓜）在如上图所示的正方形中均匀分布。标记函数$f$决定了如果实例出现在正方形内部就标记为$1$，否则为$0$.图中大正方形面积为$2$，虚线正方形面积为$1$。对于如下预测器：
显然，无论样本是什么，$L_S(h_S)=0$，因此预测器可能会选择一种ERM算法（这是一种经验最小假设，没有分类器会比这种假设有更小的误差）。另一方面，分类器通过有限个数的实例来预测标记为$1$的真实误差，本例中为$1/2$，于是$L_{\mathcal{D}}=1/2$。我们发现一个预测器在训练集上效果非常优秀，但在真实世界中极为糟糕，这种现象叫做过拟合。直观上，过拟合发生在当假设对于训练集契合地“太好了”（也许正如我们日常生活中的经验一样：一个人如果能对自己的每一个行为都能作出完美的解释，那么这个人是容易令人产生怀疑的）。
1.3 考虑归纳偏置的经验风险最小化
我们刚刚证明了ERM规则容易导致过拟合。与其放弃它，不如修正它，我们的寻找ERM不会过拟合的条件，使其在训练集上有不错的表现，也有较大的可能性在潜在的数据分布下表现良好。 通常的解决方案是在一个受限的搜索空间中使用ERM学习准则。形式上，一个学习器应该提前选择（在接触到数据之前）一个预测器的集合。这个集合成为假设类，记为$\mathcal{H}$。每一个$h\in\mathcal{H}$是从$\mathcal{X}$映射到$\mathcal{Y}$的一个函数。对于给定的假设类$\mathcal{H}$和一训练样本集$S$，ERM$_{\mathcal{H}}$学习器根据在$S$上的最小化概率误差，利用ERM规则选择一个预测器$h\in\mathcal{H}$。形式如下：
\[\text{ERM}_{\mathcal{H}}(S)\in \underset{h\in\mathcal{H}}{\rm argmin}L_S(h)\]通过限制学习器从$\mathcal{H}$中选择预测器，我们的选择偏向于一个特别的预测器集合，这种限制通常叫做归纳偏置。一位这种选择决定于学习器接触训练数据之前，所以它应该基于学习问题的一些先验知识。 在机器学习中，一个基本的问题是：选择哪种假设类ERM$_{\mathcal{H}}$不会导致过拟合。
1.3.1 有限假设类
对于一个类来说，最简单的一种限制是限定其势的上界。本节说明如果$\mathcal{H}$是有限类，ERM$_{\mathcal{H}}$将不会过拟合，前提是拥有足够多的训练样本（其大小依赖于假设类$\mathcal{H}$的势）。
我们分析ERM${\mathcal{H}}$在有限假设$\mathcal{H}$下的表现。对于一个训练样本$S$，利用某些标记函数$f:\mathcal{X}\to\mathcal{Y}$为其贴上标签。设$h_S$为对$S$利用ERM${\mathcal{H}}$得到的结果，也就是说
\[h_S\in \underset{h\in\mathcal{H}}{\rm argmin}L_S(h)\tag{1.4}\]我们先作出如下假设（这些假设在后面将会放宽）。
定义 1.1（可实现性假设）存在$h^\in\mathcal{H}$，使得$L_{\mathcal{D},f}(h^)=0$，注意，这个假设意味着对于任意的随机样本集$S$（其中$S$的实例是根据分布$\mathcal{D}$随机选取的，其标签由$f$决定)以概率$1$使得$L_S(h^*)=0$。
可实现性假设意味着对于每个ERM假设，我们有$L_S(h_S)=0$。然而对于经验风险来说，我们更感兴趣于$h_S$的真实风险$L_{\mathcal{D},f}(h_S)$。 显然，对于一个只能接触到样本集$S$的算法来说，关于潜在分布$\mathcal{D}$的任何误差保证都必须依赖于$S$和$\mathcal{D}$之间的关系。在统计机器学习中最通常的假设是$S$中训练样本是从$\mathcal{D}$中独立同分布的抽取的，形式上，
独立同分布(i.i.d.)假设：训练集中的样本根据分布$\mathcal{D}$独立同分布。
也就是说，$S$中每一个$x_i$采样于$\mathcal{D}$，然后根据标记函数$f$确定其标签。记为$S\sim\mathcal{D}^m$，其中$m$为$S$的势，$\mathcal{D}^m$表$m$-组的概率，对于$m$-组的每一个元素，都是独立于组中其他元素而从$\mathcal{D}$中独立抽取的。
直观上，训练集$S$是一个学习器从整体数据分布$\mathcal{D}$和标记函数$f$中获取的部分信息，是使得学习器接触到外部世界的一个窗口。训练样本越大，越能正确反映数据分布和标记函数。 由于$L_{\mathcal{D},f}(h_S)$依赖于训练集$S$，而训练集通过一个随机过程采样，因此通过风险$L_{\mathcal{D},f}(h_S)$来选择预测器$h_S$也存在随机性，这就是所谓的随机变量。学习器试图通过完全确定的$S$来确定一个好的分类器（从观测$\mathcal{D}$的角度说），这种想法是不切实际的，因为总有一定的概率使得训练数据中有一些对于分布$\mathcal{D}$来说完全不具有代表性。因此，在$L_{\mathcal{D},f}(h_S)$不太大的情况下，我们处理训练样本的采样概率。一般来说，我们将采样到非代表性样本的概率表示为$\sigma$，同时$1-\sigma$在预测中称为置信参数。
| 由于无法保证标签预测绝对正确，引入另一个参数来评价预测的质量，称为精度参数(accuracy parameter)，记为$\epsilon$。如果$L_{\mathcal{D},f}(h_S)>\epsilon$则是一个失败的预测。因此（固定一些标记函数$f:\mathcal{X}\to\mathcal{Y}$），设定学习器对$m$-组实例采样失败的概率上界，形式上，设$S | _x=(x_1,\cdots,x_m)$为训练实例集，其上界为 |
设$\mathcal{H}_B$为差的假设集合，也就是
\[\mathcal{H}_B=\{h\in\mathcal{H}:L_{\mathcal{D},f}(h_S)>\epsilon\}\]此外，设
\[M=\{S|_x:\exists h\in\mathcal{H}_B,L_S(h)=0\}\]| 为一个样本的误导集：对于所有的$S | x\in M$，存在一个“差”的假设$h\in\mathcal{H}_B$，使其看上去像是一个“好”的假设。现在回顾对$L{\mathcal{D},f}(h_S)>\epsilon$的概率限制，因为假设的可实现性意味着$L_S(h_S)=0$，所以只有当$h\in\mathcal{H}B,L_S(h)=0$时，$L{\mathcal{D},f}(h_S)>\epsilon$才会出现。换句话说，这种情况发生的充分必要条件是样本处于误导集$M$中。形式上，将其表示为 |
注意，$M$可以写为
\[M=\underset{h\in\mathcal{H}_B}{\cup}\{S|_x:L_S(h)=0\}\tag{1.5}\]因此，
\[\mathcal{D}^m(\{S|_x:L_{\mathcal{D},f}(h_S)>\epsilon\})\le\mathcal{D}^m(M)=\mathcal{D}^m(\underset{h\in\mathcal{H}_B}{\cup}\{S|_x:L_S(h)=0\})\tag{1.6}\]利用联合界对(1.6)式右边进行限制
引理1.2（联合界） 对于任意集合$A$，$B$以及分布$\mathcal{D}$，有 \(\mathcal{D}(A\cup B)\le\mathcal{D}(A)+\mathcal{D}(B)\)
得到
\[\mathcal{D}^m(\{S|_x:L_{\mathcal{D},f}(h_S)>\epsilon\})\le\sum_{h\in\mathcal{H}_B}\mathcal{D}^m(\{S|_x:L_S(h)=0\})\tag{1.7}\]固定某“差”假设$h\in\mathcal{H}_B$。$L_S(h)=0$等同于$\forall i,h(x_i)=f(x_i)$。由独立同分布假设，我们得到
\[\begin{multline} \mathcal{D}^m(\{S|_x:L_S(h)=0\})=\mathcal{D}^m(\{S|_x:\forall i,h(x_i)=f(x_i)\})\\ =\prod_{i=1}^{m}\mathcal{D}(\{x_i,h(x_i)=f(x_i)\})\tag{1.8} \end{multline}\]对于训练集中每一个独立的样本有
\[\mathcal{D}(\{x_i,h(x_i)=f(x_i)\})=1-L_{\mathcal{D},f}(h)\le1-\epsilon\]其中，最后一项由$h\in\mathcal{H}_B$得。结合(1.8)，利用$1-\epsilon\le e^{-\epsilon}$可得，对于所有的$h\in\mathcal{H}_B$
\[\mathcal{D}^m(\{S|_x:L_S(h)=0\})\le(1-\epsilon)^m\le e^{-\epsilon m} \tag{1.9}\]推论1.3 设$\mathcal{H}$为一个有限假设类，$\sigma\in(0,1)$，$\epsilon>0$，$m$为一个整数，以下不等式成立 \(m\ge\frac{\log(|\mathcal{H}|/\sigma)}{\epsilon}\) 从而对于任何标记函数$f$，任何分布$\mathcal{D}$，可实现性假设（即对某些$h\in\mathcal{H}$，$L_{\mathcal{D},f}(h)=0$）保证在独立同分布的样本集$S$上（$S$的势为$m$）最少以$1-\sigma$的概率，对每个ERM假设$h_S$，有以下不等式成立 \(L_{\mathcal{D},f}(h_S)\le\epsilon\)
上述推论告诉我们：对于足够大的$m$来说，由ERM$_\mathcal{D}$规则生成的有限假设类将会以概率（置信度为$1-\sigma$）近似（误差上界为$\epsilon$）正确。
2 一般学习模型
2.1 PAC学习理论
前面已经指出，在经验风险最小化的规则下，对于一个有限假设类，如果有足够多的训练样本，那么输出的假设类是概率近似正确的。现在定义概论近似正确(PAC)学习。
定义 2.1(PAC可学习) 若存在一个函数$m_\mathcal{H}:(0,1)^2\to\mathbb{N}$和一个学习算法，使得对任意$\epsilon,\sigma\in(0,1)$和$\mathcal{X}$上的任一分布$\mathcal{D}$，任意的标记函数$f:\mathcal{X}\to(0,1)$，如果在$\mathcal{H}$，$\mathcal{D}$，$f$下满足可实现的假设，那么当样本数量$m\ge m_\mathcal{H}(\epsilon,\sigma)$时，其中样本由$\mathcal{D}$独立同分布采样得到并且由函数$f$标记，算法将以不小于$1-\sigma$的概率返回一个假设类$h$，使该假设类满足$L_{\mathcal{D},f}\le\epsilon$。
概率近似正确可学习性的定义包含两个近似参数。准确度参数$\epsilon$表征输出的分类器和最优分类器之间的距离（对应于PAC的”近似正确“部分），置信参数$\sigma$表征分类器达到准确要求的可能性（对应于PAC的“概率”部分）。在我们所研究的数据访问模型中，这些近似是不可避免的。由于训练集是随机生成的，因此始终有可能发生样本不提供信息的小概率事件的情况。更进一步，即使我们足够幸运能够得到一个训练样本，它能够很好地代表$\mathcal{D}$，由于这是一个有限样本，因此$\mathcal{D}$的许多细节依然不能反映出来。准确度参数$\epsilon$允许让学到的分类器出现小错误。
2.1.1 采样复杂度
函数$m_{\mathcal{H}}:(0,1)^2\to\mathbb{N}$决定学习假设类$\mathcal{H}$的采样复杂度：保证一个概率近似正确解所需的样本数量。采样复杂度是准确度参数$\epsilon$和置信参数 $\sigma$ 的一个函数。采样复杂度也依赖于假设类$\mathcal{H}$的属性—— 比如， 对于一个有限假设类， 我们发现采样复杂度依赖于假设类$\mathcal{H}$势的对数形式。
如果假设类$\mathcal{H}$是 PAC 可学习的， 有很多函数$m_{\mathcal{H}}$满足 PAC 可学习定义给出的条件。因此， 为了更加精确， 我们定义假设类$\mathcal{H}$的采样复杂度为最小函数， 即对于任意的$\epsilon$和 $\sigma$，$m_{\mathcal{H}}(\epsilon,\sigma)$是满足 PAC 可学习条件的最小整数。
回顾上一章介绍的有限假设类的分析及结论。可以重新表述为：
引理 2. 2 任一有限假设类是 PAC 可学习的 ，其采样复杂度满足 \(m_{\mathcal{H}}(\epsilon,\sigma)\le\left[\frac{\log(|\mathcal{H}|)}{\epsilon}\right]\) 也存在无限假设类是可学习的 。随后， 我们会给出“决定一个类是否是 PAC 可学习的” 不是假设类的势有限还是无限 ， 而是根据一种名叫 VC 维的组合测度。
2.2 更常见的学习模型
前面给出的模型很容易加以推广， 可以和更广的学习任务相关联 。我们考虑两种形式的泛化：
-
去掉可实现假设 我们的学习算法在分布为$\mathcal{D}$和标记函数为 $f$上学习成功， 是基于可实现假设的前提。对于实际的任务，这种假设可能太严格了（我们真的能保证存在一个矩形区域，它完全决定哪些木瓜是好吃的？）。下一节会给出不可知 PAC 模型， 将可实现假设去掉。
-
学习问题不只是二分类问题 到目前为止 ， 我们 讨论的还是给定一个样本预测二值标号（比如好吃还是不好吃）。然而， 有许多其他形式的学习任务。例如， 假设预测一个实值数字（明天晚上 9 点的气温）或从一个有限标号集里面选出 一个标号（例如明天报纸头条的主题）。研究证明我们可以定义各种损失函数来将学习推广 。这部分内容会在 2. 2. 2 节介绍。
2.2.1 放宽可实现假设——不可知 PAC 学习
- 一种更实际的数据生成分布模型
-
可实现假设要求存在一个 $h^\in\mathcal{H}$使得$\mathbb{P}_{x\sim\mathcal{D}}[h^(x)=f(x)]=1$。在很多实际问题中， 这种假设并不成立。此外， 最好不要假设标记完全由我们假 定的特征决定（在木瓜的例子中，两个相同颜色相同软硬程度的木瓜味道有可能并不相同）。接下来 ，我们放宽 可实现的假设， 把“目标标记函数”替 换为更灵活的概念一一数据标记生成分布。
| 从现在起， 在形式上， 将$\mathcal{D}$定义为$\mathcal{X}\times\mathcal{Y}$上的概率分布， 和之前 一样， 其中$\mathcal{X}$为定义域，$\mathcal{Y}$为标签集合（一般我们认为$\mathcal{Y}= {O , 1 }$ )。即$\mathcal{D}$是定义域和标签集上的联合分布。我们可以将该分布分解为两部分：未标记定义域点的概率分布$\mathcal{D}_x$（也称为边缘分布）和每个定义 域点标记的条件概率分布织 $\mathcal{D}((x,y) | x)$。在木瓜的例子中 ，$\mathcal{D}_x$决定碰到一个木瓜（其颜色和软硬程度落在某一 范围内）的概率， 条件概率表示 $x $ 所表示的颜色和软硬程度对应的木瓜好吃的概率。在这种情况下， 确实存在相同颜色和软硬程度的木瓜分属不同类的情况。 |
- 改进后的经验误差和真实误差 对于$\mathcal{X}\times\mathcal{Y}$上的概率分布$\mathcal{D}$, 根据分布$\mathcal{D}$随机生成的带标签的数据点， 我们可以测扯假设$h$ 犯错的可能性。我们重新定 义预测器 $h $的真实误差（或风险）为
我们想要找到一个预测器$h$ , 使得上述误差最小化。然而， 学习器并不知道数据生成分布$\mathcal{D}$。学习器知道的是训练数据 $S$。经验风险依旧是原来定义的形式 ，即
\(L_S(h) \overset{\rm def}{=}\frac{|\{i\in[m]:h(x_i)\neq y_i\}|}{m} \tag{1.2}\) 给定 $S$ , 对于任何的函数$h:X\to{ 0,1}$, 学习器都可以计算$L_S(h)$。注意，$L_S(h)=L_{\mathcal{D}}(h)$（在$S$均匀分布） 。
-
目标
我们想要找到假设$h:\mathcal{X}\to\mathcal{Y}$, 使得真实风险$L_{\mathcal{D}}(h)$最小。 -
贝叶斯最优预测器
给定$\mathcal{X}\times{0,1}$上的任意概率分布$\mathcal{D}$, 将$\mathcal{X}$映射到${0,1}$的最好的预测器是
很容易验证, 对于任意的概率分布$\mathcal{D}$, 贝叶斯最优分类器$f_\mathcal{D}$是最优的，其他的分类器$g$，$L_\mathcal{D}(f_\mathcal{D})\le L_\mathcal{D}(g)$没有更低的错误率。即对任意的分类器$g$，$L_\mathcal{D}(f_\mathcal{D})\le L_\mathcal{D}(g)$。
可惜， 我们不知道概率分布 $\mathcal{D}$ , 不能使用这个最优分类器 $f_\mathcal{D}$ 。学习器只能获取训练样本。我们现在给出不可知 PAC 可学习的正式定义 ， 很自然地将 PAC可学习推广到更现实的情况， 就如之前讨论的， 假定不可实现。
很明显， 我们不能期望学习算法给出 一个假设， 其误差小于最小可能的误差 ， 即贝叶斯分类器的误差。我们在之后会给出证明 ， 如果对数据生成分布不做先 验假设， 没有算法能够保证找到一个和贝叶斯最优分类器一样好的预测器。我们希望学习算法能够找到 一个预测器， 其误差和给定假设类中最好预测器的误差相 差不大。当然， 这种要求的强度取决于假设类的选取。
定义 2. 3( 不可知 PAC 可学习） 若存在 一个函数$m_\mathcal{H}:(0,1)^2\to\mathbb{N}$ 和一个学习算 法$A$, 使得对于任 意$\epsilon,\sigma\in(0,1)$和$\mathcal{X}\to\mathcal{Y}$上的任 一分布 $\mathcal{D}$ , 当样本数量$m\ge m_\mathcal{H}(\epsilon,\sigma)$ 时，其中样本由分布 $\mathcal{D}$ 独立同分布采样得到 ．算法将以不 小于 $1 -\sigma$ 的概 率返回一 个假设类 $h$ , 使该假设类$h$ 满足 \(L_\mathcal{D}(h)\le\underset{h'\in\mathcal{H}}{\min}L_\mathcal{D}(h')+\epsilon\)
很明显， 如果满足可实现假设 ， 不可知 PAC学习和PAC 学习给出了相同的保证 。这样看来， 不可知 PAC 学习是PAC学习的一种泛化。当不满足可实现的假设时 ， 学习器是不能保证任意小的误差的 。然而， 在不可知 PAC 学习的定义下， 即使和假设类 中最好的分类器有些许差距， 学习器依然可以 认为学习成功。而 PAC 学习要求学习器学到的分类器， 其误差达到一个很小的绝对值， 而且和假设类可达到的最小误差没有关系 。
2.2.2 学习问题建模
接下来， 我们将模型进 一步拓展， 使之能应用到更广的学习任务中。让我们来看一些其他学习任务。
- 多分类 我们的分类问题不再是 二分类问题。比如文本分类问题： 我们希望设计一个程序， 能够将文档按其主题进行分类（比如 ， 新闻、体育、生物、 医学）。对于这类任务，学习器需要根据已有的正确分类的文档，生成一个程序，对新文档给出其相应的主题。我们可以将文档用 一系列的特征来表示， 特征可以是文档中不同关键词出现的频数， 或者其他相关的特征（比如文档的大小及来源）。在这个任务里 ， 标签集是所有可能的主题的集合$\mathcal{Y}$可以是任意 大的有限集）。一旦我们定义了定 义域和标签集，主体框架的其他部分和木瓜例子看起来很相似；我们的训练样本是有限的序列（特征向量， 标签）对， 学习器输出一个从定义域到标签集的函数 ， 最后， 为了测试学习是否成功， 我们可以用分类器给出错误 标签的概率来表示。
- 回归问题 在这类问题中， 希望找到数据的 简单模型——数据$\mathcal{X}$和$\mathcal{Y}$之间的关联函数。比如， 希望找到一个线性函数， 根据超声波检测到的婴儿头围 、腹围和股骨长度， 能够最好地预测出婴儿出生时的体重 。在这里， 定义域$\mathcal{X}$是$\mathbb{R}^3$（三个超声 波检测量）的一个子集， 标签集$\mathcal{Y}$是实数集（以克为单位的体重）。在此语境下， 称为目标集更为合适 。这就是我们的训练数据和输出（有限序列$(x,y)$ 对， 从$\mathcal{X}$到$\mathcal{Y}$的映射函数）。然而， 度批是否成功的标准不再和之前 一样。我们可以用 期望 平方差来 评估假设函数$h:\mathcal{X}\to\mathcal{Y}$给出的预测值和真实值之间的差异 ， 即
为了满足各式各样的学习任务．我们将学习是否成功的度量进行如下泛化：
- 广义损失函数 给定任意集合 $\mathcal{H}$( 相当千我们的假设类或模型）和定义域$Z$，令$l$为$\mathcal{H}\times Z$到非负实数的一个映射函数，$l:\mathcal{H}\times Z\to\mathbb{R}_+$ 。 我们称这种函数为损失函数。 需要注意， 对于预测问题， 有$Z=\mathcal{X}\times\mathcal{Y}$。然而， 我们定义的损失函数已经超出了预测任务的范畴， 因此可以允许$Z$可以是任意形式的定义域（比如 ， 在无监督学习问题中，$Z$不再是实例空间和标签集的乘积形式）。
我们现在定 义损失函数为分类器的期望损失 ，$h\in\mathcal{H}$, Z 上的概率分布为$\mathcal{D}$, 即
\[L\mathcal{D}(h)\overset{\rm def}{=}\underset{z\sim\mathcal{D}}{\mathbb{E}}[l(h,z)]\tag{2.3}\]也就是说， 目标$z$ 是从分布$\mathcal{D}$上随机采集到的 ， 我们考虑假设类 $h$ 在目标$z$的期望损失。与之类似 ， 可以定义经验风险为给定数据集 $S = ( z_1,\cdots,z_m)\in Z^m$上的期望损失， 即
\[L_S(h)\overset{\rm def}{=}\frac{1}{m}\sum_{i=1}^{m}l(h,z)\tag{2.4}\]前面的分类和回归问题的损失函数采用的是下述形式：
- $0-1$损失： 在这里， 随机变量 $z$ 取值序列对集合$\mathcal{X}\times\mathcal{Y}$, 损失函数为
这类损失函数用在二分类或多分类问题中。
需要注意的是， 对于随机变量$a$ , 取值为${0 , 1 }$，$\mathbb{E}{\alpha\sim\mathcal{D}}[\alpha]=\mathbb{P}{\alpha\sim\mathcal{D}}[\alpha=1]$ 。因此， 对于这类损失函数 ， 式( 2. 1 ) 和式( 2. 3 ) 给出的$L_\mathcal{D}(h)$是一致的。
- 平方损失 ： 在这里， 随机变最$z$ 取值序列对集合$\mathcal{X}\times\mathcal{Y}$， 损失函数为
这类损失函数用在回归问题中。 我们会在后续看到很多这类损失函数的实例 。 总结一下，我们正式定义广义损失函数下的不可知 PAC 学习。
定义 2. 4( 广义损失函数下的不可知 PAC 可学习） 对于集合 $Z$ 和损失函数$l:\mathcal{H}\times Z\to\mathbb{R}+$ ， 若存在一 个函数$m\mathcal{H}:(0,1)\to\mathbb{N}$和一个学习算 法， 使得对于任 意$\epsilon,\sigma\in(0,1)$，以及 $Z$ 上的任一分布$\mathcal{D}$， 当样本数量$m\ge m_\mathcal{H}(\epsilon,\sigma)$时， 其中样本由分布 $\mathcal{D}$独立同分布采样得到， 算法将以不小于 $1-\sigma$的概率返回一个假设类 $h$, 使该假设 类 $h$ 满足
\[L_\mathcal{D}(h)\le\underset{h'\in\mathcal{H}}{\min}L_\mathcal{D}(h')+\epsilon\]
其中$L_\mathcal{D}(h)=\mathbb{E}_{z\sim\mathcal{D}}[l(h,z)]$。
评注（关于可量测性） 在前面的定义中， 对于任意的$\mathcal{H}$ ， 我们将$l(h,\cdot):\mathcal{H}\times Z\to\mathbb{R}+$视为随机变量 ， 定义$L\mathcal{D}(h)$为该随机变量的期望值。因此， 我们需要要求$l(h,\cdot)$是可测量的。形式上， 我们假定存在一个 $Z$ 的$\sigma$ - 代数子集， 以及其上的概率分布$\mathcal{D}$, $\mathbb{R}_+$的每个分割的原像在这个$\sigma$-代数里。在 $0-1$损失的二分类情况下，$\sigma$-代数在$\mathcal{X}\times{0,1}$上， 在$l$上的假设相当于假设对任意的$h$,集合${(x,h(x):x\in\mathcal{X}}$是$\sigma$-代数。
评注（完全与自主表示学习） 在前面的定义中， 我们要求算法从$\mathcal{H}$中返回一个假设。 在某些情况下 ，$\mathcal{H}$是$\mathcal{H}’$ 的 一个子集，损 失函数可以拓展 为一个从$\mathcal{H}’\times Z$到实数的函数。在这种情况下 ， 我们允许算法返回 一个假设$h’\in\mathcal{H}’$，只 要它满足$L_\mathcal{D}(h’)\le\underset{h\in\mathcal{H}}{\min}L_\mathcal{D}(h)+\epsilon$。允 许 算法从$\mathcal{H}’$返回一个假设 ， 称为自主表示学习， 完全学习要求算 法必须从$\mathcal{H}$中返回一个假设。自主表示学习有时也称为“不完全学习“．尽管在自主学习中并不存在不恰当的情况。
2.3 小结
这一章定义了主要的正式学习模型——PAC 学习。基本模型基于可实现的假设，不可知 PAC 学习对样本分布不做限制。我们也将 PAC 模型推广到任意损失函数的情况。我们有时将最通用的模型简称为 PAC 学习， 省略 ”不可知” 这个前缀，让 读 者从 上 下 文中体会潜在的损失函数是什么。再次强调最原始的 PAC 模型基于可实现的假设。第 6 章会探讨可学习的其他概念。
2.4 文献评注
对广义损失函数下的不可知 PAC 可学习的基本定义， 参考了 Vladimir Vapnik 和 Alexey Chervonenkis 的著作( Vapnik 和 Chervonenkis 1971 )。特别是， 遵循了 Vapnik 关学习的一般设定( Vapnik 1982, Vapnik 1992, Vapnik 1995, Vapnik 1998) 。
PAC 学习一词由 Valiant (1984) 提出。Valiant 由于提出 PAC 模型，获 得了 2010 年的图灵奖。在 Valiant 给出的定义中采样复杂度是关于 $1/\epsilon$:、$1/\sigma$、假设类的势的多项式（也可以参考Kearns 和 Vazirani(l 994 ) )。我们将会在第 5 章看到 ，如果一 个问题是 PAC 可学习 的， 那么采样复杂度是关于$1/\epsilon$:、$\log(1/\sigma)$ 的多项式。Valiant 的定 义还要求算法的运行时间是这些变量的多项式时间。相比之下， 我们希望将学习的统计方面和计算方面分割开 来。第 7 章会详细介绍计算方面的内容。最后， 将不可知 PAC 学习规范化的工作应归功于 Haussler(1992) 。
3 学习过程的一致收敛
我们讨论过的第一个正式学习模型是 PAC 模型。第 2 章巳 经表明在可实现的假设下， 任何有限的假设类都是 PAC 可学习的。在这一章中， 我们将开发一个通用的工具—— 致收敛，并用它来表明在有一般损失函数的不可知 PAC 模型中，只要距离损失函数是有界的， 任何有限类都是可学习的。
3. 1 一致收敛是可学习的充分条件
本章讨论的学习条件背后的思想很简单。回想一下， 已知一个假设类$\mathcal{H}$， ERM 学习范式工作方式如下： 一 旦接收一个训练样本 $S$, 学习器评估每一个$\mathcal{H}$中的 $h$ 对于已知样本的损失（或误差），并 且输出$\mathcal{H}$ 中的一个最小化经验风险的元素。我们希望关千样本 $S$ 的可以最小化经验风险的 $h$ 也是一个关于真实数据概率分布的风险最小化（或者是风险接近最小化）。那么．它足以保证$\mathcal{H}$中的所有元素的经验风险是它们真实风险的一个很好的近似。换句话说，我们需要假设类中所有的假设都是一致的， 经验风险将会接近真实风险， 表达式如下所示。
定义 3. 1（$\varepsilon$-代表性样本） 如果满足下列不等式： $$\forall h \in \mathcal{H}, L_S(h)-L_{\mathcal{L}}(h) \leq \varepsilon$$ 一个训练集 $S$就称作$\varepsilon$代表性样本（关 于定义域 $Z$, 假设类$\mathcal{H}$，损失函数$l$和分布$\mathcal{H}$）
下一个简单的引理说明只要样本是$\varepsilon/2$- 代表性的，就 可以保证 ERM 学习规则返回一个好的假设。
引理 3. 2 假设一个训练集 S 是$\varepsilon/2$- 代表性的（关 于定义域 Z, 假设类$\mathcal{H}$， 损失函数$\mathbb{l}$和分布$\mathcal{H}$ ) 。那么， 任何一个ERM$_\mathcal{H}$的输出， 即任意$h_S\in \underset{h\in\mathcal{H}}{\text{argmin}}L_S(h)$都满足 \(L_{\mathcal{H}}(h_S)\leq \underset{h\in\mathcal{H}}{\min}L_{\mathcal{D}}(h)+\varepsilon\)
证明 对于所有的$h\in \mathcal{H}$
\[L_{mathcal{H}}\leq L_S(h_S)+\frac{\varepsilon}{2}\leq L_{mathcal{D}}+\varepsilon\]其中第一个和第三个不等式是由于 S 是$\varepsilon/2$ - 代表性的假设（定义 3. 1), 第二个不等式成立 因为$h_S$是 ERM 预测器的结果。 上面的引 理表明为了确保 ERM 规则是一个不可知 PAC 学习器， 应该满足至少在概率$1-\delta$下随机选择一个训练集 ，它 将是$\varepsilon$代表性训练集。一致收敛条件形式化了这个要求。
定义 3. 3( 一致收敛） 如果一个假设类${\mathcal{H}}$满足如 下条件 ， 那么它 就有一 致收敛性质（关于定 义域 $Z$ 和损失函数$l$)：存在一个函数$m_{\mathcal{H}}^{UC}$：$(0,1)\to \mathbb{N}$使得对于所有$\varepsilon,\delta \in (0,1)$和在 $Z$ 上的所有概 率分布$\mathcal{D}$ . 如果 $S$ 是从$\mathcal{D}$得到的一个独立同分 布的满足$m\geq m_{\mathcal{H}}^{UC}(\varepsilon,\delta)$的样本， 那么． 至少在概 率 $1-\delta$ 下， $S$ 是$\varepsilon$代表性的。
相似于PAC 学习中样本 复杂度的定义， 函数 对$m_{\mathcal{H}}^{UC}$ 度量了获得一致收敛性质的（最小）样本复杂度， 即我们需要多少祥木来确保至少在概率 $1-\delta$下， 样本是$\varepsilon$代表性的
一 致性在这里指的是在定 义域中所有可能的概 率分布下 ， 用千所有$\mathcal{H}$中的元素．有一个固定的样本大小 。 下面的推论直接来 自自引 理 3. 2 和一致收敛的定 义。
推论 3. 4 如果类$\mathcal{H}$关 于函数 $m_{\mathcal{H}}^{UC}$ 有一致收 敛的性质， 那么这个类是 样本复杂度 为$m_{\mathcal{H}}\leq m_{\mathcal{H}}^{UC}(\varepsilon/2,\delta)$的不可知 PAC 可学习的 。 而且在那种情况下，$ERM_\mathcal{H}$范式是关于$\mathcal{H}$的成功的不可知 PAC可学习的 。
3. 2 有限类是不可知 PAC 可学习的
鉴于推论3. 4 ，只要我们确定对 于 一个有限假设类 ，一致收敛成立 ， 那么每个有限假设类都是不可知PAC 可学习的 。
为了说明 一致收敛成立， 类似于第 1 章的推导， 我们用两步的论证。第一步用联合界 第二步用测度集中度不等式 。现在我们具体地解释这两步 。
| 固定$\varepsilon,\delta$ 。 我们需要找到 一个样本大小 $m$ 可以保证下 面的条件成立 ： 对于任何 $\mathcal{D}$, 至少在概率$1-\delta$ 下．从$\mathcal{D}$中采样得到的独立同分布的样本的选择$S= (z_1,z_2,\cdots,z_m)$ 对于所有$h\in\mathcal{H}$，$ | L_S(h)-L_{\mathcal{D}}(h) | \leq\varepsilon$成立。也就是 ， |
同样，我们需要证明
\[\mathcal{D}^m(\{S:\exists h\in\mathcal{H},|L_S(h)-L_{\mathcal{D}}(h)|> \varepsilon\})<\delta\]写出
\[\{S:\exists h\in\mathcal{H},|L_S(h)-L_{\mathcal{D}}(h)|> \varepsilon\}=\cup_{h\in \mathcal{H}}{S:|L_S(h)-L_{\mathcal{D}}(h)|>\varepsilon}\]并且应用联合界（引 理 1. 2), 我们得到 ：
\[\begin{multline}\mathcal{D}^m(\{S:\exists h\in\mathcal{H},|L_S(h)-L_{\mathcal{D}}(h)|> \varepsilon\})\\ \leq\sum{h\in\mathcal{H}}\mathcal{D}^m(\{S:|L_S(h)-L_{\mathcal{D}}(h)|> \varepsilon\})\tag{3.1}\end{multline}\]| 第二步是为了证明这个不等式右边的每个被加数都足够小（对于 一个充分大的 m ) 。也就是说， 我们将要证明对于任意固定的类 h ( 它是在训练集的采样之前提前选择的）， 真实风险与经验风险之间的差距$ | L_S{h}-L_{\mathcal{D}}(h) | $可能很小。 |
| 回想$L_\mathcal{D}(h)=\mathbb{E}{z~D}[\mathbb{l}(h,z)]$和$L_S(h)=\frac{1}{m}\sum{i=1}^m \mathbb{l}(h,z_i)$。由于每个$z_i$都从D 中独立同分布采样得来， 随机变量$\mathbb{l}(h,z_i)$的期望值是$L_{mathcal{D}}(h)$ 。由于期望的线性化，得出$L_{\mathcal{D}}(h)$也是$L_{S}(h)$的期望值。因此，$ | L_S{h}-L_{\mathcal{D}}(h) | $是随机变量$L_S{h}$与它的期望值之间的偏差。因此， 我们需要证明$L_S{h}$的度量集中在它的期望值附近。 |
一个基本的统计事实——大数定理．说明了当 $m$ 趋近于无穷大时， 经验平均值收敛到它们的真实期望。这对千$L_S{h}$也是成立的， 由于它是独立同分 布的随机变最 m 的经验平均值。可是．由于大数定理仅仅是一个渐近结果．因此它对于任意给定的有限的样本大小的经 验估计误差与其真实值之间的差距没有提供任何信息。
我们将用 Hoeffding 提出的一个测度集中度不等式来代替， 它量化了经验平均值与它们期望值之间的差距。
引理 3. 5 ( Hoeffding 不等式） 令$\theta_0,\cdots,\theta_m$是一个独立同分布的随机变量的序列，假设对于所有的 i .$\mathbb{E}[\theta_i]=\mu$且$\mathbb{P}[a\leq\theta_i\leq b]=1$ 。 那么． 对于所有的 $\varepsilon>0$
\[\mathbb{P}\left[|\frac{1}{m}\sum_{i=1}^m\theta_i-\mu|\>\varepsilon\right]\leq 2e^{-2m\varepsilon^2/(b-a)^2}\]
回到我们的问题， 令$\theta_i$ 为随机变量$\mathbb{l}(h,z_i)$。由于h是固定的， 而且$z_1,\cdots,z_m$是独立同分布采样得到的， 所以$\theta_0,\cdots,\theta_m$也是独立同分布的随机变量。而且有$L_S(h)=\frac{1}{m}\sum_{i=1}^m\theta_i$和 $L_{\mathcal{D}}(h)=\mu$。让我们进一步假设$\mathbb{l}$ 的范围是$[0,1]$, 因此 $\theta_i\in[0,1]$。因此得到
\[\mathcal{D}^m(\{S: |L_S(h)-L_{\mathcal{D}}(h)|> \varepsilon\})=\mathbb{P}\left[|\frac{1}{m}\sum_{i=1}^m\theta_i-\mu|\>\varepsilon\right]\leq 2e^{-2m\varepsilon^2/(b-a)^2}\tag{3.2}\]把它和式( 3. 1 ) 结合， 得到
\[\mathcal{D}^m(\{S:\exists h\in\mathcal{H},|L_S(h)-L_{\mathcal{D}}(h)|> \varepsilon\})\leq\sum_{h\in\mathcal{H}}2e^{-2m\varepsilon^2}=2|\mathcal{H}|e^{-2m\varepsilon^2}\]最后，如果我们选择
\[m\geq\frac{\log{(2|\mathcal{H}|/\delta)}}{2\varepsilon^2}\]那么
\[\mathcal{D}^m(S:\exists h\in \mathcal{H},|L_S(h)-L_{\mathcal{H}}|>\varepsilon)\leq\delta\]\[m_{\mathcal{H}}^{UC}(\varepsilon,\delta)\leq\left[\frac{\log(2|\mathcal{H}|/\delta)}{2\varepsilon^2}\right]\]推论 3. 6 令$\mathcal{H}$是一个有限假设类， Z 是一个定义域， 并且令$\mathbb{l}:\mathcal{H}\times Z\to[0,1]$是一个损失函数。那么$\mathcal{H}$具有一致收敛性质， 而且样 本复杂度是
而且 ， 用 ERM 算法， 这个类是不可知 PAC 可学习的， 样本复杂度是
\[m_{\mathcal{H}}(\epsilon.\delta)\leq m_{\mathcal{H}}^{UC}(\varepsilon,\delta)\leq\left[\frac{\log(2|\mathcal{H}|/\delta)}{2\varepsilon^2}\right]\]评注( “离散化技巧”) 虽然之前的推论仅仅应用千有限假设类， 但有一个简单的技巧可以让我们得到无限假设类的实际样木复杂度的一个很好的估计，考虑一个假设类由 d 个参数来参数化。比如， 令$\chi=\mathbb{R}，\mathcal{Y}={\mp 1}$ 而且假设类$\mathcal{H}$ 是所有形式为$h_\theta(x)=\text{sign}(x-\theta)$的函数。也就是说， 每个假设由 1 个参数来参数化，$\theta\in\mathbb{R}$， 而且对于所有大于 $\theta$的实例， 假设输出 $1$ ; 对小于$\theta$的实例， 假设输出$-1$。这就是一个有无限大小的假设类。然而， 如果打算用计算机实际学习这个假设类， 我们可能用浮点表示法来维持实数 ， 也就是说 64 位。结果在实际中， 假设类由可以用一个 64 位浮点数表达的标量集合来参数化。最多有$2^{64}$ 个 这样的数， 因此假设类的实际大小最多是$2^{64}$。 更一般地， 如果假设类由 $d$个数来参数化， 实际上我们学习到 一个最大为$2^{64d}$ 的假设类。应用推论 3. 6 , 我们得到这样的类的样本复杂度以$\frac{128d+2\log(2/\delta)}{\varepsilon^2}$为界。样本复杂度的这个上界依赖于机器使用的实数的特定表达方式， 这是它的缺点。第 5 章将会介绍一个分析无限大小的假设类的样本复杂度的严格方法 。然而， 在许多实际情况中， 离散化技巧可以用来得到一个样本复杂度的粗略估计。
3. 3 小 结
如果假设类$\mathcal{H}$一致收敛， 那么在大多数情况下$\mathcal{H}$中的假设的经验风险将会如实地表达它们的真实风险。用 ERM 规则， 一致收敛满足不可知 PAC 可学习的条 件。我们已经表明有限假设类有一致收敛的性质， 因此它也是不可知 PAC 可学习的。
4 偏差与复杂性权衡
在第 1 章中我们看到 ，除非很小心， 否则训练数据会误导学习器导致过拟合。为了克服这一问题， 我们将搜索空间限制在某个假设类$\mathcal{H}$下。可以认为， 这种假设类反映了学习器关于任务的先验知识， 认为假设类伈中存在一个假设是低错误率模型。例如， 在木瓜品尝问题中， 以对于其他水果的经验为基础．我们可能限制在色－度硬度平面的某个矩形区域来预测木瓜的味道。
这样的先验知识对学习的成功是否必要？ 是否存在通用的学习器（一个没有特定任务先验知识的，并 可挑战完成所有学习任务的学习器）？ 下面我们详细说明这点 。一个特定的学习任务由$\mathcal{X}\times\mathcal{Y}$上的一个未知分布$\mathcal{D}$ 所定义， 学习器的目标是寻找一个预测器$h:\mathcal{X}\to\mathcal{Y}$ , 使得损失$L_\mathcal{D}(h)$ 足够小。我们的问题是 ， 如果$A$ 收到来自$\mathcal{D}$的 $m$ 个独立同分布的样本 ， 是否存在一个学习算法$A$和一个大小为$m$ 的训练集， 使得对每一个分布$\mathcal{D}$ , 能以较大的几率输出一个具有较低风险的预测器h。
本章第一部分对此问题进行正式讨论。“没有免费的午餐”定理表明， 不存在这样的通用学习器。更准确地说， 这个定理阐述的是， 对二分预测任务， 每个学习器都存在一个使得学习失效的分布。如果学 习器接收来自同 一分布的独立同分布样本， 其输出假设可能有$\ge30%$的较大风险， 我们说学习失败； 反之对同一分布， 存在另一个学习器能输出一个具有较低风险的假设。换言之， 这个定理说明， 没有学习器能在所有可学习的任务上都学习成 功——即每个学习器都有学习失败的任务， 而这些任务对千其他学习器却能成功学习 。
因此， 解决一个由分布$\mathcal{D}$所定义的特定学习问题时， 我们应 该具备一些关于分布$\mathcal{D}$的先验知识。其中一类先验知识是限定$\mathcal{D}$来自具体的参数族分布 。关于$\mathcal{D}$的另一类先验知识是， 当定义PAC 学习模型时， 在某个事先指定的假设类$\mathcal{H}$里存在假设 $h$ , 使得$L_\mathcal{D}(h)=0$。关于$\mathcal{D}$一种较宽松的先验知识是假定$\underset{h\in\mathcal{H}}{\min}L_\mathcal{D}(h)$较小。一定程度上， 这种弱假设是使用不可知PAC 模型的先决条件， 其中我们要求输出假设的风险不会超过$\underset{h\in\mathcal{H}}{\min}L_\mathcal{D}(h)$。
在本章第二部分我们采用一个假设类作为将先验知识标准化的方式 ， 来研究其利弊性。我们将 ERM 算法在假设类$\mathcal{H}$上的误差分解为两部分。第一部分反映了先验知识的质量 ， 由假设类具有的最小风险$\underset{h\in\mathcal{H}}{\min}L_\mathcal{D}(h)$所刻画。这部分也称为逼近误差 ， 或是叫算法从$\mathcal{H}$选择一个假设所产生的偏差。第二部分是由过拟合引起的误差， 取决千假设类的大小或复杂度，也 称为估计误差。这两项意味着， 在一个较为复杂的假设（可以减小偏差但会增加过拟合的风险） 和一个简单的假设（可能会增大差偏但可以降低过拟合的风险）选择之间存在着一个权衡。
4.1 没有免费的午餐“定理
在这部分我们证明不存在通用的学习器。通过证明没有学习器能在所有的任务上学习成 功，我们将具体定理阐述如下：
定理4. 1 （没有免费的午餐） 对实例空间$\mathcal{x}$上$0-1$ 损失的二分任务， 令$A$表示任意的 学习算法 。样本大小 $m$ 表示小 于$|\mathcal{X}|/2$的任意数。则在$\mathcal{X}\times{ 0, 1}$上存在一个分布$\mathcal{D}$, 使得：
- 存在一个函数$f:\mathcal{X}\to{0,1}$满足$L_\mathcal{D}(f)=0$。
- 在样本集$S\sim\mathcal{D}^m$上， 以至少$\frac{1}{7}$的概率满足$L_\mathcal{D}(A(S))\ge\frac{1}{8}$。
| 这个定理陈述的是，对于每个学习器，都存 在一个任务使其失败，即便 这个任务能够被另一个学习器成功学习。实际上，一 个平凡的学习器能在此类情况下学习成功， 它将是关于假设类$\mathcal{H}={f}$的一个ERM 学习器； 或更广泛而言 ， 其 ERM 是对任何包含$f$且样本大小满足$m>8\log(7 | \mathcal{H} | /6)$( 见推论 1. 3) 的有限假设类而言的。 |
证明 令$C$是大小为 $2m$ 的集合$\mathcal{X}$子集。直观的证据是， 任何只观测到空间$C$ 中一半实例的学习算法，都 不具有信息量来反映$C$中剩余实例的标签。因此，存 在一个 ”事实”， 即在$C$ 中未观测到的样本上，目标函数$f$贴的标签与$A(S )$预测的标签不一致。
注意， 从$C$到${0,1}$有 $T= 2^{2m}$个 函数。这些函数表示为$f_1,\cdots,f_T$ 。 对每个这样的函数， 令$D_i$ 表示定义在$C\times{0,1}$上的分布： \(\mathcal{D}_i(\{(x,y)\})=\left\{\begin{align} 1/|C|\qquad &\text{if}\quad y=f_i(x)\\ 0 \qquad &\text{otherwise} \end{align}\right.\)
| 也就是，选择一对$(x,y)$，标 签 $y$ 刚好对应 $f_i$ 真实标签的概率是 $1/ | Cl$ , 而 $y\ne f_i(x)$的概率是 $0$。显然，$L_{\mathcal{D}_i}(f_i)=0$。 |
我们将证明，对 每一个学习算法 $A$ , 其接收到来自$C\times{0,1}$的 $m$ 大小样本集，返 回一个函数$A(S): C\to{0,1}$满足：
\[\underset{i\in[T]}{\max}\underset{S\sim\mathcal{D}_i^m}{\mathbb{E}}[L_{\mathcal{D}_i}(A(S))]\ge1/4\tag{4.1}\]显然， 这意味着对每一个学习算法$A ‘$ , 其接收到来自$C\times{0,1}$的$m$ 大小样本集，存 在一个函数$f:\mathcal{X}\to{0,1}$和$\mathcal{X}\times{ 0, 1}$上的一个分布$\mathcal{D}$ , 使得$L_\mathcal{D}(f)=0$且
\[\underset{S\sim\mathcal{D}_i^m}{\mathbb{E}}[L_{\mathcal{D}_i}(A'(S))]\ge1/4\tag{4.2}\]容易证明， 以上是满足$\mathbb{P}[[L_{\mathcal{D}_i}(A’(S))]\ge1/8]\ge1/7$的充分条件， 这也是我们所要证明的。
我们转为证明式( 4. 1) 成立。对于来自$C\times{0,1}$的$m$ 个样本， 有 $k=(2m)^m$种 可能的序列。将这些序列表示为$S_1,\cdots,\S_k$。 同时 ，如果$S_j=(x_1,\cdots.x_m)$, 我们用$S_j^i$ 表示包含由函数$f_i$ 给实例$S_j$贴标签的序列， 即$S_j^i=((x_1,f_i(x_1)),\cdots,(x_m,f_i(x_m))$。若分布是$\mathcal{D}_i$则 $A$ 可能接收到的训练样本集是$S_1^i,\cdots,S_k^i$, 并且所有的训练集被采样的概率相等。因此
\[\underset{S\sim\mathcal{D}_i^m}{\mathbb{E}}[L_{\mathcal{D}_i}(A(S))]=\frac{1}{k}\sum_{j=1}^{k}L_{\mathcal{D}_i}(A(S_j^i))\tag{4.3}\]根据“最大值”大于“平均值”以及“平均值”大于“最小值”的事实，有
\[\begin{align} \underset{i\in[T]}{\max}\frac{1}{k}\sum_{j=1}^{k}L_{\mathcal{D}_i}(A(S_j^i))&\ge\frac{1}{T}\sum_{i=1}^{T}\frac{1}{k}\sum_{j=1}^{k}L_{\mathcal{D}_i}(A(S_j^i))\\ &=\frac{1}{k}\sum_{j=1}^{k}\frac{1}{T}\sum_{j=1}^{T}L_{\mathcal{D}_i}(A(S_j^i))\\ &\ge\underset{j\in[k]}{\min}\frac{1}{T}\sum_{j=1}^{T}L_{\mathcal{D}_i}(A(S_j^i)) \end{align}\tag{4.4}\]接下来，固定某个$j\in[k]$。设$S_j=(x_1,\cdots,x_m)$并令$v_1,\cdots,v_p$中未出现在$S_j$ 的样本。显然，$p\ge m$.。 因此， 对每个函数$h:C\to{0,1}$和每个 $i$有
\[\begin{align} L_{\mathcal{D}_i}(h)&=\frac{1}{2m}\sum_{x\in C}\mathbb{l}_{[h(x)\ne f_i(x)]}\ge \frac{1}{2m}\sum_{r=1}^{p}\mathbb{l}_{[h(v_r)\ne f_i(v_r)]}\\ &\ge\frac{1}{2p}\sum_{r=1}^{p}\mathbb{l}_{[h(v_r)\ne f_i(v_r)]} \end{align}\tag{4.5}\]因此，
\[\begin{align} \frac{1}{T}\sum_{i=1}^{T}L_{\mathcal{D}_i}(A(S_j^i))&\ge\frac{1}{T}\sum_{i=1}^{T}\frac{1}{2p}\sum_{r=1}^{p}\mathbb{l}_{[A(S_j^i)(v_r)\ne f_i(v_r)]}\\ &=\frac{1}{2p}\sum_{r=1}^{p}\frac{1}{T}\sum_{i=1}^{T}\mathbb{l}_{[A(S_j^i)(v_r)\ne f_i(v_r)]}\\ &\ge\frac{1}{2}\cdot\underset{r\in[p]}{\min}\frac{1}{T}\sum_{i=1}^{T}\mathbb{l}_{[A(S_j^i)(v_r)\ne f_i(v_r)]} \end{align}\tag{4.6}\]下 面固定某个$r\in[p]$ 。 我们可以将$f_1,\cdots,f_T$中所有的函数分为 $T/2$ 对不相交的函 数， 其中， 对于每对$(f_i,f_{i’})$， 当且仅当$c=v_r$时， 对每个$c\in C$ 满足$f_i(c)\ne f_{i’}(c)$ 。因为对于每对函数， 一定有$S_j^i\ne S_j^{i’}$，且
\[\mathbb{l}_{[A(S_j^i)(v_r)\ne f_i(v_r)]}+\mathbb{l}_{[A(S_j^{i'})(v_r)\ne f_i(v_r)]}=1\]使得
\[\frac{1}{T}\sum_{i=1}^{T}\mathbb{l}_{[A(S_j^i)(v_r)\ne f_i(v_r)]}=\frac{1}{2}\]结合 上式和式(4. 6) 、式( 4. 4) 以及式 (4. 3), 可知式(4. 1 )成立，证明完成。
“没有免费的午餐”和先验知识
“没有免费的午餐”结论与对先验知识的必要与否有什么联系？考虑关于假设类凡上的一个 ERM 预测器， 这个假设类由从$X$到${0,1}$的 所有映射函数$f$构成。这个类代表先验知识的缺失：从 域到标签集上的每个函数都能看成是一个好的候选。根据“没有 免费的午餐”定理， 从假设类$\mathcal{H}$中选择输出假设的任意算法， 尤其是 ERM 预测器，都存在着某个任务使其学习失败。因此，下面的推论给出了形式化阐述，这个类不是 PAC可学习的：
推论 4. 2 令$\mathcal{X}$为一个 无限定义域集 ，$\mathcal{H}$为从$\mathcal{X}$到${0,1}$上的所有映射集，则$\mathcal{H}$不是 PAC可学习的 。
| 证明 采用反证法， 假设这个类是可学习的。选$\epsilon<1/8$和 $\delta<1/7$。由 PAC可学习性的定义，一定存在学习算法$A$ 和一个整数$m= m(\epsilon, \delta)$, 使得对于任意关于$\mathcal{X}\times{0,1}$的生成数据分布，若对于某个函数$f:\mathcal{X}\to{0,1}$ , 有$L_\mathcal{D}(f)=0$，则当 $A$ 应用于由$\mathcal{D}$产生的大小 $m$、独立同分布样本集 $S$ 上，$L_\mathcal{D}(A(S))$以大于$(1-\delta)$的概率成立。然而，应用 “ 没有免费的午餐”定 理，由于$ | \mathcal{X} | >2m$，对每个学习算法（尤其是对算法 $A$) , 存在一个分布$\mathcal{D}$使得以大于$1/7>\delta$的概率 ， $L_\mathcal{D}(A(S))>1/8>\epsilon$成立，与假设矛盾 。 |
如何避免这样的失败？我们可以利用对于特定学习任务的先验知识，结合“没有免费的 午餐”定理，来预见并脱离这样的困境，从而避免学习任务时会导致失败的分布。这样的先验知识可以通过限制假设类来表示。
但是我们如何选择一个好的假设类？一方面， 我们希望这个类包含完全无误差（在PAC 背景下）的假设， 或至少包含的假设所能达到的最小误差实际上很小（在不可知背景下）。另一 方面， 我们已经看到， 不能只简单地选择最丰富的假设类 ——给定的域上所有 函数 的类。关于权衡的讨论见下一小节。
5. 2 误差分解
为了回答本章的问题， 我们将一个ERM$\mathcal{H}$预测器的误差分解为两 部分。令$h$为一个 ERM$\mathcal{H}$假设。则写作
\(L\mathcal{D}(h_S)=\epsilon_{app}+\epsilon_{est}\tag{4.7}\) 其中：$\epsilon_{app}=\underset{h\in\mathcal{H}}{\min}L_\mathcal{D}(h)$，$\epsilon_{est}=L_\mathcal{D}(h)-\epsilon_{app}$
- 逼近误差 ： 假设类里预测器所取得的最小风险。这一项刻画由千限制到一个具体假设类所引起的风险， 即所产生的归纳偏置。逼近误差不依赖于样本大小 ， 取决于所选择的假设类。扩大假设类可以减小逼近误差。 在可实现性的假设下， 逼近误差是零。然而， 在不可知情况下， 逼近误差可能很大
- 估计误差： 逼近误差与ERM 预测器误差之间的差异。估计误差的产生是因为： 经验风险（即训练误差）只是真实风险的一个估计，所以最小化经验风险预测器只是最小化真实风险预测器的一个估计。 预测器的估计好坏取决于样本集大小和假设类的大小或复杂度。如前所示， 对一个有效假设类，$\epsilon_{est}$随$\mathcal{H}$（以对数方式）递增， 随$m$ 递减。我们可以将$\mathcal{H}$的大小作为其复杂度的一种衡量。在后面的章节我们将定义一些其他的假设类复杂度衡量指标。
由于目标是将总风险最小化， 因此我们面临着一个权衡， 称为偏差－复杂度权衡 。一方面， 选择一个丰富的假设类作为$\mathcal{H}$会导致过拟合， 使得逼近误差减小的同时估计误 差增大。另一方面， 选择一个较小的假设类作为$\mathcal{H}$, 会导致估计误差减小的同时逼近误差增大，换言之会欠拟合。当然，关 于$\mathcal{H}$的一个好的选择是， 假设类只包含一个分类器 —— 贝叶斯最优分 类器。但是贝叶斯最优分类器依赖千潜在分布互 而$\mathcal{D}$却是未知的（事实上， 事先知道分布就无需进行学习）。
学习理论研究的是我们如何使得$\mathcal{H}$丰富的同时依然保持合理的估计误差。在很多情况中， 经验研究着重千对某个域设计一个好的假设类。这里. “好”的假设类意味着其逼近误差不会过大。意思就是， 虽然我们不是专家且不知道如何构造最优分类器， 但是对面临的问题有一些先验知识， 确保能够设计一个假设类。这个假设类的逼近误差和估计误差都不会太大 。回到木瓜的例子，我们不知道如何根据木瓜的颜色和硬度预测其成熟的程度，但是我们知道 颜色－硬度的二维矩形区域可能是一个好的预测器。
5. 3 小结
“没有免费的午餐” 定理说明不存在通用的学习器。每个学习器都有其特定的任务 ， 为了学习成功要采用一些关于任务的先验知。识目前为止， 通过限定输出假设为所选假设类中的一员， 我们对先验知识进行建模。当选择这个假设类时 ， 我们面临着一个权衡， 是选择一个较大或是较复杂的假设类， 保证有较小的逼近误差 ； 还是选择一个有更多限制的假设 类， 保证较小的估计误差？关于估计误差的更多性质在下一章讨论。第 6章将讨论其他表达先验知识的方法。
