[关闭]
@devilogic 2019-02-22T05:25:26.000000Z 字数 5960 阅读 1159

计算学习理论(PAC)

devilogic


介绍

学习器的属性

计算理论的目标

判断成功的方式

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

可能学习近似正确假设

PAC可学习性

定义:考虑定义在长度为的实例集合上的一概念类别,学习器使用假设空间。当对所有上的分布满足以及满足时,学习器将以至少的概率输出以假设,使,这时称是使用可PAC学习的。所使用的时间为以及的多项式函数。

其时间最多是以多项式方式增长,多项式中定义了对输出假设要求的强度,则定义了实例空间和概念类别中固有的复杂度。这里,中实例的长度。

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

隐含限制

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

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

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

一致学习器

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

变型空间

变型空间被定义为能正确分类训练样例的所有假设的集合:

变型空间的重要意义在于,每个一致学习器都输出一个属于变型空间的假设,而不论有怎样的实例空间、假设空间或训练数据。原因很简单,由变型空间的定义,包含中所有的一致假设。因此,为界定任意一致学习器所需的样例数量,只需要界定为保证变型空间中没有不可接受假设所需的样例数量

定义:考虑一假设空间,目标概念,实例分布以及的一组训练样例。当中每个假设关于错误率小于时,变型空间被称为关于详尽()的。

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

变型空间的详尽化

若假设空间有限,且为目标概念个独立随机抽取的样例序列,那么对于任意,变型空间不是详尽(关于)的概率小于或等于:

上述的意思就是训练不出来或者训练不理想的最大概率是得到一个训练失败概率的上界。

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


并且因为,上式最多为。最后,使用一个通用不等式:当,因此:
定理得证。

证明通用不等式 当
证明:

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

从中解出,可得到:

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

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

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

不可知学习和不一致假设

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

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

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

Hoeffding边界(附加Chernoff边界)

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

真实错误率大于训练错误率+的概率小于等于

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

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

这是的一般化情形,适用于当最佳假设可能有非零训练错误率时,学习器仍能选择到最佳假设的情形。

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

假设空间定义为个布尔文字的合取,则假设空间的大小为。原因在于,任一给定的假设中每个变量可能有三种可能:该变量作为文字包含在假设中;该变量的否定作为文字包含在假设中;或假设不包含该变量。将代入中,得到以下关于布尔文字合取学习问题的样本复杂度:

其他类别的PAC可学习性

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

K项DNF和K-CNF的概念

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

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

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

  1. 它可能导致非常弱的边界。
  2. 对于无限假设空间的情形,无法适用。

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

打散一个实例集合

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

首先定义对一个实例集合的打散操作。中的每个导致中的某个划分,即分割为两个子集以及。给定某实例集合,有种可能的划分,虽然其中的一些不能由来表达。当的每个可能的划分可由中的某假设来表达时,我们称打散
定义:一个实例集被假设空间打散,当且仅当对的每个划分,存在中的某假设与此划分一致。

Vapnik-Chervonenkis维度

样本复杂度与VC维

神经网络的VC维度

为网络的输入数目,并且假定只有个输出结点。令的每个内部单元(即每个非输入结点,隐藏层)由最多个输入,并实现一个布尔函数形成一函数类。例如:若内部结点为感知器,那么为定义在上的线性阀值函数类。

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

下面的定理界定了合成的基于维和的结构的维。

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

为一分层有向无环图,有个输入节点和个内部节点,每个可至少个输入。令维为上的感念类,对应于可由每个内部节点描述的函数集合。令合成,对应于可由表示的函数集合。那么其中为自然对数的底。

这一网络维边界随单个单元的线性增长,并随(即网络中阀值单元的数目)的对数乘线性增长。

输入感知器使用线性决策面来表示上的布尔函数。在上的线性决策面的维为。因此,单独的输入感知器维为。可使用这一结果及上面的定理来计算包含输入感知器的分层无环网络的维边界,如下:


最后代入有

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

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注