gbdt原理(非常重要)

GBDT算法原理简介[e-mail]2017年7月14日内容•泰勒公式•最优化方法•梯度下降法（Gradientdescendmethod）•牛顿法（Newton’smethod)•从参数空间到函数空间•从Gradientdescend到Gradientboosting•从Newton’smethod到NewtonBoosting•GradientBoostingTree算法原理•NewtonBoostingTree算法原理：详解XGBoost•更高效的工具包LightGBM•参考文献泰勒公式•定义：泰勒公式是一个用函数在某点的信息描述其附近取值的公式。局部有效性泰勒公式•定义：泰勒公式是一个用函数在某点的信息描述其附近取值的公式。局部有效性•基本形式：•一阶泰勒展开：•二阶泰勒展开：𝑓(𝑥)=𝑛=0∞𝑓𝑛(𝑥0𝑛!𝑥−𝑥0𝑛)𝑓(𝑥)≈𝑓(𝑥0)+𝑓′(𝑥0)(𝑥−𝑥0𝑓(𝑥)≈𝑓(𝑥0)+𝑓′(𝑥0)(𝑥−𝑥0)+𝑓′′(𝑥0)𝑥−𝑥022泰勒公式•定义：泰勒公式是一个用函数在某点的信息描述其附近取值的公式。局部有效性•基本形式：•一阶泰勒展开：•二阶泰勒展开：•迭代形式：假设，将在𝑥𝑡−1处进行泰勒展开𝑓(𝑥)=𝑛=0∞𝑓𝑛(𝑥0𝑛!𝑥−𝑥0𝑛)𝑓(𝑥)≈𝑓(𝑥0)+𝑓′(𝑥0)(𝑥−𝑥0𝑓(𝑥)≈𝑓(𝑥0)+𝑓′(𝑥0)(𝑥−𝑥0)+𝑓′′(𝑥0)𝑥−𝑥022𝑥𝑡=𝑥𝑡−1+𝛥𝑥𝑓𝑥𝑡𝑓𝑥𝑡=𝑓𝑥𝑡−1+𝛥𝑥≈𝑓𝑥𝑡−1+𝑓′𝑥𝑡−1𝛥𝑥+𝑓′′𝑥𝑡−1𝛥𝑥22梯度下降法（GradientDescendMethod）在机器学习任务中，需要最小化损失函数，其中是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选取初值，不断迭代，更新的值，进行损失函数的极小化。𝐿𝜃𝜃𝜃0𝜃梯度下降法（GradientDescendMethod）在机器学习任务中，需要最小化损失函数，其中是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选取初值，不断迭代，更新的值，进行损失函数的极小化。•迭代公式：𝐿𝜃𝜃𝜃0𝜃1tt梯度下降法（GradientDescendMethod）在机器学习任务中，需要最小化损失函数，其中是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选取初值，不断迭代，更新的值，进行损失函数的极小化。•迭代公式：•将在处进行一阶泰勒展开：𝐿𝜃𝜃𝜃0𝜃1tttL1t11'1ttttLLLL梯度下降法（GradientDescendMethod）在机器学习任务中，需要最小化损失函数，其中是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选取初值，不断迭代，更新的值，进行损失函数的极小化。•迭代公式：•将在处进行一阶泰勒展开：•要使得，可取：，则：𝐿𝜃𝜃𝜃0𝜃1tttL1t11'1ttttLLLL1ttLL'1tL1'1tttL梯度下降法（GradientDescendMethod）在机器学习任务中，需要最小化损失函数，其中是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选取初值，不断迭代，更新的值，进行损失函数的极小化。•迭代公式：•将在处进行一阶泰勒展开：•要使得，可取：，则：这里是步长，可通过linesearch确定，但一般直接赋一个小的数。𝐿𝜃𝜃𝜃0𝜃1tttL1t11'1ttttLLLL1ttLL'1tL1'1tttL牛顿法（Newton’sMethod）•将在处进行二阶泰勒展开：tL1t21'1''12ttttLLLL牛顿法（Newton’sMethod）•将在处进行二阶泰勒展开：为了简化分析过程，假设参数是标量（即只有一维），则可将一阶和二阶导数分别记为g和h：tL1t21'1''12ttttLLLL212ttLLgh牛顿法（Newton’sMethod）•将在处进行二阶泰勒展开：为了简化分析过程，假设参数是标量（即只有一维），则可将一阶和二阶导数分别记为g和h：•要使得极小，即让极小，可令：求得，故tL1t21'1''12ttttLLLL212ttLLghtL22gh220ghgh11tttgh牛顿法（Newton’sMethod）•将在处进行二阶泰勒展开：为了简化分析过程，假设参数是标量（即只有一维），则可将一阶和二阶导数分别记为g和h：•要使得极小，即让极小，可令：求得，故参数推广到向量形式，迭代公式：这里H是海森矩阵tL1t21'1''12ttttLLLL212ttLLghtL22gh220ghgh11tttgh11ttHg从参数空间到函数空间•GBDT在函数空间中利用梯度下降法进行优化•XGBoost在函数空间中用牛顿法进行优化注：实际上GBDT泛指所有梯度提升树算法，包括XGBoost，它也是GBDT的一种变种，这里为了区分它们，GBDT特指“GreedyFunctionApproximation：AGradientBoostingMachine”里提出的算法，它只用了一阶导数信息。从GradientDescend到GradientBoosting参数空间1ttt第t次迭代后的参数第t-1次迭代后的参数第t次迭代的参数增量tttg参数更新方向为负梯度方向0Ttt最终参数等于每次迭代的增量的累加和，为初值0从GradientDescend到GradientBoosting参数空间函数空间1ttt第t次迭代后的参数第t-1次迭代后的参数第t次迭代的参数增量tttg参数更新方向为负梯度方向0Ttt最终参数等于每次迭代的增量的累加和，为初值01tttfxfxfx第t次迭代后的函数第t-1次迭代后的函数第t次迭代的函数增量tttfxgx0TttFxfx最终函数等于每次迭代的增量的累加和，为模型初始值，通常为常数0fx同样地，拟合负梯度从Newton’sMethod到NewtonBoosting参数空间函数空间1ttt第t次迭代后的参数第t-1次迭代后的参数第t次迭代的参数增量1tttHg0Ttt最终参数等于每次迭代的增量的累加和，为初值01tttfxfxfx第t次迭代后的函数第t-1次迭代后的函数第t次迭代的函数增量tttgxfxhx0TttFxfx最终函数等于每次迭代的增量的累加和，为模型初始值，通常为常数0fx与梯度下降法唯一不同的就是参数增量小结•Boosting算法是一种加法模型（additivetraining）0TttFxfx小结•Boosting算法是一种加法模型（additivetraining）•基分类器常采用回归树[Friedman1999]和逻辑回归[Friedman2000]。下文以回归树展开介绍。树模型有以下优缺点：•可解释性强•可处理混合类型特征•具体伸缩不变性（不用归一化特征）•有特征组合的作用•可自然地处理缺失值•对异常点鲁棒•有特征选择作用•可扩展性强，容易并行0TttFxfxf•缺乏平滑性（回归预测时输出值只能输出有限的若干种数值）•不适合处理高维稀疏数据GradientBoostingTree算法原理•Friedman于论文”GreedyFunctionApproximation…”中最早提出GBDTGradientBoostingTree算法原理•Friedman于论文”GreedyFunctionApproximation…”中最早提出GBDT•其模型F定义为加法模型：其中，x为输入样本，h为分类回归树，w是分类回归树的参数，是每棵树的权重。00;;;TTtttttttFxwhxwfxwGradientBoostingTree算法原理•Friedman于论文”GreedyFunctionApproximation…”中最早提出GBDT•其模型F定义为加法模型：其中，x为输入样本，h为分类回归树，w是分类回归树的参数，是每棵树的权重。•通过最小化损失函数求解最优模型：NP难问题-通过贪心法，迭代求局部最优解00;;;TTtttttttFxwhxwfxw*0argmin,;NiiFiFLyFxwGradientBoostingTree算法原理输入：1.初始化2.fort=1toTdo2.1计算响应：2.2学习第t棵树：2.3linesearch找步长：2.4令更新模型：3.输出,,,iixyTL0f1,,1,2,...iiiitFxFxLyFxyiNFx2*1argmin;Nitiwiwyhxw**11argmin,();NititiiLyFxhxw**(;)ttfhxw1tttFFfTFGradientBoostingTree算法原理输入：1.初始化2.fort=1toTdo2.1计算响应：2.2学习第t棵树：2.3linesearch找步长：2.4令更新模型：3.输出,,,iixyTL0f1,,1,2,...iiiitFxFxLyFxyiNFx2*1argmin;Nitiwiwyhxw**11argmin,();NititiiLyFxhxw**(;)ttfhxw1tttFFfTFGradientBoostingTree算法原理输入：1.初始化2.fort=1toTdo2.1计算响应：2.2学习第t棵树：2.3linesearch找步长：2.4令更新模型：3.输出,,,iixyTL0f1,,1,2,...iiiitFxFxLyFxyiNFx2*1argmin;Nitiwiwyhxw**11argmin,();NititiiLyFxhxw**(;)ttfhxw1tttFFfTFGradientBoostingTree算法原理输入：1.初始化2.fort=1toTdo2.1计算响应：2.2学习第t棵树：2.3linesearch找步长：2.4令更新模型：3.输出,,,iixyTL0f1,,1,2,...iiiitFxFxLyFxyiNFx2*1argmin;Nitiwiwyhxw**11arg