3

集成学习——AdaBoost多分类算法

之前介绍了集成学习——AdaBoost算法,该算法用于二分类问题,为了让AdaBoost算法能够用于多分类问题,Ji Zhu等人提出了SAMME和SAMME.R算法,它们适合用于多分类,SAMME.R算法使用概率权重,收敛效率和分类准确率高于SAMME算法,下面给出这两个算法的过程

SAMME算法
输入:训练数据集\(T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}\),其中\(x_i\epsilon{X}\subseteq{R^n}\),\(y_i\epsilon{Y}=\{1,2,…,K\}\);弱学习算法;
输出:最终分类器\(G(x)\)。
(1)初始化训练数据的权值分布

$$D_1=(w_{11},\dots,w_{1i},\dots,w_{1N}) \quad w_{1i}=\frac{1}{N}  \quad i=1,2,\dots,N$$

(2)对\(m=1,2,…,M\)
(a)使用具有权值分布$D_m$的训练数据集学习,得到基本的分类器(决策树桩或者是层数很小的决策树)
$$G_m(x):X\leftrightarrow{\{1,2,…,K\}}$$
(b)计算$G_m(x)$在训练数据集上的分类误差率

\[
e_m=P(G_m(x_i)\neq{y_i})=\sum_{i=1}^{N}w_{mi}{I(G_m(x_i)\neq{y_i})}$
\]

(c)计算$G_m(x)$的系数

\[
\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m} + \log(K-1)
\]

其中,对数是自然对数
(d)更新训练数据集的权值分布

\[
\begin{split}
D_{m+1}=(w_{m+1},_1,…,w_{m+1},_i,…,w_{m+1},_N)\\
w_{m+i},_i=\frac{w_{mi}}{Z_m}exp(-\alpha_m{y_i}G_m(x_i)),\quad{i=1,2,…,N}
\end{split}
\]

这里,$Z_m$是规范化因子

\[
Z_m=\sum_{i=1}^{N}{w_{mi}}exp(-\alpha_m{y_i}G_m(x_i))
\]

它使$D_{m+1}$成为一个概率分布
(3)构建基本分类器的线性组合

\[
f(x)=\sum_{m=1}^{M}\alpha_mG_m(x)
\]

得到最终的分类器

\[
G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_mG_m(x))
\]

SAMME.R算法
(1) Initialalize the observation weights $w_i=\frac{1}{n},i=1,2,…,n$
(2) For $m=1$ to $M$:
(a) Fit a classifer $T^{(m)}(x)$ to the training data using weights $w_i$.
(b) Obtain the weighted class probability estimates
\[
p^{(m)}_k(x)=Prob_w(c=k|x),k=1,2,…,K
\]
(c) Set
\[
h^{(m)}_k(x) =(K-1)(\log{p^{(m)}_k(x)}-\frac{1}{K}\sum_{k’}^{}\log{p}^{(m)}_{k’}(x)),k=1,2,…,K.
\]
(d) Set
\[
w_i=w_i * exp(-\frac{K-1}{K}y^T_i\log{p^{(m)}(x_i)}),i=1,2,…,m.
\]
(e) Re-normalize $w_i$
(3) Output
\[
C(x)=\arg\max_k{\sum_{m=1}^{M}h^{(m)}_k(x)}
\]

总结

SAMME与AdaBoost.M1算法(二分类AdaBoost算法)只有细微的差别,细心看的话相信已经察觉了,而SAMME.R算法使用了每个类在样本集中的权重来得到$h^{(m)}_k(x)$,然后选择使得$C(x)$最大的那个类作为输出类。SAMME.R的权重是多少呢?是不是有这个疑问,答案是$1$,是不是很神奇!

引用

  • 李航《统计学习方法》
  • J. Zhu, H. Zou, S. Rosset, T. Hastie, “Multi-class AdaBoost”, 2006.

goingmyway

我是一只野生程序猿,我关注机器学习,神经网络,深度学习,增强学习,人工智能,Python,C/C++,Linux

3 Comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注