Adaboost是一种组合学习的提升算法，能将多个弱学习算法（甚至只比随机猜测好一点）组合起来，构成一个足够强大的学习模型。
组合学习
组合学习是将多个假说组合起来，并集成它们的预测。比如对于一个问题，我们可以生成20棵决策树，让它们对新样例的分类进行预测，最后通过投票决定最终的预测。这样可以有效的降低错误率。
提升
提升是一种广泛使用的组合学习。首先解释加权训练集的概念。在这样的训练集中，每个样例都有一个权重w（不小于0）来表示一个样例的重要程度。提升算法开始于所有样例的权重均为1，从这样的训练集中产生了第一个假说H1，这个假说也许会对一些测试样例进行错误的分类，于是我们把这些样例挑选出来并增加它们的权重，然后把修改后的训练集提供给下一个假说H2进行训练。直到K个假说都产生之后，我们输出一个组合假说，它是这K个假说的加权多数函数，某个假说的权重大小取决于它在训练集上的表现。
例如下图所示，我们通过增加被错误分类的样例的权重，可以使得下一个弱学习算法在错误分类样例上表现得更好。
AdaBoost
function AdaBoost(examples, L, K) returns a weighted hypothesisinputs: exmaples, a set of example for learningL, a learning algorithmK, the number of hypotheseslocal variable: w, a vector of weighth, a vector of K hypotheses, initially 1/Nz, a vector of K hypothesis weightfor k = 1 to K doh[k] = L(examples, w)error = 0for i = 1 to N doif h[k](x_i) != y_i then error = error+w[i]for i = 1 to N doif h[k](x_i) == y_i then w[i] = w[i]*error/(1-error)w = Normalize(w)z[k] = log(1-error)/errorreturn (h, z)