面试常问问题复习(一)

1. xgboost原理

1. 简介：

XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器。因为XGBoost是一种提升树模型，所以它是将许多树模型集成在一起，形成一个很强的分类器。而所用到的树模型则是CART回归树模型。

2. CART回归树

CART回归树是假设树为二叉树，通过不断将特征进行分裂。比如当前树结点是基于第j个特征值进行分裂的，设该特征值小于s的样本划分为左子树，大于s的样本划分为右子树。
CART(回归树, regressiontree)是xgboost最基本的组成部分。其根据训练特征及训练数据构建分类树，判定每条数据的预测结果。其中构建树使用gini指数计算增益，即进行构建树的特征选取，gini指数公式如式(1), gini指数计算增益公式如式(2)：

$Gini(D) = \sum_{k=1}^Kp_k(1-p_k)$ (1)

$p_k$表示数据集 $D$中类别$k$的概率，$K$表示类别个数。

注：此处的$k$表示分类类别。

$Gini(D,A)=\frac{\left| D_{1} \right|}{\left| D \right|}Gini(D_{1}) \frac{\left| D_{2} \right|}{\left| D \right|}Gini(D_{2})$

$D$表示整个数据集，$D_1$和$D_2$分别表示数据集中特征为$A$的数据集和特征非 $A$ 的数据集， $Gini(D_1)$表示特征为$A$的数据集的gini指数。

3. Boosting tree

一个CART往往过于简单,并不能有效地做出预测，为此，采用更进一步的模型boosting tree，利用多棵树来进行组合预测。具体算法如下：

输入：训练集 $T={(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)}$

输出：提升树 $f_M( x )$

步骤：

(1) 初始化 $f_0(x) = 0$

(2) 对 $m = 1,2,\dots,M$

(a) 计算残差 $r_{mi}=y_i-f_{(m-1)} (x_i ),i=1,2,…,n$

(b) 拟合残差$r_{mi}$学习一个回归树，得到 $T(x:\theta_m)$

(3) 得到回归提升树：$f_M(x) = \sum_{m=1}^M T(x:\theta_m)$

4. XGBoost

XGBoost是一种基于决策树（CART）的分布式的高效的梯度提升算法，它可被应用到分类、回归、排序等任务中，与一般的GBDT算法相比，XGBoost主要有以下几个优点：

对叶节点的权重进行了惩罚，相当于添加了正则项，防止过拟合
XGBoost的目标函数优化利用了损失函数关于待求函数的二阶导数，而GBDT只利用了一阶信息
XGBoost支持列采样，类似于随机森林，构建每棵树时对属性进行采样，训练速度快，效果好
类似于学习率，学习到一棵树后，对其权重进行缩减，从而降低该棵树的作用，提升可学习空间
构建树的算法包括精确的算法和近似的算法，近似的算法对每维特征加权分位进行分桶，具体的算法利用到了损失函数关于待求树的二阶导数。
添加了对于稀疏数据的支持，当数据的某个特征缺失时，将该数据划分到默认的子节点，本文提出了一个算法来求解这个默认方向。
可并行的近似直方图算法，分裂节点时，数据在block中按列存放，而且已经经过了预排序，因此可以并行计算，即同时对各个属性遍历最优分裂点

boosting是属于串行的集成方法，其预测函数为多个基分类器的集成，其学习过程也是先学习前(t-1)个基分类器，再学习第t个基分类器。XGBoost中最主要的基学习器为CART（分类与回归树）。分类的话就是

离散值判定，回归的话就是将连续值分段判定（比如age<15）。每个叶子节点对应score，每个样本在每棵树里的得分相加，就是这个样本的总得分：

$\hat y_i = \sum_{k=1}^K f_k(x_i), f_k \in {F}$

K表示有K棵树，$f_k$相当于第k棵树，而F空间表示整个CART树空间。因此我们的目标函数可以写成：

$obj (\theta) = \sum_i^n l(y_i, \hat y_i) + \sum_{k=1}^K \Omega(f_k)$

然后：
$$
%
$$
假设我们的目标函数如下：

$\begin{split}obj = \sum_{i=1}^n l(y_i, \hat y_i^{(t)}) + \sum_{i=1}^t\Omega(f_i) \ \end{split}$

这个目标函数里，我们的训练目标是$f_t(x_i)$，即对应一棵树。通过递增训练（Additive Training）的方式，我们可以一棵树一棵树的求解。

那么我们如何从上面的公式中求解最优的T棵树呢？首先考虑第t棵树的目标函数：
$$
%
$$
$l$表示损失函数，$Ω(f_t)$表示第t棵树的正则化项。损失函数l可以是MSE（最小平方误差），也可以用logistic损失函数，也可以同交叉熵损失函数等。那么我们假设已知损失函数，对ll进行泰勒级数展开到二阶导数，可以得到如下目标函数：
$\text{obj}^{(t)} = \sum_{i=1}^n [l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) + constant$

去除掉所有常数项后，得到第t棵树的目标函数为：

$obj^(t)=\sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)$
这样，目标函数只依赖于损失函数的一阶导数和二阶导数了。

再考虑正则项，正则项如何定义？考虑树的复杂度，我们可以得到正则项：$\Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2$

其中，$γ$和$λ$是人工设定参数，T为树的叶子节点个数，且

$w_{q(x)} = f_t(x), w \in R^T, q:R^d\rightarrow {1,2,\cdots,T} .$

最终目标函数：
$$
%
$$

整合后目标函数为：$\text{obj}^{(t)} = \sum^T_{j=1} [G_jw_j + \frac{1}{2} (H_j+\lambda) w_j^2] +\gamma T$

5. 如何学习具体的树结构

由于我们知道了如何去评价一棵树到底有多好（上面的目标函数），那么我们就可以将构造树的步骤进行分解，每一次只优化一层树。考虑一个节点，我们要将该节点分成两个叶子节点，那么我们获得的分数（此处用gain表示，就是分之前和分之后的目标函数差）

$Gain = \frac{1}{2} \left[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma$

这个公式中包含：

左叶子节点得分
右叶子节点得分
原叶子节点得分
额外的叶子的正则化项

如果gain比$γ$稍小，那么我们最好不要增加这个分支。这就是树模型里的剪枝思想。
通过这种方式，我们不断构造各种分法的树，从而求解得到最佳的树。

6. 节点分裂算法

因为树结构未知，只能采用贪婪的算法，从根节点出发，每次选择一个属性及其对应的值，使得损失函数减少最多，根据选择的属性分裂节点。论文中给出了精确的和近似的算法，当数据量非常大时，采用近似的算法可以有效减少计算量。

6.1 精确贪婪算法(Basic Exact Greedy Algorithms)

算法如上图所示，核心思想如下

两个for循环，第一个for遍历所有特征，第二个for找出最佳的特征值作为分裂点
选分裂点的依据score为分裂前后损失函数的减少量
第二个for循环中，先对数据按照特征值进行排序，这样做的目的为了后面一次遍历就能求出所有分裂点的score值。$G_L,G_R$只需要在当前的基础上进行加减，不需要再扫描所有数据
贪心算法体现在，当前分裂点的选择只考虑能使得当前损失函数减少量最大

这里的m值通常小于样本维度d,表示列采样得到的属性个数，值得注意的是，由于要遍历所有的属性的所有取值，因此，通常需要在训练之前对所有样本做一个预排序(pre-sort)，从而避免每次选择属性都要重新排序。

6.2 近似算法(Approximate Algorithm for Split Finding)

精确贪心算法虽然很强大，但是当数据无法完全加载到内存中或者在分布式的条件下，这种基于穷举的分裂点寻找方法效率就会非常低下。于是作者提出了一种近似分割的算法，这种算法首先通过加权分位数的算法选出了一些可能的分裂点，然后再遍历这些较少的分裂点来找到最佳分裂点。

对于值为连续值的特征，当样本数非常大时，该特征取值过多，遍历所有取值复杂度较高，而且容易过拟合。因此，考虑将特征值分桶，即找到l个分位点，将位于相邻分位点之间的样本分在一个桶中，在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。注意到上面算法流程中说明了有全局的近似(global)和局部(local)的近似，所谓全局就是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部就是在具体的某一次分裂节点的过程中采用近似算法。

带权重直方图算法
主要用于近似算法中分位点的计算，假设分位点为 ${s*{k1},s*{k2},..,s*{kl}}$假设，假设$(x*{1k},h1),(x{2k},h2),..,(x{nk},h_n)$表示所有样本的第表示所有样本的第$k$ 个特征值及二阶导数,这意味着大概有$1/ϵ$个分位点。
本文还提出了分布式 weighted quantile sketch algorithm ，该算法的优点是解决了带权重的直方图算法问题，以及有理论保证。

6.3 稀疏特征处理(Sparsity-aware Split Finding)

XGBoost还特别设计了针对稀疏数据的算法，假设样本的第i个特征缺失时，无法利用该特征对样本进行划分，这里的做法是将该样本默认地分到指定的子节点，至于具体地分到哪个节点还需要下面的算法来计算：

该算法的主要思想是，分别假设特征缺失的样本属于右子树和左子树，而且只在不缺失的样本上迭代，分别计算缺失样本属于右子树和左子树的增益，选择增益最大的方向为缺失数据的默认方向。

2. GBDT原理

GBDT是一个系列算法，具有很好的性能，可以用于回归、分类、排序的机器学习任务，也是机器学习面试时常考的一个知识点，在这写下个人的一些理解，也当做个笔记。

GBDT分为两部分，GB: Gradient Boosting和DT: Decision tree。

GBDT算法是属于Boosting算法族的一部分，可将弱学习器提升为强学习器的算法，属于集成学习的范畴。

2.1 决策树

由于GBDT中的弱学习器采用的是决策树，在这儿我们先介绍下决策树。

顾名思义，决策树对应于数据结构中的树结构，可以认为是if-then规则的集合，具有可解释性、分类速度快等优点。

决策树的学习通常包含3个步骤：特征选择、决策树的生成和决策树的修剪。

决策树由结点和有向边组成，结点有两种类型：内部结点和叶子结点，内部结点表示一个特征或属性，叶子结点表示一个类。

分类时，根据内部结点的特征对样本进行测试，根据测试结果，分配到相应的子节点，递归直到到达叶子结点，则分类为叶子结点所在的类。

互斥且完备：每一个样本都被树的一条路径（一条规则）所覆盖，而且只被一条路径所覆盖。

决策树学习的本质是从训练数据中归纳出一组分类规则，由训练数据集估计条件概率模型。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割。

决策树常用的算法有ID3、C4.5和CART。

特征选择

特征选择在于选取对训练数据具有分类能力的特征。通常的准则是信息增益或信息增益比。

信息增益

表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练数据集D的信息增益$g(D,A)$，定义为集合D的经验熵与特征A给定条件下D的经验条件熵$H(D|A)$之差，即：

$g(D,A)=H(D)−H(D|A)$

信息增益大的特征具有更强的分类能力。
信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。

使用信息增益比可以对这一问题进行校正。特征A对训练数据集D的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集D关于特征A的值的熵$H_A(D)$之比，即

$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

选信息增益比高的特征
基尼指数

对于给定的样本集合D，其基尼指数为：

$Gini(D) = 1 - \sum_{k=1}^K(\frac{|C_{k}|}{|D|})^2$

$Ck$是D中属于第k类的样本子集，K是类的个数。

如果样本集合D根据某特征被分隔成$D1$和$D2$两部分：则在特征A条件下，集合D的基尼指数定义为：

$Gini(D, A) = \frac{|D_{1}|}{|D|}Gini(D_{1}) + \frac{|D_{2}|}{|D|}Gini(D_{2})$

基尼指数值越大，样本集合的不确定性也就越大。

选基尼指数小的特征分割。

平方误差最小化
这是针对回归任务来说的，在构建回归树时进行特征选取的准则。

ID3算法是使用信息增益准则来进行特征选择。
C4.5算法是使用信息增益比准则来进行特征选择。
CART算法是使用基尼指数和平方误差最小化来进行特征选择。
决策树的剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止。这样容易出现过拟合现象。

在决策树学习中将已生成的树进行简化的过程称为剪枝。

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

2.2 CART算法

分类回归树(classification and regression tree, CART)是应用广泛的决策树学习算法。

CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左边分支是取值为“是”的分支，右分支是取值为“否”的分支。

CART算法由以下两步组成：
（1）决策树生成：基于训练数据生成决策树，生成的决策树要尽量大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

1. 分类树构建

分类树构建与上面的ID3算法和C4.5算法类似，这里就不再叙述。

2. 回归树构建

一个回归树对应着输入空间的一个划分以及在划分单元上的输出值，假设已将输入空间划分为M个单元$R_1,R_2,…,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，则回归树模型可表示为：

$f(x) = \sum_{m=1}^{M}c_{m}I(x\in R_{m})$

单元$R_m$上的$c_m$的最优值$\hat c_m$是$R_m$上所有输入样本$x_i$对应的输出$y_i$的均值。

如何进行划分，采用启发式的方法，选择第$j$个变量$x(j)$和它取的值，作为切分变量和切分点，并定义两个区域：

$R1(j,s)=x|x(j)≤s$

$R2(j,s)=x|x(j)>s$

然后寻找最优切分变量j和最优切分点s，具体地，求解：

$min_{j, s} [min_{c_{1}}\sum_{x_{i}\in R_{1}(j,s)}(y_{i}-c_{1})^2 + min_{c_{2}}\sum_{x_{i}\in R_{2}(j,s)}(y_{i}-c_{2})^2]$

每次在选择切分变量j和切分点s时，遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)。

2.3 提升树模型

采用加法模型（即基函数的线性组合）与前向分布算法，以决策树为基函数的提升方法称为提升树。

1. 加法模型-积硅步以至千里

加法模型的基本思想是“积硅步以至千里”，就是每次学习一点，然后一步步的接近最终要预测的值（完全是gradient的思想~）。

提升树模型可以表示为决策树的加法模型：

$f_{M}(x) = \sum_{m=1}^M T(x;\theta_{m})$

其中，$T(x;θ_m)$表示决策树，$θ_m$为决策树的参数；M为树的个数

在给定训练数据及损失函数$L(y,f(y))$的条件下，学习加法模型$f_M(x)$称为经验风险极小化即损失函数极小化问题：

$\underset{\theta_{m}}{min} = \sum_{i = 1}^{N}L(y_{i}, \sum_{m=1}^M T(x;\theta_{m}))$

这是一个复杂的优化问题。可以使用前向分步算法来求解这一优化问题。

2. 前向分步算法

首先确定初始提升树$f_0(x)=0$，第m步模型是：

$f_{m}(x) = f_{m-1}(x)+ T(x;\theta_{m})$

其中，$f_{m−1}(x)$为当前模型，通过经验风险极小化确定下一棵决策树的参数$θ_m$，

$\hat \theta_{m} = arg \underset{\theta_{m}}{min} \sum_{i=1}^ML(y_{i}, f_{m-1}(x_{i})+T(x_{i}; \theta_{m}))$

树的线性组合可以很好的拟合训练数据，即使数据中的输入和输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同，包括用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。

3. 回归问题提升树

采用平方误差损失函数时，

$L(y, f(x)) = (y-f(x))^2$

其损失变为：

$L(y, f_{m-1}(x) + T(x;\theta_{m})) = [y-f_{m-1}(x)-T(x;\theta_{m})]^2 = [r-T(x;\theta_{m})]^2$

这里，$r = y - f_{m-1}(x)$
是当前模型拟合数据的残差，对回归问题的提升树来说，只需要简单地拟合当前模型的残差。

2.4 GBDT

当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。这时就需要用到梯度提升(gradient boosting)算法。
这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度方向在当前模型的值，

$- [\frac{\partial L(y_{i}, f(x))}{\partial f(x)}]_{f(x) = f_{m-1}(x)}$

作为回归提升树算法的残差近似值，拟合一个回归树。

1. 梯度近似

贪心法再每次选择最优基函数时仍然困难。
将样本带入当前模型，得到$f_{m−1}(x_i)$，从而损失值为$L(y_i,f_{m−1}(x_i)$。
此时我们可以求出梯度，然后进行更新：

$f_{m}(x) = f_{m-1}(x) - r_{m}\sum_{i=1}{N}\delta L(y_{i}, f_{m-1}(x))$

上式中权值为$r$为梯度下降的步长，使用线性搜索求最优步长。

$r_{m} = arg \underset{r}{min}\sum_{i=1}^N L(y_{i}, f_{m-1}(x) - r_{m}\delta L(y_{i}, f_{m-1}(x)))$

GBDT采用的是数值优化的思维，用的最速下降法去求解Loss Function的最优解，其中用CART决策树去拟合负梯度，用牛顿法求步长。

2. 衰减（Shrinkage）

这个是把学习的大步变小步，即“真实值-预测值”*shrinkage
衰减因子：v
v = 1即为原始模型，推荐选择v<0.1的小学习率。过小的学习率会造成计算次数增多。

3. XGBoost与GBDT对比

传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
- XGBoost:$L(\phi ) = \sum_{i} l(\hat y_{i}, y_{i}) + \sum_{k}\Omega (f_{k})$
  
  $Obj^{(t)} = \sum_{i=1}^nl(y_{i}, \hat y_{i}^{(t-1)}+f_{t}(x_{i})) + \Omega(f_{t}) + constant$
  
  $\Omega(f_{t}) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^Tw_{j}^2$
- GBDT:$L(\phi ) = \sum_{i} l(\hat y_{i}, y_{i}) $
GBDT优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。xgboost工具支持自定义代价函数，只要函数可一阶二阶求导。
xgboost在代价函数中引入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出score的L2。使学习出来的模型更加简单，防止过拟合。
缩减和列采样：防止过拟合，列采样是从随机森林那边学习来的，防止过拟合的效果比传统的行采样效果还要好，并且有利于后面提到的并行化处理算法。
划分点查找算法
- 贪心算法获取最优切分点
- 近似算法，提出了候选分割点概念，先通过直方图算法获得候选分割点的分布情况
- 分布式加权直方图算法
对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。稀疏感知算法。
内置交叉验证
并行化处理：各个特征的增益计算是可以并行进行的