天天看點

hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導

0 引言

霍夫丁不等式是統計學家

霍夫丁

在1963年提出并證明,霍夫丁不等式給出了随機變量的和與其期望值偏差的機率上限,通過它可以推導出機器學習在理論上的可行性[1]。關于霍夫丁不等式的推導,不得不提到"三駕馬車"(馬爾科夫、切比雪夫、切爾諾夫),如下圖所示[2],通過對以上三個不等式的推導來引出霍夫丁不等式的推導。

hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導

霍夫丁不等式推導過程

1 馬爾科夫不等式的推導

hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導

2 切比雪夫不等式的推導

hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導

3 切爾諾夫不等式的推導

hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導

4 霍夫丁不等式的推導

4.1 霍夫丁不等式

hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導

4.2 霍夫丁不等式的推導

hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導
hoeffding不等式_霍夫丁不等式(Hoeffding Inequality)的推導

以上推導過程的參考自[3]

參考

  1. ^https://zhuanlan.zhihu.com/p/45342697
  2. ^https://blog.csdn.net/liubai01/article/details/79947975
  3. ^http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/03_hoeffding.pdf