二分类的 GBDT 思想

机器学习 ALLEN ⋅ 于 2019-09-26 08:00:58 ⋅ 4 阅读

前言

GBDT(Gradient Boosting Decision Trees)梯度提升决策树,该决策树涉及了多棵树的训练。

基本思想

给定一训练集 $ X=\left \{ x_{i} \right \}_{i=1}^{N} $,其中$x_{i}\epsilon R^{D}$,每个样本的结果为 0 或 1,即$Y=\left \{ y_{i} \right \}_{i=1}^{N}$,$y_{i}\epsilon {0,1}$。我们的目标是:
选择某分类函数 $F(x)$ 使得某个指定的损失函数 $\zeta (y_{i},F(x_{i}))$ 的累计值最小:

$$F^{*}=\overset{argmin}{F} \sum_{i=1}^{N} \zeta (y_{i},F(x_{i})) (1)$$

式(1)的意义是:$F(x_{i})$ 是训练分类所得的结果,而 $y_{i}$ 是 $x_{i}$的已知分类,而损失函数代表了它们之间的某种差异值,和式就把每个样本的损失值(误差值)进行累加,所以最终所得的就是所有样本分类结果的误差值累计值,代表了训练样本集的训练结果准确度。

梯度提升(Gradient Boosting)使用累加形式来考虑函数估计$F$,

$$F(x) = \sum_{m=1}^{T} f_m(x) (2)$$

其中 $T$ 是迭代次数。${f_m(x)}$ 设计成渐进的方式(incremental fashion),第 $m$ 级(stage),新增加的函数 $f_m$ 是在 $\left \{ f_i \right \}_{j=1}^{m-1}$ 保持固定的前提下,使累加损失最小。

$f_m$ 的每个函数是属于参数化的 'base-learners' 集合;令 $\theta $ 是 base-learner 的参数向量。GBDT 使用决策树作为 base-learner(注:所以叫梯度提升决策树,而且一个函数就代表一个决策树)。所以此时,该参数向量 $\theta $ 由树结构的参数组成,比如每个节点分裂的特性,节点分裂的阈值(信息增益率等等),等等。

在 第 $m$ 级(stage),我们构造近似累加损失函数:

$$\zeta (y_i,F_{m-1}(x_i)+f_m(x_i))\approx \zeta (y_i,F_{m-1}(x_i))+g_if_m(x_i)+\frac{1}{2}f_m(x_i)^{2}, (3)$$

式(3)使用泰勒展开式

其中,$F_{m-1}(x_i) = \sum_{j=1}^{m-1} f_j(x_i)$,并且

$$g_i=\frac{\partial \zeta (yi,F(x_i))}{\partial F(x_i)}|_{F(x_i)=F_{m-1}(x_i)}$$

我们的目标是选择 $f_m$ 使得式(3)的右边达到最小,该优化可转成如下优化问题:

$$\underset{f_m}{argmin} \sum_{i=1}^{N} \frac{1}{2}(f_m(x_i)-g_i)^2 (4)$$

为什么能等价为式(4)优化问题,还不太清楚

因为只对方向进行拟合,通常会在 $f_m$ 添加到 $F_{m-1}$ 之前对 $f_m$ 应用合适的步长(shrinkage parameters-收缩参数)。

梯度提升方法的优势

梯度提升的优势在于对于不同的损失函数(loss function)只有梯度表达式会变,而剩余的优化过程,尤其是决策树的归纳步骤(induction step)对于不同的损失函数(loss function)保持不变。

参考文献

  1. Gradient Boosted Decision Trees for High Dimensional Sparse Output
  2. A Discussion on GBDT: Gradient Boosting Decision Tree

追求梦想,做最好的自己

点赞
回复数量: 0
    暂无评论~~
    • 请注意单词拼写,以及中英文排版,参考此页
    • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
    • 支持表情,使用方法请见 Emoji 自动补全来咯,可用的 Emoji 请见 :metal: :point_right: Emoji 列表 :star: :sparkles:
    • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif
    • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
      请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!
    Ctrl+Enter