提升方法最早起源于统计学习理论,得到了泛化误差的上界。然而,这些上界过于宽松,没有实际的价值。提升方法的实际表现要远优于上界给出的值。Friedman et al.(2000)根据对一个指数误差函数的顺序最小化,给出了提升方法的一个不同的且非常简单的表述。

考虑下面定义的指数误差函数

E=Nn=1exp{tnfm(xn)}

其中fm(x)是一个根据基分类器yl(x)的线性组合定义的分类器,形式为

fm(x)=12ml=1αlyl(x)

tn{1,1}是训练集目标值。我们的目标是关于权系数αl和基分类器yl(x)最小化E

然而,我们不进行误差函数的全局最小化,而是假设基分类器y1(x),...,ym1(x)以及它们的系数α1,...,αm1固定,因此我们只关于αmym(x)进行最小化。分离出基分类器ym(x)的贡献,我们可以将误差函数写成

E=Nn=1exp{tnfm1(xn)12tnαmym(xn)}=w(m)nexp{12tnαmym(xn)}

其中,系数w(m)n=exp{tnfm1(xn)}可以被看做常数,因为我们只针对αmym(x)进行最如果我们将被ym(x)正确分类的数据点的集合记作Tm,并且将剩余的误分类的点记作Mm,那么我们可以将误差函数写成下面的形式

E=eαm/2nTmw(m)neαm/2nMmw(m)n=(eαm/2eαm/2)Nn=1w(m)nI(ym(xn)tn)+eαm/2Nn=1w(m)n

当我们关于ym(x)进行最小化时,我们看到第二项是常数,因此这等价于对(14.15)进行最小化,因为在求和式前面的整个可乘性因子不影响最小值的位置。类似地,关于αm最小化,我们得到了式(14.17),其中ϵm由式(14.16)定义。

根据式(14.22),我们看到,找到αmym(x)之后,数据点的权值使用下面的公式进行更新

w(m+1)n=w(m)nexp{12tnαmym(xn)}

使用下面的事实

tnym(xn)=12I(ym(xn)tn)

我们看到在下一次迭代中,权值w(m)n的更新为

w(m+1)n=w(m)nexp(αm2)exp{αmI(ym(xn)tn)}

由于exp(αm/2)n无关,因此我们看到它对于所有数据点的权值都贡献一个相同的因子,从而可以丢弃。这样我们就得到了式(14.18)。

最后,一旦所有的基分类器被训练完毕,新数据点通过计算由(14.21)定义的组合函数的符号进行分类。由于因子1/2不影响符号,因此可以省略,得到了式(14.19)。