GBDT算法及其应用

LOGOGradientBoostingDecisionTreeAndItsApplication班级：**学生：**学号：**报告大纲第一部分：引言（概念介绍）决策树boosting方法损失函数GBDT定义第二部分：GBDT算法原理加法模型前向分步算法提升树算法梯度提升树算法Regularization第三部分：GBDT应用应用范围实例：CTR预估GBDT特征转换LR+GBDT第四部分：总结第一部分：概念介绍决策树boost方法损失函数GBDT定义第一部分：概念介绍决策树：是将空间用超平面进行划分的一种方法分类树回归树单决策树时间复杂度较低，模型容易展示，但容易over-fitting决策树的boost方法：是一个迭代的过程，每一次新的训练都是为了改进上一次的结果.传统Boost：对正确、错误的样本进行加权，每一步结束后，增加分错的点的权重，减少分对的点的权重。GB：梯度迭代GradientBoosting，每一次建立模型是在之前建立的模型损失函数的梯度下降方向第一部分：概念介绍损失函数(lossfunction)：描述的是模型的不靠谱程度，损失函数越大，则说明模型越容易出错。对于不同的Lossfunction，其梯度有不同的表达式：第一部分：概念介绍GBDT(GradientBoostingDecisionTree)：是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终结果。GBDT这个算法还有一些其他的名字，MART(MultipleAdditiveRegressionTree)，GBRT(GradientBoostRegressionTree)，TreeNet，Treelink等。第二部分：GBDT算法原理加法模型前向分步算法提升树算法梯度提升树算法Regularization第二部分：GBDT算法原理提升树利用加法模型与前向分布算法实现学习的优化过程。第二部分：GBDT算法原理前向分布算法第二部分：GBDT算法原理对于决策树，可以表示为：其中参数表示树的区域划分和各区域上的常数回归问题提升树使用以下前向分步算法所以，对于回归问题的提升树算法，只需简单拟合当前模型的残差。第二部分：GBDT算法原理第二部分：GBDT算法原理当损失函数是平方损失和指数损失函数时，每一步优化是简单的，但对一般损失函数而言，并不简单。Freidman提出了GradientBoosting算法，利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。StochasticGradientBoosting当N很大的时候，非常耗费时间，这时我们可以从中随机选取一些数据来拟合。第二部分：算法原理第二部分：GBDT算法原理RegularizationcrossvalidationShrinkage参数v(0v1)可以认为是boosting方法的学习速率。如果使用很小的v，要达到相当的训练误差，就需要使用较大的M。反之亦然。在通常情况下，较小的v在独立测试集上的performance更加好，但是这时需要较大的M，比较耗时。Subsampling使用前面提到的stochasticgradientboosting不仅减少了训练时间，同样可以起到bagging的效果，因为每次随机抽样减小了overfitting的机会。第三部分：GBDT应用应用范围实例：CTR预估LRGBDT特征转换LR+GBDT第三部分：GBDT应用应用范围GBDT几乎可用于所有回归问题（线性/非线性）亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）；不太适合做多分类问题；排序问题；常用于各大数据挖掘竞赛（模型融合）；广告推荐第三部分：GBDT应用CTR预估：广告点击率（Click-ThroughRatePrediction）CTR预估中用的最多的模型是LR（LogisticRegression），LR是广义线性模型，与传统线性模型相比，LR使用了Logit变换将函数值映射到0~1区间，映射后的函数值就是CTR的预估值。LR，逻辑回归模型，这种线性模型很容易并行化，处理上亿条训练样本不是问题，但线性模型学习能力有限，需要大量特征工程预先分析出有效的特征、特征组合，从而去间接增强LR的非线性学习能力。第三部分：GBDT应用LR模型中的特征组合很关键，但又无法直接通过特征笛卡尔积解决，只能依靠人工经验，耗时耗力同时并不一定会带来效果提升。如何自动发现有效的特征、特征组合，弥补人工经验不足，缩短LR特征实验周期，是亟需解决的问题Facebook2014年的文章介绍了通过GBDT（GradientBoostDecisionTree）解决LR的特征组合问题，随后Kaggle竞赛也有实践此思路GDBT+FM，GBDT与LR融合开始引起了业界关注第三部分：GBDT应用GBDT+LRGBDT的思想使其具有天然优势，可以发现多种有区分性的特征以及特征组合，决策树的路径可以直接作为LR输入特征使用，省去了人工寻找特征、特征组合的步骤。第三部分：GBDT应用由于树的每条路径，是通过最小化均方差等方法最终分割出来的有区分性路径，根据该路径得到的特征、特征组合都相对有区分性，效果理论上不会亚于人工经验的处理方式。第三部分：GBDT应用实验Kaggle比赛:DisplayAdvertisingChallenge详细介绍：实验过程：(比赛第一名：GBDT+FM)参考：（Xgboost：）实验结果：尚未完成，报告加上第四部分：总结总结展望References《统计学习方法》FriedmanJH.Greedyfunctionapproximation:agradientboostingmachine[J].Annalsofstatistics,2001:1189-1232.FriedmanJH.Stochasticgradientboosting[J].ComputationalStatistics&DataAnalysis,2002,38(4):367-378.HeX,PanJ,JinO,etal.PracticalLessonsfromPredictingClicksonAdsatFacebook[C]//EighthInternationalWorkshoponDataMiningforOnlineAdvertising.ACM,2014:1-9.YuanTT,ChenZ,MathiesonM.PredictingeBaylistingconversion[C]//Proceedingsofthe34thinternationalACMSIGIRconferenceonResearchanddevelopmentinInformationRetrieval.ACM,2011:1335-1336.TyreeS,WeinbergerKQ,AgrawalK,etal.Parallelboostedregressiontreesforwebsearchranking[C]//Proceedingsofthe20thinternationalconferenceonWorldwideweb.ACM,2011:387-396.:Thankyou!ina.com.cn/iwps/