由浅入深的LightGBM介绍

LightGBM是2017年初Microsoft开源的高效快速、分布式学习的梯度提升树算法，可以用于分类、回归和排序。相对比陈天奇开发的XGBoost算法，更加快速、内存消耗少。

将分几个部分来介绍：

• 监督学习基础
• 梯度提升树算法
• LightGBM与Xgboost对比
• 深入理解LightGBM的直方图算法及直方图作差加速
• LightGBM的树生长方式——leaf-wise
• LightGBM的参数说明及使用方法

监督学习基础

对监督学习来说，通过训练数据和标签学习一个模型，再用模型来预测未知类型的样本。

• 训练数据

  D = { ( X i , y i ) } ( ∣ D ∣ = n , X i ∈ R d , y i ∈ R ) \mathcal D = \{(X_i,y_i)\} \quad (|\mathcal D|=n,X_i \in \R^d,y_i \in \R) D={(Xi​,yi​)}(∣D∣=n,Xi​∈Rd,yi​∈R)

• 模型 model

  线性模型： y ^ = ∑ j w j x i j \hat{y}=\sum_jw_jx_{ij} y^​=∑j​wj​xij​，其中 $x \in R^d $

• 参数是 w w w是每个特征对应的权重： Θ = { w j ∣ j = 1 , 2 , . . . d } \Theta = \{w_j|j=1,2,...d\} Θ={wj​∣j=1,2,...d}，参数是我们要在训练数据中学到的，也就是要求的未知量。
• 损失函数（loss function）
  • 平方损失： l ( y i , y i ^ ) = ( y i − y i ^ ) 2 l(y_i,\hat{y_i})=(y_i-\hat{y_i})^2 l(yi​,yi​^​)=(yi​−yi​^​)2
  • Logistic loss： l ( y i , y ^ ) = y i l n ( 1 + e − y i ^ ) ) + ( 1 − y i ) l n ( 1 + e y i ^ ) l(y_i,\hat{y})=y_iln(1+e^{-\hat{y_i}}))+(1-y_i)ln(1+e^{\hat{y_i}}) l(yi​,y^​)=yi​ln(1+e−yi​^​))+(1−yi​)ln(1+eyi​^​)，实质上是通过sigmoid函数转化过来的。
• 正则化
  • L2正则化： Ω ( w ) = λ ∣ ∣ w ∣ ∣ 2 \Omega(w) = \lambda||w||^2 Ω(w)=λ∣∣w∣∣2
  • L1正则化： Ω ( w ) = λ ∣ ∣ w ∣ ∣ 1 \Omega(w) = \lambda||w||_1 Ω(w)=λ∣∣w∣∣1​

对于监督学习，定义一个目标函数Obj是参数 Θ \Theta Θ的函数损失函数和正则化项的和，损失函数表示模型对训练数据的拟合程度，正则化项则表示模型的复杂程度：

O b j ( Θ ) = L ( Θ ) + Ω ( Θ ) Obj(\Theta) = L(\Theta) + \Omega(\Theta) Obj(Θ)=L(Θ)+Ω(Θ)

二、梯度提升树算法

梯度提升树算法（Gradient Boosting Tree）是目前比较常用的一种算法，其实树基的算法应用比较广泛，比如随机森林、GBDT、xgboost、LightGBM、以及常用的异常检测算法Isolation Forest也是基于树的。

对于集成回归树，定义模型，假设一共有K棵树：每棵树都属于回归树空间：

y i ^ = ∑ k = 1 K f k ( x i ) , f k ∈ F w h e r e F = { f ( X ) = w q ( X ) } \hat{y_i} = \sum_{k=1}^Kf_k(x_i), \quad f_k \in \mathcal{F} \\ where \quad \mathcal F= \{f(X)=w_{q(X)}\} yi​^​=k=1∑K​fk​(xi​),fk​∈FwhereF={f(X)=wq(X)​}

参数是由两部分组成，一个是树结构（Tree structure）另一个是每个叶子节点的权重（预测值），这两个参数统一到用一个 f k f_k fk​表示，所以并不学习单独学习权重 w j ∈ R d w_j \in R^d wj​∈Rd：

Θ = { f 1 , f 2 , . . . , f K } \Theta = \{f_1,f_2,...,f_K \} Θ={f1​,f2​,...,fK​}

再定义目标函数：

O b j = ∑ i = 1 n l ( y i , y i ^ ) + ∑ k = 1 K Ω ( f k ) Obj = \sum_{i=1}^nl(y_i,\hat{y_i})+ \sum_{k=1}^K\Omega(f_k) Obj=i=1∑n​l(yi​,yi​^​)+k=1∑K​Ω(fk​)

接下来就是如果定义一棵树的复杂度了，我们知道决策树是启发式的，比如通过信息增益来进行分割(split by Information gain)、限制最大树深(max depth)、给决策树剪枝(Prune tree)及平滑叶节点(smooth leaf nodes)，这些启发式的是可以对应训练目标的，以上四个分别对应：training loss、限制函数空间的大小、通过节点个数来正则化、L2正则化。所以可以借鉴决策树，来定义集成树的正则化项，最终也是使用叶节点个数和L2正则化两项来定义，当然也可以有其它的定义方法。

目标函数我们已经有了，接下来是如何学习的问题，我们并没有使用SGD（LR模型的训练就是使用SGD的），这是由于参数是一个树模型，而不仅仅是一个向量。学习树的结构比传统的优化要难，传统的优化可以用梯度的方法。并且一下学习完所有的树是非常困难的。所以我们使用加法的方式，修正已经学习的结果，一次添加一个树。

学习使用的方法是Additive Training，加法训练，也就所说的Boosting

对于Gain理论上是正值，如果是负值，说明损失减小量已经小于正则化项了，这个时候就stop early。

实际中，在加法模型中： y i ^ ( t ) = y i ^ ( t − 1 ) + ϵ f t ( x i ) \hat{y_i}^{(t)} = \hat{y_i}^{(t-1)} + \epsilon f_t(x_i) yi​^​(t)=yi​^​(t−1)+ϵft​(xi​)，这个 ϵ \epsilon ϵ就是step-size或shinkage，通常是0.1，每一步并不是完全优化，调小可以防止过拟合，也就是每次迭代只增加一点点。

总结：

• 在每次迭代时都增加一个新树
• 在迭代前计算每个样本的 g i g_i gi​与 h i h_i hi​，这里有个问题是初始化的是 y i ^ \hat{y_i} yi​^​还是 w i w_i wi​??
• 采用贪婪的方式生成一棵树