Ch08

ZhuYuanxiang 2020-10-12 18:15:39
Categories： Tags：

C08. 提升方法 ( 集成学习 )

提升方法 ( Boosting ) 是一种统计学习方法，也是一种提升模型学习能力和泛化能力的方法，还是一种组合学习 ( 集成学习 ) 的方法，是统计学习中最有效的方法之一。

学习提纲

8.1 AdaBoost 算法 ( 提升方法 )

8.1.1 提升方法的基本思路

为什么要将各种学习方法组合起来？

注 1：概率近似正确 ( Probably Approximately Correct, PAC ) 学习[^周志华，2018] Ch 12

如何将各种学习方法组合起来？

8.1.2 AdaBoost 算法

前提条件

训练过程

注 1: AdaBoost 算法流程的理解推荐[^Bishop,2016] Sec 14.3

8.1.3 AdaBoost 的例子

注：通过这个例子，可以具体了解算法的计算过程

8.2 AdaBoost 算法的训练误差分析

AdaBoost 算法的最终分类器的训练误差界为
$$
\frac1N\sum_{i=1}^N I ( G ( \text{x}i ) \neq y_i ) \leq \frac1N\sum{i}\exp{-y_i f ( \text{x}i ) }=\prod{m} Z_m
$$

二分类问题 AdaBoost 算法的训练误差界为
$$
\begin{aligned}
\prod_{m=1}^M Z_m
&=\prod_{m=1}^M {2\sqrt{e_m ( 1-e_m )}}\
&=\prod_{m=1}^M \sqrt{1-4\gamma_m^2}\
&\leq\exp{-2\sum_{m=1}^M \gamma_m^2}\
&\gamma_m=\frac12-e_m
\end{aligned}
$$

推论 8.1：如果存在 $\gamma>0$，并且 $\forall m,\gamma_m\geq\gamma$，则：$\frac1N\sum_{i=1}^N I ( G ( \text{x}_i ) \neq y_i ) \leq\exp{-2M\gamma^2}$

8.3 AdaBoost 算法的解释

8.3.1 前向分步算法

加法模型：$f ( \text{x} ) =\sum_{m=1}^M \beta_m b ( \text{x};\gamma_m )$

在给定训练数据及损失函数 $L ( y,f ( \text{x} )$ 的条件下，学习加法模型 $f ( \text{x} )$ 成为经验风险极小化，即损失函数极小化问题
$$
\min_{\beta_m,\gamma_m}\sum_{i = 1}^N L ( y_i,\sum_{m=1}^M \beta_m b ( \text{x};\gamma_m )) \tag{8.14}
$$

基于前向分步算法优化这个损失函数：因为学习的是加法模型，因此从前向后每一步学习一个基函数及其系数，就可以逐步逼近优化目标 ( Eq 8.14 ) ，并且避免了一次优化所有参数带来的高复杂度，即简化为每步优化如下的损失函数
$$
\min_{\beta,\gamma}\sum_{i = 1}^N L ( y_i,\beta b ( \text{x}_i;\gamma ))
$$

前向分步算法

8.3.2 前向分步算法与 AdaBoost 的关系

( 由前向分步算法可以推导出 AdaBoost 算法 )

AdaBoost 算法是前向分步算法的特例

8.4 提升树

( 提升树是以分类树或者回归树为基本分类器的提升方法，是统计学习中性能最好的方法之一 )

8.4.1 提升树模型

8.4.2 提升树算法

8.4.3 梯度提升算法 ( GBDT )

本章概要

学习总结

Ch09
Ch07