1 基础知识点

1.1 Ensemble Learning

集成学习 (Ensemble Learning) 是机器学习 (Machine Learning) 里面核心的概念。它的主要思想归纳起来就是：通过训练多个弱学习器来达到一个强学习器的效果，组合后的表现比任何一个弱学习器的效果都好。在机器学习里error可以大概分两类:一类是偏差错误 (bias error)：指的是预测值与真实值的差异，另外一类是方差错误 (variance error)：指的是预测值作为随机变量的离散程度，而集成学习正好可以降低这些问题。通过组合多个分类器的结果可以降低模型预测的偏差，特别是对于一些不稳定的学习器，所以集成学习出来的学习器有更高的稳定性。而在集成学习中，常见的方法是Baging和Boosting，接下来我们先对这两个方法进行简单描述。

1.2 Bagging and Boosting

使用Bagging或者Boosting技术，我们必须选择一个base学习器。例如，我们可以选择分类tree，那么Bagging和Boosting会组合成一系列树学习器变成一个集成的学习器，接下来，Bagging和Boosting怎么训练得到N个学习器呢？

• 第一的：
  训练数据选择
  每次从原始训练数据集中生成N份新的训练数据集，然后分别训练这N个学习器。在生成每份新的训练数据集的时候，Bagging是随机选择样本，也就是说每个样本出现在新的训练集的概率是一样的，而Boosting会根据样本的权重去选择，所以有些样本会在新的训练集里更高概率被选中。
  
• 第二：
  培训过程
  其中Bagging和Boosting的最主要不同点在于训练过程，
  其中Bagging在训练阶段是并行的，每个训练器都是独立的，而Boosting是基于序列方式建立每个训练器，新的训练器建立依赖于上一个训练器，所以不是独立的
  ，对比图如下：
  
  

在Boosting算法中，每个分类器的训练数据选择，依赖于上个分类器的预测结果，所以在每个训练步骤中，样本的权重是会重新调整的，其中预测错误的数据会增大权重，在概率上会更有可能被选中进入下个分类器进行训练，重点关注这些hard sample的识别。

• 第三：
  预测过程
  训练完N个学习器后，预测结果上面，Bagging和Boosting存在差异，Bagging策略，最终的结果是N个学习器结果的平均值，而Boosting的预测结果是加权之和，用公式表示如下：
  
  
  其中，权重将根据每个分类器预测的性能进行分配，
  学习者越好，权重越高
  。但并不是说Boosting一定比Bagging好，需要根据具体的数据集，学习器等多个因素考虑，若
  单个学习器表现效果很差，那么Bagging就很难得到一个强大的学习器，但是Boosting优化策略正好可以将多个学习器的效果加强。相反，若每个学习器都过拟合了，那么Bagging是最好的选择，而Boosting对于避免过拟合没有什么帮助
  .
  

1.3 Adaptive Boosting

Adaptive Boosting (AdaBoost) 是一种Boosting方法，Boosting核心思想就是从上一个模型错误中进行学习。而AdaBoost学习方法主要是通过对分错的样本加大权重，让下一个模型更关注分错的样本识别效果。训练的基本步骤如下：

• 训练树模型
  
• 计算这个树模型的错误分类的错误率
  
• 根据错误率计算这颗决策树的wieght:
  learning_rate * log((1-e) /e)，所以错误率e越大，weight权重越小
  
• 更新每个样本的权重：样本除以模型的权重保持不变；分类错误的样本，新的权重为：
  old_weight * np.exp(weight of this tree)，更新后，样本的权重变大
  ，下一步将加强对此类误分类样本的识别
  
• 重复以上步骤，直到训练好的树达到最大值
  
• 做出最终预测：通过加权投票机制预测每个候选集样本
  

1.3 Gradient Boosting

梯度提升 (Gradient Boosting) 也是一种Boosting方法，在上面我们提到，boosting模型的核心点是从先前的错误中进行学习，而Gradient Boosting每次迭代通过直接拟合上一步的残差 (目标损失函数对输出值的偏导数) ，使得当前t步的预测结果等于目标损失函数对上一步t-1预测值的负梯度方向，从而可以通过每次迭代 (）不断降低目标损失loss，算法流程如下：

,

2 GBDT算法

2.1 原理

GBDT(Gradient Boosting Decision Tree) 是梯度提升树，接下来我们详细推导算法的细节过程。

1）GBDT预测结果值表达
假设我们有K个树，第k颗树的预测值我们用函数表示，则对于一个样本，最终预测的结果值为：

2）定义目标损失函数
损失函数用来度量模型预测的值与真实标签值之间的差异，同时一般会增加正则化项来惩罚模型的权重参数，避免模型过于复杂，但是基于树模型算法，由于没有权重参数需要优化，因此需要其它的方式来惩罚模型的复杂性。一般对于树模型，通常正则化项会从树的深度，树的叶子节点数或者叶子节点权重值的L2范数等作为因子。通常，如果一颗树的叶子节点越多，树越深越容易过拟合，或者叶子节点权重分值越高，这些都容易导致过拟合。综合这些问题，那么对于树模型，我们可以定义的目标损失函数如下：

其中，衡量模型预测与真实标签的差异，是正则化项，衡量模型的复杂度，防止模型过拟合。我们的目标是最小化上述目标损失函数。

3）目标损失函数变形
有了目标函数，那么模型怎么学习？由于我们要训练的是基于树结构的函数，而不是数值型向量，不能用梯度下降方法求解。所以需要另外一种叫additive training (boosting) 方法来找到最优解。
假设初始值为0，对于每增加一棵树，预测的结果值迭代形式如下：

…

从上述公式可以看出，在t步，最终的预测结果是累积前面t-1步的所有结果与当前的树的结果之和（这里暂时先不考虑学习率因子控制每棵树的权值分值的缩放）。我们对目标函数进行展开如下：




假设我们的目标损失函数是均方误差，变换如下：

由于函数与没有任何联系，上述目标函数第二步变化中，公式省去了单独的项。接下来介绍的是基于泰勒公式原理对GBDT优化求解的方案。

4）泰勒公式
泰勒公式是研究复函数性质时常用的逼近方法之一，也是泛函微积分的重要应用。如果函数满足一定的条件，泰勒公式可以用函数在某一点的导数值作为系数，构造一个多项式来逼近函数。公式展开如下：

5）目标函数用泰勒展开式表示
然后，接下来，我们对目标函数进行泰勒展开，求解过程如下：

我们订购：


其中，和分别代表目标函数和的一阶和二阶导数。所以我们的目标函数泰勒展开公式为：

如果认为目标损失函数为均方误差，则和的计算结果为：


所以我们将目标函数解析为：


由于常数对目标函数的优化没有影响，去掉常数部分，进一步解析为：

其中和分别代表目标函数到的一阶和二阶导数。

6）正则化项
那么目标函数的正则化项如何表示呢？首先我们要明确一点，正则化项的目的是防止模型过拟合，所以要防止模型过于复杂。基于树模型结构，我们可以定义正则化公式如下：

其中，代表叶子节点个数，代表第个叶子节点的得分。从正则化公式的表达式可以看出，正则化项可以防止一棵树的叶子节点过多以及叶子节点的值。不能太大。如下所示：

那么的计算结果为：，在前面的目标损失函数中，我们知道是模型结果的预测得分，那么对于树模型结构我们做出：

其中是T维度向量，元素里的每个值表示的是每个叶子节点分值。是映射函数，对于样本x，映射到树结构的具体哪个叶子节点。将正则化项和树模型结构表示带入上述目标函数为：

我们定义：


然后我们进一步解析上述目标函数得到：


其中是我们要优化的值，也就是树结构中的叶子节点值，最小化上述目标损失函数，我们对求导并且令结果等于0：

您可以获得以下值：

将的值带入目标损失函数，可以得到目标损失函数：

得到最终的目标损失函数表达式。我们需要解决的是和，其中和分别表示叶子节点处所有样本的一阶导数和二阶导数的分数之和。所以对于任何一种结构树，我们都可以计算出样本到达的叶子节点的目标损失函数值，如下图所示：

7）如何求解一颗树的最优分割结构
为了使得Obj最小，我们需要计算所有组合分割的树，然后根据上述公式，计算每一棵树的目标损失值，最后选择损失值最小的树结构。这样是否可行？肯定不可行，穷举所有树的结构，复杂度太高。所以，我们在树的每一层是否需要对节点切分成左节点和右节点，取决与分割后目标损失值是否比不切割前少，以及按照什么特征点切分，切分阈值，选择收益最大（新选择的切割点后目标损失loss值最低），切分收益gain计算如下（切割前的loss – 切割后的loss)：

所以该叶子节点是否要切分，通过上述公式，若gain收益大于0，则就可以继续切分，至于怎么切割，可以对所有样本的和进行排序，然后从左到右扫描选择最优的切割点，如下图所示：

2.2 训练

熟悉GBDT的原理后，接下来我们来看下GBDT模型是如何训练的，以及训练完后，我们得到的到底是什么样的模型结构

训练步骤
假设我们用的是均方差损失函数，gbdt模型训练步骤总结如下：

• 第一步（初值确定）：每个样本的初值模型预测得分为所有样本的平均值：
  
• 第二步 (建树第1棵）：对每个样本，根据之前的预测结果值以及对应的标签值，得到目标函数对模型上一步的预测值的
  一阶导数以及二阶导数，然后遍历所有特征类型，以及每个特征对应的特征值范围，进行切分后，计算切分前后的Gain增长情况，选择增长最大的切分点，然后继续向下切分节点，直到切分前后差异低于设定的阈值，或者模型的深度，叶子节点数等超过设置的阈值。最后，
  叶子节点w值计算根据上述公式
  :，其中是落入这个叶子节点的所有样本的一阶导数之和和二阶导数之和，这样一个样本就可以按照规则计算和划分，哪个叶子节点它落入
  功能。
  
• 第三步 （建树第2棵）：对所有样本，经过前面的所有树，根据切分条件，落入到每棵树的叶子节点的分值累积之和为当前样本预测的分值：, 按照第一棵建树规则过程，对于第二棵树的构建，然后计算每个叶子节点的分值
  
• 第四步 （建树第3棵）：所有样本经过前面构建好的树，根据条件到达叶子节点，则此时的样本的预测结果值为：，根据最新结果，然后计算每个样本的，选择增益最大的gain作为切分点。
  
• …
  
• 直到创建的树数达到设定的阈值
  

模型结构
训练完后，就得到了N棵树，每一棵树的结构本质上是一连串的分段规则组成，根据输入样本的特征满足情况走树的不同分支，最后落入到树的某个叶子节点，其中落入到叶子节点的权重值就是这个样本在当前这课树的预测分值，如下图所示：

2.3 预测

当训练好了模型以后，预测的过程就简单了，假设有T棵树，则最终的模型预测结果为这个样本落入到每棵树的叶子节点分值之和，用公式表达如下：

3 训练框架

接下来介绍优化Gradient Boosting算法的几种分布式训练框架，这些框架支持分布式训练，树的调优，缺失值处理，正则化等避免过拟合问题。

3.1 XGBoost

XGBoost: A Scalable Tree Boosting System是由2014年5月，由DMLC开发出来的，目前是比较受欢迎，高效分布式训练Gradient Boosted Trees算法框架，包含的详细资料可以参考官方文档:官网文档。

3.2 LightGBM

LightGBM: A Highly Efficient Gradient Boosting Decision Tree是由微软团队于2017年1月针对XGBoost框架存在的一些问题，设计出的更加高效的学习框架，主要基于梯度单边采样GOSS((Gradient Based One Side Sampling)以及互斥特征合并EFB(Exclusive Feature Bundling)来加快模型的学习效率，详细资料可以参考官方文档官网文档。下面提供的是一个简单的在基于lightgbm做rank排序代码：

import lightgbm as lgb
import numpy as np 
import pandas as pd
from sklearn.model_selection import train_test_split
import seaborn as sns
import matplotlib.pyplot as plt
import seaborn as sns
import shap
import graphviz

#读取数据，显示前面20行
df = pd.read_csv('train.csv')
df.head(20)
#显示数据列名称
df.columns
#抽取x,y对应的字段
X = df.drop(['label','query','term'], axis=1)
y = df.label
group=np.loadtxt('./group.txt')
#训练数据
train_data = lgb.Dataset(X, label=y, group=group,free_raw_data=False)
#参数定义
params = {
    'task' : 'train', 
    'boosting_type': 'gbdt',
    'objective': 'lambdarank',
    'num_iterations': 200,
    'learning_rate':0.1,
    'num_leaves': 31,
    'tree_learner': 'serial',
    'max_depth': 6,
    'metric': 'ndcg',
    'metric_freq': 10,
    'train_metric':True,
    'ndcg_at':[2],
    'max_bin':255,
    'max_position': 20,
    'verbose':0
}
#指明类别特征
categorical_feature=[0,1]
#训练
gbm=lgb.train(params,
              train_data,
              valid_sets=train_data,
              categorical_feature=categorical_feature)
#模型保存
gbm.save_model('model_large.md')
#预测
bst = lgb.Booster(model_file='model_large.md')
df_test = pd.read_csv('test.csv')
y_pred = bst.predict(test)

#feature重要度
fea_imp = pd.DataFrame({'imp': bst.feature_importance(importance_type='split'), 'col': X.columns})
fea_imp = fea_imp.sort_values(['imp', 'col'], ascending=[True, False]).iloc[-30:]
fea_imp.plot(kind='barh', x='col', y='imp', figsize=(10, 7), legend=None)
plt.title('Feature Importance')
plt.ylabel('Features')
plt.xlabel('Importance');
# 基于shap特征分析
explainer = shap.TreeExplainer(bst)
shap_values = explainer.shap_values(X)
shap.summary_plot(shap_values, X, plot_type="bar")
shap.summary_plot(shap_values, X)
shap.dependence_plot('entropy', shap_values, X, interaction_index=None, show=True)

3.3 CatBoost

CatBoost: unbiased boosting with categorical features是由2017年4月，俄罗斯搜索巨头Yandex开发出的优化xgboost的一个框架，该框架最大的优势就是能够处理categorical features，相比LightGBM，不需要对分类特征进行label encoding，方便用户的快速操作。详细的官方网址：官网网址，下面是三者的详细对比图：
训练loss对比：

模型性能对比：左边是CPU机器，右边是GPU机器

可以看出Catboost相比XGBoost和LightGBM在指标收敛效果有一定提升的条件下，在模型性能上有较大的提升。如下是基于Catboost进行训练的简单代码式例：

import numpy as np 
import pandas as pd
import os
from sklearn.metrics import mean_squared_error
from sklearn import feature_selection
from catboost import CatBoostClassifier
from sklearn.model_selection import train_test_split
from sklearn import preprocessing
import seaborn as sns
import matplotlib.pyplot as plt

#读取数据
df = pd.read_csv('data.csv')
df.head()
#显示特征名
df.columns
#显示某个特征名的数据情况
pd.set_option('display.float_format', '{:.2f}'.format)
df.f_ctf.describe()
#特征分布显示
plt.figure(figsize = (10, 4))
plt.scatter(range(df.shape[0]), np.sort(df['f_ctf'].values))
plt.xlabel('index')
plt.ylabel('f_ctf')
plt.title("f_ctf Distribution")
plt.show();
#训练样本划分
X_train, X_valid, y_train, y_valid = train_test_split(X, y, test_size=0.20, random_state=42)
#指明categorical特征
categorical_features_indices=[1,2,3]
#模型训练
model =  CatBoostClassifier(iterations=700,
                             learning_rate=0.01,
                             depth=15,
                             eval_metric='AUC',
                             random_seed = 42,
                             bagging_temperature = 0.2,
                             od_type='Iter',
                             metric_period = 75,
                             loss_function='Logloss',
                             od_wait=100)
model.fit(X_train, y_train,
                 eval_set=(X_valid, y_valid),
                 cat_features=categorical_features_indices,
                 use_best_model=True,
                 plot=True)

#特征重要度显示
fea_imp = pd.DataFrame({'imp': model.feature_importances_, 'col': X.columns})
fea_imp = fea_imp.sort_values(['imp', 'col'], ascending=[True,False]).iloc[-30:]
fea_imp.plot(kind='barh', x='col', y='imp', figsize=(10, 7), legend=None)
plt.title('CatBoost - Feature Importance')
plt.ylabel('Features')
plt.xlabel('Importance');

3.4 NGBoost

NGBoost: Natural Gradient Boosting for Probabilistic Prediction是一个比较新的训练Gradient Boosting算法框架。于2019年10月由斯坦福吴恩达团队公开发表。github代码记录在：NGBoost Github，核心点在于它使用自然梯度提升，一种用于概率预测的模块化提升算法。该算法由​基学习​器、​参数概率分布​和​评分规则​组成。

4 树模型与深度模型结合

树模型有较强的解释性和稳定性，但是缺陷就是无语义特征，泛化能力不够强，所以在实际场景中，可以将树模型与深度学习模型结合，比如简单的求个平均可能都有一定提升，这是一个简单试验对比效果，bert比gbdt模型在情感分类任务中有一定提升，但将bert和gbdt结果融合到一起简单求一个平均值，效果最佳，具体可以参考有人做的一个简单对比试验：bert vs catboost

6 参考资料

1 GBDT Youtube Video