聚合模型实际上就是将许多模型聚合在一起，从而使其分类性能更佳。
aggregation models: mix or combine hypotheses (for better performance)
下面举个例子：
你有 (T) 朋友，他们对于股票涨停的预测表现为 (g_1,cdots ,g_T)。 常见的聚合（aggregation）方法有：
- select the most trust-worthy friend from their usual performance
根据他们的平常表现，选出最值得信任的朋友
$$
G(mathbf{x})=g_{t_{}}(mathbf{x}) ext { with } t_{}=operatorname{argmin}{t in{1,2, ldots, T}} E{ ext {val }}left(g_{t}^{-} ight)[]将所有朋友的预测取平均值[][]将所有朋友的预测值取加权平均值[][]根据当前状态 (mathbf{x}) 确定权重后结合。[G(mathbf{x})=operatorname{sign}left(sum_{t=1}^{T} q_{t}(mathbf{x}) cdot g_{t}(mathbf{x}) ight) ext { with } q_{t}(mathbf{x}) geq 0 ]
学到这里，可能有一种感觉，与模型选择比较相近，并根据直观印象，取平均获得是分类器一定比最好的差，比最差的好。所以会感觉 aggregation 用处不大，那现在看一下， aggregation 的真正的用处是什么？
以下图为例：
左侧第一个图中，实际上是使用三条竖线或横线实现了二分类，虽然竖线或横线是很弱的一种分类器，但是如此结合便获得了一个较强的分类器，其分类效果好于任何一个分类器独自分类的结果。
右侧第一个图中，是许多直线的取平均值获得的，这种状态存在于数据样本较少时，可以获取一种与SVM类似的效果，虽然这么多直线对于训练样本（采样数据）的分类效果一样，但是对于测试样本（全局数据）可能有更好的分类效果。
所以说真正的 aggregation 并不只是单纯的取平均而已，其可能是为了弥补当前分类器的不足（分类器分类性能较弱，分类器的泛化能力较弱）。即合理的聚合（aggregation）代表了更好的性能（performance）。
Blending
均值融合（uniform blending）
用于分类：
数学表达如下：
有 (T) 个人，每人一票。当 (g_{t}) 预测值相近，那么性能不变。当 (g_{t}) 多样民主时，少数服从多数（majority can correct minority）
在多分类中的数学表达为：
用于回归：
当 (g_{t}) 预测值相近，那么性能不变。当 (g_{t}) 多样民主时，一些分类结果 (g_{t}(mathbf{x})>f(mathbf{x})) ，另一些分类结果 (g_{t}(mathbf{x})<f(mathbf{x}))，那么理想状态取平均可以获得最佳解。
综合上述两种需求，多样性的 hypotheses 更容易使得融合模型性能更佳。
现在进行理论分析，其性能是否改善，这里以回归模型为例：
这里的取平均是针对全部的 hypothesis 或者说 (T) 个 (g_t) 进行的，并针对的是随机的单个样本。
也就是说，在对全部训练样本 (mathbf{x}_n) 进行分析取全部误差的平均值。这里 用(mathcal{E}) 表示平均值。举个例子：(frac{1}{N}sum_{n = 1}^{N}left(g_{t}(mathrm{x}_n)-f(mathrm{x}_n) ight)^{2} = mathcal{E}left(g_{t}-f ight)^{2})。
即 (G) 优于 (g_t) 的平均值。
现在假设在分布为 (P^{N}) (i.i.d.) 的数据上选取大小为 (N) 的数据集 (mathcal{D}_{t})，并通过 (mathcal{A}left(mathcal{D}_{t} ight)) 获取 (g_{t})。那么执行无数次可以获取到 (ar g)，表达式如下：
那么现在用 (ar{g}) 代替 (G)，之前所求仍然成立，即：
其中
- (operatorname{avg}left(E_{ ext {out }}left(g_{t} ight) ight)) 代表了算法的期望性能（expected performance of A）。
- (E_{ ext {out }}(ar{g})) 代表了共识性能（performance of consensus），又叫偏差（bias）
- (operatorname{avg}left(mathcal{E}left(g_{t}-ar{g} ight)^{2} ight)) 代表了共识的期望偏差（expected deviation to consensus），又叫方差（variance）
线性融合（Linear Blending）
用于分类：
数学表达如下：
与均值融合相似，有 (T) 个人，但是每人 (alpha_t) 票，而不是都只有一票。
用于回归：
这里重温一下线性回归加非线性转换的结合模型，其数学表达如下：
可以看出两种非常相似。
所以说线性融合就是线性回归使用假设函数作为非线性转换工具，并且有约束条件。
那么该最优化问题可以写为：
在实际运用中，常常不用约束条件 (alpha_t > 0)，因为：
也就是说认为 (g_t) 的分类错误很高，与预测值常常相反。那么取反便会得到较好性能的分类器。
与模型选择一样，虽然使用训练集获取 (g_t)，但是最好使用验证集获取 (alpha_t)。
堆叠融合（Stacking or Any Blending）
前面提到的均值融合和线性融合实际上类似于滤波，将预测值乘以一个系数后输出，若将其视为一个模型，那么该模型表达式为 ( ilde g(g_1,g_2,cdots,g_T) = alpha_1 g_1 + alpha_2 g_2 + cdots + alpha_T g_T)。那么 blending 的一般形式便不局限于输入参数的线性组合，可能 ( ilde g) 是也是一个 hypothesis。
Given (g_{1}^{-}, g_{2}^{-}, ldots, g_{T}^{-}) from (mathcal{D}_{ ext {train }},) transform (left(mathbf{x}_{n}, y_{n} ight)) in (mathcal{D}_{ ext {val }}) to (left(mathbf{z}_{n}=Phi^{-}left(mathbf{x}_{n} ight), y_{n} ight),) where
学习步骤如下：
- 从训练集 (mathcal{D}_{ ext {train}}) 中获取 (g_{1}^{-}, g_{2}^{-}, ldots, g_{T}^{-})，将验证集数据映射到 (mathcal Z) 空间，即 (mathbf{z}_{n}=left(Phi^{-}left(mathbf{x}_{n} ight), y_{n} ight)) ，其中映射函数为：(Phi^{-}(mathbf{x})=left(g_{1}^{-}(mathbf{x}), ldots, g_{T}^{-}(mathbf{x}) ight))
- 在 (mathcal{Z}) 空间训练出融合各种模型的模型（函数） ( ilde{g}) (=) AnyModel (left(left{left(mathbf{z}_{n}, y_{n} ight) ight} ight))
- 最终的堆叠融合模型 (G_{mathrm{ANYB}}(mathbf{x})= ilde{g}(Phi(mathbf{x})))。
优缺点：
- 很强大（powerful），可以完成有条件的融合（conditional blending）
- 很容易过拟合（模型复杂度过高）
应用（Blending in Practice）
在 any blending 的基础上，将原来的 (g_t) 和 (G) 结合在一起再做一次融合。
Bagging
blending : 在获取 (g_t) 之后，进行聚合;
learning : 在聚合（学习）过程中获取 (g_t)。
获得多样 (g_t) 的方法有：
- diversity by different models
- diversity by different parameters: 例如优化方法GD的步长变化多样
- diversity by algorithmic randomness
- diversity by data randomness
下面便从数据出发，来满足假设函数的多样性。
那应该怎么做呢，在前面提到有共识便是一个模型的期望表现：
其优于单个的 (g_t)。
其由两个部分组成，一个是无穷多个 (g_t)，另一个则是丰富的样本数据。对于第一个问题这里提供有限个但相当多个 (g_t)，第二个问题只能从手中的数据入手，来创造多样的样本数据集 (mathcal{D}_t)。
拔靴法（Bootstrap Aggregation）
Bagging 实际上就是指 Bootstrap Aggregation，拔靴法实际上是从手中的数据重采样来获得仿真的 (mathcal{D}_t)。其实现方法是：
- 在原有的大小为 (N) 的数据集 (mathcal{D}) 上，有放回的采样 (N^prime) 次获得仿真数据集 ( ilde mathcal{D} _ t ightarrow) 这一步便是 Bootstrap 操作。
- 通过 (mathcal A ( ilde mathcal{D} _ t)) 获取 (g_t)，再使用均值融合获得：(G = operatorname {Uniform}({g_t}))。
拔靴法（bootstrap aggregation）是一种简单的基于基算法（base algorithm (mathcal A)）的融合算法（meta algorithm）。方法合理前提是：数据集的多样性和基算法 (mathcal A) 对于随机数据敏感。
Adaptive Boosting
Adaptive Boosting （AdaBoost ）实际上是从 Bagging 的核心 bootstrap 出发实现的一种融合算法。具体实现如下：
加权基算法（Weighted Base Algorithm）
数据集的构造相当于对于不同样本的权重不同，也就是说重采样（Re-sample）过程相当于重赋予权重（Re-weighting）过程：
假设重采样如下：
原来的误差计算如下：
现在则是：
其中 (u_1 = 2,u_2 = 1,u_3 = 0,u_4 = 1)。
那么袋中的每一个 (g_t) 都是通过最小化加权误差（bootstrap-weighted error）获得的。
所以加权基算法（Weighted Base Algorithm）的数学表达为：
那么通过重新赋值获取多样的 (g_t) 是另一种可行的方法：
假如两个 (g_t) 的获取方法如下：
什么时候两个人分类器会很不一样呢？就是当 (g_t) 对于权重 (u _ { n } ^ { ( t ) }) 的性能很好，但是 (g_t) 对于权重 (u _ { n } ^ { ( t + 1) }) 的性能很差，最差的 (g) 则是随机值也就是说有 50% 的概率会预测准确。即：
所以现在希望的效果是：
那么通过重新放缩权重（re-scaling (multiplying) weights）便可以实现，即：
对于 (g_t) 分类错误的样本：
对于 (g_t) 分类正确的样本：
那么在实际中如何实现呢？这里提出放缩系数。
放缩系数（Scaling Factor）
错误率 (epsilon _ { t }) 定义如下：
放缩系数的定义如下：
那么：
Linear Aggregation on the Fly
有了上述的前提，便可以设计一个由数据多样化创造的融合算法，而AdaBoost 除了上述一些前提外，还有一步，那就是 Linear Aggregation on the Fly，在学习中获得线性融合的参数 (alpha_t)，即：
- 当 (epsilon _ { t } ightarrow 0) 时，(mathbf { star } _ { t } ightarrow inf, ln(mathbf { star } _ { t }) ightarrow inf)，也就是说当无错误时，给予无穷权重，即当前 (g_t) 完全可以完成任务。
- 当 (epsilon _ { t } = frac{1}{2}) 时，(mathbf { star } _ { t } = 1, ln(mathbf { star } _ { t }) = 0)也就是说当错误率为1/2时，不给予权重，即 (g_t) 与随机数的性能一样无用。
- 当 (epsilon _ { t } ightarrow 1) 时，(mathbf { star } _ { t } = 0, ln(mathbf { star } _ { t }) ightarrow -inf) 也就是说当全错误时，给予负无穷权重，即只需要将分类结果取反便可以获得非常高准确率的 (g_t)。
AdaBoost 实现步骤
(u^{(1)} = left[frac{1}{N},cdots,frac{1}{N}
ight])
for (t = 1,cdots,T)
- 由 (mathcal { A } left( mathcal { D } , mathbf { u } ^ { ( t ) } ight)) 获取(g _ { t }) ， 其中 (mathcal { A }) 用于优化权重为 (mathbf { u } ^ { ( t ) }) 的加权误差。
- 由 (mathbf { u } ^ { ( t ) }) 更新 (mathbf { u } ^ { ( t+1 ) })[egin{aligned} ]
left[ kern-0.15em left[y _ { n } = g _ { t } left( mathbf { x } _ { n }
ight)
ight] kern-0.15em
ight] quad u ^ { ( t + 1 ) } _ n &leftarrow u ^ { ( t ) } _n / mathbf { star } _ { t } end{aligned}
$$
其中:$epsilon _ { t } = frac {sum _ { n = 1 } ^ { N } u _ { n } ^ { ( t + 1 ) } left[ kern-0.15em left[y _ { n }
eq g _ { t } left( mathbf { x } _ { n }
ight)
ight] kern-0.15em
ight] } { sum _ { n = 1 } ^ { N } u _ { n } ^ { ( t + 1 ) } }$，$mathbf { star } _ { t } = sqrt { frac { 1 - epsilon _ { t } } { epsilon _ { t } } }$
- 计算线性融合系数 (alpha_t = ln(mathbf { star } _ { t }))
- 获得最终hypothesis： (G ( mathbf { x } ) = operatorname { sign } left( sum _ { t = 1 } ^ { T } alpha _ { t } g _ { t } ( mathbf { x } ) ight))
理论证明（Theoretical Guarantee）
AdaBoost 的 VC bound 如下：
原作者有证明最多经过 (T= log(N)) 次迭代，便可以实现 (E_{ ext{in}}(G) = 0)，只要基模型比随机数性能优越即可 (epsilon _ { t } leq epsilon < frac { 1 } { 2 })。
也就是说，如果基模型 (g) 很弱（weak），但是总比随机数优秀，那么由AdaBoost + (mathcal A) 获取的 (G) 也会很强（strong）。
决策树桩（Decision Stump）
数学表达如下：
一共有三个参数 特征（feature） (i)，阈值（threshold）( heta) ，方向（direction）(s)。其实现的功能便是一个分界点，特征（feature） (i) 表达的是在第 (i) 维的分解点，阈值（threshold）( heta) 代表在本维度的分界点位于 ( heta)，方向（direction）(s) 代表了分界点两边的样本类型。
这是一个弱模型，但是将其作为 AdaBoost 的基模型便可以实现高精度预测了，并且效率很高，时间复杂度为：(O(d cdot N log N))
若使用 Decision Stump 作为 AdaBoost 的基模型，假设一个简单的数据集如下分布：
那么其学习过程的一种状态可能如下表达：
