背景概述

集成学习

在目前学界及业界，神经网络代表的方法各个领域大热时，集成学习 （ Ensemble Learning ）所代表的传统方法却屡屡在数据挖掘竞赛（如kaggle，天池）中占据绝对的领先优势，kaggle的数据挖掘经典项目中屡屡出现Top 10 solutions，Ensemble Learning占据其中80%以上的情况，并且在工业界中，由于需要处理的数据多为传统的结构化数据，实际的二分类，多分类以及回归应用中，以XGBoost等算法为代表的集成学习方法也一直占据绝对主流，因此，本文将从集成学习大框架的背景下，着重探讨目前性能最强的梯度提升树系列细节。

主流分支

1.2.1 bagging

Bagging 的思路是所有基础模型都一致对待，每个基础模型手里都只有一票。然后使用民主投票的方式得到最终的结果。大部分情况下，经过 bagging 得到的结果 方差 （variance）更小。
具体过程：
- 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
- 每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
- 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
举例： 在 bagging 的方法中，最广为熟知是随机森林：bagging + 决策树 = 随机森林

1.2.2 boosting

Boosting 和 bagging 最本质的差别在于他对基础模型不是一致对待的，而是经过不停的考验和筛选来挑选出「精英」，然后给精英更多的投票权，表现不好的基础模型则给较少的投票权，然后综合所有人的投票得到最终结果。大部分情况下，经过 boosting 得到的结果偏差（bias）更小。
具体过程：
- 通过加法模型将基础模型进行线性的组合。
- 每一轮训练都提升那些错误率小的基础模型权重，同时减小错误率高的模型权重。
- 在每一轮改变训练数据的权值或概率分布，通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。
举例： 在 boosting 的方法中，最经典的是GBDT。

Boosting

GBDT

Gradient Boosting Decision Tree, GBDT，是后续所有高阶boosting方法的基础，可以说了解GBDT基本上就了解80%的高级boosting模型知识，GBDT原论文如下所示。

暂时无法在飞书文档外展示此内容

2.1.1 前向分步算法与梯度提升

GBDT以及其他类型的提升树模型都是基于前向分步算法的（Forward stagewise algorithm）。而前向分步算法可以这样来理解，假设我们要使用决策树来预测一个人的年龄，刚开始的时候模型初始化会直接给出一个预测值 $f_0(x)$ ，注意这个预测值不需要训练决策树来得到，而且不一定精确（比如刚开始模型初始预测为0岁，或者根据人群年龄分布给出一个相对合理的值）。接着在模型上一步所给出的预测基础上来训练第一棵决策树，此时模型的输出便是模型初始化的预测值加上第一棵决策树的输出值，然后我们继续添加第二棵决策树，使得第二棵决策树能够在前面所构造的模型基础之上，让损失最小，不断的进行这一过程直到构建的决策树棵数满足要求或者损失小于一个阈值。当进行到第 m 步时，模型可以表示为：

其中 $f_{m-1}(x)$ 是已经构造的 m−1 棵决策树所组成的模型（包括模型初始值），而 T(x;Θm) 是我们当前需要构造的第 m 棵决策树， βm 代表决策树的系数。需要提及一点的是，前向分步算法并不是拘泥于某一个分类器，此处仅以决策树为例。因为前面的 m−1 棵决策树已经训练好了，参数都已经固定了，当系数 βm 取一个固定值时，那么在第 m 步，我们仅需要训练第 m 棵树的参数 Θm 来最小化当前的损失：

其中 N 代表样本的总个数， L 代表损失函数。在前向分步算法搞清楚之后，我们再来回顾一下机器学习中是如何最小化损失函数的。

假设现有一损失函数 J(θ) ，当我们需要对这个参数为 θ 的损失函数求最小值时，只要按照损失函数的负梯度方向调整参数 θ 即可，因为梯度方向是使得函数增长最快的方向，沿着梯度的反方向也就是负梯度方向会使得函数减小最快，当学习率为 ρ 时， θ 的更新方法如下：

那么同理，前向分步算法模型的损失 L 只和构造的模型 $f_{m-1}(x)$ 有关，为了使得损失总体损失 $J=\sum_iL(y_i,f_{m-1}(x_i))$ 进一步降低，需要对 $f_{m-1}(x)$ 求导，而 $f_{m-1}(x)$ 是针对 N 个样本的，所以对每个样本预测值求偏导数：

这里的 ρ 和刚才所提到的 βm 的作用是相同的。因此，对于第 m 棵决策树而言，其拟合的不再是原有数据 (xi,yi) 的目标值 yi ，而是负梯度，这样才能使得损失函数下降最快：

综合来看，GBDT中梯度提升的含义是，模型开始时会给出一个初始预测值，在构建后续的决策树时，每个样本的目标值就变成了损失函数对当前模型在这个样本产生的负梯度，这样做的目的是为了最小化损失函数，进而提升模型性能。最后我们将所有的决策树组合起来，便是GBDT模型。

2.1.2 分类树与回归树

GBDT所使用的分类与回归树（Classification and regression tree, CART）。从名字上看，CART决策树可以处理分类和回归问题，这当然取决于分裂准则的选择。当采用平方误差损失时，可以应对回归问题，当采用基尼指数指导分裂时，可以应对分类问题。但在GBDT采用CART决策树作为基函数时，尽管GBDT可以处理分类与回归问题（实际上这也取决于GBDT损失函数的选择），CART决策树的分裂准则一直采用平方误差损失（比如在sklearn的实现中，均默认采用“friedman_mse“，一种基于平方误差损失的改进版），因此在这一节中，我们主要介绍一下当损失函数为平方误差时CART决策树的生成流程。

2.1.2.1 CART树

对给定训练集 D

（1）依次遍历每个变量的取值，寻找最优切分变量 j 与切分点 s ，进而求解：

这一步就是对当前节点寻找最优切分点，使得切分之后两个节点总体平方误差最小。

（2）接着用选定的对 (j,s) 划分区域并决定相应的输出值：
- R1(j,s),R2(j,s) 分别代表的是左子节点和右子节点，而对两个节点上的估计值 $\hat{c}_m$ 采用相应子节点上目标值的均值来表示（注意这里划分区间时是一直按照平方误差损失最小划分的，但 $\hat{c}_m$ 采用均值是因为此时的损失函数为平方误差，当损失函数变化时便不是均值了）。
（3）继续对两个子区域调用步骤（1），（2），直到满足停止条件（比如子节点上样本个数过少或者决策树已经达到指定的深度）。
（4）将输入空间划分为 M 个区域 R1,R2,⋯,RM ，生成决策树：

f(x) 即为CART决策树， I(x∈Rm) 表示相应样本属于的区域，在相应区域其值为1，否则为0。

2.1.2.2 GBDT 回归

输入：训练数据集 T={(x1,y1),(x2,y2),⋯,(xN,yN)}, xi∈X, yi∈Y，以及学习率 βm

输出：提升树 $f_{m}(x)$ 。

（1）初始化 $f_{0}(x)$ = $\frac{1}{n}\sum_{i}^ny_i$ 。

（2）对 m=1,2,⋯,M 。

计算残差：

拟合残差 r 学习一个回归树，得到第 m 棵树的叶结点区域 Rmj, j=1,2,⋯,J 。注意这一步是按照平方误差损失进行分裂节点的。
对 j=1,2,⋯,J ，计算：

需要注意的是，这一步是为了计算怎么对叶结点区域内的样本进行赋值，使得模型损失最小，因此这一步是需要根据当前模型的损失函数来计算的，当前模型是针对回归问题的模型，我们的损失函数是平方误差损失，所以这一步计算结果为：每个叶结点区域残差的均值。

更新：

（3）得到回归问题提升树

需要再提一遍的是， βm 的作用和梯度下降时的学习率一致，能够使得损失函数收敛到更小的值，因此可以调小 βm ，而一个较小的学习率会使得模型趋向于训练更多的决策树，使得模型更加稳定，不至于过拟合。

2.1.2.2 GBDT 分类

因为处理回归问题的GBDT采用的是以平方误差为分裂准则的CART决策树，其叶节点的输出其实是整个实数范围的，我们可以参考逻辑回归在线性回归的基础上添加激活函数的方法，来使得GBDT同样能够应对分类问题。把二分类GBDT的损失函数定义为：

其中 y^ 代表的是当前样本类别为1的概率 P(y=1|x) 。那么对于总体损失函数 J，其对每个样本当前预测值产生的梯度为：

也就是当前模型预测的概率值与真实样本之间的差值，那么负梯度可以写为：

二分类

因此对于处理二分类问题的GBDT来说，其每次拟合的是真实样本值与模型预测值的差值，所以二分类问题的GBDT方法流程可以写为：

输入：训练数据集 T={(x1,y1),(x2,y2),⋯,(xN,yN)}, xi∈X, yi∈{0,1} ，以及学习率 βm
输出：提升树 $f_{M}(x)$ 。
- 初始化 $f_{0}(x)$ = $log\frac{p_1}{1-P_1}$ ，其中 p1 代表的是样本中 y=1 的比例
- 对 m=1,2,⋯,M 。
  - 计算负梯度：其中 y^i代表 yi=1 的概率。
  - 拟合负梯度 rmi 学习一个回归树，得到第 m 棵树的叶结点区域 Rmj, j=1,2,⋯,J 。注意这一步也是按照平方误差损失进行分裂节点的。
  - 对 j=1,2,⋯,J ，计算：
  - 同样的，当前模型是针对二分类问题，损失函数是交叉熵损失，所以这一步计算结果为
  - 更新 :
得到二分类问题提升树

多分类

二分类问题对于GBDT来讲，利用sigmoid函数将输出值归一化。而在处理多分类问题时，GBDT采用softmax函数求解。对于多分类问题每个样本的类标都要先经过one-hot编码，这样才能划分成多个二分类问题来求解。假设数据集 D 的类别数 K=4 ，样本个数为 N ，并且样本 x1,x2,x3,x4 的类标分别为 y1=0,y2=1,y3=2,y4=3 ，那么在处理多分类问题时，GBDT将会通过one-hot编码将原有的一个多分类问题转化为四个二分类问题。

对于处理多分类问题的GBDT来说，其每次拟合的是真实类标与模型预测值之差，所以多分类问题的GBDT方法流程可以写为：

输入：训练数据集 T={(x1,y1),(x2,y2),⋯,(xN,yN)}, xi∈X, yi∈{0,1,⋯,K} ，以及学习率 βm 。
输出：提升树 $f_{M}(x)$ 。
- 初始化 $f_{k,0}(x)$ =0 ，即 $P(y_{i,k}|x)=\frac{1}{k}$ ,k=1,2,⋯,K 。这样初始化是考虑到当我们对数据一无所知时，最好的假设就是每类发生的概率相等，但当我们知道数据集类别分布情况后，我们可以按照类别比例来设置初始化。
- 对 m=1,2,⋯,M 。
  - 对 i=1,2,⋯,N,k=1,2,⋯,K ，计算
  - 对 k=1,2,⋯,K ：
    - 计算负梯度：其中 $r_{i,k,m}$ 代表的是模型在第 m 轮学习中，第 k 个二分类问题里，对第 i 个样本产生的负梯度。
    - 拟合负梯度 $r_{i,k,m}$ 学习一个回归树，得到第 m 棵树的叶结点区域 $R_{j,k,m}$ ,j=1,2,⋯,J 。注意这一步也是按照平方误差损失进行分裂节点的。
    - 对 j=1,2,⋯,J ，计算：
      - 同样的，当前模型是针对多分类问题的模型，根据多分类模型的损失函数，这一步计算结果为:
    - 更新
得到多分类问题提升树:

XGBoost

XGBoost是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进，被广泛应用在机器学习竞赛中。XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致，所以叫X (Extreme) GBoosted。

2.2.1 目标函数

GBDT 使用的是损失函数一阶导数，相当于函数空间中的梯度下降；而 XGBoost 使用了损失函数二阶导数，相当于函数空间中的牛顿法。

XGB目标函数在加入了正则项：

其中，正则项 Ω(f) 表示子模型 f 的复杂度。

泰勒公式是将一个在 x=x0 处具有 n 阶导数的函数 f(x) 利用关于 Δx=x−x0 的 n 次多项式来逼近 f(x) 的方法。XGBoost运用二阶展开来近似表达损失函数。

目标函数中，将 $F_{m-1}(x_i)$ 视作 x0 ， $F_{m}(x_i)$ 视作 Δx , L(yi^,yi) 视作关于 yi^ 的函数，可得：

前 m−1 个子模型已经确定了，故上式中除了关于 $f_m(x)$ 的部分都是常数，不影响对 $f_m(x)$ ) 的优化求解。目标函数可转化为：

其中

这里的 L 是损失函数，度量一次预测的好坏。在 $F_{m-1}(x)$ 确定了的情况下，对每个样本点 i 都可以轻易计算出一个 gi 和 hi.

一个极其优异的优化：默认可处理缺失值

XGBoost模型的一个优点就是允许特征存在缺失值。对缺失值的处理方式如下：

在特征k上寻找最佳 split point 时，不会对该列特征 missing 的样本进行遍历，而只对该列特征值为 non-missing 的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。
在逻辑实现上，为了保证完备性，会将该特征值missing的样本分别分配到左叶子结点和右叶子结点，两种情形都计算一遍后，选择分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向。
如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。

2.2.2 工程优化

2.2.2.1 并行列块设计

XGBoost将每一列特征提前进行排序，以块（Block）的形式储存在缓存中，并以索引将特征值和梯度统计量 gi,hi 对应起来，每次节点分裂时会重复调用排好序的块。而且不同特征会分布在独立的块中，因此可以进行分布式或多线程的计算。

XGBoost的并行，并不是说每棵树可以并行训练，XGB 本质上仍然采用boosting思想，每棵树训练前需要等前面的树训练完成才能开始训练。因此XGBoost的并行，指的是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

2.2.2.2 缓存访问

特征值排序后通过索引来取梯度 gi,hi 会导致访问的内存空间不一致，进而降低缓存的命中率，影响算法效率。为解决这个问题，XGBoost为每个线程分配一个单独的连续缓存区，用来存放梯度信息。

2.2.2.3 核外块计算

数据量过大时，不能同时全部载入内存。XGBoost将数据分为多个blocks并储存在硬盘中，使用一个独立的线程专门从磁盘中读取数据到内存中，实现计算和读取数据的同时进行。为了进一步提高磁盘读取数据性能，XGBoost还使用了两种方法：一是通过压缩block，用解压缩的开销换取磁盘读取的开销；二是将block分散储存在多个磁盘中，有助于提高磁盘吞吐量。

2.2.3 对比GBDT

性质：GBDT是机器学习算法，XGBoost除了算法内容还包括一些工程实现方面的优化。
基于二阶导：GBDT使用的是损失函数一阶导数，相当于函数空间中的梯度下降；而XGBoost还使用了损失函数二阶导数，相当于函数空间中的牛顿法。
正则化：XGBoost显式地加入了正则项来控制模型的复杂度，能有效防止过拟合。
列采样：XGBoost采用了随机森林中的做法，每次节点分裂前进行列随机采样。
缺失值处理：XGBoost运用稀疏感知策略处理缺失值，而GBDT没有设计缺失策略。
并行高效：XGBoost的列块设计能有效支持并行运算，提高效率。

LightGbm

LightGBM 由微软提出，主要用于解决 GDBT 在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中。从 LightGBM 名字我们可以看出其是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。

2.3.1 单边梯度采样算法

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。

GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。具体算法如下所示：我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序（无需保存排序后结果），然后拿到前 a% 的梯度大的样本，和总体样本的 b%，在计算增益时，通过乘上 (1−a)/b 来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

2.3.2 直方图算法

直方图算法的基本思想是将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。

我们知道特征离散化的具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等等。对于直方图算法来说最直接的有以下两个优点（以 k=256 为例）：

内存占用更小：XGBoost 需要用 32 位的浮点数去存储特征值，并用 32 位的整形去存储索引，而 LightGBM 只需要用 8 位去存储直方图，相当于减少了 1/8；
计算代价更小：计算特征分裂增益时，XGBoost 需要遍历一次数据找到最佳分裂点，而 LightGBM 只需要遍历一次 k ，直接将时间复杂度从 O(#data * #feature) 降低到 O(k * #feature) ，而我们知道 #data>>k 。

虽然将特征离散化后无法找到精确的分割点，可能会对模型的精度产生一定的影响，但较粗的分割也起到了正则化的效果，一定程度上降低了模型的方差。

2.3.3 互斥特征捆绑算法

高维特征往往是稀疏的，而且特征间可能是相互排斥的（如两个特征不同时取非零值），如果两个特征并不完全互斥（如只有一部分情况下是不同时取非零值），可以用互斥率表示互斥程度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。

针对这种想法，我们会遇到两个问题：

哪些特征可以一起绑定？
特征绑定后，特征值如何确定？

对于问题一：EFB 算法利用特征和特征间的关系构造一个加权无向图，并将其转换为图着色算法。我们知道图着色是个 NP-Hard 问题，故采用贪心算法得到近似解，具体步骤如下：

构造一个加权无向图，顶点是特征，边是两个特征间互斥程度；
根据节点的度进行降序排序，度越大，与其他特征的冲突越大；
使得总体冲突最小。

对于问题二：论文给出特征合并算法，其关键在于原始特征能从合并的特征中分离出来。假设 Bundle 中有两个特征值，A 取值为 [0, 10]、B 取值为 [0, 20]，为了保证特征 A、B 的互斥性，我们可以给特征 B 添加一个偏移量转换为 [10, 30]，Bundle 后的特征其取值为 [0, 30]，这样便实现了特征合并。具体算法如下所示：

2.3.4 工程优化

2.3.4.1 特征并行

传统的特征并行算法在于对数据进行垂直划分，然后使用不同机器找到不同特征的最优分裂点，基于通信整合得到最佳划分点，然后基于通信告知其他机器划分结果。

传统的特征并行方法有个很大的缺点：需要告知每台机器最终划分结果，增加了额外的复杂度（因为对数据进行垂直划分，每台机器所含数据不同，划分结果需要通过通信告知）。

LightGBM 则不进行数据垂直划分，每台机器都有训练集完整数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

2.3.4.2 数据并行

传统的数据并行策略主要为水平划分数据，然后本地构建直方图并整合成全局直方图，最后在全局直方图中找出最佳划分点。

这种数据划分有一个很大的缺点：通讯开销过大。如果使用点对点通信，一台机器的通讯开销大约为 O(#machine∗#feature∗#bin) ；如果使用集成的通信，则通讯开销为 O(2∗#feature∗#bin) ，

LightGBM 采用分散规约（Reduce scatter）的方式将直方图整合的任务分摊到不同机器上，从而降低通信代价，并通过直方图做差进一步降低不同机器间的通信。

2.3.4.3 投票并行

针对数据量特别大特征也特别多的情况下，可以采用投票并行。投票并行主要针对数据并行时数据合并的通信代价比较大的瓶颈进行优化，其通过投票的方式只合并部分特征的直方图从而达到降低通信量的目的。

大致步骤为两步：

本地找出 Top K 特征，并基于投票筛选出可能是最优分割点的特征；
合并时只合并每个机器选出来的特征。

2.3.4.4 缓存优化

上边说到 XGBoost 的预排序后的特征是通过索引给出的样本梯度的统计值，因其索引访问的结果并不连续，XGBoost 提出缓存访问优化算法进行改进。

而 LightGBM 所使用直方图算法对 Cache 天生友好：

首先，所有的特征都采用相同的方法获得梯度（区别于不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中；
其次，因为不需要存储特征到样本的索引，降低了存储消耗，而且也不存在 Cache Miss的问题。

2.3.5 对比XGBoost

内存更小
- XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，降低了空间复杂度，极大的减少了内存消耗；
- LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
- LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。
- LightGBM内存占用率大约为 XGBoost 的1/6。
速度更快
- LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
- LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
- LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
- LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
- LightGBM 对缓存也进行了优化，增加了 Cache hit 的命中率。
- LightGBM比 XGBoost 快将近10倍。

3. 梯度提升树效果

树模型和神经网络，像一枚硬币的两面。在某些情况下，树模型的性能优于神经网络。

由于神经网络的复杂性，它们常常被认为是解决所有机器学习问题的「圣杯」。而另一方面，基于树的方法并未得到同等重视，主要原因在于这类算法看起来很简单。然而，这两种算法看似不同，却像一枚硬币的正反面，都很重要。

树模型 VS 神经网络

基于树的方法通常优于神经网络。本质上，将基于树的方法和基于神经网络的方法放在同一个类别中是因为，它们都通过逐步解构来处理问题，而不是像支持向量机或 Logistic 回归那样通过复杂边界来分割整个数据集。

很明显，基于树的方法沿着不同的特征逐步分割特征空间，以优化信息增益。不那么明显的是，神经网络也以类似的方式处理任务。每个神经元监视特征空间的一个特定部分（存在多种重叠）。当输入进入该空间时，某些神经元就会被激活。

神经网络以概率的视角看待这种逐段模型拟合 (piece-by-piece model fitting)，而基于树的方法则采用确定性的视角。不管怎样，这两者的性能都依赖于模型的深度，因为它们的组件与特征空间的各个部分存在关联。

包含太多组件的模型（对于树模型而言是节点，对于神经网络则是神经元）会过拟合，而组件太少的模型根本无法给出有意义的预测。（二者最开始都是记忆数据点，而不是学习泛化。）

要想更直观地了解神经网络是如何分割特征空间的，可阅读这篇介绍通用近似定理的文章：medium.com/analytics-v…

虽然决策树有许多强大的变体，如随机森林、梯度提升、AdaBoost 和深度森林，但一般来说，基于树的方法本质上是神经网络的简化版本。

基于树的方法通过垂直线和水平线逐段解决问题，以最小化熵（优化器和损失）。神经网络通过激活函数来逐段解决问题。
基于树的方法是确定性的，而不是概率性的。这带来了一些不错的简化，如自动特征选择。
决策树中被激活的条件节点类似于神经网络中被激活的神经元（信息流）。
神经网络通过拟合参数对输入进行变换，间接指导后续神经元的激活。决策树则显式地拟合参数来指导信息流。（这是确定性与概率性相对应的结果。）

信息在两个模型中的流动相似，只是在树模型中的流动方式更简单。

树模型的 1 和 0 选择 VS 神经网络的概率选择

当然，这是一个抽象的结论，甚至可能是有争议的。诚然，建立这种联系有许多障碍。不管怎样，这是理解基于树的方法何时以及为什么优于神经网络的重要部分。

对于决策树而言，处理表格或表格形式的结构化数据是很自然的。大多数人都同意用神经网络执行表格数据的回归和预测属于大材小用，所以这里做了一些简化。选择 1 和 0，而不是概率，是这两种算法之间差异的主要根源。因此，基于树的方法可成功应用于不需要概率的情况，如结构化数据。

例如，基于树的方法在 MNIST 数据集上表现出很好的性能，因为每个数字都有几个基本特征。不需要计算概率，这个问题也不是很复杂，这就是为什么设计良好的树集成模型性能可以媲美现代卷积神经网络，甚至更好。

通常，人们倾向于说「基于树的方法只是记住了规则」，这种说法是对的。神经网络也是一样，只不过它能记住更复杂的、基于概率的规则。神经网络并非显式地对 x>3 这样的条件给出真 / 假的预测，而是将输入放大到一个很高的值，从而得到 sigmoid 值 1 或生成连续表达式。

另一方面，由于神经网络非常复杂，因此使用它们可以做很多事情。卷积层和循环层都是神经网络的杰出变体，因为它们处理的数据往往需要概率计算的细微差别。

很少有图像可以用 1 和 0 建模。决策树值不能处理具有许多中间值（例如 0.5）的数据集，这就是它在 MNIST 数据集上表现很好的原因，在 MNIST 中，像素值几乎都是黑色或白色，但其他数据集的像素值不是（例如 ImageNet）。类似地，文本有太多的信息和太多的异常，无法用确定性的术语来表达。

这也是神经网络主要用于这些领域的原因，也是神经网络研究在早期（21 世纪初之前）停滞不前的原因，当时无法获得大量图像和文本数据。神经网络的其他常见用途仅限于大规模预测，比如 YouTube 视频推荐算法，其规模非常大，必须用到概率。

任何公司的数据科学团队可能都会使用基于树的模型，而不是神经网络，除非他们正在建造一个重型应用，比如模糊 Zoom 视频的背景。但在日常业务分类任务上，基于树的方法因其确定性特质，使这些任务变得轻量级，其方法与神经网络相同。

在许多实际情况下，确定性建模比概率建模更自然。例如，预测用户是否从某电商网站购买一样商品，这时树模型是很好的选择，因为用户天然地遵循基于规则的决策过程。用户的决策过程可能看起来像这样：

我以前在这个平台上有过愉快的购物经历吗？如果有，继续。
我现在需要这件商品吗？（例如，冬天我应该买太阳镜和泳裤吗？）如果是，继续。
根据我的用户统计信息，这是我有兴趣购买的产品吗？如果是，继续。
这个东西太贵吗？如果没有，继续。
其他顾客对这个产品的评价是否足够高，让我可以放心地购买它？如果是，继续。

一般来说，人类遵循基于规则和结构化的决策过程。在这些情况下，概率建模是不必要的。

结论
- 最好将基于树的方法视为神经网络的缩小版本，以更简单的方式进行特征分类、优化、信息流传递等。
- 基于树的方法和神经网络方法在用途的主要区别在于确定性（0/1）与概率性数据结构。使用确定性模型可以更好地对结构化（表格）数据进行建模。
- 根据相关研究，发现增强树算法非常适合具有少于 10000 个特征和少于一亿个训练样本的预测任务。对于使用具有数千亿训练样本的极高维稀疏数据的应用，通常深度神经网络更方便或更有效。
- 不要低估树方法的威力。

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END

# 算法

机器学习之 梯度提升树系列

背景概述

集成学习

主流分支