|
Boosting主要思想是通过多个模型去学习同一个数据集，从而得到多个简单的弱分类器模型，最后将这些模型组成一个性能十分强大的机器学习模型。
Valiant 和Kearns提出“弱可学习”和“强可学习”的概念。同时，Schapire证明出，强可学习和弱可学习是等价的。也就是一个概念可强学习的充分必要条件是这个概念可弱学习。
- 弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）
- 强学习：识别准确率很高并能在多项式时间内完成的学习算法
大多数的boosting算法通过改变训练集的概率分布或者权重，针对不同的数据分布调用不同的学习器。那么对于boosting方法来说，最重要的问题就是1、每一轮的学习如何改变数据 概率分布。2、如何将这些弱学习器组成一个强学习器。
AdaBoost
对于Adaboost来说，解决上述的两个问题的方式是：1. 提高那些被前一轮分类器错误分类的样本的权重，而降低那些被正确分类的样本的权重。这样一来，那些在上一轮分类器中没有得到正确分类的样本，由于其权重的增大而在后一轮的训练中“备受关注”。2. 各个弱分类器的组合是通过采取加权多数表决的方式，具体来说，加大分类错误率低的弱分类器的权重，因为这些分类器能更好地完成分类任务，而减小分类错误率较大的弱分类器的权重，使其在表决中起较小的作用。
现在，我们来具体介绍Adaboost算法：
假设给定一个二分类的训练数据集：
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)}，其中每个样本点由特征与类别组成。特征
x
i
∈
X
?
R
n
x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}
xi?∈X?Rn，类别
y
i
∈
Y
=
{
?
1
,
+
1
}
y_{i} \in \mathcal{Y}=\{-1,+1\}
yi?∈Y={?1,+1}，
X
\mathcal{X}
X是特征空间，$ \mathcal{Y}
是
类
别
集
合
，
输
出
最
终
分
类
器
是类别集合，输出最终分类器
是类别集合，输出最终分类器G(x)
。
A
d
a
b
o
o
s
t
算
法
如
下
：
(
1
)
初
始
化
训
练
数
据
的
分
布
：
。Adaboost算法如下： (1) 初始化训练数据的分布：
。Adaboost算法如下：(1)初始化训练数据的分布：D_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right), \quad w_{1 i}=\frac{1}{N}, \quad i=1,2, \cdots, N$
(2) 对于m=1,2,…,M
- 使用具有权值分布
D
m
D_m
Dm?的训练数据集进行学习，得到基本分类器：
G
m
(
x
)
:
X
→
{
?
1
,
+
1
}
G_{m}(x): \mathcal{X} \rightarrow\{-1,+1\}
Gm?(x):X→{?1,+1}
- 计算
G
m
(
x
)
G_m(x)
Gm?(x)在训练集上的分类误差率
e
m
=
∑
i
=
1
N
P
(
G
m
(
x
i
)
≠
y
i
)
=
∑
i
=
1
N
w
m
i
I
(
G
m
(
x
i
)
≠
y
i
)
e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{m i} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)
em?=∑i=1N?P(Gm?(xi?)?=yi?)=∑i=1N?wmi?I(Gm?(xi?)?=yi?)
- 计算
G
m
(
x
)
G_m(x)
Gm?(x)的系数
α
m
=
1
2
log
?
1
?
e
m
e
m
\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}
αm?=21?logem?1?em??，这里的log是自然对数ln
- 更新训练数据集的权重分布
D
m
+
1
=
(
w
m
+
1
,
1
,
?
?
,
w
m
+
1
,
i
,
?
?
,
w
m
+
1
,
N
)
w
m
+
1
,
i
=
w
m
i
Z
m
exp
?
(
?
α
m
y
i
G
m
(
x
i
)
)
,
i
=
1
,
2
,
?
?
,
N
\begin{array}{c} D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right) \\ w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2, \cdots, N \end{array}
Dm+1?=(wm+1,1?,?,wm+1,i?,?,wm+1,N?)wm+1,i?=Zm?wmi??exp(?αm?yi?Gm?(xi?)),i=1,2,?,N?
这里的
Z
m
Z_m
Zm?是规范化因子，使得
D
m
+
1
D_{m+1}
Dm+1?称为概率分布，
Z
m
=
∑
i
=
1
N
w
m
i
exp
?
(
?
α
m
y
i
G
m
(
x
i
)
)
Z_{m}=\sum_{i=1}^{N} w_{m i} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right)
Zm?=∑i=1N?wmi?exp(?αm?yi?Gm?(xi?))
(3) 构建基本分类器的线性组合
f
(
x
)
=
∑
m
=
1
M
α
m
G
m
(
x
)
f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)
f(x)=∑m=1M?αm?Gm?(x)，得到最终的分类器
G
(
x
)
=
sign
?
(
f
(
x
)
)
=
sign
?
(
∑
m
=
1
M
α
m
G
m
(
x
)
)
\begin{aligned} G(x) &=\operatorname{sign}(f(x)) \\ &=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right) \end{aligned}
G(x)?=sign(f(x))=sign(m=1∑M?αm?Gm?(x))?
|