目录
- 1 基本概念
- 2 算法过程
- 2.1 AdaBoost以第一种定义的算法过程
- 2.2 AdaBoost以第二种定义的算法过程
- 2.2.1 前向分布算法
- 2.2.2 前向分布算法与AdaBoost
- 3 提升树
1 基本概念
（1）第一种定义
AdaBoost（Adaptive Boosting）是将多个弱分类器合成一个强分类器。通过提高被前一轮弱分类器错误分类样本的权值，而降低被分类正确的样本的权值，实现在每一轮改变训练数据的权值或概率分布，从而把当前轮没有得到正确分类的数据，通过权值的加大而在后一轮的弱分类器中得到更大的关注。弱分类器的组合，采用加权多数表决的方法。
（2）第二种定义
AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法的二分类学习方法。
2 算法过程
2.1 AdaBoost以第一种定义的算法过程
假设给定一个二分类的训练数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
N
,
y
N
)
}
(1)
T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\tag{1}
T={(x1,y1),(x2,y2),...,(xN,yN)}(1)
其中，每个样本点由实例与标记组成。实例
x
i
∈
X
⊆
R
n
x_i \in X \subseteq R^n
xi∈X⊆Rn，标记
y
i
∈
Y
=
{
−
1
,
+
1
}
y_i \in Y = \{-1,+1\}
yi∈Y={−1,+1}，X是实例空间，Y是标记集合。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成为一个强分类器。
输入：训练数据集T，弱分类学习算法。
输出：最终分类器 G ( x ) G(x) G(x)
（1）初始化训练数据的权值分布
D
1
=
(
w
11
,
.
.
.
,
w
1
i
,
.
.
.
,
w
1
N
)
,
w
1
i
=
1
N
,
i
=
1
,
2
,
.
.
.
,
N
(2)
D_1 = (w_{11},...,w_{1i},...,w_{1N}),w_{1i} = \frac{1}{N},i=1,2,...,N \tag{2}
D1=(w11,...,w1i,...,w1N),w1i=N1,i=1,2,...,N(2)
（2）对每一个基本弱分类器，m = 1,2,…,M
a. 使用具有权值分布
D
m
D_m
Dm的训练数据集学习，得到基本分类器
G
m
(
x
)
:
X
→
{
−
1
,
+
1
}
(3)
G_m(x):X \rightarrow \{-1,+1\} \tag{3}
Gm(x):X→{−1,+1}(3)
b. 计算
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
)
(4)
e_m = \sum_{i=1}^N P(G_m(x_i) \not = y_i) = \sum_{i=1}^Nw_{mi}I(G_m(x_i) \not = y_i) \tag{4}
em=i=1∑NP(Gm(xi)=yi)=i=1∑NwmiI(Gm(xi)=yi)(4)
w m i w_{mi} wmi表示第m轮中第i个实例的权值， ∑ i = 1 N w m i = 1 \sum_{i=1}^Nw_{mi} =1 ∑i=1Nwmi=1。
c. 计算
G
m
(
x
)
G_m(x)
Gm(x)的系数
α
m
=
1
2
l
n
(
1
−
e
m
e
m
)
,
l
n
(
⋅
)
表
示
自
然
对
数
(5)
\alpha_m = \frac{1}{2}ln( \frac{1-e_m}{e_m}) ,\quad ln(\cdot)表示自然对数 \tag{5}
αm=21ln(em1−em),ln(⋅)表示自然对数(5)
d. 更新训练数据集的权值分布
D
m
+
1
=
(
w
m
+
1
,
1
,
.
.
.
,
w
m
+
1
,
i
,
,
.
.
.
,
w
m
+
1
,
N
w
m
+
1
,
i
=
w
m
i
Z
m
e
x
p
(
−
α
m
y
i
G
m
(
x
i
)
)
,
i
=
1
,
2
,
.
.
.
,
N
(6)
D_{m+1} = (w_{m+1,1},...,w_{m+1,i,},...,w_{m+1,N}\\ w_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_m y_i G_m(x_i)),i = 1,2,...,N \tag{6}
Dm+1=(wm+1,1,...,wm+1,i,,...,wm+1,Nwm+1,i=Zmwmiexp(−αmyiGm(xi)),i=1,2,...,N(6)
这里，
Z
m
Z_m
Zm是规范化因子，使得
D
m
+
1
D_{m+1}
Dm+1成为一个概率分布。
Z
m
=
∑
i
=
1
N
w
m
i
e
x
p
(
−
α
m
y
i
G
m
(
x
i
)
)
(7)
Z_m = \sum_{i=1}^N w_{mi}exp(-\alpha_m y_iG_m(x_i)) \tag{7}
Zm=i=1∑Nwmiexp(−αmyiGm(xi))(7)
（3）构建基本分类器的线性组合
f
(
x
)
=
∑
m
=
1
M
α
m
G
m
(
x
)
(8)
f(x) = \sum_{m=1}^M \alpha_m G_m(x) \tag{8}
f(x)=m=1∑MαmGm(x)(8)
得到最终分类器
G
(
x
)
=
s
i
g
n
(
f
(
x
)
)
=
s
i
g
n
(
∑
m
=
1
M
α
m
G
m
(
x
)
)
(9)
G(x) = sign(f(x)) \\ = sign(\sum_{m=1}^M \alpha_mG_{m}(x)) \tag{9}
G(x)=sign(f(x))=sign(m=1∑MαmGm(x))(9)
2.2 AdaBoost以第二种定义的算法过程
2.2.1 前向分布算法
（1）基本思路
考虑加法模型
f
(
x
)
=
∑
m
=
1
M
β
m
b
(
x
;
γ
m
)
(10)
f(x) = \sum_{m=1}^M \beta_m b(x;\gamma _m) \tag{10}
f(x)=m=1∑Mβmb(x;γm)(10)
其中$ b(x;\gamma _m)
为
基
函
数
，
为基函数，
为基函数，\gamma _m
为
基
函
数
的
参
数
，
为基函数的参数，
为基函数的参数，\beta_m $为基函数的系数。和公式（8）对比，可知，其实公式（8）就是一个加法模型。
在给定训练数据及损失函数
L
(
y
,
f
(
x
)
)
L(y,f(x))
L(y,f(x))的条件下，学习加法模型
f
(
x
)
f(x)
f(x)称为经验风险极小化即损失函数最小化问题：
m
i
n
β
m
,
γ
m
∑
i
=
1
N
L
(
y
i
,
∑
m
=
1
M
β
m
b
(
x
i
;
γ
m
)
)
(11)
min_{\beta_m,\gamma_m} \sum_{i=1}^NL(y_i,\sum_{m=1}^M \beta_m b(x_i;\gamma_m)) \tag{11}
minβm,γmi=1∑NL(yi,m=1∑Mβmb(xi;γm))(11)
公式（11）通常是一个复杂的优化问题。前向分布算法求解这一优化问题的思路：因为学习的是加法模型，如果能够从前往后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：
m
i
n
β
,
γ
∑
i
=
1
N
L
(
y
i
,
β
b
(
x
i
;
γ
)
)
(12)
min_{\beta,\gamma} \sum_{i=1}^N L(y_i,\beta b(x_i;\gamma)) \tag{12}
minβ,γi=1∑NL(yi,βb(xi;γ))(12)
（2）算法步骤
输入：训练数据集T，损失函数 L ( y , f ( x ) ) L(y,f(x)) L(y,f(x))；基本函数集 { b ( ) x ; γ } \{b()x;\gamma\} {b()x;γ};
输出：加法模型f(x)
（1）初始化 f 0 ( x ) = 0 f_0(x) = 0 f0(x)=0;
（2）对m = 1,2,…,M
a. 极小化损失函数
(
β
m
,
γ
m
)
=
a
r
g
m
i
n
β
,
γ
∑
i
=
1
N
L
(
y
i
,
f
m
−
1
(
x
i
)
+
β
b
(
x
i
;
γ
)
)
(13)
(\beta_m,\gamma_m) = arg min_{\beta,\gamma}\sum_{i=1}^N L(y_i,f_{m-1}(x_i)+ \beta b(x_i;\gamma)) \tag{13}
(βm,γm)=argminβ,γi=1∑NL(yi,fm−1(xi)+βb(xi;γ))(13)
得到参数
β
m
,
γ
m
\beta_m,\gamma_m
βm,γm。
b. 更新
f
m
(
x
)
=
f
m
−
1
(
x
)
+
β
m
b
(
x
;
γ
m
)
(14)
f_m(x ) = f_{m-1}(x) + \beta_mb(x;\gamma_m) \tag{14}
fm(x)=fm−1(x)+βmb(x;γm)(14)
（3）得到加法模型
f
(
x
)
=
f
M
(
x
)
=
∑
m
=
1
M
β
m
b
(
x
;
γ
m
)
(15)
f(x) =f_M(x) = \sum_{m=1}^M \beta_m b(x;\gamma _m) \tag{15}
f(x)=fM(x)=m=1∑Mβmb(x;γm)(15)
这样，前向分布算法将同时求解从m = 1到M所有参数
β
m
,
γ
m
\beta_m,\gamma_m
βm,γm的优化问题简化为逐次求解各个
β
m
,
γ
m
\beta_m,\gamma_m
βm,γm的优化问题。
2.2.2 前向分布算法与AdaBoost
由前向分布算法那可以推导出AdaBoost，可用如下定理叙述这一关系。
定理：AdaBoost算法是前项分布算法加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数时指数函数。
3 提升树
提升方法采用加法模型与前向分布算法，以决策树为基函数的提升方法为提升树。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。
针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。
- 回归问题：平方误差损失函数
- 分类问题：指数损失函数
- 一般决策问题：一般损失函数
