梯度提升

定义及描述

在机器学习中，提升方法（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) 。

主要事件

发展分析

瓶颈

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

未来发展方向

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

Contributor: Tiange Wang