集成学习

个体与集成

先由现有的学习算法从训练数据中产生一组个体学习器，再由某种策略将他们结合起来

同质集成：

集成中只包含同种类型的个体学习器，其中的个体学习器也称作基学习器，响应的学习算法称为基学习算法

异质集成：

集成中的个体学习器由不同的学习算法生成，其中的个体学习器也称作组件学习器

要获得好的集成，个体学习器应好而不同，即个体学习器要有一定的准确性（至少要比随机猜想强），同时也要具有多样性，即学习器间具有差异

简单投票法 (对于二分类，$y\in -1,+1$)：

$$H(x)=sign(\sum _{i=1}^T{h}_i(x))$$

即选择学习器结果的众数

个体学习器的错误率 $ϵ$

$$P(h_i(x)\ne f(x))=ϵ$$

其中 $h_i$ 表示每个个体学习器，$f$ 表示真实函数

集成个体学习器的收敛性保证：

$$\begin{array}{rl}P(H(x)\ne f(x))& =\sum _{k=0}^{\lfloor T/2\rfloor }\left(\begin{array}{c}T\\ k\end{array}\right)(1-ϵ{)}^k{ϵ}^{T-k}\\ & \le \exp (-\frac{1}{2}T(1-2ϵ{)}^2)\end{array}$$

由此可得：

• 收敛速率随着个体分类器数目呈指数级上升

• 集成错误率随着个体分类器数目呈指数级下降

• $ϵ=0.5$ 的个体分类器对收敛没有作用（大于 0.5 和小于 0.5 都能起到一定的作用）

Boosting

一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值 T，最终将这 T 个基学习器进行加权结合.

AdaBoost

对于二分类问题，其中 $y_i\in \{-1,+1\}$，$f$ 是真实函数

加性模型：

$$H(x)=\sum _{t=1}^T{\alpha }_t{h}_t(x)$$

指数损失函数：

$$l_{exp}(H|D)=E_{x\sim D}[e^{-f(x)H(x)}]$$

前向分布求解算法

每一轮只学习一个学习器 $h_t$ 和相应的权重 ${\alpha }_t$

形式化表达（第 t 轮第优化目标为）：

$$({\alpha }_t,h_t)=\underset{\alpha ,h}{\arg min}{l}_{exp}(H_{t-1}+\alpha h|D)$$