机器学习之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)

相关文章