机器学习 第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能够在训练数据集中找到一个超平面，使得所有正类和负类的点都能够被正确分类，那么这个数据集就是线性可分的。

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

不可分情形

VC维

Rademacher复杂度

稳定性