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

对“学习算法的几乎处处稳定性与泛化能力”的理解与思考该篇读书报告是针对Kutin和Niyogi的论文《Almost-everywherealgorithmicstabilityandgeneralizationerror》。为了更好的理解这篇论文，我还通过查阅相关资料了解了一些统计机器学习的相关概念。下面我将通过问答的方式，对我的论文阅读收获进行总结。首先，为什么要提出学习算法稳定性的概念？长期以来，泛化性和泛化误差是通过学习机器（或者称训练模型）的复杂度来衡量，代表性的如由Vapnik和Chervonenkis所发展的统计机器学习理论。但是这种方法引入了VC维或VC熵的理论，在学习机器的复杂度越高的情况下，VC维的计算也就更加复杂，该方法的局限性也随之体现出来了。近年来，基于学习算法本身的研究方法被提出来，这种方法通过引入算法稳定性的概念来对学习算法的泛化界做定量的估计，而不会涉及学习机器本身的VC维或者VC熵。总结而言，经典的统计学习理论是从机器的角度研究学习问题的，即研究当机器满足什么条件时学习算法具有泛化性，而学习算法的稳定性理论是从算法自身的角度研究泛化性，这是一种全新的研究学习问题的途径。其次，学习算法稳定性是如何应用到对算法泛化能力度量的？在回答这个问题之前，先介绍经典的统计机器学习方法如何度量算法的泛化能力。回忆一个概念，一个学习算法称为具有泛化性，如果对于任何概率分布P，任意的训练集S和任何ϵ0，下述等式lim𝑚→∞𝑃{|𝐼[𝑓𝑠]−𝐼𝑆[𝑓𝑠]|ϵ}=0（1）一致成立。式中，𝐼[𝑓𝑠]为期望风险（误差），𝐼𝑠[𝑓𝑠]为经验风险（误差）。根据这一定义，一个学习算法具有泛化性当且仅当经验误差在概率意义上收敛于期望误差。泛化性的概念是定性地描述了一个学习算法的预测能力。但从应用的角度来说，需要定量地把握学习算法的泛化能力，故引入泛化误差界的概念。一个算法的泛化误差界通常指如下形式的一个估计P{sup𝑓𝑠∈𝐹|𝐼[𝑓𝑠]−𝐼𝑆[𝑓𝑠]|ϵ}≤𝛿(𝜖,𝑚,𝑙(𝐹))（2）其中𝛿是以ϵ、训练集数目𝑚以及表示机器复杂度的度量𝑙(𝐹)为变量的正函数（如机器的VC维），它刻画了学习算法经验误差收敛到期望误差的速度估计。从学习算法稳定性的角度来研究泛化能力问题，就不使用机器的任何复杂性的度量（即公式（2）中的𝑙(𝐹)），而代之以使用与算法自身相关的稳定性指标𝑙(𝐴)来对泛化误差进行估计。即寻求如下形式的泛化界估计P{|𝐼[𝑓𝑠]−𝐼𝑆[𝑓𝑠]|ϵ}≤𝛿(𝜖,𝑚,𝑙(𝐴))（3）它是对机器中函数𝑓𝑠的非一致估计，更加符合应用实际和便于应用。那么，学习算法稳定性的概念有哪些不同的定义？Kutin和Niyogi所提出的“几乎处处稳定”的学习稳定性框架和其他的框架相比又有什么不同或优势？基于从算法自身研究学习问题起始于Devroye，Rogers和Wagner的研究，他们注意到留一估计中样本有小的改变时算法的稳定性性质，并将算法稳定性作为研究K-最近邻算法泛化性的一个工具（此时由于机器的VC维无限，传统的研究方法失效）。Kearns和Ron研究了具有有限VC维的机器和算法稳定性的关系（故仍旧依赖了传统的VC维的概念）；Bousquet和Elisseeff证明了回归问题正则化算法在一定意义下是一致稳定的，并且获得了正则化算法泛化误差的一个指数界估计。但由于Bousquet和Elisseeff定义的稳定性条件太强，Kutin和Niyogi引进了“几乎处处稳定”的概念，并在此基础上研究了学习算法的泛化性。经过查阅资料和阅读论文，我认为判断一个学习稳定性框架的标准有两个。第一，算法稳定性概念的定义；第二，从不同稳定性概念所推导证明出的学习算法的泛化误差界。而最理想的框架应该是这样的：在不太严苛的稳定性定义下，能够推导证明出指数形式的泛化误差界估计。要求“不太严苛”的稳定性定义，因为太严苛的稳定性是一般的学习机器很难达到的，而太弱化的稳定性定义又会导致多项式形式的泛化误差边界。显然，一个具有指数泛化误差边界的算法总是远远优于具有多项式误差边界的算法。下面就可以从稳定性定义和推导出的泛化误差界形式这两个角度来比较不同的学习稳定性框架。在稳定性定义上，Kearns和Ron的论文提出了两种定义：“𝛽ℎ假设稳定”和“𝛽𝑒逐点假设稳定”，这两种定义可称为“weakhypothesisstability”，即“弱假设稳定”。Bousquet和Elisseeff提出的定义为“𝛽𝑚一致稳定”，即“uniformhypothesisstability”，这是一种过于严苛的定义。而Kutin和Niyogi在此基础上提出的定义为“(𝛽,𝛿)几乎处处稳定”，论文中称为“trainingstability”，将“𝛽𝑚一致稳定”进行了合理的弱化处理。各种稳定性的具体定义如下：设A是一个学习算法，S是训练集，l(f,z)为损失函数，满足有界性条件0≤l(f,z)≤M（M是一个常数）。1.A称为是𝛽ℎ假设稳定的，如果∀𝑖∈{1,2,…,𝑚},𝐸𝑆,𝑧|𝑙(𝑓𝑠,𝑧)−𝑙(𝑓𝑠\𝑖,𝑧)|≤𝛽ℎ。2.A称为是𝛽𝑒逐点假设稳定的，如果∀𝑖∈{1,2,…,𝑚},𝐸𝑆|𝑙(𝑓𝑠,𝑧𝑖)−𝑙(𝑓𝑠𝑖,𝑧𝑖)|≤𝛽𝑒。3.A称为是𝛽𝑚一致稳定的，如果∀𝑆∈𝑍𝑚,∀𝑖∈{1,2,…,𝑚},‖𝑙(𝑓𝑠,∙)−𝑙(𝑓𝑠\𝑖,∙)‖∞≤𝛽𝑚。4.A称为是(𝛽,𝛿)几乎处处稳定的，如果∀𝑖∈{1,2,…,𝑚},|𝑙(𝑓𝑠,∙)−𝑙(𝑓𝑠𝑖,∙)|≤𝛽对S以1−𝛿的概率成立。其中，𝑆\𝑖和𝑆𝑖分别表示从给定训练集S中删除样本𝑧𝑖和将𝑧𝑖替换为一个新样本𝑧𝑖′所形成的新训练集（即留一训练集和换一训练集）。由上述的学习算法稳定性定义，可以分别推到出如下的泛化误差界：1.如果算法A是𝛽ℎ假设稳定的，则P{I[𝑓𝑠]≤𝐼𝑙𝑜𝑜[𝑓𝑠]+√𝛿−1𝑀2+6𝑀𝑚𝛽ℎ2𝑚}≥1−δ.2.如果算法A是𝛽𝑒逐点假设稳定的，则P{I[𝑓𝑠]≤𝐼𝑚[𝑓𝑠]+√𝛿−1𝑀2+12𝑀𝑚𝛽𝑒2𝑚}≥1−δ.3.如果算法A是𝛽𝑚一致稳定的，则∀ε,δ0,P{I[𝑓𝑠]≤𝐼𝑚[𝑓𝑠]≤2𝛽𝑚+ε}≪exp(−2𝑚𝘀2(4𝑚𝛽𝑚+𝑀)2);P{I[𝑓𝑠]≤𝐼𝑙𝑜𝑜[𝑓𝑠]≤𝛽𝑚+ε}≪exp(−2𝑚𝘀2(4𝑚𝛽𝑚+𝑀)2).4.如果算法A是(𝛽,𝛿)几乎处处稳定的，则∀ε,δ0,P{|𝐼𝑚[𝑓𝑠]−I[𝑓𝑠]|ε+β+Mδ}≪2(exp(−𝑙𝘀28(2𝑙𝛽+𝑀)2)+4𝑙2𝑀𝛿2𝑙𝛽+𝑀).从形式上来看，1和2所推导出的泛化误差界为多项式形式（结果不理想），3推导出的泛化误差界为指数形式（是最理想的），而4推导出的是一个指数和多项式混合界（当且仅当δ𝑚=𝑜(exp(−𝑚𝜏))时退化成一个指数界）。单从泛化误差界来看，Bousquet和Elisseeff提出的“𝜷𝒎一致稳定”所定义的稳定性框架要比Kutin和Niyogi基于“(β,δ)几乎处处稳定”的框架效果要好。但是，后者是基于前者进行改进的，故必定有其优势所在（否则论文岂不是毫无意义）。前者使用的“𝛽𝑚一致稳定”定义过于约束，这导致一些学习算法由于违背这一条件而无法应用；而后者引入“(β,δ)几乎处处稳定”的定义（即在大多数情况下，在训练集里改变一个点只会导致该集里的点的误差发生微小的改变），有效地放宽了限制条件，而且通过实验证明了由此定义能够得到良好的泛化误差界。此外，论文还证明了“(β,δ)几乎处处稳定”（即“trainingstability”）是“PAC可学习性”的充分必要条件。由此，“(β,δ)几乎处处稳定”定义的优势显而易见。既然基于“几乎处处稳定性”定义的学习稳定性框架这么好，那还有改进的余地吗？在哪方面可作出改进？我认为答案是肯定的。因为至少有一点没有做好：通过“几乎处处稳定”的定义推导得到的泛化误差边界不是指数形式的。通过查阅文献，发现确实有人通过引入新的稳定性定义，优化了这一点。在张海和徐宗本的论文《学习算法的稳定性与泛化：一种新的稳定性框架》中，他们引入了“{β𝑖𝑚}均方稳定”的定义，得到了与一致稳定性框架下同阶的指数式泛化误差界。主要结果如下：定义：算法A称为是{β𝑖𝑚}均方稳定的，如果对于任何训练集S∈𝑍𝑚，存在正实数{β𝑖𝑚}，i=1,…,m，使得E(𝑙(𝑓𝑠,∙)−𝑙(𝑓𝑠𝑖,∙))2|z1,𝑧2,…,𝑧𝑚≤β𝑖𝑚。定理：如果学习算法A是{β𝑖𝑚}均方稳定的，且损失函数满足0≤l(f,z)≤M，则对与任意的ϵ0，成立下述泛化误差指数界估计P{I[𝑓𝑠]𝐼𝑚[𝑓𝑠]+√𝛽+ϵ}≪exp(−𝜖216∑β𝑖𝑚+48𝑀∑√β𝑖𝑚𝑚𝑖=1𝑚+48𝑀2𝑚𝑚𝑖=1)，其中β=max𝑖β𝑖𝑚。从上面的结果可以看出，在和几乎处处稳定性框架相当的均方稳定框架下，得到了和更窄的一致稳定框架下所得到的指数界同阶的指数界估计。可以说，这一新的框架是整合了几乎处处稳定和一直稳定两个框架的优点。参考文献：[1]KutinS.,Niyogip.,Almost-EverywhereAlgorithmicStabilityandGeneralizationError,UniversityofChincago,TechnicalReportTR-200-03,2002.[2]张海,徐宗本,学习算法的稳定性与泛化:一种新的稳定性框,西安交通大学,数学学报中文版,2009,52(3):417-428