提升方法

机器学习 提升方法

---

主要思想是通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

adaboost算法
一个概念，如果存在一个多项式学习算法可以学习它，并且正确率很高，那么就称这个概念是强可学习的
如果不存在，那么这个概念就是弱可学习的。
强可学习性和弱可学习性等价。

假设给定二类分类的训练数据集
输入：

$$T = \{(x_1,y_1),(x_2,y_2),...(x_N,y_N)\}, x_i \in X \subseteq R^n, y_i \in Y = \{-1,+1\}$$
输出：最终分类器$G(x)$
1) 初始化训练数据的权值分别
$$D_i=(w_{11},...,w_{1i},...,w_{1N}), w_{1i} = \frac{1}{N}, i=1,2,...,N$$
2) 对$m=1,2,...,M$
- 使用具有权值分布$D_m$的训练数据集学习， 得到基本分类器
$$G_m(x): X \to \{-1, +1\}$$
3) 计算$G_m(x)$在训练集上的分类误差率
$$e_m = P(G_m(x) \neq y_i) = \sum_{i=1}^{N}W_{mi}I(G_m(x_i) \neq y_i)$$
4) 计算$G_m(x)$的系数
$$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$$

x = np.arange(0, 1, 0.001)
plt.plot(x, (np.log(1-x) - np.log(x))/2)
plt.plot(x, np.zeros(x.shape))
plt.xlabel("em")
plt.ylabel("am")

5) 更新训练数据集的权值分布

$$D_{m+1} = (w_{m+1,1}, w_{m+1, 2}, ... w_{m+1, N})$$
$$w_{m+1, i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i))$$
$$Z_m = \sum_{i=1}^{N}w_{mi}exp(-\alpha_my_iG_m(x_i))$$
6) 构建基本分类器的线性组合
$$f(x)=\sum_{m=1}^{M}\alpha_mG_m(x)$$

分析：

$$Z_m = \frac{w_mi}{Z_m}e^{-\alpha_m}, G_m(x_i) = y_i$$
$$Z_m = \frac{w_mi}{Z_m}e^{\alpha_m}, G_m(x_i) \neq y_i$$

被错误分类的样例在下一轮分类器中权值会被放大。

AdaBoost算法的训练误差分析

定理8.1
AdaBoost算法最终分类器的训练误差界为

$$\frac{1}{N}\sum_{i=1}^{N}I(G(x_i) \neq y_i) \leq \frac{1}{N}\sum_{i}exp(-y_if(x_i))=\prod_{m}Z_m$$

定理8.2
二类分类问题AdaBoost的训练误差界

$$\prod_{m=1}^{M}Z_m = \prod_{m=1}^{M}[{\sqrt{(1-4{\gamma_m}^2)}]} \leq exp(-2\sum_{m=1}^{M}{\gamma_m}^2), \gamma_m=1/2-e_m$$

AdaBoost算法的解释

可认为AdaBoost算法是模型为加法模型，损失函数为指数函数，学习函数为前向分布算法时的二类分类学习方法。

考虑加法模型：

$$f(x) = \sum_{m=1}^{M}\beta_mb(x;\gamma_m)$$
其中，$b(x;\gamma_m)$为基函数，$\gamma_m$为基函数的参数，$\beta_m$为基函数的系数；

经验风险极小化，即损失函数极小化

$$\min_{\beta_m,\gamma_m}\sum_{i=1}^{N}L(y_i,\sum_{m=1}^{M}\beta_mb(x_i;\gamma_m))$$
那么每一步只需要优化如下损失函数
$$\min_{\beta,\gamma}\sum_{i=1}^{N}L(y_i,\beta b(x_i;\gamma))$$

前向分步算法

输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...(x_N,y_N)\}$；损失函数$L(y,f(x))$;基函数集$\{b(x;\gamma)\}$
输出：加法模型$f(x)$
1) 初始化$f_0(x)=0$
2) 对$m=1,2,...,M$
a）极小化损失函数

$$(\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))$$ 得到参数$\beta_m, \gamma_m$
b) 更新
$$f_m(x) = f_{m-1}(x) + \beta_mb(x;\gamma_m)$$
3) 得到加法模型
$$f(x) = f_M(x) = \sum_{m=1}^{M}\beta_mb(x;\gamma_m)$$

前向分布算法与adaboost

AdaBoost算法是前向分布加法算法的特例，模型是由基本分类器组成的加法模型，损失函数是指数函数。

提升树

提升树是以分类树或回归树为基本分类器的提升方法。
提升树可以表示为决策树的加法模型

$$f_M(x) = \sum_{m=1}^{M}T(x_i;\Theta_m)$$

提升树算法

提升树算法采用前向分步算法。

$$f_0(x) = 0$$
$$f_m(x) = f_{m-1}(x) + T(x; \Theta_m)$$
$${\hat{\Theta}}_m = arg \min_{\Theta_m}\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i)+T(x_i;\Theta_m))$$

已知一个训练数据集$T=\{(x_1,y_1),(x_2,y_2),...(x_N,y_N)\}, x_i \in X \subseteq R^n, y_i \in Y \subseteq R$，回归树是将输入空间$X$划分为$J$个互不相交的区域$R_1,R_2,...R_J$，并且在每个区域上确定输出的常量$c_j$，那么树可表示为

$$T(x;\Theta) = \sum_{j=1}^{J}c_jI(x\in R_j)$$

当采用评分误差损失函数时

$$L(y,f(x)) = {(y-f(x)}^2$$
$$L(y, f_{m-1}(x)+T(x;\Theta_m)) = {[y-f_{m-1}(x)-T(x;\Theta_m)]}^2 = {[r-T(x;\Theta_m)]}^2$$
$$r = y-f_{m-1}(x)$$
是当前模型拟合数据的残差residual。那么对回归问题的提升树算法来说，只需简单的拟合当前模型的残差。

回归问题的提升树算法
输入：数据集$T=\{(x_1,y_1),(x_2,y_2),...(x_N,y_N)\}, x_i \in X \subseteq R^n, y_i \in Y \subseteq R$
输出：提升树$f_M(x)$
1) 初始化$f_0(x)=0$
2) 对$m=1,2...M$
a) 计算残差$r_{mi}=y_i-f_{m-1}(x_i), i=1,2,...,N$
b) 拟合残差，学习一个回归树，得到$T(x;\Theta_m)$
c) 更新$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$
3) 得到提升树$f_M(x)=\sum_{i=1}^{M}T(x;\Theta_m)$