第三章 PAC leaning 'Why machine can learning'

在第二章里我们学到了有限假设集

回顾：

经验风险：Ls代表了在假设为h的情况下损失的表达式

可以选择使得经验风险最小化的假设，作为选择的假设

当H是有限集的时候，模型不会有过拟合的风险，并且如果ERM是在这个有限集中被提供了大量数据的话，可以认为最后得到的假设是一个概率近似准确的假设（PAC（Probably Approximately Correct））

PAC learninability 的定义:

$\exists m_h : (0,1)^2 \rightarrow N$ 以及一个具有如下条件的学习算法： $\forall \epsilon,\delta \in (0,1)\, and\; for\,every\,\mathcal{D\,} over\mathcal{X\,},and \,for \, every\,label\,function\;f:\mathcal{X}\rightarrow \,\{0,1\}$

如果训练过程满足以上 $\mathcal{H,D,f}$ ，即样本采样自分布 $\mathcal{D}$ ,真正的映射关系是 $\mathcal{f}$ ，那么最后预估出来的假设h以至少 $1-\delta$ 的概率使得 $L_{(D,f)}(h)<\epsilon$

这个定义中， $\epsilon$ 衡量了最后学习出来的h有多接近f，即h的准确度。 $\delta$ 衡量了h接近 $\epsilon$ 的置信度。实际上，因为尽管训练集可以采样再多来自真实分布的样本，但毕竟不能用这些大量的数据去完全代表真实的分布，那么采用这个训练集去训练或多或少会有一些偏差，所以上面的两个参数，在实际训练中都是不可避免的会遇见的。而 $\epsilon$ 可以让看作学习过程中的少量偏差的接受程度。

$m_h : (0,1)^2 \rightarrow N$ 决定了学习过程中的采样复杂度，换句话说，这个方程可以看作是，为了保证PAC的话，至少需要采样多少样本。实际训练中，其实上m的方程有很多都是满足条件的，一般选择最小的m满足 $\epsilon$ ， $\delta$ 的PAC学习。

一般情况下这个m可以被一个关于， $\epsilon$ ， $\delta$ 的方程bound住

对于任意有限假设集，都存在这样的一个m满足要求

General Learning Model：

刚才描述的模型其实很容易推广，可以通过以下两个角度让模型更加一般化

1，删除可实现性假设：上面的PAC模型所需要的条件其实是非常强的，不仅需要在真实分布中采样，而且标注的内容也需要十分准确。下面会介绍Agnostic PAC模型

2，之前介绍的基本都是二分类模型，模型其实可以被推广到各类学习任务当中

Agnostic PAC：

在第一章里面做了这样的一个假设，

$\exists h^{\star} \in \mathcal{h} \; such\,that\, \mathbb{P}_{x\sim\mathcal{D}}[h^\star(x) = f(x)] = 1$ 这个假设在很多现实问题里面是不成立的，那么更现实的假设是什么呢？

现在设定 $\mathcal{D}$ 为x,y的联合分布（之前可以看作是训练数据的真实分布） $\mathcal{D}_x$ 是 $\mathcal{D}$ 的边缘分布，代表没标注的x的分布，D((x,y)|x)代表label y 的条件分布。这样去设计模型实际上允许不同的数据具有相同的特征时，属于不同的预测结果。

这样假设的情况下，误差将会被写成如下的形式：

跟之前PAC不同的点就是，在这里括号里不是h(x) 不等于 f(x)

同理，经验风险如下：

同上

最后编辑于：2019.04.11 16:34:44