引入
在上一小節(jié)"理解為什么機器可以學習——PAC學習模型"中，我們主要討論了假設(shè)的錯誤率問題和如何說一個學習器是可學習的，并給出了PAC學習理論悍汛。這一小節(jié)今妄，我們將沿著這個方向，討論一下戒幔，有限假設(shè)空間的樣本復雜度，并用Hoeffding不等式來界定概率邊界。
假設(shè)空間的樣本復雜度
PAC可學習性很大程度上由所需的訓練樣本數(shù)量決定浩习。隨著問題規(guī)模的增長所帶來的所需訓練樣本的增長稱為學習問題的樣本復雜度（sample complexity）。在多數(shù)實際問題中济丘，最限制學習器成功的因素是有限的可用的訓練數(shù)據(jù)谱秽。
我們通常都喜歡能與訓練數(shù)據(jù)擬合程度更高的假設(shè)，當一個學習器在可能時都輸出能完美擬合訓練數(shù)據(jù)的假設(shè)時摹迷，我們稱該學習器是一致的（consistent）疟赊。這就要求訓練錯誤率是0。
遺憾的是峡碉，如果假設(shè)空間里不總是能找到一個零錯誤率的假設(shè)近哟，這時，最多能要求學習器輸出的假設(shè)在訓練數(shù)據(jù)上有最小的錯誤率鲫寄。
在更一般的情形下吉执，我們要考慮學習器有非零訓練錯誤率的假設(shè)時疯淫，仍能找到一個邊界來限定學習器所需的樣本數(shù)量。
Hoeffding邊界
描述問題
現(xiàn)在戳玫，我們來更準確的描述我們要解決的問題峡竣。
令D代表學習器可觀察的特定的訓練數(shù)據(jù)集合，而P代表整個數(shù)據(jù)集合背后滿足的概率分布量九。令Ein(h)代表假設(shè)h的訓練錯誤率（在機器學習基石課程中适掰，該錯誤率被稱為in-sample error），確切的說荠列，Ein(h)是數(shù)據(jù)集D中被h誤分類的訓練數(shù)據(jù)所占比例类浪，Ein(h)是定義在訓練數(shù)據(jù)集D上的，而真實錯誤率Eout(h)（out-of-sample error）是定義在整個概率分布P上的〖∷疲現(xiàn)在令g代表H中有最小訓練錯誤率的假設(shè)费就。問：多少訓練數(shù)據(jù)才足以保證真實錯誤率Eout(h)和訓練錯誤率Ein(h)很接近，并且接近0川队。
Hoeffding不等式
Hoeffding刻畫的是某個事件的真實概率及其m個獨立重復試驗中觀察到的頻率之間的差異力细，更準確的將，它是應用于m個不同的Bernoulli試驗固额。
該不等式給出了一個概率邊界眠蚂，它說明任意選擇的假設(shè)訓練錯誤率不能代表真實情況。
確認（verification）流程
我們發(fā)現(xiàn)滿足上面給的邊界不等式的h可不可以說它是一個好的學習器呢斗躏？當然不能逝慧，上面的不等式只能說明h的訓練錯誤率和真實錯誤率很接近啄糙，但卻不一定是最小的笛臣，即h不一定是最佳的假設(shè)隧饼。所以，這只是對一個假設(shè)做確認的過程燕雁。
這里因為只有一個hypothesis在手上，所以我們還不能做選擇贵白，但是我們可以給它一些verifying examples來讓它做確認率拒，看看h的表現(xiàn)如何禁荒，正如上圖流程所示。
有限假設(shè)空間的錯誤率的概率邊界
Hoeffding不等式告訴我們什么呢呛伴？較好擬合訓練數(shù)據(jù)的假設(shè)與該假設(shè)針對整個數(shù)據(jù)集合的預測勃痴，這兩者的錯誤率差別很大的那種情況發(fā)生的概率是很小的热康。
那么現(xiàn)在的問題是什么呢？如果在多個假設(shè)中姐军，其中一個假設(shè)針對訓練數(shù)據(jù)的輸出都是正確的铁材，那要不要選這個假設(shè)作為算法的輸出的假設(shè)呢？
帶著這個問題奕锌，我們先了解一下什么叫做不好的數(shù)據(jù)著觉。
Bad Sample and Bad Data
壞的樣本就是訓練錯誤率Ein=0，而真實錯誤率Eout=1/2的情況惊暴。
壞的數(shù)據(jù)是Ein和Eout差別很大的情況饼丘，通常Ein很小，Eout很大辽话。
而Hoeffding說明的是如果把所有的訓練數(shù)據(jù)（從輸入空間中肄鸽，隨機選取產(chǎn)生的數(shù)據(jù)的不同組合）窮舉出來，得到的不好的樣本（Bad Sample）的概率是很小的油啤。
所以壞的樣本就是讓算法的預測的準確率和訓練時的正確率差別很大的情況（Ein和Eout差別很大）典徘。
上圖說明：
- 對于一個假設(shè)hi（每一行），Hoeffding保證其不好的情況總體的概率是很小的
- 對于含有BAD的每一列來說益咬，只要有BAD烂斋，算法就無法從所有假設(shè)中自由做選擇
- 表中D1126這個數(shù)據(jù)集是好的數(shù)據(jù)
Bound of BAD Data
我們來算一下壞的數(shù)據(jù)的概率邊界：
這個式子是有限個假設(shè)的Hoeffding不等式。
對于這個式子來說础废，如果訓練數(shù)據(jù)的數(shù)量N夠大的話汛骂，那么能保證Ein和Eout差別很小。
統(tǒng)計學習流程
上面的流程總結(jié)了我們這篇文章討論的問題评腺，那就是如果現(xiàn)有有限個假設(shè)且訓練數(shù)據(jù)量夠多的情況下帘瞭，那么不管我們?nèi)绾芜x擇訓練數(shù)據(jù)，訓練錯誤率和真實錯誤率都會很接近蒿讥；我們設(shè)計算法來找一個Ein最小的蝶念，PAC理論就保證了Eout很小。這樣機器學習算法是有可能學到有用的知識的芋绸！
小結(jié)
我們至此討論的是有限個假設(shè)的情況媒殉，說明了機器學習算法可以做到一些事情。那么無限多假設(shè)的情況該是如何處理呢摔敛？我將在下一小節(jié)中介紹VC理論的有關(guān)知識廷蓉。
參考資料
機器學習， Tom M.Mitchell 马昙，機械工業(yè)出版社
機器學習基石課程桃犬，林軒田刹悴，臺灣大學
轉(zhuǎn)載請注明作者Jason Ding及其出處
Github主頁(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
