Hoeffding不等式及其在机器学习中的应用

考虑二分类问题y \in\{-1,+1\} 和真实函数f , 假定基分类器的错误率为\epsilon , 即对每个基分类器h_i 有

P\left(h_{i}(x) \neq f(x)\right)=\epsilon 假设集成通过简单投票法结合T 个基分类器, 若有超过半数的基分类器正确, 则集成分类就正确:

H(x)=\operatorname{sian}\left(\sum_{i=1}^{T} h_{i}(x)\right)

假设基分类器的错误率相互独立, 则由Hoeffding不等式可知, 集成的错误率为:

P(H(x) \neq f(x))=\sum_{k=0}^{|T / 2|}\left(\begin{array}{l} T \\ k \end{array}\right)(1-\epsilon)^{k} \epsilon^{T-k} \leq \exp \left(-\frac{1}{2} T(1-2 \epsilon)^{2}\right)

Hoeffding不等式适用于有界的随机变量. 设有两两独立的一系列随机变量X_1,...,X_n. 假设对所有的1≤i≤n, X_i都是几乎有界的变量, 即满足：

P\left(X_{i} \in\left[a_{i}, b_{i}\right]\right)=1

那么这n个随机变量的经验期望：

\bar{X}=\frac{X_{1}+\cdots+X_{n}}{n} 满足以下的不等式：

\begin{array}{c} \mathbb{P}(\bar{X}-\mathbb{E}[\bar{X}] \geq t) \leq \exp \left(-\frac{2 t^{2} n^{2}}{\sum_{i=1}^{n}\left(b_{i}-a_{i}\right)^{2}}\right) \\ \mathbb{P}(|\bar{X}-\mathbb{E}[\bar{X}]| \geq t) \leq 2 \exp \left(-\frac{2 t^{2} n^{2}}{\sum_{i=1}^{n}\left(b_{i}-a_{i}\right)^{2}}\right) \end{array}

伯努利随机变量的特例

假定一个硬币A面朝上的概率为p, 则B面朝上的概率为1−p. 抛n次硬币, A面朝上次数的期望值为n∗p. 则A面朝上的次数不超过k次的概率为：

\begin{aligned} P(H(n) \leq k) &=\sum_{i=0}^{k} C_{n}^{i} p^{i}(1-p)^{n-i} \\ &=\sum_{i=0}^{k} \frac{n !}{i !(n-i) !} p^{i}(1-p)^{n-i} \end{aligned}

H(n)为抛n次硬币A面朝上的次数

对某一ε>0当k=(p−ε)n 时, 有Hoeffding不等式

P(H(n) \leq(p-\varepsilon) n) \leq e^{-2 \varepsilon^{2} n}

对应的, 当k=(p+ε)n 时，

P(H(n) \geq(p+\varepsilon) n) \leq e^{-2 \varepsilon^{2} n}

由此可得

P((p-\varepsilon) n \leq H(n) \leq(p+\varepsilon) n) \geq 1-2 e^{-2 \varepsilon^{2} n}

利用式(9)可推式(3)

式(3)的1−ϵ相当于式(9)的p , 令H(n)为基分类器分类正确的数量, 有

P(H(x) \neq f(x))=P\left(H(n) \leq\left\lfloor\frac{T}{2}\right\rfloor\right)

总分类器的数量为T(就是n), 令\frac{T}{2}=(1-\epsilon-\epsilon) T , 可推得\epsilon=\frac{1}{2}-\epsilon , 根据式(9)可得

\begin{aligned} P\left(H(n) \leq\left\lfloor\frac{T}{2}\right\rfloor\right) & \leq \exp \left(-2\left(\epsilon-\frac{1}{2}\right)^{2} T\right) \\ &=\exp \left(-2\left(\epsilon^{2}+\frac{1}{4}-\epsilon\right) T\right) \\ &=\exp \left(-\frac{T}{2}\left(4 \epsilon^{2}+1-4 \epsilon\right)\right) \\ &=\exp \left(-\frac{1}{2} T(1-2 \epsilon)^{2}\right) \end{aligned} 便得到式(3)得最终不等式形式