这篇文章主要总结 PAC 学习框架以及样本复杂度相关的东西，大致来说就是:要保证以概率 $1-\delta$ 使得 generalized error 小于 $ϵ$ 需要多大的样本复杂度，以及时间复杂度才是好的。
 
 
问题及约定
 
 
符号约定
 
 
两个 error 符号
 
 
就是我们常说的 train error 与 true error
 
接下来是定义我们要研究的问题
 
 
简单的来说就是 依赖于 $m,H,ϵ,\delta$ 这四个东西，我们找到一个 样本复杂度以及计算复杂度的界.或者说找到他们的一些关系
 
定义
 
consistent hypothesis:
 
$consistent(h,S)|=h(x)=c(x),\forall (x,c(x))\in S$
 
一个 假设称为是 consistent 的，if and only if, $\forall (x,c(x))\in S$ 都有，$h(x)=c(x)$
 
Version Space:
 

    
     
      
       
        V
       
       
        
         S
        
        
         
          H
         
         
          ,
         
         
          S
         
        
       
       
        :
       
       
        {
       
       
        h
       
       
        ∈
       
       
        H
       
       
        ∣
       
       
        c
       
       
        o
       
       
        n
       
       
        s
       
       
        i
       
       
        s
       
       
        t
       
       
        e
       
       
        n
       
       
        t
       
       
        (
       
       
        h
       
       
        ,
       
       
        S
       
       
        )
       
       
        }
       
      
      
       VS_{H,S}:\{h \in H|consistent(h,S)\}
      
     
    VSH,S​:{h∈H∣consistent(h,S)}
 
$ϵ-exhausted$
 
$V{S}_{H,S}$ 称为 $ϵ-exhausted$,当且仅当,
 
$\forall h\in H,erro{r}_D(h)<ϵ$
 
throme
 
 
这个定理的证明会在文末给出，接下来的核心就在于理解这个定理
 
理解
 
这个定理的前提:
 
$Hfinite$
$c\in H$
 
注意这个定理说的是 not，将这个定理翻译一下就是
 
$\mathrm{Pr}(\exists h\in H,(erro{r}_S(h)=0)\&(erro{r}_D(h)>ϵ))<|H|{\exp }^{-ϵm}$
 
也就是说 如果 $erro{r}_S(h)=0$, 那么 $erro{r}_D(h)<ϵ$ 的概率至少是 $|H|{\exp }^{-ϵm}$
 
如果我们想要让 $|H|{\exp }^{-ϵm}<\delta$, 那么我们需要
 
$m>{ϵ}^{-1}(\log (|H|)+\log ({\delta }^{-1}))$,这么多变量
 
if $erro{r}_S(h)=0$ 那么 至少我们有 $1-\delta$ 的概率保证
 
$erro{r}_D(h)\le m^{-1}(\log (|H|)+\log ({\delta }^{-1}))$
 
PAC learnable
 
 
简单的说，一个算法是 PAC(Probability Approximation Correct) 可学习的，要满足，时间复杂度和样本复杂度都是多项式的
 
agnostic learning
 
上面都说的是 $c\in H$ ，那如果， $c\notin H$ 呢？
 
根据 Hoeffding 不等式(see wiki)
 
fix a $h$,
 
$\mathrm{Pr}(erro{r}_D(h)-erro{r}_S(h)>ϵ)\le 2{\exp }^{-2m{ϵ}^2}$
 
修改前面的定理，
 
$\mathrm{Pr}(\exists h\in H,erro{r}_D(h)-erro{r}_S(h)>ϵ)<|H|2{\exp }^{-2m{ϵ}^2}$
 
因此在概率为 $\delta$ 的情况下，需要的样本 bound
 
就可以很容易求解了
 
erm
 
最后不加证明的给出
 
 
即 如果我们知道 $er{r}_S(h)$ 那么 $erro{r}_D(h)$ 的bound 在哪里?
 所有的证明和材料，都可见reference
 
reference
 
10716 f16 Eric Xing
10715 f18 Maria-Florina Balcan 
 
 
 
版权声明
 
 
本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
 
 
作者: taotao
 
 
转载请保留此版权声明，并注明出处
 

引自知乎，兴致勃勃地看了一会，太监了。。。
 引自Leslie Valiant
 
说实话，网上很多关于PAC看完还是一头雾水，这篇文章主要是对英文的翻译和一些自己的理解
 
引言
 
PAC学习是莱斯利·瓦利安特（Leslie Valiant）于1984年发明的，自此诞生了计算机科学的一个新的领域——计算学习理论，文中提到可以去看一看这本书《An Introduction to Computational Learning Theory.》
 
Learning intervals
 
举个栗子，两个玩家，玩家1给出一个区间$[a,b]$，玩家2给出一个数字$x$。当$a<x<b$时，玩家1给出1，反正0。
 
接下来，玩家2不断的给出$x$，获得$1/0$来确定$[\hat{a},\hat{b}]$的值。当玩家2猜测的次数很少(finite，有限)时，玩家2不可能完全猜出$a,b$的值，但是如果(infinte，无限)时，玩家2$\hat{a},\hat{b}$就很小很小，那么我们就可以说玩家2“学习”了玩家1的$a,b$，这个区间问题可以被成为PAC-learnable。
 
Distributions and Hypotheses
 
首先我们生成一些随机数集合$X$，集合可以是有限的，也可以是无限的，$X$服从固定但是任意且随机的分布$D$。严格的说，这些样本都是服从iid的。对于玩家1来说，他应该如何的生成随机数，从而让玩家2的算法陷入毁灭。
 
因此，玩家1被简化为$X$上的分布$D$。既然我们说过，无论D是多少，玩家2的算法都能很好地处理高概率，那么定义就变成了这样：
 
如果有一个算法$A$使得其能够赢得$X$在$D$上分布的游戏，那么$A$是PAC-learnable的。
 
现在我们开始讨论，“intervals”如何适用于通用的concept。因为如果我们将要讨论的是通用的学习方法，我们不会总是用“intervals”来做决定，为此我们让玩家1通过函数$c$来将$X$中的点分为$1/0$。我们将其成为concept或者target，而玩家2要去学习。也就是说，玩家2通过自己的函数$h$来标记$X$中的点，然后将其与$c$进行比较，我们将$h$称为hypothesis(hence the use of the letter h)。
 
我们通过下面的方法来比较他们：
 
$${\text{err}}_{c,D}(h)=P_D(h(x)\ne c(x))$$
 
假设$h$关于函数$c$以及分布$D$的误差，是通过$D$得到的$h(x)$和$c(x)$差异的概率。有些人可能将“差异”部分写为两个函数的对称差异，然后它就变成了一个概率密度。但是作者表示不喜欢这么表达。
 
现在对于一个PAC-learning的问题，我们可以表达为：
 
如果有一个算法$A$，面对任意的分布$D$和函数$c$，能够以高概率描述出独立抽取样本时，仅产生较小的误差，那么这个方法是PAC-learnable的。
 
但是在定义中仍然存在一些模糊的界限，(比如：一些、小、高)，也就是说存在太多不确定的概念了。即使对于有限集
    
     
      
       
        
         2
        
        
         n
        
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        }
       
      
      
       2^n\{0,1\}
      
     
    2n{0,1}，一组在$n$个元素上的值函数，如果我们希望能够在多项式时间内运行，只能表达其中的一小部分。回到interval的游戏中，如果玩家1选择的concept是任意的，期望玩家2能够获得一个合理的$h$是不合理的(无论是不是使用了interval)。作为数学家的我正在使用不可测量的集合来描绘一些疯狂的规则，但是只要说一句就足够了：您可能认为您知道有关实数的所有知识，但您不知道。
 
所以我们需要归纳出这些concept的可能性，以及学习者的表达能力。这就是concept class的作用。
 
Concept Classes
 
一个关于$X$的concept class $C$是一个函数族
    
     
      
       
        X
       
       
        →
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        }
       
      
      
       X\rightarrow\{0,1\}
      
     
    X→{0,1}
 
不，好吧，还有更多的事情要讲，但现在只是术语的转变。现在我们可以定义由区间选择引起的一类标记函数。我们可以取区间的所有特征函数的集合${}_{\chi [a,b]}(x)=1$，其中$a\le x\le b$，其他为$0$。现在concept class成为了我们算法中唯一的焦点。也就是说，算法通过concept class的知识来表达假设，因此将工作定义为：
 
如果有一种算法$A$，对于任意的样本的分布$D$和任意的concept $c\in C$，会高概率的以较小的误差的假设$h\in C$表达，那么concept class $C$就是PAC-learnable。
 
作为未来文章的一个简短的前奏：我们将能够证明，如果$C$足够简单（想想“低维”），那么任何做得合理的算法都能够学习$C$。但那是以后的事。现在我们来润色这个定义的其余部分。
 
Probably Approximately Correct Learning
 
我们并不想用游戏来定义，所以是时候将玩家从脑海中删除了。我们真正关心的是是否有一种算法能在给定随机数据时产生好的假设。但我们必须强化“给予”过程，以及对算法施加的具体限制。
 这听起来令人生畏，但就计算复杂度而言，选择是相当标准的。我们希望算法能够决定它需要多少数据，而不是像在实践中那样将样本作为一个大数据集。为此，我们向它提供一个查询函数，当它被访问时，它会在单位时间内吐出一个样本。然后，我们感兴趣的是通过合理数量的查询函数调用来学习这个concept。
 现在我们可以在我们的工作定义中去掉“一些”、“小”和“高”等词。既然我们想要误差尽可能的小，我们将引入一个参数$0＜\epsilon <1/2$来表达期望的误差范围。也就是说我们要找到一个假设$h$以高概率满足${\text{err}}_{c,D}(h)\le \epsilon$
 随着$\epsilon$越来越小(正如我们期望那样)，我们还希望算法可以在允许的时间下运行，所以我们要限制算法的时间和空间多项式在$1/\epsilon$内。
 
我们还需要另一个参数来描述“高概率”这个内容，所以我们引用$0<\delta <1/2$来表示允许的算法具有较高误差的一小部分。所以我们的目标是至少$1-\delta$的概率下假设产生的误差小于$\epsilon$，即：
 $$P_D({\text{err}}_{c,D}(h)\le \epsilon )>1-\delta$$
 
其中，$P_D$指的是调用查询函数（以及算法所做的任何其他随机选择）时获得样本的概率。因此，“高概率”是指不太可能发生的事件，即你得到的数据不能代表产生它的分布。这不是选择分布的概率，无论D是多少，学习的算法都必须学习。
 
随着我们对$\delta$的限制越来越多，我们希望算法有更多的运行时间，所以我们要求算法在a，b都是多项式时间的。
 
多项式时间代表时间/空间复杂度在$O(1),O(n),O(n^2),O(n^3)$内。
 
现在我们有了完整定义的所有部分。
 
定义：
 设一个集合$X$，以及一个关于$X$的concept class $C$。当一个算法$A(\epsilon ,\delta )$能够去表达所有$C$，比如$c\in C$以及关于$X$的分布$D$，并且保证时间复杂度在$O(\text{poly}(\frac{1}{\epsilon },\frac{1}{\delta }))$、$0<\epsilon ,\delta <\frac{1}{2}$，$A$产生假设$h$的误差最大不超过$\epsilon$的概率小于$1-\delta$，即：
 
$$P_D(P_{x\sim D}(h(x)\ne c(x))\le \epsilon )\ge 1-\delta$$
 
其中$P_D$表示了从$D$中抽取样本产生$h$的概率，同样，也可以表达为
 
$$P_D({\text{err}}_{c,D}(h)\le \epsilon )\ge 1-\delta$$
 
Intervals are PAC-Learnable
 
既然我们有了这个定义，我们就可以回到实际的学习间隔问题上来。我们的concept类是所有区间特征函数的集合（对于默认情况，我们将添加空的集合）。我们提出的学习这些区间的算法非常简单：只需抓取一堆样本点，取最大和最小的正样本，并将这些作为假设区间的终点。
 
现在我们来证明这个算法可以学习任意分布在实数上的区间。此证明将采用以下形式：
 
假设选择任意数量的样本数$m$
得出在$m$下的概率关于我们产生的假设的总误差$>\epsilon$
选择$m$足够大，使该事件（未能达到低误差）以小概率发生。
 
因此，对于任意分布$D$假设我们有$m$个样本，然后我们取最小值$I=[a_1,b_1]$，目标concept $J=[a_0,b_0]$。我们注意到一件事情，我们的假设包含在真实的区间内，即$I\subset J$。因为样本永远不会说谎，所以最大的样本一定小于最大的正样本，反之亦然。也就是说$a_0<a_1<b_1<b_0$。所以假设产生错误的概率就是$D$在$A=[a_0,a_1]$和$B=[b_1,b_0]$两个区间内产生正例子的概率。
 
这就是上面第二个要点的全部设置。总误差不超过$A$和$B$中出现一个正样本的概率之和。
 
$${\text{err}}_{J,D}\le P_{x\sim D}(x\in A)+P_{x\sim D}(x\in B)$$
 
 
图中两个绿色的间隔是可能发生错误的区域。如果我们能保证每个绿色部分都有高概率小于$\epsilon /2$，那么我们就完成了。让我们来看看$A$，这同样也适用于B。定义$A^{\prime }$是一个大很大区间$[a_0,y]$，在这个区间内，$A$从$D$中得到一个正例的概率刚好为$\epsilon /2$，如图。
 
 
粉色区域$A^{\prime }$的总概率权重为$\epsilon /2$，如果绿色区域A更大，我们就会冒很大的错误风险，无法进行PAC-learnable。
 
如果$A\subset A^{\prime }$，那么情况就很好了，这意味着我们有可能从$A$中至少以$\epsilon /2$的概率取得一个正例。所以我们不希$A^{\prime }\subset A$。但这只有在我们在算法运行期间从未看到$A^{\prime }$中的点作为样本的情况下才会发生。当我们有$m$个样本时，我们可以用$m$表示从未看到$A^{\prime }$样本的概率。
 
一个样本不在$A^{\prime }$的概率仅为$1-\epsilon /2$(根据定义)。回顾一下我们的基本概率论，两次平局是独立的事件，所以$A^{\prime }$错失$m$次的概率等于每一次未命中的概率的乘积。也就是说，我们选择的贡献误差大于$\epsilon /2$的概率最大为
 
$$P_D(A^{\prime }\subset A)\le (1-\epsilon /2{)}^m$$
 
关于$B$与上文中内容一样，所以通过并集，在$A$或$B$中发生错误$>\epsilon /2$的概率，是两者的和。
 
$$P_D({\text{err}}_{J,D}(I)>\epsilon )\le 2(1-\epsilon /2{)}^m$$
 
接下来是第三点，我们希望误差很大的概率小于$\delta$，以便于误差小于$1-\delta$，所以：
 
$$2(1-\epsilon /2{)}^m\le \delta$$
 
接下来我们去解决$m$，利用$(1-x)\le e^{-x}$，所以：
 
$$2e^{\epsilon m/2}\le \delta$$
 
则：
 
$$m\ge (2/\epsilon \log (2/\delta ))$$
 
现在，我们涵盖了所有基础：我们的算法只是为其输入$\epsilon ,\delta$，样本数$m$，查询多个样本，并计算包含正例的最匹配区间。由于需要的样本数是关于$\frac{1}{\epsilon },\frac{1}{\delta }$的多项式的(我们的算法不会做任何复杂的事情)，所以我们遵守了时间和空间的限制。最后，我们证明了我们的算法对从D中提取的新点进行错误分类的概率最大为$\delta$。所以我们证明了定理：
 
定理：实数轴上的区间是PAC-learnable的。
 
其实PAC到这里，已经差不多知道干了什么了，这里给出了一个proof
 引自知乎
 
$$L_{D,f}(h)=\underset{x\sim D}{\mathrm{Pr}}[h(x)\ne f(x)]$$
 
其中$D$代表样本的分布，$f$代表正确的$f:X\to Y$，$y_i=f(x_i)$，$h$代表假设，也就是分类器。
 

     
      
       
        
         
          L
         
         
          S
         
        
        
         (
        
        
         h
        
        
         )
        
        
         ≡
        
        
         
          1
         
         
          m
         
        
        
         
          ∑
         
         
          
           i
          
          
           =
          
          
           1
          
         
         
          m
         
        
        
         1
        
        
         {
        
        
         h
        
        
         (
        
        
         
          x
         
         
          i
         
        
        
         )
        
        
         ≠
        
        
         
          y
         
         
          i
         
        
        
         }
        
       
       
        L_S(h)\equiv\frac{1}{m}\sum_{i=1}^m1\{h(x_i)≠y_i\}
       
      
     LS​(h)≡m1​i=1∑m​1{h(xi​)​=yi​}
 
$\exists h^{\ast }\in H,L_{(D,f)}(h^{\ast })=0$，那么训练集$S$有$L_S(h^{\ast })=0$，称为ERM(Empirical Risk Minimization)。
 
$L_{D,f}(h_S)\le \epsilon$是成功的，反之则不是，那么失败概率的上界
 $$\mathrm{Pr}(L_{D,f}(h_S)>\epsilon )$$
 
但是假设$L_{(}D,f)(h_{\beta })>\epsilon$，并且$L_S(h_{\beta })=0$，那么这是欺骗了ERM。
 
如果$A\Rightarrow B$，那么$\mathrm{Pr}(A)\le \mathrm{Pr}(B)$
 
$$\mathrm{Pr}(L_{D,f}(h_S)>\epsilon )\le \mathrm{Pr}(\bigcup _{h\in H_B}{L}_S(h)=0)\le \sum _{h\in H_B}\mathrm{Pr}(L_S(h)=0)(1)$$
 其中第二个不等号是来自于布尔不等式(Boole’s Inequality)
 $$\mathrm{Pr}(A\cup B)\le \mathrm{Pr}(A)+\mathrm{Pr}(B)$$
 
现在只需要针对一些$h\in H_B$，求出这些$H_B$在训练集上不犯错
 
$$\mathrm{Pr}(L_S(h))=\mathrm{Pr}(h(x_i)=y_i,i=1,\cdots ,m)=\prod _{i=1}^m\mathrm{Pr}(h(x_i)=y_i)\le (1-\epsilon {)}^m\le e^{-m\epsilon }(2)$$
 
其中第一个不等号是来源于$H_B$的正确率小于$1-\epsilon$，第二个是来源于$1-\epsilon \le e^{-\epsilon }$
 
结合(1)(2)，可以得到
 
$$\mathrm{Pr}(L_{D,f}(h_S)>\epsilon )\le |H_B|e^{-\epsilon m}\le |H|e^{-\epsilon m}$$
 
由于$H$是无限的，所以我们用$|H|$来代替这个无限的集合，以表达一个量。
 
 
然后，我们考虑一下机器学习的理论性，引自知乎的一个回答，Alexnet为什么有 7 层 feature layer（可能记错数字了），不是8层，不是6层？仅仅是因为是不同架构试了一下，7层效果不错，完全没有理论上的 motivation。超参数为什么是这么定的？为什么卷积层之间要放 dropout layer？完全就是，“过去的人弄了，效果不错”，或者“我试了一下，效果不错”。好像是 David Duvenaud 说的，现在的神经网络设计，就想是物理学出现前的造桥。有人造桥，放了栏杆，效果不错，发篇论文；有人加了几个柱子，效果不错，再发一篇。

 
 
一个PAC文件包含一个JavaScript形式的函数“FindProxyForURL(url, host)”。
 
 
它是一段JavaScript 脚本：
 
function FindProxyForURL（ur1，host）

{ 

return"DIRECT"；

}
 
上面就是一个最简洁的PAC文件，意思是所有流量都直接进入互联网，不走代理。
PAC 语法和函数
 上面函数中，url字段就是我们在浏览器地址栏输入的待访问地址，host为该地址对应的hostname，return 语句有三种指令：
 DIRECT，表示无代理直接连接
 PROXY host:port，表示走host:port的proxy 服务
 SOCKS host:port，表示走host:port的socks服务
 而返回的接口可以是多个代理串联：
 
return"PROXY 222.20.74.89：8800；SOCKS 222.20.74.89：8899；DIRECT"；
 
上面代理的意思是，默认走222.20.74.89：8800的proxy服务；如果代理挂了或者超时，则走222.20.74.89：8899的socks代理；如果 socks也挂了，则无代理直接连接。
 PAC提供了几个内置的函数，下面挨个介绍下：
 
dnsDomainls
 
类似于==，但是对大小写不敏感，
 
if（dnsDomainIs（host，"google.com"）||
dnsDomainIs（host，"www.google.com"））

{
return"DIRECT"；

}
 
shExXpMatch Shell
 
正则匹配，*匹配用的比较多，可以是*http:/∥example.com，也是可以下面这样，
 
if（shExplMatch（host，"vpn.domain.com）l|
shExplMatch（ur1，"http://abcdomain.com/folder/*"））

{
return"DIRECT"；

}
 
isInNet
 
判断是否在网段内容，比如10.1.0.0这个网段，10.1.1.0就在网段中，
 
if（isInNet（dnsResolve（host），"172.16.0.0"，"255.240.0.0"））

{
return"DIRECT"；

}
 
mylpAddress
 
返回主机的IP
 
if（isInNet（myIpAddress（），"10.10.1.0"，"255.255.255.0））

{
return"PROXY 10.10.5.1：8080"；

}
 
dnsResolve
 
通过DNS查询主机ip
  
 
if（isInNet（dnsResolve（host），"10.0.0.0"，"255.0.0.0）||
isInNet（dnsResolve（host），"172.16.0.0"，"255.240.0.0）l|

isInNet（dnsResolve（host），"192.168.0.0"，"255.255.0.0）||
isInNet（dnsResolve（host），"127.0.0.0"，"255.255.255.0"））

{
return"DIRECT"；

}
 
isPlainHostName
 
判断是否为诸如http://barret/，http://server-name/这样的主机名
  
 
if（isPlainHostName（host））

{
return"DIRECT"；

}
 
isResolvable
 
判断主机是否可访问
 
if（isResolvable（host））{
return"PROXY proxyl.example.com：8080"；

}
 
举例一个全自动代理VPN服务器
 
function FindProxyForURL(url, host) {
    if (shExpMatch(host, '10.134.*.*'))   //地址是需要访问的地址
  {
	return 'PROXY *.*.*.*:端口';
  }
  
  else if (shExpMatch(host, '172.16.*.*'))  //地址是需要访问的地址
  {
	return 'PROXY *.*.*.*:端口';
  }
 
  else
  { 
	return 'DIRECT';
   }
}
 
如何使用
 
先介绍一下设置各个系统代理的方法。
 Windows
 Internet选项--连接 选项卡--局域网设置(如果是电脑拨号上网, 这里点'设置')-- 使用自动配置脚本--填入PAC地址--确定 
 Mac OS X
 系统设置 -- 网络 --高级 --代理 --自动代理配置 --URL中填入PAC地址 -- 好

 
关于证明PAC可学习
 
参考文章
  
 


 最近在学习statistical learning，学习到了《深入理解机器学习：从算法到原理》这本书，其中有对PAC进行了详细的介绍，在做题的时候对PAC的证明十分的困惑，这里基本想清楚后做一个总结，如有错误的还请指出。
 
首先来明确一个概念，PAC可学习是针对什么而言的，我的理解是 对于我们的假设类H（通俗点说就是分类器的集合） 可以找到一个近似正确的分类器，这个分类器满足
 其中定义m个sample组成S空间，其中每个sample服从D分布，并且互相独立；
 如果存在一个算法A，在m（sample个数）有限的情况下，找到假设h；
 使得对于任意两个数ε，δ，（ε，δ都大于0小于1）概率P(h对S中sample预测错误次数大于ε) < δ；
 
 现在我们有一个分类器集合R，我们想证明R是PAC可学习的，因此我们找到一个包含所有positive examples(这里是蓝色的点)最小的R’，来证明R’可以满足我上面所说过的不等式，即完成了R是PAC可学习的证明。（换句话说，由于我们找到了近似正确的分类器R’，所以R是PAC可学习的）
 
现在我们的目标是证明R’满足上面说过的不等式，这里我们做一个转换：
 
 我们由R向内扩展出4个小矩形：r1,2,3,4。每个r的概率x/4。（这里所说的概率是指当我们做测试集测试时的蓝色点落入r而形成的错误概率，因为蓝色点落入了r中，会被R’归类为红色的点所以形成错误；而对于R’，它的错误率相当于R’和R的补集）
 
所以，当R(R‘)>ε时，R’必须错过至少一个ri,1<=i<=4。
 
因为，当R’不相交于任何一个r时，R‘的错误率就大于等于ε，这里解释是这样的，当R’与ri,1<=i<=4,都相切时，R‘的错误率=ε，而R’与任何一个ri都不相交时，r上的错误率ε加上R’与r之间会空出一部分空间所形成的错误率==>R‘的错误率就大于ε。
 
R’与r都相交时，R‘的错误率就小于ε，这个很好理解就不过多解释了。
 
而当R’与r中的1个相交时，我们可能会有疑问，为什么此时R‘的错误率仍然大于ε呢？ 这是因为，正如上图所示，R’与r2相交了一部分，但是和其他三个r没有相交，对于与r1,3,4没有相交而空出来的那部分空间，我们仍然可以用人为的方式来使得空出的空间大于R’与r2相交的空间，并保证错误率仍然大于ε。（对于其他的相交情况是同理的）
 
因此我们可以得出我们的不等式了：
 
 （因为这里我们是想求错误率大于ε的这个概率的一个上界，所以我们取R’与任何一个r都不相交的概率为上界。）
 
由于并集的概率小于各自概率的和：
 
 
由于S中的每个sample的独立分布的，并且落在r1中的概率为x/4，所以
 
 
由于我们要求错误个数大于x的概率小于y，所以可以定义如下的不等式。
 
 
推导出m的下限。
 
这就说明只需要有限个实例就能满足上面的概率不等式。
 
 
这就说明了，上面这个平面图形中学习矩形的问题是PAC可学习的。
 
证明过程适用与《深入理解机器学习》这本书的习题2.3和3.3，希望可以给还在迷惑的同学一些帮助
 
参考文章
 
本人比较懒，所以图片和部分推导过程引用了：PAC学习框架 https://www.cnblogs.com/alphablox/p/5935826.html 这篇文章
 本文也是针对该文章基础上具体了细节和新增了一些个人理解，如有侵权，立刻删除侵权的内容。