统计学习方法（八）提升方法

发表于 更新于 分类于 阅读次数：
本文字数： 3.1k

提升方法，在分类问题中通过改变训练样本的权重，学习多个分类器，并将分类器线性组合，提高分类的性能。

8.1 AdaBoost算法

提升方法的思想是，对于一个复杂任务来说，综合多个专家的判断得出的判断效果更好。

  • 强可学习：在概率近似正确学习（PAC）的框架中，一个概念（一个类），如果存在一个多项式的学习算法 能够学习它，并且正确率很高，那么就称这个概念是强可学习的-
  • 弱可学习：一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。

Schapire后来证明强可学习与弱可学习是等价的，也即在PAC学习的框架下，一个概念是强可学习的充要条件是这个概念是弱可学习的。

利用这个前提，如果在学习中发现了”弱学习算法“，可以将其提升为”强学习算法“。对于分类问题而言，给定训练集，从弱学习算法出发，反复学习，得到一系列弱分类器，组合这些弱分类器构成一个强分类器。

给定一个二分类训练集 \[ T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} \\ x\in{\cal X}\subset{\mathbb R}^n,\quad y_i\in{\cal Y}=\{-1.+1\} \] 初始化训练数据的权值分布 \[ D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N}),\quad w_{1i}=\frac1N,\quad i=1,2,\cdots,N \] 使用权值分布为\(D_m\)的训练集学习，得到基本分类器 \[ G_m(x):{\cal X}\rightarrow\{-1,+1\} \] 计算分类器在训练集上的分类误差率 \[ e_m=\sum_{i=1}^NP(G_m(x_i)\neq y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i) \] 计算分类器的系数，取自然对数 \[ \alpha_m=\frac12\log\frac{1-e_m}{e_m} \] 更新训练集的权值分布 \[ D_{m+1}=(w_{m+1.1},\cdots,w_{m+1,i},\cdots,w_{m+1,N})\\ w_{m+1,i}=\frac{w_{mi}}{Z_m}\exp(-\alpha_my_iG_m(x_i)),\quad i=1,2,\cdots,N \] 其中，\(Z_m\)是规范化因子，使得\(D_{m+1}\)成为一个概率分布。 \[ Z_m = \sum_{i=1}^N{w_{mi}}\exp(-\alpha_my_iG_m(x_i)) \] 根据基本分类器，构造线性组合，得到最终分类器 \[ f(x)=\sum_{m=1}^M\alpha_mG_m(x) \\ G(x)=sign(f(x)) \] 计算\(G_m(x)\)系数\(\alpha_m\)时，\(e_m\leq\frac12\)时，\(\alpha_m\geq0\)，并且\(\alpha_m\)关于\(e_m\)递减，所以分类误差率越小的基本分类器，在最终分类器中的作用越大。

更新权值时，可以写成如下形式： \[ \begin{align} w_{m+1,i}=\begin{cases}\frac{w_{mi}}{Z_m}e^{-\alpha_m},\quad &G_m(x_i)=y_i\\\frac{w_{mi}}{Z_m}e^{\alpha_m},\quad &G_m(x_i)\neq y_i\end{cases} \end{align} \] 所以误分类样本的权值得以扩大，在下一轮学习中起更大的作用。不改变训练数据，而不断改变训练数据权值的分布，这是AdaBoost的一个特点。

注意，\(\sum\alpha_m\neq1\)$

8.2 AdaBoost算法的训练误差分析

定理 8.1 AdaBoost算法最终分类器的训练误差界为 \[ \frac1N\sum_{i=1}^NI(G(x_i)\neq y_i)\leq\frac1N\sum_i\exp(-y_if(x_i))\neq y_i)=\prod_mZ_m \] 定理8.2 二分类问题中，AdaBoost的训练误差界为 \[ \begin{align} \prod_{m=1}^MZ_m&=\prod_{m=1}^M[2\sqrt{e_m(1-e_m)}]\\ &=\prod_{m=1}^M\sqrt{(1-4\gamma_m^2)}\\ &\leq\exp(-2\sum_{m=1}^M\gamma_m^2) \end{align} \] 其中，\(\gamma_m=\frac12-e_m\)$

8.3 AdaBoost算法的解释

前向分步算法

考虑加法模型 \[ f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m) \] 其中，\(b(x;\gamma_m)\)为基函数，\(\gamma_m\)为函数的参数。

给定训练集及损失函数\(L(y,f(x))\)的条件下，学习加法模型即为损失函数极小化问题 \[ \min_{\beta_m,\gamma_m}\sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m)) \] 通常这是一个复杂的优化问题，前向分步算法的想法是：因为学习的是加法模型，如果能够从前向后，每步只学习一个基函数与系数，逐步逼近，就可以简化复杂度，即每步只考虑优化如下函数 \[ \min_{\beta,\gamma}\sum_{i=1}^NL(y_i,\beta b(x_i;\gamma)) \]

前向分步与AdaBoost

定理8.3 AdaBoost是前向分步算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。

8.4 提升树

提升树模型

提升方法实际采用加法模型与前向分步算法，以决策树为基函数的提升方法就称为提升树。

提升树模型可以表示为决策树的加法模型 \[ f_M(x)=\sum_{m=1}^MT(x;\Theta_m) \] 其中，\(T(x;\Theta_m)\)表示决策树，\(M\)表示树的个数。

提升树算法

首先初始化提升树\(f_0(x)=0\)，第m步的模型是 \[ f_m(x)=f_{m-1}(x)+T(x;\Theta_m) \] 通过经验风险最小化确定下一棵决策树的参数 \[ \hat\Theta_m=\arg\min_{\Theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m)) \] 对于二分类问题，提升树算法只需要将AdaBoost的基本分类器限制为二类分类树即可，此时的提升树算法是AdaBoost的特殊情况。

梯度提升

对于提升树算法，当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。

对于一般损失函数，Freidman提出了梯度提升算法，利用损失函数的负梯度值 \[ -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} \] 作为回归问题中残差的近似值，拟合回归树。

Scikit-learn

from sklearn.ensemble import AdaBoostClassifier

clf = AdaBoostClassifier(n_estimators=100, learning_rate=0.5)
clf.fit(X_train, y_train)

clf.score(X_test, y_test)
相关文章