集成学习 task6

Boosting方法

Boosting方法是一种很强大的方法,它将多个“基”分类器进行组合,产生一种形式的委员会,委员会的表现会比任何一个基分类器的表现好得多。

这里所用的基分类器可以是表现仅仅比随机猜测的表现稍好的弱学习器。Boosting方法最初被用来解决分类问题,但是也可以推广到回归问题。

Boosting方法和委员会方法(例如上面讨论的打包方法)的主要不同在于,基分类器是顺序训练的,每个基分类器使用数据集的一个加权形式进行训练,其中与每个数据点相关联的权系数依赖于前一个分类器的表现。特别地,被一个基分类器误分类的点在训练序列中的下一个分类器时会被赋予更高的权重。一旦所有的分类器都训练完毕,那么它们的预测就会通过加权投票的方法进行组合,如图所示:

考虑一个二分类问题,其中训练数据由输入向量 x_1,...,x_N 以及对应的二值目标变量 t_1,...,t_N 组成,其中 t_n \in \{−1,1\} 。每个数据点被赋予了一个关联的权值参数 w_n ,AdaBoost算法的精确形式叙述如下。

  1. 初始化数据加权系数 ${w_n} $,方法是对 n = 1,...,N ,令 w_n^{(1)} = 1 / N
  2. 对于 m = 1,...,M
  3. 使用训练数据调节一个分类器 y_m(x) ,调节的目标是最小化加权的误差函数:
J_m = \sum\limits_{n=1}^Nw_n^{(m)}I(y_m(x_n) \neq t_n)

其中 I(y_m(x_n) \neq t_n) 是一个示性函数,当 y_m(x_n) \neq t_n 时,值为1,其他情况下值为0。

  1. 计算:

    \epsilon_m = \frac{\sum\limits_{n=1}^N w_n^{(m)}I(y_m(x_n) \neq t_n)}{\sum\limits_{n=1}^N w_n^{(m)}}

    然后计算:

    \alpha_m = \ln\left\{\frac{1-\epsilon_m}{\epsilon_m}\right\}
  2. 更新数据权系数:

    w_n^{(m+1)} = w_n^{(m)}exp\{\alpha_mI(y_m(x_n) \neq t_n)\}
  3. 使用最终的模型进行预测,形式为:

    Y_M(x) = \text{sign}\left(\sum\limits_{m=1}^M\alpha_my_m(x)\right)

迭代过程中,权系数 w_n^{(m)} 对于误分类的数据点会增大,对于正确分类的数据点不改变。因此后续的分类器就会更关注那些被前一个分类器错误分类的数据点。$\epsilon_m$ 表示每个基分类器在数据集上的错误率的加权度量,于是权系数 \alpha_m 会在计算整体输出时,为更准确的分类器赋予更高的权值。

考虑下面定义的指数误差函数

E = \sum\limits_{n=1}^Nexp\{-t_nf_m(x_n)\}

其中 f_m(x) 是一个根据基分类器 y_l(x) 的线性组合定义的分类器,形式为

f_m(x) = \frac{1}{2}\sum\limits_{l=1}^m\alpha_ly_l(x)

t_n \in \{−1, 1\} 是训练集目标值。我们的目标是关于权系数 \alpha_l 和基分类器 y_l(x) 最小化 E

然而,我们不进行误差函数的全局最小化,而是假设基分类器 y_1(x),...,y_{m−1}(x) 以及它们的系数 \alpha_1,...,\alpha_{m−1} 固定,因此我们只关于 \alpha_my_m(x) 进行最小化。分离出基分类器 y_m(x) 的贡献,我们可以将误差函数写成

\begin{array}{} E &=& \sum\limits_{n=1}^N exp\left\{-t_nf_{m-1}(x_n) - \frac{1}{2}t_n\alpha_my_m(x_n)\right\} \\ &=& \sum\limits_{n=1}^N{w_n^{(m)}}exp\left\{-\frac{1}{2}t_n\alpha_my_m(x_n)\right\}\end{array}

其中,系数 w_n^{(m)} = exp\{−t_nf_{m-1}(x_n)\} 可以被看做常数,因为我们只针对 \alpha_my_m(x) 进行最如果我们将被 y_m(x) 正确分类的数据点的集合记作 T_m ,并且将剩余的误分类的点记作 M_m ,那么我们可以将误差函数写成下面的形式:

\begin{array}{} E &=& e^{-\alpha_m / 2}\sum\limits_{n \in T_m}w_n^{(m)}e^{\alpha_m / 2}\sum\limits_{n \in M_m}w_n^{(m)} \\ &=& (e^{\alpha_m / 2} - e^{-\alpha_m / 2})\sum\limits_{n=1}^Nw_n^{(m)}I(y_m(x_n) \neq t_n) + e^{-\alpha_m / 2}\sum\limits_{n=1}^Nw_n^{(m)} \end{array}

当我们关于 y_m(x) 进行最小化时,第二项是常数,因此这等价于对 \sum\limits_{n=1}^Nw_n^{(m)}I(y_m(x_n) \neq t_n) 最小化。

类似地,关于 \alpha_m 最小化,我们得到:

(e^{\alpha_m} + 1)\sum\limits_{n=1}^Nw_n^{(m)}I(y_m(x_n) \neq t_n)=\sum\limits_{n=1}^Nw_n^{(m)}

可以解得:

\alpha_m = \ln\left\{\frac{1-\epsilon_m}{\epsilon_m}\right\}

找到 \alpha_my_m(x) 之后,数据点的权值使用下面的公式进行更新

w_n^{(m+1)} = w_n^{(m)} exp\left\{-\frac{1}{2}t_n\alpha_my_m(x_n)\right\}

使用下面的事实

t_ny_m(x_n) = 1 - 2I(y_m(x_n) \neq t_n)

我们看到在下一次迭代中,权值 w_n^{(m)} 的更新为

w_n^{(m+1)} = w_n^{(m)} exp\left(-\frac{\alpha_m}{2}\right)exp\{\alpha_mI(y_m(x_n) \neq t_n)\}

由于 exp(− \alpha_m / 2)n 无关,因此我们看到它对于所有数据点的权值都贡献一个相同的因子,从而可以丢弃。

AdaBoost算法最小化的指数误差函数与之前章节讨论的误差函数不同。为了更深刻地理解指数误差函数的本质,我们首先考虑 x,t 联合分布下的期望误差,形式为

\mathbb{E}_{x,t}[exp\{-ty(x)\}] = \sum\limits_t\int exp\{-ty(x)\}p(t|x)p(x)dx

如果我们关于所有可能的函数 y(x) 进行变分最小化,那么我们有

y(x) = \frac{1}{2}\ln\left\{\frac{p(t=1|x)}{p(t=-1|x)}\right\}

因此AdaBoost算法是在由基分类器的线性组合表示的函数空间中,寻找对log odds的最好的近似,也使用符号函数得到最终的分类决策的原因。

二分类问题的交叉熵误差函数的最小函数 y(x) 由后验类概率密度给出。在目标变量 t \in \{−1, 1\} 的情形下,我们已经看到误差函数为 \ln(1 + exp(−yt))

指数误差的一个优点是它的顺序最小化会得到简单的AdaBoost方法。然而,一个缺点是,与交叉熵误差函数相比,它对负的 ty(x) 的惩罚较大。交叉熵随着 \vert ty\vert 线性增长,而指数误差随着 \vert ty \vert 指数增长。因此指数误差函数对于异常点和误分类的数据点并不鲁棒。

Gradient Boosting

在AdaBoost中每一轮基学习器训练过后都会更新样本权重,再训练下一个学习器,最后将所有的基学习器加权组合。AdaBoost使用的是指数损失,这个损失函数的缺点是对于异常点非常敏感,因而通常在噪音比较多的数据集上表现不佳。Gradient Boosting是推广的Boosting方法,可以使用任何损失函数 (只要损失函数是连续可导的),这样只要应用更鲁棒的损失函数,就能使模型抗噪音能力更强。

算法流程

给定训练集 $${ (x_1,y_1), \dots, (x_N,y_N) } $$ ,Gradient Boosting的目的是在所有具有给定形式的函数 $$F(x)$$ 中找到一个 $$\hat{F}(x)$$ 使某些指定损失函数 $$L(y, F(x))$$ 的期望值达到最小 :

\hat{F} = \underset{F}{\arg\min} \, \mathbb{E}_{x,y}[L(y, F(x))]

梯度提升方法通过某一类 $$\mathcal{H}$$ 中弱学习器,或称基学习器 $$h_i (x)$$ 带权重和的形式来表示对实值变量 y 做出估计的 $$\hat{F}(x)$$ :

\hat{F}(x) = \sum_{m=1}^M \gamma_m h_m(x)

根据经验风险最小化原理,该方法试图找到一个近似 $$\hat{F}(x)$$ 可以最大程度地减少训练集上损失函数的平均值,即,最小化经验风险。它是从一个由常数函数组成的模型 $$F_0(x)$$ 开始 ,并以贪心算法方式逐步扩展:

F_0(x) = \underset{\gamma}{\arg\min} {\sum_{n=1}^N {L(y_n, \gamma)}}
F_m(x) = F_{m-1}(x) + \underset{h_m \in \mathcal{H}}{\operatorname{arg\,min}} \left[{\sum_{i=n}^N {L(y_n, F_{m-1}(x_n) + h_m(x_n))}}\right]

然而在每个步骤中选择最佳函数通常是不可行的。 因此,考虑对这个最小化问题应用梯度下降步骤。如果我们考虑连续情况,根据以下方程式更新模型

F_m(x) = F_{m-1}(x) - \gamma_m \frac{\partial\sum_{n=1}^N L(y_n, F_{m-1}(x_n))}{\partial F_{m-1}(x)}
\gamma_m = \underset{\gamma}{\arg\min} {\sum_{n=1}^N {L\left(y_i, F_{m-1}(x_n) - \gamma \frac{\partial\sum_{n=1}^N L(y_n, F_{m-1}(x_n))}{\partial F_{m-1}(x)} \right)}}

式子中,偏导数是关于函数 $$ F_{m-1} $$ 求导,注意到 F(x_1), F(x_2), ..., F(x_n) 都是实值,可以像对正常的向量一样求导, $$\gamma_m$$ 是步长。我们选择最接近负梯度的候选函数 h_m(x) ,然后可以根据上述等式通过线搜索来计算系数 $$\gamma_m$$ 。

这种方法是一种启发式方法,因此不能给出给定问题的精确解决方案,而是一种近似方法。

  1. 初始化:$F_0(x) = \underset{\gamma}{\arg\min} {\sum_{n=1}^N {L(y_n, \gamma)}}$

  2. 对于 m = 1,...,M

  3. 计算负梯度:

    \tilde{y}_n=\frac{\partial L(y_n, F_{m-1}(x_n))}{\partial F_{m-1}(x_n)},\quad n=1,...,n
  4. 通过最小化平方误差,用基学习器 h_m(x_n) 拟合 \tilde{y}_n

    w_m=\underset{w}{\arg\min}\sum_{n=1}^N[\tilde{y}_n-h_m(x_n,w)]^2
  5. 通过线搜索来计算系数 $$\gamma_m$$

  6. F_m(x)=F_{m-1}(x)+\gamma_mh_m(x)

  7. 输出 F_M(x)

损失函数

对于分类问题,常用的损失函数包括平方损失、绝对值损失、Huber损失:

损失函数 负梯度
\frac12[y_i-F(x_i)]^2 y_i-F(x_i)
$ y_i-F(x_i)
$\begin{cases}\frac12[y_i-F(x_i)]^2&y_i-F(x_i)\le\delta\\delta( y_i-F(x_i)

GBDT

在Gradient Boosting框架中,最常用的基学习器是决策树 (一般是CART),二者结合就成了著名的梯度提升树 (GBDT)算法。

h_m(x) = \sum_{j=1}^{J_{m}} b_{jm} I(x\in R_{jm})

因此,在Gradient Boosting框架中应用CART在算法的第4步,用启发式的方法搜索最优的区域划分:

R_j=\underset{R}{\arg\min}\sum_{n=1}^N[\tilde{y}_n-h_m(x_n,R)]^2

通常,选定 R_{jm} 后,$b_{jm}$ 的值为 x\in R_{jm} 对应的 y 的平均值。按正常算法流程的第5步, 求出的 \gamma_m 对于树的任何一个区域都是一样的,一种改进方式是对树的每个区域,选择一个 \gamma_{jm}

F_m(x) = F_{m-1}(x) + \sum_{j=1}^{J_{m}} \gamma_{jm} I(x\in R_{jm}), \quad \gamma_{jm} = \underset{\gamma}{\operatorname{arg\,min}} \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma)