1、LOGOGradient Boosting Decision Tree And Its Application班班级级：*学学生：生：*学号学号：*报告大纲报告大纲第一部分：引言（概念介绍）第一部分：引言（概念介绍） 决策树 boosting方法 损失函数 GBDT定义 第二部分：第二部分：GBDT算法原理算法原理 加法模型 前向分步算法 提升树算法 梯度提升树算法 Regularization第三部分：第三部分：GBDT应用应用 应用范围 实例：CTR预估 GBDT特征转换LR+GBDT第四部分：总结第四部分：总结第一部分：概念介绍第一部分：概念介绍决策树boost方法损失函数GBDT定义
2、第一部分：概念介绍第一部分：概念介绍决策树：决策树：是将空间用超平面进行划分的一种方法是将空间用超平面进行划分的一种方法分类树回归树单决策树时间复杂度较低，模型容易展示，但容易over-fitting决策树的决策树的boost方法：方法：是一个迭代的过程，每一次新是一个迭代的过程，每一次新的训练都是为了改进上一次的结果的训练都是为了改进上一次的结果.传统传统Boost：对正确、错误的样本进行加权，每一步结：对正确、错误的样本进行加权，每一步结束后，增加分错的点的权重，减少分对的点的权重。束后，增加分错的点的权重，减少分对的点的权重。GB：梯度迭代：梯度迭代 Gradient Boosting，
3、每一次建立模型，每一次建立模型是在之前建立的模型损失函数的梯度下降方向是在之前建立的模型损失函数的梯度下降方向第一部分：概念介绍第一部分：概念介绍 损失函数损失函数(loss function)： 描述的是模型的不靠描述的是模型的不靠谱程度，损失函数越大，则说明模型越容易出错。谱程度，损失函数越大，则说明模型越容易出错。对于不同的对于不同的Loss function，其梯度有不同的表达，其梯度有不同的表达式：式：第一部分：概念介绍第一部分：概念介绍GBDT(Gradient Boosting Decision Tree) ：是：是一种迭代的决策树算法，该算法由多棵决策树组一种迭代的决策树算法，
4、该算法由多棵决策树组成，所有树的结论累加起来做最终结果。成，所有树的结论累加起来做最终结果。GBDT这个算法还有一些其他的名字，这个算法还有一些其他的名字，MART(Multiple Additive Regression Tree)，GBRT(Gradient Boost Regression Tree)，Tree Net，Treelink等。等。第二部分：第二部分：GBDT算法原理算法原理加法模型前向分步算法提升树算法梯度提升树算法Regularization 第二部分：第二部分：GBDT算法原理算法原理提升树利用加法模型与前向分布算法实现学习的优提升树利用加法模型与前向分布算法实现学习的
5、优化过程。化过程。第二部分：第二部分：GBDT算法原理算法原理前向分布算法前向分布算法第二部分：第二部分：GBDT算法原理算法原理对于决策树，可以表示为：对于决策树，可以表示为：其中参数 表示树的区域划分和各区域上的常数回归问题提升树使用以下前向分步算法回归问题提升树使用以下前向分步算法所以，对于回归问题的提升树算法，所以，对于回归问题的提升树算法， 只需简单拟合当前模型的残差。只需简单拟合当前模型的残差。 第二部分：第二部分：GBDT算法原理算法原理 第二部分：第二部分：GBDT算法原理算法原理当损失函数是平方损失和指数损失函数时，每一步优化是当损失函数是平方损失和指数损失函数时，每一步优化
6、是简单的，但对一般损失函数而言，并不简单。简单的，但对一般损失函数而言，并不简单。Freidman提提出了出了Gradient Boosting算法，利用最速下降法的近似方法，算法，利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值其关键是利用损失函数的负梯度在当前模型的值 作为回归问题提升树算法中的残差的近似值，拟合一个回作为回归问题提升树算法中的残差的近似值，拟合一个回 归树。归树。Stochastic Gradient Boosting 当N很大的时候，非常耗费时间，这时我们可以从中随机选取一些数据来拟合。 第二部分：算法原理第二部分：算法原理第二部分：第二部分：GBD
7、T算法原理算法原理Regularization cross validation Shrinkage参数v(0v1)可以认为是boosting方法的学习速率。如果使用很小的v，要达到相当的训练误差，就需要使用较大的M。反之亦然。在通常情况下，较小的v在独立测试集上的 performance更加好，但是这时需要较大的M，比较耗时。 Subsampling使用前面提到的stochastic gradient boosting不仅减少了训练时间，同样可以起到bagging的效果，因为每次随机抽样减小了overfitting的机会。第三部分：第三部分：GBDT应用应用 应用范围 实例：CTR预估LR
8、GBDT特征转换LR+GBDT 第三部分：第三部分：GBDT应用应用应用范围应用范围GBDT几乎可用于所有回归问题（线性几乎可用于所有回归问题（线性/非线性）非线性）亦可用于二分类问题（设定阈值，大于阈值为正亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）；不太适合做多分类问题；例，反之为负例）；不太适合做多分类问题；排序问题；排序问题；常用于各大数据挖掘竞赛（模型融合）；常用于各大数据挖掘竞赛（模型融合）；广告推荐广告推荐第三部分：第三部分：GBDT应用应用CTR预估：广告点击率（预估：广告点击率（Click-Through Rate Prediction）CTR预估中用的最多的模
9、型是预估中用的最多的模型是LR（Logistic Regression），），LR是广义线性模型，与传统线性是广义线性模型，与传统线性模型相比，模型相比，LR使用了使用了Logit变换将函数值映射到变换将函数值映射到01区间区间 ，映射后的函数值就是，映射后的函数值就是CTR的预估值。的预估值。LR，逻辑回归模型，这种线性模型很容易并行化，逻辑回归模型，这种线性模型很容易并行化，处理上亿条训练样本不是问题，但线性模型学习处理上亿条训练样本不是问题，但线性模型学习能力有限，需要大量特征工程预先分析出有效的能力有限，需要大量特征工程预先分析出有效的特征、特征组合，从而去间接增强特征、特征组合，从而
10、去间接增强LR 的非线性学的非线性学习能力。习能力。第三部分：第三部分：GBDT应用应用 LR模型中的特征组合很关键，但又无法直接通模型中的特征组合很关键，但又无法直接通过特征笛卡尔积解决，只能依靠人工经验，耗时过特征笛卡尔积解决，只能依靠人工经验，耗时耗力同时并不一定会带来效果提升。如何自动发耗力同时并不一定会带来效果提升。如何自动发现有效的特征、特征组合，弥补人工经验不足，现有效的特征、特征组合，弥补人工经验不足，缩短缩短LR特征实验周期，是亟需解决的问题特征实验周期，是亟需解决的问题 Facebook 2014年的文章介绍了通过年的文章介绍了通过GBDT （Gradient Boost
11、Decision Tree）解决）解决LR的的特征组合问题，随后特征组合问题，随后Kaggle竞赛也有实践此思竞赛也有实践此思路路GDBT+FM，GBDT与与LR融合开始引起了业界融合开始引起了业界关注关注第三部分：第三部分：GBDT应用应用 GBDT+LR GBDT的思想使其具有天然优势，可以发现多种的思想使其具有天然优势，可以发现多种有区分性的特征以及特征组合，决策树的路径可有区分性的特征以及特征组合，决策树的路径可以直接作为以直接作为LR输入特征使用，省去了人工寻找输入特征使用，省去了人工寻找特征、特征组合的步骤。特征、特征组合的步骤。第三部分：第三部分：GBDT应用应用由于树的每条路径
12、，由于树的每条路径，是通过最小化是通过最小化均方差等方法均方差等方法最终分割出来最终分割出来的有区分性路的有区分性路径，根据该路径，根据该路径得到的特征、径得到的特征、特征组合都相特征组合都相对有区分性，对有区分性，效果理论上不效果理论上不会亚于人工经会亚于人工经验的处理方式。验的处理方式。第三部分：第三部分：GBDT应用应用 实验实验 Kaggle比赛比赛:Display Advertising Challenge详细介绍：详细介绍：实验过程：实验过程：(比赛第一名：比赛第一名：GBDT+FM)参考：参考：（Xgboost：/xgboost）实验结果：尚未完成，报告加上实验结果：尚未完成，报
13、告加上第四部分：总结第四部分：总结 总结总结 展望展望 References 统计学习方法统计学习方法 Friedman J H. Greedy function approximation: a gradient boosting machineJ. Annals of statistics, 2001: 1189-1232. Friedman J H. Stochastic gradient boostingJ. Computational Statistics & Data Analysis, 2002, 38(4): 367-378. He X, Pan J, Jin O, et al
14、. Practical Lessons from Predicting Clicks on Ads at FacebookC/ Eighth International Workshop on Data Mining for Online Advertising. ACM, 2014:1-9. Yuan T T, Chen Z, Mathieson M. Predicting eBay listing conversionC/Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. ACM, 2011: 1335-1336. Tyree S, Weinberger K Q, Agrawal K, et al. Parallel boosted regression trees for web search rankingC/Proceedings of the 20th international conference on World wide web. ACM, 2011: 387-396. Kaggle-2014-criteo /xgboost
