基本概念
- 基学习器 同质/异质 准确性/多样性 弱学习器
- 集成学习器
- 结合策略
- 集成分类器错误率随个体分类器数目的增大指数下降
$$ \mathbb{P} (H(x) \neq f(x))
= \sum_{k=0}^{\lfloor T/2 \rfloor} \binom{T}{k}(1-\varepsilon)^k\varepsilon^{T-k}
\leq exp\left(-\frac{1}{2}T(1-2\varepsilon)^2\right) $$
结合策略
优点
- 处理同等性能假设
- 避免陷入局部最小点
- 拓展假设空间
方法
平均法
- 数值型输出
- 简单平均法
- 加权平均法
投票法
- 分类任务 – 基学习器的输出是类标记或类概率
- 绝对多数投票法 – 优点：提供了拒绝决策机制
- 相对多数投票法
- 加权投票法
学习法 （Stacking）
- 利用初级学习算法和初始数据集生成初级学习器
- 利用初级学习器生成新数据集
- 利用次级学习算法和新数据集生成结合策略
- 为防止过拟合，通常可用k折交叉验证，用初级学习器未使用的数据集生成次级学习算法的数据集
基学习器多样性
误差-分歧分解
$$ E = \bar{E} - \bar{A} $$
- 个体学习器分歧 $$ A(h_i\,|\,x) = (h_i(x)-H(x))^2 $$
- 个体学习器误差 $$ E(h_i\,|\,x) = (h_i(x)-f(x))^2 $$
- 集成泛化误差 $$ E = \int E(H\,|\,x)p(x) $$
- 集成加权分歧 $$ \bar{A} = \sum_{i=1}^{T} w_i \int A(h_i\,|\,x)p(x) \;dx $$
- 集成加权误差 $$ \bar{E} = \sum_{i=1}^{T} w_i \int E(h_i\,|\,x)p(x) \;dx $$
多样性度量
- 考虑基学习器的两两相似/不相似性
- 预测结果列联表
| $h_i=+1$ | $h_i=-1$ | |
|---|---|---|
| $h_j=+1$ | a | b |
| $h_j=-1$ | c | d |
- 不合度量 $$\frac{b+c}{a+b+c+d}$$
- 相关系数 $$\frac{ad-bc}{\sqrt{(a+b)(a+c)(b+d)(c+d)}}$$
- Q-统计量 $$\frac{ad-bc}{ad+bc}$$
- $\kappa$-统计量, $p_1,p_2$ 分别为两个分类器一致和偶然一致的概率 $$\frac{p_1-p_2}{1-p_2}$$
- 成对形多样性度量：$\kappa$-误差图（准确性、多样性分布图）
多样性增强
- 数据样本扰动 – 对不稳定学习器效果（决策树、神经网络）明显
- 输入属性扰动 – 随机子空间算法
- 输出表示扰动
- 算法参数扰动 – 神经网络层数、LASSO惩罚因子、决策树属性89003714选择机制
Boosting
- 关注降低偏差
算法机制
- 根据初始训练集训练一个基学习器
- 根据基学习器对数据样本分布进行调整（使得先前基学习器做错的样本受到更多的关注）
- 根据调整的样本训练一个新的基学习器
- 重新调整样本数据分布并生成新的基学习器，直至达到事先指定的基学习器数目
- 将所有基学习器加权结合
AdaBoost
算法机制
基学习器更新：
$$ h_t = \mathfrak{L}(\mathcal{D},\mathcal{D_t}) $$分类误差更新：
$$ \varepsilon_t = \mathbb{P}_{x\sim\mathcal{D}_t}(h_t(x) \neq f(x)) $$分类器权重更新公式:
$$ \alpha_t =
\frac{1}{2}\ln \left( \frac{1-\varepsilon_t}{\varepsilon_t} \right) $$样本数据分布更新公式：
$$ \mathcal{D}_{t+1}(x)
\propto
\mathcal{D}_t(x) e^{-f(x)\alpha_t h_t(x)} $$
算法原理
指数损失函数是分类任务0/1损失函数的一致替代函数
$$ loss_{exp}(H\,|\,\mathcal{D}) =
\mathbb{E}_{x\sim\mathcal{D}}[e^{-f(x)H(x)}] $$$h_t(x), \alpha_t$ 最小化 $\mathbb{E}_{x\sim\mathcal{D}_t}[e^{-f(x)\alpha_t h_t(x)}]$
加法模型
前向分步算法
Bagging
- 关注降低方差
算法原理
- 相互有交叠的采样子集
- 自主采样法（Bootstrap sampling）
- 简单投票法、简单平均法
算法优势
- 高效集成学习算法
- 适用于二分类、多分类、回归等任务（标准AdaBoost仅适用于二分类）
- 利用包外样本做泛化误差分析、防止过拟合等
$$ H^{oob}(x) = \sum_{t=1}^{T} \mathbb{I}(h_t(x)=y)\cdot\mathbb{I}(x\notin D_t) $$
$$ \varepsilon^{oob} = \frac{1}{|D|} \sum_{(x,y)\in D}\mathbb{I}(H^{oob}(x)\neq y) $$
Random Forest
算法原理
- Bagging + 决策树 + 随机属性选择
- 样本扰动 + 自属性扰动
算法优势
- 简单、易实现、计算开销小、功能强大
- 跟Bagging比较，往往具有类似的收敛性、更小的泛化误差、更高的训练效率