当前位置: 开发笔记 > 前端 > 正文

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

作者：手机用户2602929123 | 来源：互联网 | 2023-08-28 13:30

前言今天翻了下gayhub,随手点进去了follow的一个大佬wepe,看到一个非常和谐的repo名:tgboost.看完readme发现了作者的一个pptGBDT算法原理与系统

前言

今天翻了下gayhub,随手点进去了follow的一个大佬wepe,看到一个非常和谐的repo名:tgboost.看完readme发现了作者的一个pptGBDT算法原理与系统设计简介,平时工作接触的比较少,对于这俩算法一直都是处于一知半解的状态.这回从头复习了一波相关的内容,写两篇记录下来.
从根本上来说, GBDT 与XGBoost最大的区别在于二者用的优化方法不一样,所以从先从最优化方法开始复习.

几种最优化算法

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

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

函数优化问题: 优化的对象是一定区间内的连续变量.
组合优化问题: 优化的对象是解空间内的离散状态.如TSP(旅行商问题)
上文ppt里的这一页讲的非常好,就暂且抄一波

函数优化与组合优化

在机器学习中,典型的做法就是选择一个合适的模型 $H(\theta)$

几种梯度下降法对比

牛顿法与拟牛顿法

牛顿法原理
从本质上来说,牛顿法是二阶收敛,梯度下降是一阶收敛,因此,牛顿法肯定更快.
在数学分析这门课里,我们学习过一种求解高阶方程的方法:牛顿下山法.牛顿下山法的迭代公式为: $x_n&＃61;x_{n-1}-\frac{f(x_{n-1})}{{f}&＃39;(x_{n-1})}$

海塞矩阵

可以看出,虽然牛顿法收敛速度较快,但是每次迭代过程,计算海塞矩阵的逆过程相当繁琐,特别是当该矩阵维度较大时.因此就有了逆牛顿法,他使用正定矩阵来近似求海塞矩阵的逆.
拟牛顿法和梯度下降法一样只要求每一步迭代时知道目标函数的梯度,另外&＃xff0c;因为拟牛顿法不需要二阶导数的信息&＃xff0c;所以有时比牛顿法更为有效。常用的拟牛顿法有DFP算法和BFGS算法.此处不再赘述.
下面补充拟牛顿法的思路(摘自[3]):

拟牛顿法原理
牛顿法的迭代过程中,计算海塞矩阵 $H^{-1}$ 这一过程比较复杂,考虑使用一个满足拟牛顿条件的矩阵 $G_k&＃61;G(x^{(k)})$ 来近似代替海塞矩阵.这个矩阵的构造思想是,不用二阶偏导数就构造出可以近似海塞矩阵的正定矩阵,
$g_{k&＃43;1}-g_{k}&＃61;H_{k&＃43;1}{(x^{(k&＃43;1)}-x^{(k)})}$ ,简写为
$y_k&＃61;H_{k&＃43;1}*s_k&＃61;>s_k&＃61;{H_{k&＃43;1}}^{-1}*y_k$ (拟牛顿条件)
针对这个拟牛顿条件,有两个常见的算法变种:DFP算法与BFGS算法.
简述一下两个算法的原理

DFP算法
构造 $D_k\approx {H_k}^{-1}$ 利用一个原理,可逆的对称矩阵一定正定.假设算法的迭代过程为:
$D_{k&＃43;1}&＃61;D_k &＃43; \Delta D_k$ ,根据这个原理,可以初始化一个 $D_0&＃61;I$ (单位矩阵), 构造一个 $\Delta D_k$ 为对称矩阵.由此得到这个假设 $\Delta D_k&＃61;\alpha u u^T&＃43;\beta v v^T$ ,代入到拟牛顿条件中得到
$s_k&＃61;D_{k&＃43;1}y_k&＃61;(D_k&＃43;\Delta D_k)y_k &＃61;D_{k}y_k&＃43;\alpha uu^{T}y_k&＃43;\beta vv^{T}y_k$ 利用矩阵乘法的结合律变换后: $s_k&＃61;D_k y_k&＃43;\alpha u^Ty_ku&＃43;\beta v^Ty_kv$ ,u,v前面的部分为常数,假定 $\alpha u^Ty_k&＃61;1,\beta v^Ty_k&＃61;-1$ 可以得到 $\alpha&＃61;\frac{1}{u^Ty_k},\beta &＃61; \frac{-1}{v^Ty_k}$ ,此外 $s_k&＃61;D_k y_k&＃43;u-v&＃61;>u-v&＃61;s_k-D_k y_k$ , 假设 $u&＃61;s_k, v&＃61;D_ky_k$ ,再代回前面的式子得到 $\alpha&＃61;\frac{1}{{s_k}^Ty_k}, \beta&＃61;\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)&＃61;x^TQx&＃43;q^Tx$
什么是共轭梯度
假设 $Q\in \mathbb{R}^{n\times n}$ 为对称正定矩阵, $d_i \in \mathbb{R}^n$ , 满足 ${d_i}^T Q d_j&＃61;0, i\neq j, \forall i,j&＃61;1,2...m$ , 则称 $d_1,d_2...d_m$ 对于 $Q$ 相互共轭,称为 $Q-$ 共轭方向组.
算法推导
以一组共轭向量为更新方向最终会得到全局最小值,是共轭梯度法的最终原理.
此处数学推导没有全部弄明白,后续再补充.
直观地来说,因为一共n个方向&＃xff0c;每次都消除了一个方向上的误差&＃xff0c;经过n轮迭代&＃xff0c;就一定可以得到正解。
4.算法步骤
从 $x_0$ 出发,依次沿 $d_0,d_1,...d_{k-1}$ 进行搜索则:
$x_k &＃61; x_{i&＃43;1}&＃43;\sum_{j&＃61;i&＃43;1}^{k-1}\lambda_j d_j (i&＃61;0,1,...k-1)$
它的搜索方向是负梯度方向和上一次搜索方向的一个组合
$d_k&＃61;-g_k&＃43;\beta_{k-1} d_{k-1}$ ,其中 $\beta$ 一般有两种公式
优缺点
收敛快,计算量大,介于牛顿法与梯度下降法之间.

启发式算法

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

拉格朗日乘数法

上面前三种算法,解决的问题都仅限于无约束的凸优化, 而拉格朗日乘数法则解决含有约束条件的优化问题,例如svm算法的解法推导.约束优化问题的一般形式是:
$\underset{s.t.g(x.y.z)&＃61;0}{min/max f(x,y,z)}$
这个问题可以转化成函数 $F(x,y,z,\lambda)&＃61;f(x,y,z)&＃43;\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.

作者&＃xff1a;MashoO
链接&＃xff1a;https://www.jianshu.com/p/78f27fcf532d
来源&＃xff1a;简书
简书著作权归作者所有&＃xff0c;任何形式的转载都请联系作者获得授权并注明出处。

推荐阅读

js
大数据时代的机器学习：人工特征工程与线性模型的局限

本文探讨了在大数据背景下，人工特征工程与线性模型的应用及其局限性。随着数据量的激增和技术的进步，传统的特征工程方法面临挑战，文章提出了未来发展的可能方向。 ... [详细]

蜡笔小新 2024-12-07 11:58:58
js
LambdaMART算法详解

本文详细介绍了LambdaMART算法的背景、原理及其在信息检索中的应用。首先回顾了LambdaMART的发展历程，包括其前身RankNet和LambdaRank，然后深入探讨了LambdaMART如何结合梯度提升决策树（GBDT）和LambdaRank来优化排序问题。 ... [详细]

蜡笔小新 2024-12-18 12:30:35
html
垃圾回收机制解析

在程序运行过程中，各种编程语言都会动态创建对象，并为其分配内存。当这些对象不再使用时，释放其所占内存变得至关重要，以确保资源的有效利用。本文深入探讨了垃圾回收（GC）的工作原理，包括如何识别、何时及如何回收不再使用的对象。 ... [详细]

蜡笔小新 2024-12-18 11:53:47
html
全能终端工具推荐：高效、免费、易用

介绍一款备受好评的全能型终端工具——MobaXterm，它不仅功能强大，而且完全免费，适合各类用户使用。 ... [详细]

蜡笔小新 2024-12-16 21:02:15
js
在Ubuntu 16.04中使用Anaconda安装TensorFlow

本文详细介绍了如何在Ubuntu 16.04系统上通过Anaconda环境管理工具安装TensorFlow。首先，需要下载并安装Anaconda，然后配置环境变量以确保系统能够识别Anaconda命令。接着，创建一个特定的Python环境用于安装TensorFlow，并通过指定的镜像源加速安装过程。最后，通过一个简单的线性回归示例验证TensorFlow的安装是否成功。 ... [详细]

蜡笔小新 2024-12-11 19:07:39
上传
图像标签与以图搜图技术的应用与实践

本文探讨了图像标签的多种分类场景及其在以图搜图技术中的应用，涵盖了从基础理论到实际项目实施的全面解析。 ... [详细]

蜡笔小新 2024-12-07 14:28:06
js
微信小程序中实现位置获取的全面指南

本文详细介绍了如何在微信小程序中实现地理位置的获取，包括通过微信官方API和腾讯地图API两种方式。文中不仅涵盖了必要的准备工作，如申请开发者密钥、下载并配置SDK等，还提供了处理用户授权及位置信息获取的具体代码示例。 ... [详细]

蜡笔小新 2024-12-18 10:41:24
js
Web与游戏开发的主要差异

本文探讨了Web开发与游戏开发之间的主要区别，旨在帮助开发者更好地理解两种开发领域的特性和需求。文章基于作者的实际经验和网络资料整理而成。 ... [详细]

蜡笔小新 2024-12-18 08:26:30
html
C语言中如何正确编写头文件

本文探讨了在C语言编程中，如何有效避免多文件项目中的重定义问题，通过合理使用预处理器指令和extern关键字，确保代码的健壮性和可维护性。 ... [详细]

蜡笔小新 2024-12-17 19:39:04
js
Python库在GIS与三维可视化中的应用

Python库极大地扩展了GIS的能力，使其能够执行复杂的数据科学任务。本文探讨了几个关键的Python库，这些库不仅增强了GIS的核心功能，还推动了地理信息系统向更高层次的应用发展。 ... [详细]

蜡笔小新 2024-12-13 17:24:24
js
厘清机器学习与数据分析的界限

本文旨在探讨机器学习与数据分析之间的差异，不仅在于它们处理的数据类型，还包括技术背景、业务应用场景以及参与者的不同。通过深入分析，希望能为读者提供清晰的理解。 ... [详细]

蜡笔小新 2024-12-12 15:15:36
js
《MySQL DBA修炼之道》正式上架

我的新书已正式上市，可在当当和京东购买。如果您喜欢本书，欢迎留下宝贵评价。本书历时3至4年完成，内容涵盖MySQL的安装、配置、开发、测试、监控和运维等方面，旨在帮助读者系统地学习MySQL。 ... [详细]

蜡笔小新 2024-12-08 20:49:40
js
吴恩达推出TensorFlow实践课程，Python基础即可入门，四个月掌握核心技能

量子位报道，deeplearning.ai最新发布了TensorFlow实践课程，适合希望使用TensorFlow开发AI应用的学习者。该课程涵盖机器学习模型构建、图像识别、自然语言处理及时间序列预测等多个方面。 ... [详细]

蜡笔小新 2024-12-08 17:26:10
overflow
机器学习算法（五）—— 最优化方法：梯度下降

一、什么是梯度下降梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数，即无约束优化问题时，梯度下降（GradientDescent ... [详细]

蜡笔小新 2024-12-07 19:53:54
overflow
深入解析Bagging与Boosting算法原理及应用

本文通过详细分析Bagging与Boosting两种集成学习技术的基本概念、工作原理及其在实际项目中的应用案例，帮助读者深入了解这两种强大的机器学习方法。同时，提供相关资源链接以供进一步学习。 ... [详细]

蜡笔小新 2024-12-06 10:47:27

手机用户2602929123

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章