《机器学习》周志华-CH8（集成学习）
8.1个体与集成
集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统，基于委员会的学习。
同质”集成“：只包含同种类型的个体学习器，同质集成中的个体学习器亦称“基学习器”，相应的学习算法称为“基学习算法”
异质“集成”：由不同学习算法生成，不再有基学习法，称“组件学习器”。
集成学习常获得比单一学习器显著优越的泛化性能，对“弱学习器”尤为明显。
要想获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，并且也有差异“多样性”
以二分类问题
y
∈
{
−
1
,
+
1
}
y\in\{-1,+1\}
y∈{−1,+1}和函数
f
f
f为例，假定基分类器错误率为
ξ
\xi
ξ,对每个基分类器
h
i
h_i
hi有：
P
(
h
i
(
x
)
≠
f
(
x
)
)
=
ξ
\begin{equation} P(h_i(x)\neq{f(x)})=\xi \tag{8.1} \end{equation}
P(hi(x)=f(x))=ξ(8.1)
假设集成通过投票要对
T
T
T个基分类器判断，则超过半数为正确
H
(
x
)
=
s
i
g
n
(
∑
i
=
1
T
h
i
(
x
)
)
\begin{equation} H(x)=sign(\sum_{i=1}^Th_i(x)) \tag{8.2} \end{equation}
H(x)=sign(i=1∑Thi(x))(8.2)
集成错误率为：
P
(
H
(
x
)
≠
f
(
x
)
)
=
s
i
g
n
(
∑
k
=
0
T
/
2
[
T
K
]
(
1
−
ξ
)
ξ
T
−
K
≤
e
x
p
(
−
1
2
T
(
1
−
2
ξ
)
2
)
\begin{equation} P(H(x)\ne{f(x)})=sign(\sum_{k=0}^{T/2}\left[ \begin{matrix} T \\ K \\ \end{matrix} \right](1-\xi)\xi^{T-K}\leq{exp(-\frac{1}{2}T(1-2\xi )^2)} \tag{8.3} \end{equation}
P(H(x)=f(x))=sign(k=0∑T/2[TK](1−ξ)ξT−K≤exp(−21T(1−2ξ)2)(8.3)
随集成个体分类器数目 T T T增大，集成的错误率将指数级下降，最终趋于零。
集成学习分两大类：
- 个体学习器存在强依赖关系，必须串行生成序列化方法。如：Boosting
- 不存在强依赖关系，可同时生成的并行化方法，如Bagging和随机深林。
8.2Boosting
Boosting工作机制： 先从初始训练集中训练出一个基学习器，再根据基学习器表现对训练样本分布调整，使先前错的样本后续得到更大关注，基于调整后的样本训练下一个基学习器，反复直到达到指定值 T T T。最终将 T T T个学习器加权结合。
Boosting族算法最著名的是AdaBoost，比较容易理解的是基于“加性模型”即基学习器线性组和
H
(
x
)
=
∑
i
=
1
T
α
t
h
t
(
x
)
\begin{equation} H(x)=\sum_{i=1}^T{\alpha_t}h_t(x) \tag{8.4} \end{equation}
H(x)=i=1∑Tαtht(x)(8.4)
其中，
T
T
T指代的是
T
T
T个学习器
最小化指数损失函数
若H(x)(8.4)能令指数损失函数最小化考虑(8.5)对(8.4)求偏导
在AdaBoost算法中，第一个基分类器
h
1
h_1
h1是通过直接将基学习算法用于初始数据分布而得；此后迭代生成
h
t
h_t
ht和
α
t
\alpha_t
αt。当基分类器
h
t
h_t
ht基于分布
D
t
D_t
Dt产生后，该分类器的权重
α
t
\alpha_t
αt应使得
α
t
h
t
\alpha_th_t
αtht最小化指数损失函数
AdaBoost算法在获得
H
e
−
1
H_{e-1}
He−1之后样本分布将进行调整，使下一轮基学习器
h
t
h_t
ht能纠正一些
H
t
−
1
H_{t-1}
Ht−1错误，理想是纠正所有错误，即最小化。
8.3Bagging与随机森林
个体学习器不存在强依赖关系，可同时生成的并行化方法。
欲得到泛化性能强的集成，个体学习器应尽可能有较大差异。一个数据集可产生若干子集，每个子集可训练出一个基学习器。使用相互交叠的采样子集.
8.3.1Bagging
基于自助采样法，给定包含 m m m个样本数据集，使得下次采样该样本仍能被选中。经过 m m m个随机采样，得到 m m m个样本的采样集。（取出再放回重来，比如100个球，先取1个放采样集中，然后再放回，再从100个取1个放采样集）。
初始训练集中有的样本在采样集中多次出现，有的从未出现。初始训练集中约有63.2％样本出现在采样集中
Bagging基本流程：
可采样出
T
T
T个含
m
m
m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些学习器结合。
结合时
{
对分类任务使用简单投票法，票数一样随机取一个
对回归任务使用简单平均法
结合时 \begin{cases} 对分类任务使用简单投票法，票数一样随机取一个 & \\ 对回归任务使用简单平均法 & \\ \end{cases}
结合时{对分类任务使用简单投票法，票数一样随机取一个对回归任务使用简单平均法
自助采样过程给Bagging带来的优点： 由于每个基学习器只使用了初始训练集中约63.2％的样本，剩下约36.8%的样本可用作验证集对泛化性能进行“包外估计”
D
t
D_t
Dt表示
h
t
h_t
ht实际使用训练样本集
H
o
o
b
(
x
)
H^{oob}(x)
Hoob(x)表示对样本
x
x
x的包外预测，仅针对未使用的预测
包外估计
→
用途
{
基学习器是决策树，可辅助剪枝或辅助对零训练样本结点处理
基学习器是神经网络，辅助早期停止以减小过拟合风险
包外估计\xrightarrow{用途} \begin{cases} 基学习器是决策树，可辅助剪枝或辅助对零训练样本结点处理 & \\ 基学习器是神经网络，辅助早期停止以减小过拟合风险 & \\ \end{cases}
包外估计用途{基学习器是决策树，可辅助剪枝或辅助对零训练样本结点处理基学习器是神经网络，辅助早期停止以减小过拟合风险
Bagging主要关注降低方差，它在不剪枝决策树、神经网络等易受样本扰动的 学习器上效用明显
8.3.2随机森林（Random Forest，RF）
随机森林是Bagging一个扩展变体
RF以决策树为基学习器构建Bagging集成，在决策树训练过程中引入了随机属性选择
- 传统决策树在选择划分属性时是在当前结点的属性集合选一个最优属性
- RF中，对基决策树的每个结点，先从该结点属性集合随机选择一个包含
k
k
k个属性的集合，然后再从子集中选择最优属性划分。
其中： - k = d k=d k=d与传统决策树相同
- k = 1 k=1 k=1，随机选择一个属性用于划分
- 一般推荐， k = log 2 d k=\log_{2}{d} k=log2d
8.4结合策略
学习器结合带来的三个好处：
- 从统计方面，单学习器可能因误选而导致泛化性能不佳，结合多个学习器会减小这一风险
- 从计算方面，多次运行之后结合，可降低陷入糟糕局部极小点风险
- 从表示方面，结合多个学习器，相应的假设空间有所扩大，有可能学到更好的近似。
8.4.1平均法
对数值型输出 h i ( x ) ∈ R h_i(x)\in{R} hi(x)∈R,最常见的结合策略是使用平均法（averaging）
- 简单平均法
H ( x ) = 1 T ∑ i = 1 T h i ( x ) \begin{equation} H(x)=\frac{1}{T}\sum_{i=1}^Th_i(x) \tag{8.22} \end{equation} H(x)=T1i=1∑Thi(x)(8.22) - 加权平均法
H ( x ) = 1 T ∑ i = 1 T w i h i ( x ) \begin{equation} H(x)=\frac{1}{T}\sum_{i=1}^Tw_ih_i(x) \tag{8.23} \end{equation} H(x)=T1i=1∑Twihi(x)(8.23)
8.4.2投票法
学习器 h i h_i hi将从类别标记集合 { c 1 , c 2 , . . . c N } \{c_1,c_2,...c_N\} {c1,c2,...cN}中预测出一个标记。
将
h
i
h_i
hi在样本
x
x
x上的预测输出表示为
N
N
N维向量
(
h
i
1
(
x
)
,
h
i
2
(
x
)
,
.
.
.
h
i
N
(
x
)
)
(h_i^1(x),h_i^2(x),...h_i^{N}(x))
(hi1(x),hi2(x),...hiN(x)),
h
i
j
(
x
)
h_i^j(x)
hij(x)是
h
i
h_i
hi在类别
c
j
c_j
cj上的输出
不同类型个体学习器可能产生不同类型的 h i j ( x ) h_i^j(x) hij(x)的值，常见的有
- 类标记： h i j ( x ) ∈ { 0 , 1 } h_i^j(x)\in\{0,1\} hij(x)∈{0,1}, h i h_i hi将样本 X X X预测为 c j c_j cj的取值为1，或为0.称为“硬投票”
- 类概率： h i j ( x ) ∈ [ 0 , 1 ] h_i^j(x)\in[0,1] hij(x)∈[0,1],相当于后验概率 P ( c j ∣ x ) P(c_j|x) P(cj∣x)的一个估计，称为“软投票”
8.4.3学习法
当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器进行结合
Stacking是典型代表
将个体学习器称为初级学习器，用于结合的学习器称为次学习器或元学习器。
- Stacking先从初始数据集训练出初级学习器，“生成”一个新数据集用于训练次级学习器
- 初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记
- 次数训练集是利用初级学习器产生的
一般使用交叉验证或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本
将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归（Multi-response Linear Regression，简称MLR）作为次级学习算法效果最好，在MLR中使用不同的属性集更加
贝叶斯模型平均（bayes Model Averaging,BMA）基于后验概率来为不同模型赋予权重，可视为加强平均法的一种特殊实现。
Stacking通常优于BMA，鲁棒性好，对近似误差敏感。
8.5多样性
8.5.1误差-分歧分解
欲构建泛化能力强的集成，个体学习器应“好而不同”
假定用个体学习器 h 1 , h 2 , . . . h T h_1,h_2,...h_T h1,h2,...hT通过加强平均法结合产生的集成来完成回归学习任务 f : R d → R f:R^d\xrightarrow{}R f:RdR
对示例
x
x
x，定义学习器
h
i
h_i
hi的“分歧”为
A
(
h
i
∣
x
)
=
(
h
i
(
x
)
−
H
(
x
)
)
2
\begin{equation} A(h_i|x)=(h_i(x)-H(x))^2 \tag{8.27} \end{equation}
A(hi∣x)=(hi(x)−H(x))2(8.27)
集成的分歧是：
A
‾
(
h
∣
x
)
=
∑
i
=
1
T
w
i
A
(
h
i
∣
x
)
=
∑
i
=
1
T
w
i
(
h
i
(
x
)
−
H
(
x
)
)
2
\begin{equation} \overline{A}(h|x)=\sum_{i=1}^Tw_iA(h_i|x)\\ =\sum_{i=1}^Tw_i(h_i(x)-H(x))^2 \tag{8.27} \end{equation}
A(h∣x)=i=1∑TwiA(hi∣x)=i=1∑Twi(hi(x)−H(x))2(8.27)
显然，这里的分歧显示了个体学习器的多样性。
个体学习器
h
i
h_i
hi和集成
H
H
H的平方误差：
E
(
h
i
∣
x
)
=
(
f
(
x
)
−
h
i
(
x
)
)
2
E(h_i|x)=(f(x)-h_i(x))^2
E(hi∣x)=(f(x)−hi(x))2
E
(
H
∣
X
)
=
(
f
(
x
)
−
H
(
x
)
)
2
E(H|X)=(f(x)-H(x))^2
E(H∣X)=(f(x)−H(x))2
令
E
‾
(
h
∣
x
)
=
∑
i
=
1
T
w
i
∗
E
(
h
i
∣
x
)
\overline{E}(h|x)=\sum^T_{i=1}w_i*E(h_i|x)
E(h∣x)=∑i=1Twi∗E(hi∣x)表示个体学习器误差的加强均值
A
‾
(
h
∣
x
)
=
∑
i
=
1
T
w
i
A
(
h
i
∣
x
)
−
E
(
H
∣
X
)
=
E
‾
(
h
∣
x
)
−
E
(
H
∣
X
)
\begin{equation} \overline{A}(h|x)=\sum_{i=1}^Tw_iA(h_i|x)-E(H|X)=\overline{E}(h|x)-E(H|X) \tag{8.31} \end{equation}
A(h∣x)=i=1∑TwiA(hi∣x)−E(H∣X)=E(h∣x)−E(H∣X)(8.31)
8.5.2多样性度量
度量集成个体分类器的多样性，即估算个体学习器多样化程度。
比如考虑个体分类器的两两相似/不相似性
给定数据集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
(
x
m
,
y
m
)
}
D=\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\}
D={(x1,y1),(x2,y2),...(xm,ym)},对二分类任务，
y
i
∈
{
−
1
,
+
1
}
y_i\in\{-1,+1\}
yi∈{−1,+1}分类器
h
i
h_i
hi与
h
j
h_j
hj预测结果联表
a
a
a表示
h
i
,
h
j
h_i,h_j
hi,hj均预测为正类的样本数目。
a
+
b
+
c
+
d
=
m
a+b+c+d=m
a+b+c+d=m
8.5.3多样性增强
如何有效地增大多样性大的个体学习器，主要是对数据样本、输入属性、输出表示、算法参数进行扰动
