集成学习 - 简书

1. 个体与集成

集成学习通过构建并结合多个学习器完成学习任务，常可获得比单一学习器显著优越的泛化性能
1. 集成学习对于弱学习器的集成效果最明显
2. 实践中往往使用较强的学习器以减少学习器的使用数量，或重用关于常见学习器的一些经验

image-20200528115445126.png

同质集成与异质集成
1. 同质集成中的个体学习器称为“基学习器”，相应学习算法称为“基学习算法”
2. 异质集成中的个体学习器称为“组件学习器”
集成学习的结果根据“投票法”产生（少数服从多数）

image-20200528120038731.png

二分类问题 $y \in \{-1,+1\}$ 和真实函数 $f$ ，假定基分类器的错误率为 $\epsilon$ ，对每个基分类器 $h_i$ 有
$P(h_i(x) \not = f(x)) = \epsilon$
假设集成通过简单投票法结合 $T$ （方便起见设为奇数）个基分类器，若有超过半数判为正确则集成分类正确：
$H(x)=sign(\Sigma_{i=1}^Th_i(x))$
各个基分类器 $h_i$ 的分类结果求和之后数字的正、负或0，代表投票法产生的结果，即“少数服从多数”，符号函数，将正数变成1，负数变成-1，0仍然是0，所以 $H_(x)$ 是由投票法产生的分类结果
由 $Hoeffding$ 不等式可知集成错误率为
$\begin{array}{l} P(H(x) \not = f(x)) \\ =\Sigma_{k=0}^{\lfloor T/2 \rfloor}\binom{T}{k}(1-\epsilon)^k\epsilon^{T-k}\\ \leq \exp(-\frac{1}{2}T(1-2\epsilon)^2) \end{array}$
随着个体分类器数目 $T$ 的增大，集成错误率将指数下降趋于零
* 证明
由基分类器相互独立，设 $x_i$ 为每个分类器分类正确的次数，则 $x_i \sim B(1,1-\epsilon)$
假设随机变量 $X$ 为 $T$ 个基分类器分类正确的次数，则 $X \sim B(T,1-\epsilon)$
$\begin{array}{l} P(H(x) \not = f(x))\\ = P(X \leq \lfloor T/2 \rfloor)\\ \leq P(X \leq T/2)\\ =P[X-(1-\epsilon)T \leq \frac{T}{2}-(1-\epsilon)T]\\ =P[X-(1-\epsilon)T \leq - \frac{T}{2}(1-2\epsilon)]\\ =P[\Sigma_{i=1}^Tx_i - \Sigma_{i=1}^T\mathbb E(x_i) \leq - \frac{T}{2}(1-2\epsilon)]\\ =P[\frac{1}{T}\Sigma_{i=1}^Tx_i - \frac{1}{T}\Sigma_{i=1}^T\mathbb E(x_i) \leq - \frac{1}{2}(1-2\epsilon)] \end{array}$
由 $Hoeffding$ 不等式知
$P(\frac{1}{m}\Sigma_{i=1}^mx_i-\frac{1}{m}\Sigma_{i=1}^m \mathbb E(x_i)\geq \epsilon) \leq \exp(-2m\epsilon^2)$
令 $X=-X$ 有
$P(\frac{1}{m}\Sigma_{i=1}^m \mathbb E(x_i) - \frac{1}{m}\Sigma_{i=1}^mx_i\geq \epsilon) \leq \exp(-2m\epsilon^2)$
等价于
$P(\frac{1}{m}\Sigma_{i=1}^mx_i-\frac{1}{m}\Sigma_{i=1}^m \mathbb E(x_i)\leq -\epsilon) \leq \exp(-2m\epsilon^2)$
令 $\epsilon = \frac{1-2\epsilon}{2},m=T$ 得到
$\begin{array}{l} P(H(x) \not = f(x)) \\ =\Sigma_{k=0}^{\lfloor T/2 \rfloor}\binom{T}{k}(1-\epsilon)^k\epsilon^{T-k}\\ \leq \exp(-\frac{1}{2}T(1-2\epsilon)^2) \end{array}$

2.Boosting

工作机制
1. 先从初始训练集训练出一个基学习器，
2. 再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注
3. 基于调整后的样本训练下一个基学习器
4. 如此重复进行直到基学习器数目(训练轮数)达到事先指定的值T，最终将T个基学习器进行加权结合
Adaboost算法

image-20200528125326366.png
- 基于“加性模型”最小化指数损失函数
  - 加性模型（基学习器线性组合）
    $H(x)=\Sigma_{t=1}^T\alpha_th_t(x)\\ \alpha_t=\frac{1}{2}\ln(\frac{1-\epsilon_t}{\epsilon_t})$
    该分类器的权重只与分类器的错误率负相关（错误率越大权重越低）
  - 指数损失函数
    $l_{exp}(H|D)\\ = \mathbb E_{x \sim D}[e^{-f(x)H(x)}]\\ = \Sigma_{x \in D}D(x)e^{-f(x)H(x)}$
    $f(x) \in \{+1,-1\},H(x) \in \mathbb R$
    1. 若预测结果正确，则 $H(x)f(x) > 0$ ， $e^{-f(x)H(x)} = e^{-|H(x)|} < 1$ ,且 $H(x)$ 越大（视为分类器对预测结果的信心），损失函数值越小。 $H(x)$ 接近0，则损失函数值较大
    2. 若预测结果错误，则 $H(x)f(x) < 0$ ， $e^{-f(x)H(x)} = e^{|H(x)|} > 1$ ,且 $H(x)$ 越大（视为分类器对预测结果的信心），损失函数值越大。 $H(x)$ 接近0，则损失函数值较小
  - 寻找这样的 $H(x)$ 使得指数损失函数最小化，对 $H(x)$ 求偏导
    $\begin{array}{l} \frac{\partial l_{exp}(H|D)}{\partial H(x)}\\ =\frac{\partial \mathbb E_{x \sim D}[e^{-f(x)H(x)}]}{\partial H(x)}\\ =\frac{\partial\Sigma_{x \in D}D(x)e^{-f(x)H(x)}}{\partial H(x)}\\ =\frac{\partial\Sigma_{i=1}^{|D|}D(x_i)[(e^{-H(x_i)}P(f(x_i)=1|x_i)+e^{H(x_i)}P(f(x_i)=-1|x_i)]}{\partial H(x)}\\ =e^{-H(x)}P(f(x)=1|x)+e^{H(x)}P(f(x)=-1|x) \end{array}$
    令上式取0，得到
    $H(x)=\frac{1}{2}\ ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)}$
    取符号函数，得到
    $\begin{array}{} sign(H(x))\\ = sign(\frac{1}{2}\ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)})\\ = \left\{ \begin{array}{lcl} 1, &{P(f(x)=1|x)}>{P(f(x)=-1|x)} \\ -1, &{P(f(x)=1|x)}<{P(f(x)=-1|x)} \end{array} \right. \\ = \arg max_{y \in \{-1,1\}}P(f(x) = y|x) \end {array}$
    $sign(H(x))$ 达到了贝叶斯最优错误率
    
    若指数损失函数最小化，则 $H(x)f(x) > 0$ ，分类错误率也将最小化
    
    指数损失函数是分类任务原本0/1损失函数的一致的替代损失函数
  - 确定基分类器的权重 $\alpha_t$
    $H(x)=\Sigma_{t=1}^T\alpha_th_t(x)$
    为了得到使得指数损失函数尽可能小的 $H(x)$ ，应确定 $\alpha_t$ 使得每次添加的 $\alpha_t h_t$ 最小化指数损失函数
    $\begin{array}{l} l_{exp}(\alpha_t h_t|D_t)\\ =\mathbb E_{x \sim D_t}[e^{-f(x)\alpha_th_t(x)}]\\ =\mathbb E_{x \sim D_t}[e^{-\alpha_t}\mathbb I(f(x)=h_t(x))+e^{\alpha_t}\mathbb I(f(x)\not = h_t(x))]\\ =e^{-\alpha_t}P_{x \sim D_t}(f(x)=h_t(x) + e^{\alpha_t}P_{x \sim D_t}(f(x)\not =h_t(x)\\ =e^{-\alpha_t}(1 - \epsilon_t)+e^{\alpha_t}\epsilon_t \end{array}$
    对 $\alpha_t$ 求偏导
    $\frac{\partial l_{exp}(\alpha_th_t|D_t)}{\partial \alpha_t} = -e^{-\alpha_t}(1 - \epsilon_t)+e^{\alpha_t}\epsilon_t$
    令偏导数取0，得到 $\alpha_t$ 的闭式解
    $\alpha_t = \frac{1}{2}\ln(\frac{1-\epsilon_t}{\epsilon_t})$
  - 对样本分布进行调整，使得下一轮的基学习器 $h_t$ 能纠正 $H_{t-1}$ 的一些错误
    
    $H_{t-1}=\Sigma_{t=1}^{T-1}\alpha_th_t(x)$
    
    要求最小化
    $\begin{array}{} l_{exp}(H_{t-1} + h_t|D)\\ =\mathbb E_{x \sim D}[e^{-f(x)(H_{t-1}(x) + h_t(x))}]\\ =\mathbb E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}e^{-f(x)h_t(x)}] \end{array}$
    由于 $f^2(x) = h_t^2(x) = 1$ , $e^x=1 + x + \frac{x^2}{2}+o(x^2)$ ,得到
    $\begin{array}{} l_{exp}(H_{t-1} + h_t|D)\\ =\mathbb E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}e^{-f(x)h_t(x)}]\\ \approx E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}(1-f(x)h_t(x)+\frac{f^2(x)h_t^2(x)}{2})]\\ = \mathbb E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}(1-f(x)h_t(x)+\frac{1}{2})]\\ \end{array}$
    由此得出理想的基学习器应满足这样的约束
    $\begin{array}{l} h_t(x) \\ = \arg min_{h} l_{exp}(H_{t-1} + h_t|D) \\ = \arg min_{h} E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}(1-f(x)h_t(x)+\frac{1}{2})]\\ = \arg max_{h} E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}f(x)h_t(x)]\\ = \arg max_{h} E_{x \sim D}[\frac{e^{-f(x)(H_{t-1}(x)}}{E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}]}f(x)h_t(x)] \end{array}$
    其中 $E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}]=\Sigma_{i=1}^{|D|}D(x_i)[e^{-f(x)(H_{t-1}(x)}]$ 是一个常数
    
    令 $D_t$ 表示一个分布
    $D_t(x)=\frac{D(x)e^{-f(x)H_{t-1}(x)}}{\mathbb E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}]}$
    等价于令
    $\begin{array}{l} h_t(x) \\ = \arg max_{h} \mathbb E_{x \sim D}[\frac{e^{-f(x)(H_{t-1}(x)}}{E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}]}f(x)h_t(x)]\\ = \arg max_{h} \Sigma_{i=1}^{|D|}D(x_i)[\frac{e^{-f(x)(H_{t-1}(x)}}{E_{x \sim D}[e^{-f(x)(H_{t-1}(x)}]}f(x_i)h_t(x_i)]\\ = \arg max_{h} \Sigma_{i=1}^{|D_t|}D_t(x_i)[f(x_i)h_t(x_i)]\\ = \arg max_{h} \mathbb E_{x \sim D_t}[f(x)h_t(x)] \end{array}$
    由于 $f(x),h(x) \in \{-1,+1\}$ ，有
    $f(x)h(x) = 1 - 2\mathbb I(f(x) \not = h(x))$
    则理想的基学习器将在分布 $D_t$ 下最小化分类误差，因此弱分类器的训练集将基于分布 $D_t$ 来训练，且分类误差应小于0.5
    $h_t(x)=\arg min_h \mathbb E_{x \sim D_t}[\mathbb I(f(x) \not = h(x))]$
    考虑到 $D_t$ 和 $D_{t+1}$ 的关系，有
    $\begin{array}{ll} D_{t+1}(x)\\ = \frac{D(x)e^{-f(x)H_t(x)}}{\mathbb E_{x \sim D}[e^{-f(x)H_t(x)}]}\\ = \frac{D(x)e^{-f(x)H_{t-1}(x)}e^{-f(x)\alpha_t h_t(x)}}{\mathbb E_{x \sim D}[e^{-f(x)H_t(x)}]}\\ =D_t(x)e^{-f(x)\alpha_t h_t(x)}\frac{e^{-f(x)H_{t-1}(x)}}{e^{-f(x)H_t(x)}} \end{array}$
总结
1. Boosting算法在训练过程中的每一轮中，根据样本分布为每个训练样本重新赋予一个权重
2. 对无法接受带权样本的基学习算法，通过重采样法来处理
3. Boosting算法在训练每一轮都要检查当前生成的基学习器是否满足基本条件（ $\epsilon < 0.5$ ）分类结果比随机猜测好（学习过程停止，重采样与重启动？）
4. Boosting主要关注降低偏差，因此能基于泛化性能弱的数据集构建出很强的集成