[comment]: # 机器学习实战 - 读书笔记(07) - 利用AdaBoost元算法提高分类性能
前言
最近在看Peter Harrington写的“机器学习实战”，这是我的学习笔记，这次是第7章 - 利用AdaBoost元算法提高分类性能。
核心思想
在使用某个特定的算法是，有时会发现生成的算法\(f(x)\)的错误率比较高，只使用这个算法达不到要求。
这时\(f(x)\)就是一个弱算法。
在以前学习算法的过程中，我们认识到算法的参数很重要，所以把公式改写成这样：
\[f(x,arguments) \\
where \\
\qquad x \text{ : calculated data} \\
\qquad arguments \text{ : function arguments}
\]
where \\
\qquad x \text{ : calculated data} \\
\qquad arguments \text{ : 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 =
\begin{cases}
\frac{1}{2}ln \left (\frac{1 - \epsilon_i}{\epsilon_i} \right), & \text{if} \epsilon_i > C \\
\frac{1}{2}ln \left (\frac{1 - \epsilon_i}{C} \right), & \text{if} \epsilon_i \leqslant C
\end{cases} \\
where \\
\qquad \epsilon_i = \frac{count(\text{wrong classified samples})}{count(\text{all samples})} \text{ : error rate of function i} \\
\qquad C \text{ : constant }\ e^{-16}
\]
\begin{cases}
\frac{1}{2}ln \left (\frac{1 - \epsilon_i}{\epsilon_i} \right), & \text{if} \epsilon_i > C \\
\frac{1}{2}ln \left (\frac{1 - \epsilon_i}{C} \right), & \text{if} \epsilon_i \leqslant C
\end{cases} \\
where \\
\qquad \epsilon_i = \frac{count(\text{wrong classified samples})}{count(\text{all samples})} \text{ : error rate of function i} \\
\qquad C \text{ : constant }\ e^{-16}
\]
解释：为什要用自然对数？
个人认为在权重方面，自然对数和\(log_2,log_{10}\)性质上是一样的，它们的结果是等比例的。
数学家倾向于使用自然对数。
求对数是可以将数据关系线性化。比如:\(log_{10}1000 = 3, log_{10}100 = 2, log_{10}10 = 1\).
* 训练算法 - 调整样本数据：每条样本数据的权重$D_1$
\[D_i^{'(t)} =
\begin{cases}
D_i^{(t)}e^{-\alpha}, & \text{if the sample is classified correctly} \\
D_i^{(t)}e^{\alpha}, & \text{if the sample is not classified correctly}
\end{cases} \\
D_i^{(t+1)} = \frac{D_i^{'(t)}}{\textstyle \sum_{j=1}^n D_j^{'(t)}} \\
where \\
\qquad \alpha \text{ : weight of current weak function} \\
\qquad D \text{ : is a vector, the length is the length of samples data} \\
\qquad D_i \text{ : is weight value of sample data i} \\
\qquad D_i^{(t)} \text{ : is weight value of sample i for this function} \\
\qquad D_i^{(t+1)} \text{ : is weight value of sample i for next week function}
\]
\begin{cases}
D_i^{(t)}e^{-\alpha}, & \text{if the sample is classified correctly} \\
D_i^{(t)}e^{\alpha}, & \text{if the sample is not classified correctly}
\end{cases} \\
D_i^{(t+1)} = \frac{D_i^{'(t)}}{\textstyle \sum_{j=1}^n D_j^{'(t)}} \\
where \\
\qquad \alpha \text{ : weight of current weak function} \\
\qquad D \text{ : is a vector, the length is the length of samples data} \\
\qquad D_i \text{ : is weight value of sample data i} \\
\qquad D_i^{(t)} \text{ : is weight value of sample i for this function} \\
\qquad D_i^{(t+1)} \text{ : is weight value of sample i for next week function}
\]
解释：
假如有1000个sample，有100个sample被分错类，则:
\[\begin{array}{lcl}
\epsilon & =\frac{100}{1000} \\
\alpha & = \frac{1}{2}ln \left(\frac{1 - \frac{100}{1000}}{\frac{100}{1000}} \right) \\
& = \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}
\]
\epsilon & =\frac{100}{1000} \\
\alpha & = \frac{1}{2}ln \left(\frac{1 - \frac{100}{1000}}{\frac{100}{1000}} \right) \\
& = \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分类器中计算公式
\[\textstyle \sum_{i=1}^n \alpha_if_i(x) \\
where \\
\qquad \alpha_i \text{ : weight of weak function i} \\
\qquad f_i(x) \text{ : weak function i}
\]
where \\
\qquad \alpha_i \text{ : weight of weak function i} \\
\qquad f_i(x) \text{ : weak function i}
\]
参考
- Machine Learning in Action by Peter Harrington
- Boosting (machine learning)