基础知识

计算学习理论是机器学习的理论基础，其目的是分析学习任务的困难本质，并根据分析结果指导算法设计。例如：在什么条件下可进行有效的学习，需要多少训练样本能获得较好的精度等，从而为机器学习算法提供理论保证。
其对于机器学习，极具重要性。
给定数据集 , 假设所有样本独立同分布,并服从分布.
令为的映射,则泛化误差为:

PAC学习

PAC理论（Probably Approximately Correct）是学习理论中最基本的理论。
一些定义：
1、概念：令表示“概念”，它代表从样本空间 到标记空间 的映射,若有对任何样例有,则称为目标概念, 所有目标概念的集合称为概念类；
2、假设空间：设为学习算法, 其能表示的所有可能概念的集合称为假设空间，以表示，由于通常不同, 所以对于我们不确定其是否为目标概念,则称之为假设（hypothesis）；
3、可分的：若假设空间存在至少一个目标概念, 则称该问题对算法可分,一致, 否则即为不可分,不一致。
显然，我们希望学习算法学到的h尽可能接近c,即希望以较大的概率学习到误差满足预设上限的模型，也就是“概率”“近似正确”的含义。
有了上面的概念，给定置信度，误差参数,我们定义:

• PAC辨识: 对, , 所有和分布, 若存在学习算法, 其输出的假设 满足:

  
  其中可以理解为一种置信度。

• PAC可学习：在PAC辨识的基础上，令m表示从分布中独立同分布采样得到的样例数目，, ,对所有分布，若存在学习算法和多项式函数poly(·,·,·,·)，使得对于任何,能从假设空间中PAC辨识概念类，则称概念类对于假设空间来说是PAC可学习的。

• PAC学习算法：若学习算法使概念类为PAC可学习的，且算法的运行时间也是多项式函数,则称概念类是高效PAC可学习的，也称算法为概念类的PAC学习算法。

• 样本复杂度：满足PAC学习算法所需的中最小的m，称为学习算法的样本复杂度。
  简单地概括一下上述的四个概念：
  1、若算法足够优秀，使得误差大概率下足够小，那么目标概念类对于算法来说是PAC可辨识的；
  2、若采样数目大于一定阈值，概念类一定能被算法PAC辨识，那么概念类对于算法来说是PAC可学习的；
  3、若算法的时间复杂度也在一定范围内（多项式函数poly），算法就是概念类的PAC学习算法；
  4、PAC学习算法所需的最小样本数m被称为算法的样本复杂度。

显然PAC学习给出了一个抽象地刻画机器学习能力的框架，基于此框架能对很多重要的问题进行讨论，例如研究任务再什么样条件下可学得较好的模型？某算法在怎样的条件下可进行有效学习？需要多少训练样例才能获得较好的模型？$

PAC学习的一个关键因素是假设空间的复杂程度，于是我们将对是否有限进行讨论。

有限假设空间

可分情况

可分情形意味着目标概念属于假设空间，给定包含m个样例的训练集D，其中一个简单的学习策略：D中的样例标记都是由概念类赋予的，且c存在于H中，那么任何在D中出现的标记错误的假设肯定不是目标概念c.

不可分情况

此时目标概念不在假设空间中，我们可以证明：
从上式看出，我们可以学得一个泛化误差最小的假设。如此我们将PAC学习推广到的情况，即不可知PAC可学习。

VC维

在现实任务中，我们通常面临的都是无限假设空间，于是我们常用的工具便是假设空间的VC维。
在介绍VC维之前，先来了解几个概念：
1、增长函数：表示假设空间H对m个示例所能赋予标记的最大可能结果数n的映射关系。增长函数能够体现假设空间的表达能力和复杂度, 有定理如下:

2、对分：对于二分类问题来说，H中的假设对D中示例赋予标记的每种可能结果称为对D的一种对分。
3、打散：若假设空间能够实现示例集D上的所有对分，即对于m个示例的样本集D的增长函数等于，则称示例集D能被假设空间H打散。

有了以上的概念，便可以开始讨论VC维了，假设空间的VC维是能被假设空间H打散的最大示例集的大小：
,其中VC(H)=d表示存在大小为d的示例集能被打散，但不代表所有大小为d的示例集都能被打散。于是看得出，VC维的定义和分布无关，通常我们用大小为d的示例集能被打散，而d+1的数据集不能用来计算VC维。
由上面的定义可知，VC维与增长函数有密切联系，以下给出了二者之间的定量关系：.
于是计算出增长函数的上界：.
然后得到基于VC维的泛化误差：.
于是我们可以得出以下定理：

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

Rademacher复杂度

基于 VC 维的泛化误差界是分布无关、数据独立的，也就是说对于任意的数据分布都成立。但就是因为没有考虑到数据本身，基于VC维得到的泛化误差界通常比较松散，对于那些与学习问题的典型问题情况相差甚远的较坏分布来说尤其如此。
Rademacher复杂度是另一种刻画假设空间复杂度的途径，与 VC 维不同，它在一定程度上考虑了数据分布。

• 机器学习算法的性能体现在其泛化误差足够小，但是现实中泛化误差往往求不得，一般用经验误差来进行近似。
• 考虑噪音对假设空间性能影响，用Rademacher复杂度计算引入Rademacher随机变量来代替训练样本中的标记，以0.5概率为-1，0.5概率为+1.
• 在一个确定的训练集上，经验Rademacher复杂度其实计算的是假设空间与随机噪音相关性的期望，期望值越大，则假设空间与随机噪音拟合得越好，即也说明假设空间越复杂。
• 假设训练集样本自分布D，则Rademacher复杂度是f分布D上的经验Rademacher复杂度的期望。
• 于是通过Rademacher复杂度，我们可以计算出基于Rademacher复杂度的泛化误差界。

稳定性

算法稳定性考察的是算法在输入发生变化时，输出是否也会跟着发生变化。
给定D是来自分布的独立同分布示例，对于假设空间，和学习算法，且令表示基于训练集从假设空间中学到的假设。考虑D的以下变化：

• 表示移除第个样本后的集合

• 表示替换D中第个样例得到的集合

定义损失函数：
1、泛化损失：
2、经验损失：
3、留一损失：
下面定义算法的均匀稳定性：
对于任何,若算法满足：.
则称学习算法关于损失函数满足——均匀稳定性。

稳定性分析关注的是：.
而假设空间复杂度分析关注的是：.

稳定性和可学习性之间的关系：
若学习算法是ERM且稳定的，则假设空间可学习。即若学习算法符合经验风险最小化原则（ERM）且满足β-均匀稳定性，则假设空间是可学习的。
ERM指的是经验风险最小化，即学习算法输出的假设满足经验损失最小化。
稳定性与假设空间并非无关，两者通过损失函数联系起来。即有稳定性通过损失函数与假设空间的可学习联系在了一起，区别在于：假设空间关注的是经验误差与泛化误差，需要考虑到所有可能的假设；而稳定性只关注当前的输出假设。