本章是关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

12.1 基础知识

本章主要讨论二分类问题，故y_i∈Y={-1,+1}。
给定样本集D={(x₁,y₁),(x₂,y₂),…,(x_m,y_m)}，x_i∈X。样本服从某个分布Ψ，D中样本都是独立同分布样本。
设h为X→Y的一个映射，泛化误差E(h)和h在D上的经验误差E^(h)分别为

不合

• 常用不等式
  1.Jensen不等式：对任意凸函数f(x)，有
  
  2.Hoeffding不等式：若x₁,x₂,…，x_m为m个独立随机变量，且0≤x_i≤1，则对于任意ε＞0，有
  
  3.McDiarmid不等式：若x₁,x₂,…,x_m为m个独立随机变量，且1≤i≤m，函数f满足
  sup是单词supremum的简写,意思是最小上界
  则对任意ε＞0，有

12.2 PAC学习

计算机理论中最基础的理论为概率近似正确PAC学习理论。PAC学习理论有四个核心定义：PAC辨识、PAC可学习、PAC学习算法、样本复杂度。在讲解四个定义前，先说明几个名词。

• 几个名词解释
  1）设样本空间X到标记空间Y的映射为c，称为概念(concept)。
  它决定了样本x的真实标记y，即对任意样本，有y=c(x)成立；则c称为目标概念。
  目标概念c构成的集合C，称为"概念类"。
  2）假设空间H：给定学习算法￡，它所考虑的所有可能概念的集合为假设空间H。
  H与C通常不同，因为H包含的可能目标概念除了真实目标概念外还有其他可能目标概念，即学习算法事先不知道概念类C的存在。
  也就是说，对于H里面的可能概念h，是一个假设h，h∈H，h也是样本空间X→标记空间Y的映射。
  3）可分与不可分
  ① 若目标概念c∈H，则H中存在假设h能将所有样本按照与其真实标记一致的方式正确分类，则该问题对学习算法￡来说是可分的、一致的。
  ② 若目标概念c∉H，则H中不存在假设h能将所有样本正确分类，则该问题对学习算法￡来说是不可分的、不一致的。

由于机器学习过程中受到诸多因素制约，如，样本数量有限、采样的偶然性，因此我们无法总是精确地学到目标概念真实映射c。
于是，我们退而求其次。给定数据集D，我们希望基于学习算法￡学得的模型所对应的假设h尽可能接近目标概念c。
也就是说，以较大的概率学得误差满足预设上限ε的模型，这就是"概率"，"近似正确"的含义。下面用数学语言来进行描述：

• 定义1：PAC辨识
  对0＜ε,δ＜1，所有c∈C和分布Ψ，若存在学习算法￡，其输出假设h满足，

  学习算法￡能以较大的概率(至少 1-δ) 学得目标概念c的近似 (误差最多为 ε)
  则称学习算法￡能从假设空间对中 PAC 辨识概念类 C。

• 定义2：PAC可学习
  令m表示在分布Ψ中独立同分布采样得到的样本数目。
  对0＜ε,δ＜1，对所有分布Ψ，若存在学习算法￡和多项式函数poly()，使得 对于任意m≥ploy(1/ε,1/δ,size(x),size(c))，
  有￡能从假设空间H中PAC辨识概念类C，则概念类C是PAC可学习的。
  size(x)和size(c)分别表示数据本身的复杂度和目标概念的负责度。

• 定义3：PAC学习算法
  

• 定义4：样本复杂度
  

• PAC学习理论的作用
  PAC 学习给出了一个抽象地刻画机器学习能力的框架，基于这个框架能对很多重要问题进行理论探讨。

• PAC的关键
  PAC学习的关键因素是假设空间H的复杂度。
  在现实任务中，假设空间H往往和概念类C不同，即H≠C。
  一般而言，H越大，包含任意目标概念c的可能性越大，但寻找难度随之增加。若H有限时，称H为"有限假设空间"；否则为"无线假设空间"。

12.3 有限假设空间

12.3.1 可分情形

可分情形意味着目标概念c∈假设空间H。给定m个样本的数据集D，如何找出满足误差参数ε的假设h呢？

一种策略如：由于D中的样例标记y_i是由目标概念c映射的，且c∈H，也就是说训练集D上出现了错误标记的假设h，则h肯定不是我们要的c。因此，我们只保留与D一致的假设h，剔除与D不一致的假设即可。
通常，训练集规模有限，假设空间H可能存在多个假设h与D一致，对于这些h，我们需要进一步比较，找出更优的h与目标概念c近似。

那么需要多少(m个)样本才能学得近似目标概念c的假设呢？
PAC学习中，只要训练集D的规模能使学习算法￡以概率1-δ找到目标假设的ε近似即可。最终m如下

样本数m

12.3.2 不可分情形

不可分，则说明c∉H，这是较困难的学习问题。由于c∉H，则对于任何假设h有，经验误差E^(h)≠0，即任何一个假设h都会在训练集上出现错误。

由Hoeffding不等式可知：

• 引理
  若训练集D包含m个独立同分布样本，0<ε<1，则对任意h，有

• 推论
  若训练集D包含m个独立同分布样本，0<ε<1，则对任意h，有下式以至少1-δ的概率成立：

  该式表明，样本数m越大，经验误差E^(h)与泛化误差E(h)越接近

• 定理
  若H为有限假设空间，0<δ<1，则对任意h∈H，有

• 不可知PAC学习
  当c∉H，学习算法就难以找到近似于目标概念c的h；但是在假设空间H中，一定有假设h使得泛化误差最小，找出该假设h的ε也是一个靠近c的较好的目标。

  这样子，目标就转化为在H中寻找使得泛化误差E(h)最小的假设h了。
  以此为目标可将PAC学习推广到c∉H的情况，这就是"不可知学习"。

  具体数学描述如下：
  m表示独立分布样本数目，0<ε,δ<1。
  对所有分布，若存在学习算法￡和多项式函数ploy(·,·,·,·)，
  使得对于任何样本数目m≥ploy(1/ε,1/δ,size(x),size(c))，学习算法￡能从假设空间H中得到假设h满足下式，则称H是不可知PAC学习的。

  h∈H满足该式，则称H是不可知PAC学习的

12.4 VC维

现实学习中通常面临的是无线假设空间。对此情形的学习进行研究，需要度量假设空间的复杂度。最常见的方法是考虑假设空间的"VC维"。在介绍VC维之前先介绍几个概念。

• 几个概念
  给定假设空间H和样本集D={x₁,…,x_m}，H中每个假设h都能对x_i赋予标记，所有样本的标记结果为

  m越大，所有假设对D中样本所能赋予标记的可能结果数目也随之增大。
  1）增长函数
  对所有m∈N(N是自然数域)，假设空间H的增长函数为∏_H(m)，即
  增长函数
  增长函数表示假设空间H对m个样本所能赋予标记的最大可能结果数。可能结果数越大，H表示能力越强，对学习任务的适应能力也越强。
  增长函数描述了假设空间的表示能力，由此反映出假设空间的复杂度。

  2）对分和打散
  可以用增长函数来估计经验误差与泛化误差之间的关系：
  定理1：对假设空间H，m∈N, 0<ε<1和任意h，有

  假设空间中不同的假设h对于D中样本的标记不尽相同，但即使有多个假设，对D中的样本标记的可能结果是有限的：对m个样本，最多有2^m中可能。
  对分：对二分类问题，H中的假设对D中样本赋予标记的美中可能结果称为对D的一种"对分"。如m=1，最多有2种可能，即2种对分，则其中一种"对分"，为"+"或者"-"。
  打散：若假设空间H能实现D上的所有对分，即∏_H(m)=2^m，则称D能被假设空间H"打散"。

• VC维
  假设空间H的VC维是能被H打散的最大示例集的大小，即

  VC(H)=d表明存在(不是所有)大小为d的样本集能被假设空间对打散。VC维的定义与数据分布无关；因此，在数据分布未知时仍能计算出假设空间H的VC维。
  VC维的计算如下：若存在大小为d的示例集能被H打散，但不存在任何一个大小为d+1的示例集能被对打散，则对的VC维是d。如

• VC维与增长函数的关系
  引理1：若假设空间H的VC维为，则对任意m∈N，有

• 增长函数的上界
  推论1：若假设空间H的VC维为d，则对任意整数m≥d，有

  e为自然常数

• 基于VC维的泛化误差界
  1）若假设空间H的VC维为d，则对任意m>d, 0<δ<1和h∈H，有

  基于VC维的泛化误差界，由定理1和推论1得出
  基于VC维的泛化误差界是分布无关、数据独立的。

  2）h表示学习算法￡输出的假设，若h满足下式，则称算法￡为满足经验风险最小化原则的算法。

  h满足该式，则算法ERM原则

• 定理3
  任何VC维有限的假设空间H都是不可知PAC学习的。

12.5 Rademacher复杂度

基于VC维的泛化误差界是与分布无关、数据独立的。Rademacher复杂度与VC维不同，它是另一种刻画假设空间的复杂度的途径，在一定程度上考虑了数据和分布。

• 考虑随机噪声影响的假设
  给定训练集D={(x₁,y₁),(x₁,y₁),…,(x_m,y_m)}，假设h的经验误差为

  若对所有训练样本都有h(x_i)=y_i，即经验误差为0，则有
  也就是说，经验误差最小的假设是
  但由于有一些噪声样本使得预测值y_i不是样本的真实标记。于是，H不如考虑随机噪声影响的假设，而不是使经验误差最小的假设。

  Rademacher随机变量
  Rademacher随机变量σ_i，它以1/2的概率取值-1或+1，基于σ_i，可以将目标重写为

  对于H中所有假设h，对上式取期望得
  σ={σ₁,σ₂,…,σ_m}，期望的范围在[0,1]，体现假设空间H的表现能力。

• 函数空间F关于Z的经验Rademacher复杂度
  考虑实值函数空间F和Z={z₁,z₁,…,z_m}，将X和H替换为Z和F。则有
  函数空间F关于Z的经验Rademacher复杂度

  经验Rademacher复杂度衡量了函数空间F与随机噪声在集合Z中的相关性。

• 函数空间F关于Z上分布Ψ的Rademacher复杂度
  通常我们希望了解函数空间F上在Z关于分布Ψ的相关性，因此，对所有从Ψ独立同分布采样而得的大小为m的集合Z求期望可得

  函数空间F关于Z上分布Ψ的Rademacher复杂度

• 对于回归问题的定理1
  

  函数空间F是区间[0,1]上的实值函数，因此定理1只适用于回归问题。

• 对于二分类的定理2
  

  该定理给出了基于 Rademacher 复杂度的泛化误差界。可以看出12.47式与分布有关，12.48式与数据D有关。

12.6 稳定性

算法的"稳定性"考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。
给定训练集D={z₁=(x₁,y₁),z₂=(x₂,y₂),…,z_m=(x_m,y_m)}，x_i∈X独立同分布样本，y_i∈{-1,+1}。对假设空间H和学习算法￡，令￡_D∈H表示基于训练集D从假设空间究中学得的假设。

1.对于D有定义以下两种变化：

2.损失函数

损失函数L(￡_D(x),y)刻画了假设￡_D的预测标记￡_D(x)与真实标记y_i的差别，记为L(￡_D,z)。有几种关于假设￡_D的损失：

• 泛化损失
  泛化损失
• 经验损失
  经验损失
• 留一损失
  留一损失

3.算法￡的均匀稳定性

对于任何x∈X，z=(x,y)，若学习算法￡满足下式，则称对于损失函数L，￡满足β-均有稳定性。

算法满足该式，则具有β-均有稳定性

4.学习算法￡学得的假设的泛化误差界

若损失函数L有界，即对所有D和z=(x,y)有0≤L(￡_D,z)≤M，则有以下定理：

给定m个独立同分布样本的样本集，若学习算法￡满足关于损失函数L的β均匀稳定性，且损失函数的上界为M，0 < δ < 1，则对任意m≥1，以至少 1-δ 的概率有

5.稳定性与可学习性之间的关系

• ERM原则
  对损失函数L若学习算法￡所输出的假设满足经验损失最小化，则称算法满足经验风险最小化原则，简称算法是ERM的。

• 稳定性与可学习性之间的关系

十二章思维导图

思维导图