GBDT

技术文章 1年前 (2020) 完美者
723 0

标签:梯度   random   维数   lin   oba   wiki   ring   模型训练   支持   

GBDT

概述

本文主要总结集成学习(ensemble learning)中一大类boosting模型--梯度提升。主要包括GBDT, XGBoost, LightBoost, CatBoost 这4种模型的原理,以及关于这4个模型的简单示例。

GB(Gradient Boosting, 梯度提升)是boosting的一种,和AdaBoost不同的是,AdaBoost是在每次迭代种调整数据元组权重,相当于更专注于难分对的数据元组。而GB是让新的预测器针对前一个预测器的残差进行拟合。

Leo Breiman给出的GB的思想是:GB是针对合适的成本函数的优化算法。这样通过梯度下降算法来优化分类器。可以处理多样的问题,包括回归,分类和排名(ranking).

XGBoost作为GBDT优化的工程实现,目前在实际种应用广泛,效果也是很好的。

GB基本原理

基本描述

p003-01

数据集共N个样本,\(\{x_i, y_i\}_1^{N}\)

分类器为\(F(x)\); \(F^*(x)\) 是在所有样本联合分布条件下最小化损失函数\(L(y, F(x))\)期望的最优分类器。

\[F^*=\arg \min_{F} E_{y,x}L(y,F(x))=\arg \min_{F} E_{x}[E_{y}(L(y,F(x)))|x] \]

损失函数的选择很多,可以是均方误差、绝对误差、二分类的log损失函数。

梯度提升包括M个分类器。假设得到了第1个模型\(F_1\), 梯度提升就是增加一个新的估计量\(h\)。即基于新的估计量\(h\)来训练模型\(F_2\)

\[F_1(x) \sim F_0(x)+h_0(x)=y \]

\[F_2(x) \sim F_1(x)+h_1(x) = y \]

等价于

\[h_1(x) = y - F_1(x) \]

y为真实值,\(\hat{y} = F_m(x)\)为第m个分类器的预测值,\(h_m(x)\)为拟合残差的第m个分类器的估计量。

依次类推,通过M个分类器,不断优化误差,最终得到模型。可以观察到,残差\(h_1(x)= y - F_1(x)\)是均方损失函数\(\frac{1}{2}(y-F(x))^2\)关于\(F(x)\)的负梯度。因此梯度提升其实是一种梯度下降算法,可以使用其它损失函数,得到不同梯度。

算法描述

p003-02

算法详细推导见参考[3]。

通过加性策略来组合M个分类器,得到最终的模型:

\[F^*(x)=\sum_{m=0}^{M}\gamma_m h_m(x) \]

其中,\(F_0\)是初始化猜的,可以为0. 其它通过梯度下降得到,

\[F_0(x)=\arg \min_{\gamma} \sum_{i=1}^{n}L(y_i,\gamma) \]

循环训练其它M个分类器。

计算伪残差,或者叫计算负梯度, 对于n个数据点:

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

用数据\(\{ x_i, r_{im} \}_{i=1}^n\)训练第m个分类器,得到\(h_{m}(x)\).

通过线性搜索,得到分类器的乘数$ \gamma $:

\[\gamma_m = \arg \min_{\gamma} \sum_{i=1}^{n}L(y_i,F_{m-1}(x_i)+\gamma h_m(x_i)) \]

更新模型:

\[F_m(x)= F_{m-1}(x) + \gamma_m h_m(x) \]

得到最终的模型$ F^*(x) $。

总结

  • 模型是加性(additive)策略组合的模型,前向递进计算得到。
  • 每个分类器都有一个权重。
  • 每次的分类器,都是基于负梯度来训练。
  • 因此,任何有一阶导的损失函数都可以应用。
  • Absolute loss and Huber loss are more robust to outliers than square loss

GBDT

GBDT(Gradient Boosted Decision Trees, 梯度提升决策树)是一种boosting方法,使用的基分类器为决策树,一般为CART。有的文献也称为GBM( gradient boosting machine )。

GBDT是在梯度提升的基础上得到的。

决策树可以看作对空间的划分,每个叶子节点占有一个空间区域。

\[R_j, j = 1, 2, ..., J \]

\(J\) 表示树的终端节点(叶子节点)。常量 $ \gamma_j$ 是空间区域系数。

\[x \in R_j \Rightarrow F(x)=\gamma_j \]

一个树模型可以表示为:

\[T(x;\Theta) = \sum_{j=1}^J \gamma_j I(x\in R_j) \]

\(I\) 类似于\(\delta\)函数。$ \Theta = {R_j, \gamma_j}_1^J$ 是组合参数。\(J\) 是超参数。

p003-03

这样,其它和梯度提升基本相同。

而且,在2-d中可以加入超参数,收缩率(Shrinkage) \(v\)

\[f_m(x) = f_{m-1}(x) + v \sum_{j=1}^{J_m} \gamma_{jm}I(x\in R_{jm}) \]

总结

  • 将决策树作为基分类器
  • 可以处理分类、回归问题
  • 使用损失函数的一阶导数
  • 模型是顺序训练,并行性不好。

XGBoost

基本描述

XGBoost 是GBDT算法的工程实现。

基本原理是,首先给出目标函数,是损失函数\(L\) 和正则项\(\Omega\)的和:

\[obj(\theta) = L(\theta) + \Omega(\theta) \]

对于GBDT:

\[obj(\theta) = \sum_i^N l(y_i, \hat{y}_i) + \sum_{m=1}^M\Omega(f_m) \]

其中,数据集为\(\{x_i, y_i\}_1^{N}\),共N个样本; 分类器个数超参数为M;\(f_m\) 是函数空间\(F\) 的一个,\(F\) 一般为CART决策树。\(\hat{y}_i\) 是M个分类器加性策略得到的:

\[\hat{y}_i = \sum_{m=1}^M f_m(x_i) \]

MSE可以直接得到解析形式,包括一次项(残差)和二次项。其它形式的损失函数不容易得到,因此这里进行泰勒展开到二阶,参数空间为\(f_t(x_i)\), 展开点为\(\hat{y}_i^{t-1}\)

\[l(y_i, \hat{y}_i^{(t)}) = l(y_i, \hat{y}_i^{(t-1)}) + \frac{\partial l(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} f_t(x_i) + \frac{1}{2}\frac{\partial^2 l(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} f_t^2(x_i) \]

移除常量,在t(m)步的目标函数为,令一次项系数为\(g_i\), 二次项系数为\(h_i\):

\[obj^{(t)} = \sum_{i=1}^N [g_if_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)] + \Omega(f_t) \]

由于目标函数只依赖\(g_i\), \(h_i\), 因此XGBoost支持自定义损失函数。

对于正则项,包括叶子个数和叶子上的值。

\[\Omega(f) = \gamma J + \frac{1}{2}\lambda \sum_{j=1}^J w_j^2 \]

其中\(\gamma\)\(\lambda\)是系数,超参数。\(J\) 是叶子节点个数。\(w\)是树模型叶子节点上的值。

\[obj^{(t)} = \sum_{j=1}^J [G_j w_j + \frac{1}{2}(H_j+\lambda)w_j^2] + \gamma J \]

其中,定义

\[G_j = \sum_{i\in I_j}g_i \]

\[H_j = \sum_{i\in I_j}h_i \]

\(I_j\)是第j个叶子节点上分配的数据点的索引集合。在同一个叶子上的数据点分数相同。

\(w_j\) 之间,就是叶子之间是独立的。二次项\(G_j w_j + \frac{1}{2}(H_j+\lambda)w_j^2\) ,对于给定的结构\(q(x)\), 即\(f_{t-1}\) 的树结构是确定的,在对称轴取极值:

\[w_j^* = -\frac{b}{2a} = -\frac{G_j}{H_j + \lambda} \]

\[obj^* = -\frac{1}{2} \sum_{j=1}^J \frac{G_j^2}{H_j+\lambda} + \gamma J \]

测量一个树的好坏,有如下公式。就是尝试某个特征,将该叶子进行分裂为两个叶子,看下得分Gain:

\[Gain = \frac{1}{2}[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}] - \gamma \]

修剪技术,增益如果小于$\gamma $ 则不添加该分支。

另外加性策略的树也有其局限性。

最后,同样通过贪婪策略进行学习。

总结

  • 应用广泛:回归、分类、ranking
  • 加入了关于叶子个数和叶子值的正则项,防过拟合,增加鲁棒性
  • 相对于GBDT, XGBoost有损失函数的二阶信息
  • XGBoost可以使用不同的损失函数,只要满足二次可导
  • ...

LightGBM

LightGBM也是基于树的梯度提升。最大特点是分布式和高效。

在这两点上做了很多优化,详见论文LightGBM: A Highly Efficient Gradient Boosting Decision Tree。

  • Gradient-based One-Side Sampling (GOSS)
  • Exclusive Feature Bundling (EFB)

总结

  • 优势是处理高维数据、大量数据。

CatBoost

同样,CatBoost也是GBDT一个工程实现。官网catboost.ai。

CatBoost是Yandex公司开发的。广泛应用在排名任务、预测和推荐任务中。

catboost主要有两个方面的改进。一是对于类别型特征,使用ordered TS ,就是排序的类别统计(Target statistics)。类别统计有多种其它改进,包括Greedy TS, Holdout TS, Leave-one-out TS, Ordered TS.

二是Ordered boosting,使用的基分类器是oblivious决策树,也叫做decision tables.

总结

  • 实用性:可以处理类别型特征
  • 可扩展:允许自定义损失函数
  • 易于使用:有python 的类似scikit的接口
  • 稳健:减少对于超参数的调参。

应用示例

下面是随机的二分类数据。3个模型都是用的scikit-learn api。

import numpy as np

# 训练数据集
train_data = np.random.randint(
    0, 100,
    size=(100, 10)
)
train_labels = np.random.randint(
    0, 2,
    size=(100)
)
# 测试数据集
test_data = np.random.randint(
    0, 100,
    size=(10, 10)
)

XGBoost

python接口文档,参考文献6.

下面是一个简单的例子。

import xgboost as xgb

model = xgb.XGBClassifier()

# 模型训练
model.fit(train_data, train_labels)
# 模型评估
# 模型预测
preds_class = model.predict(test_data)

LightGBM

python接口文档,参考文献7.

下面是一个简单的例子。

import lightgbm as lgb

model = lgb.LGBMClassifier()

# 模型训练
model.fit(train_data, train_labels)
# 模型评估
# 模型预测
preds_class = model.predict(test_data)

CarBoost

python接口文档catboost

下面是一个简单的分类例子。

from catboost import CatBoostClassifier, Pool

model = CatBoostClassifier(
	iterations=2,
    depth=2,
    learning_rate=1,
    loss_function=‘Logloss‘,
    verbose=True
)
# 模型训练
model.fit(train_data, train_labels)
# 模型评估
# 模型预测
preds_class = model.predict(test_data)
preds_proba = model.predict_proba(test_data)

参考

  1. scikit-learn 0.23.2, Gradient Tree Boosting
  2. wikipedia, Gradient boosting
  3. Friedman, J. H. Greedy Function Approximation: A Gradient Boosting Machine (PDF). February 1999.
  4. Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
  5. Vishal Morde, 2019. XGBoost Algorithm: Long May She Reign!
  6. Introduction to Boosted Trees
  7. lightgbm
  8. catboost.ai
  9. CatBoost: unbiased boosting with categorical features
  10. 机器学习算法之Catboost

GBDT

标签:梯度   random   维数   lin   oba   wiki   ring   模型训练   支持   

原文地址:https://www.cnblogs.com/mszhai/p/13578090.html

版权声明:完美者 发表于 2020-09-08 20:50:31。
转载请注明:GBDT | 完美导航

暂无评论

暂无评论...