• 1.VC维和Rademacher复杂度得到的结果与具体学习算法无关,对所有学习算法都适用.
• 2.若希望获得与算法有关的分析结果,稳定性(stability)分析是这方面一个方向.

算法的”稳定性”考察的是算法在输入发生变化时,输出是否会随之发生较大的变化,学习算法的输入是训练集.
给定是来自分布的独立同分布示例,.对假设空间和学习算法,令表示基于训练集从假设空间中学得的假设,考虑的以下变化:

• 表示移除中第个样例得到的集合

• 表示替换中第个样例得到的集合

其中,服从分布并独立于.
损失函数刻画了假设的预测标记与真实标记之间的差别,简记为,下面定义关于假设的几种损失.

• 1.泛化损失

• 2.经验损失

• 3.留一(leave-one-out)损失

下面定义算法的均匀稳定性(uniform stability):

定义12.10

对任何,若学习算法满足

解析:根据三角不等式,有,将带入即可得出第一个不等式,根据表示移除中第个样本,表示替换中第个样本,那么的变动均为一个样本,根据式子12.57,,因此.

则称关于损失函数满足-均匀稳定性.
显然,若算法关于损失函数满足-均匀稳定性,则有:

也就是说,移除示例的稳定性包含替换示例的稳定性.
若损失函数有界,即对所有和有,则有

定理12.8

给定从分布上独立同分布采样得到的大小为的示例集,若学习算法满足关于损失函数的-均匀稳定性,且损失函数的上界为,则对任意,以至少的概率有

证明:比较繁琐,同书上所示,参见Foundations of Machine Learning

定理12.8给出了基于稳定性分析推导出的学习算法学得假设的泛化误差界.从式子(12.58)可看出,经验损失与泛化损失之间差别的收敛率为;若,则可保证收敛率为.与定理12.3和定理12.6比较可知,这与基于VC维和Rademacher复杂度得到的收敛率一致.
需注意,学习算法的稳定性分析所关注的是,而假设空间复杂度分析所关注的是;也就是说,稳定性分析不必考虑假设空间中所有可能的假设,只需根据算法自身的特性(稳定性)来讨论输出假设的泛化误差界,那么,稳定性与可学习性之间有什么关系呢?
首先,必须假设,这样才能保证稳定的学习算法具有一定的泛化能力,即使经验损失收敛于泛化损失,否则可学习性无从谈起,为便于计算,我们假定,带入式(12.58)可得

证明:将带入式子12.58即得证.

对损失函数,若学习算法所输出的假设满足经验损失最小化,则成算法满足经验风险最小化(Empirical Risk Minimization)原则,简称算法是ERM的,关于学习算法的稳定性和可学习性,有如下定理:

定理12.9

若学习算法是ERM且稳定的.则假设空间可学习.

解析:若学习算法是ERM且是稳定的,则假设空间可学习. 首先明确几个概念,ERM表示算法满足经验风险最小化(Empirical Risk Minimization),学习算法稳定表示,由于满足经验误差最小化,则可令表示假设空间中具有最小化泛化损失的假设,即 再令 将带入到可以解得,由Hoeffding不等式12.6 其中,带入可得 根据逆事件的概率可得 即文中至少以的概率成立. 由可以求解出 即 由可以按照同公式12.31中介绍的相同的方法推导出 又因为为关于的多项式,因此根据定理12.2,定理12.5,得到结论是(不可知)PAC可学习的.

证明,令表示中具有最小化泛化损失的假设,即

再令

由Hoeffding不等式(12.6)可知,当时,

以至少的概率成立,令式子(12.60)中

解得使

以至少的概率成立,从而可得

以至少的概率成立,定理12.9得证.
对上面这个定理读者也许会纳闷,为什么学习算法的稳定性能导出假设空间的可学习型?学习算法和假设空间是两码事,事实上,要注意到稳定性与假设空间并非无关,由稳定性的定义可知两者通过损失函数联系起来.