引言
機率、統計和機器學習中的一個基本問題是:給定一個期望為
hoeffding不等式_統計學習--詳解Hoeffding不等式 的随機變量
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,
hoeffding不等式_統計學習--詳解Hoeffding不等式 接近其期望的可能性有多大?更準确地說，它有多接近?
為了解決這個問題，我們可以使用一些工具來計算邊界：
hoeffding不等式_統計學習--詳解Hoeffding不等式 Hoeffding不等式 是一種強大的技巧——也許是學習理論中最重要的不等式——用于
限定有界随機變量和 過大或過小的機率。
幾個需要使用到的命題
馬爾可夫不等式 Markov’s inequality
假設
hoeffding不等式_統計學習--詳解Hoeffding不等式 是一個非負的随機變量:
hoeffding不等式_統計學習--詳解Hoeffding不等式 證明如下:
hoeffding不等式_統計學習--詳解Hoeffding不等式 切比雪夫不等式 Chebyshev’s inequality 假設
hoeffding不等式_統計學習--詳解Hoeffding不等式 是任何均方差
hoeffding不等式_統計學習--詳解Hoeffding不等式 :
hoeffding不等式_統計學習--詳解Hoeffding不等式 均方差 hoeffding不等式_統計學習--詳解Hoeffding不等式
證明可以使用馬爾可夫不等式：
hoeffding不等式_統計學習--詳解Hoeffding不等式 我們可以考慮一種特殊情況，
hoeffding不等式_統計學習--詳解Hoeffding不等式 。此時我們定義
hoeffding不等式_統計學習--詳解Hoeffding不等式 ，則有如下不等式關系：
hoeffding不等式_統計學習--詳解Hoeffding不等式 矩量母函數MGF 在統計學中，矩又被稱為
動差 (Moment)。
矩量母函數 (Moment Generating Function,簡稱mgf)又被稱為
動差生成函數 。
我們稱
hoeffding不等式_統計學習--詳解Hoeffding不等式 的數學期望為随機變量ξ的矩量母函數，記作
hoeffding不等式_統計學習--詳解Hoeffding不等式 .
連續型随機變量ξ的MGF為：
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,積分區間為(-∞,+∞)，f(x)為ξ的機率密度函數。
離散型随機變量ξ的MGF為：
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,其中連加号代表對ξ的所有取值連加，p(ξ=x)為ξ的機率分布函數。
矩量母函數 存在當且僅當 上述積分(連加)極限存在。
MGF的定義引用自百度百科。
矩量母函數的例子 下面将給出幾個矩量母函數的例子，并且會衍生出一些偏差不等式。
我們使用如下形式的邊界：
hoeffding不等式_統計學習--詳解Hoeffding不等式 .
C的大小依賴于Z的分布。
首先，拿經典的正态分布做例子：
hoeffding不等式_統計學習--詳解Hoeffding不等式 第二個例子：
Rademacher随機變量 (随機信号變量)。
關于Rademacher分布的機率密度函數為如下:
hoeffding不等式_統計學習--詳解Hoeffding不等式 hoeffding不等式_統計學習--詳解Hoeffding不等式 對于不等式1),我們可以使用
泰勒展開 将指數函數展開：
hoeffding不等式_統計學習--詳解Hoeffding不等式 值得注意的是，對于随機信号變量，當k為奇數時，
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,當k為偶數時，
hoeffding不等式_統計學習--詳解Hoeffding不等式 .
是以得到：
hoeffding不等式_統計學習--詳解Hoeffding不等式 而對于任意自然數k,有不等式
hoeffding不等式_統計學習--詳解Hoeffding不等式 成立，是以：
hoeffding不等式_統計學習--詳解Hoeffding不等式 如果我們有Z為Rademacher分布：
hoeffding不等式_統計學習--詳解Hoeffding不等式 ，其中
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,則
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,于是結合切爾諾夫界，我們可以立即得到如下不等式：
hoeffding不等式_統計學習--詳解Hoeffding不等式 由上式知，要是的
hoeffding不等式_統計學習--詳解Hoeffding不等式 達到最小，隻需要找到
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,使得：
hoeffding不等式_統計學習--詳解Hoeffding不等式 可以對上式關于
hoeffding不等式_統計學習--詳解Hoeffding不等式 求偏導，得到
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,代入2)中最後可以得到:
hoeffding不等式_統計學習--詳解Hoeffding不等式 如果我們令
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,可以得到更加簡化的形式：
hoeffding不等式_統計學習--詳解Hoeffding不等式 于是有
hoeffding不等式_統計學習--詳解Hoeffding不等式 有非常高的機率使得n個獨立随機符号的和基本上不大于
hoeffding不等式_統計學習--詳解Hoeffding不等式 .
切爾諾夫邊界 Chernoff bounds 我們定義Z的矩量母函數：
hoeffding不等式_統計學習--詳解Hoeffding不等式 。
切爾諾夫邊界使用矩量母函數(Moment generating functions)作為一種必要的方法來給出
指數偏差界限 。
對于随機變量Z,
hoeffding不等式_統計學習--詳解Hoeffding不等式 同樣該式可以使用馬爾可夫不等式進行證明：
hoeffding不等式_統計學習--詳解Hoeffding不等式 切爾諾夫不等式(切爾諾夫界)由于有了矩量母函數，是以對求和非常友好。我們假設
hoeffding不等式_統計學習--詳解Hoeffding不等式 都是獨立的，可以得到如下等式：
hoeffding不等式_統計學習--詳解Hoeffding不等式 如此意味着，當我們要計算一些
獨立同分布 變量和的切爾諾夫界時，我們隻需要計算這些變量中的
一個 的矩量母函數。
假設
hoeffding不等式_統計學習--詳解Hoeffding不等式 都是i.i.d,并且為了簡化，假設均值為0，可以得到：
hoeffding不等式_統計學習--詳解Hoeffding不等式 大數定理
我們可以由切比雪夫不等式直接推得大數定理。
設随機變量
hoeffding不等式_統計學習--詳解Hoeffding不等式 互相獨立，并且具有相同的期望
hoeffding不等式_統計學習--詳解Hoeffding不等式 和方差
hoeffding不等式_統計學習--詳解Hoeffding不等式 .對于前n個随機變量的平均
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,則有任意正數
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,有：
hoeffding不等式_統計學習--詳解Hoeffding不等式 hoeffding不等式_統計學習--詳解Hoeffding不等式 大數定理說明當n很大時，随機變量
hoeffding不等式_統計學習--詳解Hoeffding不等式 的平均值
hoeffding不等式_統計學習--詳解Hoeffding不等式 在機率意義下無限接近于期望
hoeffding不等式_統計學習--詳解Hoeffding不等式 .
而對于統計學習中一個重要概念——
PAC: 對于非常大的N時，有
hoeffding不等式_統計學習--詳解Hoeffding不等式 幾乎相對正确 (probably approxiamtely correct. PAC) :
hoeffding不等式_統計學習--詳解Hoeffding不等式 霍夫丁引理及霍夫丁不等式
Theorem(Hoeffding's inequality). 假設一系列随機有界獨立變量:
hoeffding不等式_統計學習--詳解Hoeffding不等式 , 有:
hoeffding不等式_統計學習--詳解Hoeffding不等式 Lemma 霍夫丁引理(Hoeffding's lemma):
假設随機有界變量
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,有：
hoeffding不等式_統計學習--詳解Hoeffding不等式 我們結合
切爾諾夫界 和霍夫丁引理即可以證明霍夫丁不等式。
重頭戲 為證明霍夫丁不等式，我們先證明霍夫丁引理的一個弱化形式:
hoeffding不等式_統計學習--詳解Hoeffding不等式 引入
延森不等式 (Jensen's inequality)
Jensen不等式在EM算法中也起到非常大的作用。
Jensen不等式内容如下：
如果實數域上的映射
hoeffding不等式_統計學習--詳解Hoeffding不等式 是一個
凸函數 (convex function),即意味着f是一個碗狀函數，則有：
hoeffding不等式_統計學習--詳解Hoeffding不等式 可以結合高等數學或者數學分析學習的凸函數形狀來記憶了解。常見的凸函數如 hoeffding不等式_統計學習--詳解Hoeffding不等式 .
我們将使用一個在機率論、機器學習和統計中常用的技巧
對稱化 來給出結果。
令 Z' 為一個和Z擁有相同分布的獨立複制變量，于是：
hoeffding不等式_統計學習--詳解Hoeffding不等式 現在我們可以得到如下不等式：
hoeffding不等式_統計學習--詳解Hoeffding不等式 hoeffding不等式_統計學習--詳解Hoeffding不等式 為`E,E'`的期望值。
不等式中的步驟(i)是對函數
hoeffding不等式_統計學習--詳解Hoeffding不等式 使用Jensen不等式的結果，即有：
hoeffding不等式_統計學習--詳解Hoeffding不等式 注意到 Z-Z' 是關于
零對稱 的，于是如果S是一個随機信号變量，則有 S(Z-Z') 和 Z-Z' 具有相同的分布情況，即 S(Z-Z') 與 Z-Z' 同正同負，故：
hoeffding不等式_統計學習--詳解Hoeffding不等式 關于這個等式的意義，我還有些許疑惑，望評論區大佬指點。
有了上述準備後，我們可以根據随機信号函數的矩量母函數的 不等式 1) 給出如下不等式：
hoeffding不等式_統計學習--詳解Hoeffding不等式 又由于假設
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,于是
hoeffding不等式_統計學習--詳解Hoeffding不等式 ,即有
hoeffding不等式_統計學習--詳解Hoeffding不等式 , 聯立4)式有：
hoeffding不等式_統計學習--詳解Hoeffding不等式 這樣我們就證明了霍夫丁引理的弱化式3). :)
堅持，馬上就到底了！
接下來開始證明
霍夫丁不等式 ：
我們隻需證明第一個不等式(第二種證明類似)：
hoeffding不等式_統計學習--詳解Hoeffding不等式 這裡步驟(i)使用到了 霍夫丁引理.
結合上文矩量母函數中求Rademacher分布機率最小的方法,我們可以求得該情況下的機率上界：
hoeffding不等式_統計學習--詳解Hoeffding不等式 Q.E.D.
參考文獻Reference [1] 斯坦福大學課堂講義:CS229 Supplemental Lecture notes: Hoeffding’s inequality
[2] Rademacher distribution
