机器学习技法笔记 – Adaptive Boosting(AdaBoost)

Motivation of Boosting

在上一章中,我们证明了在Blending时,如果\(g_t(x)\)之间的差异越大,则最后得到的\(G(x)\)的泛化能力越强。

在上一章的结尾我们介绍了Bootstrap,这Bagging Aggregation种方法通过在数据集\(D\)中随机抽取\(N\)组数据,重复\(T\)次,每次训练出\(g_t(x)\),然后在用Linear Blending做Aggregation,得到\(G(x)\),这是一种通过数据集的差异性来获得\(g_t(x)\)的方法。

在本章中,我们将引入Weighted(权重)的概念,并介绍一种Weighted Base Algorithm,通过权重的差异性得到差异化的\(g_t(x)\),这种算法我们称之为Adaptive Boosting,通常简称为AdaBoost。

Diversity by Re-weighting

下图是一个引入权重的例子:

在右图中,描述了一次Bootstrap在\(\widetilde{D}_t\)上随机选取的数据点,可以发现\((x_1, y_1)\)被选取了两次。

在左图中,数据集\(D\)上每一组\((x_n ,y_n)\)的权重\(u_n\)为该次Bootstrap该数据被选中的次数,然后通过最小化\(E_{in}\),得到\(g(x)\)。

最小化带权重的\(E^{u}_{in}\)的一般形式如下:

接下来,我们将介绍如何通过Re-weighting(重置权重)来得到差异化的\(g(x)\):

从上图可以看出,对于相同的数据集\(D\),我们如果想要得到不同的\(g_t(x)\),那我们需要使每次用于训练\(g(x)\)的权重\(u^{(t)}_n\)不同,或者说非常不同。

那么如何使得\(u^{(t)}_n\)非常不同呢?

比较直观的做法是,让\(g_t(x)\)在使用\(u^{(t+1)}_n\)进行Blending后得到的\(G(x)\)在\(D\)上表现非常差,甚至正确率只有50%,如同抛硬币:

假设数据集\(D\)上共有7337个数据,使用\(u^{(t)}_n\)的\(G(x)\)的正确分类了6211个数据,错误分类了1126个数据,则使用\(u^{(t)}_n\)的正确率为\(\frac{6211}{7337}\),为了使得\(u^{(t+1)}_n\)的正确率为\(\frac{1126}{7337}\),需要使\(u^{(t)}_n\)乘以\(\frac{6211}{1126}\)。

有了Re-weighted的思想,我们将在下节介绍AdaBoost算法。

Adaptive Boosting Algorithm

我们先定义错误率\(\epsilon_t\)如下:

在定义缩放因子如下:

其中,\(\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\)在定义域\([0, 1]\)上单调递减,在\(\epsilon_t = 0\)的极限为\(∞\),在\(\epsilon_t = \frac{1}{2}\)时值为\(\frac{1}{2}\),在\(\epsilon_t = 1\)时值为\(0\),从\(u^t_n\)更新到\(u^{t+1}_n\),只需要乘以或者除以放缩因子即可。

完整的AdaBoost算法如下:

首先初始化\(u^{(1)} = [\frac{1}{N}, \frac{1}{N}, ···, \frac{1}{N}]\),然后重复\(T\)次下述操作:

  • 从数据集\(D\)中以\(u^{(t)}\)权重训练出\(g_t\)
  • 更新权重\(u^{(t)}\)到\(u^{(t+1)}\),具体根据需要乘以或者除以放缩因子。
  • 计算\(\alpha_t\)

最终得到\(G(x) = sign(\sum^{T}_{t=1} \alpha_tg_t(x))\)

下图是AdaBoost的理论保证:

即只要\(\epsilon_t < frac{1}{2}\),\(E_{in}(G)\)经过T轮迭代后会足够小,而且\(d_{vc}\)增长较慢

Adaptive Boosting in Action

在实际问题中,我们通常会使用一个比较弱的Learning Algorithm,较为常用的是Decision Stump(决策桩):

Decision Stump在二维数据集上是一条有向线段,下图是一个AdaBoost算法在经过\(t = 100\)次循环后在二维数据集上的表现:

以上是对Adaptive Boosting在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Decision Tree。