去年的学习笔记，最近复习拿出来整理一下。

Aggregation Model

假设有$T$个模型$g_1,\cdots ,g_T$，常见的聚合方法有：

1. 在一个验证集上选出最佳的：

G(x)=gt∗(x)with t∗=argmin⁡t∈{1,2,…,T}Eval (gt−)G(\mathbf{x})=g_{t_{*}}(\mathbf{x}) \text { with } t_{*}=\operatorname{argmin}_{t \in\{1,2, \ldots, T\}} E_{\text {val }}\left(g_{t}^{-}\right) G(x)=gt∗​​(x) with t∗​=argmint∈{1,2,…,T}​Eval ​(gt−​)

2. 将所有模型取平均值：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^{T}1\cdot g_t(\mathbf{x})\right)$$

3. 将所有模型加权平均：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{\alpha }_t\cdot g_t(\mathbf{x})\right)\text{ with }{\alpha }_t\ge 0$$

4. 根据当前状态确定：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{q}_t(\mathbf{x})\cdot g_t(\mathbf{x})\right)\text{ with }{q}_t(\mathbf{x})\ge 0$$

以上都是直观上的想法，下面进一步研究。

Blending

均值融合（Uniform Blending）

在分类问题中：
$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{g}_t(\mathbf{x})\right)$$
在多分类任务中少数服从多数：

在回归时就是取所有模型输出的均值。

当$g_t$预测值相近，那么性能不变。当$g_t$多样民主时，一些分类结果$g_t(\mathbf{x})>f(\mathbf{x})$，另一些分类结果$ g_{t}(\mathbf{x})<f(\mathbf{x})$，那么理想状态取平均可以获得最佳解。综合上述两种需求，多样性的hypotheses更容易使得融合模型性能更佳。

可以通过理论推导得出，均值融合可以降低误差：
$$\mathrm{avg}\left(E_{\text{out }}\left(g_t\right)\right)=\mathrm{avg}\left(\mathcal{E}{\left(g_t-G\right)}^2\right)+E_{\text{out }}(G)$$
从上式可以得出除非所有的$g_t$相等，否则融合后的模型$G$的误差是要比所有子模型误差的平均小的（相差了一个方差）。

线性融合（Linear Blending）

分类问题：
$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{\alpha }_t\cdot g_t(\mathbf{x})\right)\text{ with }{\alpha }_t\ge 0$$
回归问题：
$$\underset{{\alpha }_t\ge 0}{\min }\frac{1}{N}\sum _{n=1}^N{\left(y_n-\sum _{t=1}^T{\alpha }_t{g}_t\left({\mathbf{x}}_n\right)\right)}^2$$
那么最优化问题就可以写为：
$$\underset{\alpha t\ge 0}{\min }\frac{1}{N}\sum _{n=1}^N\mathrm{err}\left(y_n,\sum _{t=1}^T{\alpha }_t{g}_t\left({\mathbf{x}}_n\right)\right)$$
使用训练集获取$g_t$，但是最好使用验证集获取${\alpha }_t$。

Stacking

如上图所示，第一部分是用$N$个基础模型如xgb1、lgb1进行$n$折交叉验证，那么就得到了一个$N\ast n$的特征矩阵，用这个特征矩阵作为第二层模型的输入。测试时也要把原数据集通过$N$个基模型映射到$N$维的空间上去。

Bagging

Blending是学到不同的$g_t$后把他们聚合起来，那能不能边学$g_t$边聚合。

获得多样性$g_t$的方法有：

• diversity by different models
• diversity by different parameters: 例如优化方法GD的步长变化多样
• diversity by algorithmic randomness：例如模型算法中自带随机性
• diversity by data randomness

Bootstrap Aggregation

从数据出发，如果能得到很多多样性的数据集$D_t$来训练一个$g_t$就好了。可以用数据重采样获得仿真的$D_t$：

1. 在原有的大小为 $N$ 的数据集 $\mathcal{D}$ 上, 有放回的采样 $N^{\prime }$ 次获得仿真数据集 ${\mathcal{D}}_t\to$ 这一步便是 Bootstrap 操作
2. 通过 $\mathcal{A}\left({\tilde{\mathcal{D}}}_t\right)$ 获取 $g_t$, 再使用均值融合获得: G=Uniform⁡({gt})G=\operatorname{Uniform}\left(\left\{g_{t}\right\}\right)G=Uniform({gt​}) 。

Boostrap方法合理前提是：数据集的多样性和基算法 $\mathcal{A}$对于随机数据敏感。

Adaptive Boosting （AdaBoost ）实际上是从 Bagging 的核心 bootstrap 出发实现的一种融合算法，下面具体介绍。

AdaBoost

AdaBoost的核心思想是当前所有模型错分类的数据会被强化，训练下个弱分类器。最终所有弱分类器投票。一个经典的示意图：

简单图示算法流程：

算法流程

对二元分类问题总结一下：

输入为样本集D={(x,y1),(x2,y2),…(xn,yn)}D=\left\{\left(x, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots\left(x_{n}, y_{n}\right)\right\}D={(x,y1​),(x2​,y2​),…(xn​,yn​)}，，弱学习器算法, 弱学习器迭代次数$T$。

输出为最终的强学习器$G(x)$。

1. 初始化样本集权重为

$${\mathbf{u}}^{(1)}=\left[\frac{1}{N},\frac{1}{N},\cdots ,\frac{1}{N}\right]$$

2. 对于$t=1,2,...,T$：

   (a) 使用具有权重${\mathbf{u}}^{(t)}$的样本集来训练数据，得到弱学习器$g_t(x)$

   (b) 计算$g_t(x)$的分类误差率
   $${ϵ}_t=\frac{{\sum }_{n=1}^N{u}_n^{(t)}[y_n\ne g_t\left({\mathbf{x}}_n\right)]}{{\sum }_{n=1}^N{u}_n^{(t)}}$$
   © 更新样本集的权重分布：分类对的样本，权重$u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot \sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}$；分类错的样本，权重$u_n^{(t+1)}\leftarrow u_n^{(t)}/\sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}$

   (d) 计算弱分类器的系数：
   $${\alpha }_t=\ln \left(\sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}\right)$$

3. 最终构建的分类器为：

$$G(\mathbf{x})=\mathrm{sign}\left(\sum _{t=1}^T{\alpha }_t{g}_t(\mathbf{x})\right)$$

这里最弱的分类器可以是一个decision stump（单层决策树），只有三个参数：选择一个特征$i$，设定一个阈值$\theta$，判定阈值左右是什么类$s$。