《对“学习算法的几乎处处稳定性与泛化能力”的理解与思考.docx》由会员分享，可在线阅读，更多相关《对“学习算法的几乎处处稳定性与泛化能力”的理解与思考.docx（4页珍藏版）》请在三一文库上搜索。
1、精品文档对“学习算法的几乎处处稳定性与泛化能力”的理解与思考该篇读书报告是针对 Kutin 和 Niyogi 的论文 Almost-everywhere algorithmic stability and generalization error。为了更好的理解这篇论文，我还通过查阅相关资料了解了一些统计机器学习的相关概念。 下面我将通过问答的方式， 对我的论文阅读收获进 行总结。首先，为什么要提出学习算法稳定性的概念？长期以来，泛化性和泛化误差是通过学习机器（或者称训练模型）的复杂度来衡量，代表性的如由 Vapnik 和 Chervonenkis 所发展的统计机器学习理论。但是这种方法引入了
2、VC维或VC嫡的理论，在学习机器的复杂度越高的情况下，VC维的计算也就更加复杂，该方法的局限性也随之体现出来了。 近年来， 基于学习算法本身的研究方法被提出来， 这种方法通过引入算法稳定性的概念来对学习算法的泛化界做定量的估计， 而不会涉及学习机器本身的VC维或者VC嫡。总结而言，经典的统计学习理论是从机器的角度研究学习问题的，即研究当机器满足什么条件时学习算法具有泛化性， 而学习算法的稳定性理论是从算法自身的角度研究泛化性，这是一种全新的研究学习问题的途径。其次，学习算法稳定性是如何应用到对算法泛化能力度量的？在回答这个问题之前，先介绍经典的统计机器学习方法如何度量算法的泛化能力。回忆一个概
3、念，一个学习算法称为具有泛化性，如果对于任何概率分布P,任意的训练集 S 和任何 0 ，下述等式（1）一致成立。式中， 为期望风险（误差） ， 为经验风险（误差） 。根据这一定义，一个学习算法具有泛化性当且仅当经验误差在概率意义上收敛于期望误差。泛化性的概念是定性地描述了一个学习算法的预测能力。但从应用的角度来说，需要定量地把握学习算法的泛化能力， 故引入泛化误差界的概念。 一个算法的泛化误差界通常指 如下形式的一个估计（ 2）其中 是以?、训练集数目以及表示机器复杂度的度量为变量的正函数（如机器的 VC维） ，它刻画了学习算法经验误差收敛到期望误差的速度估计。从学习算法稳定性的角度来研究泛化
4、能力问题， 就不使用机器的任何复杂性的度量 （即公式（ 2）中的） ，而代之以使用与算法自身相关的稳定性指标 来对泛化误差进行估计。即寻求如下形式的泛化界估计（ 3）它是对机器中函数 的非一致估计，更加符合应用实际和便于应用。那么， 学习算法稳定性的概念有哪些不同的定义？ Kutin 和 Niyogi 所提出的 “几乎处处稳定 ” 的学习稳定性框架和其他的框架相比又有什么不同或优势？基于从算法自身研究学习问题起始于Devroye , Rogers和Wagner的研究，他们注意到留一估计中样本有小的改变时算法的稳定性性质，并将算法稳定性作为研究K- 最近邻算法泛化性的一个工具（此时由于机器的VC
5、维无限，传统的研究方法失效）。Kearns和Ron研究了具有有限VC维的机器和算法稳定性的关系（故仍旧依赖了传统的VC维的概念）；Bousquet 和 Elisseeff 证明了回归问题正则化算法在一定意义下是一致稳定的，并且获得了正则化算法泛化误差的一个指数界估计。但由于Bousquet和Elisseeff 定义的稳定性条件太强，Kutin和Niyogi引进了 几乎处处稳定”的概念，并在此基础上研究了学习算法的 泛化性。经过查阅资料和阅读论文，我认为判断一个学习稳定性框架的标准有两个。第一，算法稳定性概念的定义；第二，从不同稳定性概念所推导证明出的学习算法的泛化误差界。而 最理想的框架应该是
6、这样的：在不太严苛的稳定性定义下，能够推导证明出指数形式的泛 化误差界估计。要求不太严苛”的稳定性定义，因为太严苛的稳定性是一般的学习机器很难 达到的，而太弱化的稳定性定义又会导致多项式形式的泛化误差边界。显然，一个具有指数泛化误差边界的算法总是远远优于具有多项式误差边界的算法。下面就可以从稳定性定义和推导出的泛化误差界形式这两个角度来比较不同的学习稳 定性框架。在稳定性定义上，Kearns和Ron的论文提出了两种定义：“假设稳定”和“逐点假设稳定”，这两种定义可称为weak hypothesis stability ,即 弱假设稳定。Bousquet和Elisseeff 提出的定义为 一致稳
7、定，即uniform hypothesis stability ,这是一种过 于严苛的定义。而Kutin和Niyogi在此基础上提出的定义为()几乎处处稳定”，论文中称为training stability ”，将“ 一致稳定”进行了合理的弱化处理。各种稳定性的具体定 义如下：设A是一个学习算法，S是训练集，l(f, z)为损失函数，满足有界性条件(M是一个常数)。1. A称为是假设稳定的，如果2.A称为是逐点假设稳定的，如果3. A称为是致稳定的，如果4. A称为是几乎处处稳定的，如果对S以的概率成立。其中， 和分别表示从给定训练集 S中删除样本和将替换为一个新样本 所形成 的新训练集(即留
8、一训练集和换一训练集)。由上述的学习算法稳定性定义，可以分别推到出如下的泛化误差界：1 .如果算法A是 假设稳定的，则2 .如果算法A是 逐点假设稳定的，则3 .如果算法A是 一致稳定的，则4 .如果算法A是几乎处处稳定的，则从形式上来看，1和2所推导出的泛化误差界为多项式形式（结果不理想），3推导出的泛化误差界为指数形式（是最理想的），而4推导出的是一个指数和多项式混合界（当且仅当时退化成一个指数界）。单从泛化误差界来看，Bousquet和Elisseeff 提出的“ 一致稳定”所定义的稳定性框架要比Kutin和Niyogi基于“（8 几乎处处稳定”的框架效果要好。但是，后者是基于 前者进行
9、改进的，故必定有其优势所在（否则论文岂不是毫无意义）。前者使用的“ 一致稳定”定义过于约束，这导致一些学习算法由于违背这一条件而无 法应用；而后者引入“ （8 a几乎处处稳定”的定义（即在大多数情况下，在训练集里改变一 个点只会导致该集里的点的误差发生微小的改变），有效地放宽了限制条件，而且通过实验证明了由此定义能够得到良好的泛化误差界。此外，论文还证明了 “（ 8 2）几乎处处稳定”（即“ training stability ）是“ PAC可学习性”的充分必要条件。由此， “（8 ?几乎处 处稳定”定义的优势显而易见。既然基于“几乎处处稳定性”定义的学习稳定性框架这么好，那还有改进的余地吗
10、？在 哪方面可作出改进？我认为答案是肯定的。因为至少有一点没有做好：通过“几乎处处稳定”的定义推导得到的泛化误差边界 不是指数形式 的。通过查阅文献，发现确实有人通过引入新的稳定性定义， 优化了这一点。在张海和徐宗 本的论文学习算法的稳定性与泛化：一种新的稳定性框架中，他们引入了 “均方稳定”的定义，得到了与一致稳定性框架下同阶的指数式泛化误差界。主要结果如下：定义：算法A称为是均方稳定的，如果对于任何训练集，存在正实数 ，,使得O定理：如果学习算法 A是均方稳定的，且损失函数满足，则对与任意的 ，成立下述泛化误差指数界估计其中。从上面的结果可以看出，在和几乎处处稳定性框架相当的均方稳定框架下
11、，得到了和更窄的一致稳定框架下所得到的指数界同阶的指数界估计。可以说，这一新的框架是整合了几乎处处稳定和一直稳定两个框架的优点。参考文献：1Kutin S., Niyogi p., Almost-Everywhere Algorithmic Stability and Generalization Error, University of Chincago, Technical Report TR-200-03, 2002.2张海，徐宗本，学习算法的稳定性与泛化：一种新的稳定性框，西安交通大学，数学学报中文版，2009, 52（3）: 417-428欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议， 策划案计划书，学习资料等等打造全网一站式需求4欢迎下载