PAC概率近似正确学习模型

作者: 闪电侠悟空 | 来源:发表于2021-02-05 10:47 被阅读0次

集成学习-提升（boosting）方法
PAC概率近似正确学习模型
【机器学习】（七）马尔可夫链、马尔可夫随机场、条件随机场
数据挖掘之Boosting&AdaBoost
统计学习方法1.1-1.3 笔记
马尔科夫链蒙特卡罗法
机器学习熵的整理
机器学习模型比较
Day 2080：学习
简单理解PRF

《Understanding Machine Learning-From Theory to Algorithms》
第二章，最后一段关于predictor 失败的分析

一个upper bound的推导和理解

有了精度参数 $\epsilon$ , 我们就可以定义失败的假设 $L_{(D,f)}(h_S)>\epsilon$ . 我们有m个训练样本 $(x_1,...,x_m)$ ，是通过采样产生的，组成了样本集合 $S$ 。不同人/时间，采样的结果是不一样的，就有不同的样本集合，比如有 $S_1, S_2, ...,S_N$ . 这些样本集合有多大概率产生失败的predictor呢？记训练实例集为 $S|x=(x_1,...,x_m)$ . 我们关心的是下面概率的上界。

$D^m(\{S|x:L_{(D,f)}(h_S)>\epsilon\})$ #m-组实例采样中导致失败预测器的概率。

怎么算这个上界 upper bound?

引入bad hypothesis set的集合
$\mathcal{H}_B =\{h\in \mathcal{H}:L_{(D,f)}(h)>\epsilon\}$ .
从bad hypothesis出发，定义数据误导集
$M=\{S|x:\exists h \in \mathcal{H}_B,L_S(h)=0 \}$
也就是误导集是依赖bad hypothesis的，不同的 $h_B$ 会有不同的误导集，整个误导集是所有bad hypothesis的并集。
回到关注的问题中的集合 $\{S|x:L_{(D,f)}(h_S)>\epsilon\}$ , 这个集合等价于：
$\{S|x:L_{(D,f)}(h)>\epsilon,L_S(h)=0\}$ ,继续等价于：
$\{S|x:h \in \mathcal{H}_B,L_S(h)=0\}$ ，子集关系就出来了：
$\{S|x:L_{(D,f)}(h_S)>\epsilon\}\subseteq M$ , 这个集合只是误导集的子集而已。
概率不等关系也就出来了：
$D^m(\{S|x:L_{(D,f)}(h_S)>\epsilon\})\leq D^m(M)$
从第2点中可以看出 $M$ 还是个并集。 $M = \mathop{\cup}_{h\in\mathcal{H}_B}\{S|x:L_S(h)=0\}$ 。利用联合界的方式缩放：
$D^m(M)\leq\mathop{\Sigma}_{h\in\mathcal{H}_B} D^m(\{S|x:L_S(h)=0\})$ .
固定某个"bad"假设，展开：
$D^m(\{S|x:L_S(h)=0\})=D^m(\{S|x:\forall i, h(x_i)=f(x_i)\})=\mathop{\Pi}_{i=1}^m D(\{x_i: h(x_i)=f(x_i)\})$
对于每个sample, $D(\{x_i: h(x_i)=f(x_i)\})=1-L_{(D,f)}(h)\leq 1-\epsilon\leq e^{-\epsilon}$ ，注意第6步中使用的bad hypothesis, 所以不等式成立。
所以整个的上界upper bound
$D^m(\{S|x:L_{(D,f)}(h_S)>\epsilon\})\leq |\mathcal{H}|e^{-\epsilon m}$
说明：

假设空间很小 $|\mathcal{H}|=1$ , 训练样本量 $m$ 只需要很少；但是由于实际问题的复杂性， $|\mathcal{H}|$ 必须要很大(比如深度学习)。为了控制这个upper bound, 就必然要求大的 $m$ ，大数据量。
精度参数 $\epsilon$ 是一个要求指标，精度需求越高， $\epsilon$ 越小，实现相同的upper bound，就需要更大的 $m$ ，数据量和精度有关系。通过数据增强提高分类精度，这个公式也可以看出端倪。
算法理论分析的牛逼之处在于：给定少量的假设条件，就能够分析出关键配置对性能影响关系。

推论2.3

假设 $m\geq \frac{log(|\mathcal{H}|/\delta)}{\epsilon}$

$D^m(\{S|x:L_{(D,f)}(h_S)>\epsilon\})\leq |\mathcal{H}|e^{-\epsilon m}\leq \delta$

说明：在m足够大的时候，在独立同分布的样本集S上，最少以 $1-\delta$ 的大概率保证 $h_S$ 有效，即 $L_{(D,f)}(h_S)\leq \epsilon$ .

集成学习-提升（boosting）方法
1 提升方法 1.1 概率近似正确（PAC）学习框架在概率近似正确（PAC）学习框架中，一个概念，如果存在一个多...
PAC概率近似正确学习模型
《Understanding Machine Learning-From Theory to Algorithms...
【机器学习】（七）马尔可夫链、马尔可夫随机场、条件随机场
概率模型与概率图模型概率模型概率模型（probabilistic model）提供了一种描述框架，将学习任务归...
数据挖掘之Boosting&AdaBoost
大纲：Boosting介绍AdaBoost 算法 1. 背景知识（1）PAC学习模型（Probability A...
统计学习方法1.1-1.3 笔记
1.1 统计学习方法分类按模型分类：概率模型：条件概率分布表达的模型。x为条件，y的概率分布。决策树、朴素贝叶...
马尔科夫链蒙特卡罗法
蒙特卡罗法（Monte Carlo Method）也称为统计模拟方法，是通过概率模型的随机抽样进行近似数值计算的方...
机器学习熵的整理
1.近似熵：近似熵能够衡量时间序列中产生新模式的概率大小，产生新模式的概率越大，序列就越复杂。由于近似熵的计...
机器学习模型比较
判别模型与生成模型生成模型学习联合概率分布，求出条件概率分布P(Y|X)=P(X,Y)/P(X)。朴素贝叶斯法、...
Day 2080：学习
#统计学习最大熵模型：由最大熵原理推导而得最大熵原理是概率模型学习的一个准则，它认为所有可能的概率模型中，熵最...
简单理解PRF
精准率模型输出的结果是正确的概率召回率模型中原本应该输出的结果是实际输出的概率混淆矩阵精准率计算公式召...