集成分类的有效性证明

本文证明分类问题使用集成学习方法的有效性。

设有集成模型

$$\begin{align} H_{T}(x) = \cases{ 1 \;\; \text{if } \sum h_{t} > 0\cr -1 \;\; \text{if } \sum h_{t} \le 0 } \end{align}$$

$T$ 表示基分类器的个数。每个基分类器

$$\begin{align} h_{t}(x) = \cases{ 1 & \text{if x 判别为正类}\cr -1 & \text{if x 判别为负类} }, \quad t=1, \dots, T \end{align}$$

每个基分类器分类错误的概率为

$$P(h_{t}(x) \neq f(x)) = \varepsilon_{t}$$

由于每个基分类器的分类性能大致相等，为化简起见，我们令所有基分类器的分类错误概率均为 $\varepsilon \lt 0.5$ （弱可学习器）.

设 $C(H_{T}(x))$ 表示集成模型中，基分类器分类正确的数量，则根据二项分布有

$$P(C(H_{T}(x)) \leq k) = \sum_{i=1}^{k}C_{T}^{i}(1-\varepsilon)^{i}\varepsilon^{k-i}$$

上式表示分类正确的基分类器数量在 $k$ 范围内的概率。

为方便起见，集成模型的基分类器个数 $T$ 为偶数。因此，当 $k \leq \frac{T}{2}$ 时，集成模型分类错误，其误分类概率为

$$P(C(H_{T}(x)) \leq \frac{T}{2}) = \sum_{i=1}^{\frac{T}{2}}C_{T}^{i}(1-\varepsilon)^{i}\varepsilon^{k-i}$$

现在我们要评估这个概率的上限。根据 Hoeffding’s inequality ，有

$$\mathrm { P } ( C(H_{T}(x)) \leq ( \varepsilon - \lambda ) T ) \leq \exp \left( - 2 \lambda ^ { 2 } T \right)$$

取 $( \varepsilon - \lambda ) T=\frac{T}{2}$ 代入上式消去 $ \lambda $ ，有

$$P(C(H_{T}(x)) \leq \frac{T}{2}) \leq \exp(-\frac{1}{2}(1-2\varepsilon)^{2}T)$$

也就是说，随着基分类器数量的增加，集成模型的误分类概率呈指数下降。那么，我们只需要证明集成模型的误分类概率小于基分类模型的即可

$$\begin{align} P(C(H_{T}(x)) \leq \frac{T}{2}) &\leq \exp(-\frac{1}{2}(1-2\varepsilon)^{2}T) \newline & \lt P(h_{t}(x) \neq f(x)) \newline &= \varepsilon \end{align}$$

即，

$$\exp(-\frac{1}{2}(1-2\varepsilon)^{2}T) \lt \varepsilon$$

化简有，

$$T \gt -\frac{2\ln{\varepsilon}}{(1-2\varepsilon)^2}$$

易知，任给 $\varepsilon \in (0, 0.5)$ ，总能找到恰当的 $T$ 使上式成立。也就是说如果基分类器的分类正确率在 $(0.5, 1)$ 区间，模型集成是有效的。

Q.E.D.

转载请包括本文地址：https://allenwind.github.io/blog/7464/

更多文章请参考：https://allenwind.github.io/blog/archives/