沿著PAC學(xué)習(xí)理論，討論有限假設(shè)空間的樣本復(fù)雜度，并用Hoeffding不等式來界定概率邊界。

假設(shè)空間的樣本復(fù)雜度

PAC可學(xué)習(xí)性很大程度上由所需的訓(xùn)練樣本數(shù)量決定。隨著問題規(guī)模的增長所帶來的所需訓(xùn)練樣本的增長稱為學(xué)習(xí)問題的樣本復(fù)雜度（sample complexity）。在多數(shù)實際問題中，最限制學(xué)習(xí)器成功的因素是有限的可用的訓(xùn)練數(shù)據(jù)。

我們通常都喜歡能與訓(xùn)練數(shù)據(jù)擬合程度更高的假設(shè)，當(dāng)一個學(xué)習(xí)器在可能時都輸出能完美擬合訓(xùn)練數(shù)據(jù)的假設(shè)時，我們稱該學(xué)習(xí)器是一致的（consistent）。這就要求訓(xùn)練錯誤率是0。

遺憾的是，如果假設(shè)空間里不總是能找到一個零錯誤率的假設(shè)，這時，最多能要求學(xué)習(xí)器輸出的假設(shè)在訓(xùn)練數(shù)據(jù)上有最小的錯誤率。

在更一般的情形下，我們要考慮學(xué)習(xí)器有非零訓(xùn)練錯誤率的假設(shè)時，仍能找到一個邊界來限定學(xué)習(xí)器所需的樣本數(shù)量。

Hoeffding邊界

描述問題

現(xiàn)在，我們來更準(zhǔn)確的描述我們要解決的問題。

令D代表學(xué)習(xí)器可觀察的特定的訓(xùn)練數(shù)據(jù)集合，而P代表整個數(shù)據(jù)集合背后滿足的概率分布。令Ein(h)代表假設(shè)h的訓(xùn)練錯誤率（在機器學(xué)習(xí)基石課程中，該錯誤率被稱為in-sample error），確切的說，Ein(h)是數(shù)據(jù)集D中被h誤分類的訓(xùn)練數(shù)據(jù)所占比例，Ein(h)是定義在訓(xùn)練數(shù)據(jù)集D上的，而真實錯誤率Eout(h)（out-of-sample error）是定義在整個概率分布P上的?，F(xiàn)在令g代表H中有最小訓(xùn)練錯誤率的假設(shè)。問：多少訓(xùn)練數(shù)據(jù)才足以保證真實錯誤率Eout(h)和訓(xùn)練錯誤率Ein(h)很接近，并且接近0。

Hoeffding不等式

Hoeffding Inequality

Hoeffding刻畫的是某個事件的真實概率及其m個獨立重復(fù)試驗中觀察到的頻率之間的差異，更準(zhǔn)確的將，它是應(yīng)用于m個不同的Bernoulli試驗。

該不等式給出了一個概率邊界，它說明任意選擇的假設(shè)訓(xùn)練錯誤率不能代表真實情況。

確認(rèn)（verification）流程

我們發(fā)現(xiàn)滿足上面給的邊界不等式的h可不可以說它是一個好的學(xué)習(xí)器呢？當(dāng)然不能，上面的不等式只能說明h的訓(xùn)練錯誤率和真實錯誤率很接近，但卻不一定是最小的，即h不一定是最佳的假設(shè)。所以，這只是對一個假設(shè)做確認(rèn)的過程。

這里因為只有一個hypothesis在手上，所以我們還不能做選擇，但是我們可以給它一些verifying examples來讓它做確認(rèn)，看看h的表現(xiàn)如何，正如上圖流程所示。

有限假設(shè)空間的錯誤率的概率邊界

Hoeffding不等式告訴我們什么呢？較好擬合訓(xùn)練數(shù)據(jù)的假設(shè)與該假設(shè)針對整個數(shù)據(jù)集合的預(yù)測，這兩者的錯誤率差別很大的那種情況發(fā)生的概率是很小的。

那么現(xiàn)在的問題是什么呢？如果在多個假設(shè)中，其中一個假設(shè)針對訓(xùn)練數(shù)據(jù)的輸出都是正確的，那要不要選這個假設(shè)作為算法的輸出的假設(shè)呢？

帶著這個問題，我們先了解一下什么叫做不好的數(shù)據(jù)。

Bad Sample and Bad Data

壞的樣本就是訓(xùn)練錯誤率Ein=0，而真實錯誤率Eout=1/2的情況。

壞的數(shù)據(jù)是Ein和Eout差別很大的情況，通常Ein很小，Eout很大。

而Hoeffding說明的是如果把所有的訓(xùn)練數(shù)據(jù)（從輸入空間中，隨機選取產(chǎn)生的數(shù)據(jù)的不同組合）窮舉出來，得到的不好的樣本（Bad Sample）的概率是很小的。

所以壞的樣本就是讓算法的預(yù)測的準(zhǔn)確率和訓(xùn)練時的正確率差別很大的情況（Ein和Eout差別很大）。

上圖說明：

對于一個假設(shè)hi（每一行），Hoeffding保證其不好的情況總體的概率是很小的

對于含有BAD的每一列來說，只要有BAD，算法就無法從所有假設(shè)中自由做選擇

表中D1126這個數(shù)據(jù)集是好的數(shù)據(jù)

Bound of BAD Data

我們來算一下壞的數(shù)據(jù)的概率邊界：

這個式子是有限個假設(shè)的Hoeffding不等式。

對于這個式子來說，如果訓(xùn)練數(shù)據(jù)的數(shù)量N夠大的話，那么能保證Ein和Eout差別很小。

總結(jié)：如果現(xiàn)有有限個假設(shè)且訓(xùn)練數(shù)據(jù)量夠多的情況下，那么不管我們?nèi)绾芜x擇訓(xùn)練數(shù)據(jù)，訓(xùn)練錯誤率和真實錯誤率都會很接近；我們設(shè)計算法來找一個Ein最小的，PAC理論就保證了Eout很小。這樣機器學(xué)習(xí)算法是有可能學(xué)到有用的知識的！

————————————————

原文鏈接：https://blog.csdn.net/jasonding1354/java/article/details/41871733