新吴区住房和建设交通局网站,普陀网站制作有哪些,淘宝推广方法有哪些,如何自己创建一个网址目录
1.LightGBM的直方图算法(Histogram)
直方图做差加速
2.LightGBM得两大先进技术(GOSSEFB)
2.1 单边梯度抽样算法(GOSS)
2.2 互斥特征捆绑算法(EFB)
3.LightGBM得生长策略(leaf-wise) 通过与xgboost对比#xff0c;在这里列出lgb新提出的几个方面的技术
1.Ligh…目录
1.LightGBM的直方图算法(Histogram)
直方图做差加速
2.LightGBM得两大先进技术(GOSSEFB)
2.1 单边梯度抽样算法(GOSS)
2.2 互斥特征捆绑算法(EFB)
3.LightGBM得生长策略(leaf-wise) 通过与xgboost对比在这里列出lgb新提出的几个方面的技术
1.LightGBM的直方图算法(Histogram)
LightGBM里面的直方图算法是为了减少分裂点的数量。
直方图就是把连续的浮点特征离散化为k个整数(也就是分桶bins的思想)比如[0,0.1)-0,[0.1,0.3)-1。并根据特征所在的bin对其进行梯度累加和个数统计在遍历数据的时候根据离散化后的值作为索引在直方图中累计统计量当遍历一次数据后直方图累积了需要的统计量当遍历一次数据后直方图累积了需要的统计量然后根据直方图的离散值遍历寻找最优的分割点。我们来形象化的画个图。 这样在遍历到该特征的时候只需要根据直方图的离散值遍历寻找最优的分割点即可由于bins的数量是远小于样本不同取值的数量的所以分桶之后要遍历的分裂点的个数会少了很多这样就可以减少计算量。基于上面的这个方式如果是把所有特征放到一块的话应该是下面的这种感觉 histogram算法还可以进一步加速。一个叶子节点的histogram可以直接由父节点的histogram和兄弟节点的histogram做差得到。一般情况下构造histogram需要遍历该叶子上的所有数据通过该方法只需要遍历histogram的k个桶。
直方图做差加速
当节点分裂成两个时右边的子节点的直方图其实等于父节点的直方图减去左边子节点的直方图 再举个例子形象化的理解 histogram算法并不是完美的。由于特征被离散化后找到的并不是很精确的分割点所以会对结果产生影响。但在实际的数据集上表明离散化的分裂点对最终的精度影响并不大甚至会好一些。原因在于decision tree本身就是一个弱学习器分割点是不是精确并不是太重要采用histogram算法会起到正则化的效果有效地防止模型的过拟合(bin数量决定了正则化的程度bin越少惩罚越严重欠拟合风险越高) 。
因为xgboost的近似分割算法也用了分桶这里和xgboost中的weight quantile sketch算法做一个比较xgboost考虑的是对loss的影响权值用的每个样本的hi来标识的相当于基于hi的分布去找候选分割点这样带来的一个问题就是每一层划分完了之后下一次依然需要构建这样的直方图毕竟样本被划分到了不同的节点中二阶导分布也就变了。所以xgboost在每一层都得动态构建直方图因为它这个直方图算法不是针对某个特定得feature得而是所有feature共享一个直方图(每个样本权重得二阶导)。而lightgbm对每个特征都有一个直方图这样构建一次就ok并且分裂得时候还能通过直方图进行加速。故xgboost得直方图算法是不如lightgbm得直方图算法快得。
2.LightGBM得两大先进技术(GOSSEFB)
接下来说lightgbm得两大先进技术(GOSSEFB)这两大技术是lightgbm相对于xgboost独有得分别是单边梯度抽样算法(GOSS)和互斥特征捆绑算法(EFB)GOSS可以减少样本得数量而EFB可以减少特征得数量这样就能降低模型分裂过程中得复杂度。
2.1 单边梯度抽样算法(GOSS)
goss通过减少样本数量去帮助lgb更快
单边梯度抽样算法(Gradient-based One-Side Sampling)是从减少样本得角度出发排除大部分权重小得样本仅用剩下得样本计算信息增益它是一种在减少数据和保证精度上平衡得算法。
但是这个时候就有个问题权重从哪来我们通过了解GBDT得原理可以知道在训练新模型得过程中梯度比较小得样本对于降低残差得作用效果不是太大所以我们可以关注梯度高得样本这样就可以减少计算量了。这里我们再记录下为啥梯度小得样本对降低残差效果不大。 可以看到梯度就是残差得一个相反数也就是 这个常数不用管这样也就是说如果我新得模型想降低残差得效果好那么样本得梯度应该越大越好所以这就是为啥梯度小得样本对于降低残差得效果不大。也是为啥样本得梯度大小可以反映样本权重得原因。
但是要是盲目得直接去掉这些梯度小得数据这样就会改变数据得分布了啊所以lgb才提出了单边梯度抽样算法根据样本得权重信息对样本进行抽样减少了大量梯度小得样本但是还能不会过多得改变数据集得分布。
GOSS算法保留了梯度大的样本并对梯度小得样本进行随机抽样为了不改变样本得数据分布再计算增益时为梯度小得样本引入了一个常数进行平衡。具体首先先根据样本得梯度对样本从大到小排序然后拿到前a%得梯度大得样本和剩下样本得b%再计算增益时后面得这b%通过乘上(1-a)/b来放大梯度小得样本得权重。一方面算法将更多得注意力放在训练不足得样本上另一方面通过乘上权重来防止采样对原始数据分布造成太大得影响。
我们来看一个具体得例子 通过上面我们就通过采样得方式选出了我们得样本两个梯度大得6号和7号然后又从剩下得样本里面随机选取了2个梯度小得4号和2号这时候我们看看goss算法怎么做 这里得Ni是样本数梯度小得样本乘上相应的权重之后我们再基于采样样本得估计直方图中可以返现Ni得总个数依然是8个虽然6个梯度小得样本中去掉了4个留下了两个。但是这2个样本再梯度上和个数上都进行了3倍数得方法所以可以防止采样对原始数据分布造成太大得影响。
2.2 互斥特征捆绑算法(EFB) EFB是从减少特征的角度去帮助lgb更快。
高维度得数据往往是稀疏得这种稀疏性启发我们设计一种无损得方法来减少特征的维度。通常被捆绑得特征都是互斥得这样两个特征捆绑起来才会丢失信息。如果两个特征并不是完全互斥(部分情况下两个特征都是非零值)可以用一个指标对特征不互斥程度进行衡量称之为冲突比率当这个值较小时我们可以选择把不完全互斥得两个特征捆绑而不影响最后得精度。
举一个很极端得例子。 可以看到每一个特征都只有一个训练样本时非0且都不是同一个训练样本这样的话特征之间也没有冲突了。这样得情况就可以把这四个特征捆绑成一个这样维度就减少了。
EFB指出如果将一些特征进行融合绑定则可以降低特征数量。这样再构建直方图得时候时间复杂度从O(#data*#feature)变成O(#data*#bundle)这里得#bundle指的是特征融合后特征包得个数且#bundle#feature。针对这个特征捆绑融合有两个问题需要解决。
怎么判断哪些特征应该绑在一起特征绑在一起之后特征值应该如何确定呢
对于问题一EFB算法利用特征和特征间得关系构造一个加权无向图并将其转换为图着色得问题来求解解释下就是这样得
1.首先将所有得特征看成图得各个顶点将不相互独立得特征用一条边连起来边得权重就是两个相连接得特征得总冲突值(也就是这两个特征上同时不为0得样本个数)。
2.然后按照节点得度对特征降序排序度越大说明与其他特征得冲突越大
3.对于每一个特征遍历已有得特征簇如果发现该特征加入到特征簇中得矛盾数不超过某一个阈值则将该特征加入到该簇中。如果该特征不能加入任何一个已有得特征簇则新建一个簇将该特征加入到新建得簇中。
具体可以看下面得例子 上面这个过程得时间复杂度其实是O(#features^2)得因为要遍历特征每个特征还要遍历所有得簇在特征不多得情况下还行但是如果特征维度很大就不好使了。所以为了改善效率可以不建立图而是将特征按照非零值个数进行排序因为更多得非零值得特征会导致更多得冲突所以跳过了上面得第一步直接排序然后第三步分簇。
对于问题二捆绑完了之后特征应该如何取值呢这里面得一个关键就是原始特征能从合并得特征中分离出来也就是绑定几个特征在同一个bundle里需要保证绑定前得原始特征得值可以在bundle里面进行识别考虑到直方图算法将连续得值保存为离散得bins我们可以是的不同特征得值分到簇中不同bins里面去这可以通过在特征值中加入一个偏置常数来解决。
比如我们把特征A和B绑定到了同一个bundle里面A特征得原始取值区间[0,10)B特征原始取值区间[0,20)这样如果直接绑定那么会发现我们从bundle里面取出了一个值5就分不出这个5到底是来自特征A还是B了。所以我们可以再B特征的取值上加一个常数10转换为[10,30),这样绑定好得特征取值就是[0,30)我如果再从bundle里面取出5就知道这个来自特征A。
从而有趣的是对于类别特征如果转换为onehot编码则这些onehot编码后得多个特征相互之间是互斥得从而可以被捆绑成为一个特征。因此对于指定为类别型得特征lgb可以直接将每个特征取值和一个bin关联从而自动得处理它们而需要预处理成onehot编码多此一举。
3.LightGBM得生长策略(leaf-wise)
我们整理了lgb是如何再寻找最优分裂点得过程中降低时间复杂度得我们说xgb再寻找最优分裂点得时间复杂度其实可以归到三个角度:特征得数量分裂点得数量和样本得数量。而lgb也提出了三种策略分别从这三个角度进行优化直方图算法是为了减少分裂点得数量goss算法为了减少样本得数量而efb算法为了减少特征得数量。
lgb除了在寻找最优分裂点过程中进行了优化其实在树得生长过程中也进行了优化它抛弃了xgb里面得按层生长(level-wise)而是使用了带有深度限制得按叶子生长(leaf-wise)。
xgb在树得生长过程中采用level-wise得增长策略该策略遍历一次数据可以同时分裂同一层得叶子容易进行多线程优化也好控制模型复杂度不容易过拟合。但实际上level-wise是一种低效得算法因为它不加区分得对待同一层得叶子实际上很多叶子得分裂增益较低没必要进行搜索和分裂因此带来了很多不必要得计算开销。 leaf-wise则是一种更为高效得策略每次从当前所有叶子中找到分裂增益最大得一个叶子然后分裂如此循环。因此同level-wise相比在分裂次数相同得情况下leaf-wise可以降低更多得误差得到更好得精度。leaf-wise得缺点是可能会长出比较深得决策树产生过拟合。因此lgb在leaf-wise之上增加了一个最大深度得限制在保证高效率得同时防止过拟合。 因此,level-wise得做法会产生一些低信息增益得节点浪费运算资源但是这个对防止过拟合挺有用。而leaf-wise能够追求更好得精度降低误差但是会带来过拟合问题其使用了max_depth来控制树得高度防止过拟合另外直方图和goss得各个操作本身都有天然正则化得作用。
最后还有lgb得工程优化看下面这个链接
https://zhongqiang.blog.csdn.net/article/details/105350579
lightGBM - 知乎
在这里提一下lighgbm是第一个直接支持类别特征的GBDT工具。
