提升方法的基本思路
理论基础：
强可学习(strongly learning)：在概率近似正确(probably approximately correct, PAC)学习框架下，一个概念(一个类)如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么称他为强可学习的。
弱可学习(weakly learnable): 一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测好，那么称这个概念为弱可学习的。
Schapire证明强可学习与弱可学习是等价的。即在PAC学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。这样如果发现了“弱学习算法”能否将他提升为“强可学习算法”。大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布)，针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。下面介绍最典型的AdaBoost算法。
还有两个问题是：
1) 每一轮如何改变训练数据的权值或概率分布？
AdaBoost的做法是提高被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。
2) 如何将弱分类器组合为一个强分类器？
AdaBoost 采取加权多数表决方法，加大分类误差率小的弱分类器的权重，使其在表决中起较大作用，减小分类误差率大的弱分类器的权值，使其表决中起较小的作用。
AdaBoost算法
AdaBoost二分类算法
假设给定一个二分类训练数据集：
其中，每个样本点由实例与标记组成，实例 $ x_{i}\epsilon\chi\subseteq\mathbb{R}_{n} $ , 标记 $ y_{i}\epsilon Y =(-1,+1) $ , X 是实例空间，Y是标记集合。
算法：AdaBoost
输入：训练数据集 $ T=((x_{1}, y_{1}),(x_{2},y_{2}),…,(x_{N},y_{N})) $ ,其中 $ x_{i}\epsilon\chi \subseteq\mathbb{R}_{n},y_{i}\epsilon Y =(-1,+1) $ ;弱学习算法。
输出：最终分类器G(x).
- (1) 初始化训练数据的权值分布：
$$ D_{1}=(w_{11},…,w_{1i},…,w_{1N}), w_{1i}=\frac{1}{N}, i=1,2,…,N $$ - (2) 对 m=1,2,…,M
– (a) 使用具有权值分布 $ D_{m} $ 的训练数据集学习，得到基本分类器：$$ G_{m}(x):\chi \rightarrow (-1,+1). $$
– (b) 计算 $ G_{m}(x) $ 在训练数据集上的分类误差率：$$ e_{m}=P(G_{m}(x_{i})\neq y_{i})=\sum_{i=1}^{N}w_{mi}I(G_{m}(x_{i})\neq y_{i}) $$
– (c) 计算 $ G_{m}(x) $ 的系数：$$ \alpha_{m}=\frac{1}{2}log\frac{1-e_{m}}{e_{m}} $$
– (d) 更新训练数据集的权值分布：$$ D_{m+1}=(w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N}) $$ $$ w_{m+1,i}=\frac{w_{mi}}{Z_{m}}exp(-\alpha_{m}y_{i}G_{m}(x_{i})),i=1,2,…,N $$
这里， $ Z_{m} $ 是规范因子$$ Z_{m}=\sum_{i=1}^{N}w_{mi}exp(-\alpha_{m}y_{i}G_{m}(x_{i})) $$
它使 $ D_{m+1} $ 成为一个概率分布. - (3) 构建基本分类器的线性组合
$$ f(x)=\sum_{m=1}^{M}\alpha_{m}G_{m}(x) $$
得到最终分类器：$$ G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_{m}G_{m}(x)) $$
AdaBoost回归问题算法流程
输入：样本集 $ T=((x_{1},y_{1}),(x_{2},y_{2}),…,(x_{m},y_{m})) $ , 弱学习器算法，弱学习器迭代器K.
输出：强学习器 $ f(x) $
- (1) 初始化样本权重：
$$ D_{1}=(w_{11},…,w_{1i},…,w_{1N}), w_{1i}=\frac{1}{N}, i=1,2,…,N $$ - (2) 对于k=1,2,…,k:
– a) 使用具有权重 $ D_{k} $ 的样本集来训练数据，得到弱学习器 $ G_{k}(x) $
– b) 计算训练集上的最大误差： $ E_{k}=max|y_{i} - G_{k}(x_{i})|, i=1,2,…,m $
– c) 计算每个样本相对误差：
— 如果是线性误差，则 $ e_{ki} = \frac{|y_{i}-G_{k}(x_{i})|}{E_{k}} $
— 如果是平方误差，则 $ e_{ki} = \frac{(y_{i}-G_{k}(x_{i}))^{2}}{E_{k}^{2}} $
— 如果是指数误差，则 $ e_{ki} = 1-exp(\frac{-|y_{i}-G_{k}(x_{i})|}{E_{k}}) $
– d) 计算回归误差率： $ e_{k}=\sum_{i=1}^{m}w_{ki}e_{ki} $
– e) 计算弱学习器系数： $ \alpha_{k} = \frac{e_{k}}{1-e_{k}} $
– f) 更新样本集的权重分布： $ w_{k+1,i}=\frac{w_{ki}}{Z_{k}}\alpha_{k}^{1-e_{ki}} $ ,其中 $ Z_{k} $ 是规范化因子： $ Z_{k}=\sum_{i=1}^{m}w_{ki}\alpha_{k}^{1-e_{ki}} $ . - (3) 构建最终强学习器为： $ f(x)=G_{k*}(x) $ .
其中， $ G_ {k∗}(x) $ 是所有 $ ln\frac{1}{\alpha_{k}}, k=1,2,…,K $的中位数值对应序号k∗对应的弱学习器。