i. 个体学习器数目 $K$ 对集成学习准确率的影响
假设各个学习器相互独立（重要假设，其实肯定不成立），基学习器 $h_i(\boldsymbol x)$，真实函数 $f(\boldsymbol x)$，二分类问题标签取值 $y \in \{ -1, +1\}$。
假设每个基学习器的正确率 $p_+$ 都相同且大于 1/2，为：
$$ p_+ = P(h_i(\boldsymbol x) = f(\boldsymbol x)) > \frac 12 $$
通过简单投票法结合 $K$ 个基分类器成为集成学习器 $H(\boldsymbol x)$，如果超过半数正确就正确，假设 $K$ 为奇数。
$$ H(\boldsymbol x) = {\text {sign}} \left( \sum_{k=1}^K h_k(\boldsymbol x) \right) $$
根据 Hoeffding 不等式：
对于服从二项分布的变量 $b(n, p)$，可知：
$$ P(b(n, p) = k) = C_n^k \cdot p^k (1 - p)^{n-k} $$
因而有：
$$ P(b(n, p) \le k) = \sum_{k=0}^n C_n^k \cdot p^k (1 - p)^{n-k} $$
对于 $\delta > 0$，令 $k = (p - \delta) n$，有 Hoeffding 不等式：
$$ P(b(n, p) \le (p - \delta ) n) \le {\text e}^{-2 \delta^2 n} $$
可知各 $h_k(\boldsymbol x)$ 的正确次数 $N$ 服从二项分布 $b(K, p_+)$。因 $p_+ > \frac 12$，令 $\delta = p_+ - \frac 12 > 0$，作 $k = (p_+ - \delta)K = \frac K 2$，有：
$$ P \left (N \le \frac K 2 \right) \le {\rm e}^{-2K(p_+ - \frac 12)^2 } $$
左边即集成学习的错误率：
$$ P \left ( H(\boldsymbol x) \neq f(\boldsymbol x) \right) \le {\rm e}^{-2K(p_+ - \frac 12)^2 } $$
因而 $K \to +\infin$ 时，错误率上界逼近于 $0$。
ii. 个体学习器间的多样性
i. Bagging 方法综述
产生尽可能有差异的基学习器的一个方法，就是通过对训练样本集进行多次不同的采样，得到多个子集，并从不同的子集训练出不同的基学习器。
比如之前提过的「有放回采样法 / 自助采样法 (bootstrap sampling)」：对 $|X|$ 大小的样本进行 $|X|$ 次有放回采样，得到一个新样本集，其中将出现 63.2% 的原始样本。
Bagging (Bootstrap Aggregating) 方法就是进行 $K$ 轮自助采样得到 $K$ 个数据集，每个数据集训练出一个基学习器 $h_k(\boldsymbol x)$，再通过结合成为集成学习器 $H(\boldsymbol x)$。分类任务一般用简单投票法（如下式）、回归任务一般用简单平均法。
$$ H(\boldsymbol x) = \argmax_{y \in {\mathcal Y}} \sum_{k=1}^K {\mathbb I} (h_k(\boldsymbol x) = y) $$
优势：
特性：
ii. 包外估计 (out-of-bag estimate)
包外验证：对每个基学习器而言，训练全集中约 36.8% 的样本没有被用到，它们可以用作验证集来评估泛化性能。如果 $D$ 为训练全集，$D_k$ 为自助采样得到的子集，对应的验证集即为 $V_{k} = D_k / D$。
包外预测：对于每一个样本 $\boldsymbol x$ 的包外预测 $H_{oob}(\boldsymbol x)$，即是仅考虑验证集包含 $\boldsymbol x$ 的各个基学习器（$h_k(\boldsymbol x) \ {\rm where} \ \boldsymbol x \in V_k$）集成起来的结果，比如简单投票法时：
$$ H_{oob}(\boldsymbol x) = \argmax_{y \in {\mathcal Y}} \sum_{k=1}^K {\mathbb I} (h_k(\boldsymbol x) = y) \cdot {\mathbb I} (\boldsymbol x\in V_{k}) $$
包外准确率：即包外预测结果的准确率，能够表示包外泛化误差。
$$ \epsilon_{oob} = \frac {1}{|D|} \sum_{(\boldsymbol x, y) \in D} {\mathbb I} (H_{oob}(\boldsymbol x) \neq y) $$
包外数据的其他用途：