机器学习基础---集成学习---GBDT梯度提升树

• Adaboost方法采用指数损失函数，其对噪声点较为敏感
• 因此需要一个可以应用不同损失函数函数的提升方法

• 仍然是基于决策树的加法模型
• 与Adaboost不同，不考虑样本的分布，单纯考虑最小化损失函数
• 采用前向分步方法，分步训练基学习器，每步训练的模型都是对先前累加模型的负梯度拟合

• 模型
  f M ( x ) = ∑ m = 1 M T ( x , θ m ) f_M(x)=sum_{m=1}^MT(x,theta_m) fM​(x)=m=1∑M​T(x,θm​)

• 优化目标

a r g   m i n θ L ( y , f M ( x ) ) underset{theta}{arg min}L(y,f_M(x)) θarg min​L(y,fM​(x))

• 梯度提升

  • 向量空间

    • 对函数 f ( θ ) f(theta) f(θ)，将 f ( θ t ) f(theta^t) f(θt)在 θ t − 1 theta^{t-1} θt−1处一阶泰勒展开
      f ( θ t ) ≈ f ( θ t − 1 ) + f ′ ( θ t − 1 ) Δ θ f(theta^t)approx f(theta^{t-1})+f'(theta^{t-1})Deltatheta f(θt)≈f(θt−1)+f′(θt−1)Δθ

    • 要使 f ( θ t ) > f ( θ t − 1 ) f(theta^t)>f(theta^{t-1}) f(θt)>f(θt−1)，可以取
      Δ θ = − α f ′ ( θ t − 1 ) Deltatheta=-alpha f'(theta^{t-1}) Δθ=−αf′(θt−1)
      则有：
      θ t = θ t − 1 − α f ′ ( θ t − 1 ) theta^t=theta^{t-1}-alpha f'(theta^{t-1}) θt=θt−1−αf′(θt−1)
      此处 α alpha α为步长

    • 若以上式对 θ t − 1 theta^{t-1} θt−1进行更新，可以令 f ( θ t ) > f ( θ t − 1 ) f(theta^t)>f(theta^{t-1}) f(θt)>f(θt−1)，即函数值提升

    • 此处的 θ theta θ若为标量，直接求导更新；若为向量，进行向量求导并更新

  • 函数空间与负梯度拟合

    • 对函数 g ( f ( θ ) ) g(f(theta)) g(f(θ))，同样有梯度提升更新
      f ( θ t ) = f ( θ t − 1 ) − α g ′ ( f ( θ t − 1 ) ) f(theta^t)=f(theta^{t-1})-alpha{g'(f(theta^{t-1}))} f(θt)=f(θt−1)−αg′(f(θt−1))

    • 此处不同处在于对函数负梯度 ∇ f ( θ ) g ( f ( θ ) ) nabla_{f(theta)}g(f(theta)) ∇f(θ)​g(f(θ))的求解，难以通过解析方式求解，因此考虑通过数值方法求解

    • 已知 ( f ( θ ) , g ( f ( x ) ) ) (f(theta),g(f(x))) (f(θ),g(f(x)))对，使用数值方法求得对应点处梯度，构成 ( θ , ∇ f ( θ ) g ( f ( θ ) ) ) (theta,nabla_{f(theta)}g(f(theta))) (θ,∇f(θ)​g(f(θ)))点对

    • 要求的负梯度应该是一个函数，其可以根据任意 θ theta θ求得对应的梯度，而上一步只是得到有限点处的数值梯度

    • 因此还需要引入一个用于回归的学习器，以 ( θ , ∇ f ( θ ) g ( f ( θ ) ) ) (theta,nabla_{f(theta)}g(f(theta))) (θ,∇f(θ)​g(f(θ)))点对学习 θ theta θ到梯度的映射关系

• CART回归树学习过程

  • GBDT方法使用的基分类器为CART回归树而非分类树，
    • 其具有以下优点
      • 可解释性强；有特征组合、特征选择的作用；对异常点鲁棒；容易并行；可处理混合类型特征；具有伸缩不变性；可自然处理缺失值
    • 但同时也有**缺乏平滑性（输出数值种类有限）**的缺点
  • 对 d d d维样本集 X X X训练回归树的过程大致如下：
    • 遍历当前可选特征维度，每个维度上遍历切分点，对每个切分分别计算切分之后 D 1 ,   D 2 D_1, D_2 D1​, D2​两部分的误差平方和
    • 选择对应误差平方和最小的特征及切分点进行切分，接着递归对 D 1 ,   D 2 D_1, D_2 D1​, D2​两部分进行切分直到满足约束
    • 每个子节点（不可再分样本集）对应输出值是其内部样本均值、
  • 回归树的训练过程实际上就是对样本空间各维度进行划分的过程，在划分完成后再为每个空间确定一个输出值

• 依照前向分步算法的过程逐一学习基学习器，假设已经经过 m − 1 m-1 m−1轮迭代，得到累加模型 f m − 1 ( x ) f_{m-1}(x) fm−1​(x)

• 在当前步骤下（第m步），优化目标为：
  a r g   m i n f m   L ( f m ( x ) ,   y i ) underset{f_m}{arg min} L(f_{m}(x), y_i) fm​arg min​ L(fm​(x), yi​)

  • 根据梯度提升思想，展开损失函数

  L ( f m ( x ) ,   y i ) = L ( f m − 1 ( x ) , y i ) + ∇ f m − 1 ( x ) L ( f m − 1 ( x ) , y i ) L(f_{m}(x), y_i)=L(f_{m-1}(x),y_i)+nabla_{f_{m-1}(x)}L(f_{m-1}(x),y_i) L(fm​(x), yi​)=L(fm−1​(x),yi​)+∇fm−1​(x)​L(fm−1​(x),yi​)

  ​ f m ( x ) f_m(x) fm​(x)更新：
  f m ( x ) = f m − 1 ( x ) − α ∇ f m − 1 ( x ) L ( f m − 1 ( x ) , y i ) f_m(x)=f_{m-1}(x)-alphanabla_{f_{m-1}(x)}L(f_{m-1}(x),y_i) fm​(x)=fm−1​(x)−α∇fm−1​(x)​L(fm−1​(x),yi​)
  ​ 有：
  T m ( x , θ m ) = f m ( x ) − f m − 1 ( x ) = − ∇ f m − 1 ( x ) L ( f m − 1 ( x ) , y i ) T_m(x,theta_m)=f_m(x)-f_{m-1}(x)=-nabla_{f_{m-1}(x)}L(f_{m-1}(x),y_i) Tm​(x,θm​)=fm​(x)−fm−1​(x)=−∇fm−1​(x)​L(fm−1​(x),yi​)

  • 故，第m步时建立的回归树，其目的是对损失函数对上一步累加模型的负梯度进行拟合
  • 当损失函数是平方损失函数时，负梯度正好为残差

• 初始化：
  f 0 ( x ) = a r g m i n c ∑ i = 1 n L ( y i , c ) f_0 (x)=underset{c}{argmin} sum_{i=1}^nL(y_i,c) f0​(x)=cargmin​i=1∑n​L(yi​,c)

• 对 m = 1 , 2 , … , M m=1,2,…,M m=1,2,…,M

  • 对 i = 1 , 2 , … , N i=1,2,…,N i=1,2,…,N分别计算样本点处负梯度
    − [ ∂ L ( y i , f ( x ) ) ∂ f ( x ) ] ∣ f ( x ) = f m − 1 ( x ) -[frac{partial{L(y_i,f(x))}}{partial{f(x)}}]|_{f(x)=f_{m-1}(x)} −[∂f(x)∂L(yi​,f(x))​]∣f(x)=fm−1​(x)​

  • 对负梯度点对使用回归树进行拟合，得到树 T ( x , θ m ) T(x,theta_m) T(x,θm​)，及回归树对区域的划分

  • 对各区域，计算
    c m j = a r g   m i n c ∑ x i ∈ R m j L ( y i , c m j ) c_{mj}=underset{c}{arg min}sum_{x_iin{R_{mj}}}L(y_i,c_{mj}) cmj​=carg min​xi​∈Rmj​∑​L(yi​,cmj​)

  • 更新 f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x ∈ R m j ) f_m(x)=f_{m-1}(x)+sum_{j=1}^Jc_{mj}I(xin{R_mj}) fm​(x)=fm−1​(x)+∑j=1J​cmj​I(x∈Rm​j)

• 得到最终提升树 f M ( x ) f_M(x) fM​(x)

【1】《集成学习》周志华