精华内容
下载资源
问答
  • 梯度提升决策树
    2022-04-04 09:21:47

    阅读本文需要的背景知识点:自适应增强算法、泰勒公式、One-Hot编码、一丢丢编程知识

    一、引言

      前面一节我们学习了自适应增强算法(Adaptive Boosting / AdaBoost Algorithm),是一种提升算法 (Boosting Algorithm),而该算法家族中还有另一种重要的算法——梯度提升决策树1 (Gradient Boosted Decision Trees / GBDT),GBDT 及其变体算法在传统机器学习中有着广泛的应用,了解其背后的思想与原理对于以后的学习有很大的帮助。

    二、模型介绍

      梯度提升决策树同自适应增强算法一样是一种提升算法,也可以解释为一种加法模型,第 k 轮后的强估计器为第 k - 1 轮后的强估计器加上带系数的弱估计器 h(x):

    H k ( x ) = H k − 1 ( x ) + α k h k ( x ) H_k(x) = H_{k - 1}(x) + \alpha_k h_k(x) Hk(x)=Hk1(x)+αkhk(x)

    式2-1

      假设第 k - 1 轮对应的代价函数为 C o s t ( y , H k − 1 ( X ) ) Cost(y, H_{k - 1}(X)) Cost(y,Hk1(X)), 第 k 轮对应的代价函数为 C o s t ( y , H k ( X ) ) Cost(y, H_k(X)) Cost(y,Hk(X)),我们的目的是使得每次迭代后,其代价函数都会逐渐变小。
      由于每个不同的代价函数对应的优化方式不同,Jerome H. Friedman 在其原始算法的论文2 中给出了一个统一处理的方法,可以使用代价函数的负梯度来拟合该轮迭代代价函数的减小,这也是最速下降法的一种近似,其本质是使用一阶泰勒公式近似其代价函数。当基础估计器使用的是决策回归树时,该算法被称为梯度提升决策树(GBDT)。
    y ^ k , i = − [ ∂ C o s t ( y i , H ( X i ) ) ∂ H ( X i ) ] H ( x ) = H k − 1 ( x ) \hat{y}_{k, i} = -\left[\frac{\partial Cost(y_i, H(X_i))}{\partial H(X_i)} \right]_{H(x) = H_{k-1}(x)} y^k,i=[H(Xi)Cost(yi,H(Xi))]H(x)=Hk1(x)

    式2-2

      下面还是同 AdaBoost 算法一样,分别考虑回归、二分类、多分类这三个问题,一一介绍每个问题对应的算法。由于 GBDT 算法回归比分类简单,所以这次将回归问题放在前面介绍。

    回归

      对于回归问题的代价函数,我们先使用平方误差来作为代价函数:
    C o s t ( y , H ( x ) ) = ( y − H ( x ) ) 2 Cost(y, H(x)) = (y - H(x))^2 Cost(y,H(x))=(yH(x))2

    式2-3

      第 k 轮的代价函数:
    (1)带入式 2-1
    (2)带入平方误差的代价函数
    (3)改变括号
    (4)将 y 与第 k - 1 轮的结果之差记为 y ^ k \hat{y}_k y^k
    C o s t ( y , H k ( x ) ) = C o s t ( y , H k − 1 ( x ) + α k h k ( x ) ) ( 1 ) = ( y − ( H k − 1 ( x ) + α k h k ( x ) ) ) 2 ( 2 ) = ( ( y − H k − 1 ( x ) ) − α k h k ( x ) ) 2 ( 3 ) = ( y ^ k − α k h k ( x ) ) 2 ( 4 ) \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} Cost(y,Hk(x))=Cost(y,Hk1(x)+αkhk(x))=(y(Hk1(x)+αkhk(x)))2=((yHk1(x))αkhk(x))2=(y^kαkhk(x))2(1)(2)(3)(4)

    式2-4

      观察式 2-4 中的(4)式会发现这就是前面章节中介绍的决策回归树的代价函数,只是该回归树不再是使用训练集中的 y,而是去拟合上式中的 y ^ \hat{y} y^,也可以称为残差。得到回归树后更新 H(x) ,然后进行新的迭代。
      这样就得到了最简单的最小二乘回归的 GBDT 算法实现,具体步骤可以参考第三节的算法步骤中的回归部分,可以看到其中的系数 α \alpha α 可以理解为融入到了回归树内部。
      在论文中作者还介绍了其他的几种代价函数,分别是最小绝对偏差(LDA)、Huber 损失3 等,感兴趣的读者可以阅读论文中对应的章节。

      由于 GBDT 需要计算负梯度是个连续值,所以对于分类问题, 其基础估计器没有使用分类树,而是依然使用的回归树。

    二分类

      对于分类问题的代价函数,可以使用指数函数与对数函数。当使用指数函数时,GBDT 将等同于前面一节中介绍的 AdaBoost 算法,这里我们使用对数函数作为代价函数:
    C o s t ( y , H ( x ) ) = log ⁡ ( 1 + e − 2 y H ( x ) ) Cost(y, H(x)) = \log (1 + e^{-2yH(x)}) Cost(y,H(x))=log(1+e2yH(x))

    式2-5

      按照前面模型介绍的计算负梯度的方法,带入代价函数计算出 y ^ \hat{y} y^
    y ^ k , i = − [ ∂ C o s t ( y i , H ( X i ) ) ∂ H ( X i ) ] H ( x ) = H k − 1 ( x ) ( 1 ) = 2 y i 1 + e 2 y i H k − 1 ( X i ) ( 2 ) \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} y^k,i=[H(Xi)Cost(yi,H(Xi))]H(x)=Hk1(x)=1+e2yiHk1(Xi)2yi(1)(2)

    式2-6

      计算出 y ^ \hat{y} y^ 后我们可以拟合出一颗回归树估计器 h(x) ,这时我们要求的是每轮迭代后的估计器的系数 α \alpha α
    α k = a r g m i n α ∑ i = 1 N log ⁡ ( 1 + e − 2 y i ( H k − 1 ( X i ) + α h k ( X i ) ) ) \alpha_k = \underset{\alpha}{argmin} \sum_{i = 1}^{N} \log (1 + e^{-2y_i(H_{k - 1}(X_i) + \alpha h_k(X_i))}) αk=αargmini=1Nlog(1+e2yi(Hk1(Xi)+αhk(Xi)))

    式2-7

      我们先来看下这个回归树估计器 h(x) ,其表达式可以写成下式,其中回归树一共有 J 个叶子结点, R j R_j Rj β j \beta_j βj分别代表回归树第 j 个叶子结点包含的训练集合和取值, I ( x ) I(x) I(x) 为前面章节中提到过的指示函数:
    h ( x ) = ∑ j = 1 J β j I ( x ∈ R j ) h(x) = \sum_{j = 1}^{J} \beta_j I(x \in R_j) h(x)=j=1JβjI(xRj)

    式2-8

      这时将式 2-8 带入式 2-7 中改写一下,这时就不再是求估计器的系数 alpha,转而直接求 γ \gamma γ,其中 γ k , j = α k ∗ β k , j \gamma_{k,j} = \alpha_k * \beta _{k,j} γk,j=αkβk,j
    γ k , j = a r g m i n γ ∑ X i ∈ R k , j log ⁡ ( 1 + e − 2 y i ( H k − 1 ( X i ) + γ ) ) \gamma_{k, j} = \underset{\gamma}{argmin} \sum_{X_i \in R_{k, j}}^{} \log (1 + e^{-2y_i(H_{k - 1}(X_i) + \gamma )}) γk,j=γargminXiRk,jlog(1+e2yi(Hk1(Xi)+γ))

    式2-9

      由于式 2-9 中包含了对数指数函数,导致其没有闭式解,这时可以使用二阶泰勒公式对其进行近似处理得到如下结果:
    γ k , j = ∑ X i ∈ R k , j y ^ k , i ∑ X i ∈ R k , j ∣ y ^ k , i ∣ ( 2 − ∣ y ^ k , i ∣ ) \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}|)} γk,j=XiRk,jy^k,i(2y^k,i)XiRk,jy^k,i

    式2-10

      得到 gamma 后更新 H(x) ,然后进行新的迭代。
      这样就得到了二分类的 GBDT 算法实现,具体步骤可以参考第三节的算法步骤中的二分类部分,具体的公式的来由可以参考第四节的原理证明。

    多分类

      多分类相对二分类更复杂一些,同样是使用对数函数作为其代价函数,还用到了前面多分类对数几率回归算法中介绍的 Softmax 函数,同时还需对输入的标签值 y 进行 One-Hot 编码4 操作,其代价函数如下:
    C o s t ( y , H ( x ) ) = ∑ m = 1 M y m log ⁡ p m ( x ) ( 1 ) p m ( x ) = e H m ( x ) ∑ l = 1 M e H l ( x ) ( 2 ) \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} Cost(y,H(x))pm(x)=m=1Mymlogpm(x)=l=1MeHl(x)eHm(x)(1)(2)

    式2-11

      同样按照前面模型介绍的计算负梯度的方法,带入代价函数计算出 y ^ \hat{y} y^
    y ^ k , m , i = − [ ∂ C o s t ( y i , H ( X i ) ) ∂ H ( X i ) ] H ( x ) = H k − 1 ( x ) ( 1 ) = y m , i − p k − 1 , m ( X i ) ( 2 ) \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} y^k,m,i=[H(Xi)Cost(yi,H(Xi))]H(x)=Hk1(x)=ym,ipk1,m(Xi)(1)(2)

    式2-12

      同二分类一样,拟合回归树,同时将其转化为求对应的 γ \gamma γ,不同的是需要对每一个分类都拟合一个回归树,所以多分类一共需要拟合 K * M 个决策回归树:
    γ k , m , j = a r g m i n γ ∑ i = 1 N ∑ m = 1 M C o s t ( y m , i , H k − 1 , m ( X i ) + ∑ j = 1 J γ I ( X i ∈ R k , m , j ) ) \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) γk,m,j=γargmini=1Nm=1MCost(ym,i,Hk1,m(Xi)+j=1JγI(XiRk,m,j))

    式2-13

      同样使用泰勒公式对其进行近似处理得到如下结果:
    γ k , m , j = M − 1 M ∑ X i ∈ R k , m , j y ^ k , m , i ∑ X i ∈ R k , m , j ∣ y ^ k , m , i ∣ ( 1 − ∣ y ^ k , m , i ∣ ) \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}|)} γk,m,j=MM1XiRk,m,jy^k,m,i(1y^k,m,i)XiRk,m,jy^k,m,i

    式2-14

      得到 γ \gamma γ 后更新对应分类的 H(x) ,然后进行新的迭代。
      这样就得到了多分类的 GBDT 算法实现,具体步骤可以参考第三节的算法步骤中的多分类部分。

    三、算法步骤

    回归

      假设训练集 T = { X i X_i Xi, y i y_i yi },i = 1,…,N,h(x) 为估计器,估计器的数量为 K。

    梯度提升决策树回归算法步骤如下:

    初始化 H 0 ( x ) H_0(x) H0(x),令其等于 y 的平均值 y ˉ \bar{y} yˉ
    H 0 ( X i ) = y ˉ H_0(X_i) = \bar{y} H0(Xi)=yˉ

    遍历估计器的数量 K 次:
      计算第 k 轮的残差 y ^ k \hat{y}_{k} y^k
    y ^ k , i = y i − H k − 1 ( X i ) \hat{y}_{k, i} = y_i - H_{k-1}(X_i) y^k,i=yiHk1(Xi)

      将第 k 轮 y ^ k \hat{y}_{k} y^k 当作标签值拟合训练集,得到决策回归树估计器 h k ( x ) h_k(x) hk(x)
      更新 H k ( x ) H_k(x) Hk(x)
    H k ( X i ) = H k − 1 ( X i ) + h k ( X i ) H_k(X_i) = H_{k-1}(X_i) + h_k(X_i) Hk(Xi)=Hk1(Xi)+hk(Xi)

    结束循环

    最后的预测策略:

      输入 x ,K 个决策回归树估计器依次预测后相加,然后加上初始值 H 0 H_0 H0,得到最后的预测结果
    H ( x ) = H 0 + ∑ k = 1 K h k ( x ) H(x) = H_{0} + \sum_{k = 1}^K h_k(x) H(x)=H0+k=1Khk(x)

    二分类

      假设训练集 T = { X i X_i Xi, y i y_i yi },i = 1,…,N, y i ∈ { − 1 , + 1 } y_i \in \{ -1, +1 \} yi{1,+1} ,h(x) 为估计器,估计器的数量为 K。

    梯度提升决策树二分类算法步骤如下:

    初始化 H 0 ( x ) H_0(x) H0(x),其中 y ˉ \bar{y} yˉ 为 y 的平均值
    H 0 ( X i ) = 1 2 log ⁡ 1 + y ˉ 1 − y ˉ H_0(X_i) = \frac{1}{2} \log \frac{1 + \bar{y}}{1 - \bar{y}} H0(Xi)=21log1yˉ1+yˉ

    遍历估计器的数量 K 次:
      计算第 k 轮的 y ^ k \hat{y}_{k} y^k
    y ^ k , i = 2 y i 1 + e 2 y i H k − 1 ( X i ) \hat{y}_{k,i} = \frac{2y_i}{1 + e^{2y_iH_{k-1}(X_i)}} y^k,i=1+e2yiHk1(Xi)2yi

      将第 k 轮 y ^ k \hat{y}_{k} y^k 当作标签值拟合训练集,得到决策回归树估计器 h k ( x ) h_k(x) hk(x),其中 h k ( x ) h_k(x) hk(x) 包含 J 个叶子结点
      计算第 k 轮第 j 个叶子结点的系数 γ \gamma γ,其中 R k j R_{kj} Rkj 代表第 k 轮拟合出的决策回归树估计器 h k ( x ) h_k(x) hk(x) 第 j 个叶子结点包含的训练集合
    γ k , j = ∑ X i ∈ R k , j y ^ k , i ∑ X i ∈ R k , j ∣ y ^ k , i ∣ ( 2 − ∣ y ^ k , i ∣ ) \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}|)} γk,j=XiRk,jy^k,i(2y^k,i)XiRk,jy^k,i

      更新 H k ( x ) H_k(x) Hk(x),其中 I ( x ) I(x) I(x) 为前面章节中提到过的指示函数
    H k ( X i ) = H k − 1 ( X i ) + ∑ j = 1 J γ k , j I ( X i ∈ R k , j ) H_k(X_i) = H_{k - 1}(X_i) + \sum_{j = 1}^{J} \gamma_{k,j} I(X_i \in R_{k,j}) Hk(Xi)=Hk1(Xi)+j=1Jγk,jI(XiRk,j)

    结束循环

    最后的预测策略:

      输入 x ,K 个决策回归树估计器依次判断所属叶子结点,将叶子结点对应的系数 γ \gamma γ 累加,然后加上初始值 H 0 H_0 H0,得到 H(x)
    H ( x ) = H 0 + ∑ k = 1 K ∑ j = 1 J γ k , j I ( x ∈ R k , j ) H(x) = H_0 + \sum_{k = 1}^{K}\sum_{j = 1}^{J} \gamma_{k,j} I(x \in R_{k,j}) H(x)=H0+k=1Kj=1Jγk,jI(xRk,j)

      分别计算正类和负类的概率
    {   p + ( x ) = 1 1 + e − 2 H ( x ) p − ( x ) = 1 1 + e 2 H ( x ) \left\{ \space \begin{aligned} p_+(x) &= \frac{1}{1 + e^{-2H(x)}} \\ p_-(x) &= \frac{1}{1 + e^{2H(x)}} \end{aligned} \right.  p+(x)p(x)=1+e2H(x)1=1+e2H(x)1

      取正类和负类概率中最大的分类,作为最后的分类结果
    a r g m a x m   p m ( x ) ( m ∈ { + , − } ) \underset{m}{argmax} \space p_m(x) \quad (m \in \{+ , -\}) margmax pm(x)(m{+,})

    多分类

      假设训练集 T = { X i , y i X_i, y_i Xi,yi },i = 1,…,N,y 的取值有 M 种可能,h(x) 为估计器,估计器的数量为 K。

    梯度提升决策树多分类算法步骤如下:

    对训练集中的标签值 y 进行 One-Hot 编码
    初始化 H 0 , m ( x ) H_{0,m}(x) H0,m(x),其中 m 为第 m 个分类,在原始论文中赋值为 0 ,而 scikit-learn 中的实现为各个分类的先验
    H 0 , m ( X i ) = ∑ i = 1 N I ( y i = m ) N 或 0 H_{0, m}(X_i) = \frac{\sum_{i=1}^{N}I(y_i = m)}{N} 或 0 H0,m(Xi)=Ni=1NI(yi=m)0

    遍历估计器的数量 K 次:
      遍历分类的数量 M 次:
        计算第 k - 1 轮第 m 个分类的概率 p(x)
    p k − 1 , m ( X i ) = e H k − 1 , m ( X i ) ∑ l = 1 M e H k − 1 , l ( X i ) 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)}} pk1,m(Xi)=l=1MeHk1,l(Xi)eHk1,m(Xi)

        计算第 k 轮第 m 个分类的 y ^ k , m \hat{y}_{k, m} y^k,m
    y ^ k , m , i = y m , i − p k − 1 , m ( X i ) \hat{y}_{k, m, i} = y_{m, i} - p_{k-1, m}(X_i) y^k,m,i=ym,ipk1,m(Xi)

        将第 k 轮第 m 个分类的 y ^ k , m \hat{y}_{k, m} y^k,m 当作标签值拟合训练集,得到决策回归树估计器 h k , m ( x ) h_{k,m}(x) hk,m(x),其中 h k , m ( x ) h_{k,m}(x) hk,m(x) 包含 J 个叶子结点
        计算第 k 轮第 m 个分类第 j 个叶子结点的系数 γ \gamma γ,其中 R k , m , j R_{k,m,j} Rk,m,j 代表第 k 轮第 m 个分类拟合出的决策回归树估计器 h k , m ( x ) h_{k,m}(x) hk,m(x) 第 j 个叶子结点包含的训练集合
    γ k , m , j = M − 1 M ∑ X i ∈ R k , m , j y ^ k , m , i ∑ X i ∈ R k , m , j ∣ y ^ k , m , i ∣ ( 1 − ∣ y ^ k , m , i ∣ ) \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}|)} γk,m,j=MM1XiRk,m,jy^k,m,i(1y^k,m,i)XiRk,m,jy^k,m,i

        更新 H k , m ( x ) H_{k,m}(x) Hk,m(x),其中 I ( x ) I(x) I(x) 为前面章节中提到过的指示函数
    H k , m ( X i ) = H k − 1 , m ( X i ) + ∑ j = 1 J γ k , m , j I ( X i ∈ R k , m , j ) 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}) Hk,m(Xi)=Hk1,m(Xi)+j=1Jγk,m,jI(XiRk,m,j)

      结束循环
    结束循环

    最后的预测策略:

      输入 x ,第 m 个分类对应的 K 个决策回归树估计器依次判断所属叶子结点,将叶子结点对应的系数 γ \gamma γ 累加,然后加上第 m 个分类的初始值 H 0 H_0 H0,得到第 m 个分类的 H(x)
    H m ( x ) = H 0 , m + ∑ k = 1 K ∑ j = 1 J γ k , m , j I ( x ∈ R k , m , j ) 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}) Hm(x)=H0,m+k=1Kj=1Jγk,m,jI(xRk,m,j)

      依次计算每个分类的概率
    p m ( x ) = e H m ( x ) ∑ l = 1 M e H l ( x ) p_m(x) = \frac{e^{H_m(x)}}{\sum_{l = 1}^M e^{H_l(x)}} pm(x)=l=1MeHl(x)eHm(x)

      取每个分类的概率中最大的分类,作为最后的分类结果
    a r g m a x m   p m ( x ) ( m = 1 , 2 , … , M ) \underset{m}{argmax} \space p_m(x) \quad (m = 1,2,\dots,M) margmax pm(x)(m=1,2,,M)

    四、原理证明

    回归问题初始值

      对于用平方误差作为代价函数的最小二乘回归,其初始值为 y 的均值:
    (1)回归问题的代价函数
    (2)对代价函数求导数并令其等于零
    (3)可以算出其初始值为 y 的均值
    C o s t ( H ( x ) ) = ∑ i = 1 N ( y i − H ( x ) ) 2 ( 1 ) ∂ C o s t ( H ( x ) ) ∂ H ( x ) = 2 ∑ i = 1 N ( H ( x ) − y i ) = 0 ( 2 ) H ( x ) = ∑ i = 1 N y i N = y ˉ ( 3 ) \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} Cost(H(x))H(x)Cost(H(x))H(x)=i=1N(yiH(x))2=2i=1N(H(x)yi)=0=Ni=1Nyi=yˉ(1)(2)(3)

    式4-1

      即得证

    二分类问题初始值

      对于二分类问题, y ∈ { − 1 , + 1 } y \in \{ -1, +1 \} y{1,+1}
    (1) y = + 1 y = +1 y=+1 的个数
    (2) y = − 1 y = -1 y=1 的个数
    (3)两式之和为 N
    n + = ∑ i = 1 N I ( y i = + 1 ) ( 1 ) n − = ∑ i = 1 N I ( y i = − 1 ) ( 2 ) N = n + + n − ( 3 ) \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} n+nN=i=1NI(yi=+1)=i=1NI(yi=1)=n++n(1)(2)(3)

    式4-2

    (1)y 的平均值的表达式
    (2)化简得到
    y ˉ = 1 ∗ n + + ( − 1 ) ∗ n − N ( 1 ) = n + − n − N ( 2 ) \begin{aligned} \bar{y} &= \frac{1 * n_{+} + (-1) * n_{-}}{N} & (1) \\ &= \frac{n_{+} - n_{-}}{N} & (2) \\ \end{aligned} yˉ=N1n++(1)n=Nn+n(1)(2)

    式4-3

      由式 4-2 中的(3)式和式 4-3 中的(2)式,可以分别求得如下结果:
    n + = N ( 1 + y ˉ ) 2 ( 1 ) n − = N ( 1 − y ˉ ) 2 ( 2 ) \begin{aligned} n_{+} &= \frac{N(1 + \bar{y})}{2} & (1) \\ n_{-} &= \frac{N(1 - \bar{y})}{2} & (2) \end{aligned} n+n=2N(1+yˉ)=2N(1yˉ)(1)(2)

    式4-4

    (1)二分类问题的代价函数
    (2)对代价函数求导数
    (3)将(2)式的结果拆分为两个连加的和
    (4)带入式 4-4 的结果,将连加符号去除
    (5)化简后令其等于零
    (6)最后可以算出其初始值
    C o s t ( H ( x ) ) = ∑ i = 1 N log ⁡ ( 1 + e − 2 y i H ( x ) ) ( 1 ) ∂ C o s t ( H ( x ) ) ∂ H ( x ) = − ∑ i = 1 N 2 y i 1 + e 2 y i H ( x ) ( 2 ) = − ∑ y i = + 1 2 y i 1 + e 2 y i H ( x ) − ∑ y i = − 1 2 y i 1 + e 2 y i H ( x ) ( 3 ) = − N ( 1 + y ˉ ) 2 ∗ 2 1 + e 2 H ( x ) − N ( 1 − y ˉ ) 2 ∗ − 2 1 + e − 2 H ( x ) ( 4 ) = − N ( 1 + y ˉ ) 1 + e 2 H ( x ) + N ( 1 − y ˉ ) 1 + e − 2 H ( x ) = 0 ( 5 ) H ( x ) = 1 2 log ⁡ 1 + y ˉ 1 − y ˉ ( 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} Cost(H(x))H(x)Cost(H(x))H(x)=i=1Nlog(1+e2yiH(x))=i=1N1+e2yiH(x)2yi=yi=+11+e2yiH(x)2yiyi=11+e2yiH(x)2yi=2N(1+yˉ)1+e2H(x)22N(1yˉ)1+e2H(x)2=1+e2H(x)N(1+yˉ)+1+e2H(x)N(1yˉ)=0=21log1yˉ1+yˉ(1)(2)(3)(4)(5)(6)

    式4-5

      即得证

    二分类问题系数 γ \gamma γ

      我们先来看下 γ \gamma γ 的优化目标函数:
    (1)二分类问题的代价函数
    (2)式 2-9 得到的 γ \gamma γ 的优化目标
    (3)对(2)式在 H k − 1 ( x ) H_{k - 1}(x) Hk1(x) 处进行二阶泰勒展开近似
    (4)可以看到 H ( x ) − H k − 1 ( x ) H(x) - H_{k - 1}(x) H(x)Hk1(x) 等于 γ \gamma γ
    C o s t ( H ( x ) ) = ∑ X i ∈ R k , j log ⁡ ( 1 + e − 2 y i H ( X i ) ) ( 1 ) γ k , j = a r g m i n γ ∑ X i ∈ R k , j log ⁡ ( 1 + e − 2 y i ( H k − 1 ( X i ) + γ ) ) ( 2 ) = a r g m i n γ ∑ X i ∈ R k , j C o s t ( H k − 1 ( X i ) ) + C o s t ′ ( H k − 1 ( X i ) ) ( H ( X i ) − H k − 1 ( X i ) ) + 1 2 C o s t ′ ′ ( H k − 1 ( X i ) ) ( H ( X i ) − H k − 1 ( X i ) ) 2 ( 3 ) = a r g m i n γ ∑ X i ∈ R k , j C o s t ( H k − 1 ( X i ) ) + C o s t ′ ( H k − 1 ( X i ) ) γ + 1 2 C o s t ′ ′ ( H k − 1 ( X i ) ) γ 2 ( 4 ) \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} Cost(H(x))γk,j=XiRk,jlog(1+e2yiH(Xi))=γargminXiRk,jlog(1+e2yi(Hk1(Xi)+γ))=γargminXiRk,jCost(Hk1(Xi))+Cost(Hk1(Xi))(H(Xi)Hk1(Xi))+21Cost(Hk1(Xi))(H(Xi)Hk1(Xi))2=γargminXiRk,jCost(Hk1(Xi))+Cost(Hk1(Xi))γ+21Cost(Hk1(Xi))γ2(1)(2)(3)(4)

    式4-6

      对其近似进行求解:
    (1)式 4-6 得到的 γ \gamma γ 的泰勒展开近似
    (2)对函数求导并令其为零
    (3)得到 γ \gamma γ 的结果
    ϕ ( γ ) = ∑ X i ∈ R k , j C o s t ( H k − 1 ( X i ) ) + C o s t ′ ( H k − 1 ( X i ) ) γ + 1 2 C o s t ′ ′ ( H k − 1 ( X i ) ) γ 2 ( 1 ) ∂ ϕ ( γ ) ∂ γ = ∑ X i ∈ R k , j + C o s t ′ ( H k − 1 ( X i ) ) + C o s t ′ ′ ( H k − 1 ( X i ) ) γ = 0 ( 2 ) γ = − ∑ X i ∈ R k , j C o s t ′ ( H k − 1 ( X i ) ) ∑ X i ∈ R k , j C o s t ′ ′ ( H k − 1 ( X i ) ) ( 3 ) \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} ϕ(γ)γϕ(γ)γ=XiRk,jCost(Hk1(Xi))+Cost(Hk1(Xi))γ+21Cost(Hk1(Xi))γ2=XiRk,j+Cost(Hk1(Xi))+Cost(Hk1(Xi))γ=0=XiRk,jCost(Hk1(Xi))XiRk,jCost(Hk1(Xi))(1)(2)(3)

    式4-7

      下面依次求代价函数的一阶导数和二阶导数:
    C o s t ′ ( H k − 1 ( X i ) ) = − 2 y i 1 + e 2 y i H k − 1 ( X i ) = − y i ^ ( 1 ) C o s t ′ ′ ( H k − 1 ( X i ) ) = 4 y i 2 e 2 y i H k − 1 ( X i ) ( 1 + e 2 y i H k − 1 ( X i ) ) 2 = 2 y i ^ y i − y ^ i 2 ( 2 ) \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} Cost(Hk1(Xi))Cost(Hk1(Xi))=1+e2yiHk1(Xi)2yi=yi^=(1+e2yiHk1(Xi))24yi2e2yiHk1(Xi)=2yi^yiy^i2(1)(2)

    式4-8

    (1)式 4-7 中得到的 γ \gamma γ 的表达式
    (2)带入式 4-8 得到
    (3)当 y = + 1 y = +1 y=+1 时, y ^ ∈ ( 0 , 2 ) \hat{y} \in (0, 2) y^(0,2),当 y = − 1 y = -1 y=1 时, y ^ ∈ ( − 2 , 0 ) \hat{y} \in (-2, 0) y^(2,0),所以 y ^ ∗ y = ∣ y ^ ∣ \hat{y} * y = |\hat{y}| y^y=y^
    (4)分母提出 ∣ y ^ ∣ |\hat{y}| y^
    γ = − ∑ X i ∈ R k , j C o s t ′ ( H k − 1 ( X i ) ) ∑ X i ∈ R k , j C o s t ′ ′ ( H k − 1 ( X i ) ) ( 1 ) = ∑ X i ∈ R k , j y ^ i ∑ X i ∈ R k , j ( 2 y ^ i y i − y ^ i 2 ) ( 2 ) = ∑ X i ∈ R k , j y ^ i ∑ X i ∈ R k , j ( 2 ∣ y ^ i ∣ − y ^ i 2 ) ( 3 ) = ∑ X i ∈ R k , j y ^ i ∑ X i ∈ R k , j ∣ y ^ i ∣ ( 2 − ∣ y ^ i ∣ ) ( 4 ) \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} γ=XiRk,jCost(Hk1(Xi))XiRk,jCost(Hk1(Xi))=XiRk,j(2y^iyiy^i2)XiRk,jy^i=XiRk,j(2y^iy^i2)XiRk,jy^i=XiRk,jy^i(2y^i)XiRk,jy^i(1)(2)(3)(4)

    式4-9

      即得证

    多分类问题系数 γ \gamma γ

      多分类问题的系数 γ \gamma γ 由于存在多棵树重叠,涉及到黑塞矩阵,无法像二分类一样单独求解,论文中是使用对角近似其黑塞矩阵,直接给出了结果,由于笔者能力有限,如有知道如何推导出结果的读者请留言或私信。

    五、正则化

      梯度提升树同样也需要进行正则化操作来防止过拟合的情况,其正则化的方法一般有如下几种方式:

    学习速率

      在每次迭代更新 H(x) 时增加一个学习速率 η \eta η 的超参数,下式中分别展示了学习速率 η \eta η 在不同问题中的使用方法:
    H k ( x ) = H k − 1 ( x ) + η α k h k ( x ) ( 1 ) H k ( x ) = H k − 1 ( x ) + η ∑ j = 1 J γ k , j I ( x ∈ R k , j ) ( 2 ) H k , m ( x ) = H k − 1 , m ( x ) + η ∑ j = 1 J γ k , m , j I ( x ∈ R k , m , j ) ( 3 ) \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} Hk(x)Hk(x)Hk,m(x)=Hk1(x)+ηαkhk(x)=Hk1(x)+ηj=1Jγk,jI(xRk,j)=Hk1,m(x)+ηj=1Jγk,m,jI(xRk,m,j)(1)(2)(3)

    式5-1

      其中学习速率 η ∈ ( 0 , 1 ] \eta \in (0,1] η(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-learn5 实现:

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

    scikit-learn6 实现:

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

    八、示例演示

      下面三张图片分别展示了使用梯度提升算法进行二分类,多分类与回归的结果
    0.png

    图8-1

    1.png

    图8-2

    2.png

    图8-3

    九、思维导图

    3.jpeg

    图9-1

    十、参考文献

    1. https://en.wikipedia.org/wiki/Gradient_boosting
    2. https://www.cse.cuhk.edu.hk/irwin.king/_media/presentations/2001_greedy_function_approximation_a_gradient_boosting_machine.pdf
    3. https://en.wikipedia.org/wiki/Huber_loss
    4. https://en.wikipedia.org/wiki/One-hot
    5. https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingClassifier.html
    6. https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingRegressor.html

    完整演示请点击这里

    注:本文力求准确并通俗易懂,但由于笔者也是初学者,水平有限,如文中存在错误或遗漏之处,恳请读者通过留言的方式批评指正

    本文首发于——AI导图,欢迎关注

    更多相关内容
  • 梯度提升决策树算法(GBDT)作者:江尘([受电子邮件保护])GBDT是Jerome H. Friedman的梯度提升决策树算法的高性能且功能齐全的C ++实现。 ([受电子邮件保护])GBDT是Jerome H. Friedman的“梯度增强决策树算法”...
  • 并利用梯度提升决策树(GBDT)模型对监测信息进行融合,建立了边坡稳定性预测的非线性模型,并与不同融合算法进行对比,得到如下结论:①将梯度提升决策树和有限元强度折减法相结合,可以实现边坡的位移、应力和微震等...
  • 随机梯度提升决策树,可独立使用,并通过 Python 接口。 ArXiv 上的论文: FastBDT:用于多元分类的随机梯度提升决策树的速度优化和缓存友好实现 随机梯度提升决策树被广泛用于多元分类和回归任务。 本文提出了一种...
  • 机器学习——梯度提升决策树(GBDT)

    相关文章链接:

            机器学习——人工神经网络(NN)

            机器学习——卷积神经网络(CNN)

            机器学习——循环神经网络(RNN)

            机器学习——长短期记忆(LSTM)

            机器学习——决策树(decision tree)

            机器学习——随机森林(Random forest)

            机器学习——XGboost模型

    一、提升树Boosting Decision Tree

            提升树(Boosting Decision Tree)是以CART决策树为基学习器的集成学习方法。

    GBDT提升树

            提升树实际上就是加法模型和前向分布算法,表示为:

            在前向分布算法第m步,给定当前的模型fm-1(x),求解:

            得到第m棵决策树   。不同问题的提升树的区别在于损失函数的不同,如分类用指数损失函数,回归用平方误差损失。

            当提升树采用平方损失函数时,第m次迭代表示为:

      

            称r为残差,所以第m棵决策树  是对该残差的拟合。

            要注意的是提升树算法中的基学习器CART是回归树,

    二、GBDT概念

            GBDT 的全称是 Gradient Boosting Decision Tree,梯度提升决策树,理解为梯度提升 + 决策树GB代表的是Gradient Boosting,意为梯度提升,梯度是一种数学概念,一个函数的梯度方向是函数上升最快的方向,相反的,负梯度方向是函数下降最快的方向。GBDT中所有的树都是回归树,而不是分类树,也就是说DT独指Regression Decision Tree。

            GBDT是通过采用加法模型(即基函数的线性组合),以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。

            GBDT同样由许多决策树组成,但它于随机森林有许多不同。其中之一是GBDT中的树都是回归树。决策树分为两大类,分类树和回归树。分类树用于分类标签值,如将苹果单纯的分为好与坏的是分类树;回归树用于预测实数值,如能为苹果的好坏程度打个分就是回归树。另一个不同是每棵树都是建立在前一棵树的基础上实现的

            Friedman提出了利用最速下降的近似方法,利用利用损失函数的负梯度在当前模型的值,作为回归问题中提升树算法的残差的近似值,拟合一个回归树。

            在GBDT中使用负梯度作为残差进行拟合。

    GBDT梯度提升流程

            GBDT与提升树的区别在于是残差使用梯度代替,而且每个基学习器有对应的参数权重

    三、 GBDT的流程

    GBDT的训练过程

            GBDT通过多轮迭代,每轮迭代产生一个弱分类器,每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单,并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度,(此处是可以证明的)。

            弱分类器一般会选择为CART TREE(也就是分类回归树)。由于上述高偏差和简单的要求 每个分类回归树的深度不会很深。最终的总分类器 是将每轮训练得到的弱分类器加权求和得到的(也就是加法模型)。

    步骤:

    • 针对每个类别都先训练一个回归树。
    • 对每个类别分别计算残差。
    • 重复直到迭代M轮,就得到了最后的模型。预测的时候只要找出概率最高的即为对应的类别。

    四、GBDT工作过程实例

            如年龄预测,假设训练集只有4个人A、B、C、D,他们的年龄分别是14,16,24,26.其中A,B分别是高一和高三学生;C,D分别是应届毕业生和工作两年的员工,若用一颗传统的回归决策树来训练,会得到如下图结果:

            如果使用GBDT来训练,由于数据太少,限定叶子节点最多有两个,并且限定只学两棵树,会得到下图结果:

             两图最终效果相同,为何还需要GBDT呢?答案是过拟合。过拟合是指为了让训练集精度更高,学到了很多“仅在训练集上成立的规律”导致换一个数据集当前规律就不适用了。只要允许一棵树的叶子节点足够多,训练集总是能训练到100%准确率的。在训练精度和实际精度之间,后者才是更重要的。

    五、GBDT的优缺点

    优点

    1. 相对少的调参时间情况下可以得到较高的准确率
    2. 可灵活处理各种类型数据包括连续值和离散值使用范围广
    3. 可使用一些健壮的损失函数对异常值的鲁棒性较强

    缺点

            弱学习器之间存在依赖关系,难以并行训练数据

    展开全文
  • 一、提升树 二、梯度下降 ...1.机器学习之梯度提升决策树(GBDT)_谓之小一的博客-CSDN博客_梯度提升决策树 2.GBDT的原理、公式推导、Python实现、可视化和应用 - 知乎 3. 《统计学习方法 第二版》.李航 ...

    一、提升树

            以决策树为基函数的提升方法称为提升树。其中,分类问题采用二叉分类树,回归问题采用二叉回归树。sklearn中的提升树采用的是CART树。模型可以表示为决策树的加法模型:

    f_M(x) = \sum_{m=1}^{M} T(x;\Theta _m)

     其中,T(x;\Theta _m)表示决策树,\Theta _m为决策树的参数,M为树的个数。       

    提升树算法采用前向分步算法。首先,初始确定初始提升树为f_0(x) = 0。第m步的模型是f_m(x) = f_{m-1}(x) + T(x; \Theta _m)

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

    arg \ min_{\Theta _m} \sum_{i=1}^{N}L(y_i, f_{m-1}(x_i) + T(x_i; \Theta _m))

            由于树的线性组合能很好地拟合训练数据,即使数据中的输入与输出关系很复杂也是如此,所以提升树是一个高功能的学习算法。

            不同提升树算法的区别在于所采用的损失函数不同。例如,分类树采用指数损失函数;回归树采用平方误差损失函数;一般决策树采用一般损失函数。

           

            1. 回归问题提升树

            在之前的文章中已经介绍过二叉回归树,在这里不在进行赘述。对于回归问题,提升树采用平方误差损失函数,即

    L(y, f(x)) = [y-f(x)]^2

    带入第m步得到的提升树模型,得到

    \begin{aligned} L(y, f(x)) &= [y - f(x)]^2 \\&=[y - f_{m-1}(x) - T(x; \Theta _m)]^2 \\ & =[r - T(x;\Theta _m)]^2 \end{aligned}

    其中,r = y - f_{m-1}(x)为训练数据真实值与当前模型取值的差,即拟合数据的残差。要是上述的损失函数最小,只需训练的模型更好地拟合当前模型的残差即可。

            回归问题的提升树算法可描述如下:

            输入:训练数据集D

            输出:提升树f_M(x)

            训练过程:

            ① 初始化f_0(x) = 0 

            ② 对m = 1, \2,\ ...\ , \ M

                   (a)计算残差

    r_{mi} = y_i - f_{m-1}(x_i), \ \ \ \ i=1, \ 2, \ ..., \ N

                   (b)拟合残差r_{mi},学习一个二叉回归树,得到T(x;\Theta _m)

                   (c)更新f_m = f_{m-1} + T(x; \Theta _m)

            ③ 得到回归问题提升树

    f_M(x) = \sum_{m=1}^{M} T(x; \Theta _m)

            

            2. 分类问题提升树  

            对于二分类问题,只需要将AdaBoost算法中的基学习器限制为二类分类树(只有一个根结点和两个叶子结点,高度为2的二叉树),基分类器的权重全部置为1即可。训练过程中用指数损失函数来调整样本数据的权重,从而让每个基分类器学习到不同的内容。

    二、梯度下降

            首先介绍梯度下降法的整体思想。假设你现在站在某个山峰的顶峰,在天黑前要到达山底,在不考虑安全性的基础上,如何下山最快?

            最快的方法是:以当前所在的位置为基准点,按照该点最陡峭的方向向山底前进。走一段距离后,在重新以当前点为基准点,重复上述操作,知道到底山底(最低点)。在这个过程中,需要不停地去重新定位最陡峭的方向,才不会限于局部最优。

    在下山过程中会面临两个问题:

    • 如何测量山峰的“陡峭”程度;这就是梯度。梯度是一个向量,梯度的方向是函数在指定点上升最快的方向,那么梯度的反方向自然就是下降最快的方向。计算方式是函数求偏导。

    • 每一步需要走多远;走太长距离,可能会错过最佳路线;最太短,下降速度会比较慢。这是步长。

            当前位置的梯度表示为\frac{\partial f}{\partial \theta },取步长\alpha,则下一步所在的位置如下:

    { \theta}' = \theta _m - \alpha \frac{\partial f}{\partial \theta }|_{\theta =\theta _m}

            总结:梯度下降用来求某个函数取最小值时,自变量对应的取值。

            

            1. 机器学习任务中的梯度下降

            在机器学习任务中,梯度下降一般运用在通过损失函数L(\theta )最小化求解模型参数\theta中。使用梯度下降算法求解最优模型参数\theta的过程如下:

            (1)确定当前位置\theta _t处的损失函数的梯度\frac{\partial L(\theta )}{\partial \theta _{t}}

            (2)用步长\eta乘以损失函数的梯度,得到当前位置下降的距离,即:\eta * \frac{\partial L(\theta )}{\partial \theta _t}

            (3)判断梯度下降的距离是否小于阈值\varepsilon,如果小于,则算法终止,当前的\theta _t即为求得的最优参数;否则进入步骤(4);

            (4)更新\theta _t,其更新表达式为\theta _t = \theta _t - \eta * \frac{\partial L(\theta )}{\partial \theta _t}。更新后继续转入步骤(1)。

           

            从泰勒公式的角度理解梯度下降:

            (1)首先,给出迭代公式:\theta _t = \theta _{t-1} + \Delta \theta

            (2)将L(\theta _t)\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 _t) - L(\theta _{t-1}) \approx {L}'(\theta _{t-1})\Delta \theta

            其中,{L}'(\theta _{t-1})\Delta \theta均为向量,{L}'(\theta _{t-1})\Delta \theta表示二者点乘,当二者方向相同,即夹角为0时,点乘的值最大。这个点乘代表了从L(\theta _{t-1})L(\theta _t)函数值的上升量。{L}'(\theta _{t-1})L(\theta _{t-1})\theta _{t-1}处的梯度,这也说明了当\Delta \theta与梯度方向相同时,函数值上升最快;反之,如果\Delta \theta与负梯度方向相同(与梯度方向相反时),函数梯度下降的最快。所以\Delta \theta可以取-\eta{L}'(\theta _{t-1}),此时,\Delta \theta与负梯度方向相同,函数值下降最快,这正式所需要的,因为目标是最小化损失函数,损失函数值下降的越快越好。于是,参数的迭代公式如下:

    \theta _t = \theta _{t-1} - \eta {L}'(\theta _{t-1})

    三、梯度提升树(GBDT)

            在提升树算法中,对于损失函数采用平方误差或者指数损失时,每一步的优化是比较简单的,但是对于一般损失函数,则很难进行。针对这一问题,Friedman提出了梯度提升树算法,利用最速下降的近似方法,将当前模型的损失函数的负梯度作为提升树算法中残差的近似值,即每一步的基学习器(CART回归树)拟合损失函数的负梯度。

           

             1. Boosting算法中的梯度下降

           梯度提升算法有梯度下降和Boosting两部分组成。常规的梯度下降是在参数空间进行地,目的是得到最优的模型参数。这里的梯度下降是在函数空间进行,目的是得到最优的模型。

            提升树第m步的模型可以表示为:

            f_m(x) = f_{m-1}(x) + T(x;\Theta _m)

      其中,f_{m-1}(x)是已知的,所以求出T(x;\Theta _m)也就求得f_m(x)。此时,要优化的损失函数如下:

    min_ {T(x;\Theta _m)} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + T(x_i;\Theta _m))

    L(y_i, f_{m-1}(x_i) + T(x_i;\Theta _m))f_{m-1}(x)处进行一阶泰勒展开:

    L(y_i, f_{m-1}(x_i) + T(x_i;\Theta _m)) \approx L(y_i, f_{m-1}(x_i)) + \frac{\partial {L}'(y_i, f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}T(x_i;\Theta _m)

    可以发现公式中的梯度变量变为模型(函数),所以说是在函数空间进行的梯度下降。在常规的梯度下降中,为了使损失函数下降最快,到这一步后是直接取负梯度乘上步长来更新参数;但是在Boosting算法中,我们要更新的是模型,而不是参数,所以只能让模型来拟合负梯度,即在第m步中,T(x_i;\Theta _m)的求解公式如下:

    T(x_i;\Theta _m) = argmin_{T \in \tau } \sum_{i=1}^{N} [ -\frac{\partial {L}'(y_i, f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}- T(x_i; \Theta _m)]^2

    求出T(x;\Theta _m)就可以求出f_m(x)

            

            2. GBDT回归树

            处理回归问题时,GBDT一般使用平方误差损失函数,损失函数的负梯度即为残差。平方误差损失函数如下:

    L(y, f(x)) = \frac{1}{2}[y- f(x)]^2

    f_{m-1}(x_i)求梯度得

    -\frac{\partial L(y_i, f_{m-1}(x_i))}{\partial f_{m-1}(x_i)} = y_i - f_{m-1}(x_i)

            GBDT回归树的训练流程如下

            输入:训练数据集\{(x_1, y_1), \ (x_2, y_2), \ ...., \(x_N, y_N) \},损失函数L(y, f(x))(一般是平方误差损失函数),学习率\lambda(梯度下降算法中的步长);

            输出:回归树f(x)

            训练过程:

            ① 初始化

    f_0(x) = arg\ min_c \sum_{i=1}^{N} \ L(y_i, c)

    在损失函数是平方误差损失函数时,取标签的平均值。

            ② 对m = 1, \ 2, \ ... \ , \ M

                    (a)对i = 1, \2, \, ...\ , N,计算

    r_{mi} = -\lambda [\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} ] _{f_{m-1}(x_i)}

    当损失函数为平方误差损失函数时,负梯度等于残差。

                    (b)对r_{mi}拟合一个CART回归树,得到第m棵树的叶结点区域R_{mj}, \ \ \ j = 1. \ 2, \ ... \ , \ J

                    (c)对j = 1, \ 2, \ ... \ , \ J,计算

    c_{mj} = arg \ min_{c} \sum_{x \in R_{mj}}^{} L(y_i, f_{m-1}(x_i) + c)

    利用线性搜索估计叶结点区域的值,使得损失函数极小化。损失函数为平方误差损失函数时,c_{mj}等于第j个叶结点区域的全部样本标签的平均值。

                    (d)更新f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J} c_{mj}I(x \in R_{mj})

            ③ 得到回归树

    \hat{f}(x) = f_M(x) = \sum_{m=1}^{M}\sum_{j=1}^{J} c_{mj} I(x \in R_{mj})

            在训练过程中,如果选择了合适的步长\lambda,损失函数的梯度是逐渐递减的,当损失函数的梯度为0时,达到极值点,此时,残差也必然接近0,损失函数获得最小值。因此,迭代生成CART树的过程本质是梯度减小的过程,是一个二次函数优化的过程。

            3. GBDT分类树

           对于分类问题,GBDT的基学习器也是CART回归树。与回归问题的区别在于使用的损失函数不同。分类问题通常使用交叉熵作为损失函数,交叉熵损失函数形式如下:

    L(y, f(x)) =- \sum_{i=1}^{N}\sum_{j=1}^{M} y_{ij}logf(x_{ij})

    其中,i表示样本数量,j表示类别数量,y_{ij}表示第i个样本属于第j个类别,f(x_{ij})表示将i个样本预测为第j个类别的概率。

            CART回归树的叶子结点值是一个实数,对于回归问题,由损失函数最优化,可得叶子结点的取值为样本标签的均值。由于分类问题,样本标签是离散值,使用交叉熵损失函数,所以需要把预测的实数转换成概率。

            (1)二分类问题

           在二分类问题中(类别标签取值为0或者1),可以与逻辑回归一样,使用Sigmoid函数即可把实数值转变成概率形式,如下:

    f(x) = \frac{1}{1+ e^{-x}}

      其倒数为:{f}'(x) = f(x)(1-f(x))

            首先,求各叶结点的取值

            二分类问题中,使用的交叉熵损失函数,可写成如下形式:

    L(y, f(x)) =- \sum_{i=1}^{N} [y_i logf(x_i) + (1-y_i)log(1-f(x_i))]

            假设,在生成CART树的过程中,第m轮的树为F_m(x) = F_{m-1}(x) + T(x;\Theta _m),样本被预测为正样本的概率可以用如下形式表示:

    p = \frac{1}{1+e^{-F_m(x)}}

            损失函数为:

    \begin{aligned}L(y, F_m(x)) &= L(y, F_{m-1}(x) + T(x;\Theta _m)) \\&=-\sum_{i=1}^{N} [y_ilogp_i + (1-y_i)log(1-p_i)] \end{aligend}

            由一阶泰勒展开式

    L(y, F_m(x)) = L(y, F_{m-1}(x) + T(x;\Theta _m)) \approx L(y, F_{m-1}(x)) + {L}'(y, F_{m-1}(x))T(x;\Theta _m)

    其中,T(x;\Theta _m)为各叶结点的取得的实数值。上述式子对{F}'_{m-1}(x)求导:

    \begin{aligned} {L}'(y, F_m(x)) &= {L}'(y, F_{m-1}(x)) + {L}''(y, F_{m-1}(x))T(x;\Theta _m) \\ &= \frac{\partial L}{\partial p} \frac{\partial p}{\partial F_{m-1}(x)} + {[\frac{\partial L}{\partial p} \frac{\partial p}{\partial F_{m-1}(x)}]}'T(x;\Theta _m) \\ &= \sum_{i=1}^{N} (p_i - y_i) + [\sum_{i=1}^{N} p_i(1 - p_i) ]T(x;\Theta _m) \end{aligned}

            由于,导数为0时,可以取得最优值,令上述导数为0,可求得:

    \begin{aligned} T(x;\Theta _m) &= \frac{\sum_{i=1}^{N}(p_i -y_i)}{\sum_{i=1}^{N} p_i(1-p_i)} \\ &= \frac{\sum_{i=1}^{N} r_{mi}}{\sum_{i=1}^{N} (y_i - r_{mi})(1-y_i + r_{mi})}\end{aligned}

    以上,即为第m生成的叶结点的取值。

            下面,来求初始值F_0(x) = c,损失函数函数:

    L(y, F_0(x)) = -\sum_{i=1}^{N} [y_i log p_i + (1-y_i)log(1-p_i)]

    其中,p_i = \frac{1}{1+ e^{-F_0(x_i)}}= \frac{1}{1+ e^{-c}}为常数,L(y, F_0(x))p_i求导,并且令导数为0,此时,损失函数取得最优值,求得:

    \sum_{i=1}^{N} (p_i- y_i) = 0, \ \ \ p_i = p = \frac{1}{N}\sum_{i=1}^{N}y_i

    从而求得:F_0(x) = c = log \frac{p}{1-p} = log\frac{\sum_{i=1}^{N}y_i}{\sum _{i=1}^{N}(1-y_i)}

            

     GBDT二分类树的训练流程如下

            输入:训练数据集\{(x_1, y_1), \ (x_2, y_2), \ ...., \(x_N, y_N) \},其中,y_i \in \{0, 1\},损失函数L(y, f(x))(一般是交叉熵损失函数),学习率\lambda(梯度下降算法中的步长);

            输出:二分类树f(x)

            训练过程:

            ① 初始化

    f_0(x) = arg\ min_c \sum_{i=1}^{N} \ L(y_i, c)

    在损失函数是交叉熵损失函数时,c = log\frac{\sum_{i=1}^{N}y_i}{\sum_{i=1}^{N}(1-y_i)}

            ② 对m = 1, \ 2, \ ... \ , \ M

                    (a)对i = 1, \2, \, ...\ , N,计算

    r_{mi} = -\lambda [\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} ] _{f_{m-1}(x_i)}

    当损失函数时交叉熵时,负梯度等于残差。

                    (b)对r_{mi}拟合一个CART回归树,得到第m棵树的叶结点区域R_{mj}, \ \ \ j = 1. \ 2, \ ... \ , \ J

                    (c)对j = 1, \ 2, \ ... \ , \ J,计算

    c_{mj} = arg \ min_{c} \sum_{x \in R_{mj}}^{} L(y_i, f_{m-1}(x_i) + c)

    利用线性搜索估计叶结点区域的值,使得损失函数极小化。损失函数为交叉熵损失函数时,

    c_{mj} = \frac{\sum_{x_i \in R_{mj}} r_{m,i}}{\sum_{x_i \in R_{mj}}(y_i-r_{m,i})(1-y_i+r_{m, i})}

                    (d)更新f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J} c_{mj}I(x \in R_{mj})

            ③ 得到二分类树

    \hat{f}(x) = \frac{1}{1+e^{-f_M(x) }}= \frac{1}{1+e^{-\sum_{m=1}^{M}\sum_{j=1}^{J} c_{mj} I(x \in R_{mj})}}

            分类和回归中所使用的到回归树是一样的,传入属性值作为分裂待选结点,利用残差作为目标值,回归树regression_tree使用平方差函数作为信息增益函数。

            (2)多分类问题

            二分类可拓展至多分类,采用one vs rest的策略,假设有s个类别,则每轮需要训练s棵树,每一棵树用来判断是否属于其中的一个类别。其中,样本的类型标签,需要进行one-hot处理,生成s为列向量。第m轮,第k棵树(用来识别类别k),CART树为F_{m,k},利用softmax函数可以将F_{m,k}转化为概率:

    P(y_i=k|x_i) = \frac{e^{F_{m,k}(x_i)}}{\sum_{t=1}^{s}e^{F_{m,t}(x_i)}}

            使用交叉熵作为损失函数,得到如下损失函数表达式:

    \begin{aligned} L(y, F_m(x)) &= -\sum_{i=1}^{N}y_i \sum_{j=1}^{s} log P_{i,j} \\ &= -\sum_{i=1}^{N}\sum_{j=1}^{S}y_i log \frac{e^{F_m,j(x_i)}}{\sum_{t=1}^{s}e^{F_{m,t}(x_i)}} \end{aligned}

    利用softmax函数性质,损失函数对m轮第q棵树求导,可得:

    \frac{\partial L}{\partial F_{m,q}} = - (y_i - P_q)

    可以看出,GBDT的多分类仍然是残差的形式。

            

             GBDT多分类树的训练流程如下

            输入:训练数据集\{(x_1, y_1), \ (x_2, y_2), \ ...., \(x_N, y_N) \},其中,y_i \in \{0, 1, \ ... \ , s \},损失函数L(y, f(x))(一般是交叉熵损失函数),学习率\lambda(梯度下降算法中的步长);

            输出:s棵二分类树f_1(x), f_2(x), ..., f_s(x)

            训练过程:

            ① 对样本的类别标签进行one-hot向量化,生成s * N维类别向量,每行数据只含有0或1,即为二分类问题。

            ② 初始化s棵树的初始值

    f_{0,k}(x) = 0  或 f_{0,k}(x) = \frac{count(k)}{N}, \ \ \ , k = 1, 2, ..., s

            ③ 对m = 1, \2, \, ...\ , M 

                    (a)对k = 1, 2, \ ... \ , s

                            (i)对i = 1, \2, \, ...\ , N,利用softmax函数,计算出第i个样本属于第s个类别的概率:

    P(y_i=k|x_i) = \frac{e^{F_{m,k}(x_i)}}{\sum_{t=1}^{s}e^{F_{m,t}(x_i)}}

                            (ii)对i = 1, \2, \, ...\ , N,计算负梯度,由上述描述可知,亦为样本的残差

       r_{m,k,i} = -\lambda [\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} ] _{f_{m-1,k}(x_i)} = y_{i,k} - P_k(x_i)

                    (b)对r_{m,k,i},拟合一棵CART回归树,得到第m轮,第k棵树的叶结点区域R_{mj, k}, \ \ \ j = 1, \ 2, \ ... \ , \ J

                    (c)对j = 1, \ 2, \ ... \ , \ J,计算

    c_{m,k,j} = arg \ min_{c} \sum_{x \in R_{m,k,j}}^{} L(y_i, f_{m-1,k}(x_i) + c)

    利用线性搜索估计叶结点区域的值,使得损失函数极小化。损失函数为交叉熵损失函数时,

    c_{m,k,j} =\frac{s-1}{s} \frac{\sum_{x_i \in R_{m,k,j}} r_{m,k,i}}{\sum_{x_i \in R_{m,k,j}}(|r_{m,k,i}|)(1-|r_{m,k, i}|)}

                    (d)更新

    f_{m,k}(x) = f_{m-1,k}(x) + \sum_{j=1}^{J} c_{m,k,j}I(x \in R_{m,k,j})

            ③ 得到s棵二分类树

    P_k(x) = f_{M,k} (x)= \frac{e^{(f_{m,k}(x))}}{\sum_{t=1}^{s}e^{(f_{m,t}(x))}} = \frac{e^{\sum_{m=1}^{M}\sum_{j=1}^{J} c_{m,k,j}I(x \in R_{m,k,j})}}{\sum_{t=1}^{s}e^{\sum_{m=1}^{M}\sum_{j=1}^{J} c_{m,t,j}I(x \in R_{m,t,j})}}

    label = arg \ max_k P_k(x)

    四、GBDT特征重要度的计算

           Friedman在GBM的论文中提出的方法: 特征j的全局重要性,通过特征j在单棵树中的重要度的均值来衡量,即

    Importance_j = \frac{1}{M} \sum_{m=1}^{M} Importance_{m,j}

    其中,Importance_{m,j}表示特征j在第m轮训练的CART回归树中的重要度。

    Importance_{m,j} = \sum_{t=1}^{L-1} i_t I(v_t=j)

    其中,t表示第m棵树的内部结点,L为树的叶结点数(由完全二叉树的性质,树的内部结点数=叶结点数-1),mse(i_t)表示,在结点t分裂后减小的平方误差损失,v_t表示当前结点分裂时使用的特征。

    五、优缺点

    (1)GBDT算法优点

    • 预测精度高
    • 适合低维数据
    • 能处理非线性数据
    • 可以灵活处理各类型的数据,包括连续值和离散值
    • 在相对少的调参时间情况下,预测的准确率也可以比较高(这是相对SVM来说的)
    • 使用一些健壮的损失函数,对异常值的鲁棒性非常棒,比如Huber损失函数和Quantile损失函数

    (2)GBDT算法缺点

    • 由于弱学习器之间存在依赖关系,难以进行并行训练数据,不过可以通过自采用的SGBT来达到部分并行
    • 数据维度较高时,会加大算法的计算复杂度

    六、GBDT与AdaBoost的区别

    •  GBDT集成的对象必须是CART回归树,而AdaBoosting集成目标是弱分类器
    • 两者迭代的方式也有区别,AdaBoosting利用上一轮错误率来更新下一轮分类器的权重、从而实现最终识别能力的提升;而GBDT使用梯度来实现模型的提升,算法中利用残差来拟合梯度,通过不断减小残差实现梯度的下降

    附录

    1. 机器学习之梯度提升决策树(GBDT)_谓之小一的博客-CSDN博客_梯度提升决策树

    2. GBDT的原理、公式推导、Python实现、可视化和应用 - 知乎

    3. 《统计学习方法 第二版》.李航

    4. GBDT算法——理论与sklearn代码实现 - 知乎

    5. Sklearn参数详解—GBDT - 百度文库

    6. GBDT算法的特征重要度计算_yangxudong的博客-CSDN博客_gbdt特征重要性

    7. 梯度提升决策树-GBDT

    8. 通俗易懂讲解梯度下降法 - 知乎

    9. 梯度下降(详解)_流年若逝的博客-CSDN博客_梯度下降

    10. GBDT原理与实践-多分类篇_kingsam_的博客-CSDN博客_gbdt多分类

    11. GBDT算法的优缺点_suv1234的博客-CSDN博客_gbdt优点

    展开全文
  • GBDT梯度提升决策树

    2022-04-16 19:47:03
    一、GBDT梯度提升决策树的概念 GBDT算法是是有boosting思想和决策树组成的,是一个由多个弱学习器组成的集成学习。GBDT算法的每一个弱学习器模型的建立是为了消除上一次的残差(使用函数空间梯度下降的方法) 注意:...

    一、GBDT梯度提升决策树的概念

    GBDT算法是是有boosting思想和决策树组成的,是一个由多个弱学习器组成的集成学习。GBDT算法的每一个弱学习器模型的建立是为了消除上一次的残差(使用函数空间梯度下降的方法)

    注意:残差是通过损失的出来的,学习率shrinkage 得用

    二、GBDT应用于回归(残差、负梯度、回归树)

    1、回归树

    2、每棵树训练的真实值是负梯度(残差)

    3、GBDT应用于回归问题的总体流程

    4、GBDT应用于回归问题总结

      

     三、应用GBDT做二分类任务

    1、原理

    分类模型的预测y_hat  

    其中就是学习到的决策树 (弱学习器)

    使用逻辑回归作为二分类任务的base model

    则单个样本的损失函数为

     

     2、GBDT应用于二分类算法流程总结

    注意: 这个负梯度的是传给下一时刻的预期值的

     

     

     四、GBDT做多分类任务

    1、原理

    使用softmax作为base model

    每个样本属于每个类别的概率

     

    五、GBDT用于回归、二分类、多分类任务的相同点和不同点:

    1、相同点:

                 都是使用残差拟合下一棵树,使用了回归树

                 分裂指标都是mse

    2、不同点:

    •  使用损失函数的不同

    • 叶子节点分值计算不同

    • 初始值的方式不同

    六、叶子节点分值计算

     

    1、回归的叶子节点分值是求平均

    2、二分类的叶子节点分支

     于是我们所得到叶子分值的近似值 

     

     

    3、多分类的叶子节点分支

    七、特征选择

     

     

    八、特征组合降维在GBDT+LR架构上的应用

    1、架构图

     

    2、流程

    2.1 训练

    • 训练好GBDT用作二分类的强学习器
    • 把GBDT训练好的模型的特征进行编码
    • 训练lr模型

    2.2 预测

    • 新的数据进入gbdt获取到特征编码(one-hot)
    • 把特征编码后的进行逻辑回归预测

     

    展开全文
  • 一个基于梯度提升决策树的商品推荐算法,吕超,朱郑州,在个性化推荐领域,如何使用海量数据设计出合理的用户画像和商品画像,严重影响到推荐效果。本文基于梯度提升决策理论,使用海量
  • 梯度提升决策树(GBDT)1 基于残差学习的梯度提升树2 梯度提升决策树(GBDT)3 算法实践 梯度提升决策树(GBDT),在传统机器学习中算得上是TOP3的算法。GBDT使用的基学习器是CART回归树,而且无论是回归还是分类,...
  • 提升树(Boosting Tree)是以分类或者回归位基本分类器到提升方法,提升树被认为是统计学习中性能最好的方法之一 Boosting方法训练基分类器时采用串行的方式,各个基分类器之间有依赖。它的基本思路是将基分类器...
  • 梯度提升决策树 GBRT,Gradient Boosting Regression Tree,梯度回归树 MART,Multiple Additive Regression Tree,多重累加回归树 GBDT是一种迭代的决策树算法,由多棵回归决策树组成,将所有决策树的输出累加作为...
  • 原理: 决策树生成算法: 是递归地生成决策树,它往往分类精细,对训练数据集分类准确,但是对未知数据集却没有那么准确,有比较...梯度提升决策树按照一定的次序搭建多个分类模型。模型之间彼此存在依赖关系。后续加入
  • 摘要:GBDT是一种性能非常好的机器学习模型...用于实战的完整版GBDT是比较复杂的,为了降低学习曲线,这里首先介绍了GBDT的核心,即如何基于目标函数得到每棵CART的拟合目标,然后列举了常见的用于提升GBDT效果的策...
  • CatBoost 一种基于梯度提升决策树的机器学习方法。CatBoost is a machine learning method based on gradient boosting over decision trees。
  • Gradient Boosting Decision Tree 1. 构建与使用 1.1 构建 Windows: 使用 Visual Studio 2017 打开解决方案并生成即可。 Linux: 根目录提供了 makefile 文件,使用 make 编译即可,需要 gcc >= 5.4.0 ...
  • GBDT梯度提升决策树与GBRT梯度提升回归树原理详解 1提升树的原理 2 提升树算法 3GBDT与GBRT 4 GBRT的数学实例 5 API详解 补充集成学习的多样性增强 总结:集成学习中各个算法分别如何做分类和回归的 学GBDT,GBRT之前...
  • 使用梯度提升决策树构建预测模型的demo
  • GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree),是一种迭代的决策树算法,该算法由多棵决策树组成,所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是...
  • 梯度提升决策树(GBDT)由于准确率高、训练快速等优点,被广泛应用到分类、回归合排序问题中。该算法是一种additive树模型,每棵树学习之前additive树模型的残差。许多研究者相继提出XGBoost、LightGBM等,又进一步...
  • 梯度提升决策树(GBDT:GradientBoostingDecisionTree)算法是集成学习中boosting的一种。总体思路是利用每个弱学习器计算当前输出与真实值的残差,然后讲每个学习器输出的残差进行累加,以求接近真实值。训练过程...
  • 机器学习之梯度提升决策树(GBDT)

    千次阅读 2020-08-24 17:42:48
    GBDT(Gradient Boosting Decision Tree),全名叫梯度提升决策树,使用的是Boosting的思想。 1.1 Boosting 思想 Boosting方法训练基分类器时采用串行的方式,各个基分类器之间有依赖。它的基本思路是将基分类器层层...
  • 梯度提升决策树(Gradient Boosting Decision Tree,GBDT)

    万次阅读 多人点赞 2019-07-07 15:09:56
    梯度提升决策树(Gradient Boosting Decision Tree,GBDT) 集成学习的系列博客: 集成学习(ensemble learning)基础知识 随机森林(random forest) AdaBoost算法(一)——基础知识篇 AdaBoost算法(二)——...
  • 1. 梯度提升决策树概述 梯度提升决策树(Gradient Boosting Decision Tree,GBDT)是以决策树为基学习器的一种Boosting算法,它在每一轮迭代中建立一个决策树,使当前模型的残差在梯度方向上减少;然后将该决策树与...
  • 今天是周末,之前给自己定了一个小目标:每周都要写一篇博客,不管是关于什么内容的都行,关键在于总结和思考,今天我选的主题是梯度提升树的一些方法,主要从这些方法的原理以及实现过程入手讲解这个问题。...
  • 机器学习之梯度提升决策树(GBDT)

    万次阅读 多人点赞 2018-05-02 16:16:06
    GBDT(Gradient Boosting Decision Tree)是一种迭代的决策树算法,由多棵决策树组成,所有树的结论累加起来作为最终答案,我们根据其名字(Gradient Boosting Decision Tree)来展开推导过程。决策树(Decision Tree)...
  • 文章目录总结综述一、Regression Decision Tree:回归树二、Boosting Decision Tree:提升树算法三、Gradient Boosting Decision Tree:梯度提升决策树四、重要参数的意义及设置五、拓展 总结 回归树: 用均方误差的...
  • GBDT(Gradient Boosting Decision Tree,梯度提升决策树),由名字可以看出涉及到三点: 1、boosting 简单讲,就是每次训练单个弱学习器时,都将上一次分错的数据权重提高一点再进行当前单个弱学习器的学习。这样...
  • 梯度提升决策树 英文是Gradient Boosting Decision Tree (GBDT)。是一种迭代的决策树算法,由多棵决策树组成,将所有树的结论累加起来做最终答案。值得注意的是,GBDT中的树都是回归树,不是分类树。GBDT主要用于...
  • GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree),是一种迭代的决策树算法,该算法由多棵决策树组成,所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是...
  • 梯度提升决策树

    2021-04-13 12:05:58
    待完成

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,342
精华内容 6,136
关键字:

梯度提升决策树

友情链接: canvas_baozha.zip