统计机器学习-提升方法

作者: 又双叒叕苟了一天 | 来源:发表于2020-07-16 17:01 被阅读0次

提升方法的思路就是学习多个分类器，对多个分类器进行线性组合，提高分类的性能。首先定义强可学习和弱可学习。如果存在一个多项式的学习算法可以学习一个分类，并且正确率很高，则称为强可学习。如果一个多项式的学习算法可以学习一个分类，并且正确率相比随机猜测要略好，那么称为弱可学习。事实上，两者是等价的，即一个问题弱可学习，则可以强可学习。提升方法的目标就是组合弱分类器，使其称为一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

提升方法需要解决两个问题：

（1）每一轮如何改变训练数据的权值或概率分布

（2）如何将若分类器组合成一个强分类器

对于这两个问题，Adaboost（适应性提升方法）的做法是：

（1）训练数据被分类错误，权值上升，被分类正确，权值下降

（2）加权多数表决，误差率越小，权值越高

AdaBoost算法

输入：训练数据集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，其中 $x_i\in\mathcal X\subseteq\textbf R^n$ ， $y_i\in\mathcal Y= \{-1,+1\}$ ；弱学习算法

输出：最终分类器 $G(x)$ 。

（1）初始化训练数据的权值分布
$D_1=(w_{11},w_{12},\cdots,w_{1i},\cdots,w_{1N}),\ \ w_{1i}=\frac1N,\ \ i=1,2,\cdots,N$
（2）对 $m=1,2,\cdots,M$

（a）使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器
$G_m(x):\mathcal X\rightarrow\{-1,+1\}$
（b）计算 $G_m(x)$ 在训练数据集上的分类误差率
$e_m=\sum_{i=1}^NP(G_m(x)\neq y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)$
（c）计算 $G_m(x)$ 的系数
$\alpha_m=\frac12\log\frac{1-e_m}{e_m}$
这里的对数是自然对数。

（d）更新训练数据集的权值分布
$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)),\ \ i=1,2,\cdots,N$

这里， $Z_m$ 是规范化因子
$Z_m=\sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i))$
它使 $D_{m+1}$ 成为一个概率分布。

（3）构建基本分类器的线性组合
$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$
得到最终分类器
$G(x)=\mathrm{sign}(f(x))=\mathrm{sign}\bigg(\sum_{m=1}^M\alpha_mG_m(x)\bigg)$
对AdaBoost算法作如下说明

（1）训练数据集初始权值均匀分布，保证能够在原始数据上学习基本分类器 $G_1(x)$

（2）每轮训练一个分类器， $M$ 轮共训练 $M$ 个弱分类器

（a）使用加权的数据集学习弱分类器

（b）分类的误差率也是加权得到的

（c）系数 $\alpha_m$ 根据计算公式可以得知，随着误差率 $e_m$ （在 $e_m\leq\frac12$ 时，因为弱分类器分类误差小于等于 $\frac12$ ）的减小而增大，即误差越小的弱分类器，所起的作用越大。

（d）权值更新公式
$w_{m+1,i}= \begin{cases} \frac{w_{mi}}{Z_m}e^{-\alpha_m},&G_m(x_i)=y_i\\ \frac{w_{mi}}{Z_m}e^{\alpha_m},&G_m(x_i)\neq y_i \end{cases}$
因为弱分类器分类误差 $e_m\leq\frac12$ ，所以 $\alpha_m=\frac12\log\frac{1-e_m}{e_m}\geq0$ 。当分类正确时， $e^{-\alpha_m}\leq1$ ，样本权值变小，当分类错误时， $e^{-\alpha_m}\geq1$ ，样本权值变大。

提升树

提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。决策树部分可以查看决策树，此处略。分类提升树只需将上述算法的弱分类器限制为二类分类树，这里介绍回归提升树，推导过程略。

回归问题的提升树算法

输入：训练数据集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，其中 $x_i\in\mathcal X\subseteq\textbf R^n$ ， $y_i\in\mathcal Y\subseteq\textbf R$ ；

输出：提升树 $f_M(x)$ 。

（1）初始化 $f_0(x)=0$

（2）对 $m=1,2,\cdots,M$

（a）计算残差
$r_{mi}=y_i-f_{m-1}(x_i),\ \ i=1,2,\cdots,N$
（b）拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x;\Theta_m)$

（c）更新 $f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$

（3）得到回归问题提升树
$f_M(x)=\sum_{m=1}^MT(x;\Theta_m)$
需要注意的是，这里残差是根据平方误差损失计算得到的。

梯度提升

上述算法中的残差是基于损失函数是平方误差损失得到的，如果不是平方误差损失，则根据梯度提升算法，可以用损失函数的负梯度作为上述算法残差的近似，即
$-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}$
可以看到在使用平方误差损失时：
$-\bigg[\frac{\partial L(y,f(x))}{\partial f(x)}\bigg]=-\frac{\partial\frac12(y-f_{m-1}(x))^2}{\partial f(x)}=y-f_{m-1}(x)$
所以上述回归问题的提升树算法是梯度提升算法在使用平方误差损失时的一个特例。

梯度提升算法

输入：训练数据集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，其中 $x_i\in\mathcal X\subseteq\textbf R^n$ ， $y_i\in\mathcal Y\subseteq\textbf R$ ；损失函数 $L(y,f(x))$

输出：回归树 $\hat f(x)$ 。

（1）初始化
$f_0(x)=\arg\min_c\sum_{i=1}^NL(y_i,c)$
（2）对 $m=1,2,\cdots,M$

（a）对 $i=1,2,\cdots,N$ ，计算
$r_{mi}=-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}$
（b）对 $r_{mi}$ 拟合一个回归树，得到第 $m$ 棵树的叶结点区域 $R_{mj}$ ， $j=1,2,\cdots,J$

（c）对 $j=1,2,\cdots,J$ ，计算
$c_{mj}=\arg\min_c\sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$
（d）更新 $f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$

（3）得到回归树
$\hat f(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$
需要注意的是，在第(1)步初始化时，选择的是让损失函数最小的常数值。在(2)(b)时，估计叶结点区域（ $J$ 个区域），以拟合残差的近似值。(2)(c)时利用现行搜索，搜索估计叶结点区域的值，使损失函数最小化（在平方误差损失时，容易得知 $c_j$ 是该结点区域所有 $y_i$ 的均值）。

统计机器学习-提升方法

AdaBoost算法

提升树

回归问题的提升树算法

梯度提升

梯度提升算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读