机器学习之AdaBoost

时间:2024-07-26 12:05:14

Adaboost是一种组合学习的提升算法,能将多个弱学习算法(甚至只比随机猜测好一点)组合起来,构成一个足够强大的学习模型。

组合学习

组合学习是将多个假说组合起来,并集成它们的预测。比如对于一个问题,我们可以生成20棵决策树,让它们对新样例的分类进行预测,最后通过投票决定最终的预测。这样可以有效的降低错误率。

提升

 提升是一种广泛使用的组合学习。首先解释加权训练集的概念。在这样的训练集中,每个样例都有一个权重w(不小于0)来表示一个样例的重要程度。提升算法开始于所有样例的权重均为1,从这样的训练集中产生了第一个假说H1,这个假说也许会对一些测试样例进行错误的分类,于是我们把这些样例挑选出来并增加它们的权重,然后把修改后的训练集提供给下一个假说H2进行训练。直到K个假说都产生之后,我们输出一个组合假说,它是这K个假说的加权多数函数,某个假说的权重大小取决于它在训练集上的表现。

 例如下图所示,我们通过增加被错误分类的样例的权重,可以使得下一个弱学习算法在错误分类样例上表现得更好。

机器学习之AdaBoost

AdaBoost

function AdaBoost(examples, L, K) returns a weighted hypothesis
inputs: exmaples, a set of example for learning
L, a learning algorithm
K, the number of hypotheses
local variable: w, a vector of weight
h, a vector of K hypotheses, initially 1/N
z, a vector of K hypothesis weight for k = 1 to K do
h[k] = L(examples, w)
error = 0
for i = 1 to N do
if h[k](x_i) != y_i then error = error+w[i]
for i = 1 to N do
if h[k](x_i) == y_i then w[i] = w[i]*error/(1-error)
w = Normalize(w)
z[k] = log(1-error)/error
return (h, z)