Task 08

侧边栏练习

【练习7】请写出 L ( m ) ( F i ( m ) ) L^{(m)}(F_i^{(m)}) L(m)(Fi(m)​)在 F i ( m ) = F i ( m − 1 ) F_i^{(m)} = F_i^{(m-1)} Fi(m)​=Fi(m−1)​处的二阶展开。
L ( m ) ( F i ( m ) ) = γ T + 1 2 λ ∑ j = 1 T w j 2 + ∑ i = 1 N [ ∂ L ∂ h i ∣ h i = 0 h i + ∂ 2 L ∂ h i 2 ∣ h i = 0 h i 2 ] + c o n s t a n t = γ T + 1 2 λ ∑ j = 1 T w j 2 + ∑ i = 1 N [ ∂ L ∂ F i ( m − 1 ) ∣ F i ( m ) = F i ( m − 1 ) ( F i ( m ) − F i ( m − 1 ) ) + ∂ 2 L ∂ ( F i ( m − 1 ) ) 2 ∣ F i ( m ) = F i ( m − 1 ) ( F i ( m ) − F i ( m − 1 ) ) 2 ] + c o n s t a n t \begin{aligned} L^{(m)}(F_i^{(m)}) &= \gamma T + \cfrac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \sum_{i=1}^N [\cfrac{\partial L}{\partial h_i}|_{h_i=0}h_i + \cfrac{\partial^2 L}{\partial h_i^2}|_{h_i=0} h_i^2] + constant \\ &= \gamma T + \cfrac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \sum_{i=1}^N [\cfrac{\partial L}{\partial F_i^{(m-1)}}|_{F_i^{(m)} = F_i^{(m-1)}}(F_i^{(m)} - F_i^{(m-1)}) + \cfrac{\partial^2 L}{\partial (F_i^{(m-1)})^2}|_{F_i^{(m)} = F_i^{(m-1)}} (F_i^{(m)} - F_i^{(m-1)})^2 ] + constant \end{aligned} L(m)(Fi(m)​)​=γT+21​λj=1∑T​wj2​+i=1∑N​[∂hi​∂L​∣hi​=0​hi​+∂hi2​∂2L​∣hi​=0​hi2​]+constant=γT+21​λj=1∑T​wj2​+i=1∑N​[∂Fi(m−1)​∂L​∣Fi(m)​=Fi(m−1)​​(Fi(m)​−Fi(m−1)​)+∂(Fi(m−1)​)2∂2L​∣Fi(m)​=Fi(m−1)​​(Fi(m)​−Fi(m−1)​)2]+constant​

其中constant为 ∑ i = 1 N L ( y i , F i ( m − 1 ) ) \sum_{i=1}^N L(y_i, F_i^{(m-1)}) ∑i=1N​L(yi​,Fi(m−1)​)​.

【练习8】试说明不将损失函数展开至更高阶的原因。

展开到更高，所需要的计算量也就会更大，为了平衡准确率以及计算量，我们一般选择展开到二阶。

【练习9】请写出平方损失下的近似损失。

假设损失函数为：
L ( y , y ^ ) = 1 2 ∑ i = 1 N ( y i − y ^ i ) 2 L(y, \hat{y}) = \cfrac{1}{2} \sum_{i=1}^N (y_i - \hat{y}_i)^2 L(y,y^​)=21​i=1∑N​(yi​−y^​i​)2

令 h i = y i − y ^ i h_i = y_i - \hat{y}_i hi​=yi​−y^​i​​， 则损失函数 L ( y , y ^ ) L(y, \hat{y}) L(y,y^​)​的一节导数， 二阶导数分别为 p i = h i p_i = h_i pi​=hi​​​, q i = 1 q_i = 1 qi​=1​

L ~ ( m ) ( m ) = γ T + 1 2 ∑ j = 1 T w j 2 + ∑ i = 1 N [ p i h i + 1 2 q i h i 2 ] = γ T + 1 2 λ ∑ j = 1 T w j 2 + ∑ i = 1 N [ h i 2 + 1 2 h i 2 ] = γ T + 1 2 λ ∑ j = 1 T w j 2 + 3 2 ∑ i = 1 N h i 2 = γ T + 1 2 λ ∑ j = 1 T w j 2 + 3 2 ∑ j = 1 T [ ( ∑ i ∈ I j 1 ) w i 2 ] = γ T + 1 2 ∑ j = 1 T [ ( λ + 3 ∑ i ∈ I j 1 ) w i 2 ] \begin{aligned} \tilde{L}^{(m)}(\textbf{m}) &= \gamma T + \cfrac{1}{2} \sum_{j=1}^T w_j^2 + \sum_{i=1}^N [p_i h_i + \cfrac{1}{2} q_i h_i^2] \\ &= \gamma T + \cfrac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \sum_{i=1}^N[h_i^2 + \cfrac{1}{2} h_i^2] \\ &= \gamma T + \cfrac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \cfrac{3}{2} \sum_{i=1}^Nh_i^2 \\ &= \gamma T + \cfrac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \cfrac{3}{2} \sum_{j=1}^T[(\sum_{i \in I_j} 1) w_i^2] \\ &= \gamma T + \cfrac{1}{2} \sum_{j=1}^T [(\lambda +3 \sum_{i \in I_j} 1)w_i^2] \end{aligned} L~(m)(m)​=γT+21​j=1∑T​wj2​+i=1∑N​[pi​hi​+21​qi​hi2​]=γT+21​λj=1∑T​wj2​+i=1∑N​[hi2​+21​hi2​]=γT+21​λj=1∑T​wj2​+23​i=1∑N​hi2​=γT+21​λj=1∑T​wj2​+23​j=1∑T​[(i∈Ij​∑​1)wi2​]=γT+21​j=1∑T​[(λ+3i∈Ij​∑​1)wi2​]​

【练习10】在下列的三个损失函数 L ( y , y ^ ) L(y, \hat{y}) L(y,y^​)中，请选出一个不应作为XGBoost损失的函数并说明理由。

• Root Absolute Error: ∣ y − y ^ ∣ \sqrt{|y - \hat{y}|} ∣y−y^​∣ ​
• Squared Log Error: 1 2 [ log ⁡ ( y + 1 y ^ + 1 ) ] 2 \cfrac{1}{2}[\log (\cfrac{y + 1}{\hat{y} + 1})]^2 21​[log(y^​+1y+1​)]2​
• Pseudo Huber Error: δ 2 ( 1 + ( y − y ^ δ ) 2 − 1 ) \delta^2(\sqrt{1 + (\cfrac{y - \hat{y}}{\delta})^2} - 1) δ2(1+(δy−y^​​)2 ​−1)

第二个。因为第二个的损失函数关于 y − y ^ y - \hat{y} y−y^​​的二阶导数是关于 y ^ \hat{y} y^​的函数，而是说存在有零点的。

【练习11】请求出顶点最大度（即最多邻居数量）为 d d d​的无向图在最差和最好情况下需要多少种着色数，同时请构造对应的例子。

不会无向图… 学了来补

【练习12】在最差情况下LightGBM会生成几族互斥特征？这种情况的发生需要满足什么条件？
也不会。。。

知识回顾

1\ GBDT和梯度下降方法有什么联系？

GBDT 的参数的更新使用的时梯度下降法。
对损失函数关于参数求导，得到梯度，利用梯度下降法的更新公式来更新参数，使得损失函数朝着梯度的方向最速下降。

2、 请叙述GBDT用于分类问题的算法流程。

(a) 建立M颗决策树(迭代M次
(b) 表示对函数估计值F(x) 进行losgistic变换, 进行softmax归一化
© for m in 1… M
1、计算属于第k类的概率为 e F k i ∑ c = 1 K e F c i \cfrac{e^{F_{ki}}}{\sum_{c=1}^K e^{F_{ci}}} ∑c=1K​eFci​eFki​​,
2、令 y i = [ y 1 i , ⋯   , y K i ] \textbf{y}_i = [y_{1i}, \cdots, y_{Ki}] yi​=[y1i​,⋯,yKi​]为第i个样本的类别独热编码,记 F i = [ F 1 i , ⋯   , F K i ] \textbf{F}_i = [F_{1i}, \cdots, F_{Ki}] Fi​=[F1i​,⋯,FKi​]
3、对每个样本计算损失:
L ( y i , F i ) = − ∑ c = 1 K y c i log ⁡ e F c i ∑ c ~ = 1 K e F c ~ i L(\textbf{y}_i, \textbf{F}_i) = - \sum_{c=1}^K y_{ci} \log \cfrac{e^{F_{ci}}}{\sum_{\tilde{c}=1^K e^{F_{\tilde{c}i}}}} L(yi​,Fi​)=−c=1∑K​yci​log∑c~=1KeFc~i​​eFci​​
​ 4、对 F i ∗ ( m ) F_i^{*(m)} Fi∗(m)​进行梯度更新

5、 $h_i = F_i^{(m)} - F_i^{(m-1)}$，最后更新的学习学习器为$F_i^{(m-1)} + \eta h_i^{*(m)}$为更新之后的学习器​

(d) 将 F i ( M ) F_i^{(M)} Fi(M)​作为最终的分类器输出

3、 XGBoost和GBDT树有何异同？（可从目标损失、近似方法、分裂依据等方面考虑）

目标损失：
GBDT: 使用的是预测值和真实值之间的差距度量的损失函数
G ( w ) = ∑ i = 1 N L ( y i , F i ( m ) ) = ∑ i = 1 N L ( y i , F i ( m − 1 ) + w i ) \begin{aligned} G(\textbf{w}) &= \sum_{i=1}^N L(y_i, F_i^{(m)}) \\ &= \sum_{i=1}^N L(y_i, F_i^{(m-1)} + w_i) \end{aligned} G(w)​=i=1∑N​L(yi​,Fi(m)​)=i=1∑N​L(yi​,Fi(m−1)​+wi​)​
其中 w i w_i wi​​为我们要拟合的一颗树，这棵树使得 F i ( m − 1 ) + h m ( X i ) F_i^{(m-1)} + h_m(X_i) Fi(m−1)​+hm​(Xi​)​与 y i y_i yi​之间的损失尽可能小。

XGBoost: 损失函数 + 正则项
L ( m ) = γ T + 1 2 λ ∑ j = 1 T w j 2 + ∑ i = 1 N L ( y i , F i ( m ) ) L^{(m)} = \gamma T + \cfrac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \sum_{i=1}^N L(y_i, F_i^{(m)}) L(m)=γT+21​λj=1∑T​wj2​+i=1∑N​L(yi​,Fi(m)​)

其中损失函数 L ( y i , F i ( m ) ) L(y_i, F_i^{(m)}) L(yi​,Fi(m)​)一般为我们定义的一个二阶导数恒为正的损失函数.

近似方法：
GBDT: 使用梯度下降来更新参数，即利用泰勒展开式的一阶导数来对目标函数进行拟合。
XGBoost： 使用一阶导数和二阶导数来对目标函数进行拟合，其展开式为:
$$
\begin{aligned}
L^{(m)}(\textbf{h}) &=
\gamma T + \cfrac{1}{2} \lambda \sum_{j=1}^T w_j^2

• \sum_{i=1}^N[
  \cfrac{\partial L}{\partial h_i} |_{hi=0} h_i
• \cfrac{1}{2} \cfrac{\partial^2L}{\partial h_i^2} |_{h_i=0} + constant
  ]
  \end{aligned}
  $$

其中 c o n s t a n t = ∑ i = 1 N L ( y i , F i ( m − 1 ) ) constant = \sum_{i=1}^N L(y_i, F_i^{(m-1)}) constant=∑i=1N​L(yi​,Fi(m−1)​)​

分裂依据：

GBDT： 按照信息增益或者CART树的gini指数来进行分裂
XGBoost: 将损失函数作为信息增益的另一种表现形式，对所有的特征，分别找到对应的分裂节点，将使得损失函数下降最大的分裂节点，以及分裂节点所对应的特征，作为我们用于分裂的特征和节点。

4\ 请叙述LightGBM中GOSS和EFB的作用及算法流程。

GOSS作用:
减少只具有小梯度的数据实例,便于在计算信息增益的时候, 只利用高梯度的数据. 这比XGBoost遍历所有特征值少了不少时间和空间上的开销.

GOSS算法流程
(a) 输入训练数据, 迭代的次数, 对大梯度数据采样的比例a,对小梯度数据采样的比例b, 定义损失函数
(b) i代表迭代次数, 从1 到 d开始迭代
对训练样本的梯度的绝对值进行降序排序
对降序后的结果选取钱a * 100%的样本生成一个大梯度样本点的子集
对剩下的集合(1-a) * 100% 的样本,随机的选取 1 − a b \cfrac{1-a}{b} b1−a​​ 个样本点,生成一个小梯度样本点的集合
将大梯度样本和采样的梯度样本合并
将小梯度样本乘上一个权重系数
使用上述的采样样本,学习一个新的学习器
直到 步骤达到d,或者收敛为止
EFB作用:
将许多互斥的特征绑定为一个特征, 这样达到了降维的目的.

EFB算法流程:
(a) 构造一个加权无向图,顶点是特征,变有权重,其权重与两个特征见冲突相关
(b) 根据节点的度进行降序排序,度越大,与其它特征的冲突越大
© 遍历每个特征,将它分配给先右的特征组合,或者构建一个新的特征组合, 来使得总体冲突最小

最后，代码我又没有写…我之后补上