提升方法最早起源于统计学习理论,得到了泛化误差的上界。然而,这些上界过于宽松,没有实际的价值。提升方法的实际表现要远优于上界给出的值。Friedman et al.(2000)根据对一个指数误差函数的顺序最小化,给出了提升方法的一个不同的且非常简单的表述。
考虑下面定义的指数误差函数
E=N∑n=1exp{−tnfm(xn)}
其中fm(x)是一个根据基分类器yl(x)的线性组合定义的分类器,形式为
fm(x)=12m∑l=1αlyl(x)
tn∈{−1,1}是训练集目标值。我们的目标是关于权系数αl和基分类器yl(x)最小化E。
然而,我们不进行误差函数的全局最小化,而是假设基分类器y1(x),...,ym−1(x)以及它们的系数α1,...,αm−1固定,因此我们只关于αm和ym(x)进行最小化。分离出基分类器ym(x)的贡献,我们可以将误差函数写成
E=N∑n=1exp{−tnfm−1(xn)−12tnαmym(xn)}=∑w(m)nexp{−12tnαmym(xn)}
其中,系数w(m)n=exp{−tnfm−1(xn)}可以被看做常数,因为我们只针对αm和ym(x)进行最如果我们将被ym(x)正确分类的数据点的集合记作Tm,并且将剩余的误分类的点记作Mm,那么我们可以将误差函数写成下面的形式
E=e−αm/2∑n∈Tmw(m)neαm/2∑n∈Mmw(m)n=(eαm/2−e−αm/2)N∑n=1w(m)nI(ym(xn)≠tn)+e−αm/2N∑n=1w(m)n
当我们关于ym(x)进行最小化时,我们看到第二项是常数,因此这等价于对(14.15)进行最小化,因为在求和式前面的整个可乘性因子不影响最小值的位置。类似地,关于αm最小化,我们得到了式(14.17),其中ϵm由式(14.16)定义。
根据式(14.22),我们看到,找到αm和ym(x)之后,数据点的权值使用下面的公式进行更新
w(m+1)n=w(m)nexp{−12tnαmym(xn)}
使用下面的事实
tnym(xn)=1−2I(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)。