计算学习理论(PAC)

devilogic

---

介绍

学习器的属性

• 学习器所考虑的假设空间的大小和复杂度
• 目标概念须近似到怎样的精度
• 学习器输出成功的假设的可能性
• 训练样例提供给学习器的方式

计算理论的目标

• 样本复杂度：学习器要收敛到成功假设（以较高的概率），需要多少训练样例？
• 计算复杂度：学习器要收敛到成功假设（以较高的概率），需要多大的计算量？
• 出错界限：在成功收敛到一个假设前，学习器对训练样例的错误分类有多少次？

判断成功的方式

1. 学习器的输出与目标概念相等
2. 学习器的输出的假设与目标概念在多数时间内一致

可能学习近似正确假设

PAC可学习性

定义：考虑定义在长度为$n$的实例集合$X$上的一概念类别$C$，学习器$L$使用假设空间$H$。当对所有$c \in C$，$X$上的分布$\mathscr D$，$\epsilon$满足$0 \lt \epsilon \lt \frac{1}{2}$以及$\delta$满足$0 \lt \delta \lt \frac{1}{2}$时，学习器$L$将以至少$1-\delta$的概率输出以假设$h \in H$，使$error_{\mathscr D}(h) \le \epsilon$，这时称$C$是使用$H$的$L$可PAC学习的。所使用的时间为$\frac{1}{\epsilon}$、$\frac{1}{\delta}$、$n$以及$size(c)$的多项式函数。

其时间最多是以多项式方式增长，多项式中$\frac{1}{\epsilon}$和$\frac{1}{\delta}$定义了对输出假设要求的强度，$n$和$size(c)$则定义了实例空间$X$和概念类别$C$中固有的复杂度。这里，$n$为$X$中实例的长度。

为显示某目标概念类别$C$是可$PAC$学习的，一个典型的途径是证明$C$中每个目标概念可以从多项式数量的训练样例中学习到，而后证明每样例处理时间也限制于多项式级。

隐含限制

该定义隐含假定了学习器的假设空间$H$包含一个假设，它与$C$中每个目标概念可有任意小的误差（能被学习到，例如：在神经网络中必定有一组权值矩阵可以满足某个目标概念的识别）。

有限假设空间的样本复杂度

PAC可学习性很大程度上由所需的训练样例数确定。随着问题规模的增长所带来的所需训练样例的增长称为该学习问题的样本复杂度。

一致学习器

一个学习器是一致的，当它只要在可能时都输出能完美拟合训练数据的假设。由于通常更喜欢能与训练数据拟合程度更高的假设，因此要求学习算法具有一致性是合理的。

变型空间

变型空间$VS_{H,D}$被定义为能正确分类训练样例$D$的所有假设$h \in H$的集合：

$$VS_{H,D} = \{h \in H |(\forall<x, c(x)> \in D) \quad (h(x) = c(x))\}$$ 变型空间的重要意义在于，每个一致学习器都输出一个属于变型空间的假设，而不论有怎样的实例空间$X$、假设空间$H$或训练数据$D$。原因很简单，由变型空间的定义，$VS_{H,D}$包含$H$中所有的一致假设。因此，为界定任意一致学习器所需的样例数量，只需要界定为保证变型空间中没有不可接受假设所需的样例数量。

定义：考虑一假设空间$H$，目标概念$c$，实例分布$\mathscr D$以及$c$的一组训练样例$D$。当$VS_{H,D}$中每个假设$h$关于$c$和$\mathscr D$错误率小于$\epsilon$时，变型空间被称为关于$c$和$\mathscr D$是$\epsilon-$详尽($\epsilon-exhausted$)的。

$$(\forall h \in VS_{H,D})error_{\mathscr D}(h) \lt \epsilon$$

对于变型空间中所有的假设都可以在真实错误率小于$\epsilon$下，称为$\epsilon$详尽
对于神经网络而言，$H$即是权值矩阵的所有取值集合，$D$是输入向量的训练向量集合，$C$是目标集合。

变型空间的$\epsilon-$详尽化

若假设空间$H$有限，且$D$为目标概念$c$的$m \ge 1$个独立随机抽取的样例序列，那么对于任意$0 \le \epsilon \le 1$，变型空间$VS_{H,D}$不是$\epsilon-$详尽（关于$c$）的概率小于或等于：

$$|H|e^{-\epsilon m}$$

上述的意思就是训练不出来或者训练不理想的最大概率是$|H|e^{-\epsilon m}$得到一个训练失败概率的上界。

证明：令$h_1,h_2,\cdots h_k$为$H$中关于$c$的真实错误率大于$\epsilon$的所有假设。当且仅当$k$个假设中至少有一个恰好与所有$m$个独立随机抽取样例一致时，不能使变型空间$\epsilon-$详尽化。任何一个真实错误率大于$\epsilon$的假设，它与一个随机抽取样例一致的概率最多为($1 - \epsilon$)。因此，该假设与$m$个独立抽取样例都一致的概率最多为$(1 - \epsilon)^m$。由于已知有$k$个假设错误率大于$\epsilon$，那么至少有一个假设与所有$m$个训练样例都一致的概率最多为：

$$k(1 - \epsilon)^m$$
并且因为$k \le |H|$，上式最多为$|H|(1-\epsilon)^m$。最后，使用一个通用不等式：当$0 \le \epsilon \le 1$则$(1 - \epsilon) \le e^{- \epsilon}$，因此： $$k(1-\epsilon)^m \le |H|(1-\epsilon)^m \le |H|e^{-\epsilon m}$$ 定理得证。

证明通用不等式 当$0 \le \epsilon \le 1$则$(1 - \epsilon) \le e^{- \epsilon}$
证明：

基于训练样例的数目$m$、允许的错误率$\epsilon$和$H$的大小，得到了变型空间不是$\epsilon-$详尽的概率的上界。将一个希望程度$\delta$(学习成功率)关联则：

$$|H|e^{-\epsilon m} \le \delta$$ 从中解出$m$，可得到： $$m \ge \frac{1}{\epsilon}(ln|H|+ln(\frac{1}{\delta})) \tag{公式1}\label{eqv1}$$

其实$\delta$是一个希望的值的概念。一个衡量成功的标准，它是至少等于训练不出来概率的最大值。$\delta$表示不成功率，而$1-\delta$表示训练成功率。

上述不等式提供了训练样例数目得一般边界，该数目得样例足以在所期望得值$\delta$和$\epsilon$程度下，使任何一致学习器成功地学习到$H$中的任意目标概念。训练样例的数目$m$足以保证任意一致假设是可能（可能性为$1-\delta$）近似（错误率为$\epsilon$）正确的。注意，$m$随着$\frac{1}{\epsilon}$线性增长，并随$\frac{1}{\delta}$对数增长。它还随着假设空间$H$的规模对数增长。

上述的界限有可能是过高的估计。不等式给出的边界可能过高估计了所需的训练样例的数量。此边界的脆弱性主要来自于$|H|$项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和。

不可知学习和不一致假设

上面叙述的不等式，它告诉我们有多少训练样例才足以保证($1-\delta$)$H$中每个有零训练错误率的假设的真实错误率最多为$\epsilon$。如果$H$不包含目标概念$c$，那么并不总能找到一个零错误率假设。这时，最多能要求学习器输出的假设在训练样例上有最小的错误率。如果学习器不假定目标概念可在$H$中表示，而只简单地寻找具有最小训练错误率的假设，这样的学习器称为不可知学习器，因为它不预先认定$C \subseteq H$。

令$D$代表学习器可观察到的特定训练样例集合，而与此不同的$\mathscr D$代表在整个实例集合上的概率分布。令$error_D(h)$代表假设$h$的训练错误率。确切地说，$error_D(h)$定义为$D$中被$h$误分类的训练样例所占比例，注意$error_D(h)$是在特定训练数据样本$D$上的，它与真实错误率$error_{\mathscr D}(h)$不同，后者是定义在整个概率分布$\mathscr D$上的。现在令$h_{best}$代表$H$中有最小训练错误率的假设。多少训练样例才足以（以较高的概率）保证其真实错误率$error_{\mathscr D}(h_{best})$不会多于$\epsilon + error_D(h_{best})$呢？上一节讨论的情况只是这种情况的特例，其中$error_D(h_{best})$恰好为0。

当训练错误率不为0，但是仍然能保证真实错误率在一定可接受范围

Hoeffding边界（附加Chernoff边界）

Hoeffding边界刻画的是某事件的真实概率及其$m$个独立试验中观察到的频率之间的差异。Hoeffding边界表明，当训练错误率$error_D(H)$在包含$m$个随机抽取样例的集合$D$上测量时，则：

$$Pr[error_{\mathscr D}(h) \gt error_D(h) + \epsilon] \le e^{-2m\epsilon^2}$$

真实错误率大于训练错误率+$\epsilon$的概率小于等于$e^{-2m\epsilon^2}$

它给出一个概率边界，说明任意选择的假设训练错误率不能代表真实情况。为保证$L$寻找到最佳的假设的错误率有以上的边界，我们必须考虑这$|H|$个假设中任一个有较大错误率的概率：

$$Pr[(\exists h \in H)(error_{\mathscr D}(h) \gt error_D(h) + \epsilon)] \le |H|e^{-2m\epsilon^2}$$

如果将此概率称为$\delta$，并且问多少个训练样例$m$才足以使$\delta$维持在一渴望得到的值内，可得下式：

$$m \ge \frac{1}{2 \epsilon^2}(ln|H| + ln(\frac{1}{\delta}))\tag{公式2}\label{eqv2}$$

这是$\eqref{eqv1}$的一般化情形，适用于当最佳假设可能有非零训练错误率时，学习器仍能选择到最佳假设$h \in H$的情形。

布尔文字的合取是PAC可学习的

假设空间$H$定义为$n$个布尔文字的合取，则假设空间$|H|$的大小为$3^n$。原因在于，任一给定的假设中每个变量可能有三种可能：该变量作为文字包含在假设中；该变量的否定作为文字包含在假设中；或假设不包含该变量。将$H=3^n$代入$\eqref{eqv2}$中，得到以下关于$n$布尔文字合取学习问题的样本复杂度：

$$m \ge \frac{1}{\epsilon}(nln3 + ln(\frac{1}{\delta}))$$

其他类别的PAC可学习性

考虑一无偏概念类$C$，它包含与$X$相关的所有可教授概念。该集合$C$对应于$X$的幂集，即$X$的所有子集的集合，共包含$|C|=2^{|H|}$个概念。若$X$中的实例定义为$n$个布尔值特征，将有$|X|=2^n$个不同实例，因此有$|C|=2^{|H|}=2^{2^n}$个不同的概念。当然为学习这样的无偏概念类，学习器本身也必须使用一无偏的假设空间$H=C$。则：

$$m \ge \frac{1}{\epsilon}(2^{n}ln2+ln(\frac{1}{\delta}))$$

K项DNF和K-CNF的概念

即某概念类有多项式级的样本复杂度，但不能够在多项式时间内学习到。

无限假设空间的样本复杂度

PAC学习的样本复杂度随假设空间对数增长。以$|H|$项来刻画样本复杂度有两个缺点。

1. 它可能导致非常弱的边界。
2. 对于无限假设空间的情形，$\eqref{eqv2}$无法适用。

这里我们考虑$H$的复杂度的另一种度量，称为$H$的Vapnik-Chervonenkis维度（简称$VC$维度或$VC(H)$)用$VC(H)$替代$|H|$使得边界更紧凑。

打散一个实例集合

$VC$维衡量假设空间复杂度的方法不是用不同假设的数量$|H|$，而是用$X$中能被$H$切底区分不同实例的数量。

首先定义对一个实例集合的打散操作。$H$中的每个$h$导致$S$中的某个划分，即$h$将$S$分割为两个子集$\{ x \in S | h(x) = 1 \}$以及$\{ x \in S | h(x) = 0 \}$。给定某实例集合$S$，有$2^{|S|}$种可能的划分，虽然其中的一些不能由$H$来表达。当$S$的每个可能的划分可由$H$中的某假设来表达时，我们称$H$打散$S$。
定义：一个实例集$S$被假设空间$H$打散，当且仅当对$S$的每个划分，存在$H$中的某假设与此划分一致。

Vapnik-Chervonenkis维度

样本复杂度与VC维

$$m \ge \frac{1}{\epsilon}(4log_2(\frac{2}{\epsilon})+8VC(H)log_2(\frac{13}{\epsilon}) \quad (VC(H) \le log_2|H|)$$

神经网络的VC维度

令$n$为网络$G$的输入数目，并且假定只有$1$个输出结点。令$G$的每个内部单元$N_i$（即每个非输入结点，隐藏层）由最多$r$个输入，并实现一个布尔函数$c_i: \mathscr R^r \rightarrow \{0,1\}$形成一函数类$C$。例如：若内部结点为感知器，那么$C$为定义在$\mathscr R^r$上的线性阀值函数类。

现在可定义$C$的$G-$合成为，网络$G$能实现的所有函数的类，其中$G$中的独立单元都取类$C$中的函数，简单地说，$C$的$G-$合成是可由网络$G$表示的假设空间。

下面的定理界定了$C$的$G-$合成的基于$C$的$VC$维和$G$的结构的$VC$维。

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

令$G$为一分层有向无环图，有$n$个输入节点和$s \ge 2$个内部节点，每个可至少$r$个输入。令$C$为$VC$维为$d$的$\mathscr R^r$上的感念类，对应于可由每个内部节点$s$描述的函数集合。令$C_G$为$C$的$G$合成，对应于可由$G$表示的函数集合。那么$VC(C_G) \le 2dslog(es)$其中$e$为自然对数的底。

这一网络$G$的$VC$维边界随单个单元的$VC$维$d$线性增长，并随$s$（即网络中阀值单元的数目）的对数乘线性增长。

$r$输入感知器使用线性决策面来表示$\mathscr R^r$上的布尔函数。在$\mathscr R^r$上的线性决策面的$VC$维为$r+1$。因此，单独的$r$输入感知器$VC$维为$r+1$。可使用这一结果及上面的定理来计算包含$s$个$r$输入感知器的分层无环网络的$VC$维边界，如下：

$$VC(C^{perceptrons}_{G}) \le 2(r+1)slog(es)$$
最后代入有 $$\begin{align} m &T \ge \frac{1}{\epsilon}(4log(\frac{2}{\delta}) + 8VC(H)log(\frac{13}{\epsilon}) \\ & \ge \frac{1}{\epsilon}(4log(\frac{2}{\delta}) + 16(r+1)slog(es)log(\frac{13}{\epsilon})) \end{align}$$

它提供了一个一般性方法，基于网络结构和单个单元的$VC$维界定分层无环单元网络的$VC$维。不过上面的结果不能直接应用于反向传播网络，原因有两个。首先，此结果应用于感知器网络，而不是sigmoid单元网络，后者是反向传播算法应用的范围。然后，注意到sigmoid单元可以任意精度逼近感知器。因此，上面的$m$边界至少会与sigmoid单元组成的分层无环网络中的一样大。

BP网络的样本度要比上面这个$m$要小