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

基础知识

计算学习理论研究的是关于通过"计算"来进行"学习"的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
给定样例集 $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\}$ , $x_{i}\epsilon \chi$ ,假设 $\chi$ 中的所有样本服从一个隐含未知的分布 $\mathcal{D}$ , D 中所有样本都是独立地从这个分布上采样而得.

PAC学习

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

定义1：PAC辨识：对 $0<\epsilon$ , $\delta <1$ ,所有 $c\epsilon \mathcal{C}$ 和分布 $\mathcal{D}$ ，若存在学习算法 $\varsigma$ ，其输出假设 $h\epsilon \mathcal{H}$ 满足 $P(E(h)\le \epsilon )\ge 1-\delta$ ,则称学习算法 $\varsigma$ 能从假设空间中PAC辨识概念类 $\mathrm {} C$
定义2：PAC可学习：令m表示从分布D中独立同分布采样得到的样例数目， $0<\epsilon$ , $\delta <1$ ，对所有分布T，若存在学习算法 $\mathcal{L}$ 和多项式函数poly(…),使得对任何 $m\ge poly\left ( 1/\epsilon ,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}$ 包含了学习算法 $\varepsilon$ 所有可能输出的假设，若在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维，可以使学习机器在整个样本集上的期望风险得到控制。