ML——计算学习理论

基础知识

泛化误差：训练出的模型在除训练样本外的新样本集上的误差；

                        

经验误差：训练出的模型在训练集上的误差。

                 

本章后面部分将研究经验误差与泛化误差间的逼近程度，若h在数据集D上的经验误差为0，则称h与D一致，否则称其不一致。

Jensen不等式：对任意凸函数f(x)，有；

Hoeffding不等式：若为m个独立r.v.，且满足，则对任意，有

McDiarmid不等式：若为m个独立r.v.，且对任意，函数f满足：

则对任意，有：

PAC学习

PAC：概率近似正确，以比较大的把握学得比较好的模型，即以较大的概率学得误差满足预设上限的模型；

概念c：从样本空间X到标记空间Y的映射，决定示例x的真实标记y；

目标概念c：对任何样例(x,y)，有c(x)=y成立；

概念类C：所学目标概念构成的集合；

假设空间H：给定学习算法L，考虑的所有可能概念的集合；

假设h：从样本空间X到标记空间Y的映射，不确定的目标概念；

可分（一致）：若目标概念，则H中存在假设能将所有示例按与真实标记一致的方式完全分开，称该问题对学习算法L是“可分的”。

不可分（不一致）：若，则H中不存在假设能将所有示例完全正确分开，称该问题对学习算法L是“不可分的”。

PAC辨识：学习算法L能以较大的概率（至少）学得目标概念c的近似（误差最多为）。

PAC可学习：m为从分布D中独立同分布采样得到的样例数，，对所有分布D，若存在学习算法L和多项式函数poly()，使得对任何，L能从假设空间H中PAC辨识概念类C，则称概念类C对假设空间H而言是PAC可学习的。

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

假定学习算法L处理每个样本的时间为常数，则L的时间复杂度等价于样本复杂度。对算法时间复杂度的关心转化为对样本复杂度的关心。

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

若在PAC学习中假设空间和概念类完全相同H=C，则称为“恰PAC可学习”。但实际中研究的是假设空间与概念类不同的情形。一般而言，H越大，包含目标概念的可能性越大，但从中找出具体目标概念的难度越大。有限时，称H为“有限假设空间”，否则为“无限假设空间”。

有限假设空间

可分情形

可分意味着目标概念包含在算法的假设空间中，对于目标概念，在训练集D中的经验误差一定为0。一种简单的学习策略是：不断剔除出现预测错误的假设，保留经验误差为0的假设。但由于训练规模有限，假设空间中可能有多个假设在D中经验误差为0，因此将问题转化为只要训练集D的规模能使学习算法L以概率找到目标假设的近似即可。

D包含m个独立同分布采样得到的样例，对某个输出假设泛化误差大于即，且在训练集上表现完美的概率，即h与D表现一致的概率为：

则所有这样的假设出现的概率为：

即：          

可得：                        

因此，有限假设空间H都是PAC可学习的，所需样例数如上式。

不可分情形

不可分指的是目标概念不存在于假设空间中，此时学习算法L无法学得目标概念c的近似。但当假设空间H给定时，必存在一个泛化误差最小的假设，找出此假设的近似亦可。由此引申出“不可知学习”。

不可知PAC可学习：令m表示从分布D中独立同分布采样得到的样例数，，对所有分布D，若存在学习算法L和多项式函数poly()，使得对任何，L能从假设空间H中输出满足下式的假设h：

                    

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

由Hoeffding不等式知单个假设误差概率如下：

对于假设空间的所有假设，出现泛化误差与经验误差之差大于e的概率和为：

       

因此，可令不等式右边小于等于，便可求出满足泛化误差与经验误差相差小于e所需最少样本数，同时也可求出泛化误差界。

VC维

现实学习任务面临的常是无限假设空间，欲对此情形的可学习性进行研究，需度量假设空间的复杂度，此时可考虑假设空间的VC维。

给定假设空间H和示例集，H中每个假设都可对示例赋予标记，标记结果为：

增长函数：对所有，假设空间的增长函数为：

增长函数描述假设空间对示例所能赋予标记的最大可能结果数，比如说现在数据集有两个数据点，考虑一种二分类的情况，可以将其分类成A或者B，则可能的值有：AA、AB、BA和BB，所以这里增长函数的值为4。可能结果数越大，该假设空间的表示能力越强。可利用增长函数估计经验函数与泛化误差的关系：

对分：对二分类问题，H中的假设对示例赋予标记的每种可能结果称为对示例空间的一种对分（将示例集一分为二）。

打散：当假设空间H作用于大小为m的样本集D时，产生的对分数量为，即，称样本集D被假设空间H打散。

上图显示，二维空间中的三个点（不在一条直线上）可被平面上所有直线这个假设空间打散，此时，但如下图的四个点就不能被这个假设空间打散了，此时

break point：对于假设空间 H 的增长函数 ，从 m=1 出发逐渐增大，当增大到 k时，出现 的情形，则说 k是该假设空间的break point。即对于任何大小为 m(m≥k) 的数据集， H都没有办法打散它。eg当假设空间 H定义为平面上所有直线时，其break point就为4。

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

              

根据此定义，有 VC(H)=k−1，其中k是H的break point。VC维反映了函数集的学习能力，VC维越大，能学到的模型越复杂。VC维的大小与学习算法无关，与数据集的具体分布无关，与求解的目标函数也无关，只与模型和假设空间有关。另外，实践中有这样一个规律：一般情况下，假设空间的VC维约等于假设自由变量的数目。

周志华《机器学习》

https://blog.csdn.net/u011826404/article/details/73351162

https://tangshusen.me/2018/12/09/vc-dimension/

http://www.flickering.cn/machine_learning/2015/04/vc%E7%BB%B4%E7%9A%84%E6%9D%A5%E9%BE%99%E5%8E%BB%E8%84%89/