浏览本文须要的背景知识点：自适应加强算法、泰勒公式、One-Hot 编码、一丢丢编程常识

一、引言

  后面一节咱们学习了自适应加强算法（Adaptive Boosting / AdaBoost Algorithm），是一种晋升算法（Boosting Algorithm），而该算法家族中还有另一种重要的算法——梯度晋升决策树 ¹（Gradient Boosted Decision Trees / GBDT），GBDT 及其变体算法在传统机器学习中有着宽泛的利用，理解其背地的思维与原理对于当前的学习有很大的帮忙。

二、模型介绍

  梯度晋升决策树同自适应加强算法一样是一种晋升算法，也能够解释为一种加法模型，第 k 轮后的强预计器为第 k – 1 轮后的强预计器加上带系数的弱预计器 h(x)：

$$
H_k(x) = H_{k – 1}(x) + \alpha_k h_k(x)
$$

<center> 式 2 -1</center>

  假如第 k – 1 轮对应的代价函数为 $Cost(y, H_{k – 1}(X))$, 第 k 轮对应的代价函数为 $Cost(y, H_k(X))$，咱们的目标是使得每次迭代后，其代价函数都会逐步变小。

  因为每个不同的代价函数对应的优化形式不同，Jerome H. Friedman 在其原始算法的论文 ² 中给出了一个对立解决的办法，能够应用代价函数的负梯度来拟合该轮迭代代价函数的减小，这也是最速降落法的一种近似，其本质是应用一阶泰勒公式近似其代价函数。当根底预计器应用的是决策回归树时，该算法被称为梯度晋升决策树（GBDT）。

$$
\hat{y}_{k, i} = -\left[\frac{\partial Cost(y_i, H(X_i))}{\partial H(X_i)} \right]_{H(x) = H_{k-1}(x)}
$$

<center> 式 2 -2</center>

  上面还是同 AdaBoost 算法一样，别离思考回归、二分类、多分类这三个问题，一一介绍每个问题对应的算法。因为 GBDT 算法回归比分类简略，所以这次将回归问题放在后面介绍。

回归

  对于回归问题的代价函数，咱们先应用平方误差来作为代价函数：

$$
Cost(y, H(x)) = (y – H(x))^2
$$

<center> 式 2 -3</center>

  第 k 轮的代价函数：

（1）带入式 2-1

（2）带入平方误差的代价函数

（3）扭转括号

（4）将 y 与第 k – 1 轮的后果之差记为 $\hat{y}_k$

$$
\begin{aligned}
Cost(y, H_{k}(x)) & = Cost(y, H_{k – 1}(x) + \alpha_kh_k(x)) & (1) \\
& = (y – (H_{k – 1}(x) + \alpha_kh_k(x) ))^2 & (2) \\
&= ((y – H_{k – 1}(x)) – \alpha_kh_k(x))^2 & (3) \\
&= (\hat{y}_k – \alpha_kh_k(x))^2 & (4)
\end{aligned}
$$

<center> 式 2 -4</center>

  察看式 2-4 中的（4）式会发现这就是后面章节中介绍的决策回归树的代价函数，只是该回归树不再是应用训练集中的 y，而是去拟合上式中的 $\hat{y}$，也能够称为残差。失去回归树后更新 H(x)，而后进行新的迭代。

  这样就失去了最简略的最小二乘回归的 GBDT 算法实现，具体步骤能够参考第三节的算法步骤中的回归局部，能够看到其中的系数 $\alpha$ 能够了解为融入到了回归树外部。

  在论文中作者还介绍了其余的几种代价函数，别离是最小相对偏差（LDA）、Huber 损失 ³ 等，感兴趣的读者能够浏览论文中对应的章节。

  因为 GBDT 须要计算负梯度是个间断值，所以对于分类问题，其根底预计器没有应用分类树，而是仍然应用的回归树。

二分类

  对于分类问题的代价函数，能够应用指数函数与对数函数。当应用指数函数时，GBDT 将等同于后面一节中介绍的 AdaBoost 算法，这里咱们应用对数函数作为代价函数：

$$
Cost(y, H(x)) = \log (1 + e^{-2yH(x)})
$$

<center> 式 2 -5</center>

  依照后面模型介绍的计算负梯度的办法，带入代价函数计算出 $\hat{y}$：

$$
\begin{aligned}
\hat{y}_{k, i} &= -\left[\frac{\partial Cost(y_i, H(X_i))}{\partial H(X_i)} \right]_{H(x) = H_{k-1}(x)} & (1)\\
&= \frac{2y_i}{1 + e^{2y_iH_{k-1}(X_i)}} & (2)
\end{aligned}
$$

<center> 式 2 -6</center>

  计算出 $\hat{y}$ 后咱们能够拟合出一颗回归树预计器 h(x)，这时咱们要求的是每轮迭代后的预计器的系数 $\alpha$：

$$
\alpha_k = \underset{\alpha}{argmin} \sum_{i = 1}^{N} \log (1 + e^{-2y_i(H_{k – 1}(X_i) + \alpha h_k(X_i))})
$$

<center> 式 2 -7</center>

  咱们先来看下这个回归树预计器 h(x)，其表达式能够写成下式，其中回归树一共有 J 个叶子结点，$R_j$、$\beta_j$ 别离代表回归树第 j 个叶子结点蕴含的训练汇合和取值，$I(x)$ 为后面章节中提到过的批示函数：

$$
h(x) = \sum_{j = 1}^{J} \beta_j I(x \in R_j)
$$

<center> 式 2 -8</center>

  这时将式 2-8 带入式 2-7 中改写一下，这时就不再是求预计器的系数 alpha，转而间接求 $\gamma$，其中 $\gamma_{k,j} = \alpha_k * \beta _{k,j}$：

$$
\gamma_{k, j} = \underset{\gamma}{argmin} \sum_{X_i \in R_{k, j}}^{} \log (1 + e^{-2y_i(H_{k – 1}(X_i) + \gamma )})
$$

<center> 式 2 -9</center>

  因为式 2-9 中蕴含了对数指数函数，导致其没有闭式解，这时能够应用二阶泰勒公式对其进行近似解决失去如下后果：

$$
\gamma_{k,j} = \frac{\sum_{X_i \in R_{k,j}} \hat{y}_{k,i}}{\sum_{X_i \in R_{k,j}} |\hat{y}_{k,i}| (2 – |\hat{y}_{k,i}|)}
$$

<center> 式 2 -10</center>

  失去 gamma 后更新 H(x)，而后进行新的迭代。

  这样就失去了二分类的 GBDT 算法实现，具体步骤能够参考第三节的算法步骤中的二分类局部，具体的公式的来由能够参考第四节的原理证实。

多分类

  多分类绝对二分类更简单一些，同样是应用对数函数作为其代价函数，还用到了后面多分类对数几率回归算法中介绍的 Softmax 函数，同时还需对输出的标签值 y 进行 One-Hot 编码 ⁴ 操作，其代价函数如下：

$$
\begin{aligned}
Cost(y, H(x)) &= \sum_{m = 1}^M y_m \log p_m(x) & (1) \\
p_{m}(x) &= \frac{e^{H_{m}(x)}}{\sum_{l=1}^M e^{H_{l}(x)}} & (2) \\
\end{aligned}
$$

<center> 式 2 -11</center>

  同样依照后面模型介绍的计算负梯度的办法，带入代价函数计算出 $\hat{y}$：

$$
\begin{aligned}
\hat{y}_{k, m, i} &= -\left[\frac{\partial Cost(y_i, H(X_i))}{\partial H(X_i)} \right]_{H(x) = H_{k-1}(x)} & (1)\\
&= y_{m, i} – p_{k-1, m}(X_i) & (2) \\
\end{aligned}
$$

<center> 式 2 -12</center>

  同二分类一样，拟合回归树，同时将其转化为求对应的 $\gamma$，不同的是须要对每一个分类都拟合一个回归树，所以多分类一共须要拟合 K * M 个决策回归树：

$$
\gamma_{k, m, j} = \underset{\gamma}{argmin} \sum_{i = 1}^{N} \sum_{m = 1}^{M} Cost\left(y_{m,i}, H_{k – 1, m}(X_i) + \sum_{j = 1}^{J} \gamma I(X_i \in R_{k, m, j})\right)
$$

<center> 式 2 -13</center>

  同样应用泰勒公式对其进行近似解决失去如下后果：

$$
\gamma_{k, m, j} = \frac{M – 1}{M} \frac{\sum_{X_i \in R_{k, m, j}} \hat{y}_{k, m, i}}{\sum_{X_i \in R_{k, m, j}} |\hat{y}_{k, m, i}| (1 – |\hat{y}_{k, m, i}|)}
$$

<center> 式 2 -14</center>

  失去 $\gamma$ 后更新对应分类的 H(x)，而后进行新的迭代。

  这样就失去了多分类的 GBDT 算法实现，具体步骤能够参考第三节的算法步骤中的多分类局部。

三、算法步骤

回归

  假如训练集 T = {$X_i$, $y_i$}，i = 1，…，N，h(x) 为预计器，预计器的数量为 K。

梯度晋升决策树回归算法步骤如下：

初始化 $H_0(x)$，令其等于 y 的平均值 $\bar{y}$

$$
H_0(X_i) = \bar{y}
$$

遍历预计器的数量 K 次：

  计算第 k 轮的残差 $\hat{y}_{k}$

$$
\hat{y}_{k, i} = y_i – H_{k-1}(X_i)
$$

  将第 k 轮 $\hat{y}_{k}$ 当作标签值拟合训练集，失去决策回归树预计器 $h_k(x)$

  更新 $H_k(x)$

$$
H_k(X_i) = H_{k-1}(X_i) + h_k(X_i)
$$

完结循环

最初的预测策略：

  输出 x，K 个决策回归树预计器顺次预测后相加，而后加上初始值 $H_0$，失去最初的预测后果

$$
H(x) = H_{0} + \sum_{k = 1}^K h_k(x)
$$

二分类

  假如训练集 T = {$X_i$, $y_i$}，i = 1，…，N，$y_i \in \{-1, +1 \}$，h(x) 为预计器，预计器的数量为 K。

梯度晋升决策树二分类算法步骤如下：

初始化 $H_0(x)$，其中 $\bar{y}$ 为 y 的平均值

$$
H_0(X_i) = \frac{1}{2} \log \frac{1 + \bar{y}}{1 – \bar{y}}
$$

遍历预计器的数量 K 次：

  计算第 k 轮的 $\hat{y}_{k}$

$$
\hat{y}_{k,i} = \frac{2y_i}{1 + e^{2y_iH_{k-1}(X_i)}}
$$

  将第 k 轮 $\hat{y}_{k}$ 当作标签值拟合训练集，失去决策回归树预计器 $h_k(x)$，其中 $h_k(x)$ 蕴含 J 个叶子结点

  计算第 k 轮第 j 个叶子结点的系数 $\gamma$，其中 $R_{kj}$ 代表第 k 轮拟合出的决策回归树预计器 $h_k(x)$ 第 j 个叶子结点蕴含的训练汇合

$$
\gamma_{k,j} = \frac{\sum_{X_i \in R_{k,j}} \hat{y}_{k,i}}{\sum_{X_i \in R_{k,j}} |\hat{y}_{k,i}| (2 – |\hat{y}_{k,i}|)}
$$

  更新 $H_k(x)$，其中 $I(x)$ 为后面章节中提到过的批示函数

$$
H_k(X_i) = H_{k – 1}(X_i) + \sum_{j = 1}^{J} \gamma_{k,j} I(X_i \in R_{k,j})
$$

完结循环

最初的预测策略：

  输出 x，K 个决策回归树预计器顺次判断所属叶子结点，将叶子结点对应的系数 $\gamma$ 累加，而后加上初始值 $H_0$，失去 H(x)

$$
H(x) = H_0 + \sum_{k = 1}^{K}\sum_{j = 1}^{J} \gamma_{k,j} I(x \in R_{k,j})
$$

  别离计算正类和负类的概率

$$
\left\{\space
\begin{aligned}
p_+(x) &= \frac{1}{1 + e^{-2H(x)}} \\
p_-(x) &= \frac{1}{1 + e^{2H(x)}}
\end{aligned}
\right.
$$

  取正类和负类概率中最大的分类，作为最初的分类后果

$$
\underset{m}{argmax} \space p_m(x) \quad (m \in \{+ , -\})
$$

多分类

  假如训练集 T = {$X_i, y_i$}，i = 1，…，N，y 的取值有 M 种可能，h(x) 为预计器，预计器的数量为 K。

梯度晋升决策树多分类算法步骤如下：

对训练集中的标签值 y 进行 One-Hot 编码

初始化 $H_{0,m}(x)$，其中 m 为第 m 个分类，在原始论文中赋值为 0，而 scikit-learn 中的实现为各个分类的先验

$$
H_{0, m}(X_i) = \frac{\sum_{i=1}^{N}I(y_i = m)}{N} 或 0
$$

遍历预计器的数量 K 次：

  遍历分类的数量 M 次：

    计算第 k – 1 轮第 m 个分类的概率 p(x)

$$
p_{k-1, m}(X_i) = \frac{e^{H_{k-1, m}(X_i)}}{\sum_{l=1}^M e^{H_{k-1, l}(X_i)}}
$$

    计算第 k 轮第 m 个分类的 $\hat{y}_{k, m}$

$$
\hat{y}_{k, m, i} = y_{m, i} – p_{k-1, m}(X_i)
$$

    将第 k 轮第 m 个分类的 $\hat{y}_{k, m}$ 当作标签值拟合训练集，失去决策回归树预计器 $h_{k,m}(x)$，其中 $h_{k,m}(x)$ 蕴含 J 个叶子结点

    计算第 k 轮第 m 个分类第 j 个叶子结点的系数 $\gamma$，其中 $R_{k,m,j}$ 代表第 k 轮第 m 个分类拟合出的决策回归树预计器 $h_{k,m}(x)$ 第 j 个叶子结点蕴含的训练汇合

$$
\gamma_{k, m, j} = \frac{M – 1}{M} \frac{\sum_{X_i \in R_{k, m, j}} \hat{y}_{k, m, i}}{\sum_{X_i \in R_{k, m, j}} |\hat{y}_{k, m, i}| (1 – |\hat{y}_{k, m, i}|)}
$$

    更新 $H_{k,m}(x)$，其中 $I(x)$ 为后面章节中提到过的批示函数

$$
H_{k, m}(X_i) = H_{k – 1, m}(X_i) + \sum_{j = 1}^{J} \gamma_{k, m, j} I(X_i \in R_{k, m, j})
$$

  完结循环

完结循环

最初的预测策略：

  输出 x，第 m 个分类对应的 K 个决策回归树预计器顺次判断所属叶子结点，将叶子结点对应的系数 $\gamma$ 累加，而后加上第 m 个分类的初始值 $H_0$，失去第 m 个分类的 H(x)

$$
H_{m}(x) = H_{0,m} + \sum_{k = 1}^{K} \sum_{j = 1}^{J} \gamma_{k, m, j} I(x \in R_{k, m, j})
$$

  顺次计算每个分类的概率

$$
p_m(x) = \frac{e^{H_m(x)}}{\sum_{l = 1}^M e^{H_l(x)}}
$$

  取每个分类的概率中最大的分类，作为最初的分类后果

$$
\underset{m}{argmax} \space p_m(x) \quad (m = 1,2,\dots,M)
$$

四、原理证实

回归问题初始值

  对于用平方误差作为代价函数的最小二乘回归，其初始值为 y 的均值：

（1）回归问题的代价函数

（2）对代价函数求导数并令其等于零

（3）能够算出其初始值为 y 的均值

$$
\begin{aligned}
Cost(H(x)) &= \sum_{i = 1}^{N} (y_i – H(x))^2 & (1) \\
\frac{\partial Cost(H(x))}{\partial H(x)} &= 2\sum_{i = 1}^{N} (H(x) – y_i) = 0 & (2) \\
H(x) &= \frac{\sum_{i = 1}^{N} y_i}{N} = \bar{y} & (3) \\
\end{aligned}
$$

<center> 式 4 -1</center>

  即得证

二分类问题初始值

  对于二分类问题，$y \in \{-1, +1 \}$：

（1）$y = +1$ 的个数

（2）$y = -1$ 的个数

（3）两式之和为 N

$$
\begin{aligned}
n_{+} &= \sum_{i = 1}^N I(y_i = +1) & (1) \\
n_{-} &= \sum_{i = 1}^N I(y_i = -1) & (2) \\
N &= n_{+} + n_{-} & (3) \\
\end{aligned}
$$

<center> 式 4 -2</center>

（1）y 的平均值的表达式
（2）化简失去

$$
\begin{aligned}
\bar{y} &= \frac{1 * n_{+} + (-1) * n_{-}}{N} & (1) \\
&= \frac{n_{+} – n_{-}}{N} & (2) \\
\end{aligned}
$$

<center> 式 4 -3</center>

  由式 4-2 中的（3）式和式 4-3 中的（2）式，能够别离求得如下后果：

$$
\begin{aligned}
n_{+} &= \frac{N(1 + \bar{y})}{2} & (1) \\
n_{-} &= \frac{N(1 – \bar{y})}{2} & (2)
\end{aligned}
$$

<center> 式 4 -4</center>

（1）二分类问题的代价函数

（2）对代价函数求导数

（3）将（2）式的后果拆分为两个连加的和

（4）带入式 4-4 的后果，将连加符号去除

（5）化简后令其等于零

（6）最初能够算出其初始值

$$
\begin{aligned}
Cost(H(x)) & = \sum_{i = 1}^N \log (1 + e^{-2y_iH(x)}) & (1) \\
\frac{\partial Cost(H(x))}{\partial H(x)} &= -\sum_{i = 1}^N \frac{2y_i}{1 + e^{2y_iH(x)}} & (2) \\
&= -\sum_{y_i = +1} \frac{2y_i}{1 + e^{2y_iH(x)}} – \sum_{y_i = -1} \frac{2y_i}{1 + e^{2y_iH(x)}} & (3) \\
&= – \frac{N(1 + \bar{y})}{2} * \frac{2}{1 + e^{2H(x)}} – \frac{N(1 – \bar{y})}{2} * \frac{-2}{1 + e^{-2H(x)}} & (4) \\
&= – \frac{N(1 + \bar{y})}{1 + e^{2H(x)}} + \frac{N(1 – \bar{y})}{1 + e^{-2H(x)}} = 0 & (5) \\
H(x) &= \frac{1}{2} \log \frac{1 + \bar{y}}{1 – \bar{y}} & (6)
\end{aligned}
$$

<center> 式 4 -5</center>

  即得证

二分类问题系数 $\gamma$

  咱们先来看下 $\gamma$ 的优化指标函数：

（1）二分类问题的代价函数

（2）式 2-9 失去的 $\gamma$ 的优化指标

（3）对（2）式在 $H_{k – 1}(x)$ 处进行二阶泰勒开展近似

（4）能够看到 $H(x) – H_{k – 1}(x)$ 等于 $\gamma$

$$
\begin{aligned}
Cost(H(x)) &= \sum_{X_i \in R_{k, j}}^{} \log (1 + e^{-2y_iH(X_i)}) & (1) \\
\gamma_{k, j} &= \underset{\gamma}{argmin} \sum_{X_i \in R_{k, j}}^{} \log (1 + e^{-2y_i(H_{k – 1}(X_i) + \gamma )}) & (2)\\
&= \underset{\gamma}{argmin} \sum_{X_i \in R_{k, j}}^{} Cost(H_{k – 1}(X_i)) + Cost^{‘}(H_{k – 1}(X_i)) (H(X_i) – H_{k – 1}(X_i)) + \frac{1}{2} Cost^{”}(H_{k – 1}(X_i)) (H(X_i) – H_{k – 1}(X_i))^2 & (3) \\
&= \underset{\gamma}{argmin} \sum_{X_i \in R_{k, j}}^{} Cost(H_{k – 1}(X_i)) + Cost^{‘}(H_{k – 1}(X_i)) \gamma + \frac{1}{2} Cost^{”}(H_{k – 1}(X_i)) \gamma^2 & (4)
\end{aligned}
$$

<center> 式 4 -6</center>

  对其近似进行求解：

（1）式 4-6 失去的 $\gamma$ 的泰勒开展近似

（2）对函数求导并令其为零

（3）失去 $\gamma$ 的后果

$$
\begin{aligned}
\phi (\gamma) &= \sum_{X_i \in R_{k, j}}^{} Cost(H_{k – 1}(X_i)) + Cost^{‘}(H_{k – 1}(X_i)) \gamma + \frac{1}{2} Cost^{”}(H_{k – 1}(X_i)) \gamma^2 & (1) \\
\frac{\partial \phi (\gamma)}{\partial \gamma} &= \sum_{X_i \in R_{k, j}}^{} + Cost^{‘}(H_{k – 1}(X_i)) + Cost^{”}(H_{k – 1}(X_i)) \gamma = 0 & (2) \\
\gamma &= -\frac{\sum_{X_i \in R_{k, j}}^{} Cost^{‘}(H_{k – 1}(X_i))}{\sum_{X_i \in R_{k, j}}^{} Cost^{”}(H_{k – 1}(X_i))} & (3) \\
\end{aligned}
$$

<center> 式 4 -7</center>

  上面顺次求代价函数的一阶导数和二阶导数：

$$
\begin{aligned}
Cost^{‘}(H_{k – 1}(X_i)) &= -\frac{2y_i}{1 + e^{2y_iH_{k-1}(X_i)}} = -\hat{y_i} & (1) \\
Cost^{”}(H_{k – 1}(X_i)) &= \frac{4y_i^2e^{2y_iH_{k-1}(X_i)}}{(1 + e^{2y_iH_{k-1}(X_i)})^2} = 2\hat{y_i}y_i – \hat{y}_i^2 & (2) \\
\end{aligned}
$$

<center> 式 4 -8</center>

（1）式 4-7 中失去的 $\gamma$ 的表达式

（2）带入式 4-8 失去

（3）当 $y = +1$ 时，$\hat{y} \in (0, 2)$，当 $y = -1$ 时，$\hat{y} \in (-2, 0)$，所以 $\hat{y} * y = |\hat{y}|$

（4）分母提出 $|\hat{y}|$

$$
\begin{aligned}
\gamma &= -\frac{\sum_{X_i \in R_{k, j}}^{} Cost^{‘}(H_{k – 1}(X_i))}{\sum_{X_i \in R_{k, j}}^{} Cost^{”}(H_{k – 1}(X_i))} & (1) \\
&= \frac{\sum_{X_i \in R_{k, j}}^{} \hat{y}_i}{\sum_{X_i \in R_{k, j}}^{} (2\hat{y}_iy_i – \hat{y}_i^2) } & (2) \\
&= \frac{\sum_{X_i \in R_{k, j}}^{} \hat{y}_i}{\sum_{X_i \in R_{k, j}}^{} (2|\hat{y}_i| – \hat{y}_i^2) } & (3) \\
&= \frac{\sum_{X_i \in R_{k, j}} \hat{y}_{i}}{\sum_{X_i \in R_{k,j}} |\hat{y}_{i}| (2 – |\hat{y}_{i}|)} & (4) \\
\end{aligned}
$$

<center> 式 4 -9</center>

  即得证

多分类问题系数 $\gamma$

  多分类问题的系数 $\gamma$ 因为存在多棵树重叠，波及到黑塞矩阵，无奈像二分类一样独自求解，论文中是应用对角近似其黑塞矩阵，间接给出了后果，因为笔者能力无限，如有晓得如何推导出后果的读者请留言或私信。

五、正则化

  梯度晋升树同样也须要进行正则化操作来避免过拟合的状况，其正则化的办法个别有如下几种形式：

学习速率

  在每次迭代更新 H(x) 时减少一个学习速率 $\eta$ 的超参数，下式中别离展现了学习速率 $\eta$ 在不同问题中的应用办法：

$$
\begin{aligned}
H_k(x) &= H_{k – 1}(x) + \eta \alpha_k h_k(x) & (1) \\
H_k(x) &= H_{k – 1}(x) + \eta \sum_{j = 1}^{J} \gamma_{k,j} I(x \in R_{k,j}) & (2) \\
H_{k, m}(x) &= H_{k – 1, m}(x) + \eta \sum_{j = 1}^{J} \gamma_{k, m ,j} I(x \in R_{k, m, j}) & (3) \\
\end{aligned}
$$

<center> 式 5 -1</center>

  其中学习速率 $\eta \in (0,1]$，当学习速率 $\eta$ 过小时，须要减少迭代次数能力达到好的学习效果，所以咱们须要综合思考该超参数的应用。在 scikit-learn 中应用 learning_rate 参数来管制。

子采样

  子采样相似于随机梯度降落的办法，每次只取一部分的训练集来学习，能够减小方差，然而同时也会减少偏差。在 scikit-learn 中应用 subsample 参数来管制，同样为大于 0 小于等于 1 的小数。

决策树枝剪

  决策树枝剪同后面在决策树章节中介绍的办法一样，通过对基预计器的管制来达到正则化的目标。在 scikit-learn 中应用决策树相干的参数来管制。

  上面代码实现中只实现了利用学习速率来正则化的操作，其余的办法能够参考 scikit-learn 的源码实现。

六、代码实现

应用 Python 实现梯度晋升树回归算法：

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class gbdtr:
    """梯度晋升树回归算法"""
    
    def __init__(self, n_estimators = 100, learning_rate = 0.1):
        # 梯度晋升树弱学习器数量
        self.n_estimators = n_estimators
        # 学习速率
        self.learning_rate = learning_rate
        
    def fit(self, X, y):
        """梯度晋升树回归算法拟合"""
        # 初始化 H0
        self.H0 = np.average(y)
        # 初始化预测值
        H = np.ones(X.shape[0]) * self.H0
        # 预计器数组
        estimators = []
        # 遍历 n_estimators 次
        for k in range(self.n_estimators):
            # 计算残差 y_hat
            y_hat = y - H
            # 初始化决策回归树预计器
            estimator = DecisionTreeRegressor(max_depth = 3)
            # 用 y_hat 拟合训练集
            estimator.fit(X, y_hat)
            # 应用回归树的预测值
            y_predict = estimator.predict(X)
            # 更新预测值
            H += self.learning_rate * y_predict
            estimators.append(estimator)
        self.estimators = np.array(estimators)
        
    def predict(self, X):
        """梯度晋升树回归算法预测"""
        # 初始化预测值
        H = np.ones(X.shape[0]) * self.H0
        # 遍历预计器
        for k in range(self.n_estimators):
            estimator = self.estimators[k]
            y_predict = estimator.predict(X)
            # 计算预测值
            H += self.learning_rate * y_predict
        return H

应用 Python 实现梯度晋升树二分类算法：

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class gbdtc:
    """梯度晋升树二分类算法"""
    
    def __init__(self, n_estimators = 100, learning_rate = 0.1):
        # 梯度晋升树弱学习器数量
        self.n_estimators = n_estimators
        # 学习速率
        self.learning_rate = learning_rate
        
    def fit(self, X, y):
        """梯度晋升树二分类算法拟合"""
        # 标签类
        self.y_classes = np.unique(y)
        # 标签类数量
        self.n_classes = len(self.y_classes)
        # 标签的平均值
        y_avg = np.average(y)
        # 初始化 H0
        self.H0 = np.log((1 + y_avg) / (1 - y_avg)) / 2
        # 初始化预测值
        H = np.ones(X.shape[0]) * self.H0
        # 预计器数组
        estimators = []
        # 叶子结点取值数组
        gammas = []
        for k in range(self.n_estimators):
            # 计算 y_hat
            y_hat = 2 * np.multiply(y, 1 / (1 + np.exp(2 * np.multiply(y, H))))
            # 初始化决策回归树预计器
            estimator = DecisionTreeRegressor(max_depth = 3, criterion="friedman_mse")
            # 将 y_hat 当作标签值拟合训练集
            estimator.fit(X, y_hat)
            # 计算训练集在以后决策回归树的叶子结点
            leaf_ids = estimator.apply(X)
            # 每个叶子结点下蕴含的训练数据序号
            node_ids_dict = self.get_leaf_nodes(leaf_ids)
            # 叶子结点取值字典表
            gamma_dict = {}
            # 计算叶子结点取值
            for leaf_id, node_ids in node_ids_dict.items():
                # 以后叶子结点蕴含的 y_hat
                y_hat_sub = y_hat[node_ids]
                y_hat_sub_abs = np.abs(y_hat_sub)
                # 计算叶子结点取值
                gamma = np.sum(y_hat_sub) / np.sum(np.multiply(y_hat_sub_abs, 2 - y_hat_sub_abs))
                gamma_dict[leaf_id] = gamma
                # 更新预测值
                H[node_ids] += self.learning_rate * gamma
            estimators.append(estimator)
            gammas.append(gamma_dict)
        self.estimators = estimators
        self.gammas = gammas
        
    def predict(self, X):
        """梯度晋升树二分类算法预测"""
        # 初始化预测值
        H = np.ones(X.shape[0]) * self.H0
        # 遍历预计器
        for k in range(self.n_estimators):
            estimator = self.estimators[k]
            # 计算在以后决策回归树的叶子结点
            leaf_ids = estimator.apply(X)
            # 每个叶子结点下蕴含的数据序号
            node_ids_dict = self.get_leaf_nodes(leaf_ids)
            # 叶子结点取值字典表
            gamma_dict = self.gammas[k]
            # 计算预测值
            for leaf_id, node_ids in node_ids_dict.items():
                gamma = gamma_dict[leaf_id]
                H[node_ids] += self.learning_rate * gamma
        # 计算概率
        probs = np.zeros((X.shape[0], self.n_classes))
        probs[:, 0] = 1 / (1 + np.exp(2 * H))
        probs[:, 1] = 1 / (1 + np.exp(-2 * H))
        return self.y_classes.take(np.argmax(probs, axis=1), axis = 0)
    
    def get_leaf_nodes(self, leaf_ids):
        """每个叶子结点下蕴含的数据序号"""
        node_ids_dict = {}
        for j in range(len(leaf_ids)):
            leaf_id = leaf_ids[j]
            node_ids = node_ids_dict.setdefault(leaf_id, [])
            node_ids.append(j)
        return node_ids_dict

应用 Python 实现梯度晋升树多分类算法：

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class gbdtmc:
    """梯度晋升树多分类算法"""
    
    def __init__(self, n_estimators = 100, learning_rate = 0.1):
        # 梯度晋升树弱学习器数量
        self.n_estimators = n_estimators
        # 学习速率
        self.learning_rate = learning_rate
        
    def fit(self, X, y):
        """梯度晋升树多分类算法拟合"""
        # 标签类，对应标签的数量
        self.y_classes, y_counts = np.unique(y, return_counts = True)
        # 标签类数量
        self.n_classes = len(self.y_classes)
        # 对标签进行 One-Hot 编码
        y_onehot = np.zeros((y.size, y.max() + 1))
        y_onehot[np.arange(y.size), y] = 1
        # 初始化 H0
        self.H0 = y_counts / X.shape[0]
        # 初始化预测值
        H = np.ones((X.shape[0], 1)).dot(self.H0.reshape(1, -1))
        # 预计器数组
        estimators = []
        # 叶子结点取值数组
        gammas = []
        # 遍历 n_estimators 次
        for k in range(self.n_estimators):
            H_exp = np.exp(H)
            H_exp_sum = np.sum(H_exp, axis = 1)
            # 预计器
            sub_estimators = []
            # 叶子结点取值
            sub_gammas = []
            # 遍历 n_classes 次
            for m in range(self.n_classes):
                p_m = H_exp[:, m] / H_exp_sum
                # 计算第 m 个 y_hat
                y_hat_m = y_onehot[:, m] - p_m
                # 初始化决策回归树预计器
                estimator = DecisionTreeRegressor(max_depth = 3, criterion="friedman_mse")
                # 将第 m 个 y_hat 当作标签值拟合训练集
                estimator.fit(X, y_hat_m)
                # 计算训练集在以后决策回归树的叶子结点
                leaf_ids = estimator.apply(X)
                # 每个叶子结点下蕴含的训练数据序号
                node_ids_dict = self.get_leaf_nodes(leaf_ids)
                # 叶子结点取值字典表
                gamma_dict = {}
                # 计算叶子结点取值
                for leaf_id, node_ids in node_ids_dict.items():
                    # 以后叶子结点蕴含的 y_hat
                    y_hat_sub = y_hat_m[node_ids]
                    y_hat_sub_abs = np.abs(y_hat_sub)
                    # 计算叶子结点取值
                    gamma = np.sum(y_hat_sub) / np.sum(np.multiply(y_hat_sub_abs, 1 - y_hat_sub_abs)) * (self.n_classes - 1) / self.n_classes
                    gamma_dict[leaf_id] = gamma
                    # 更新预测值
                    H[node_ids, m] += self.learning_rate * gamma
                sub_estimators.append(estimator)
                sub_gammas.append(gamma_dict)
            estimators.append(sub_estimators)
            gammas.append(sub_gammas)
        self.estimators = estimators
        self.gammas = gammas
        
    def predict(self, X):
        """梯度晋升树多分类算法预测"""
        # 初始化预测值
        H = np.ones((X.shape[0], 1)).dot(self.H0.reshape(1, -1))
        # 遍历预计器
        for k in range(self.n_estimators):
            sub_estimators = self.estimators[k]
            sub_gammas = self.gammas[k]
            # 遍历分类数
            for m in range(self.n_classes):
                estimator = sub_estimators[m]
                # 计算在以后决策回归树的叶子结点
                leaf_ids = estimator.apply(X)
                # 每个叶子结点下蕴含的训练数据序号
                node_ids_dict = self.get_leaf_nodes(leaf_ids)
                # 叶子结点取值字典表
                gamma_dict = sub_gammas[m]
                # 计算预测值
                for leaf_id, node_ids in node_ids_dict.items():
                    gamma = gamma_dict[leaf_id]
                    H[node_ids, m] += self.learning_rate * gamma
        H_exp = np.exp(H)
        H_exp_sum = np.sum(H_exp, axis = 1)
        # 计算概率
        probs = np.zeros((X.shape[0], self.n_classes))
        for m in range(self.n_classes):
            probs[:, m] = H_exp[:, m] / H_exp_sum
        return self.y_classes.take(np.argmax(probs, axis=1), axis = 0)
    
    def get_leaf_nodes(self, leaf_ids):
        """每个叶子结点下蕴含的数据序号"""
        node_ids_dict = {}
        for j in range(len(leaf_ids)):
            leaf_id = leaf_ids[j]
            node_ids = node_ids_dict.setdefault(leaf_id, [])
            node_ids.append(j)
        return node_ids_dict

七、第三方库实现

scikit-learn⁵ 实现：

from sklearn.ensemble import GradientBoostingClassifier

# 梯度晋升树分类器
clf = GradientBoostingClassifier(n_estimators = 100)
# 拟合数据集
clf = clf.fit(X, y)

scikit-learn⁶ 实现：

from sklearn.ensemble import GradientBoostingRegressor

# 梯度晋升树回归器
reg = GradientBoostingRegressor(n_estimators = 100, max_depth = 3, random_state = 0, loss = 'ls')
# 拟合数据集
reg = reg.fit(X, y)

八、示例演示

  上面三张图片别离展现了应用梯度晋升算法进行二分类，多分类与回归的后果

<center> 图 8 -1</center>

<center> 图 8 -2</center>

<center> 图 8 -3</center>

九、思维导图

<center> 图 9 -1</center>

十、参考文献

1. https://en.wikipedia.org/wiki…
2. https://www.cse.cuhk.edu.hk/i…
3. https://en.wikipedia.org/wiki…
4. https://en.wikipedia.org/wiki…
5. https://scikit-learn.org/stab…
6. https://scikit-learn.org/stab…

残缺演示请点击这里

注：本文力求精确并通俗易懂，但因为笔者也是初学者，程度无限，如文中存在谬误或脱漏之处，恳请读者通过留言的形式批评指正

本文首发于——AI 导图 ，欢送关注