Adaboost与指数损失 - Breezedeus | 算法优化世界

Adaboost是著名的ensemble分类算法，具体算法描述见下图1：

Adaboost算法

上面算法步骤里，有两个关键点：

下面从可加模型和指数损失的角度来说明为什么样本权重和子分类器权重的计算公式是上面那样的。

记m≜fθ(x)y（其中y∈{−1,1}），指数损失如下定义，它也是0/1损失的一种近似（见下图）：

Jexp(m)=exp(−m) 。

指数损失函数

而可加模型是多个输出为1和−1的二值基函数{φj}bj=1的线性组合：

fθ(x)=b∑j=1θjφj(x) ，

它通过最小化指数损失来逐步学习φj：

minθn∑i=1exp(−fθ(xi)yi) 。

例如，我们已经获得了˜f(x)，那么学习下一个基函数φ和θ就是通过最小化下面的指数损失目标函数来获得：

minθ, φn∑i=1exp(−{˜f(xi)+θφ(xi)}yi)=minθ, φn∑i=1˜ωiexp(−θφ(xi)yi) ，

˜ωi≜exp(−˜f(xi)yi) 。

这就是Adaboost里样本权重的计算公式（未归一化）。

不妨设θ≥0（θ<0时只要把φ的符号反一下就行），则：

n∑i=1˜ωiexp(−θφ(xi)yi)=exp(−θ)∑i: yi=φ(xi)˜ωi+exp(θ)∑i: yi≠φ(xi)˜ωi=(exp(θ)−exp(−θ))n∑i=1˜ωi2(1−φ(xi)yi)+exp(−θ)n∑i=1˜ωi 。

所以，φ的估计可以通过最小化下面的目标函数获得：

ˆφ=argminφn∑i=1˜ωi2(1−φ(xi)yi) 。

而前面的式子对θ求导，并使其等于0，可以得到θ的估计：

ˆθ=12log1−ˆRˆR ，

ˆR≜1∑ni=1˜ωin∑i=1˜ωi2(1−φ(xi)yi) 。

上面计算ˆθ的公式，就是Adaboost里子分类器对应权重的计算公式。

经过上面的推导，我们可以认为Adaboost对应着指数损失函数的可加模型。很多研究者也提出了基于其他损失函数的Boosting算法，如MAdaboost和Logitboost等。

更详细的资料可见参考文献1。

References

Adaboost与指数损失