周志华先生《机器学习》一书学习笔记
记录学习过程
本博客记录Chapter12

Table of Contents

1 基础知识

计算学习理论（computational learning theory）：关于通过“计算”来进行“学习”的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法体统理论保证，并根据结果指导算法设计。

对于二分类问题，给定样本集机器学习（周志华）第12章计算学习理论，。假设所有样本服从一个隐含未知的分布，所有样本均独立同分布（independent and identically distributed）。

令机器学习（周志华）第12章计算学习理论为样本到的映射，其泛化误差为

对的经验误差为

由于D是机器学习（周志华）第12章计算学习理论的独立同分布采样，因此的经验误差的期望等于其泛化误差。在上下文明确时，我们将和分别简记为和。令为的上限，即；我们通常用表示预先设定的学得模型所应满足的误差要求，亦称“误差参数”。

我们将研究经验误差和泛化误差之间的逼近程度；若机器学习（周志华）第12章计算学习理论在数据集上的经验误差为0，则称与D一致，否则称其不一致。对于任意两个映射，用不合（disagreement）来度量他们之间的差别：

我们将使用几个常见的不等式：

Jensen不等式：对任意凸函数，有
Hoeffding不等式：若为个独立随机变量，且满足，对任意，有
McDiarmid不等式：若为个独立随机变量，且满足，函数满足：

那么对于任何，我们有

2 PAC学习

概率近似正确理论（Probably Approximately Correct，PAC）：

先介绍两个概念：
：概念类。表示从样本空间到标签空间的映射，可以对任意样本做。
：假设类。学习算法聚合了它认为可能形成的目标概念。
如果，则表示该假设可以以与ground truth标签一致的方式完全分离所有示例，该问题对于学习算法而言称为“可分离”；否则称为“形影不离”
对于训练集，我们希望学习算法学习到的模型所对应的假设尽可能接近目标概念。我们希望以更大的确定性来学习一个更好的模型，即学习一个误差达到预设上限的概率更大的模型，也就是“概率近似正确”的意思。形式上，令表示置信度，可以定义为：
PAC辨识：对，所有的和分布，若存在学习算法，其输出假设满足：

则称学习算法能从假设空间中PAC辨识概念类。这样的学习算法能以较大的概率(至少) 学得目标概念的近似 (误差最多为)。在此基础上可定义:
PAC可学习：令表示从分布中独立同分布采样得到的样例数目，，对所有分布，若存在学习算法和多项式函数（样例数目与误差、置信度、数据本身的复杂度、目标概念的复杂度都有关），使得对于任何，学习算法能从假设空间中PAC辨识概念类，则称概念类对假设空间而言是PAC可学习的，有时也简称概念类是PAC 可学习的。
PAC学习算法：满足PAC可学习的算法。（假定学习算法处理每个样本的时间为常数，因此的时间复杂度等价于样本复杂度。于是，我们对算法时间复杂度的关心就转化为对样本复杂度的关心）
样本复杂度（Sample Complexity）：满足的最小的。
PAC学习中一个关键因素是假设空间H的复杂度。H包含了学习算法所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即H=C，这称为”恰PAC可学习” (properly PAC learnable)。直观地看，这意味着学习算法的能力与学习任务”恰好匹配“。
然而，这个要求拥有来自概念类的所有候选假设似乎是合理的，但并不实用，因为在现实世界的应用中我们通常对概念类一无所知，更不用说获得一个假设空间和概念类完全一样学习算法。显然，更重要的是研究假设空间与概念类不同的情况，即。一般来说，越大，越有可能包含任何目标概念，但越难从中找到具体的目标概念。当它是有限时，我们称之为“有限假设空间”，否则称为“无限假设空间”。

3 有限假设空间

3.1 可分情形

对于PAC来说，只要训练集机器学习（周志华）第12章计算学习理论的规模能使得学习算法以概率找到目标假设的近似即可。

首先估计泛化误差大于机器学习（周志华）第12章计算学习理论但仍然在训练集上表现完美的假设的概率。假设的泛化误差大于，对于从分布随机抽样得到的任意样本，我们有：

由于包含例子，和一致的概率为：

我们事先并不知道学习算法会输出哪个假设，但我们只需要保证泛化误差大于机器学习（周志华）第12章计算学习理论，并且在训练集上完美的多个假设的出现概率之和不大于比。

令上式不大于机器学习（周志华）第12章计算学习理论

可用的

由此可知，有限假设空间都是PAC可学习的，所需的样例数目如上式所示，输出假设的泛化误差随样例数目的增多而收敛到 0，收敛速率为。

3.2 不可分情形

当机器学习（周志华）第12章计算学习理论时，我们的学习算法无法学习到目标概念的近似，但是当假设空间给定时，必然存在泛化误差最小的假设，找到这个假设的近似也是一个不错的目标。 .

机器学习（周志华）第12章计算学习理论中泛化误差最小的假设是，以此为目标可将PAC学习推广到的情况，称为**”不可知学习“**（agnostic learning）。其概念如下：

令机器学习（周志华）第12章计算学习理论表示从分布，中独立且相同的分布采样的样本数，对于所有分布，如果存在学习算法和多项式函数，使得对于任何，学习算法可以从满足下列方程的假设空间假设：

则称假设空间是不可知PAC学习的。

4 VC维

VC维：假设空间机器学习（周志华）第12章计算学习理论的VC维是能被打散的最大示例集的大小：

例如对二分类问题来说，m个样本最多有个可能结果，每种可能结果称为一种“对分”，若假设空间能实现数据集D的所有对分，则称数据集能被该假设空间打散。VC维指能被机器学习（周志华）第12章计算学习理论打散的最大示例集的大小。

应注意到，VC维与数据分布机器学习（周志华）第12章计算学习理论无关！在数据分布未知时，仍能计算出假设空间的VC维。

机器学习（周志华）第12章计算学习理论

若假设空间机器学习（周志华）第12章计算学习理论的VC维是，则对任意整数，有：

同时任何VC维有限的假设空间都是（不可知）PAC学习的。

5 Rademacher复杂度

Rademacher 复杂度 (Rademacher complexity) 是另一种刻画假设空间复杂度的途径，与VC维不同的是，它在一定程度上考虑了数据分布。

考虑实值函数空间机器学习（周志华）第12章计算学习理论，令。函数空间关于的经验Rademacher复杂度

经验Rademacher复杂度衡量了函数空间与随机噪声在集合中的相关性。通常我们希望了解函数空间在上关于分布的相关性，因此，对所
从采样的 IID 有一个大小为机器学习（周志华）第12章计算学习理论的集合。

假设空间的Rdemacher复杂度与增长函数满足