经典机器学习系列(十四)PAC-Learning

    当在设计一个算法的时候：  

• 怎么样才能学习地更有效率？
• 什么样的问题天生很难学？
• 需要多少样本才能学好？
• 所学出来的model泛化能力好吗？

PAC学习模型

  这就是PAC要做的事情，解决上述疑问。PAC英文全程Probably Approximately Correct。在开始介绍这个framework之前需要定义一些notation：  

• $\mathcal{X}$：examples或称为instances的集合，有时也代表输入空间。
• $\mathcal{Y}$：labels或者称为target的集合。
• $\mathcal{X}\to \mathcal{Y}$：称之为一个概念(concept)，由于是一个二分类问题，所以c 可以被定义为$\mathcal{X}$中label全为1的一个子集。
• $\mathcal{C}$: 所有的概念(concept)组成concept class，是需要去learn的。

  考虑一个binary classi cation问题，之后扩展到更一般的情形。假设样本是独立地满足一个固定但是未知的分布$\mathcal{D}$。   从$\mathcal{D}$中sample一些样本S=(x1​,⋯,xm​)和它的标签(c(x1​),⋯,c(xm​))，之后基于这些带label的样本选择hypothesis hS​∈H，使得其泛化误差(generalization error)最小。  

定义 Generalization error ：

  给定hypothesis$h\in \mathcal{H}$，target concept $c\in \mathcal{C}$和一个潜在distribution $\mathcal{D}$，generalization error或者h 的risk被定义为：  
  可以看出某个hypothesis的generalization error并不是全部由learner所导致的，与distribution D D和 target concept $c$ 都有关系。  

定义 Empirical error ：

  给定一个hypothesis $h\in \mathcal{H}$，一个target concept $c\in \mathcal{C}$，一个sample S=(x1​,⋯,xm​)，empirical risk被定义为：  
  可以看出empirical risk是sample下的平均error，而generalization error是在distribution$\mathcal{D}$下的expected error。   对于一个固定的$h\in \mathcal{H}$，基于独立同分布采样得到的期望empirical error与generalization error是相等的：  
 

Learning axisaligned rectangles

  考虑这样一种情况，样本是平面上的一些点，X∈R2，概念类(concept class)是R2中所有的与轴平行的矩形，因此每个concept $c$ 是轴平行矩形中的点，矩形内部为1，外部为2。要学习的问题就是基于有label的训练数据确定能够最小error的轴平行矩形框：  
  如上图所示R 表示目标axisaligned rectangles，R′是hypothesis。如上图所示误差主要来自两部分：  

• false negatives：在矩形R 内，但是不在矩形R′内。也就是实际label为1的被R′标记为0。

• false positives：在矩形R′内，但是不在矩形R 内。也就是实际label为0的被R′标记为1。

  有这样一个算法$\mathcal{A}$，给一些被标记的样本$S$，算法会返回一个最紧的轴平行矩形(tightest axis-aligned rectangle) R′=Rs​ ，包含了label为1的样本，如下图2.2所示：  
  依据定义可知，Rs​中不包含任何false postives，因此Rs​错误的区域(region)被包含在R 中。   记$R\in \mathcal{C}$为target concept。固定$\epsilon >0$。$\mathbb{P}[R]$被定义为随机从分布$\mathcal{D}$中采一个点，落入到$R$内的概率。因为由算法所导致的误差的点只会落入到$R$内，所以假设$\mathbb{P}[R]>\epsilon$。   定义好了$\mathbb{P}[R]>\epsilon$之后，再定义四个延边矩形r1​,r2​,r3​,r4​，每个的概率至少都是$\epsilon /4$。这些region可以从整个矩形$R$开始构造，然后移动其中的一条边，使其尽可能地小，但是要保证其distribution mass至少都是$\epsilon /4$，即P[ri​]≥ε/4。如下图所示：  
  令l ，r ，b 和t 是四个真实的值，R 定义为：$R=[l,r]\times [b,t]$。那对于左边的r4​区域可以被定义成r4​=[l,s4​]×[b,t]，其中s4​=inf{s:P[[l,s]×[b,t]]≥1/4}。   如果RS​与四个沿边矩形ri​都有交集，因为其是矩形，所有每个regionri​中都有RS​的一条边，也就是RS​一定在矩形R 内，即R(RS​)≤ε。相反，如果R(RS​)>ε，那至少有一个regionRS​没有边相交。可以写成：  
  也就是没有样本点在沿边矩形ri​的内部或者边上。上式中我们使用了一个通用的不等式1−x≤e−x，对于任意$\delta >0$，要使得
 
  要注意的是这里的hypothesis set $\mathcal{H}$是无限的。上述证明PAC-learnable用了矩形的几何关系，是整个证明的key，上述的证明过程泛化能力并不是很强。之后会在finite hypothesis set下证明更一般的情形。  

PAC learning

  在开始证明之前，我们需要先来了解一下这个PAC-learning定义：  
  如果存在一个算法$\mathcal{A}$和一个多项式函数$plot(\cdot ,\cdot ,\cdot ,\cdot )$，对于任意的$\epsilon >0$和$\delta >0$，对$\mathcal{X}$上所有的分布$\mathcal{D}$和任意一个target concept $c\in \mathcal{C}$，当样本$m\ge ploy(1/\epsilon ,1/\delta ,n,size(c))$时，有：  
  也就是在很大概率($1-\delta$)上是近似正确的(误差为ε )。   有一些关键知识点：  

1. PAC框架是与分布$\mathcal{D}$无关的，因为其没有对分布做任何假设。
2. 样本是从相同的分布$\mathcal{D}$中采样得到的。
3. PAC框架处理的是概念类(concept class) $\mathcal{C}$(is known to the algorithm)，而不是目标类(target concept) $c\in \mathcal{C}$ (is unknown)。

Guarantees for finite hypothesis sets — consistent case

  在axis-aligned rectangles的例子中，算法给出的hypothesis hS​总是consistent，也就是说在training sample S 上是没有error的。针对consistent hypotheses情形来证generalization bound，假定target concept c  在$\mathcal{H}$中。  

• 定理(Learning bound有限$\mathcal{H}$，consistent情况下)：$\mathcal{H}$是$\mathcal{X}$到Y的一个有限集合。$\mathcal{A}$是一个从任意target concept c ∈ H ，样本S 满足独立同分布，的一个学习算法，返回一个consistent hypothesis h S : R^S​(hS​)=0。对任意的$\delta >0$，如果

 
  用generalization bound来描述：对于任意$\delta$，至少以概率$1-\delta$：  
  Proof：固定$\epsilon >0$，定义$R(h)\ge \epsilon \}$(泛化误差的含义是对随机一个样本，预测错误的概率。)，对于h∈HE​，它在training sample S 下的consistent(每个样本误差为0的情况)可表示为：  
  又有(事件的包含关系，左边事情发生，则右边事情一定发生)：  
  令等式右边等于$\delta$即可得证。  

Guarantees for finite hypothesis sets — inconsistent case

  上一小节的证明是在consistent情况下的证明，然而在大多数情况下是达不到这样一种情况的。更一般的假设可以采用Hoeffding inequality来得到generalization error和empirical error之间的关系。  

• Corollary(推论)：固定$\epsilon >0$，对于任意hypothesis $X\to \{0,1\}$，有以下inequalities：

 
  Theorem(learning bound - finite $\mathcal{H}$, inconsistent case)：$\mathcal{H}$是一个finite hypothesis 集合。对于任意$\delta >0$，有概率至少$1-\delta$以下式子成立：  
  Proof：h1​,⋯,hH​是$\mathcal{H}$中的elements。采用corollary将其union在一起得到：  
  令右边等于δ 得证。consistent在上述等式下也是成立的，这是一个更加松的bound。从这里就可以得到hypothesis的大小，样本大小和误差之间的关系。    

Generalities

  更一般的情况，输出的label是输入数据的一个概率，比如说输入身高和体重预测这个人的性别这种问题。也就是说label是一个概率分布这样。  

• 定义 Agnostic PAC learning：

 
  如果label可以被某个function $\mathcal{X}\to \mathcal{Y}$ 独一无二地确定下来，将其称为deterministic，会存在某个target function使得generalization error $R(h)=0$，在stochastic情形下就不存在说会使得某个hypothesis下的error为0：  

• 定义(Bayes error)：给定distribution $\mathcal{D}$，Bayes error R∗被定义为measurable function $\mathcal{X}\to \mathcal{Y}$的误差下界：

 
  hypothesis h  withR(h)=R∗被称作Bayes hypothesis或者是Bayes classi er。通过定义可知，在deterministic的情况下R∗=0，但是在stochastic的情况下R∗​=0。   Bayes classi er h Bayes​可以被定义成以下条件概率的情形：