C08. 集成学习

8.1 个体与集成

集成学习 ( Ensemble Learning ) 通过构建并且结合多个学习器来完成学习任务，也被称为多分类器系统 ( Multi-Classifiter System ) 、基于委员会的学习 ( Committee-Based Learning ) 等等。

集成学习的一般结构：先产生一组「个体学习器」 ( Individual Learner ) ，再用某种策略将它们结合起来。

• 同质集成：所有的个体学习器都是同种类型的，统称这些个体学习器为「基学习器」，因此学习算法称为「基学习算法」
• 异质集成：个体学习器可以存在不同的类型，不再有基学习算法，也称这些个体学习器为「组件学习器」

集成学习通过将多个学习器进行结合，常可获得比单一学习器更好的泛化性能，对「弱学习器」更加明显，因此集成学习的许多理论研究都是针对弱学习器进行 的，而基学习器也被称为弱学习器。

集成学习的质量依赖于个体学习器要「好而不同」

• 个体学习器需要一定的「准确性」，即学习器的效果不能太差
• 个体学习器需要一定的「多样性」，即学习器间具有差异
• 集成学习研究的核心：产生并且结合「好而不同」的个体学习器的算法

假设基分类器的错误率朴素独立，则集成的错误率将随着集成的数目呈指数级下降，并且最终趋向于零

常用的集成学习方法

• Boosting：个体学习器之间存在强依赖关系，必须串行生成的序列化方法
  • AdaBoost
  • GBDT
• Bagging：个体学习器之间不存在强依赖关系，可以并行生成
  • Random Forest

8.2 Boosting

Boosting 算法的工作机制

• 从初始训练集训练出一个基学习器
• 根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在以后的训练中受到更多关注
• 基于调整后的样本分布来训练下一个基学习器
• 重复进行，直到基学习器的数目达到预先设定的值 $T$
• 对这 $T$ 个基学习器进行加权结合

基于「加性模型」的 AdaBoost 算法

• 基学习器的线性组合：$H ( \text{x} ) =\sum_{t=1}^T \alpha_t h_t ( \text{x} )$
• 最小化的指数损失函数：$l_{\exp} ( H|D ) =\mathbb{E}_{\text{x}\sim\mathcal{D}}[\exp{-f ( \text{x} ) H ( \text{x} ) }]$
• 求导损失函数：$\frac{\partial l_{\exp} ( H|D )}{\partial H ( \text{x} )}=-\exp{-H ( \text{x} ) } P ( f ( \text{x} ) =1|\text{x} ) +\exp{H ( \text{x} ) }P ( f ( \text{x} ) =-1|\text{x} )$
• 极值：$H(\text{x})=\frac12\ln\frac{P(f ( \text{x})=1|\text{x})}{P( f ( \text{x})=-1|\text{x})}$

$$
\begin{aligned}
\text{sign}(H ( \text{x}))
&=\text{sign}(\frac12\ln\frac{P(f ( \text{x})=1|\text{x})}{P( f ( \text{x})=-1|\text{x})})\
&=\begin{cases}
1,&P( f ( \text{x})=1|\text{x})>P( f ( \text{x})=-1|\text{x})\
-1,&P( f ( \text{x})=1|\text{x})<P( f ( \text{x})=-1|\text{x})
\end{cases}\
&= \arg\max_{y\in{-1,1}} P( f ( \text{x})=y|\text{x})
\end{aligned}
$$