<commit_before>---
layout: post
title: XGBoost解读(1)--原理
categories:
- datamining
tags:
- GBDT
- XGBoost
image:
    teaser: /datamining/xgboost_fig/xgboost_logo.png
---

#### 1 集成学习
科学研究中，有种方法叫做组合，甚是强大，小硕们毕业基本靠它了。将别人的方法一起组合起来然后搞成一个集成的算法，集百家之长，效果一般不会差。其实也不能怪小硕们，大牛们也有这么做的，只是大牛们做的比较漂亮。

在PAC学习框架下（Probably Approximately Correct）, Kearns和Valiant指出，若存在一个多项式级的学习算法来识别一组概念，并且识别正确率很高，那么这组概念是强可学习的；而如果学习算法识别一组概念的正确率仅比随机猜测略好，那么这组概念是弱可学习的。Schapire证明了弱学习算法与强学习算法的等价性问题，这样在学习概念时，只要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。这为集成学习提供了理论支持。

在众多单模型中（与集成模型相对应），决策树这种算法有着很多良好的特性，比如说训练时间复杂度较低，预测的过程比较快速，模型可解释强等。但是同时，单决策树又有一些不好的地方，比如说容易over-fitting，虽然有一些方法，如剪枝可以减少这种情况，但是还是不够的。

集成学习还是有很多方法的，在这里只介绍两种普遍做法：bagging集成和boosting集成。bagging集成，例如随机森林，对样本随机抽样建立很多树，每棵树之间没有关联，这些树组成森林，构成随机森林模型。boosting集成后一个模型是对前一个模型产生误差的矫正。gradient boost更具体，是指每个新模型的引入是为了减少上个模型的残差(residual)，而为了消除残差，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。如果基础模型是决策树，那么这样的模型就被称为Gradient Boost Decision Tree（GBDT）

#### 2 XGBoost
GBDT可以看做是个框架，最早的一种实现方法由Friedman 在论文GREEDY FUNCTION APPROXIMATION: A GRADIENT BOOSTING MACHINE 。xgboost（Extreme Gradient Boosting）是最近提出的一个新的GBDT实现，由陈天奇提出，在Kaggle、KDD Cup等数据挖掘比赛中大方异彩，成为冠军队伍的标配，另外很多大公司，如腾讯、阿里、美团已在公司里面部署。XGBoost有如下优点:

* 显示的把树模型复杂度作为正则项加到优化目标中。
* 公式推导中用到了二阶导数，用了二阶泰勒展开。
* 实现了分裂点寻找近似算法。
* 利用了特征的稀疏性。
* 数据事先排序并且以block形式存储，有利于并行计算。
* 基于分布式通信框架rabit，可以运行在MPI和yarn上。
* 实现做了面向体系结构的优化，针对cache和内存做了性能优化。

#### 3 监督学习要素
XGBoost应用于监督学习问题，使用训练数据(有很多特征)$x_i$来预测目标$y_i$。 监督学习的三要素：模型、参数和目标函数

##### 3.1 模型
模型指给定输入$x_i$如何去预测输出$y_i$。我们比较常见的模型如线性模型（包括线性回归和logistic regression）采用了线性叠加的方式进行预测$\hat{y}_i=\sum_j x_{j}$. 其实这里的预测$y$可以有不同的解释，比如我们可以用它来作为回归目标的输出，或者进行sigmoid 变换得到概率，或者作为排序的指标等。而一个线性模型根据$y$的解释不同（以及设计对应的目标函数）用到回归，分类或排序等场景。<commit_msg>modify latex<commit_after>---
layout: post
title: XGBoost解读(1)--原理
categories:
- datamining
tags:
- GBDT
- XGBoost
image:
    teaser: /datamining/xgboost_fig/xgboost_logo.png
---

#### 1 集成学习
科学研究中，有种方法叫做组合，甚是强大，小硕们毕业基本靠它了。将别人的方法一起组合起来然后搞成一个集成的算法，集百家之长，效果一般不会差。其实也不能怪小硕们，大牛们也有这么做的，只是大牛们做的比较漂亮。

在PAC学习框架下（Probably Approximately Correct）, Kearns和Valiant指出，若存在一个多项式级的学习算法来识别一组概念，并且识别正确率很高，那么这组概念是强可学习的；而如果学习算法识别一组概念的正确率仅比随机猜测略好，那么这组概念是弱可学习的。Schapire证明了弱学习算法与强学习算法的等价性问题，这样在学习概念时，只要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。这为集成学习提供了理论支持。

在众多单模型中（与集成模型相对应），决策树这种算法有着很多良好的特性，比如说训练时间复杂度较低，预测的过程比较快速，模型可解释强等。但是同时，单决策树又有一些不好的地方，比如说容易over-fitting，虽然有一些方法，如剪枝可以减少这种情况，但是还是不够的。

集成学习还是有很多方法的，在这里只介绍两种普遍做法：bagging集成和boosting集成。bagging集成，例如随机森林，对样本随机抽样建立很多树，每棵树之间没有关联，这些树组成森林，构成随机森林模型。boosting集成后一个模型是对前一个模型产生误差的矫正。gradient boost更具体，是指每个新模型的引入是为了减少上个模型的残差(residual)，而为了消除残差，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。如果基础模型是决策树，那么这样的模型就被称为Gradient Boost Decision Tree（GBDT）

#### 2 XGBoost
GBDT可以看做是个框架，最早的一种实现方法由Friedman 在论文GREEDY FUNCTION APPROXIMATION: A GRADIENT BOOSTING MACHINE 。xgboost（Extreme Gradient Boosting）是最近提出的一个新的GBDT实现，由陈天奇提出，在Kaggle、KDD Cup等数据挖掘比赛中大方异彩，成为冠军队伍的标配，另外很多大公司，如腾讯、阿里、美团已在公司里面部署。XGBoost有如下优点:

* 显示的把树模型复杂度作为正则项加到优化目标中。
* 公式推导中用到了二阶导数，用了二阶泰勒展开。
* 实现了分裂点寻找近似算法。
* 利用了特征的稀疏性。
* 数据事先排序并且以block形式存储，有利于并行计算。
* 基于分布式通信框架rabit，可以运行在MPI和yarn上。
* 实现做了面向体系结构的优化，针对cache和内存做了性能优化。

#### 3 监督学习要素
XGBoost应用于监督学习问题，使用训练数据(有很多特征)$x_i$来预测目标$y_i$。 监督学习的三要素：模型、参数和目标函数

##### 3.1 模型
模型指给定输入$x_i$如何去预测输出$y_i$。我们比较常见的模型如线性模型（包括线性回归和logistic regression）采用了线性叠加的方式进行预测$\hat{y}_i=\sum_j x_ij$. 其实这里的预测$y$可以有不同的解释，比如我们可以用它来作为回归目标的输出，或者进行sigmoid 变换得到概率，或者作为排序的指标等。而一个线性模型根据$y$的解释不同（以及设计对应的目标函数）用到回归，分类或排序等场景。
{'fraction_non_alphanumeric': 0.10251903925014645, 'fraction_numerical': 0.0035149384885764497, 'mean_word_length': 15.261904761904763, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3858311', 'n_tokens_mistral': 2802, 'n_tokens_neox': 3214, 'n_words': 116}