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∑Twj2+i=1∑N[∂hi∂L∣hi=0hi+∂hi2∂2L∣hi=0hi2]+constant=γT+21λj=1∑Twj2+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=1NL(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^)=21i=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+21j=1∑Twj2+i=1∑N[pihi+21qihi2]=γT+21λj=1∑Twj2+i=1∑N[hi2+21hi2]=γT+21λj=1∑Twj2+23i=1∑Nhi2=γT+21λj=1∑Twj2+23j=1∑T[(i∈Ij∑1)wi2]=γT+21j=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=1KeFcieFki,
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∑Kycilog∑c~=1KeFc~ieFci
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∑NL(yi,Fi(m))=i=1∑NL(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∑Twj2+i=1∑NL(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=1NL(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) 根据节点的度进行降序排序,度越大,与其它特征的冲突越大
© 遍历每个特征,将它分配给先右的特征组合,或者构建一个新的特征组合, 来使得总体冲突最小
最后，代码我又没有写…我之后补上