集成学习
个体与集成¶
先由现有的学习算法从训练数据中产生一组个体学习器，再由某种策略将他们结合起来
同质集成：
集成中只包含同种类型的个体学习器，其中的个体学习器也称作基学习器，响应的学习算法称为基学习算法
异质集成：
集成中的个体学习器由不同的学习算法生成，其中的个体学习器也称作组件学习器
要获得好的集成，个体学习器应好而不同，即个体学习器要有一定的准确性（至少要比随机猜想强），同时也要具有多样性，即学习器间具有差异
简单投票法 (对于二分类，\(y \in {-1, +1}\))：
\[
H(x) = sign(\sum_{i = 1}^{T}h_i(x))
\]
即选择学习器结果的众数
个体学习器的错误率 \(\epsilon\)
\[
P(h_i(x) \neq f(x)) = \epsilon
\]
其中 \(h_i\) 表示每个个体学习器，\(f\) 表示真实函数
集成个体学习器的收敛性保证：
\[
\begin{align}
P(H(x) \neq f(x)) &= \sum_{k = 0}^{\lfloor T/2 \rfloor}
\begin{pmatrix}
T \\
k
\end{pmatrix}(1 - \epsilon)^k\epsilon^{T-k} \\
&\leq \exp(-\frac{1}{2}T(1 - 2\epsilon)^2)
\end{align}
\]
由此可得：
-
收敛速率随着个体分类器数目呈指数级上升
-
集成错误率随着个体分类器数目呈指数级下降
-
\(\epsilon = 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) = \mathop{\arg\min}_{\alpha, h} \ l_{exp}(H_{t - 1} + \alpha h | D)
\]