梯度提升

梯度提升是用于回归和分类问题的机器学习技术,其以弱预测模型(通常为决策树)的集合的形式产生预测模型。 它像其他增强方法一样以阶段式方式构建模型,并且通过允许优化任意可微损失函数来推广它们。

来源:Wikipedia
简介

定义及描述

在机器学习中,提升方法(Boosting)是一种通过组合一群复杂度低,训练的成本低,不容易过度拟合的弱分类器(weak learner),建立N个模型(分类),并且尝试在每次分类中都将上一次分错的数据权重提高一点再进行分类,来获得一个强分类器(strong learner)的方法。

梯度提升(Gradient Boosting)是一种提升方法,也是一种常用于回归和分类问题的集成学习算法和机器学习技术,以弱预测模型(通常是决策树)集合的形式产生预测模型。主要思想是每一次建立模型都是在之前建立模型损失函数的梯度下降方向,即通过优化损失函数(loss function)来生成这些模型。

梯度提升主要涉及三个要素:

  1. 要优化的损失函数。
  2. 做出预测的弱分类器。
  3. 一个加法模型,用于添加弱分类器以最小化损失函数。

梯度提升的过程用数学方法,可以描述为 (公式下列出了Latex代码):

假设我们的模型能够用下面的函数来表示,现有一个输出变量y,一个输入变量x,和联合概率分布函数P(x,y)。对于已知的X和对应的Y,使用训练集{(x1, y1), ... ,(xn, yn)} 找到近似值 F*(x)的 到一个函数F(X)来最大限度地减少某些指定损失函数的预期值ψ(y, F(X)),即对于N个样本点(xi,yi)计算其在模型F(x;α,β)下的损失函数,最优的{α,β}就是能够使得这个损失函数最小的{α,β}。

F*(\mathbf{x})=\ \arg \min {F(\mathbf{x}\rangle }\boldsymbol{\mathcal{E}}{\boldsymbol{\mathcal{Y}},\mathbf{X}}\boldsymbol{\mathit{\Psi }}(\boldsymbol{\mathcal{Y}},F(\mathbf{x})).

通过拓展F*(X)的形式来提升F*(X)的估计值,可以获得F(X):

其中,函数h(x; a)(基础分类器)通常用参数a = {a1; a2;...an}来选取含x的简单函数。拓展系数βm和参数am以向前的阶段式方式联合拟合到训练数据。

F(\mathbf{x})=^{\sum_{\mathbf{m}=0}^{\boldsymbol{M}}}\beta_{\mathbf{m}}h(\mathbf{x};\mathbf{am})

因此,我们获得了拓展系数βm和参数am的关系和函数Fm(X),也就是我们将要得到的模型Fm(x)的参数{αm,βm}能够使得Fm的方向是之前得到的模型Fm-1(x)的损失函数下降最快的方向。对于每一个数据点x都可以得到一个y im(x),最终我们可以得到一个完整梯度下降方向,即新的函数y im:

(\beta {\mathbf{m}},\mathbf{am})=\ \arg \min {\beta {'}\mathbf{a}}\sum {{\boldsymbol{l}}^{\blacksquare }-\mathbf{l}}^{N}\dot{\boldsymbol{\mathit{\Psi }}(\mathcal{Y}\boldsymbol{l}},F{\mathbf{m}-\mathbf{l}}(\mathbf{x}_{\boldsymbol{l})+\beta h(\mathbf{x}\boldsymbol{l}}^{\blacksquare };\mathbf{a}))

F_{\mathbf{m}}(\mathbf{x})=F_{\mathbf{m}-\mathbf{l}}(\mathbf{x})+\beta \mathbf{m}h(\mathbf{x};\mathbf{am}).

{\mathcal{Y}{\boldsymbol{l}\mathbf{m}=}^{\blacksquare }}^{\boldsymbol{m}}-[\frac{\partial \boldsymbol{\mathit{\Psi }}(\mathcal{Y}{\boldsymbol{l}}^{\blacksquare },F(\mathbf{x}{\boldsymbol{l}}^{\blacksquare }))}{\partial F(\mathbf{x}{\boldsymbol{l})}}^{]{F(\mathbf{X})=F_{\mathbf{m}-\mathrm{l}}(\mathbf{X})}}.

为了使得Fm(x)能够在y im(x)的方向上,使用最小二乘法优化上面的式子可以得到am:

\mathbf{a}{\mathbf{\ae }}=\ \arg \min {\mathbf{a},\rho }\sum {\boldsymbol{l}=1}^{N}[{\mathcal{Y}{\boldsymbol{l}\mathfrak{R}}}^{\boldsymbol{m}}-\rho h(\mathbf{x}{\boldsymbol{l}}^{\blacksquare };\mathbf{a})]^{2}

进而得到βm:

\beta {\mathbf{m}}=\ \arg \min {\beta }\sum {{\boldsymbol{l}=}^{\blacksquare }1}^{N}\boldsymbol{\mathit{\Psi }}(\mathcal{Y}\boldsymbol{l}^{\blacksquare },F_{\mathbf{m}-^{{\mathbf{l}}(\mathbf{x}{\boldsymbol{l})+\beta h(\mathbf{x}_{\boldsymbol{l}};\mathbf{am})).}}}

基于标准的损失函数的预期值ψ,βm可以简化为:

7'\mathbf{m}=\ \arg \min {7\quad \mathbf{x}}$  $\sum $  ${i}\in R_{'\mathbf{\oe }}$  $\boldsymbol{\mathit{\Psi }}(\mathcal{Y}{\boldsymbol{l},F{\mathbf{m}-\mathbf{l}}(\mathbf{x}{\boldsymbol{l})+{7}}).}^{\blacksquare }

最终合并到模型中:

F_{\mathbf{m}}(\mathbf{x})=F\mathbf{m}-^{{\mathbf{l}}(\mathbf{x})+{^{\mathcal{V}.}7'\mathbf{ml}(\mathbf{x}\in R_{l\mathbf{m}).}}}

以上流程以算法的伪代码可以表示为:

描述来源:Friedman, J. H. (2002). Stochastic gradient boosting. Computational Statistics & Data Analysis, 38(4), 367-378.,URL:https://www.sciencedirect.com/science/article/pii/S0167947301000652

发展历史

描述

1997年,Yoav Freund 和 Robert Schapire 提出了第一个成功且实用的提升算法 Adaboost 的概念。

1998年,Leo Breiman 将 Adaboost 归纳为建立在特殊损失函数的梯度下降方向上的算法。

1999-2001年,Jerome H. Friedman 将梯度下降的思想引入 Boosting 算法,提出了Gradient Boosting 的概念,以便处理不同的损失函数。

1999-2000年,Llew Mason,Jonathan Baxter,Peter Bartlett 和 Marcus Frean 也提出了适用于更普遍情况的一般功能性梯度提升 (General Functional Gradient Boosting),通过迭代地选择指向负梯度方向的函数来优化功能空间上的成本函数。

2015年,陈天奇 提出了Xgboost的概念并开源使其作为一个研究项目,并用于深度机器学习社区 (DMLC) 。

主要事件

年份事件相关论文/Reference
1997Yoav Freund 和 Robert Schapire 提出 AdaboostFreund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1), 119-139.
1998Leo Breiman重新总结归纳Adaboost的性质Breiman, L. (1998). Arcing classifier (with discussion and a rejoinder by the author). The annals of statistics, 26(3), 801-849.
1999-2001Jerome H. Friedman 提出 Gradient BoostingFriedman, J. H. (2001). Greedy function approximation: a gradient boosting machine. Annals of statistics, 1189-1232.
1999-2000Llew Mason,Jonathan Baxter,Peter Bartlett 和 Marcus Frean 提出 General Functional Gradient BoostingMason, L., Baxter, J., Bartlett, P. L., & Frean, M. R. (2000). Boosting algorithms as gradient descent. In Advances in neural information processing systems (pp. 512-518).
2015陈天奇 提出了Xgboost的概念Chen, T., He, T., & Benesty, M. (2015). Xgboost: extreme gradient boosting. R package version 0.4-2, 1-4.

发展分析

瓶颈

GBFS (Gradient Boosting Feature Selection)的一个瓶颈是它使用复杂度为O(dn)的CART (Classification and regression trees)算法来探索特征(d表示特征维数的数量,n表示数据点的数量)。 如果特征多达上百万,这可能会成为问题。 一种可能突破这种瓶颈的方法是提高d的可扩展性,将搜索限制为新功能的随机子集,类似于随机森林(Random Forest)。 然而,与随机森林相比,GBFS的迭代性质允许我们通过其先前迭代的分裂值来偏置特征的采样概率,从而避免不必要地选择不重要的特征。

未来发展方向

Gradient Boosting 可用于学习排名领域,网络搜索引擎雅虎和Yandex在他们的机器学习排名引擎中已经成熟地使用各种梯度增强算法。


Contributor: Tiange Wang

相关人物
简介
相关人物