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

• 2019 年 11 月 29 日
• 笔记

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_36670529/article/details/103125058

考虑二分类问题

和真实函数

, 假定基分类器的错误率为

, 即对每个基分类器

有

(1)

假设集成通过简单投票法结合

个基分类器, 若有超过半数的基分类器正确, 则集成分类就正确:

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

(3)

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

(4)

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

(5)

满足以下的不等式：

(6),(7)

伯努利随机变量的特例

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

(8)

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

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

(9)

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

(10)

由此可得

(11)

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

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

(12)

总分类器的数量为T(就是n), 令

, 可推得

, 根据式(9)可得

(13)

便得到式(3)得最终不等式形式