对“学习算法的几乎处处稳定性与泛化能力”的理解与思考Word格式.docx

对“学习算法的几乎处处稳定性与泛化能力”的理解与思考Word格式.docx

《对“学习算法的几乎处处稳定性与泛化能力”的理解与思考Word格式.docx》由会员分享，可在线阅读，更多相关《对“学习算法的几乎处处稳定性与泛化能力”的理解与思考Word格式.docx（3页珍藏版）》请在冰点文库上搜索。

在回答这个问题之前，先介绍经典的统计机器学习方法如何度量算法的泛化能力。

回忆一个概念，一个学习算法称为具有泛化性，如果对于任何概率分布P，任意的训练集S和任何ϵ>

0，下述等式

limm→∞PIfs-ISfs>

ϵ=0

（1）

一致成立。

式中，Ifs为期望风险（误差），Isfs为经验风险（误差）。

根据这一定义，一个学习算法具有泛化性当且仅当经验误差在概率意义上收敛于期望误差。

泛化性的概念是定性地描述了一个学习算法的预测能力。

但从应用的角度来说，需要定量地把握学习算法的泛化能力，故引入泛化误差界的概念。

一个算法的泛化误差界通常指如下形式的一个估计

Psupfs∈FIfs-ISfs>

ϵ≤δϵ,m,lF

（2）

其中δ是以ϵ、训练集数目m以及表示机器复杂度的度量l（F）为变量的正函数（如机器的VC维），它刻画了学习算法经验误差收敛到期望误差的速度估计。

从学习算法稳定性的角度来研究泛化能力问题，就不使用机器的任何复杂性的度量（即公式

（2）中的l（F）），而代之以使用与算法自身相关的稳定性指标l（A）来对泛化误差进行估计。

即寻求如下形式的泛化界估计

PIfs-IS[fs]>

ϵ≤δ（ϵ,m,l（A））（3）

它是对机器中函数fs的非一致估计，更加符合应用实际和便于应用。

那么，学习算法稳定性的概念有哪些不同的定义？

Kutin和Niyogi所提出的“几乎处处稳定”的学习稳定性框架和其他的框架相比又有什么不同或优势？

基于从算法自身研究学习问题起始于Devroye，Rogers和Wagner的研究，他们注意到留一估计中样本有小的改变时算法的稳定性性质，并将算法稳定性作为研究K-最近邻算法泛化性的一个工具（此时由于机器的VC维无限，传统的研究方法失效）。

Kearns和Ron研究了具有有限VC维的机器和算法稳定性的关系（故仍旧依赖了传统的VC维的概念）；

Bousquet和Elisseeff证明了回归问题正则化算法在一定意义下是一致稳定的，并且获得了正则化算法泛化误差的一个指数界估计。

但由于Bousquet和Elisseeff定义的稳定性条件太强，Kutin和Niyogi引进了“几乎处处稳定”的概念，并在此基础上研究了学习算法的泛化性。

经过查阅资料和阅读论文，我认为判断一个学习稳定性框架的标准有两个。

第一，算法稳定性概念的定义；

第二，从不同稳定性概念所推导证明出的学习算法的泛化误差界。

而最理想的框架应该是这样的：

在不太严苛的稳定性定义下，能够推导证明出指数形式的泛化误差界估计。

要求“不太严苛”的稳定性定义，因为太严苛的稳定性是一般的学习机器很难达到的，而太弱化的稳定性定义又会导致多项式形式的泛化误差边界。

显然，一个具有指数泛化误差边界的算法总是远远优于具有多项式误差边界的算法。

下面就可以从稳定性定义和推导出的泛化误差界形式这两个角度来比较不同的学习稳定性框架。

在稳定性定义上，Kearns和Ron的论文提出了两种定义：

“βh假设稳定”和“βe逐点假设稳定”，这两种定义可称为“weakhypothesisstability”，即“弱假设稳定”。

Bousquet和Elisseeff提出的定义为“βm一致稳定”，即“uniformhypothesisstability”，这是一种过于严苛的定义。

而Kutin和Niyogi在此基础上提出的定义为“（β,δ）几乎处处稳定”，论文中称为“trainingstability”，将“βm一致稳定”进行了合理的弱化处理。

各种稳定性的具体定义如下：

设A是一个学习算法，S是训练集，l（f,z）为损失函数，满足有界性条件0≤l（f,z）≤M（M是一个常数）。

1.A称为是βh假设稳定的，如果

∀i∈1,2,…,m,ES,z|lfs,z-l（fs\i,z）|≤βh。

2.A称为是βe逐点假设稳定的，如果

∀i∈1,2,…,m,ES|lfs,zi-l（fsi,zi）|≤βe。

3.A称为是βm一致稳定的，如果

∀S∈Zm,∀i∈1,2,…,m,lfs,∙-l（fs\i,∙）∞≤βm。

4.A称为是（β,δ）几乎处处稳定的，如果

∀i∈1,2,…,m,lfs,∙-l（fsi,∙）≤β

对S以1-δ的概率成立。

其中，S\i和Si分别表示从给定训练集S中删除样本zi和将zi替换为一个新样本zi'

所形成的新训练集（即留一训练集和换一训练集）。

由上述的学习算法稳定性定义，可以分别推到出如下的泛化误差界：

1.如果算法A是βh假设稳定的，则

PIfs≤Iloofs+δ-1M2+6Mmβh2m≥1-δ.

2.如果算法A是βe逐点假设稳定的，则

PIfs≤Imfs+δ-1M2+12Mmβe2m≥1-δ.

3.如果算法A是βm一致稳定的，则∀ε,δ>

0,

P{Ifs≤Imfs≤2βm+ε}≪exp⁡（-2mε2（4mβm+M）2）;

P{Ifs≤Iloofs≤βm+ε}≪exp⁡（-2mε2（4mβm+M）2）.

4.如果算法A是（β,δ）几乎处处稳定的，则∀ε,δ>

P{Imfs-Ifs>

ε+β+Mδ}≪2（exp-lε282lβ+M2+4l2Mδ2lβ+M）.

从形式上来看，1和2所推导出的泛化误差界为多项式形式（结果不理想），3推导出的泛化误差界为指数形式（是最理想的），而4推导出的是一个指数和多项式混合界（当且仅当δm=o（exp⁡（-mτ））时退化成一个指数界）。

单从泛化误差界来看，Bousquet和Elisseeff提出的“βm一致稳定”所定义的稳定性框架要比Kutin和Niyogi基于“（β,δ）几乎处处稳定”的框架效果要好。

但是，后者是基于前者进行改进的，故必定有其优势所在（否则论文岂不是毫无意义）。

前者使用的“βm一致稳定”定义过于约束，这导致一些学习算法由于违背这一条件而无法应用；

而后者引入“（β,δ）几乎处处稳定”的定义（即在大多数情况下，在训练集里改变一个点只会导致该集里的点的误差发生微小的改变），有效地放宽了限制条件，而且通过实验证明了由此定义能够得到良好的泛化误差界。

此外，论文还证明了“（β,δ）几乎处处稳定”（即“trainingstability”）是“PAC可学习性”的充分必要条件。

由此，“（β,δ）几乎处处稳定”定义的优势显而易见。

既然基于“几乎处处稳定性”定义的学习稳定性框架这么好，那还有改进的余地吗？

在哪方面可作出改进？

我认为答案是肯定的。

因为至少有一点没有做好：

通过“几乎处处稳定”的定义推导得到的泛化误差边界不是指数形式的。

通过查阅文献，发现确实有人通过引入新的稳定性定义，优化了这一点。

在张海和徐宗本的论文《学习算法的稳定性与泛化：

一种新的稳定性框架》中，他们引入了“{βim}均方稳定”的定义，得到了与一致稳定性框架下同阶的指数式泛化误差界。

主要结果如下：

定义：

算法A称为是{βim}均方稳定的，如果对于任何训练集S∈Zm，存在正实数{βim}，i=1,…,m，使得

E（lfs,∙-l（fsi,∙））2|z1,z2,…,zm≤βim。

定理：

如果学习算法A是{βim}均方稳定的，且损失函数满足0≤l（f,z）≤M，则对与任意的ϵ>

0，成立下述泛化误差指数界估计

P{Ifs>

Imfs+β+ϵ}≪exp⁡（-ϵ216i=1mβim+48Mi=1mβimm+48M2m），

其中β=maxiβim。

从上面的结果可以看出，在和几乎处处稳定性框架相当的均方稳定框架下，得到了和更窄的一致稳定框架下所得到的指数界同阶的指数界估计。

可以说，这一新的框架是整合了几乎处处稳定和一直稳定两个框架的优点。

参考文献：

[1]KutinS.,Niyogip.,Almost-EverywhereAlgorithmicStabilityandGeneralizationError,UniversityofChincago,TechnicalReportTR-200-03,2002.

[2]张海,徐宗本,学习算法的稳定性与泛化:

一种新的稳定性框,西安交通大学,数学学报中文版,2009,52（3）:

417-428