大连理工大学选修课——机器学习笔记（8）：Boosting及提升树

Boosting及提升树

Boosting概述

• Bootstrap强调的是抽样方法

不同的数据集彼此独立，可并行操作

• Boosting注重数据集改造

数据集之间存在强依赖关系，只能串行实现

处理的结果都是带来了训练集改变，从而得到不同的学习模型

Boosting基本思想

boosting样本集中，初始权重均等；根据上一个弱模型预测结果修改错分样本的权重。

• 生成具有不同样本权重的新数据集
• 训练新的弱学习模型

循环操作，生成n个不同的数据集

• 新数据集依次递进生成

• 训练n个不同的学习模型

• 根据组合策略生成强学习模型

  

Boosting的基本问题

1. 如何计算预测的错误率
2. 如何设置弱学习模型的权重系数
3. 如何更新训练样本的权重
4. 如何选择集成学习的组合策略

Boosting的常用方法

• AdaBoost 自适应提升
• Gradient Boosting 梯度提升
• Extreme Gradient Boosting 极端梯度提升

常用的弱学习模型

• 决策树
  • GBDT(Gradient Boosting DecisionTree)
  • XGBDT(eXtreme Gradient Boosting DecisionTree)

AdaBoost

• 加法模型：强学习模型是弱学习模型的线性组合
• 损失函数是指数型函数
• 学习算法是正向分步算法
  • 采用“正向激励+递进”机制
  • 也是需要根据损失函数自动调节

AdaBoost的特点

• 不是人为地调节训练样本权重，通过损失函数自适应权重调节
• 弱学习模型也有各自的权重
  • 调节投票权大小
  • 也是需要根据损失函数自动调节

分类误差率

• 对于样本集$X=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$

• 建立K个弱学习模型，第k个模型的训练样本权重

  $$D(k)=(w_{k1},w_{k2},\cdots ,w_{kN})$$

• 权重的初始化

$$w_{1i}=\frac{1}{N};i=1,2,\cdots ,N$$

• 样本的权重对应一种概率分布

  $$\sum _{i=1}^N{w}_{ki}=1$$

• 定义二值分类问题的误差，假定二值$[-1,1]$

  • 第k个弱学习模型的加权误差率

  $$\begin{gathered} e_k=P(G_k(x_i)\ne y_i)=\sum _{i=1}^N{w}_{ki}I(G_k(x_i)\ne y_i) \\ I(G_k(x_i)\ne y_i)=1 \end{gathered}$$

  即：

  $$e_k=P(G_k(x_i)\ne y_i)=\sum _{y_i\ne G_k(x_i)}^N{w}_{ki}$$

AdaBoost的组合策略

学习模型通过正向分布算法获得

每一轮都会生成新的弱模型，第k轮对应的强模型定义为：

$$f_k(x)=\sum _{i=1}^k{\alpha }_i{G}_i(x)$$

由当前所有的弱模型的线性组合而成，最终的强学习模型：

$$f(x)=sign(\sum _{k=1}^K{\alpha }_k{G}_k(x))$$

弱学习模型的权重

第k轮：

$$f_k(x)=\sum _{i=1}^k{\alpha }_i{G}_i(x)=f_{k-1}(x)+{\alpha }_k{G}_k(x)$$

求解：

$$({\alpha }_k,G_k(x))=argmin\sum _{i=1}^{N}exp[-y_i(f_{k-1}(x_i)+\alpha G(x_i))]$$

令${\overline{w}}_{ki}=exp[-y_i[f_{k-1}(x_i)]$

且$G_k^{\ast }=argmin{\sum }_{i=1}^N{\overline{w}}_{ki}I(y_i\ne G(x_i))$

则：

$$\begin{gathered} \sum _{i=1}^N{\overline{w}}_{ki}{e}^{[-y_i\alpha }G(x_i)]=\sum _{y_i=G_k(x_i)}{\overline{w}}_{ki}{e}^{(-\alpha )}+\sum _{y_i\ne G_i(x_i)}{\overline{w}}_{ki}{e}^{(\alpha )} \\ =(e^{(\alpha )}-e^{-\alpha })\sum _{i=1}^N{\overline{w}}_{ki}I(y_i\ne G(x_i))+e^{-\alpha }\sum _{i=1}^N{\overline{w}}_{ki} \\ ({\alpha }_k)=argmin((e^{\alpha }-e^{-\alpha })\sum _{i=1}^N{\overline{w}}_{ki}I(y_i\ne G(x_i))+e^{-\alpha }\sum _{i=1}^N{\overline{w}}_{ki}) \end{gathered}$$

对$\alpha$求导，令导数为0，得：${\alpha }_k^{\ast }=\frac{1}{2}ln\frac{1-e_k}{e_k}$

其中，$e_k={\sum }_{i=1}^N{w}_{ki}I(y_i\ne G(x_i))$

强学习模型权重

$$f_k(x)=\sum _{i=1}^k{\alpha }_i{G}_i(x)=f_{k-1}(x)+{\alpha }_k{G}_k(x)$$

$${\overline{w}}_{k+1}=\frac{{\overline{w}}_{ki}}{Z_k}{e}^{y_i{\alpha }_k{G}_k(x)}$$

AdaBoost的回归分析

• 计算错误率
  • 第k个弱模型的最大误差 $E_k=max|y_i-G_k(x_i)|$
  • 每个样本的误差 $e_{ki}=\frac{|y_i-G_k(x_i)|}{E_k}$
  • 第k个弱模型的错误率 $e_k={\sum }_{i=1}^N{w}_{ki}{e}_{ki}$
• 权重的更新
  • 第k个弱模型的权重 ${\alpha }_k=\frac{e_k}{1-e_k}$
  • 每个样本的权重更新 $w_{k+1}=\frac{w_{ki}}{Z_k}{\alpha }_k^{1-e{k}_i}$,$（Z_k={\sum }_{i=1}^N{w}_{ki}{\alpha }_k^{1-e_{ki}})$
• 组合策略
  • 对加权的弱学习器，取权重中位数对应的弱学习器，作为强学习器的方法。
  • 最终的强回归器为 $f(x)=G_k^{\ast }(x)$
  • 其中$G_k^{\ast }(x)$是K个弱模型权重中位数对应的模型

AdaBoost的正则化

• 为了防止过拟合，可以引入正则化

对于强学习模型而言：

$$f_k(x)=f_{k-1}(x)+{\alpha }_k{G}_k(x)$$

改进模型：

$$f_k(x)=f_{k-1}(x)+v{\alpha }_k{G}_k(x)$$

其中，v为正则化参数，在此也称为步长(或者学习率），调节弱模型的生成。

AdaBoost的分类算法描述（二值）

AdaBoost的分类算法描述（多值）

AdaBoost回归算法描述

以AdaBoost R2为例

Gradient Boosting Tree

Boosting的本质：采用加法模型与正向激励算法

对弱学习模型的要求：学习能力差的模型，输出结果低方差，高偏差

弱模型采用决策树：

1. 提升树（Boosting Tree）
2. 采用CART（二叉树）
3. 深度1-5即可，不宜太大

梯度提升树

初始化

$$f_0(x)=argmin\sum _{i=1}^{N}L(y_i,c)$$

第m步残差

$$r_{mi}=-(\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}{)}_{f(x)=f_{x-1}(x)}$$

利用$(x_i,r_{mi})(i=1,2,\cdots ,N)$，可以拟合一棵CART回归树

对于叶子结点

$$c_{mj}=argmin\sum L(y_i,f_{m-1}(x_i)+c)$$

第m步的强模型

$$f_m(x)=f_{m-1}(x)+\sum c_{mj}I(x\in R_{mj})$$

最终的强模型

$$\hat{f}(x)=f_M(x)=f_0(x)+\sum _{m=1}^M\sum _{j=1}^J{c}_{mi}I(x\in R_{mj})$$

对于分类树，与回归树的损失函数不同

如果采用指数函数，提升树退化为AdaBoost

也可采用逻辑回归函数

• 对数似然损失函数
• 二值分类和多值分类有不同的表示形式

对于二值分类

• 损失函数

  L(y,f(x))=log(1+e−yf(x)),y∈{−1,1} L(y,f(x))=log(1+e^{-yf(x)}),\quad y\in \{-1,1\} L(y,f(x))=log(1+e−yf(x)),y∈{−1,1}

• 残差计算

  $$r_{mj}=-(\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)})=\frac{y_i}{1+e^{y_i(x_i)}}$$

• 对于为你和残差构建的决策树

  $$c_{mj}=argmin\sum log(1+e^{-y_i(f_{m-1}(x_i)+c)})$$

  最优值的近似计算

  $$c_{mj}\approx \frac{\sum r_{mj}}{\sum |r_{mj}|(1-|r_{mj}|)}$$

对于多值分类

• 对应K个分类的损失函数

  $$L（y,f(x))=\sum _{k=1}^K{y}_{k}log{p}_k(x)$$

  如果输出样本类别为k，则$y_k=1$

• 第k类的概率的表达式为

$$p_k(x)=e^{f_k(x)}/\sum _{l=1}^K{e}^{f_l(x)}$$

• 计算残差

  $$r_{mil}=-(\frac{\partial L(y_i,f(x_i)}{\partial f(x_i)}{)}_{f_k(x)=f_{l,m-1}(x)}=y_{il}-p_{l,m-1}(x_i)$$

  上式对应样本i对应类别l的真实概率和第m-1轮预测概率的差值

• 对于决策树优化

  

  最优值的近似计算

  

梯度提升树的其它常用损失函数

指数损失函数

$$L(y,f(x))=e^{-yf(x)}$$

使用该函数，提升树退化为AdaBoost

绝对误差

$$L(y,f(x))=|y-f(x)|$$

对应的负梯度误差

$$sign(y_i-f(x_i))$$

Huber损失函数

均方差和绝对差的折中产物，用于处理异常点

对应的负梯度误差：

Qutantile（分位数）损失函数

也能有效处理异常点

对应的负梯度误差

梯度提升树的正则化

方法一：

$$f_k(x)=f_{k-1}(x)+v{h}_k(x)$$

与AdaBoost算法手段相同

方法二:

采用采样比，取值为$(0,1]$

用部分样本去拟合决策树，克服过拟合

此时的模型称为随机梯度提升树

可以实现部分并行，从而提升执行效率

梯度提升树总结

• 优点
  • 可灵活处理各类数据
  • 在相对少的调参情况下，预测准确率也可以比较高
  • 对异常值鲁棒性强