PAC 学习理论概述

【概述】

计算学习理论（Computational Learning Theory）是研究关于通过计算来进行学习的理论，即机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计

计算学习理论中最基本的就是概率近似正确（Probably Approximately Correct，PAC）学习理论，其给出了一个抽象地刻画机器学习能力的框架，基于这个框架能够对很多重要问题进行理论探讨，例如研究某任务在什么样的条件下可习得较好的模型、某算法在什么样的条件下可进行有效的学习、需要多少训练样本才能得到较好的模型等

【基本假设】

对于给定样本集 $D\in \{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\cdots,(\mathbf{x}_n,y_n)\},\mathbf{x}_i\in\mathcal{X},y_i\in\mathcal{Y}=\{-1,+1\}$，假设 $\mathcal{X}$ 中的所有样本服从一个隐含未知的分布 $\mathcal{D}$，$D$ 中的所有样本都是独立从该分布中采样取得的

对于从样本空间 $\mathcal{X}$ 到标记空间 $\mathcal{Y}$ 的映射 $h$，其泛化误差为：

$$E(h;\mathcal{D})=P_{\mathbf{x}\sim \mathcal{D}}(h(\mathbf{x})\neq y)$$

$h$ 在 $D$ 上的经验误差为：

$$\hat{E}(h;\mathcal{D})=\frac{1}{n} \sum_{i=1}^n \mathbb{I}(h(\mathbf{x}_i)\neq y_i)$$

由于样本集 $D$ 是未知分布 $\mathcal{D}$ 独立同分布采样得来的，因此 $h$​ 的经验误差的期望等于其泛化误差

为便于表达，将 $h$ 的泛化误差和经验误差分别简记为 $E(h)$ 和 $\hat{E}(h)$，并令 $\epsilon$ 为 $E(h)$ 的上限，即:

$$E(h) \leq \epsilon$$

通常用其表示预先设定的习得模型所应满足的误差要求，称为误差参数

【基本定义】

进一步，给出如下的基本定义：

• 概念（Concept）：从样本空间 $\mathcal{X}$ 到标记空间 $\mathcal{Y}$ 的映射 $c$，其决定了样本 $\mathbf{x}$ 的真实标记 $y$
• 目标概念（Target Concept）：若对任何样本 $(\mathbf{x},y)$ 有 $c(\mathbf{x})=y$ 成立，则称 $c$ 为目标概念
• 概念类（Concept Class）：所有希望习得的目标概念所构成的集合 $\mathcal{C}$
• 假设空间（Hypothesis Space）：对于给定的学习算法 $\mathcal{L}$，其所考虑的所有可能概念的集合 $\mathcal{H}$

由于学习算法 $\mathcal{L}$ 事先并不知道概念类 $\mathcal{C}$ 是否真实存在，因此假设空间 $\mathcal{H}$ 和概念类 $\mathcal{C}$ 通常是不同的，学习算法 $\mathcal{L}$ 会把自认为可能的目标概念集中起来构成 $\mathcal{H}$

对于 $h\in \mathcal{H}$，由于并不能确定其是否真的为目标概念，因此常称 $h$ 为假设（Hypothesis），显然，假设 $h$ 也是从样本空间 $\mathcal{X}$ 到标记空间 $\mathcal{Y}$ 的映射

进一步，若目标概念 $c\in\mathcal{H}$，则假设空间 $\mathcal{H}$ 中存在假设 $h$ 能够将所有样本按与真实标记一致的方式分开，此时称问题对学习算法 $\mathcal{L}$ 是可分的（Separable），反之，若 $c\notin \mathcal{H}$，则假设空间 $H$ 中不存在任何假设 $h$ 能够将所有样本完全正确分开，此时称问题对学习算法 $\mathcal{L}$ 是不可分的（Non-separable）

【PCA 学习理论】

含义

对于给定训练集 $D$，希望基于学习算法 $\mathcal{L}$ 习得的模型所对应的假设 $h$ 能够尽可能的接近目标概念 $c$，即以较大的概率习得误差满足预设上限的模型，这就是概率近似正确的含义

之所以不是希望精确地学习到目标概念 $c$，是因为机器学习过程受到诸多因素的制约，例如训练集 $D$ 中的样本数量有限，通常会存在一些在 $D$ 上等效的假设，学习算法无法对它们进行区别；又例如从分布 $\mathcal{D}$ 中采样得到 $D$ 具备一定的偶然性，即使对于同样大小的不同训练集，习得结果也有可能不同

PAC 辨识

对 $0<\epsilon,\delta<1$，所有 $c\in\mathcal{C}$ 和分布 $\mathcal{D}$，若存在学习算法 $\mathcal{L}$，其输出假设 $h\in\mathcal{H}$ 满足：

$$P(E(h)\leq \epsilon) \geq 1-\delta$$

则称学习算法 $\mathcal{L}$ 能从假设空间 $H$ 中 PAC 辨识（PAC Identify）概念类 $\mathcal{C}$

这样的学习算法 $\mathcal{L}$ 能以误差至多为 $\epsilon$，概率至少为 $1-\delta$，习得目标概念 $c$ 的近似

PAC 可学习

进一步，令 $n$ 表示从分布 $\mathcal{D}$ 中独立同分布采样得到的样本数，若存在学习算法 $\mathcal{L}$ 和多项式函数 $\text{poly}(\cdot,\cdot,\cdot,\cdot)$，使得对任何

$$n\geq \text{poly}\Big[\frac{1}{\epsilon},\frac{1}{\delta},\text{size}(\mathbf{x}),\text{size}(\mathbf{c}) \Big]$$

学习算法 $\mathcal{L}$ 能从假设空间 $\mathcal{H}$ 中 PAC 辨识概念类 $\mathcal{C}$，则称概念类 $\mathcal{C}$ 对假设空间 $\mathcal{H}$ 是 PAC 可学习的（PAC Learnable）

PAC 学习算法

对于计算机算法来说，必然要考虑事件复杂度，那么若学习算法 $\mathcal{L}$ 使概念类 $\mathcal{C}$ 是 PAC 可学习的，且 $\mathcal{L}$​ 的运行时间也是多项式函数

$$\text{poly}\Big[\frac{1}{\epsilon},\frac{1}{\delta},\text{size}(\mathbf{x}),\text{size}(\mathbf{c}) \Big]$$

则称概念类 $\mathcal{C}$ 是高效 PAC 可学习的（Efficiently PAC Learnable），称学习算法 $\mathcal{L}$ 是概念类 $\mathcal{C}$ 的 PAC 学习算法（PAC Learning Algorithm）

样本复杂度

假定学习算法 $\mathcal{L}$ 处理每个样本的时间为常数，那么学习算法 $\mathcal{L}$ 的时间复杂度等价于样本复杂度，于是对算法时间复杂度的关心，就转化为对样本复杂度的关心

对满足 PAC 学习算法 $\mathcal{L}$ 所需的样本数

$$n\geq \text{poly}\Big[\frac{1}{\epsilon},\frac{1}{\delta},\text{size}(\mathbf{x}),\text{size}(\mathbf{c}) \Big]$$

中最小的 $n$，称为 PAC 学习算法 $\mathcal{L}$ 的样本复杂度（Sample Complexity）

【恰 PAC 可学习】

PAC 学习中一个关键因素是假设空间 $\mathcal{H}$ 的复杂度，$\mathcal{H}$ 中包含了学习算法 $\mathcal{L}$ 所有可能输出的假设，若在 PAC 学习中假设空间 $\mathcal{H}$ 与概念类 $\mathcal{C}$ 完全相同，即

$$\mathcal{H} = \mathcal{C}$$

那么称为恰 PAC 可学习（Properly PAC Learnable）

直观上来看，这意味着学习算法的能力与学习任务恰好匹配，但这种让所有候选假设都来自于概念类的要求看似合理，但并不实际，因为在现实应用中对概念类 $\mathcal{C}$ 通常一无所知，更不用说获得一个假设空间 $H$ 和概念类 $C$ 恰好相同的学习算法

显然，更重要的是研究假设空间 $\mathcal{H}$ 与概念类 $\mathcal{C}$ 不同的情景，即在给定 $n$ 个样本的训练集 $D$ 时，找出满足误差参数 $\epsilon$ 的假设

一般而言，假设空间 $\mathcal{H}$ 越大，其包含任意目标概念的可能性就越大，但从中找到某个具体目标概念的难度也就越大，在 $|\mathcal{H}|$ 有限时，称假设空间 $\mathcal{H}$ 为有限假设空间，反之，当 $|\mathcal{H}|$ 无限时，称假设空间 $\mathcal{H}$​ 为无限假设空间

现实学习任务所面临的通常是无限假设空间，例如实数域中的所有空间、$\mathbb{R}^d$ 空间中的所有线性超平面等，要想对该种情形的可学习性进行研究，就需要度量假设空间的复杂度，最常见的方法就是考虑假设空间的 VC 维（Vapnik-Chervonenkis Dimension）、Rademacher 复杂度

关于有限假设空间、VC 维、Rademacher 复杂度，详见：

• 有限假设空间
• VC 维与 Rademacher 复杂度

无论是基于 VC 维还是 Rademacher 复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关，对所有学习算法都适用，这使得人们能够脱离具体学习算法的设计来考虑学习问题本身的性质，但在另一方面，若希望获得与算法有关的分析结果，则需另辟蹊径，稳定性分析（Stability Analysis）就是这方面中的一个方向

• 稳定性分析