AdaBoost算法

本篇笔记是针对二分类的AdaBoost算法总结。主要参考林轩田老师的《机器学习技法》课程，以及李航博士的《统计学习方法》第二版。没错，第二版已经出版了，快去买啊！

符号声明

• \(D = \{(x_1, y_1), (x_2, y_2), (x_3, y_3), \cdots, (x_N, y_N)\}\) - 用于训练的数据集，\(x_n\)为实例，\(y_n\)为对应的标签{-1, +1}
• \(T\) - 需要训练的基分类器总个数
• \({g_t}\) - 第t轮训练出的基分类器，\(t = 1, 2, 3, ..., T\)
• \(u^{(t)} = \{u_{1}^{(t)}, u_{2}^{(t)}, u_{3}^{(t)}, \cdots, u_{N}^{(t)}\}\) - 第\(t\)轮的样本权重
• \(G\) - 最终的强分类器
• \(\left[\left[ \cdot \right]\right]\) - 双中括号内的·若为真，则\(\left[\left[ \cdot \right]\right]=1\)，否则\(\left[\left[ \cdot \right]\right]=0\)

算法

???

为什么这样更新权重

集成学习的思想主要体现在“多个弱分类器通过某种方式组合得到最终的强分类器”。要想最后的强分类器有好的性能，则需要保证每个弱分类器尽可能的不同。

那么如何能让每个分类器尽量的不同？

第\(t\)轮训练的基分类器是\({g_t}\),然后根据\({g_t}\)在带有权重\(\{{u_n}^{(t)}\}\)的训练集\(D\)上的表现更新权重至\(\{{u_n}^{(t+1)}\}\)。倘若上一轮的\({g_t}\)在下一轮权重为\(\{{u_n}^{(t+1)}\}\)的训练集\(D\)上表现得不好，则可以认为\({g_t}\)和\({g_{t+1}}\)比较的不同。

也就是说，如果满足：\[ \begin{equation} \frac{\sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} \neq g_{t}\left(\mathbf{x}_{n}\right)\right]\right]}{\sum_{n=1}^{N} u_{n}^{(t+1)}}=\frac{1}{2} \end{equation} \]

\((1)\)说明\({g_t}\)在第\(t+1\)轮的训练集上表现得就像随机乱猜一样，是\(\frac{1}{2}\)的概率。而在该轮训练集上经过训练后确定下来的\({g_{t+1}}\)应该是性能比较好的，所以可以说\({g_t}\)和\({g_{t+1}}\)是比较不同的。

那要如何更新第\(t\)轮的权重能满足\((1)\)？

显然，有\[ \begin{equation} \sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} \neq g_{t}\left(\mathbf{x}_{n}\right)\right]\right] + \sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} = g_{t}\left(\mathbf{x}_{n}\right)\right]\right] = \sum_{n=1}^{N} {u_{n}^{(t+1)}} \end{equation} \]

所以，\((1)\)可以写为\[ \begin{equation} \frac{\sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} \neq g_{t}\left(\mathbf{x}_{n}\right)\right]\right]}{\sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} \neq g_{t}\left(\mathbf{x}_{n}\right)\right]\right] + \sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} = g_{t}\left(\mathbf{x}_{n}\right)\right]\right]}=\frac{1}{2} \end{equation} \]

为了最后得到的概率为\(\frac{1}{2}\)，那么需要\[ \begin{equation} \sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} \neq g_{t}\left(\mathbf{x}_{n}\right)\right]\right] = \sum_{n=1}^{N} u_{n}^{(t+1)}\left[\left[y_{n} = g_{t}\left(\mathbf{x}_{n}\right)\right]\right] \end{equation} \]

那么更新的做法可以如下所示：

?

最终将两者一整合，就能得到每次更新的方式，如同上述算法所述。

为什么选择\(\alpha_t\)作为基分类器前的权重

• 待编辑

AdaBoost算法

原文：https://www.cnblogs.com/shayue/p/AdaBoost-suan-fa.html