前言

最近在看Peter Harrington写的“机器学习实战”，这是我的学习笔记，这次是第7章 - 利用AdaBoost元算法提高分类性能。

核心思想

在使用某个特定的算法是，有时会发现生成的算法(f(x))的错误率比较高，只使用这个算法达不到要求。
这时(f(x))就是一个弱算法。
在以前学习算法的过程中，我们认识到算法的参数很重要，所以把公式改写成这样：

[f(x,arguments) \ where \ qquad x ext{ : calculated data} \ qquad arguments ext{ : function arguments} ]

一个思路是通过多个弱算法组合形成一个强算法来满足需求。
训练多个弱算法的思路如下：

根据样本数据，求出(f(x,arguments_1))；
调整样本数据：将满足匹配(f(x,arguments_1))的样本数据的权重调低，将不满足匹配(f(x,arguments_1))的样本数据的权重调高。
重复以上步骤，训练出多个弱算法算法(f(x,arguments_1), ..., f(x,arguments_n))，直到这些弱算法组合的错误率等于0，或者小于指定值为止。

这个思路称之为Adaboost算法，是对其它算法组合的一种方式。
我们可以看出弱算法是同类的算法，也就是说，它们是基于相同的算法，只不过参数不同。这样元算法在训练算法的步骤中就好容易控制。
注：也有其它的的元算法，可以针对不同算法的。

基本概念

元算法（meta-algorithm），是对其它算法组合的一种方式。也称为集成方法(ensemble method)。
弱算法：准确度较低的算法。元算法通过组合多个弱算法来提高准确率。
强算法：可以认为是组合后的算法。
boosting ：是一种元算法，将多个弱算法变成强算法的算法族。除了AdsBoost，还有LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost, and others.
Adaboost ： Adaptive Boosting的简称。一个具体的boosting算法。本章就是介绍这个算法。

详解Adaboost

说明：书中弱算法是一个单层决策树算法，返回的是一个二类分类结果(-1, 1)。所以书中Adaboost也是一个二类分类算法。

Adaboost训练算法

输入
- 样本数据
- 弱算法的数量
输出
- 一个弱算法数组(弱算法参数，弱算法权重(alpha_i))
逻辑

在一个迭代中(弱算法数量)
    计算当前算法的参数
    计算当前算法的错误率
    计算当前算法的权重
    计算下次样本数据的权重
    计算当前的样本数据错误数，如果是0,退出。

核心数学公式
- 训练算法 - 计算弱算法(f_i(x))的权重(alpha_i):

[alpha_i = egin{cases} frac{1}{2}ln left (frac{1 - epsilon_i}{epsilon_i} ight), & ext{if} epsilon_i > C \ frac{1}{2}ln left (frac{1 - epsilon_i}{C} ight), & ext{if} epsilon_i leqslant C end{cases} \ where \ qquad epsilon_i = frac{count( ext{wrong classified samples})}{count( ext{all samples})} ext{ : error rate of function i} \ qquad C ext{ : constant } e^{-16} ]

解释：为什要用自然对数？
个人认为在权重方面，自然对数和(log_2,log_{10})性质上是一样的，它们的结果是等比例的。
数学家倾向于使用自然对数。
求对数是可以将数据关系线性化。比如:(log_{10}1000 = 3, log_{10}100 = 2, log_{10}10 = 1).

* 训练算法 - 调整样本数据：每条样本数据的权重$D_1$

[D_i^{'(t)} = egin{cases} D_i^{(t)}e^{-alpha}, & ext{if the sample is classified correctly} \ D_i^{(t)}e^{alpha}, & ext{if the sample is not classified correctly} end{cases} \ D_i^{(t+1)} = frac{D_i^{'(t)}}{ extstyle sum_{j=1}^n D_j^{'(t)}} \ where \ qquad alpha ext{ : weight of current weak function} \ qquad D ext{ : is a vector, the length is the length of samples data} \ qquad D_i ext{ : is weight value of sample data i} \ qquad D_i^{(t)} ext{ : is weight value of sample i for this function} \ qquad D_i^{(t+1)} ext{ : is weight value of sample i for next week function} ]

解释：
假如有1000个sample，有100个sample被分错类，则:

[egin{array}{lcl} epsilon & =frac{100}{1000} \ alpha & = frac{1}{2}ln left(frac{1 - frac{100}{1000}}{frac{100}{1000}} ight) \ & = frac{1}{2}ln(9) \ D_{correct}^{'} & = 1 * e^{-frac{1}{2}ln(9)} \ & = frac{1}{e^{frac{1}{2}} * 9} \ D_{incorrect}^{'} & = 1 * e^{frac{1}{2}ln(9)} \ & = e^{frac{1}{2}} * 9 \ frac{D_{incorrect}^{'}}{D_{correct}^{'}} & = e * 9 ^ 2 end{array} ]

可以看出错误的sample占的比例越小，下次的权重是二次方级数增大。

Adaboost分类算法

输入
- 分类数据
- 弱算法数组
输出
- 分类结果
逻辑

在一个迭代中(弱算法数量)
    用当前弱算法计算分类结果$classified_i$
    计算强分类结果（使用下面的公式）
返回分类结果

AdaBoost分类器中计算公式

[ extstyle sum_{i=1}^n alpha_if_i(x) \ where \ qquad alpha_i ext{ : weight of weak function i} \ qquad f_i(x) ext{ : weak function i} ]

参考

Machine Learning in Action by Peter Harrington
Boosting (machine learning)