LR+GBDT二分类和多分类梯度计算和更新过程

梯度推导

SIGMOID 函数分类(LR+GBDT)

sigmoid函数通常将结果映射到[0,1]之间，先推导通过后向传播求其梯度，假设非映射结果为（$F_m(x)$）：

$\begin {align} Sigmoid映射：h(x;\theta) &= \frac{1}{1+e^{-F_m(x)}} \tag{1} \\ 损失函数：Loss(y,\hat y) &= -\sum_{i=0}^1y_ilog\hat y_i \nonumber\\ &=-[y_ilog h_i+(1-y_i)log(1-h_i)]\tag{2} \\ \end {align}$

应该注意的是$\hat y$是预测结果，并且$\hat y = h(x;\theta)$，交叉熵作为损失函数是为了评估实际值（标签）$y_i$与预测值的相似程度。先求其梯度，且暂时不考虑使用什么函数拟合。

$\begin{align} 一般形式（拟合函数F_m(x)）：g_t &= \frac{\partial Loss(y,\hat y)}{\partial F_m(x)} \nonumber \\ &=(h(x;\theta)-y_i) \tag{3} \end{align}$

求一阶导数的时候不需要一下把所有的的函数都代入，这样会比较复杂，链式求导一般会较少计算错误率。上式若拟合函数是多元线性组合形式，则为LR的梯度求导过程，只需要代入$F_m(x) = w^Tx$:

$\begin{align} g_t &= (h(x;\theta)-y_i)\frac{\partial F_m(x)}{\partial w_i} \nonumber\\ & = (\hat y_i-y_i)x_i \tag{4} \end{align}$

LR采用梯度下降时，更新方法为：

LR更新方法-梯度下降法
第一步：初始化$[w_1,w_2,…,w_n]^T$;

第二步：计算梯度Jacobian矩阵。

$g_t =[g_1,g_2,…,g_i]^T= [(\hat y_1-y_1)x_i,(\hat y_2-y_2)x_2,…,(\hat y_i-y_i)x_i]$;

第三步：$[w_1,w_2,…,w_n]^T:=[w_1,w_2,…,w_n]^T-\alpha g_t$;

第四步：$w^* = arg \min_wLoss $;

第五步：算法结束

和LR中用线性模型拟合有些不同，GBDT或者XGBOOST中采用回归树进行建模，即拟合函数$F_m(x)=w_{q(x)}$为回归树（Regression Tree），处理二分类问题时，可计算其梯度：

$\begin{align} &Loss函数为交叉熵：H(p,q) =-\sum_{j=1}^n \sum_{i=1}^mp_ilogq_i \nonumber \\ & = \sum_{j=1}^n c_0log (1+e^{-F_m(x)})+(1-c_0)(F_m(x)+log(1+e^{-F_m(x)})) \tag{5} \\ &梯度求解：\partial Loss(y,\hat y)|_{\hat y = F_m(x)} = -c_0+\frac{1}{1+e^{-F_m(x)}} = \hat y - y_i \tag{6} \end{align}$

GBDT具有自己的特点：1）梯度提升（每棵树都是前m-1棵树的负梯度方向）；2）加性模型（预测结果为m棵树的累加）。

$\begin{align} &一般损失：L(y,\hat y) = L(y_i,F_{m-1}(x_i)+f_m(x_i)) \tag{7} \\ &泰勒展开：L(y,\hat y) = L(y_i,F_{m-1}(x_i))+f_m(x_i)L^\prime(y_i,F_{m-1}(x_i))|_{F_{m-1}} \tag{8}\\ &新树：f_m(x_i) = -\alpha L^\prime(y_i,F_{m-1}(x_i))|_{F_{m-1}} \tag{9} \end{align}$

GBDT采用梯度下降法进行更新步骤：

//GBDT更新方法-梯度下降法

第一步：初始化第一棵树$f_0=log\frac{p_1}{1-p_1}$,其中$p_1$是训练样本中y=1的比例，利用先验知识初始化。

第二步：计算梯度。$g_i = \hat y - y$,并使用训练集$\{(x_i,-g_i)\}^n_{i=1}$训练一棵树$f_m(x)$，其中$\hat y = \frac{1}{1+e^{F_{m-1}(x)}}$

第三步：通过line search方法找到每棵树的最佳权重(Shrinkage)：$\gamma_m =arg min_{\gamma_m}L(y_i,F_{m-1}(x)+\gamma_mf_m(x)) $

第四步：累加所有树，得到模型：$F_m(x) = \sum_{i=0}^m \alpha \gamma_mf_m(x)$

SOFTMAX分类问题(LR+GBDT)

处理多分类的时候，一般会选用SOFTMAX函数作为映射函数：

$SoftMax映射：q_j = \frac{e^{F^j_m(x_i)}}{\sum_{j^\prime =1}^m e^{F^{j^\prime}_m(x_i)}} \tag{10}$

多分类的输出是One-hot，也就说，只有一个为标签为1，分类问题交叉熵作为损失函数，则有：

$\begin{align} &一个样本：Loss(y_i,\hat y) = -\sum_{j=1}^m y_jlogq_j \tag{11}\\ &只有一个标签为1,其余均为0：Loss(y_i,\hat y) = -log \frac{e^{F^j_m(x_i)}}{\sum_{j^\prime =1}^m e^{F^{j^\prime}_m(x_i)}} \tag{12}\\ &求多分类梯度：if \quad j = i \to \partial L(y_i,\hat y)|_{\hat y =F_m(x)} = (q_j-1)\nonumber\\ &if \quad j\ne i \to \partial L(y_i,\hat y)|_{\hat y =F_m(x)} = q_j \nonumber\\ &总结多分类梯度更新方式为：g_t|_{F_m(x)} = \hat y_i - y_i \tag{13} \end{align}$

先举例说明计算时梯度如何计算，不管是LR还是GBDT:

//举例说明如何更新梯度（对$F_m(x)$的梯度）

第一步：获取得分$F^j_m(x)$，比如三分类输出$[2,1,0.3]^T$

第二步：计算预测结果，即SoftMax输出结果$[0.64,0.23,0.13]$

第三步：计算梯度。假设第二类为正确预测的结果，由上面梯度计算结果可知：

$[0.64,0.23-1,0.13] = [0.64,-0.77,0.13] $

梯度计算完毕

先给出LR-MULTICLASSIFIER迭代过程：

//LR-MultiClassifer-StochasticGradient

第一步：初始化线性拟合部分模型参数$[w_1,w_2,w_3,…,w_n]$

第二步：计算梯度,Jacobian矩阵。计算$g_t=(\hat y_j -y_j)x_i=[g_1,g_2,…,g_j]$，输入$\{(x_i,y_i,-g_t)\}$，其中$j$为输出的维度（分类的类别数）且$\hat y_j = softmax_j$

第三步：更新参数。$[w_1,w_2,…,w_n]^T:=[w_1,w_2,…,w_n]^T-\alpha g_t$;

第四步：达到最优。$w^* = argmin_w L(y_i,\hat y)$

结束算法。

GBDT的算法迭代方式和二分类非常的类似，这里就不在累述。

总结

不管是LR还是树模型，计算梯度都可使用后向传输（链式求导）的方法求其梯度。并且不管是二分类还是多分类，其损失函数对$F_m(x)$（拟合输出得分，对于LR就是线性拟合结果，对于树模型就是叶子节点的得分），都是$g_t = \hat y - y$。但是应该注意的是，GBDT在更新的过程中，是对$F_{m-1}(x)$的导数，这个应该注意。

参考文献

[1] Jerome H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine[J]. Annals of Statistics, 29(5):1189-1232.

[2] http://willwolf.io/2017/05/18/minimizing_the_negative_log_likelihood_in_english/