机器学习 第12章 计算学习理论

基础知识

计算学习理论研究的是关于通过"计算"来进行"学习"的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
给定样例集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m ) } D=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\} D={(x1​,y1​),(x2​,y2​),…,(xm​,ym​)},$x_iϵ\chi$,假设$\chi$中的所有样本服从一个隐含未知的分布$\mathcal{D}$, D 中所有样本都是独立地从这个分布上采样而得.

PAC学习

计算学习理论中最基本的是概率近似正确 (Probably Approximately Correct，简称 PAC)学习理论 。下面介绍几个定义

定义1：PAC辨识：对$0<ϵ$,$\delta <1$,所有$cϵ\mathcal{C}$和分布$\mathcal{D}$，若存在学习算法$\varsigma$，其输出假设$hϵ\mathcal{H}$满足$$P(E(h)\le ϵ)\ge 1-\delta$$,则称学习算法$\varsigma$能从假设空间中PAC辨识概念类$C$
定义2：PAC可学习：令m表示从分布D中独立同分布采样得到的样例数目，$0<ϵ$,$\delta <1$，对所有分布T，若存在学习算法$\mathcal{L}$和多项式函数poly(…),使得对任何$m\ge poly\left(1/ϵ,1/\delta ,size\left(x\right),size\left(c\right)\right)$,$\mathcal{L}$能从假设空间$\mathcal{H}$中PAC辨识概念类$\mathcal{C}$，则称概念类$\mathcal{C}$对假设空间而言是PAC可学习的。

PAC 学习中一个关键因素是假设空间$\mathcal{H}$的复杂度。$\mathcal{H}$包含了学习算法$\epsilon$所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即$\mathcal{H}$=$\mathcal{C}$，这称为"恰PAC可学习"，这意味着学习算法的能力与学习任务"恰好匹配"。

有限假设空间

有限假设空间是指假设空间中的假设数目是有限的。在这种情况下，可以更容易地分析学习算法的表现。对于有限假设空间，根据是否能找到一个假设完全匹配训练数据，可以分为可分情形和不可分情形。

可分情形

在机器学习中，“可分情形”指的是存在一个假设（即学习算法中的模型）可以在训练数据集上达到零误差，即这个假设能够完全正确地标记所有训练样本。当这种情况发生时，我们说训练数据集对于这个假设空间是“可分的”。

在可分情形下，学习算法的目标是找到这个假设，也就是找到一个决策边界或分类规则，使得所有训练样本都能够被正确分类。例如，在二分类问题中，如果存在一条超平面（在高维空间中也称为超平面）能够完美地将两类数据分开，那么这个问题就是线性可分的。
判断数据集是否线性可分可以通过以下几种方法：
可视化: 如果数据集维度较低（如二维或三维），可以通过绘制数据集的散点图来直观地判断是否线性可分6。
SVM: 使用支持向量机(Support Vector Machine, SVM)，如果SVM能够在训练数据集中找到一个超平面，使得所有正类和负类的点都能够被正确分类，那么这个数据集就是线性可分的。

在可分情形下，学习算法的目标非常明确，就是要找到一个能够在训练集上达到零误差的假设。这种情况下，学习算法通常会表现得非常好，因为它不需要处理噪声或异常值所带来的影响。然而，值得注意的是，在实际应用中，数据往往含有噪声或不一致之处，因此很少能够遇到真正的可分情形，更多的是处理不可分情形，这时就需要引入如正则化等技术来改善模型的泛化能力。

不可分情形

在某些情况下，学习算法可能无法准确地学习到目标概念，尤其是在概念本身不在假设空间内的时候。然而，即便在这种情况下，学习算法也可以尝试找到一个接近最优解的假设。这就是所谓的不可知学习（Agnostic Learning）。不可知PAC学习允许算法在假设空间中寻找一个假设，即使这个假设不是最优的，但却是对于当前假设空间而言最好的。定义中指出，如果对于所有的分布，存在一个学习算法能够在多项式时间内找到一个近似的假设，使得经验误差和泛化误差之差不超过一个给定的界限，则假设空间是不可知PAC可学习的。

VC维

定义：VC维是统计学习理论中的一个重要概念，。对于一个二分类问题，如果存在h个样本能够被假设空间中的函数按照所有可能的$2^h$种形式分开（即打散），则称假设空间能够把h个样本打散。假设空间的VC维就是它能打散的最大样本数目h。如果对于任意数目的样本都有函数能将它们打散，则假设空间的VC维是无穷大。

意义：VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大）。所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的VC维，可以使学习机器在整个样本集上的期望风险得到控制。

稳定性

稳定性是衡量学习算法对输入数据微小变化的敏感程度。稳定的算法在输入数据发生微小变化时，输出结果的变化也很小。稳定性与可学习性之间存在着密切的关系，因为一个稳定的算法往往有更好的泛化能力。通过分析算法的稳定性，可以推断算法的可学习性。