前情回顧
機(jī)器學(xué)習(xí)100天|Day1數(shù)據(jù)預(yù)處理
100天搞定機(jī)器學(xué)習(xí)|Day2簡單線性回歸分析
100天搞定機(jī)器學(xué)習(xí)|Day3多元線性回歸
100天搞定機(jī)器學(xué)習(xí)|Day4-6 邏輯回歸
100天搞定機(jī)器學(xué)習(xí)|Day7 K-NN
100天搞定機(jī)器學(xué)習(xí)|Day8 邏輯回歸的數(shù)學(xué)原理
100天搞定機(jī)器學(xué)習(xí)|Day9-12 支持向量機(jī)
100天搞定機(jī)器學(xué)習(xí)|Day11 實(shí)現(xiàn)KNN
100天搞定機(jī)器學(xué)習(xí)|Day13-14 SVM的實(shí)現(xiàn)
100天搞定機(jī)器學(xué)習(xí)|Day15 樸素貝葉斯
100天搞定機(jī)器學(xué)習(xí)|Day16 通過內(nèi)核技巧實(shí)現(xiàn)SVM
100天搞定機(jī)器學(xué)習(xí)|Day17-18 神奇的邏輯回歸
100天搞定機(jī)器學(xué)習(xí)|Day19-20 加州理工學(xué)院公開課：機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘
Day17，Avik-Jain第22天完成Yaser Abu-Mostafa教授的Caltech機(jī)器學(xué)習(xí)課程-CS156中的課程2。
1 Hoeffding不等式
假設(shè)有一個(gè)罐子裝滿了橙色和綠色的球，為了估計(jì)罐子中橙色和綠色的比例，我們隨機(jī)抓一把球，稱為樣本：
其中，設(shè)罐子中橙色球的比例為μ，樣本中橙色球比例為v，樣本的大小為N，我們對真實(shí)分布μ和樣本分布v的差異容忍度為ε，則有下面的不等式成立：
也就是存在一個(gè)概率上界，只要我們保證樣本容量N很大，就能使得“μ和v的差異大”這件事的概率是很小的。
2 對于一個(gè)假設(shè)函數(shù)h的情況
如果我們的假設(shè)函數(shù)h已經(jīng)確定了，那么我們可以這樣把我們的問題對應(yīng)到罐子模型：每個(gè)球表示一個(gè)輸入x，橙色表示h與真實(shí)的函數(shù)f預(yù)測的值不相同，綠色表示相同，即：
那么罐子中的所有球就是所有可能的輸入x，而抓的一把球表示我們的訓(xùn)練集（注意！這里其實(shí)是做了一個(gè)假設(shè)：我們的訓(xùn)練集和測試集都由同一個(gè)未知的概率分布P來產(chǎn)生，也就是來源于同一個(gè)罐子），那么橙色球占的比例μ就表示我們的假設(shè)函數(shù)h在真正的輸入空間中的預(yù)測錯誤率Eout（我們最后想要降低的），v就表示我們在訓(xùn)練集中的預(yù)測錯誤率Ein(我們的算法能最小化的)，由Hoeffding不等式，就能得到：
也就是說，只要我們能保證訓(xùn)練集的量N足夠大，就能保證訓(xùn)練集的錯誤率與真實(shí)的預(yù)測錯誤率是有很大概率接近的。
3 對于有限多個(gè)h的情況
上面一節(jié)我們證明了，對于一個(gè)給定的假設(shè)函數(shù)h，只要訓(xùn)練集足夠大，我們能保證它在訓(xùn)練集上的預(yù)測效果與真正的預(yù)測效果很大概率是接近的。但是，我們只能保證它們的預(yù)測效果接近，也可能預(yù)測效果都是壞呢？
我們的機(jī)器學(xué)習(xí)算法是在假設(shè)空間里面選一個(gè)h，使得這個(gè)h在訓(xùn)練集上錯誤率很小，那么這個(gè)h是不是在整個(gè)輸入空間上錯誤率也很小呢？這一節(jié)我們要證明的就是，對于假設(shè)空間只有有限個(gè)h時(shí)，只要訓(xùn)練集N足夠大，這也是很大概率成立的。
首先我們來看這張表：
首先，對于一個(gè)給定的h，我們可以定義一個(gè)概念：“壞的訓(xùn)練集”（對應(yīng)于表中紅色的bad）。所謂壞的訓(xùn)練集，就是h在這個(gè)訓(xùn)練集上面的Ein和真實(shí)的Eout的差異超過了我們定義的容忍度ε。Hoeffding不等式保證了，對于一個(gè)給定的h（表中的一行），選到壞的訓(xùn)練集的概率是很低的。
然后，對于假設(shè)空間里面有M個(gè)候選的h，我們重新定義“壞的訓(xùn)練集”的概念（對應(yīng)于表中橙色的bad）,只要它對于任何一個(gè)h是壞的，那么它就是一個(gè)壞的。那么我們選到橙色壞的訓(xùn)練集的概率可以如下推導(dǎo)：
由于M是有限的，只要訓(xùn)練集N足夠大，我們選到壞訓(xùn)練集的概率仍然是很小的。也就是說，我們的訓(xùn)練集很大可能是一個(gè)好的訓(xùn)練集，所有的h在上面都是好的，算法只要選取一個(gè)在訓(xùn)練集上表現(xiàn)好的h，那么它的預(yù)測能力也是PAC好的。也就是有不等式：
因此機(jī)器學(xué)習(xí)過程如下圖：
（這里多出來的橙色部分表示，訓(xùn)練集和測試集是由同一個(gè)概率分布產(chǎn)生的）
因此當(dāng)有限個(gè)h的情況下，機(jī)器學(xué)習(xí)算法確實(shí)是能學(xué)到東西的。
之后我們會討論，當(dāng)假設(shè)空間存在無限個(gè)h時(shí)，機(jī)器學(xué)習(xí)是否還有效。
上一節(jié)我們證明了，當(dāng)假設(shè)空間的大小是M時(shí)，可以得到概率上界：
即，只要訓(xùn)練數(shù)據(jù)量N足夠大，那么訓(xùn)練集上的Ein與真實(shí)的預(yù)測錯誤率Eout是PAC（大概率）接近的。
但是，我們上面的理論只有在假設(shè)空間大小有限時(shí)才成立，如果假設(shè)空間無限大，右邊的概率上界就會變成無限大。
事實(shí)上，右邊的邊界是一個(gè)比較弱的邊界，這一節(jié)我們要找出一個(gè)更強(qiáng)的邊界，來證明我們的機(jī)器學(xué)習(xí)算法對于假設(shè)空間無限大的情形仍然是可行的。我們將會用一個(gè)m來代替大M，并且證明當(dāng)假設(shè)空間具有break point時(shí)，m具有N的多項(xiàng)式級別的上界。
2 成長函數(shù)
對于一組給定的訓(xùn)練集x1,x2,...,xN。定義函數(shù)H(x1，x2，......，xN)，表示使用假設(shè)空間H里面的假設(shè)函數(shù)h，最多能把訓(xùn)練集劃分成多少種圈圈叉叉組合（即產(chǎn)生多少種Dichotomy，最大是2^N）。
例如，假設(shè)空間是平面上的所有線，訓(xùn)練數(shù)據(jù)集是平面上的N個(gè)點(diǎn)，則有：
N = 1 時(shí)，有2種劃分方式：
N = 2時(shí)，有4種劃分方式：
N = 3 時(shí)， 有8種劃分方式：
N = 4時(shí)，有14種劃分方式（因?yàn)橛袃煞N是不可能用一條直線劃分出來的）：
…………
另外，劃分?jǐn)?shù)與訓(xùn)練集有關(guān)，（例如N=3時(shí)，如果三個(gè)點(diǎn)共線，那么有兩種劃分就不可能產(chǎn)生，因此只有6種劃分而不是8種）：
為了排除對于訓(xùn)練數(shù)據(jù)的依賴性，我們定義成長函數(shù)：
因此，成長函數(shù)的意義就是：使用假設(shè)空間H， 最多有多少種對訓(xùn)練集（大小為N）的劃分方式。成長函數(shù)只與兩個(gè)因素有關(guān)：訓(xùn)練集的大小N，假設(shè)空間的類型H。
下面列舉了幾種假設(shè)空間的成長函數(shù)：
3 break point
這里我們定義break point。所謂break point，就是指當(dāng)訓(xùn)練集的大小為k時(shí)，成長函數(shù)滿足：
即假設(shè)空間所不能shatter的訓(xùn)練集容量。
容易想到，如果k是break point，那么k + 1, k + 2....也是break point。
4 成長函數(shù)的上界
由于第一個(gè)break point會對后面的成長函數(shù)有所限制，于是我們定義上界函數(shù)B(N,k)，表示在第一個(gè)break point是k的限制下，成長函數(shù)mH(N)的最大可能值：
現(xiàn)在我們開始推導(dǎo)這個(gè)上界函數(shù)的上界：
首先，B(N,k)產(chǎn)生的Dichotomy可以分為兩種類型，一種是前N-1個(gè)點(diǎn)成對的出現(xiàn)，一種是前N-1個(gè)點(diǎn)只出現(xiàn)一次：
因此顯然有：
然后，對于前N-1個(gè)點(diǎn)在這里產(chǎn)生的所有情況：
顯然這里的個(gè)數(shù)就是α+β，顯然，這前N-1個(gè)點(diǎn)產(chǎn)生的Dichotomy數(shù)仍然要受限于break point是k這個(gè)前提，因此：
然后，對于成對出現(xiàn)的Dichotomy的前N-1個(gè)點(diǎn)：
我們可以說，這里的前N-1個(gè)點(diǎn)將會受限于break point是k-1。反證法：如果這里有k-1個(gè)點(diǎn)是能夠shatter的，那么配合上我們的第N個(gè)點(diǎn)，就能找出k個(gè)點(diǎn)能shatter，這與B(N,k)的定義就矛盾了。因此我們有：
綜合上面，我們有：
利用這個(gè)遞推關(guān)系以及邊界情形，我們可以用數(shù)學(xué)歸納法簡單證明得到（事實(shí)上可以證明下面是等號關(guān)系）：
因此成長函數(shù)具有多項(xiàng)式級別的上界。
5 VC-Bound
這里我們不涉及嚴(yán)格的數(shù)學(xué)證明，而是用一種通俗化的方法來引出VC-Bound。也就是如何用m來替換M。
于是我們就得到了機(jī)器學(xué)習(xí)問題的PAC概率上界，稱為VC-Bound：
因此我們得到了更強(qiáng)的邊界，當(dāng)右邊的成長函數(shù)具有break point時(shí)，它的上界是N^k-1級別的，只要我們的N足夠大，“存在一個(gè)假設(shè)函數(shù)h使得壞情況發(fā)生”這件事的幾率就會很小。
6 結(jié)論
結(jié)論：當(dāng)假設(shè)空間的成長函數(shù)具有break point時(shí)，只要N足夠大，我們能PAC地保證訓(xùn)練集是一個(gè)好的訓(xùn)練集，所有h在上面的Ein和Eout都是近似的，算法可以對這些h做自由選擇。也就是機(jī)器學(xué)習(xí)算法確實(shí)是能work的。
通俗的說，機(jī)器學(xué)習(xí)能work的條件：
1 好的假設(shè)空間。使得成長函數(shù)具有break point。
2 好的訓(xùn)練數(shù)據(jù)集。使得N足夠大。
3 好的算法。使得我們能選擇在訓(xùn)練集上表現(xiàn)好的h。
4 好的運(yùn)氣。因?yàn)檫€是有一定小概率會發(fā)生壞情況。
END
本文轉(zhuǎn)自：
https://www.cnblogs.com/coldyan/
