前向分布算法
在Adaboost算法中，我们的最终目的是通过构建弱分类器的线性组合：
f
(
x
)
=
∑
m
=
1
M
G
m
(
x
)
f(x)= \sum_ {m=1}^{M}G_{m}(x)
f
(
x
)
=
m
=
1
∑
M
G
m
(
x
)
加法模型的表达式为：
f
(
x
)
=
∑
m
=
1
M
β
m
b
(
x
;
γ
m
)
f(x)= \sum_ {m=1}^{M}\beta _{m}b(x; \gamma_{m})
f
(
x
)
=
m
=
1
∑
M
β
m
b
(
x
;
γ
m
)
其中，
b
(
x
;
r
m
)
b(x;r_{m})
b
(
x
;
r
m
)
为基函数，
r
m
r_{m}
r
m
是基函数的参数，
β
m
\beta_{m}
β
m
为基函数的系数。
前向分布算法总结如下：
输入：
训练数据集T ={(x1,y1), (x2, y2), …, (xN, yN)}；损失函数L(y, f(x))；基函数集{b(x; r)}；
输出：
加法模型f(x)
解：
- 初始化f0(x)= 0
-
对m = 1, 2,…, M
a，极小化损失函数>
(β
m
,
γ
m
)
=
arg
min
β
,
γ
∑
i
=
1
N
L
(
y
i
,
f
m
−
1
(
x
i
)
+
β
b
(
x
i
;
γ
)
)
\left(\beta_{m}, \gamma_{m}\right)=\arg \min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right)
(
β
m
,
γ
m
)
=
ar
g
β
,
γ
min
i
=
1
∑
N
L
(
y
i
,
f
m
−
1
(
x
i
)
+
β
b
(
x
i
;
γ
)
)
b，更新
fm
(
x
)
=
f
m
−
1
(
x
)
+
β
m
b
(
x
;
γ
m
)
f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right)
f
m
(
x
)
=
f
m
−
1
(
x
)
+
β
m
b
(
x
;
γ
m
)
-
得到加法模型
fm
(
x
)
=
f
m
−
1
(
x
)
+
β
m
b
(
x
;
γ
m
)
f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right)
f
m
(
x
)
=
f
m
−
1
(
x
)
+
β
m
b
(
x
;
γ
m
)
这样，前向分布算法将同时求解从m=1到M的所有参数βm, rm的优化问题简化为逐次求解各个βm, rm的优化问题。
负梯度拟合
针对各种各样损失函数如何让进行通用性拟合的问题，Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。
第t轮的第i个样本的损失函数的负梯度表示为：
损失函数
-
分类算法损失
-
指数损失
L(
y
,
f
(
x
)
)
=
e
x
p
(
−
y
f
(
x
)
)
L(y,f(x))=exp(-yf(x))
L
(
y
,
f
(
x
)
)
=
e
x
p
(
−
y
f
(
x
)
)
-
对数损失
L(
y
,
f
(
x
)
)
=
l
o
g
(
1
+
e
x
p
(
−
y
f
(
x
)
)
)
L(y,f(x))=log(1+exp(-yf(x)))
L
(
y
,
f
(
x
)
)
=
l
o
g
(
1
+
e
x
p
(
−
y
f
(
x
)
)
)
二分类
L(
y
,
f
(
x
)
)
=
−
∑
k
=
1
K
y
k
log
p
k
(
x
)
L(y, f(x))=-\sum_{k=1}^{K} y_{k} \log p_{k}(x)
L
(
y
,
f
(
x
)
)
=
−
∑
k
=
1
K
y
k
lo
g
p
k
(
x
)
多分类
-
指数损失
-
回归算法损失
均方差
绝对损失
Huber损失（均方差和绝对损失的折中产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量）
分位损失
二分类，多分类
二分类
多分类
正则化
-
和Adaboost类似的正则化项，即步长(learning rate)。定义为ν。（Shrinkage 的思想）ν的取值范围为0<ν≤1。对于同样的训练集学习效果，较小的ν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
-
通过子采样比例（subsample）。取值为(0,1]。这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。
-
使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。减少弱学习器难以并行学习的弱点。
-
对于弱学习器即CART回归树进行正则化剪枝。
优缺点
优点
- 可以灵活处理各种类型的数据，包括连续值和离散值。
- 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。
- 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
缺点
由于弱学习器之间存在依赖关系，难以并行训练数据。（SGBT进行了改善）
sklearn参数
Boosting框架的重要参数：
loss {‘deviance’, ‘exponential’}, 默认‘deviance’
损失函数。有对数似然损失函数”deviance”和指数损失函数”exponential”两个选项。一般来说，推荐使用默认的对数似然损失函数”deviance”，它对于二元分类和多元分类都有较好的优化效果。而指数损失函数”exponential”相当于执行了Adaboost算法。
learning_rate float，范围（0，1]，默认0.1
弱学习器的权重缩减系数ν。
n_estimators int (default=100)
弱学习器的最大迭代次数，或者说最大的弱学习器个数。一般来说n_estimators太小，容易欠拟合，而n_estimators太大，又容易过拟合。调参过程中，常常将它和参数learning_rate一起来考虑。
subsample float, (default=1.0)
子采样比例，取值为(0,1]。推荐在[0.5, 0.8]之间选择。
init estimator
初始化的弱学习器。。如果不输入，则用训练集样本来做样本集的初始化分类回归预测，否则使用init参数提供的学习器来做初始化分类回归预测。一般用在我们对数据有先验知识或者之前做过拟合的时候，否则就不用考虑这个参数了。
validation_fraction float （0，1），默认0.1
验证集比例。在n_iter_no_change为integer时使用，用于提前终止训练。
n_iter_no_change int, default None
None表示不会提前终止训练。为int时表示验证集的评分在多轮迭代中没有提高，则停止训练。
tol float, optional, default 1e-4
提前停止的容忍程度。在n_iter_no_change轮迭代中，损失都没能提高tol，则停止训练。
决策树类相关参数：
决策树相关参数。在随机森林算法中已经对这些参数进行了细致的说明：
https://blog.csdn.net/m0_38019841/article/details/85100588
criterion
max_depth
max_features
min_samples_split
min_samples_leaf
min_weight_fraction_leaf
min_impurity_decrease
min_impurity_split
max_leaf_nodes
random_state
verbose
warm_start
presort bool, optional (default=False)
是否预先对数据排序以加快拟合中最佳分裂的发现。
应用场景
- Facebook使用其来自动发现有效的特征、特征组合，来作为LR模型中的特征，以提高 CTR预估（Click-Through Rate Prediction）的准确性
- GBDT在淘宝的搜索及预测业务上也发挥了重要作用