Skip to content

Latest commit

 

History

History
91 lines (48 loc) · 4.35 KB

bagging_boosting.md

File metadata and controls

91 lines (48 loc) · 4.35 KB
Raw

Adaboost:

算法描述：

  • 输入： 训练集$T={(x_1, y_1), ..., (x_N, y_N)}, x_i \in R^n, y_i \in {-1, +1}$, 基学习器$G_1(x)$
  • 输出：最终学习器$G(x)$

  1. 初始化训练数据的权值分布

    $D_1= (w_{1,1}, ... , w_{1,N}), w_{1,i} = \frac{1}{N}, i=1,2,...,N$

  2. 对 $m=1,2,...,M$

    i. 使用权值分布为$D_m$的训练集，得到基分类器

    ii. 计算$G_m(x)$在训练集上的分类误差率

    ​ $e_m = P(G_m(x_i)\ne y_i) = \sum^{N}{i=1}w{m,i}\cdot I(G_m(x_i)\ne y_i)$

    iii. 计算$G_m(x)$的系数(系数和分类误差率)

    ​ $\alpha_{m} = \frac{1}{2}ln\frac{1-e_m}{e_m}$

    iv. 更新训练数据的权值分布$D_{m+1}$(误差率越大，权值越大)

    $w_{m+1,i} = \frac{w_{m,i} \cdot exp(-\alpha_{m}\cdot y_iG_m(x_i))}{Z_m}$

    $Z_m = \sum^N_{i=1} w_{m,i} \cdot e^{-\alpha_m \cdot y_iG_m(x_i)}$（$Z_m$使得满足概率分布）

  3. 最终分类器：$G(x) = sign(\sum_{m=1}^M\alpha_m G_m(x))$

GBDT:

  • 利用损失函数得负梯度作为提升树算法中得残差的近似值。（对于一般损失函数而言，优化起来不容易，所以用负梯度作为提升树算法中残差的近似值）。对于MSE loss，负梯度就是残差。

  • GBDT用于分类时，使用一系列CART回归树来拟合对数几率。

  • BDT是拟合残差，GBDT是用梯度作为残差的近似

  • 算法流程

    1. 初始化弱学习器

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

      当损失为mse loss时，$f_0(x)$为均值

    2. 对m=1,2,...,M：

      （a) 对每个样本，计算负梯度，即残差

      $r_{im} = -[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}]{f(x)=f{m-1}(x)}$

      (b) 将上步得到的残差作为样本的真实值，将样本数据$(x_i, r_{im})$作为下棵树的训练数据，得到一颗新的回归树。叶子节点区域为$R_{jm}$.

      如何得到一颗新的回归树？

      • 树的深度 例如树的深度为3，需要找两个属性作为切分点

      • 每次计算以那个属性(年龄>7 or <7)切分，分别计算分裂后两组数据的平方损失（对于MSE而言，其实就是方差）0.175，使得两组损失和最小。

      • 直到深度达到预定要求

      • 给每个叶子节点赋值，MSE就为该叶子节点上包含样本的残差均值。

        (c) 对于每个叶子区域，计算最佳拟合值。MSE就是节点区域的均值。

      $\gamma_{im}=argmin_{\gamma}\sum_{x_i\in R_{jm}}L(y_i, f_{m-1}(x_i) + \gamma)$

      (d) 更新强学习器

      $f_{m}x = f_{m-1}(x) + \sum_{j=1}^J\gamma_{jm}I(x\in R_{jm}) $

      (e) 得到最终学习器

      $f(x) = f_M x = f_0(x) + \sum_{m=1}^{M}\sum_{j=1}^{J}\gamma_{jm}I(x\in R_{jm})$

XGBOOST

  • 传统的GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑回归（分类问题）或线性回归（回归问题）
  • 传统的GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。
  • xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数，每个叶子节点上输出的score的L2摸得平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型得variance，使学习出来的模型更加简单，防止过拟合。

随机森林

　　1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。

　　2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。

　　3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。

　　4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。