点击上方卡片链接就可以进入专栏，专栏右上角有订阅选项，欢迎大家订阅～

前言

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第1.13节：XGBoost算法（上）。这是鬼仔第一次开设专栏，每篇文章鬼仔都会用心认真编写，希望能将每个知识点讲透、讲深，帮助同学们系统性地学习和掌握机器学习中的基础知识，希望大家能多多支持鬼仔的专栏～

这一节的内容较多，分为上下两篇解读：上篇讲算法原理，下篇解析高频面试真题。目前这篇是试读，后续的文章需要订阅才能查看哦，专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

一、目标函数定义和求解

XGBoost是boosting模型的集大成者，它在系统实现中的创新大大提高了算法的实用性，在许多机器学习和数据挖掘问题中产生了广泛的影响，在竞赛中也被广泛使用。XGBoost在任何场景下的可扩展性都很强，在单台机器上的运行速度很快，并可在分布式或内存限制设置中可扩展到数十亿个实例。本文主要参考作者陈天奇大佬的原文introduction to xgboost，行文逻辑非常清晰。

如果不考虑工程实现上的一些差异，xgboost与gbdt比较大的不同就是目标函数的定义。xgboost的目标函数如下：

三个红框分别对应XGBoost的损失函数（加法模型）、正则项（包括L1、L2）和常数项（前t-1棵树的复杂度）。

XGBoost和GBT的另一个重要区别是：XGBoost对目标函数执行二阶泰勒展开，而提升树模型只采用一阶泰勒展开。

1. 决策树的定义

上面损失函数中的表示的是决策树，可以形式化地定义为：，即将一颗决策树拆分成结构部分q和叶子权重部分w，结构函数q把输入数据映射到叶子索引，而叶子权重w表示每个叶子索引对应的分数。

2. 正则项的定义

XGBoost的目标函数中考虑了正则项，效果类似于剪枝操作，防止生成的决策树过于复杂，导致过拟合。正则项有多种定义方式，一般采用下图中的经验公式，这个公式包含了一棵树里面节点的个数，以及每个叶子节点分数的L2模平方。

从正则项的公式可以看出：

• 叶结点越多，则决策树越复杂。
• 每个叶结点输出分数的绝对值越大，则决策树越复杂。

从Bayes角度来看，正则相当于对模型参数引入先验分布：

3. 目标函数的优化

根据前面对决策树和正则项的定义，并去掉常数项后，我们可以将目标函数优化为以下形式：

其中定义叶子结点j上的实例集合为：，g是一阶导数，h是二阶导数，n为样本数，T为叶子节点数，w为待求解权重。

该目标函数为T个相互独立的二次函数之和，我们进一步简化目标函数的公式：

为求得目标函数的极值，我们对求导等于0，可得到最优解，最后将其代入原目标函数可得：

目标函数Obj也可以称为结构分数，它是衡量第t棵CART树的结构好坏的标准，值越小，代表树的结构越好。

二、结点分裂算法

结构分数Obj可以评估每棵树的得分，为了找出最优的树结构，我们可以枚举出所有的树，然后计算每棵树的得分，然后保留得分最高的树，但是实际中这样的操作是不现实的，树的结构近乎无限