这一章全是理论知识和公式，个人感觉有点难。这一章主要介绍了计算学习理论，即如何判断一个算法能否得到目标概念类，针对一个算法得到的假设空间分为有限和无限，而有限分为两种情形为可分和不可分；无限则需要研究它的vc维或Rademacher复杂度来进行判断分析。

12.1基础知识

计算学习理论关于计算器学习的理论基础，其目的是分析学习任务的困难本质。

泛化误差：学习器在整个样本空间上的误差。
经验误差：学习器在训练集上的误差。
因为D是独立同分布采样，所以h 的经验误差的期望等于其泛化误差。

不合disagreement：

常用不等式

Jensen不等式
Hoeffding不等式
McDiarmid不等式

常用不等式.PNG

12.2概率近似正确(PAC)学习

基础定义

概念c：从样本空间到标记空间的映射。
目标概念：对于任何样例(x,y)，成立的c。
概念类C：包含目标概念的集合。
假设h：学习算法得出的从样本空间到标记空间的映射。
假设空间H：学习算法包含的所有假设的集合。

算法的可分与不可分

若目标概念c∈H，则H中存在假设可以将所有示例按与真实标记一致的方式完全分开，称该问题对学习算法是“可分的”，亦称“一致的”。
若c∉H，则H中不存在任何假设能将所有示例完全正确分开，称该问题对学习算法是“不可分的”亦称“不一致的”。

PAC辨识

对0<，<1，所有c∈C和分布，若存在学习算法，其输出假设h∈H满足
则称学习算法能从假设空间H中PAC辨识概念类C.

PAC可学习

将样本考虑进来，若样本数量达到某一数量时，则算法总能PAC辨识概念类，称为PAC可学习的。

PAC可学习.png

PAC学习算法

连运行时间也考虑进来，当运行时间为多项式函数，则称概念类C是高效PAC学习可学习的，称为概念类C的PAC学习算法。
【注：为复杂度】

样本复杂度

满足PAC学习算法所需的m≥中最小的m，称为学习算法的样本复杂度。

12.3有限假设空间

有限假设空间：|H|中假设有限。该假设空间可能包含有目标概念称为可分情形，若假设空间没有包含目标概念则称为不可分情形。
无限假设空间：|H|中有无限个假设。该假设中一定有目标概念。

可分情形

我们要如何从假设空间中学得目标概念呢？
可以通过训练集来排除那些不符合的假设，直到只剩下一个假设时，它就是目标概念。但是实际上我们可能得到多个经验误差为0的假设。这个时候就没办法进一步区分了。所以我们需要越来越多的训练样本才能更好的区分，如果训练样本就是样本集合，那么我们就一定可以得到目标概念。

那么需要多少训练样本才可以得到目标概念有效近似呢？
对PAC学习来说，只要训练集D的规模能使学习算法以概率找到目标假设的近似即可。

推导过程和结论.PNG

不可分情形

不可分情形说明假设空间中并没有目标概念，但是我们却可以找出其中泛化误差最小的假设也不失为一个好的目标，这就是不可知学习的来源。

推论定理.png

定理.png

不可知PAC可学习

若存在学习算法满足则称假设空间H是不可知可学习的。

当学习算法的运行时间也是多项式函数，则称假设空间H是高效不可知PAC可学习的。

12.4VC维

对于无限的假设空间，要先研究其可学习性，需要度量假设空间的复杂度，而度量空间复杂度的常用方法是考虑空间的VC维。

增长函数

假设h对D中示例的标记结果为：对所有，假设空间增长函数为：表示假设空间H对m个示例所能赋予标记的最大可能结果数，值越大说明该假设空间的表示能力越强。

对分和打散

尽管H中有无限个假设，但其对D中示例赋予标记的可能结果是有限的。
对分：对二分类问题来说，假设对D中示例赋予标记的每种可能结果称为对D的一种对分。
打散：若假设空间H能实现示例集D上的所有对分，即，则称示例集D能被假设空间H“打散”。

VC维

假设空间H的VC维是能被H打散的最大示例集的大小，即
【注：并非所有的大小为d的示例集都能被假设空间打散】

增长函数的上界与假设空间的VC维有关：

引理12.2.png

分布无关(数据独立)性：VC维的泛化误差只与样例数目m有关，收敛速率为，与数据分布无关。
任何VC维有限的假设空间H都是(不可知)PAC可学习的。

12.5Rademacher复杂度

基于VC维的泛化误差界是分布无关、数据独立的，也就是对任何分布都成立，所以它得到的泛化误差界比较的“松”的。
Rademacher复杂度是另一种刻画空间复杂度的途径，它在一定程度上考虑了数据分布。

Rademacher复杂度对h的经验误差进行了一点小的改变，引入了Rademacher随机变量。

Rademacher推导过程.PNG

定义12.8.png

定义12.9.png

回归问题泛化误差界.png

二分类问题的泛化误差.png

定理12.7.png

12.6稳定性

稳定性分析可以获得宇算法有关的分析结果，主要考察算法在输入发生变化时，输出是否发生较大变化。

算法输入的变化主要有以下两种：
表示移除D中第i个样例得到的集合。
表示替换D中第i样例得到的集合。

关于假设的几种损失

三种损失.png

算法的均匀稳定性

均匀稳定性.png

若学习算法所输出的假设满足经验损失最小化，则称为算法满足经验风险最小化(ERM)原则，简称算法是ERM的。

【注：经验风险最小化(ERM)原则，即算法输出的假设h为假设空间中经验误差最小的假设】

稳定性通过损失函数将学习算法和假设空间联系起来，区别在于：
假设空间关注的是经验误差与泛化误差，需要考虑到所有可能的假设：
稳定性只关心当前的输出，只要当前输出满足经验损失最小即可：
若学习算法是ERM且稳定的，则假设空间H可学习。

参考：https://blog.csdn.net/cristianojason/article/details/79057977
https://blog.csdn.net/Julialove102123/article/details/79983545