Created by potrace 1.13, written by Peter Selinger 2001-2015

集成学习

集成学习

集成学习是使用多个个体学习器,同时对数据进行学习,学习器可以是同一种类型的,也可以是不同种类型的.

image

集成学习好比一个团队,每个学习器是团队里的一员,最终结果为团队成员商议的结果,即少数服从多数.在下图(a)中，每个分类器都只有66.6%的精度,但集成学习却达到了100%; 在图(b)中,三个分类器没有差别，集成之后性能没有提高;在图(c)中，每个分类器的精度都只有33.3% ，集成学习的结果变得更糟.

image

这个简单的例子显示出:要获得好的集成，个体学习器应好而不同,即个体学习器要有一定的"准确性",并且要有"多样性".集成学习研究的核心就是如何让这些个体学习器"好而不同".

image

Boosting 和 Bagging

目前集成学习方法可大致分为两大类,一类个体学习器之间存在强依赖关系,即后一个个体学习器取决于前一个个体学习器,所以个体学习器必须串行化生成.另一类是个体学习器之间不存在依赖关系,可并行化生成.前者的代表是Boosting,后者的代表是Bagging.

Boosting核心思路是先生成一个个体学习器,评估这个个体学习器对哪些样本做了正确的预测,对哪些样本做了错误的预测.接下来提升错误预测样本的权重,生成下一个个体学习器的时候让权重大的样本起更大的作用.这样的话对于每个样本总有多数的个体学习器可以对其正确预测.这里按照损失函数的不同，将其细分为若干类算法，下表给出了4种不同损失函数对应的Boosting方法：

算法 损失函数(Loss) 导数(Derivative) 目标函数 f^∗
L2Boosting \frac{1}{2} (y^{(i)} - f(x^{(i)}))^2 y^{(i)} - f(x^{(i)}) E[y \vert x^{(i)}]
Gradient Boosting \vert y^{(i)} - f(x^{(i)}) \vert sign(y^{(i)} - f(x^{(i)}) median(y \vert x^{(i)})
AdaBoost \exp(- \tilde {y^{(i)}} f(x^{(i)})) - \tilde {y^{(i)}} exp(-\tilde {y^{(i)}} f(x^{(i)})) \frac{1}{2} \log \frac{\pi_i}{1 - \pi_i}
LogitBoost \log (1+e^{- \tilde{y^{(i)}} f_i}) y^{(i)} - \pi_i \frac{1}{2} \log \frac{\pi_i}{1 - \pi_i}

Bagging核心思路是从样本集中随机放回取样,每次取m个样本,取T次,这样就得到T个不同的样本集,使用这些不同的样本集训练个体学习器可以使个体学习器有明显差异.

image

AdaBoosting

AdaBoosting是Boosting的著名算法,通过调整样本权重达到调整每个个体学习器样本分布的目的.下面让我们来推导AdaBoosting算法的实现.

加法模型

我们可以把集成学习理解为个体学习器按照权重相加的线型模型:

f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)

其中， b(x;\gamma_m) 为基函数， \gamma_m 为基函数的参数， \beta_m 为基函数的系数（权重）。

在给定训练数据及损失函数的条件下，学习加法模型成为经验风险极小化（即损失函数极小化）问题：

min_{\beta_m,\gamma_m}\sum_{i=1}^{N}L(y_i,\sum_{m=1}^{M}\beta_m b(x_i;\gamma_m))

即同时考虑N个样本在整个线性模型组中的损失函数的极小值，通常这是一个十分复杂的优化问题（求极值问题），想要一步到位求出最优解特别困难。

前向分步算法（forward stagewise algorithm）求解这一优化问题的思想是：因为学习的是加法模型（线性模型），如果能够从前向后，每一步只学习一个基函数 b(x;\gamma_m) 及其系数 \beta_m ，逐步逼近优化目标函数式.那么就可以极大简化优化的复杂度。具体地，每步优化如下损失函数：

min_{\beta_m,\gamma_m}\sum_{i=1}^{N}L(y_i,\beta_m b(x_i;\gamma_m))

每次只要考虑一个基函数及其系数即可。因为每一步只学习一个 \gamma_m 和 \beta_m ,所以第m次学习可以把m次之前的参数当成常数,即:

f_m(x) = f_{m-1} +a_mG_m(x)

前向分步算法 与Adaboost

加法模型等价于AdaBoost的最终分类器

f(x)=\sum_{m=1}^{M}\alpha_{m}G_{m}(x)

f_{m}(x)=f_{m-1}(x)+\alpha _{m}G_{m}(x)

由基本分类器 G_{m}(x) 及其系数 \alpha _{m} 组成， m=1,2,...,M 。

二分类问题可以使用0/1损失函数.假设 y \in \{-1,1\} ,当 y = f(x) ,损失函数为0,当 y \not= f(x) ,损失函数为1.

L(y,f(x))=\begin{cases}0 \qquad if \;\; yf(x)\geq0 \newline 1 \qquad if \;\; yf(x) < 0\end{cases}

但是0/1损失函数不连续、非凸，优化困难，因而我们使用指数损失函数代替:

L(y,f(x))=exp(-yf(x))

当分类错误的时候指数函数比较大,当分类正确的时候指数函数比较小,所以最小化指数损失函数也可以让错误分类最小化.

对于整个数据集 T 来说,目标是优化 \alpha_{m} 和 G_{m} 使损失最小，即：

(\alpha _{m},G_{m}(x))=arg~\underset{\alpha,G}{min}\sum_{i=1}^{N}exp[-y_{i}(f_{m-1}(x_{i})+\alpha G(x_{i}))]

可以表示成：

(\alpha _{m},G_{m}(x))=arg~\underset{\alpha,G}{min}\sum_{i=1}^{N}\overline{w}_{mi}exp[-y_{i}\alpha G(x_{i})]

其中， \overline{w}_{mi}=exp[-y_{i}f_{m-1}(x_{i})] ，为每个样本损失函数的权重,也就是样本的权重 .这里可以这样理解,上一次学习被错误分类的样本损失函数大,正确分类的样本损失函数小,相当于本次学习给上次被错误分类的样本更大的权重,给上次正确分类的样本更小的权重.

把损失函数进行一下变形：

\begin{equation} \begin{split} &\sum_{i=1}^{N}\overline{w}_{mi}exp[-y_{i}\alpha G(x_{i})] \\ &=\sum_{i=1}^{N}\overline{w}_{mi}e^{-\alpha}I\{y_{i}=G(x_{i})\}+\sum_{i=1}^{N}\overline{w}_{mi}e^{\alpha}I\{y_{i}\neq G(x_{i})\} \\ &=e^{-\alpha}\sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}=G(x_{i})\}+e^{\alpha}\sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}\neq G(x_{i})\}+e^{-\alpha}\sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}\neq G(x_{i})\}-e^{-\alpha}\sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}\neq G(x_{i})\}\\ &=e^{-\alpha}\sum_{i=1}^{N}\overline{w}_{mi}+(e^{\alpha}-e^{-\alpha})\sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}\neq G(x_{i})\} \end{split} \end{equation}

令 c = \sum_{i=1}^{N}\overline{w}_{mi},d = \sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}\neq G(x_{i})\} ,对上式中的 \alpha 求导并令其导数为0,可得:

de^{a-1} = (c-d)e^{-a-1}

等式两边取自然对数:

\alpha =\dfrac{1}{2}\log\frac{c -d}{d}=\dfrac{1}{2}\log\frac{1-e_{m}}{e_{m}}

其中 e_{m} 为分类错误率：

e_{m}=\frac {\sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}\neq G(x_{i})\}}{\sum_{i=1}^{N}\overline{w}_{mi}}=\sum_{i=1}^{N}w_{mi}I\{y_{i}\neq G(x_{i})\}

至此,我们已经推导出了Adaboost的参数 \alpha

再看一下每一轮的权值更新，对：

f_{m}(x)=f_{m-1}(x)+\alpha_{m}G_{m}(x)

两边乘 -y 再取对数:

exp[-yf_{m}(x)]=exp[-yf_{m-1}(x)]exp[-y\alpha_{m}G_{x}]

由 \overline{w}_{m}=exp[-yf_{m-1}(x)] ，可得：

\overline{w}_{m+1}=\overline{w}_{m}exp[-y\alpha_{m}G_{x}]

为了使权值之和为1,我们还会进行规范化:

\overline{w}_{m+1}=\frac{\overline{w}_{m}}{Z_m}exp[-y\alpha_{m}G_{x}]

Adaboost的流程

下面我们再来总结一下Adaboost训练时的流程:
首先,初始化训练数据的权值分布 w .
然后,对M个分类器,每个分类器的训练步骤如下:

  1. 计算误差

e_{m} = \sum_{i=1}^{N}\overline{w}_{mi}I\{y_{i}\neq G(x_{i})\}

  1. 计算 \alpha

\alpha_m =\dfrac{1}{2}\log\frac{1-e_{m}}{e_{m}}

  1. 根据当前分类器对样本的分类情况,更新权值参数

w_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_m y_i G_m(x_i)),\ i = 1,2,\cdots,N

最后将这M个分类器组合起来:

f(x)=\sum_{m=1}^{M}\alpha_m G_m(x)

随机森林

随机森林(Random Forest)是Bagging的一个扩展变体.随机森林在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择.具体来说，传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性;而在随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分. 这里的参数k控制了随机性的引入程度;若令k = d,则基决策树的构建与传统决策树相同;若令 k=1 则是随机选择1个属性用于划分,一般情况下，推荐值 k = log_2 d .

随机森林简单、容易实现、计算开销小，令人惊的是，它在很多现实任务中展现出强大的性能，被誉为"代表集成学习技术水平的方法".可以看出，随机森林对 Bagging 只做了小改动, 但是与 Bagging 中基学习器的"多样性"仅通过样本扰动(通过对初始训练集采样)而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升.

组合策略

当个体学习器得出结果后,我们需要综合这些结果得出一个最终的结论.

一般来说,对于回归问题,我们取加权平均值:

H(x) = \sum_{i=1}^T w_i h_i(x)

其中 w_i 是个体学习器 h_i 的权重,通常要求 w_i \leq 0 , \sum_{i=1}^T w_i = 1

对于分类问题,我们采用投票法,即少数服从多数:

H(x) = c_{arg \; max\sum_{i=1}^T w_i h_i(x)}

其中 w_i 是个体学习器 h_i 的权重,通常要求 w_i \leq 0 , \sum_{i=1}^T w_i = 1

参考:
李航<统计学习方法>
周志华<机器学习>

posted @ 2018-09-20 16:19:09
评论加载中...
发表评论