模型思想¹

Boosting思想其实相当的简单，大概就是，对一份数据，建立M个模型（比如分类），一般这种模型比较简单，称为弱分类器(weak learner)。每次分类都将上一次分错的数据权重提高一点再进行分类，越往后执行，训练出的模型就越会在意那些容易分错（权重高）的点。这样最终得到的分类器在测试数据与训练数据上都可以得到比较好的成绩。

Boosting可以用下面的公式来表示：

训练集中一共有$n$个点，我们可以为里面的每一个点赋上一个权重$W_i$，表示这个点的重要程度，通过依次训练模型的过程，我们对点的权重进行修正，如果分类正确了，权重降低，如果分类错了，则权重提高，初始的时候，权重都是一样的。上图中绿色的线就是表示依次训练模型，可以想象得到，程序越往后执行，训练出的模型就越会在意那些容易分错（权重高）的点。当全部的程序执行完后，会得到M个模型，分别对应上图的$y_1(x)…y_M(x)$，通过加权或投票的方式组合成一个最终的模型$Y_M(x)$。

Boosting更像是一个人学习的过程，开始学一样东西的时候，会去做一些习题，但是常常连一些简单的题目都会弄错，但是越到后面，简单的题目已经难不倒他了，就会去做更复杂的题目，等到他做了很多的题目后，不管是难题还是简单的题都可以解决掉了。

---

算法流程

具体说来，整个AdaBoost 迭代算法就3步：

• 初始化训练数据的权值分布。如果有$N$个样本，则每一个训练样本最开始时都被赋予相同的权值：$\frac{1}{N}$。
• 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
• 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小²。

---

$$\begin{align} &\{ \\ &\quad 输入：训练数据集D=\{(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \cdots, (x^{(M)},y^{(M)})\}，x^{(i)} \in \mathcal{X} \subseteq R^N，\\ &\qquad\qquad y^{(i)} \in \mathcal{Y} = \{-1, +1\}, 弱分类器; \\ &\quad 输出：最终分类器G(x). \\ &\quad 过程：\\ &\qquad (1). 初始化训练数据的权值分布 \\ &\qquad\qquad\qquad D_1=(w_{11}, w_{12}, \cdots, w_{1M}), \quad w_{1i}=\frac{1}{M}, \; i=1,2,\cdots,M \\ &\qquad (2). 训练K个弱分类器 k=1,2,\cdots,K \\ &\qquad\qquad (a). 使用具有权值分布D_k的训练数据集学习，得到基本分类器 \\ &\qquad\qquad\qquad\qquad G_k(x): \mathcal{X} \rightarrow \{-1, +1\} \qquad\qquad(ml.1.6.3)\\ &\qquad\qquad (b). 计算G_k(x)在训练数据集上的分类误差率 \\ &\qquad\qquad\qquad\qquad e_k = P(G_k(x^{(i)}) \not= y^{(i)}) = \sum_{i=1}^{M} w_{ki} I(G_k(x^{(i)}) \not= y^{(i)}) \qquad(ml.1.6.4)\\ &\qquad\qquad (c). 计算G_k(x)的系数 \\ &\qquad\qquad\qquad\qquad \alpha_k = \frac{1}{2} \log \frac{1-e_k}{e_k} \quad(e是自然对数) \qquad(ml.1.6.5)\\ &\qquad\qquad (d). 更新训练数据集的权值分布 \\ &\qquad\qquad\qquad\qquad D_{k+1} = (w_{k+1,1}, w_{k+1,2}, \cdots, w_{k+1,M})\\ &\qquad\qquad\qquad\qquad w_{k+1,i} = \frac{w_{k,i}}{Z_k} \exp(-\alpha_k y^{(i)} G_k(x^{(i)})), \quad i=1,2,\cdots,M \quad(ml.1.6.6)\\ &\qquad\qquad\qquad Z_k是规范化因子 \\ &\qquad\qquad\qquad\qquad Z_k = \sum_{i=1}^{M} w_{k,i} \cdot \exp(-\alpha_k y^{(i)} G_k(x^{(i)})) \qquad(ml.1.6.7)\\ &\qquad\qquad\qquad 使D_{k+1}成为一个概率分布。\\ &\qquad (3). 构建基本分类器的线性组合 \\ &\qquad\qquad\qquad f(x) = \sum_{k=1}^{K} \alpha_k G_k(x) \qquad(ml.1.6.8)\\ &\qquad 得到最终的分类器 \\ &\qquad\qquad G(x) = sign (f(x)) = sign \left(\sum_{k=1}^{K} \alpha_k G_k(x) \right) \qquad(ml.1.6.9)\\ &\} \end{align}$$

---

举个栗子

下面我们举一个简单的例子来看看AdaBoost的实现过程³⁴：

图中，“$+$”和“$-$”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。

---

第一次分类：

第一次分类有3个点划分错误，根据误差表达式：

$$\varepsilon_t = Pr_{i\thicksim D_t}[h_t(x_i)\neq y_i] = \sum_{i=1}^{N}D_t[h_t(x_i)\neq y_i]$$

则：

$$\varepsilon_1 = 0.1+0.1+0.1 = 0.3$$

分类器权重：

$$\alpha_1 = \frac{1}{2} \ln(\frac{1-\varepsilon_1}{\varepsilon_1}) = \frac{1}{2} \ln(\frac{1-0.3}{0.3}) = 0.42$$

然后根据算法把错分点的权值变大。对于正确分类的7个点，权值不变，仍为0.1,对于错分的3个点，权值为：

$$D_1 = D_0(\frac{1-\varepsilon_1}{\varepsilon_1}) = 0.1*(\frac{1-0.3}{0.3}) = 0.2333$$

---

第二次分类：

如图所示，有3个”$-$”分类错误。上轮分类后权值之和为：

$$0.1*7+0.2333*3=1.3990$$

分类误差：

$$\varepsilon_2 = 0.1*3/1.3990 = 0.2144$$

分类器权重：

$$\alpha_2 = \frac{1}{2} \ln(\frac{1-\varepsilon_2}{\varepsilon_2}) = \frac{1}{2} \ln(\frac{1-0.2144}{0.2144}) = 0.6493$$

错分的3个点的权值：

$$D_2 = D_1(\frac{1-\varepsilon_2}{\varepsilon_2}) = 0.2333*(\frac{1-0.2144}{0.2144}) = 0.2333$$

---

第三次分类：

同理可求得：

$$\varepsilon_3=0.1365;\alpha_3=0.9223;D_3=0.6326$$

---

---

整合所有子分类器⁵：

即使是简单的分类器，组合起来也能获得很好的分类效果。

---

前向分步加法模型

下面我们来解释下AdaBoost的算法流程为啥是这样的？

其实AdaBoost算法是前向分步加法算法的特例，我们先来搞清楚前向分步加法算法。

• 加法模型（addtive model）

$$f(x) = \sum_{k=1}^{K} \beta_k \cdot b(x; \gamma_k)$$

其中，$b(x; \gamma_k)$为基函数，$\gamma_k$为基函数的参数，$\beta_k$为基函数的系数。

深入浅出ML之Boosting家族

AdaBoost算法是模型为加法模型、损失函数为指数函数($L(y, f(x)) = \exp [-y f(x)]$)、学习算法为前向分步算法时的学习方法。

---

---

---