树系列（三）adaboost

核心思想

从训练数据中学习一系列的弱分类器，将这些弱分类器线性组合成为一个强分类器，这里讲述的核心是二分类问题，

输入：训练集 $T = (x_{1}, y_{1}), . . ., (x_{N}, y_{N})$ ，其中 $x_{i} \in R^{n}, y_{i} = - 1, + 1$ ,弱学习算法，

输出：最终分类器G(x)
1. 初始化训练数据权值分布
$D_{1} = (w_{11}, . . ., w_{1 N}), w_{1 i} = \frac{1}{N}, i = 1, 2, 3, . . ., N$
1. 对于m=1,2,…,M
  1. 使用具有权值分布(这里的权值分布是建立在之前所有的分类器的计算结果之上的) $D_{m}$ 的训练数据集学习，得到基本分类器，
    $G_{m} (x) : X \to {- 1, 1}$
  2. 计算 $G_{m} (x)$ 在训练数据集上的分类误差率，
  $e_{m} = P (G_{m} (x) \neq y_{i}) = \sum_{i = 1}^{N} w_{m i} I (G_{m} (x) \neq y_{i})$
  1. 计算 $G_{m} (x)$ 的系数
  $α_{m} = \frac{1}{2} l o g \frac{1 - e_{m}}{e_{m}}$
  
  这里的对数是自然对数，且 $α_{m}$ 会随着 $e_{m}$ 的减小而增大，因而分类误差越小的基分类器在最终分类器的作用越大，
  1. 更新整体的权值分布，
    $D_{m + 1} = (w_{m + 1, 1}, . . ., w_{m + 1, N}), i = 1, 2, 3, . . ., N$
    $w_{m + 1, i} = \frac{w_{m i}}{Z_{m}} e x p (- α_{m} y_{i} G_{m} (x))$
    这里 $Z_{m}$ 是正则化因子，
  $Z_{m} = \sum_{m = 1}^{M} e x p (- α_{m} y_{i} G_{m} (x))$
  
  更新整体分布权值可以重写为如下公式，
  
  ${\begin{matrix} \frac{w_{m i}}{Z_{m}} e^{- α_{m}}, G_{m} (x) = y_{i} \\ \frac{w_{m i}}{Z_{m}} e^{α_{m}}, G_{m} (x) \neq y_{i} \end{matrix}$
  
  相对比来说，误分类样本的权值被放大了 $e^{2 α_{m}} = \frac{e_{m}}{1 - e_{m}}$ 倍，这样误分类的样本就会被更多的关注，
2. 构建基分类器的线性组合
  
  得到最终的分类器
  $G (x) = s i g n (f (x)) = s i g n (\sum_{m = 1}^{M} α_{m} G_{m} (x))$
adaboost的核心是不改变训练数据本身，而不断改变自定义的训练数据的权值分布，从而提高训练的正确率，
原理解释

前向分步算法

加法模型

$f (x) = \sum_{m = 1}^{M} β_{m} b (x; γ_{m})$

学习加法模型f(x)转换为损失函数极小化问题：

$m i n_{β_{m}, γ_{m}} \sum_{i = 1}^{N} L (y_{i}, \sum_{m = 1}^{M} β_{m} b (x; γ_{m}))$

前向分步算法一步一步优化，每步只学习一个基函数及其系数，逐渐逼近目标，

$m i n_{β, γ} \sum_{i = 1}^{N} L (y_{i}, β b (x; γ))$

输入：训练集 $T = (x_{1}, y_{1}), . . ., (x_{N}, y_{N})$ ，损失函数 $L (y, f (x))$ ，基函数基 ${b (x; γ)}$

输出：加法模型f(x)
1. 初始化 $f_{0} (x) = 0$ ,
2. 对于m=1,2,…,M
  1. 极小化损失函数
  $(β_{m}, γ_{m}) = a r g m i n_{β, γ} \sum_{i = 1}^{N} L (y_{i}, f_{m - 1} (x) + β b (x_{i}, γ))$
  
  得到更新参数 $β_{m}, γ_{m}$ ,
  1. 更新
  $f_{m} (x) = f_{m - 1} (x) + β_{m} b (x; γ_{m})$
3. 得到加法模型
$f (x) = f_{M} (x) = \sum_{m = 1}^{M} β_{m} b (x; γ_{m})$

adaboost是一种基函数为基本分类器的加法模型，损失函数为指数函数，这个指数函数如下

$L (y, f (x)) = e x p [- y f (x)]$

证明如下，

经过m次训练，得到的分类器为

$f_{m} (x) = α_{1} G_{1} (x) + . . . + α_{m} G_{m} (x)$

我们需要求解的目标如***意，这才是adaboost真正需要解决的问题，得到一个分类器，使得这个分类器和之前所有分类器的结果的加权平均的指数函数最小，而不是只是单纯一个分类器达到最优，

$(α_{m}, G_{m}) = a r g m i n_{α, G} \sum_{i = 1}^{N} e x p [- y_{i} (f_{m - 1} (x) + α G (x))]$

上式可表示为

$(α_{m}, G_{m}) = a r g m i n_{α, G} \sum_{i = 1}^{N} \bar{w_{m i}} e x p [- y_{i} α G (x))]$

其中 $\bar{w_{m i}} = e x p [- y_{i} f_{m - 1} (x)]$ , 这代表了之前所有分类器加权平均后对于 $(x_{i}, y_{i})$ 的权重分布，而 $w_{m i}$ 代表的是 $G_{m} (x)$ 对于 $(x_{i}, y_{i})$ 的权重分布， $w_{m i}$ 是建立在 $\bar{w_{m i}}$ 的基础上的，

现在的目标需要求解 $α_{m}^{*}$ 和 $G_{m}^{*} (x)$ ,
1. 对于任意的 $α > 0$ , 使得上述式子最小由如下式子得到，这个式子能这么改写的依据是 $\bar{w_{m i}}$ 不随 $α$ 变化，
$G_{m}^{*} (x) = a r g m i n_{G} \sum_{i = 1}^{N} \bar{w_{m i}} I (y_{i} \neq G (x_{i}))$

此分类器即为adaboost求解的及分类器，使第m轮训练分类误差最小，
1. 求解 $α_{m}^{*}$ ，
如下公式变形，

$\sum_{i = 1}^{N} \bar{w_{m i}} e x p [- y_{i} α G (x_{i})]$

$= \sum_{y_{i} = G_{m} (x)} \bar{w_{m i}} e^{- α} + \sum_{y_{i} \neq G_{m} (x)} \bar{w_{m i}} e^{α}$

$= (e^{α} - e^{- α}) \sum_{y_{i} = G_{m} (x)} \bar{w_{m i}} I (y_{i} \neq G (x_{i})) + e^{- α} \sum_{i = 1}^{N} \bar{w_{m i}} (1)$

现在说一下一个比较重要的公式，如下

$e_{m} = \frac{\sum_{i = 1}^{N} \bar{w_{m i}} I (y_{i} \neq G (x_{i}))}{\sum_{i = 1}^{N} \bar{w_{m i}}} = \sum_{i = 1}^{N} w_{m i} I (y_{i} \neq G (x_{i})) (2)$

这个公式表示了从m-1次概率分布更新到m次概率分布的重要衔接点，第二个等式代表的是对于 $(x_{i}, y_{i})$ 建立在所有m-1个分类器的加权平均的权重分布的基础上第m轮分类的分类误差概率，第三个等式是第二个等式的代表含义，

经过对公式(1)的求导和公式(2)的转换，可以得到如下式子，

$α_{m}^{*} = \frac{1}{2} l o g \frac{1 - e_{m}}{e_{m}}$

公式推导如下，

最后每一轮的权值更新，

$\bar{w_{m + 1, i}} = e x p [- y_{i} f_{m} (x_{i})] = \bar{w_{m, i}} e x p [- y_{i} α_{m} G_{m} (x_{i})]$

和之前 $w_{m i}$ 的权值更新只差了规范化因子，这个是无伤大雅的，

因而证明了之前的结论：adaboost是一种损失函数为指数函数，基函数为基本分类器的加法模型。
个人理解
算法一开始对于每个样本的权重都是一样的，而后选择基于之前的结果的最优的一个弱分类器，经过分类得出一个结果，这个结果和标签进行对比，把分错的样本的权重加大，把分对的样本的权重变小，而后再基于这个新更新的权重列表选择最优的弱分类器，这时这个弱分类器就对上次分错的数据很敏感，因为一旦上次分错的样本这次又被分错，那么对于整体的错误概率就会瞬间提高很多，因而要想选出最优的分类器，就尽量让上次分错的样本这次划分正确，因而能够保证这次的分类器比上次能够达到更好的结果，经过有限次迭代之后，就会产生若干个弱分类器，每个分类器都有一个权重，这个权重反比于这个分类器的整体错误概率，即分类器精确度越高，其权重就会越大，这样把所有的弱分类器按照加权和放到一起，之后再按照分类阈值划分，得到一个强分类器，因而当测试的时候输入未知样本，送入强分类器之后，就能够得到较为可靠的结果。

而为什么要把所有的分类器都放到一起加权求和，有两点原因，第一点就是这一轮的选择本身就是建立在之前所有分类器的的加权平均的结果，只有这样才能够体现加法模型的意义，第二个原因个人觉得是因为规避过拟合的问题，因为第n轮迭代只是更加关注第n-1轮没有分类正确的样本，而没有过多的关注n-1轮分类正确的样本，因而第n轮迭代中已经分类正确的样本在这一轮更加容易分错，久而久之就会产生过拟合的问题，而加权平均就能够很好地规避这个问题，既关注每一轮分类正确的样本，也关注分类错误的样本，
Adaboost 学习到的其实是每个样本的权重，通过样本的权重来控制下一步的阈值划分，

在实际操作过程中，还会添加一个learning_rate 的参数，之前所有的基学习器训练完成的时候都是直接根据每个基学习器的权重加起来的，如下所示，
$f_{k} (x) = f_{k - 1} (x) + α_{k} G_{k} (x)$

但现在不是这样了，引入了learning_rate, 如下图所示，

$f_{k} (x) = f_{k - 1} (x) + v * α_{k} G_{k} (x)$

这样能够保证完成相同的学习任务，要用更多的基学习器才能够达成相同的目的，但是这样学习的结果会更加精确，实际调参的时候要把基学习器的个数n_estimator 和learning_rate 一起调才能达到更好的效果，

树系列（三）adaboost

minβ,γ∑i=1NL(yi,βb(x;γ))minβ,γ∑i=1NL(yi,βb(x;γ))

f(x)=fM(x)=∑m=1Mβmb(x;γm)f(x)=fM(x)=∑m=1Mβmb(x;γm)

=(eα−e−α)∑yi=Gm(x)wmi¯I(yi≠G(xi))+e−α∑i=1Nwmi¯(1)=(eα−e−α)∑yi=Gm(x)wmi¯I(yi≠G(xi))+e−α∑i=1Nwmi¯(1)

相关推荐

$m i n_{β, γ} \sum_{i = 1}^{N} L (y_{i}, β b (x; γ))$

$f (x) = f_{M} (x) = \sum_{m = 1}^{M} β_{m} b (x; γ_{m})$

$= (e^{α} - e^{- α}) \sum_{y_{i} = G_{m} (x)} \bar{w_{m i}} I (y_{i} \neq G (x_{i})) + e^{- α} \sum_{i = 1}^{N} \bar{w_{m i}} (1)$