高中生做网站网页,高性能网站建设指南,品牌vi设计是什么意思,织梦网站分页问题点击上方“智能与算法之路”#xff0c;选择“星标”公众号第一时间获取价值内容本文主要介绍基于 Boosting 框架的主流集成算法#xff0c;包括 XGBoost 和 LightGBM。送上完整的思维导图#xff1a;XGBoostXGBoost 是大规模并行 boosting tree 的工具#xff0c;它是目前… 点击上方“智能与算法之路”选择“星标”公众号第一时间获取价值内容本文主要介绍基于 Boosting 框架的主流集成算法包括 XGBoost 和 LightGBM。送上完整的思维导图XGBoostXGBoost 是大规模并行 boosting tree 的工具它是目前最快最好的开源 boosting tree 工具包比常见的工具包快 10 倍以上。Xgboost 和 GBDT 两者都是 boosting 方法除了工程实现、解决问题上的一些差异外最大的不同就是目标函数的定义。故本文将从数学原理和工程实现上进行介绍并在最后介绍下 Xgboost 的优点。1.1 数学原理1.1.1 目标函数我们知道 XGBoost 是由 k 个基模型组成的一个加法运算式其中 为第 k 个基模型 为第 i 个样本的预测值。损失函数可由预测值 与真实值 进行表示其中 n 为样本数量。我们知道模型的预测精度由模型的偏差和方差共同决定损失函数代表了模型的偏差想要方差小则需要简单的模型所以目标函数由模型的损失函数 L 与抑制模型复杂度的正则项 组成所以我们有为模型的正则项由于 XGBoost 支持决策树也支持线性模型所以这里不再展开描述。我们知道 boosting 模型是前向加法以第 t 步的模型为例模型对第 i 个样本 的预测为其中 由第 t-1 步的模型给出的预测值是已知常数 是我们这次需要加入的新模型的预测值此时目标函数就可以写成求此时最优化目标函数就相当于求解 。泰勒公式是将一个在 处具有 n 阶导数的函数 f(x) 利用关于 的 n 次多项式来逼近函数的方法若函数 f(x) 在包含 的某个闭区间 上具有 n 阶导数且在开区间 (a,b) 上具有 n1 阶导数则对闭区间 上任意一点 x 有 其中的多项式称为函数在 处的泰勒展开式是泰勒公式的余项且是 的高阶无穷小。根据泰勒公式我们把函数 在点 x 处进行泰勒的二阶展开可得到如下等式我们把 视为 视为 故可以将目标函数写为其中 为损失函数的一阶导 为损失函数的二阶导注意这里的求导是对 求导。我们以平方损失函数为例则由于在第 t 步时 其实是一个已知的值所以 是一个常数其对函数的优化不会产生影响因此目标函数可以写成所以我们只需要求出每一步损失函数的一阶导和二阶导的值(由于前一步的 是已知的所以这两个值就是常数)然后最优化目标函数就可以得到每一步的 f(x) 最后根据加法模型得到一个整体模型。1.1.2 基于决策树的目标函数我们知道 Xgboost 的基模型不仅支持决策树还支持线性模型这里我们主要介绍基于决策树的目标函数。我们可以将决策树定义为 x 为某一样本这里的 q(x) 代表了该样本在哪个叶子结点上而 w_q 则代表了叶子结点取值 w 所以 就代表了每个样本的取值 w (即预测值)。决策树的复杂度可由叶子数 T 组成叶子节点越少模型越简单此外叶子节点也不应该含有过高的权重 w (类比 LR 的每个变量的权重)所以目标函数的正则项可以定义为即决策树模型的复杂度由生成的所有决策树的叶子节点数量和所有节点权重所组成的向量的 范式共同决定。这张图给出了基于决策树的 XGBoost 的正则项的求解方式。我们设 为第 j 个叶子节点的样本集合故我们的目标函数可以写成第二步到第三步可能看的不是特别明白这边做些解释第二步是遍历所有的样本后求每个样本的损失函数但样本最终会落在叶子节点上所以我们也可以遍历叶子节点然后获取叶子节点上的样本集合最后在求损失函数。即我们之前样本的集合现在都改写成叶子结点的集合由于一个叶子结点有多个样本存在因此才有了 和 这两项 为第 j 个叶子节点取值。为简化表达式我们定义 则目标函数为这里我们要注意 和 是前 t-1 步得到的结果其值已知可视为常数只有最后一棵树的叶子节点 不确定那么将目标函数对 求一阶导并令其等于 0 则可以求得叶子结点 j 对应的权值所以目标函数可以化简为上图给出目标函数计算的例子求每个节点每个样本的一阶导数 和二阶导数 然后针对每个节点对所含样本求和得到的 和 最后遍历决策树的节点即可得到目标函数。1.1.3 最优切分点划分算法在决策树的生长过程中一个非常关键的问题是如何找到叶子的节点的最优切分点Xgboost 支持两种分裂节点的方法——贪心算法和近似算法。1)贪心算法从深度为 0 的树开始对每个叶节点枚举所有的可用特征针对每个特征把属于该节点的训练样本根据该特征值进行升序排列通过线性扫描的方式来决定该特征的最佳分裂点并记录该特征的分裂收益选择收益最大的特征作为分裂特征用该特征的最佳分裂点作为分裂位置在该节点上分裂出左右两个新的叶节点并为每个新节点关联对应的样本集回到第 1 步递归执行到满足特定条件为止那么如何计算每个特征的分裂收益呢假设我们在某一节点完成特征分裂则分列前的目标函数可以写为分裂后的目标函数为则对于目标函数来说分裂后的收益为注意该特征收益也可作为特征重要性输出的重要依据。对于每次分裂我们都需要枚举所有特征可能的分割方案如何高效地枚举所有的分割呢我假设我们要枚举所有 x a 这样的条件对于某个特定的分割点 a 我们要计算 a 左边和右边的导数和。我们可以发现对于所有的分裂点 a我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和 和 。然后用上面的公式计算每个分割方案的分数就可以了。2)近似算法贪婪算法可以的到最优解但当数据量太大时则无法读入内存进行计算近似算法主要针对贪婪算法这一缺点给出了近似最优解。对于每个特征只考察分位点可以减少计算复杂度。该算法会首先根据特征分布的分位数提出候选划分点然后将连续型特征映射到由这些候选点划分的桶中然后聚合统计信息找到所有区间的最佳分裂点。在提出候选切分点时有两种策略Global学习每棵树前就提出候选切分点并在每次分裂时都采用这种分割Local每次分裂前将重新提出候选切分点。直观上来看Local 策略需要更多的计算步骤而 Global 策略因为节点没有划分所以需要更多的候选点。下图给出不同种分裂策略的 AUC 变换曲线横坐标为迭代次数纵坐标为测试集 AUCeps 为近似算法的精度其倒数为桶的数量。我们可以看到 Global 策略在候选点数多时(eps 小)可以和 Local 策略在候选点少时(eps 大)具有相似的精度。此外我们还发现在 eps 取值合理的情况下分位数策略可以获得与贪婪算法相同的精度。第一个 for 循环对特征 k 根据该特征分布的分位数找到切割点的候选集合 。XGBoost 支持 Global 策略和 Local 策略。第二个 for 循环针对每个特征的候选集合将样本映射到由该特征对应的候选点集构成的分桶区间中即 对每个桶统计 G,H 值最后在这些统计量上寻找最佳分裂点。下图给出近似算法的具体例子以三分位为例根据样本特征进行排序然后基于分位数进行划分并统计三个桶内的 G,H 值最终求解节点划分的增益。1.1.4 加权分位数缩略图事实上 XGBoost 不是简单地按照样本个数进行分位而是以二阶导数值 作为样本的权重进行划分如下那么问题来了为什么要用 进行样本加权我们知道模型的目标函数为我们稍作整理便可以看出 有对 loss 加权的作用。其中 与 C 皆为常数。我们可以看到 h_i 就是平方损失函数中样本的权重。对于样本权值相同的数据集来说找到候选分位点已经有了解决方案(GK 算法)但是当样本权值不一样时该如何找到候选分位点呢(作者给出了一个 Weighted Quantile Sketch 算法这里将不做介绍。)1.1.5 稀疏感知算法在决策树的第一篇文章中我们介绍 CART 树在应对数据缺失时的分裂策略XGBoost 也给出了其解决方案。XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历而为每个节点增加了一个缺省方向当样本相应的特征值缺失时可以被归类到缺省方向上最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支其实很简单分别枚举特征缺省的样本归为左右分支后的增益选择增益最大的枚举项即为最优缺省方向。在构建树的过程中需要枚举特征缺失的样本乍一看该算法的计算量增加了一倍但其实该算法在构建树的过程中只考虑了特征未缺失的样本遍历而特征值缺失的样本无需遍历只需直接分配到左右节点故算法所需遍历的样本量减少下图可以看到稀疏感知算法比 basic 算法速度块了超过 50 倍。1.2 工程实现1.2.1 块结构设计我们知道决策树的学习最耗时的一个步骤就是在每次寻找最佳分裂点是都需要对特征的值进行排序。而 XGBoost 在训练之前对根据特征对数据进行了排序然后保存到块结构中并在每个块结构中都采用了稀疏矩阵存储格式(Compressed Sparse Columns FormatCSC)进行存储后面的训练过程中会重复地使用块结构可以大大减小计算量。每一个块结构包括一个或多个已经排序好的特征缺失特征值将不进行排序每个特征会存储指向样本梯度统计值的索引方便计算一阶导和二阶导数值这种块结构存储的特征之间相互独立方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征作为分裂这时各个特征的增益计算可以同时进行这也是 Xgboost 能够实现分布式或者多线程计算的原因。1.2.2 缓存访问优化算法块结构的设计可以减少节点分裂时的计算量但特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续这样会造成缓存命中率低从而影响到算法的效率。为了解决缓存命中率低的问题XGBoost 提出了缓存访问优化算法为每个线程分配一个连续的缓存区将需要的梯度信息存放在缓冲区中这样就是实现了非连续空间到连续空间的转换提高了算法效率。此外适当调整块大小也可以有助于缓存优化。1.2.3 “核外”块计算当数据量过大时无法将数据全部加载到内存中只能先将无法加载到内存中的数据暂存到硬盘中直到需要时再进行加载计算而这种操作必然涉及到因内存与硬盘速度不同而造成的资源浪费和性能瓶颈。为了解决这个问题XGBoost 独立一个线程专门用于从硬盘读入数据以实现处理数据和读入数据同时进行。此外XGBoost 还用了两种方法来降低硬盘读写的开销块压缩对 Block 进行按列压缩并在读取时进行解压块拆分将每个块存储到不同的磁盘中从多个磁盘读取可以增加吞吐量。1.3 优缺点1.3.1 优点精度更高GBDT 只用到一阶泰勒展开而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度另一方面也是为了能够自定义损失函数二阶泰勒展开可以近似大量损失函数灵活性更强GBDT 以 CART 作为基分类器XGBoost 不仅支持 CART 还支持线性分类器(使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题))。此外XGBoost 工具支持自定义损失函数只需函数支持一阶和二阶求导正则化XGBoost 在目标函数中加入了正则项用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差使学习出来的模型更加简单有助于防止过拟合Shrinkage(缩减)相当于学习速率。XGBoost 在进行完一次迭代后会将叶子节点的权重乘上该系数主要是为了削弱每棵树的影响让后面有更大的学习空间列抽样XGBoost 借鉴了随机森林的做法支持列抽样不仅能降低过拟合还能减少计算缺失值处理XGBoost 采用的稀疏感知算法极大的加快了节点分裂的速度可以并行化操作块结构可以很好的支持并行计算。1.3.2 缺点虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量但在节点分裂过程中仍需要遍历数据集预排序过程的空间复杂度过高不仅需要存储特征值还需要存储特征对应样本的梯度统计值的索引相当于消耗了两倍的内存。LightGBMLightGBM 由微软提出主要用于解决 GDBT 在海量数据中遇到的问题以便其可以更好更快地用于工业实践中。从 LightGBM 名字我们可以看出其是轻量级(Light)的梯度提升机(GBM)其相对 XGBoost 具有训练速度快、内存占用低的特点。下图分别显示了 XGBoost、XGBoost_hist(利用梯度直方图的 XGBoost) 和 LightGBM 三者之间针对不同数据集情况下的内存和训练时间的对比那么 LightGBM 到底如何做到更快的训练速度和更低的内存使用的呢我们刚刚分析了 XGBoost 的缺点LightGBM 为了解决这些问题提出了以下几点解决方案单边梯度抽样算法直方图算法互斥特征捆绑算法基于最大深度的 Leaf-wise 的垂直生长算法类别特征最优分割特征并行和数据并行缓存优化。本节将继续从数学原理和工程实现两个角度介绍 LightGBM。2.1 数学原理2.1.1 单边梯度抽样算法GBDT 算法的梯度大小可以反应样本的权重梯度越小说明模型拟合的越好单边梯度抽样算法(Gradient-based One-Side Sampling, GOSS)利用这一信息对样本进行抽样减少了大量梯度小的样本在接下来的计算锅中只需关注梯度高的样本极大的减少了计算量。GOSS 算法保留了梯度大的样本并对梯度小的样本进行随机抽样为了不改变样本的数据分布在计算增益时为梯度小的样本引入一个常数进行平衡。具体算法如下所示我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序(无需保存排序后结果)然后拿到前 a% 的梯度大的样本和剩下样本的 b%在计算增益时通过乘上 rac{1-a}{b} 来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。2.1.2 直方图算法直方图算法直方图算法的基本思想是将连续的特征离散化为 k 个离散特征同时构造一个宽度为 k 的直方图用于统计信息(含有 k 个 bin)。利用直方图算法我们无需遍历数据只需要遍历 k 个 bin 即可找到最佳分裂点。我们知道特征离散化的具有很多优点如存储方便、运算更快、鲁棒性强、模型更加稳定等等。对于直方图算法来说最直接的有以下两个优点(以 k256 为例)内存占用更小XGBoost 需要用 32 位的浮点数去存储特征值并用 32 位的整形去存储索引而 LightGBM 只需要用 8 位去存储直方图相当于减少了 1/8计算代价更小计算特征分裂增益时XGBoost 需要遍历一次数据找到最佳分裂点而 LightGBM 只需要遍历一次 k 次直接将时间复杂度从 O(#data * #feature) 降低到 O(k * #feature) 而我们知道 #data k 。虽然将特征离散化后无法找到精确的分割点可能会对模型的精度产生一定的影响但较粗的分割也起到了正则化的效果一定程度上降低了模型的方差。直方图加速在构建叶节点的直方图时我们还可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建从而减少了一半的计算量。在实际操作过程中我们还可以先计算直方图小的叶子节点然后利用直方图作差来获得直方图大的叶子节点。稀疏特征优化XGBoost 在进行预排序时只考虑非零值进行加速而 LightGBM 也采用类似策略只用非零特征构建直方图。2.1.3 互斥特征捆绑算法高维特征往往是稀疏的而且特征间可能是相互排斥的(如两个特征不同时取非零值)如果两个特征并不完全互斥(如只有一部分情况下是不同时取非零值)可以用互斥率表示互斥程度。互斥特征捆绑算法(Exclusive Feature Bundling, EFB)指出如果将一些特征进行融合绑定则可以降低特征数量。针对这种想法我们会遇到两个问题哪些特征可以一起绑定特征绑定后特征值如何确定对于问题一EFB 算法利用特征和特征间的关系构造一个加权无向图并将其转换为图着色算法。我们知道图着色是个 NP-Hard 问题故采用贪婪算法得到近似解具体步骤如下构造一个加权无向图顶点是特征边是两个特征间互斥程度根据节点的度进行降序排序度越大与其他特征的冲突越大遍历每个特征将它分配给现有特征包或者新建一个特征包是的总体冲突最小。算法允许两两特征并不完全互斥来增加特征捆绑的数量通过设置最大互斥率 来平衡算法的精度和效率。EFB 算法的伪代码如下所示我们看到时间复杂度为 O(#feature^2) 在特征不多的情况下可以应付但如果特征维度达到百万级别计算量则会非常大为了改善效率我们提出了一个更快的解决方案将 EFB 算法中通过构建图根据节点度来排序的策略改成了根据非零值的技术排序因为非零值越多互斥的概率会越大。对于问题二论文给出特征合并算法其关键在于原始特征能从合并的特征中分离出来。假设 Bundle 中有两个特征值A 取值为 [0, 10]、B 取值为 [0, 20]为了保证特征 A、B 的互斥性我们可以给特征 B 添加一个偏移量转换为 [10, 30]Bundle 后的特征其取值为 [0, 30]这样便实现了特征合并。具体算法如下所示2.1.4 带深度限制的 Leaf-wise 算法在建树的过程中有两种策略Level-wise基于层进行生长直到达到停止条件Leaf-wise每次分裂增益最大的叶子节点直到达到停止条件。XGBoost 采用 Level-wise 的增长策略方便并行计算每一层的分裂节点提高了训练速度但同时也因为节点增益过小增加了很多不必要的分裂降低了计算量LightGBM 采用 Leaf-wise 的增长策略减少了计算量配合最大深度的限制防止过拟合由于每次都需要计算增益最大的节点所以无法并行分裂。2.1.5 类别特征最优分割大部分的机器学习算法都不能直接支持类别特征一般都会对类别特征进行编码然后再输入到模型中。常见的处理类别特征的方法为 one-hot 编码但我们知道对于决策树来说并不推荐使用 one-hot 编码会产生样本切分不平衡问题切分增益会非常小。如国籍切分后会产生是否中国是否美国等一系列特征这一系列特征上只有少量样本为 1大量样本为 0。这种划分的增益非常小较小的那个拆分样本集它占总样本的比例太小。无论增益多大乘以该比例之后几乎可以忽略较大的那个拆分样本集它几乎就是原始的样本集增益几乎为零影响决策树学习决策树依赖的是数据的统计信息而独热码编码会把数据切分到零散的小空间上。在这些零散的小空间上统计信息不准确的学习效果变差。本质是因为独热码编码之后的特征的表达能力较差的特征的预测能力被人为的拆分成多份每一份与其他特征竞争最优划分点都失败最终该特征得到的重要性会比实际值低。LightGBM 原生支持类别特征采用 many-vs-many 的切分方式将类别特征分为两个子集实现类别特征的最优切分。假设有某维特征有 k 个类别则有 2^{(k-1)} - 1 中可能时间复杂度为 O(2^k) LightGBM 基于 Fisher 大佬的 《On Grouping For Maximum Homogeneity》实现了 O(klog_2k) 的时间复杂度。上图为左边为基于 one-hot 编码进行分裂后图为 LightGBM 基于 many-vs-many 进行分裂在给定深度情况下后者能学出更好的模型。其基本思想在于每次分组时都会根据训练目标对类别特征进行分类根据其累积值 rac{sum gradient }{sum hessian} 对直方图进行排序然后在排序的直方图上找到最佳分割。此外LightGBM 还加了约束条件正则化防止过拟合。我们可以看到这种处理类别特征的方式使得 AUC 提高了 1.5 个点且时间仅仅多了 20%。2.2 工程实现2.2.1 特征并行传统的特征并行算法在于对数据进行垂直划分然后使用不同机器找到不同特征的最优分裂点基于通信整合得到最佳划分点然后基于通信告知其他机器划分结果。传统的特征并行方法有个很大的缺点需要告知每台机器最终划分结果增加了额外的复杂度(因为对数据进行垂直划分每台机器所含数据不同划分结果需要通过通信告知)。LightGBM 则不进行数据垂直划分每台机器都有训练集完整数据在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。2.2.2 数据并行传统的数据并行策略主要为水平划分数据然后本地构建直方图并整合成全局直方图最后在全局直方图中找出最佳划分点。这种数据划分有一个很大的缺点通讯开销过大。如果使用点对点通信一台机器的通讯开销大约为 O(#machine * #feature *#bin ) 如果使用集成的通信则通讯开销为 O(2 * #feature *#bin ) LightGBM 采用分散规约(Reduce scatter)的方式将直方图整合的任务分摊到不同机器上从而降低通信代价并通过直方图做差进一步降低不同机器间的通信。2.2.3 投票并行针对数据量特别大特征也特别多的情况下可以采用投票并行。投票并行主要针对数据并行时数据合并的通信代价比较大的瓶颈进行优化其通过投票的方式只合并部分特征的直方图从而达到降低通信量的目的。大致步骤为两步本地找出 Top K 特征并基于投票筛选出可能是最优分割点的特征合并时只合并每个机器选出来的特征。2.2.4 缓存优化上边说到 XGBoost 的预排序后的特征是通过索引给出的样本梯度的统计值因其索引访问的结果并不连续XGBoost 提出缓存访问优化算法进行改进。而 LightGBM 所使用直方图算法对 Cache 天生友好首先所有的特征都采用相同的方法获得梯度(区别于不同特征通过不同的索引获得梯度)只需要对梯度进行排序并可实现连续访问大大提高了缓存命中其次因为不需要存储特征到样本的索引降低了存储消耗而且也不存在 Cache Miss的问题。2.3 与 XGBoost 的对比本节主要总结下 LightGBM 相对于 XGBoost 的优点从内存和速度两方面进行介绍。2.3.1 内存更小XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引而 LightGBM 使用了直方图算法将特征值转变为 bin 值且不需要记录特征到样本的索引将空间复杂度从 O(2*#data) 降低为 O(#bin) 极大的减少了内存消耗LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值降低了内存消耗LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量降低了内存消耗。2.3.2 速度更快LightGBM 采用了直方图算法将遍历样本转变为遍历直方图极大的降低了时间复杂度LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本减少了大量的计算LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树减少了很多不必要的计算量LightGBM 采用优化后的特征并行、数据并行方法加速计算当数据量非常大的时候还可以采用投票并行的策略LightGBM 对缓存也进行了优化增加了 Cache hit 的命中率。参考文献XGBoost: A Scalable Tree Boosting System陈天奇论文演讲 PPT机器学习算法中 GBDT 和 XGBOOST 的区别有哪些- wepon的回答 - 知乎LightGBM: A Highly Efficient Gradient Boosting Decision TreeLightGBM 文档论文阅读——LightGBM 原理机器学习算法之 LightGBM关于sklearn中的决策树是否应该用one-hot编码- 柯国霖的回答 - 知乎如何玩转LightGBMA Communication-Efficient Parallel Algorithm for Decision Tree.—— 完 ——欢迎关注我们收获资源干货喜欢就点「在看」吧 !
