Boosted Trees简介【翻译+自己的理解】

雨点打透心脏的1/2处 2022-03-21 15:47 147阅读 0赞

## 原文 ##

> [https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf][https_homes.cs.washington.edu_tqchen_pdf_BoostedTree.pdf]  
> 华盛顿大学的 Introduction to Boosted Trees. Tianqi Chen.

本文结合该论文和网上其他资料，在自己理解之后，书写下来~

### 文章目录 ###

*   *  原文
     *  监督学习
     *  Regression Tree and Ensemble
     *   *  Regression Tree 回归树（GART）
         *  Regression Trees Ensemble 回归树集成
     *  Gradient boosting 梯度提升
     *   *  模型复杂度
     *  结构得分

## 监督学习 ##

*  `Objective function`(目标函数)：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]
 *  训练损失：一般有两种
    
     *  平方损失函数： ( y i − y ^ i ) 2 (y\_i - \\hat y\_i)^2 (yi−y^i)2
     *  逻辑损失函数： y i ln ⁡ ( 1 + e − y ^ i ) + ( 1 − y i ) ln ⁡ ( 1 + e y ^ i ) y\_i\\ln \{(1+e^\{-\\hat y\_i\}) \}+ (1-y\_i) \\ln\{(1+e^\{\\hat y\_i\})\} yiln(1\+e−y^i)\+(1−yi)ln(1\+ey^i)
 *  正则化损失：
    
     *  L1正则化（Lasso）：  λ ∣ ∣ w ∣ ∣ 1 \\lambda||w||\_1 λ∣∣w∣∣1
     *  L2正则化： λ ∣ ∣ w ∣ ∣ 2 \\lambda ||w||^2 λ∣∣w∣∣2

## Regression Tree and Ensemble ##

### Regression Tree 回归树（GART） ###

*  决策的原则类似于决策树
 *  但是叶子节点上包含有分数  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 1]

### Regression Trees Ensemble 回归树集成 ###

*  将多个回归树的结果求和，就是回归树集成  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 2]
 *  树集合的方法有很多种  
    例如：`GBM(gradient boosting machine 梯度提升机器)`、`random forest 随机森林`…
 *  输入放缩固定，所以不需要在特征正则化上太小心。

假设我们使用K个树，那么有  
 y ^ i = ∑ k K f i ( x i ) f i ∈ F \\hat y\_i = \\sum\_\{k\}^\{K\}\{f\_i(xi)\} \\\\ f\_i \\in F y^i=k∑Kfi(xi)fi∈F

*  其中F是所有树的集合（**其实是上面的图片所示的数学表达而已**）
 *  **回归树不只能做回归，还可以做排序，分类…** 主要取决于对应的目标函数。

## Gradient boosting 梯度提升 ##

*  这里不能直接使用SGD，因为寻找的f是树，而不是向量。所以使用 Additive Training (Boosting)
 *  每次在原来的基础上，加上一个新的函数，构成第t轮下的数值。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 3]
 *  那么推导到对应的目标函数，也就是找到对应的树，让这个整个数值最小。（训练损失也要小，模型损失也要小）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 4]

*  使用泰勒展开，g是一阶导，h是二阶导。偏移值是 f t ( x ) f\_t(x) ft(x)  
    下图最后一行的例子，只是说明了在损失函数是平方函数时候的情况。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 5]

### 模型复杂度 ###

之前曾考虑过，除了训练的复杂度之外，还需要考虑模型的损失。

*  下面是其中一种的定义：（再引入了两个超参数）
    
     *  T：叶子数量
     *  w: 回归树对应叶子节点的得分  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 6]

## 结构得分 ##

*  I：被选的树的集合
 *  然后给出下面的关于G和H的定义
 *  如果树的结构已经确定，那么对应的最优的权重也可以算出来。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 7]
 *  下面会用到一种思维，假设所有的树一开始都是一棵树。之后，再根据对应的条件节点来做分割。
 *  L表示的左树，R表示的是右树。  
    ![在这里插入图片描述][20190203110847124.png]

[https_homes.cs.washington.edu_tqchen_pdf_BoostedTree.pdf]: https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]: /images/20220321/dca798df0d314f2eb2fcdb91d5f9dcc1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 1]: /images/20220321/f1db232b83914c1cbcc6240e4116e008.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 2]: /images/20220321/ca3d18c2d28441e69d5f2f15e414b406.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 3]: /images/20220321/60cad17c97064ac985eb8a73278866df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 4]: /images/20220321/f9d8103abe5c4f7d87eb779764e42321.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 5]: /images/20220321/3824db45b4824fd9bc91dc8616e5945f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 6]: /images/20220321/0812f1f17fea4df499bf950f29b536f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 7]: /images/20220321/d4f64cce01b94f7abf8869a4f3c4c18c.png
[20190203110847124.png]: /images/20220321/f499a7bf9a2d4137afe7e2cbb56412b7.png