11 深度学习读书笔记(2)——PAC学习框架

机器学习基础，第二章

1 什么是PAC

PAC是Probably Approximate Correct的简写，即概率近似正确。PAC框架借助样本复杂度和学习算法的时间复杂度来定义可学习的概念类。读完这章我感觉PAC可学习是一个理论用来证明哪些问题是用机器学习可解决的，关心的是能不能从假设空间中找到一个好的假设，这个“好的假设”用两个条件来表示：一个是让泛化误差小于一个很小的数$\epsilon$，这就是近似正确；然后这个近似正确的事件不用百分百成立，只要让概率接近于1($\geq 1-\delta$)就行，这两个合起来就是概率近似正确。

2 基本概念

概念(concept)$\boldsymbol{c}$：$\mathcal{X} \rightarrow\mathcal{Y}$，指一个从所有可能的样本的集合$\mathcal{X}$到所有可能的目标值的集合$\mathcal{Y}$的映射.

概念类：指的是我们可能想要学习的概念构成的集合，记为$C$。

假设集：一个固定的、由所有可能的概念组成的集合，记为$H$。

3 相关定义定理

泛化误差：给定一个假设$h\in H$，一个目标概念$c\in C$，以及一个潜在的分布$D$，则$h$的泛化误差或风险定义为

$$R(h)=\underset{x\sim D}{Pr}[h(x)\not = c(x)]=\underset{x\sim D}{E}[1_{h(x)\not = c(x)}]=\int p(x)\cdot 1_{h(x)\not = c(x)} \text{d}x$$

学习器的任务就是利用已标记的样本集$S$选择一个假设$h_s\in H$使其关于目标概念c有尽可能小的泛化误差，但是由于真实分布$D$和目标概念$c$都是未知的，所以假设泛化误差求不出来。但是学习器可以在有标签的样本集$S$上求假设的经验误差。

经验误差：给定一个假设$h\in H$，一个目标概念$c\in C$，以及一个样本集$S=(x_1,x_2,\cdots,x_m$，则$h$的经验误差或经验风险定义为

$$\hat{R}(h)=\frac{1}{m}\sum_{i=1}^m 1_{h(x_i)\not = c(x_i)}$$

对于一个固定的$h\in H$,在i.i.d.样本集上成立 $E[\hat{R}(h)]=R(h)$

---

PAC学习：$\forall \epsilon>0,\delta>0$，对于所有在$\mathcal{X}$上的分布D以及$\forall c\in C$，$\exists算法\mathcal{A}$和一个多项式函数$poly(\cdot,\cdot,\cdot,\cdot)$，当样本规模$m \geq poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c))$时，有

$$\underset{S\sim D^m}{Pr}[R(h_s)\leq \epsilon]\geq 1-\delta$$

则概念类$C$是PAC可学习(PAC-learnable)。如果$\mathcal{A}$的运行复杂度在$poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c))$内，则概念类$C$是高效PAC可学习。并且当这样的算法$\mathcal{A}$存在时，称其为$C$的一个PAC学习算法。

PAC学习的定义特别像数分中极限的定义，看到后面给的矩形的例子，发现证明过程也像，都是将定义中任意的数固定，然后构造存在的算法$\mathcal{A}$，根据定义中的不等式一步步放缩找到多项式函数$poly$，不过相比于极限的证明，这个证明中构造一个算法和不等式放缩比较难

---

学习界——有限假设集H，一致的情况：令H为一个有限的、由$\mathcal{X}$到$\mathcal{Y}$的映射函数组成的集合。令$\mathcal{A}$为学习任意目标概念$c\in H$的算法并且根据i.i.d.样本$S$返回的是一个一致的假设$h_s:\hat{R}(h_s)=0$（即假设在训练样本不会产生误差）。那么$\forall \epsilon,\delta>0$，不等式$\underset{S\sim D^m}{Pr}[R(h_s)\leq \epsilon]\geq 1-\delta$成立的条件是

$$m \geq \frac{1}{\epsilon}(\log \vert H \vert + \log \frac{1}{\delta})$$

并且对这样的样本复杂度可以得到泛化界：$\forall \epsilon,\delta>0$,以至少为$1-\delta$的概率，有

$$R(h_s) \leq \frac{1}{m}(\log \vert H \vert + \log \frac{1}{\delta})$$

这个定理说明了当假设集$H$有限时，一致算法$\mathcal{A}$是PAC学习算法，并且泛化误差的以至少为$1-\delta$误差的上界是随着样本规模m增大而减少，随着假设集的增大而增大，这也符合预期。另外也说明了泛化误差减少的速率为O(1/m)

---

学习界——有限假设集H，不一致的情况：令$H$为一个有限的假设集，则$\forall \delta>0$,以至少为$1-\delta$的概率，有：

$$\forall h \in H，R(h) \leq \hat{R}(h)+\sqrt{\frac{\log \vert H \vert + \log \frac{2}{\delta}}{2m}}$$

---

确定性情境：一个样本的标签可以有某个唯一的可测函数$f:\mathcal{X} \rightarrow \mathcal{Y}$(以概率1成立)确定时，这种情境叫做确定性情境。

随机性情境：一般的监督学习情境，分布$D$是定义在$\mathcal{X} \times \mathcal{Y}$上的，并且训练样本是根据分布$D$采样得到的i.i.d.样本$S=((x_1,x_2),\cdots,(x_m,y_m))$，学习器要解决的问题也是找到一个有较小泛化误差的假设$h \in H$：

$$R(h)=\underset{(x,y)\sim D}{Pr}[h(x)\not = y]=\underset{(x,y)\sim D}{E}[1_{h(x)\not = y}]=\int p(x,y)\cdot 1_{h(x)\not = y} \text{d}x$$

这种情况在很多实际情况中更符合，比如给定一个输入，这个输入可能对应很多个标签，但是各个标签的概率不同，所以在这种情况下，学习算法输出的标签是输入的概率函数，即$y\sim P(y \vert x)$

不可知PAC学习：令$H$为一个假设集。$\mathcal{A}$是一个不可知PAC学习算法的条件是：$\forall \epsilon,\delta>0$，对所有在$\mathcal{X \times Y}$上的分布$D$，存在一个多项式函数$poly(\cdot,\cdot,\cdot,\cdot)$，当样本规模$m \geq poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c))$时，有

$$\underset{S \sim D^m}{Pr}[R(h_s)-\underset{h \in H}{\min} R(h) \leq \epsilon] \geq 1 - \delta$$

并且如果$\mathcal{A}$的运行复杂度在$poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c))$内，则其可称为一个高效的不可知PAC学习算法。

贝叶斯误差：给定一个在$\mathcal{X} \times \mathcal{Y}$上的分布$D$，贝叶斯误差$R^$定义为由可测函数*类$h:\mathcal{X} \times \mathcal{Y}$产生的误差下界

$$R^*=\underset{h\ measurable}{\underset{h}{\inf}}R(h)$$

如果一个假设满足$R(h)=R^*$，则该假设被称为贝叶斯假设或贝叶斯分类器，记为$h_{Bayes}$，其可以由条件概率来定义

$$\forall x \in \mathcal{X}，h_{Bayes}(x)=\underset{y \in \{0,1\}}{\text{argmax}}\ Pr[y \vert x]$$

所以可以得出，$h_{Bayes}$在$x \in \mathcal{X}$的平均误差为$\min{ Pr[0 \vert x],Pr[1 \vert x] }$

噪声：给定一个在$\mathcal{X \times Y}$上的分布$D$，在样本点$x \in \mathcal{X}$上的噪声为

$$noise(x)=\min\{ Pr[0 \vert x],Pr[1 \vert x] \}$$

估计误差与近似误差：对一个假设$h \in H$的误差和贝叶斯误差的差异进行分解：

$$R(h)-R^*=\underset{估计误差}{\underbrace{(R(h)-R(h^*))}}+\underset{近似误差}{\underbrace{(R(h^*)-R^*)}}$$

其中，$h^*$表示$H$中误差最小的假设。

估计误差可以看做离假设集中最优假设的差距，学习器的任务也是来不断的减少估计误差，不可知PAC学习的定义中基于的就是估计误差；而近似误差是假设集$H$的一个性质，是无法避免的。