当前位置: 首页 > 工具软件 > PAC > 使用案例 >

【机器学习】PAC 学习理论

董桐
2023-12-01


一、计算学习理论(computation learning theory)

计算学习理论研究的是关于通过“计算”来进行“学习”的理论,即关于机器学习的理论基础,其目的是分析学习任务的困难本质,为学习算法提供理论保证,并根据分析结果指导算法设计。


二、PAC 学习(Probably Approximately Correct,概率近似正确)在干什么?

计算学习理论中最基本的是概率近似正确(Probably Approximately Correct,PAC)学习理论。
我们通过一个”猜区间“游戏来说明PAC learning是什么。

  1. Learning intervals(区间学习)

首先举一个简单的猜数游戏:

玩家1 心中默默假想一个区间[a b],同时随机地选取一个数字x。无论他怎么选择x,他都要告诉大家x是否在区间[a b]内(即a<x<b是否成立)。我们假设如果x在区间内为1,如果在区间外则为0。

玩家2 则通过玩家1 口中报出来的数字x和“1”、“0”来确定区间[a b]的值。因为玩家1 报数字的次数总归是有限(finite)的,所以很明显玩家2 几乎不可能完全的猜对a和b的值。但玩家2 可以根据玩家1 报出的新数据不断地更正自己的猜测。

极端的想象一下,如果玩家1 可以无限(infinte)次地去报数字,并且告诉大家这个数字x是否在区间内,我们就可以计算玩家 2 的区间所预测的错误结果的可能性。如果这个误差很小很小,那我们就可以说玩家2 “学习”了玩家1 的区间[a b]。也就是玩家2 猜对了!那么这个区间问题可以被称为PAC-learnable。

  1. PAC learning

讲完这个游戏,我们重新回顾一下PAC learning的全名:probably approximately correct learning。

Probably的意思是:如果玩家1 可以无限次的玩这个游戏来报数字,玩家2 就能给出一个很好的区间预测。换句话说,玩家2 可以极大可能的猜对玩家1 假象的区间[a b]

Approximately correct 的意思是:在给定新的报数后,预测区间已经十分接近于玩家1 心中的假想区间了。并且这个预测区间的误差很小很小很小…………


三、PAC 学习理论简单总结

先放PAC学习相关理论的一个总结:同等条件下,模型越复杂泛化误差越大。同一模型在样本满足一定条件的情况下,样本数量越大,模型泛化误差越小,因此还可以说模型越复杂越吃样本。


四、为什么要学习 PAC 学习理论?

此理论可以帮助我们更深入的了解机器学习的学习机制。

已经入门或者从事过一段时间机器学习相关工作的你,有没有想过为什么在训练样本上学习了一个假设(函数?模型?下文统一叫假设)就能保证这个假设在训练样本之外的数据上有效?小样本量数据为什么不适用CNN/RNN?

也就是所谓的泛化性?


五、什么是PAC学习理论?

先说一下机器学习。机器学习有两个元素:模型与数据。其中模型又包含两部分:优化算法与假设空间。所谓机器学习就是用优化算法从假设空间中选择一个假设,使此假设能符合给定的数据描述。因此优化算法通俗的讲就是假设选择算法。

而PAC学习理论不关心假设选择算法,他关心的是能否从假设空间 H 中学习一个好的假设 h 。看到 能否 二字了没?此理论不关心怎样在假设空间中寻找好的假设,只关心能不能找得到。现在我们在来看一下什么叫“好假设”?只要满足两个条件(PAC辨识条件)即可:

  1. 近似正确:泛化误差 E(h) 足够小
    E(h) 越小越好,最好泛化误差能等于0,但一般是不可能的。那我们就把 E(h) 限定在一个很小的数 η之内,即只要假设 h 满足 E(h) < η ,我们就认为 h 是正确的。
  2. 可能正确
    不指望选择的假设 h 百分之百是近似正确的(按上段所述,即 E(h) < η ),只要 很可能 是近似正确的就可以,即我们给定一个值 μ ,假设 h 满足 P(h近似正确)>=1-μ。

综上两点,就得到了PAC(可能近似正确,probably approximate correct)可学习的定义。简单的讲就是模型在短时间内利用少量的(多项式级别)样本能够找到一个假设 h ,使其满足 P(E(h) < η) >=1-μ,其中0<η,μ<1。


参考链接

  1. 周志华《机器学习》西瓜书
  2. https://zhuanlan.zhihu.com/p/34687134
  3. 30分钟了解PAC学习理论——计算学习理论第一讲
 类似资料: