XGBoost与GBDT(一)-几种最优化方法对比

前言

今天翻了下gayhub,随手点进去了follow的一个大佬

wepe

,看到一个非常和谐的repo名:tgboost.看完readme发现了作者的一个ppt

GBDT算法原理与系统设计简介

,平时工作接触的比较少,对于这俩算法一直都是处于一知半解的状态.这回从头复习了一波相关的内容,写两篇记录下来.

从根本上来说, GBDT 与XGBoost最大的区别在于二者用的优化方法不一样,所以从先从最优化方法开始复习.

几种最优化算法

在生活或者工作中存在各种各样的最优化问题，比如每个企业和个人都要考虑的一个问题“在一定成本下，如何使利润最大化”等。最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。[2]

最优化问题通常分为两个大类:

函数优化问题: 优化的对象是一定区间内的连续变量.
组合优化问题: 优化的对象是解空间内的离散状态.如TSP(旅行商问题)

上文ppt里的这一页讲的非常好,就暂且抄一波

函数优化与组合优化

在机器学习中,典型的做法就是选择一个合适的模型
$H(\theta)$
,对该模型的损失函数
$L(\theta)$
,通过最优化的方法最小化损失函数,从而求解模型的参数.

最常见的几种优化方法包括[2]:

梯度下降法(Gradient Decent)
牛顿法与拟牛顿法(Newton’s method & Quasi-Newton Methods)
共轭梯度法(Conjugate Gradient)
启发式算法(Heuristic algorithm)
拉格朗日乘数法(Lagrange Multiplier Method)

下面简单介绍以上几种优化方法

梯度下降法

原理

梯度下降法是最简单也是最常用的最优化方法,它是一种迭代方法:随机选取初值
$\theta^{0}$
, 不断迭代更新
$\theta$
的值,从而进行损失函数极小化.注意这里是极小化而非最小化.当求解问题是凸函数时,这个极小值也就是全局最小值,或者说全局解,其他情况下,梯度下降法并不保证求解全局最优.

梯度下降法的思想是贪心的,在当前位置负梯度方向搜索,因为该方向是当前位置下的最快下降方向.迭代公式如下

$\theta^{t}=\theta^{t-1}+\Delta\theta$

将
$L(\theta)$
在
$\theta^{t-1}$
处一阶泰勒展开:

$L(\theta^t)=L(\theta^{t-1}+\Delta\theta)\approx L(\theta^{t-1})+{L}'(\theta^{t-1})\Delta\theta$

要优化
$L(\theta)$
,需要保证
$L(\theta^t)<L(\theta^{t-1})$
, 可取
$\Delta\theta=-\alpha{L}'(\theta^{t-1})$
, 其中
$\alpha$
为学习率,得到梯度下降的迭代公式:

$\theta^{t}=\theta^{t-1}+-\alpha{L}'(\theta^{t-1})$
优点

简单粗暴,好像也找不到其他的优点了.
缺点

越靠近解收敛越慢;容易出现之字行搜索;样本量大时速度缓慢
常见的两种梯度下降法

批量梯度下降(BGD)

每次迭代使用

所有样本

,训练速度慢;矩阵计算可并行,凸函数全局最优.
随机梯度下降(SGD)

每次迭代使用

一个样本

,速度快但是对噪声相当敏感,单样本不能代表全部.
小批量梯度下降(MBGD)

每次迭代使用

batch_size

的样本.训练快,可并行,但是batch_size难以选取.增大bs跑一次epoch迭代次数减少,并行化效率提高,并且更准;坏处就是需要更大的内存,训练时间可能大大增加.

几种梯度下降法对比

牛顿法与拟牛顿法

牛顿法原理

从本质上来说,牛顿法是二阶收敛,梯度下降是一阶收敛,因此,牛顿法肯定更快.

在数学分析这门课里,我们学习过一种求解高阶方程的方法:牛顿下山法.牛顿下山法的迭代公式为:
$x_n=x_{n-1}-\frac{f(x_{n-1})}{{f}'(x_{n-1})}$
,当应用于求解无约束最优化问题时,认为最优解满足
${L}'(\theta)=0$
(凸函数的极值点),此处用牛顿下山法求解该方程得到牛顿法的迭代公式:
$\theta^t=\theta^{t-1}-\frac{{L}'(\theta^{t-1})}{{L}''(\theta^{t-1})}$

切换到矩阵形态就变成了:
$\theta^t=\theta^{t-1}-{H_t}^{-1}\Delta_{\theta^{t-1}}L(\theta_{t-1})$
,此处推导过程涉及矩阵求导法则,没有彻底了解,有机会再补上.海塞矩阵也是一个公式,具推导过程不详:

海塞矩阵

可以看出,虽然牛顿法收敛速度较快,但是每次迭代过程,计算海塞矩阵的逆过程相当繁琐,特别是当该矩阵维度较大时.因此就有了逆牛顿法,他使用正定矩阵来近似求海塞矩阵的逆.

拟牛顿法和梯度下降法一样只要求每一步迭代时知道目标函数的梯度,另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。常用的拟牛顿法有DFP算法和BFGS算法.此处不再赘述.

下面补充拟牛顿法的思路(摘自[3]):

拟牛顿法原理

牛顿法的迭代过程中,计算海塞矩阵
$H^{-1}$
这一过程比较复杂,考虑使用一个满足拟牛顿条件的矩阵
$G_k=G(x^{(k)})$
来近似代替海塞矩阵.这个矩阵的构造思想是,不用二阶偏导数就构造出可以近似海塞矩阵的正定矩阵,

$g_{k+1}-g_{k}=H_{k+1}{(x^{(k+1)}-x^{(k)})}$
,简写为

$y_k=H_{k+1}*s_k=>s_k={H_{k+1}}^{-1}*y_k$
(拟牛顿条件)

针对这个拟牛顿条件,有两个常见的算法变种:DFP算法与BFGS算法.

简述一下两个算法的原理

DFP算法

构造
$D_k\approx {H_k}^{-1}$
利用一个原理,可逆的对称矩阵一定正定.假设算法的迭代过程为:

<center>
$D_{k+1}=D_k + \Delta D_k$
</center>,根据这个原理,可以初始化一个
$D_0=I$
(单位矩阵), 构造一个
$\Delta D_k$
为对称矩阵.由此得到这个假设
$\Delta D_k=\alpha u u^T+\beta v v^T$
,代入到拟牛顿条件中得到

$s_k=D_{k+1}y_k=(D_k+\Delta D_k)y_k =D_{k}y_k+\alpha uu^{T}y_k+\beta vv^{T}y_k$
利用矩阵乘法的结合律变换后:
$s_k=D_k y_k+\alpha u^Ty_ku+\beta v^Ty_kv$
,u,v前面的部分为常数,假定
$\alpha u^Ty_k=1,\beta v^Ty_k=-1$
可以得到
$\alpha=\frac{1}{u^Ty_k},\beta = \frac{-1}{v^Ty_k}$
,此外
$s_k=D_k y_k+u-v=>u-v=s_k-D_k y_k$
, 假设
$u=s_k, v=D_ky_k$
,再代回前面的式子得到
$\alpha=\frac{1}{{s_k}^Ty_k}, \beta=\frac{-1}{{y_k}^T{D_k}^Ty_k}$
,将
$\alpha, \beta, u, v$
带入就可以得到
$\Delta D_k$
. 非常鸡贼.
BFGS算法

构造
$D_k\approx {H_k}$
,利用拟牛顿条件左边公式,推导方式与DFP算法一致,相对来说效率比DFP算法好,此处不再赘述推导过程.
L-BFGS算法

针对BFGS进行速度上的优化,并行时效率较高.

优缺点

1	优点	缺点
牛顿法	相对于梯度下降法,牛顿法使用二阶偏导数进行优化,收敛速度较快	牛顿法由于使用了二阶偏导数,要求目标函数必须一二阶偏导连续,并且具有正定的海塞矩阵.此外,计算海塞矩阵的过程又相对麻烦,计算量巨大.
拟牛顿法	收敛快,计算比牛顿法快	当样本量大时计算量过大

共轭梯度法

共轭梯度法是一种用于解决无约束凸二次规划问题的方法.

原理

无约束凸二次规划问题

最优化理论的内容,不是很熟.

$\underset{x}{min}f(x)=x^TQx+q^Tx$
什么是共轭梯度

假设
$Q\in \mathbb{R}^{n\times n}$
为对称正定矩阵,
$d_i \in \mathbb{R}^n$
, 满足
${d_i}^T Q d_j=0, i\neq j, \forall i,j=1,2...m$
, 则称
$d_1,d_2...d_m$
对于
$Q$
相互共轭,称为
$Q-$
共轭方向组.
算法推导

以一组共轭向量为更新方向最终会得到全局最小值,是共轭梯度法的最终原理.

此处数学推导没有全部弄明白,后续再补充.

直观地来说,因为一共n个方向，每次都消除了一个方向上的误差，经过n轮迭代，就一定可以得到正解。

4.算法步骤

从
$x_0$
出发,依次沿
$d_0,d_1,...d_{k-1}$
进行搜索则:

$x_k = x_{i+1}+\sum_{j=i+1}^{k-1}\lambda_j d_j (i=0,1,...k-1)$

它的搜索方向是负梯度方向和上一次搜索方向的一个组合

$d_k=-g_k+\beta_{k-1} d_{k-1}$
,其中
$\beta$
一般有两种公式
优缺点

收敛快,计算量大,介于牛顿法与梯度下降法之间.

启发式算法

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多，包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。

拉格朗日乘数法

上面前三种算法,解决的问题都仅限于无约束的凸优化, 而拉格朗日乘数法则解决含有约束条件的优化问题,例如svm算法的解法推导.约束优化问题的一般形式是:

$\underset{s.t.g(x.y.z)=0}{min/max f(x,y,z)}$

这个问题可以转化成函数
$F(x,y,z,\lambda)=f(x,y,z)+\lambda g(x,y,z)$
的无条件极值问题.

对于约束条件为不等式的问题,有科学家拓展了拉格朗日乘数法.增加了kkt条件以求解.没学过最优化,这块就没法细谈了.有机会一定要补上.

参考文献

[1]Poll的笔记.常见的几种最优化方法[EB/OL].

https://www.cnblogs.com/maybe2030/p/4751804.html,2015-08-23

.

[2]超神冉.最优化算法——常见优化算法分类及总结[EB/OL].

https://blog.csdn.net/qq997843911/article/details/83445318,2018-10-27

.

[3]李航.统计学习方法[M].清华大学出版社:北京,2012:220.

[4]Ja1r0.共轭梯度法[EB/OL].

https://zhuanlan.zhihu.com/p/28623599,2018-05-28

.

作者：MashoO

链接：https://www.jianshu.com/p/78f27fcf532d

来源：简书

简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

前言