- 1 基本概念
- 2 算法过程
- 2.1 AdaBoost以第一种定义的算法过程
- 2.2 AdaBoost以第二种定义的算法过程
- 2.2.1 前向分布算法
- 2.2.2 前向分布算法与AdaBoost
- 3 提升树
（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 提升树提升方法采用加法模型与前向分布算法，以决策树为基函数的提升方法为提升树。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。 针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。
- 回归问题：平方误差损失函数
- 分类问题：指数损失函数
- 一般决策问题：一般损失函数
