机器学习 第12章 计算学习理论
目录
- 基础知识
- PAC学习
- 有限假设空间
- 可分情形
- 不可分情形
- VC维
- 稳定性
基础知识
计算学习理论研究的是关于通过"计算"来进行"学习"的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
给定样例集 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 ϵ χ x_{i}\epsilon \chi xiϵχ,假设 χ \chi χ中的所有样本服从一个隐含未知的分布 D \mathcal{D} D, D 中所有样本都是独立地从这个分布上采样而得.
PAC学习
计算学习理论中最基本的是概率近似正确 (Probably Approximately Correct，简称 PAC)学习理论 。下面介绍几个定义
定义1：PAC辨识：对 0 < ϵ 0<\epsilon 0<ϵ, δ < 1 \delta <1 δ<1,所有 c ϵ C c\epsilon \mathcal{C} cϵC和分布 D \mathcal{D} D，若存在学习算法 ς \varsigma ς，其输出假设 h ϵ H h\epsilon \mathcal{H} hϵH满足 P ( E ( h ) ≤ ϵ ) ≥ 1 − δ P(E(h)\le \epsilon )\ge 1-\delta P(E(h)≤ϵ)≥1−δ,则称学习算法 ς \varsigma ς能从假设空间中PAC辨识概念类 C \mathrm {} C C
定义2：PAC可学习：令m表示从分布D中独立同分布采样得到的样例数目， 0 < ϵ 0<\epsilon 0<ϵ, δ < 1 \delta <1 δ<1，对所有分布T，若存在学习算法 L \mathcal{L} L和多项式函数poly(…),使得对任何 m ≥ p o l y ( 1 / ϵ , 1 / δ , s i z e ( x ) , s i z e ( c ) ) m\ge poly\left ( 1/\epsilon ,1/\delta ,size\left ( x \right ),size\left ( c \right ) \right ) m≥poly(1/ϵ,1/δ,size(x),size(c)), L \mathcal{L} L能从假设空间 H \mathcal{H} H中PAC辨识概念类 C \mathcal{C} C，则称概念类 C \mathcal{C} C对假设空间而言是PAC可学习的。
PAC 学习中一个关键因素是假设空间 H \mathcal{H} H的复杂度。 H \mathcal{H} H包含了学习算法 ε \varepsilon ε所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即 H \mathcal{H} H= C \mathcal{C} C，这称为"恰PAC可学习"，这意味着学习算法的能力与学习任务"恰好匹配"。
有限假设空间
有限假设空间是指假设空间中的假设数目是有限的。在这种情况下，可以更容易地分析学习算法的表现。对于有限假设空间，根据是否能找到一个假设完全匹配训练数据，可以分为可分情形和不可分情形。
可分情形
在机器学习中，“可分情形”指的是存在一个假设（即学习算法中的模型）可以在训练数据集上达到零误差，即这个假设能够完全正确地标记所有训练样本。当这种情况发生时，我们说训练数据集对于这个假设空间是“可分的”。
在可分情形下，学习算法的目标是找到这个假设，也就是找到一个决策边界或分类规则，使得所有训练样本都能够被正确分类。例如，在二分类问题中，如果存在一条超平面（在高维空间中也称为超平面）能够完美地将两类数据分开，那么这个问题就是线性可分的。
判断数据集是否线性可分可以通过以下几种方法：
可视化: 如果数据集维度较低（如二维或三维），可以通过绘制数据集的散点图来直观地判断是否线性可分6。
SVM: 使用支持向量机(Support Vector Machine, SVM)，如果SVM能够在训练数据集中找到一个超平面，使得所有正类和负类的点都能够被正确分类，那么这个数据集就是线性可分的。
在可分情形下，学习算法的目标非常明确，就是要找到一个能够在训练集上达到零误差的假设。这种情况下，学习算法通常会表现得非常好，因为它不需要处理噪声或异常值所带来的影响。然而，值得注意的是，在实际应用中，数据往往含有噪声或不一致之处，因此很少能够遇到真正的可分情形，更多的是处理不可分情形，这时就需要引入如正则化等技术来改善模型的泛化能力。
不可分情形
在某些情况下，学习算法可能无法准确地学习到目标概念，尤其是在概念本身不在假设空间内的时候。然而，即便在这种情况下，学习算法也可以尝试找到一个接近最优解的假设。这就是所谓的不可知学习（Agnostic Learning）。不可知PAC学习允许算法在假设空间中寻找一个假设，即使这个假设不是最优的，但却是对于当前假设空间而言最好的。定义中指出，如果对于所有的分布，存在一个学习算法能够在多项式时间内找到一个近似的假设，使得经验误差和泛化误差之差不超过一个给定的界限，则假设空间是不可知PAC可学习的。
VC维
定义：VC维是统计学习理论中的一个重要概念，。对于一个二分类问题，如果存在h个样本能够被假设空间中的函数按照所有可能的 2 h 2^{h} 2h种形式分开（即打散），则称假设空间能够把h个样本打散。假设空间的VC维就是它能打散的最大样本数目h。如果对于任意数目的样本都有函数能将它们打散，则假设空间的VC维是无穷大。
意义：VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大）。所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的VC维，可以使学习机器在整个样本集上的期望风险得到控制。
稳定性
稳定性是衡量学习算法对输入数据微小变化的敏感程度。稳定的算法在输入数据发生微小变化时，输出结果的变化也很小。稳定性与可学习性之间存在着密切的关系，因为一个稳定的算法往往有更好的泛化能力。通过分析算法的稳定性，可以推断算法的可学习性。