大数据,机器学习,人工智能机器学习与数据挖掘程序员

一文掌握XGBoost核心原理

2019-04-09  本文已影响9人  心智万花筒

XGBoost是经典的提升树学习框架,其配套论文和PPT分享也相当经典,本文简单梳理其思路,原文见XGBoost原理简介

整体思路

和一般提升模型一样,提升树模型也遵循相同的范式

同时要考虑过拟合等问题「overfitting is everywhere」。

Tree Ensemble

遵循李航老师统计学习三要素公式

方法=模型+策略+算法

假设空间「模型」

Tree Ensemble基本思想是将多棵树的结果融合作为最终输出,示意图如下

paper-xgboost-tree-ensemble

不难看出,模型的假设空间是一系列CART树的集成,输出为

\hat y_i = \sum_{k=1}^{K} f_k(x_i), \quad f_k \in F

其模型参数为K颗树

\circleddash = \{f_1, f_2, \dots, f_K\}

目标函数「策略」

模型假设有了,另一个核心元素就是目标函数,和一般监督模型一样

Obj(\circleddash)=L(\circleddash)+\Omega(\circleddash)

目标函数分两部分「Bias-variance tradeoff is everywhere

具体到Tree Ensemble,其目标函数为

Obj = \sum_{i=1}^{n} l(y_i, \hat y_i) + \sum_{k=1}^{K}\Omega(f_k)

优化求解「算法」

模型参数的最终求解。参数\circleddash = \{f_1, f_2, \dots, f_K\}K颗树,无法用SGD类似方法优化求解,因为不是R^d空间上的数值向量。一般采用Additive Training(Boosting)的思想求解。

Gradient Boosting

Tree Ensemble章节回答了what we are learning的问题,Gradient Boosting章节要回答how do we learn的问题。

Additive Traing范式

采用Additive Training(Boosting)的模式,即每一轮学习一颗新树f_t

paper-xgboost-boosting
学习一颗新树

问题是每一轮\hat y_i^{(t)} = \hat y_i^{(t-1)} + f_t(x_i)中,f_t如何学习?

Define objective(loss, regularization) and optimize it.

在第t轮,树的每一次生长,确定选那个特征分裂/分裂点取在哪里即可。其依据是使Objective最小,这里涉及两点,即w\in R^T取何值Objective最小,以及Objective最小值表达式是什么。

定义Objective及其近似

Objective是w的一般函数,其最小值一般表达式并不完全确定「not general」。XGBoost对其进行二阶泰勒展开近似,推导变换后Objective可形式化为T个独立的二项式,表达式可统一「只需Objective一阶二阶可导即可」。

以下简单梳理推导核心步骤。

paper-xgboost-taylor-expansion

其中每次迭代f_t(x)视为\Delta x泰勒近似展开,用一阶二阶导表示。对应到Square Loss后理解会更直观一些,一阶导正比于残差,二阶导为常数。

经过简化,现在Objective为

Obj^{(t)} = \sum_{i=1}^{n}[g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t)

此时学习只依赖loss function一阶二阶导,理论理解和工程实现都简洁不少。

The learning of function only depend on the objective via g_i and h_i.

确定Objective最小值

为方便推导,需要一些符号表示上的辅助

paper-xgboost-regularization

不难推导如下式子

\begin{align} Obj^{(t)} &\approx \sum_{i=1}^{n} [g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t) \\ &= \sum_{i=1}^{n} [g_iw_{q(x_i)} + \frac{1}{2}h_iw_{w_{q(x_i)}}^2] + \gamma T + \lambda\frac{1}{2}\sum_{j=1}^{T}w_j^2 \\ &= \sum_{j=1}^{T} [(\sum_{i\in I_j}g_j)w_j + \frac{1}{2}(\sum_{i\in I_j}h_j)w_j^2 + \lambda] + \gamma T \\ &= \sum_{j=1}^{T} [G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2] + \gamma T \end{align}

对上述四个式子几点解释

对二项式y = ax^2 + bx + c,在x=-\frac{b}{2a}取极值y=\frac{4ac-b^2}{4a}。不难得出w^*取值为

w_j^* = -\frac{G_j}{H_j + \lambda}

时,Obj有以下最小值

Obj = -\frac{1}{2}\sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T

最小值中包含两项,第一项表示树拟合好坏,第二项表示树的复杂度。如此,即可根据gain选择分裂特征和分裂点了。

Gain = \frac{1}{2}\big[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L + H_R + \lambda}\big] - \gamma

一点验证

当模型为GBDT,Loss选为Square Loss,不加正则项,其结论应该跟上述推导完全一致。Square Loss

l(y_i, \hat y_i^{(t-1)}) = \frac{1}{2}(y_i - \hat y_i^{(t-1)})^2

求一阶导

g_i = -(y_i - \hat y_i^{(t-1)})

即其一阶导是负残差。求二阶导,其值为常数

h_i = 1

Square Loss情况下,取I_j集合的均值「残差均值」作为该节点预测值「optimal weight」,应该跟w^*保持一致。

w_j^* = -\frac{G_j}{H_j + \lambda}

不难看出

综上,其optimal weight即为残差均值,其实是XGBoost里w_j^*的特例。

如何表征一棵树

决策树可看做一系列If-Then规则的集合,但这样表示起来比较麻烦。为了方便公式的推导,XGBoost将其表示为一向量。

Think regression tree as a function that maps the attributes to the score. We define tree by a vector of scores in leafs, and a leaf index mapping function that maps an instance to a leaf.

即用长度为T「叶子节点数」的向量w和将样本实例映射到叶子索引的映射函数q(x)表示。

paper-xgboost-tree

这样树的预测输出可直接用w表示,跟正则项\vert w\vert ^2保持一致,公式表示推导上比较方便。

如何防止过拟合

XGBoost中有很多防止过拟合手段,比如

正则化

每一轮树的目标函数Objective中可以包含正则项,是防止过拟合经典手段

\Omega(f) = \gamma T + \frac{1}{2}\lambda||w||^2

Shrinkage

每一轮树都不完全拟合残差或梯度,给后续学习器学习的空间

y^{(t)} = y^{(t-1)} + \epsilon f_t(x_i)

\epsilon is called step-size or shrinkage, usually set around 0.1. This means we do not do full optimization in each step and reserve chance for future rounds, it helps prevent overfitting

Column Subsampling

随机森林里使用的经典方法,也叫做feature subsampling,每次只用一部分特征学习,也可防止过拟合。

Candidate Proposal

在选择连续特征分裂点时,不遍历所有可能值「exact greedy algorithm」,而是由数据分位点生成一系列候选「candidate proposal」,从中选择分裂点。这样不仅降低了计算量,同时还有一定防止过拟合效果。

特征重要性

树模型一个优点就是可以确定特征重要性,具体如何做呢?XGBoost里提供这几个衡量标准

详细可参考文档Python API Reference

当然还有更一般化确定特征重要性的方法,比如Permutation Test,林轩田老师在机器学习技法中随机森林章节中有介绍。其基本思想是某一维特征做permutation,依据模型performance的下降程度判定特征重要性。

符号约定

Ref

上一篇 下一篇

猜你喜欢

热点阅读