【机器学习第十二章——计算学习理论】

12.计算学习理论

12.1 基础知识

• 从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力

• 这个理论要回答的问题是:

  • 在什么样的条件下成功的学习是可能的?
  • 在什么条件下某个特定的学习算法可保证成功运行?

• 机器学习理论的一些问题:

  • 是否可能独立于学习算法确定学习问题中固有的难度?
  • 能否知道为保证成功的学习有多少训练样例是必要的或充足的?
  • 如果学习器被允许向施加者提出查询，而不是观察训练集的随机样本，会对所需样例数目有怎样的影响?
  • 能否刻画出学习器在学到目标函数前会有多少次出错?
  • 能否刻画出一类学习问题中固有的计算复杂度?

• 主要解决的问题是:

  • 需要多少训练样例才足以成功地学习到目标函数
  • 学习器在达到目标前会出多少次错

12.1 可能学习近似正确假设（PAC）

• 可能近似正确学习模型(PAC)
  • 指定PAC学习模型适用的问题
  • 在此模型下，学习不同类别的目标函数需要多少训练样例和多大的计算量

X表示所有实例的集合，C代表学习器要学习的目标概念集合，C中每个目标概念c对应于X的某个子集或一个等效的布尔函数c:
X → { 0 , 1 } X→\{0,1\} X→{0,1}

假定实例按照某概率分布D从X中随机产生

学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后，L必须从H中输出某假设h，它是对c的估计

我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新实例与训练数据具有相同的概率分布

我们要求L足够一般，以至可以从C中学到任何目标概念而不管训练样例的分布如何，因此，我们会对C中所有可能的目标概念和所有可能的实例分布D进行最差情况的分析

12.3 有限假设空间

• PAC可学习性很大程度上由所需的训练样例数确定
• 随着问题规模的增长所带来的所需训练样例的增长称为该学习问题的样本复杂度
• 我们把样本复杂度的讨论限定于一致学习器(输出完美拟合训练数据的学习器)
• 能够独立于特定算法，推导出任意一致学习器所需训练样例数的界限
• 变型空间:能正确分类训练样例D的所有假设的集合。

V S H , D = { h ∈ H ∣ ( ∀ < x , c ( x ) > ∈ D ( h ( x ) = c ( x ) ) ) } VS_{H,D}=\{h\in H|(\forall\quad <x,c(x)>\quad\in D(h(x)=c(x)))\} VSH,D​={h∈H∣(∀<x,c(x)>∈D(h(x)=c(x)))}

• 变型空间的重要意义是：每个一致学习器都输出一个属于变型空间的假设

• 因此界定任意一个一致学习器所需的样例数量，只需要界定为保证变型中没有不可接受假设所需的样例数量

• 定义:考虑一假设空间H，目标概念c，实例分布D以及c的一组训练样例S。当
  $$V{S}_{H,D}$$
  中每个假设h关于c和D错误率小于ε时，变型空间被称为c和D是ε-详尽的。

$$(\forall h\in V{S}_{H,D})erro{r}_D(h)<\epsilon$$

• 详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于ε

• 从学习器的角度看，所能知道的只是这些假设能同等地拟合训练数据，它们都有零训练错误率

• 只有知道目标概念的观察者才能确定变型空间是否为ε-详尽的

• 但是，即使不知道确切的目标概念或训练样例抽取的分布，一种概率方法可在给定数目的训练样例之后界定变型空间为ε-详尽的

• 定理7.1(变型空间的ε-详尽化）

  • 若假设空间H有限，且D为目标概念c的一系列m>=1个独立随机抽取的样例，那么对于任意0=<ε<=1，变型空间不是ε-详尽的概率小于或等于:
    $$|H|e^{-\epsilon m}$$

  • 证明:

    • 令
      $$h_1,...,h_k$$
      为H中关于c的真实错误率大于ε的所有假设。当且仅当k个假设中至少有一个恰好与所有m个独立随机抽取样例一致时，不能使变型空间ε-详尽化。

    • 任一假设真实错误率大于ε，且与一个随机抽取样例一致的可能性最多为1-ε，因此，该假设与m个独立抽取样例一致的概率最多为
      $$(1-\epsilon {)}^m$$

    • 由于已知有k个假设错误率大于ε，那么至少有一个与所有m个训练样例都不一致的概率最多为
      $$\begin{gathered} 当0\le \epsilon \le 1,则1-\epsilon \le e^{\epsilon } \\ k(1-\epsilon {)}^m\le |H|(1-\epsilon {)}^m\le |H|e^{-\epsilon m}(7.2) \end{gathered}$$

• 定理7.1基于训练样例的数目m、允许的错误率ε和H的大小，给出了变型空间不是ε-详尽的概率的上界

• 即它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设（错误率大于ε的假设)剔除出去的概率

• 利用上面的结论来确定为了减少此“未剔除”概率到一希望程度ε所需的训练样例数
  $$由|H|e^{-\epsilon m}\le \delta \to m\ge \frac{1}{\epsilon }(\ln |H|+\ln (1/\delta ))$$

• 式子7.2提供了训练样例数目的一般边界，该数目的样例足以在所期望的值ε和δ程度下，使任何一致学习器成功地学习到H中的任意目标概念

• 训练样例的数目m足以保证任意一致假设是可能（可能性为1-δ）近似（错误率为ε）正确的

• m随着1/ε线性增长，随着1/δ和假设空间的规模对数增长

• 上面的界限可能是过高的估计，主要来源于|H|项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和

12.4 VC维

• 分层有向无环图的特点:

  • 节点可划分成层，即所有第1层出来的有向边进入到第l+1层节点
  • 没有有向环，即有向弧形成的回路

• 这样网络的VC维的界定可以基于其图的结构和构造该图的基本单元的VC维

• 定义一些术语

  • G表示神经网络

  • n是G的输入数目

  • G只有1个输出节点

  • G的每个内部单元Ni最多有r个输入，并实现布尔函数
    c i : R r → { 0 , 1 } c_i:R^r→\{0,1\} ci​:Rr→{0,1}
    形成函数类C

  • 定义C的G-合成:网络G能实现的所有函数的类，即网络G表示的假设空间，表示成
    $$C_G$$

• 定理7.4分层有向无环网络的VC维

  • 令G为一分层有向无环图，有n个输入节点和s>=2个内部节点，每个至少有r个输入，令C为VC维为d的
    $$R^r$$
    上的概念类，对应于可由每个内部节点s描述的函数集合，令
    $$C_G$$
    为C的G合成，对应于可由G表示的函数集合，则
    $$VC(C_G)<=2ds\log (es)$$

• 假定要考虑的分层有向无环网络中单个节点都是感知器，由于单独的r输入感知器VC维为r+1，代入定理7.4和式子7.7，得到
  $$VC(C_G^{perceptions})\le 2(r+1)s\log (es)$$

  $$m\ge \frac{1}{\epsilon }(4\log (2/\delta )+16(r+1)s\log (es)\log (13/\epsilon ))$$

• 上面的结果不能直接应用于反向传播的网络，原因有两个:

  • 此结果应用于感知器网络，而不是sigmoid单元网络
  • 不能处理反向传播中的训练过程