【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.PAC学习
计算学习理论中最基本的是概率近似正确（Probably Approximately Correct，简称PAC）学习理论。
令$c$表示“概念”（concept），这是从样本空间$\mathcal{X}$到标记空间$\mathcal{Y}$的映射，它决定示例$\mathbf{x}$的真实标记$y$，若对任何样例$(\mathbf{x},y)$有$c(\mathbf{x})=y$成立，则称$c$为目标概念；所有我们希望学得的目标概念所构成的集合称为“概念类”（concept class），用符号$\mathcal{C}$表示。
给定学习算法$\mathcal{L}$，它所考虑的所有可能概念的集合称为“假设空间”（hypothesis space），用符号$\mathcal{H}$表示。由于学习算法事先并不知道概念类的真实存在，因此$\mathcal{H}$和$\mathcal{C}$通常是不同的，学习算法会把自认为可能的目标概念集中起来构成$\mathcal{H}$，对$h\in \mathcal{H}$，由于并不能确定它是否真是目标概念，因此称为“假设”（hypothesis）。显然，假设$h$也是从样本空间$\mathcal{X}$到标记空间$\mathcal{Y}$的映射。
若目标概念$c \in \mathcal{H}$，则$\mathcal{H}$中存在假设能将所有示例按与真实标记一致的方式完全分开，我们称该问题对学习算法$\mathcal{L}$是“可分的”（separable），亦称“一致的”（consistent）；若$c \notin \mathcal{H}$，则$\mathcal{H}$中不存在任何假设能将所有示例完全正确分开，称该问题对学习算法$\mathcal{L}$是“不可分的”（non-separable），亦称“不一致的”（non-consistent）。
给定训练集$D$，我们希望基于学习算法$\mathcal{L}$学得的模型所对应的假设$h$尽可能接近目标概念$c$。那为什么不是希望精确地学到目标概念$c$呢？这是由于机器学习过程受到很多因素的制约，例如我们获得的训练集$D$往往仅包含有限数量的样例，因此，通常会存在一些在$D$上“等效”的假设，学习算法对它们无法区别；再如，从分布$\mathcal{D}$采样得到$D$的过程有一定偶然性（一般来说，训练样例越少，采样偶然性越大），可以想象，即便对同样大小的不同训练集，学得结果也可能有所不同。因此，我们是希望以比较大的把握学得比较好的模型，也就是说，以较大的概率学得误差满足预设上限的模型；这就是“概率”“近似正确”的含义。形式化地说，令$\delta$表示置信度，可定义：
定义1 PAC辨识（PAC Identify）：对$0<\epsilon,\delta<1$，所有$c \in \mathcal{C}$和分布$\mathcal{D}$，若存在学习算法$\mathcal{L}$，其输出假设$h \in \mathcal{H}$满足：
\[P(E(h) \leqslant \epsilon) \geqslant 1-\delta \tag{1}\]$E$表示泛化误差，见此处式(1)。
则称学习算法$\mathcal{L}$能从假设空间$\mathcal{H}$中PAC辨识概念类$\mathcal{C}$。
这样的学习算法$\mathcal{L}$能以较大的概率（至少$1-\delta$）学得目标概念$c$的近似（误差最多为$\epsilon$）。在此基础上可定义：
定义2 PAC可学习（PAC Learnable）：令$m$表示从分布$\mathcal{D}$中独立同分布采样得到的样例数目，$0<\epsilon,\delta<1$，对所有分布$\mathcal{D}$，若存在学习算法$\mathcal{L}$和多项式函数$\text{poly}(\cdot,\cdot,\cdot,\cdot)$，使得对于任何$m \geqslant \text{poly}(1/\epsilon,1/\delta,\text{size}(\mathbf{x}),\text{size}(c))$，$\mathcal{L}$能从假设空间$\mathcal{H}$中PAC辨识概念类$\mathcal{C}$，则称概念类$\mathcal{C}$对假设空间$\mathcal{H}$而言是PAC可学习的，有时也简称概念类$\mathcal{C}$是PAC可学习的。
样例数目$m$与误差$\epsilon$、置信度$\delta$、数据本身的复杂度$\text{size}(\mathbf{x})$、目标概念的复杂度$\text{size}(c)$都有关。
对计算机算法来说，必然要考虑时间复杂度，于是：
定义3 PAC学习算法（PAC Learning Algorithm）：若学习算法$\mathcal{L}$使概念类$\mathcal{C}$为PAC可学习的，且$\mathcal{L}$的运行时间也是多项式函数$\text{poly}(1/\epsilon,1/\delta,\text{size}(\mathbf{x}),\text{size}(c))$，则称概念类$\mathcal{C}$是高效PAC可学习（efficiently PAC learnable）的，称$\mathcal{L}$为概念类$\mathcal{C}$的PAC学习算法。
假定学习算法$\mathcal{L}$处理每个样本的时间为常数，则$\mathcal{L}$的时间复杂度等价于样本复杂度。于是，我们对算法时间复杂度的关心就转化为对样本复杂度的关心：
定义4 样本复杂度（Sample Complexity）：满足PAC学习算法$\mathcal{L}$所需的$m \geqslant \text{poly}(1/\epsilon,1/\delta,\text{size}(\mathbf{x}),\text{size}(c))$中最小的$m$，称为学习算法$\mathcal{L}$的样本复杂度。
显然，PAC学习给出了一个抽象地刻画机器学习能力的框架，基于这个框架能对很多重要问题进行理论探讨，例如研究某任务在什么样的条件下可学得较好的模型？某算法在什么样的条件下可进行有效的学习？需多少训练样例才能获得较好的模型？
PAC学习中一个关键因素是假设空间$\mathcal{H}$的复杂度。$\mathcal{H}$包含了学习算法$\mathcal{L}$所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即$\mathcal{H}=\mathcal{C}$，这称为“恰PAC可学习”（properly PAC learnable）；直观地看，这意味着学习算法的能力与学习任务“恰好匹配”。然而，这种让所有候选假设都来自概念类的要求看似合理，但却并不实际，因为在现实应用中我们对概念类$\mathcal{C}$同样一无所知，更别说获得一个假设空间与概念类恰好相同的学习算法。显然，更重要的是研究假设空间与概念类不同的情形，即$\mathcal{H}\neq \mathcal{C}$。一般而言，$\mathcal{H}$越大，其包含任意目标概念的可能性越大，但从中找到某个具体目标概念的难度也越大。$\lvert \mathcal{H} \rvert$有限时，我们称$\mathcal{H}$为“有限假设空间”，否则称为“无限假设空间”。
