0 引言
霍夫丁不等式是統計學家
霍夫丁在1963年提出并證明,霍夫丁不等式給出了随機變量的和與其期望值偏差的機率上限,通過它可以推導出機器學習在理論上的可行性[1]。關于霍夫丁不等式的推導,不得不提到"三駕馬車"(馬爾科夫、切比雪夫、切爾諾夫),如下圖所示[2],通過對以上三個不等式的推導來引出霍夫丁不等式的推導。
霍夫丁不等式推導過程
1 馬爾科夫不等式的推導
2 切比雪夫不等式的推導
3 切爾諾夫不等式的推導
4 霍夫丁不等式的推導
4.1 霍夫丁不等式
4.2 霍夫丁不等式的推導
以上推導過程的參考自[3]
參考
- ^https://zhuanlan.zhihu.com/p/45342697
- ^https://blog.csdn.net/liubai01/article/details/79947975
- ^http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/03_hoeffding.pdf