逻辑回归(Logistic Regression, LR)

逻辑回归是一种广义线性模型，通过对数概率函数，将线性函数的结果进行映射，从而将目标函数的取值空间从\((- \infinity ,+\infinity)\)映射到了\((0,1)\)，从而可以处理分类问题。注意：逻辑回归是一种分类算法。

• 前置知识

  • 对数概率函数

    又称对数几率函数，sigmoid函数等。函数表达式：
    \[
    g(z)=\frac{1}{1+e^{-z}}
    \]
    s形曲线，值域：\((0,1)\)

    且其导数满足：
    \[
    g'(z)=g(z)(1-g(z))
    \]

  • 梯度

    梯度的本质是一个向量(矢量)，表示某一函数在该点处的方向导数沿着该方向能够取得最大值，即函数在该点处沿着梯度的方向变化最快，变化率最大。

    参见：梯度-百度百科

  • 指数运算法则
    \[
    log_a\prod_{i=0}^m h(x)=\sum_{i=0}^m log_ah(x)\\
    log_aM^n=nlog_aM
    \]

• 定义

  二项逻辑回归模型的条件概率分布：
  \[
  P(Y=1|X)=\frac{1}{1+e^{-\theta ^Tx}}\\
  P(Y=0|X)=1-\frac{1}{1+e^{-\theta ^Tx}}
  \]
  其中，\(x\in R^n\)是输入，\(Y\in \{0,1\}\)是输出，\(\theta ^T\)是待学习参数。对于给定的输入实例\(X\)，将样本\(X\)输入到上述公式中求得\(P(Y=1|X)\)和\(P(Y=0|X)\)，比较两个条件概率值，将样本归到条件概率值较大的那一类。

• 梯度下降法求解逻辑回归
  \[
  h_\theta=\frac{1}{1+e^{-\theta^Tx}}
  \]
  即：
  \[
  h_\theta=g(\theta^Tx)
  \]
  其中，\(g(z)\)为上述的对数概率函数或称sigmoid函数

  构造对应的最大似然：
  \[
  L(\theta)=\prod_{i=1}^mP(y_i|x_i;\theta)=\prod_{i=1}^{m}(h_{\theta}(x))^y(1-h_{\theta}(x))^{1-y}
  \]
  两端取对数：
  \[
  l(\theta)=logL(\theta)=\sum_{i=1}^{m}(y_ilogh_{\theta}(x_i)+(1-y_i)log(1-h_{\theta}(x_i)))
  \]
  为简化问题，现在以只有一个训练样本的情况为例(实际这种情形就是随机梯度下降)：
  \[
  l(\theta)=ylogh_{\theta}(x)+(1-y)log(1-h_\theta(x))\\
  \]
  对参数\(\theta\)求偏导：
  \[
  \frac{\partial}{\partial \theta_j} l(\theta)=(y\frac{1}{g(\theta^Tx)}-(1-y)\frac{1}{1-g(\theta^Tx)})\frac{\partial}{\partial \theta_j}g(\theta^Tx)\\
  \frac{\partial}{\partial \theta_j} l(\theta)=(y\frac{1}{g(\theta^Tx)}-(1-y)\frac{1}{1-g(\theta^Tx)})g(\theta^Tx)(1-g(\theta^Tx))\frac{\partial}{\partial\theta_j}\theta^Tx\qquad 该步使用g'(z)=g(z)(1-g(z))\\
  \frac{\partial}{\partial \theta_j} l(\theta)=(y(1-g(\theta^Tx))-(1-y)g(\theta^Tx))x_j\qquad 注意：\frac{\partial}{\partial \theta_j}\theta^Tx=x_j，x_j为样本x的第j个特征\\
  \frac{\partial}{\partial \theta_j} l(\theta)=(y-h_{\theta}(x))x_j\qquad 整理结果
  \]
  求得参数梯度，现在希望最大化似然函数，因此梯度上升，迭代参数。参数\(\theta\)的迭代公式：
  \[
  \theta_{j+1}:=\theta_j+\alpha(y-h_{\theta}(x))x_j
  \]
  其中，\(\alpha\)为学习率，\((y-h_{\theta}(x))x_j\)为上述所求得的梯度

  推广至m个样本：
  \[
  \theta_{j+1}:=\theta_j+\alpha\frac{1}{m}\sum_{i=1}^m(y^i-h_{\theta}(x^i))x^{i}_j
  \]

• 逻辑回归算法流程

  输入：训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)},x_1\in X \subseteq R^n,y_1\in Y \subseteq R^n $

  输出：逻辑回归模型\(\hat f(x)\)

  1. 随机初始化参数\(\theta\)；
  2. 对样本\(i=1,2,…,m\)，计算\(\theta_{j+1}:=\theta_j+\alpha\frac{1}{m}\sum_{i=1}^m(y^i-h_{\theta}(x^i))x^{i}_j\)，其中：\(j=1,2,…,n​\)为样本的特征数
  3. 迭代获得逻辑回归模型

• 逻辑回归算法的快速迭代

  在实际应用中，为了提高算法收敛速度和节省内存，在迭代求解时往往采用高效的优化算法如LBFGS、信赖域算法，这些算法是基于批量处理的，无法高效处理超大规模数据集，也无法对线上模型进行快速实时更新。随机梯度下降是相对批处理的另一种优化算法，每次只用一个样本更新模型权重。谷歌的FTRL就是基于随机梯度下降的一种逻辑回归优化算法。

  FTRL算法参见：各大公司广泛使用的在线学习算法FTRL详解

• 逻辑回归应用

  逻辑回归适合用来学习需要大规模训练的样本和特征，对于计算广告等有天然优势。其缺点是：1.模型表达能力弱，需要大量的特征组合提高特征的表达；2.模型简单，容易欠拟合。

  对逻辑回归的求解有很多优化方法，如BFGS、LBFGS、共轭梯度法、信赖域法，其中前两种是牛顿法的变种，LBFGS算法是BFGS在内存受限情况下的近似优化；针对逻辑回归在线学习的稀疏性和准确性，逻辑回归又有FOBOS、RDA和FTRL等变种。

  逻辑回归需要注意正则化问题，\(L_1\)正则(又称LASSO)假设模型参数满足拉普拉斯分布，\(L_2\)正则(又称RIDGE)假设模型参数满足高斯分布。参见：变量的选择——Lasso&Ridge&ElasticNet，线性回归中的抗过拟

• 逻辑回归练习题，参见：10道题带你了解逻辑回归模型

  • 逻辑回归是有监督机器学习算法，训练时需要输入变量X和目标变量Y。

  • 逻辑回归是分类算法。

  • 能否用神经网络设计一个逻辑回归算法？

    答：可以，神经网络是一个通用的逼近算法，所以它可以实现逻辑回归。

  • 逻辑回归中可以用哪种方法来调整数据？

    答：逻辑回归使用最大似然估计来训练回归模型。

  • 类似于线性回归的R-squared，判断逻辑回归表现的一个方法是AIC，那么AIC的值是越大越好还是越小越好？

    答：AIC最小的逻辑回归模型最佳。

  • 在训练逻辑回归模型之前，对特征进行标准化是必须的吗？

    答：非必须，特征标准化的主要目的是实现模型的最优化。

  • 哪种算法可以用于逻辑回归的变量选择？

    答：LASSO，RIDGE等。

因子分解机(Factorization Machine, FM)

逻辑回归无法学习到特征间的组合关系，而特征组合关系在推荐中是比较常见的。例如，同一个用户在不同时间或地点感兴趣的广告是不同的，在这里就需要对表征用户的特征，表征时间的特征，表征地点的特征进行组合，以获得较好的预测。利用模型做特征组合，可以使用支持向量机的核函数来实现特征之间的交叉，但是多项式核函数的问题在于二次参数过多，设特征维数为\(n\)，则二次项的参数数目为\(\frac{n(n+1)}{2}\)，增加模型复杂度并且获得的特征矩阵十分稀疏，降低模型表现。因子分解机及场感知因子分解机能够自动做特征组合，并且算法效率较高。

• 前置知识

  • 向量点乘

    向量点乘输出标量，运算的数学表示：\(<·,·>\)
    \[
    <v_i,v_j>=\sum_{f=1}^kv_{i,f}·v_{j,f}
    \]

• 因子分解机原理
  因子分解机要求二次项参数矩阵是低秩的，并且能够分解为低秩矩阵的乘积。所有二次项参数矩阵\(W\)可分解为\(W=V^TV\)，\(V\)的第j列对应\(X\)的第j维特征为二次项参数矩阵贡献的向量，换言之，\(w_{ij}=<v_i,v_j>\)就是因子分解机的核心思想，其将巨大的二次项参数矩阵分解为较小的矩阵：
  \[
  \phi_{FM}(w,x)=w_0+\sum_{i=0}^nw_ix_i+\sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>x_ix_j
  \]
  其中，n是样本维度(对离散特征进行onehot等操作后的特征维度)；\(x_i\)表示第i个特征(如果是离散特征，那么onehot后只有一个维度值为1，其余维度为0，在这种情况下\(x_i\)的值通常是0或1；而对于一般的连续型特征，\(x_i\)是经过归一化或离散后的数值)，注意到：在数据稀疏情况下，同时满足\(x_i\)和\(x_j\)都不为0的情况很少，如果不进行矩阵分解，\(x_ix_j\)的系数很难训练；参数\(w_0\in \mathbb{R},w\in \mathbb{R}^n,V\in \mathbb{R}^{n×k}\)，\(v_i\)是i维特征的权重向量，该隐向量长度为k，\(k\in \mathbb{N}^+\)是因子分解机的超参数(一般设置在100以内，且\(k\ll n\)) ，\(v_i=(v_{i1},v_{i2},…,v_{ik})\)，用内积结果\(<v_i,v_j>\)来表示\(x_ix_j\)的系数：
  \[
  V=\begin{pmatrix}
  v_{11} & v_{12} & … & v_{1k}\\
  v_{21} & v_{22} & … & v_{2k}\\
  … & … & … & …\\
  v_{n1} & v_{n2} & … & v_{nk}
  \end{pmatrix}_{n×k}=
  \begin{pmatrix}
  v_1\\
  v_2\\
  …\\
  v_n
  \end{pmatrix}
  \]
  实际上，\(v_i\)可以理解为特征分量\(x_i\)的另一种表示形式，类似于词向量的表示形式。词向量中将一个单词转化为向量表示形式，单词是固定的，因此一个单词对应一个词向量；而在因子分解机中，将一个类别特征(onehot之前的特征)转化为一个向量，由于该类别特征可以有多个取值，并且每种取值对应一个向量，也即上述将类别特征进行onehot之后，每一个特征分量\(x_i\)会对应一个\(v_i\)。因此，因子分解机确实将类别特征转化为向量形式，只不过向量会根据特征的取值发生变化。

  此时，二次项组合参数就可以被分解为：
  \[
  W=VV^T=\begin{pmatrix}
  v_1\\
  v_2\\
  …\\
  v_n
  \end{pmatrix}\begin{pmatrix}
  v_1^T
  ,v_2^T,
  …,
  v_n^T
  \end{pmatrix}
  \]
  将组合参数进行分解的优势：

  • 从原先要求的\(\frac{n(n-1)}{2}\)个组合参数变成了求矩阵\(V\)，参数数量降低为\(nk\)，其中k一般远小于n
  • 削弱高阶参数间的独立性。k越大，对特征分量的表征能力越强，高阶参数间独立性越强，模型越精细；k越小，模型泛化能力越强

  参数因子化使得组合特征\(x_hx_i\)和\(x_ix_j\)不再相互独立，\(x_hx_i\)和\(x_ix_j\)的系数分别为\(<v_h,v_i>\)和\(<v_i,v_j>\)，它们有共同项\(v_i\)。通常，由于数据稀疏，特征分量\(x_i\)很多样本值是0，组合参数很难学习到，但是可以通过特征i与所有其它特征的组合，学习到特征i对应的隐向量\(v_i\)，因此所有包含特征\(x_i\)的非零组合特征的样本都可以用来学习隐向量\(v_i\)，这很大程度上避免了数据稀疏性造成的影响，而在支持向量机的多项式模型中，\(w_{hi}\)和\(w_{ij}\)就是相互独立学习的。

  上述因子分子机公式是一个通用的拟合方程，可以采用不同的损失函数解决分类、回归问题，如采用均方差损失函数，就可以使用该拟合方程求解回归问题。

• 因子分解机化简

  因子分解机的计算复杂度，考虑计算量最大的二次项：
  \[
  \sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>x_ix_j
  \]
  计算复杂度为\(O(kn^2)\)。

  可以先把标量\(x_i\)和对应的隐向量\(v_i\)相乘，并存储下来，即：
  \[
  u_i=x_iv_i
  \]
  则上式变为：
  \[
  \sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>x_ix_j=\sum_{i=1}^{n}\sum_{j=i+1}^{n}<u_i,u_j>=\sum_{f=1}^k(\sum_{i=1}^n\sum_{j=i+1}^nu_{i,f}u_{j,f})
  \]
  考虑到：
  \[
  (a+b+c)^2=a^2+b^2+c^2+2ab+2ac+2bc
  \]
  左侧只需要1次乘法，右侧需要6次乘法。因此将二次项凑成和的平方可以节约计算。

  因此二次项可变为：
  \[ {equation}
  \begin{split}
  \sum_{f=1}^k(\sum_{i=1}^n\sum_{j=i+1}^nu_{i,f}u_{j,f})&=\frac{1}{2}\sum_{f=1}^{k}(\sum_{i=1}^n\sum_{j=1}^nu_{i,f}u_{j,f}-\sum_{i=1}^nu_{i,f}^2)\\
  &=\frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nu_{i,f}^2)-\sum_{i=1}^nu_{i,f}^2)
  \end{split}
  \] {equation}
  完整的变换：
  \[ {equation}
  \begin{split}
  \sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>x_ix_j
  &=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}<v_i,v_j>x_ix_j-\frac{1}{2}\sum_{i=1}^{n}<v_i,v_i>x_ix_i\\
  &=\frac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n\sum_{f=1}^kv_{i,f}v_{j,f}x_{i}x_j-\sum_{i=1}^n\sum_{f=1}^kv_{i,f}v_{i,f}x_ix_i)\\
  &=\frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i,f}x_i)(\sum_{j=1}^nv_{j,f}x_j)-\sum_{i=1}^{n}v_{i,f}^2x_i^2) \qquad \sum_{i=1}^nv_{i,f}x_i和\sum_{j=1}^nv_{j,f}x_j地位等价\\
  &=\frac{1}{2}\sum_{f=1}^{k}((\sum_{i=1}^{n}v_{i,f})^2-\sum_{i=1}^{n}v_{i,f}^2x_i^2)
  \end{split}
  \] {equation}
  因子分解机的复杂度被优化到\(O(kn)\)。

• 场感知因子分解机(Field Factorization Machine, FFM)

  因子分解机任意两组特征交叉的隐向量都是相关的，这实际上限制了模型的复杂度。但如果任意两组特征组合是完全独立的，这与支持向量机核函数来计算特征交叉类似，有着极高的复杂性和自由度，模型计算过于复杂。场感知因子分解机是两者的折中。

  场感知因子分解机把具有相同性质的特征都归于同一个“场”，按照场级别分别计算当前特征与其它场里特征组合时的特征向量。即认为不同场的特征是相互独立的，同一场内的特征是不独立的。

  在场感知因子分解机中，每一维的特征\(x_ix_j\)，针对其它特征的每一种场\(f_if_j\)组合，都会学习一个隐变量\(v_{i,f_j}v_{j,f_i}\)，每个特征属于某个特定的场。每个特征将映射出多个隐向量，每个隐向量对应一个场，这也就是说，一个特征在不同场中对应的隐向量是不同的。当两个特征组合时，它们分别使用这两个特征对应场的隐向量做内积。场感知因子分解机的模型方程为：
  \[
  \phi _{FFM}(w,x)=\sum_{i=1}^{n}\sum_{j=i+1}^n<v_{i,f_j},v_{j,f_i}>x_i,x_j
  \]
  其中，\(v_{j,f_i}​\)是第j个特征所属的场。若隐向量长度为k，则场感知因子分解机的二次参数有nfk个，远多于因子分解机的nk个。场感知因子分解机对每个样本的预测的时间复杂度为\(O(kn^2)​\)，但场感知因子分解机的k值一般远小于因子分解机的k值。

  在因子分解机中，每一维特征的隐向量只有一个，因此因子分解机可以看作是场感知因子分解机的特例，即因子分解机是把所有特征都归属到一个场时的场感知因子分解机。

• 场感知因子分解机的应用

  场感知因子分解机可以自动做特征组合和处理高维稀疏特征，因此它在处理大量离散特征的问题上往往有比较好的效果。使用场感知因子分解机时要注意对连续特征做归一化或离散化。

  因子分解机、场感知因子分解机和其它模型的对比关系：

  • 因子分解机和场感知因子分解机。场感知因子分解机对因子分解机引入场的概念，增加了模型复杂度和模型的表达能力。
  • 因子分解机和神经网络。神经网络难以直接处理高维稀疏的离散特征，因为这导致了神经元的连接参数太多，而因子分解机可以看作对高维稀疏特征的离散特征做嵌入。
  • 因子分解机和梯度提升树。因子分解机与梯度提升树都可以做特征组合，当数据不是高度稀疏时，梯度提升树可以有效的学习到比较复杂的特征组合，但在高度稀疏的数据中，特征二阶组合就足以让绝大多数组合特征找不到样本。
  • 因子分解机和其它模型。因子分解机是一种比较灵活的模型，通过合适的特征变换方式，因子分解机可以模拟二阶多项式核的支持向量机模型、MF模型、SVD++模型等。但SVD++与MF扩展性不如因子分解机，支持向量机核函数计算复杂度较高。(MF、SVD++均为矩阵分解模型，参见：推荐系统总结MF->PMF->CTR->CDL->CNN，矩阵分解之SVD和SVD++)

梯度提升树(Gradient Boosting Decison Tree, GBDT)

梯度提升树是一种基于回归树的集成学习方法，通过构造多个弱的回归树作为基学习器，并将这些树的结果累加起来作为最终的预测输出。

• 前置知识

  • 机器学习的大致流程就是确定模型集合；定义经验损失函数；利用给定的数据集\(\{(x_i,y_i)\}\)从模型集合中寻找最佳模型(一般就是寻找最佳的模型参数)。

  • 决策树是一种模型，它的主要思想是将输入空间划分为不同的子区域，然后给每个子区域确定一个值，该子区域又称为树的叶子节点。如果是分类树，这个值就是类别；如果是回归树，这个值就是实数值，该值又称作叶子节点的权重值，分数等。
    \[
    f(x)=\sum_{j=1}^Jc_jI(x\in R_j)
    \]
    其中，\(f(x)\)是决策树表征的函数；\(c_j\)是子区域对应的值；\(J\)为子区域的个数；\(I\)是指示函数，若\(x\in R_j\)则\(I(x\in R_j)=1\)，否则为0

  • 加法模型
    \[
    h(x)=\sum_{m=1}^M\beta_mf_m(x)
    \]
    \(f_m(x)\)称作基学习器；\(\beta_m\)是基学习器的系数，一般假设大于0

  • 梯度提升树中的决策树是回归树，不是分类树，也就是说，只有回归树才有所谓的梯度提升。

  • 泰勒公式

    二阶泰勒展开：
    \[
    f(x+\Delta x)=f(x)+\frac{\partial f}{\partial x}\Delta x+\frac{1}{2}\frac{\partial ^2f}{\partial x^2}\Delta x^2+o(\Delta x)
    \]

    示例：对\(L(y,h_m(x)+\beta f(x))\)进行一阶泰勒展开，令\((y,h_m(x))\)为\(x\)，\(\beta f(x)\)为\(\Delta x\)，则：
    \[
    L(y,h_m(x)+\beta f(x))=L(y,h_m(x))+\beta f(x)\frac{\partial L(y,h_m(x))}{\partial h_m(x)}
    \]

• 梯度提升树原理

  梯度提升树是集成学习Boosting家族的一员，在训练时采用前向分步算法，首先确定第一棵树拟合的值，然后基于之前所有树的误差来更新并训练下一棵树，一步一步迭代下去直到梯度提升树构建完毕。

• 梯度提升树算法

  简单起见，首先介绍与梯度提升树相近的提升树(Boosting Tree)。

  • 提升树算法(以回归问题为例)

    输入：训练数据集\(T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\},x_i\in X\subseteq \mathbb{R}^n,y\in Y\subseteq{R}\)

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

    1. 初始化\(f_0(x)=0\)

    2. 对\(m=1,2,…,M\):

       a. 计算残差：\(r_{mi}=y_i-f_{m-1}(x_i),\quad i=1,2,…,N\)

       其中，\(f_{m-1}(x)\)为第\(m-1\)步时回归树加和的模型

       b. 拟合残差\(r_{mi}\)学习一个回归树，获得\(T(x;\Theta_m)\)

       其中，\(T(x;\Theta_m)\)是第\(m\)步的训练获得的基学习器，通过经验风险最小化确定这棵树的参数：
       \[
       \Theta_m=\mathop{argmin}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x;\Theta_m))
       \]
       对于回归问题而言，\(L(y,\hat{y})\)可采用平方损失误差

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

    3. 获得回归问题的提升树：
       \[
       f_M(x)=\sum_{m=1}^MT(x;\Theta_m)
       \]

    在提升树中，每一棵树的生成采用的训练数据都是上次预测结果与真实值的残差，这个残差会不断减小。

    这实际就是前置知识中加法模型的典型应用。注意：由于这里基学习器是回归树，叶子节点的值是实数值，因此基学习器前的系数可省略。

  • 梯度提升树

    梯度提升树的算法流程与提升树类似，只是不再使用残差作为一棵树的拟合目标，而是使用损失函数的梯度作为拟合目标。梯度提升算法利用最速下降法的近似方法，考虑经验损失函数：
    \[
    \sum_{i=1}^NL(y_i,f_{m-1}(x_i)+\beta f(x_i))
    \]
    其中，\(N\)为样本数，\(f_{m-1}(x_i)\)为第\(m-1\)步时所有树的累加，\(\beta\)为基学习器的系数，\(f(x_i)\)为本次要训练的树，即：
    \[
    f(x)=\sum_{j=1}^Jc_jI(x\in R_j)
    \]
    简单起见，考虑一个样本，对损失函数进行一阶泰勒展开：
    \[
    L(y_i,f_{m-1}(x_i)+\beta f(x_i))=L(y_i,f_{m-1}(x_i))+\beta f(x_i)\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}
    \]
    由于\(\beta\)是大于0的，要使\(L(y_i,f_{m-1}(x_i)+\beta f(x_i))\leq L(y_i,f_{m-1}(x_i))\)，令
    \[
    f(x_i)=-\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}
    \]
    每一个样本点上，上式尽可能成立的\(f(x_i)\)就是我们本次要构建的树。

    简言之，对损失函数\(L(y,\hat{y})\)求关于\(f(x)\)的偏导，然后带入\(f_{m-1}(x)\)：
    \[
    r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}
    \]
    就是每一步上，一棵树需要拟合的目标。

    梯度提升树算法流程

    输入：训练数据集\(T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},x_i\in X \subseteq \mathbb{R}^n,y_i\in Y \subseteq \mathbb{R}\)；损失函数\(L(y,f(x))\)

    输出：回归树\(\hat{f(x)}\)

    1. 初始化
       \[
       f_0(x)=\mathop{argmin}_c\sum_{i=1}^NL(y_i,c)
       \]

    2. 对\(m=1,2,…,M\):

       a. 对\(i=1,2,…,N\)，计算
       \[
       r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}
       \]

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

       c. 对\(j=1,2,…,J\)，计算
       \[
       c_{mj}=\mathop{argmin}_c\sum_{x\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)
       \]

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

    3. 获得回归树：
       \[
       \hat{f(x)}=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})
       \]

    同样，梯度提升树的基学习器是回归树，加法模型中每个基学习器前的系数会内化到回归树内部，因此可省略。

    注意到当使用\(r_{mi}\)拟合出一个回归树后，2-c进一步使用整体损失函数对这棵回归树的值进行了优化。这就是”先局部，后整体“的思想，就是先通过逐步的局部优化获得一个结果，然后从全局的角度优化结果。决策树的生成和剪枝也是这样，先通过局部优化，如信息增益等指标选择特征，得出一个决策树；再从降低整体损失的角度，进行剪枝。

    梯度提升树和提升树的关系：

    提升树每一次提升都是用上次的预测结果和训练数据真实值的误差作为新的训练数据进行进一步学习，而梯度提升树把对误差的拟合替换为对损失函数梯度的拟合。提升树主要缺点有：在回归问题中，提升树的平方损失目标函数对于异常值特别敏感；对于一些损失函数，不易优化，如绝对值损失函数等。

• XGBoost

  XGBoost是Boosting Tree的一种实现，相比于梯度提升树，XGBoost对损失函数进行了二阶泰勒展开，同时用到了一阶和二阶导数；并且引入了适用于树模型的正则化项用于控制模型的复杂度，正则化项包含树的叶子节点个数、叶子节点分数的\(L_2\)正则。

  目标函数：
  \[
  Obj(\Theta)=L(\Theta)+\Omega (\Theta)\\
  Obj=\sum_{i=1}^nl(y_i,\hat{y_i})+\sum_{k=1}^K\Omega(f_k)
  \]
  可以看到，目标函数包含两个部分：训练误差和树的复杂度。其中，树的复杂度包括：a.树的深度；b.内部节点个数；c.叶子节点个数(T)；d.叶子节点分数(w)

  和梯度提升树的思路一致，
  \[
  \begin{split}
  Obj^{(t)}&=\sum_{i=1}^nl(y_i,\hat{y_{i}}^{(t)})+\Omega(f_t(x))\\
  &=\sum_{i=1}^nl(y_i,\hat{y_{i}}^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant
  \end{split}
  \]
  思考如何寻找一个\(f_t\)来优化这个目标函数。

  这里和梯度提升树不同，XGBoost进行了二阶泰勒展开，令\(x=(y_i,\hat{y_i}^{(t-1)}),\Delta x=f_t(x_i)\)：
  \[
  Obj^{(t)}\approx \sum_{i=1}^n(l(y_i,\hat{y_i}^{(t-1)})+g_if_t(x)+\frac{1}{2}h_if_t^2(x_i))+\Omega(f_t)+constant
  \]
  其中，\(g_i\)为一阶导，\(h_i\)为二阶导
  \[
  g_i=\frac{\partial l(y_i,\hat{y}^{(t-1)})}{\partial \hat{y}^{(t-1)}},\\
  h_i=\frac{\partial ^2 l(y_i,\hat{y}^{(t-1)})}{{\partial \hat{y}^{(t-1)}}^2}
  \]
  \(l(y_i,\hat{y_i}^{(t-1)})\)为常数项；\(f_t(x)=W_{q_{(x)}}\)为决策树表征的函数，\(w\in \mathbb{R}^T\)表示树的叶子权重，\(q(x)\)表示树结构，这是上述对决策树\(f(x)=\sum_{j=1}^Jc_jI(x\in R_j)\)的另一种记法。

  去除目标函数中的常数项：
  \[
  Obj=\sum_{i=1}^n(g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i))+\Omega(f_t)
  \]
  

  

  定义叶子\(j\)：
  \[
  I_j=\{i|q(x_i)=j\}
  \]
  表示第\(j\)个叶子中的样本，其中\(q(x_i)\)表示样本\(x_i\)所属的叶节点
  \[
  \begin{split}
  Obj^{(t-1)}&\approx \sum_{i=1}^n(g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i))+\Omega(f_t)\\
  &=\sum_{i=1}^n(g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_{q(x_i)})+\gamma T+\lambda \frac{1}{2}\sum_{j=1}^Tw_j^2\\
  &=\sum_{j=1}^T((\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w_j^2)+\gamma T
  \end{split}
  \]
  现在希望将\(n\)个样本组成的目标损失，转化为\(T\)个叶子节点的目标损失，令：
  \[
  G_j=\sum_{i\in I_j}g_i\\
  H_j=\sum_{i\in I_j}h_i
  \]
  目标损失变为：
  \[
  \begin{split}
  Obj^{(t)}&=\sum_{j=1}^T((\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w_j^2)+\lambda T\\
  &=\sum_{j=1}^T(G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2)+\lambda T
  \end{split}
  \]
  现在求一个树结构下能够获得的目标函数的最小值：

  求目标函数关于\(w_j\)的偏导，并令该偏导\(\frac{\partial Obj}{w_j}=0\)，可得：
  \[
  w_j^*=-\frac{G_j}{H_j+\lambda}
  \]
  因此，对一个树结构而言，能够得到的目标函数的最小值：
  \[
  Obj^*=-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T
  \]
  其中，\(G_j\)为叶子节点\(j\)中样本的一阶导，\(H_j\)为叶子节点\(j\)中样本的二阶导，\(T\)为叶子节点数，\(\lambda\)为正则化系数。

  在所有可能的树结构中，\(Obj^*\)越小，该树结构越好。因此，现在考虑如何寻找这个最优的树结构：

  

  最直白的方法就是列举所有的树结构，在其中选择\(Obj^*\)最小的作为最佳树结构，但是这实际是一个\(NP\)难问题。在实践中，通常使用树的精确贪婪学习：

  1. 贪婪：选分割点时，只考虑当前树结构到下一步树结构的loss变化，不考虑全局
  2. 精确：当前层所有特征值中的所有可能，进行遍历，寻找最优分割点

  

  类似于ID3的信息增益、C4.5的增益率、CART的基尼指数，定义XGBoost选择最优特征的准则：
  \[
  Gain=\frac{G_L^2}{H_L^2+\lambda}+\frac{G_R^2}{H_R^2+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}-\gamma
  \]
  遍历所有的特征，计算Gain值，选择最大的特征进行分割
  \[
  \begin{split}
  &for\ k: 0\to K: \quad \#\ 对每个节点\\
  &\quad for\ d:0\to D:\quad \#\ 对每个特征\\
  &\qquad for\ n:0\to N:\quad \#\ 对每个实例\\
  &\qquad\quad 在n\to N中，实例排序的时间复杂度为O(nlog(n))
  \end{split}
  \]
  因此，深度为\(k\)的树，总的时间复杂度为\(O(ndklog(n))\)

  注意到，对于每个节点，也就是每一步构建子树时，寻找最佳分裂点有两层含义：a.寻找特征中最优的分裂值；b.寻找最优的特征

  为了降低时间复杂度，可以采用一些近似算法：对于每个特征，只考虑分位点，

  

  就是把一些样本捆绑在一起，形成bin，这样就能降低最终要排序的样本数量。实际上，XGBoost不是简单的按照上图那样，按照样本个数进行分位，而是以二阶导数值作为权重：

  

  之所以使用\(h_i\)加权，是因为目标函数可以被整理成下式：
  \[
  Obj=\sum_{i=1}^n\frac{1}{2}h_i(f_t(x_i)-\frac{g_i}{h_i})^2+\Omega(f_t)+constant
  \]
  可以看到，\(h_i​\)对loss有加权的作用。

  另外，观察XGBoost的最优特征准则：
  \[
  Gain=\frac{G_L^2}{H_L^2+\lambda}+\frac{G_R^2}{H_R^2+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}-\gamma
  \]
  其中，等式右侧前半部分表示训练loss的减少，\(\gamma\)为正则化。上式有可能是负的，也就是说，loss的减少比正则化力度还要小时，分裂的增益会是负的。因此类似于预剪枝和后剪枝，有两种训练策略：

  1. 提前停止：如果最佳分裂点是负的，那么提前停止分裂。这是这种策略过于贪婪，该分裂有可能有益于后面的分裂。
  2. 后剪枝：将一棵树生成到它的最大深度，递归剪枝，剪去叶子节点分裂是负增益的。

  XGBoost的其它特性：

  1. 行抽样
  2. 列抽样
  3. 缩减学习率
  4. 支持自定义损失函数，当然，该损失函数需要二阶可导
  5. 增加了对稀疏数据的支持，在计算分裂增益时，只利用没有missing值的样本
  6. 支持并行化，在分裂节点计算增益时，并行

  XGBoost论文地址：XGBoost: A Scalable Tree Boosting System

  XGBoost官网：XGBoost Documentation

• LightGBM

  与XGBoost的不同：

  • 直方图算法

    把连续的浮点特征值离散化为k个整数，同时构造一个宽度为k的直方图。在遍历数据时，根据离散化后的值作为索引，在直方图中计算统计量。当遍历一次数据后，直方图计算了需要的统计量，然后根据直方图的离散值，遍历寻找最优分割点。

    

    优势：减少了内存占用；减少了分裂点计算增益时的计算量

  • 直方图加速

    一个叶子的直方图可以由它的父节点的直方图与它的兄弟节点的直方图，做差而得，提升一倍速度。

    

  • 建树方法

    XGBoost是Level-wise，LightGBM是Leaf-wise

    

  总而言之，LightGBM特性：

  • 基于Histogram的决策树算法

  • 直方图差加速

  • 带深度限制的Leaf-wise的叶子生长策略

  • 直接支持类别特征(Categorical Feature)

  • Cache命中率优化

  • 基于直方图的稀疏特征优化

  • 多线程优化

  LightGBM论文地址：Lightgbm: A highly efficient gradient boosting decision tree

  LightGBM官网：LightGBM Documentation