為什么機器學(xué)習(xí)真的可以學(xué)到東西

開始跟《機器學(xué)習(xí)基石》這門課，相對于Stanford那門課，這門明顯難度大很多，我跟到第10個Lecture，才剛剛講到Logistic Regression。前面費了很大力氣在講機器什么時候可以學(xué)習(xí)，以及證明為什么能學(xué)習(xí)。

此文主要是基于《機器學(xué)習(xí)基石》的學(xué)習(xí)筆記。Topic是為什么機器可以學(xué)習(xí)？

機器學(xué)習(xí)流程

下面是一個粗略的機器學(xué)習(xí)流程圖

機器學(xué)習(xí)最開始也是最終的目的是獲得一個target function，喂進去數(shù)據(jù)能直接得到正確結(jié)論的函數(shù)。為了得到這個函數(shù)，我們需要一大堆的訓(xùn)練數(shù)據(jù)。然后通過一個好的機器學(xué)習(xí)算法，從一大堆可能的function(也就是H)中挑選一個比較好的function(也就是g)，這個g和target function長得越像越好。

Hoeffding’s inequality

大家有沒有想過，為什么這樣就能學(xué)到東西。我們的算法只是在訓(xùn)練數(shù)據(jù)上跑，從訓(xùn)練數(shù)據(jù)跑出來的g，我們怎么能確定它也能在測試數(shù)據(jù)上跑的很好呢？這個就是問題的關(guān)鍵。其實接下來內(nèi)容主要就是論證這個問題。

先來考慮一個簡單的問題。比如說我們現(xiàn)在有一個黑罐子，里面有很多彈珠，只有兩種顏色，黃的和綠的。好現(xiàn)在問你，你怎么能知道黃色彈珠大概有多少顆？

大家肯定都會說抽樣。沒錯，我們抽出10個彈珠，很容易能知道黃色彈珠在sample中的比例。但是這個比例真的能代表罐子中的比例嗎？也許能，也許不能。而且能的記錄會隨著我們sample數(shù)目的增大而增大。但是也有可能你抓出一把全綠。但這種情況發(fā)生的記錄很小。這里我們有一個定理保證這種偏差發(fā)生的記錄很小。

Hoeffding's inequality可以保證偏差很大發(fā)生的幾率很小，并且隨著N的增大很減小。公式如下，v代表sample中黃色彈珠的比例，μ表示罐子中黃色彈珠的比例。?也就是偏差。

壞事的發(fā)生

現(xiàn)在我們稱v為Ein,μ為Eout，現(xiàn)在我們已經(jīng)證明了Ein和Eout不會差的太遠，更重要的事情是保重Ein越小越好，這就需要一個好的算法。
還記得上面的學(xué)習(xí)流程嗎，我們的算法是從很多個h中去挑選一個Ein最小的h讓它成為g。但是這里會有壞事情發(fā)生。
所謂的壞事情就是bad sample，就是說我們抽出了十個全是綠的彈珠?，F(xiàn)在有一個好的h稱之為h1，和壞的h叫h2，h1對于這個bad sample的表現(xiàn)當然是糟糕的，而恰好h2表現(xiàn)很好，那h2就被選成g了。

當出現(xiàn)壞事的時候，我們學(xué)習(xí)就會困難，可以直接說不能學(xué)習(xí)。所以這個壞事出現(xiàn)的概率是多少呢？把所有h中發(fā)生壞事的幾率加起來。

從上圖的式子中可以看到，壞事發(fā)生的幾率和M有關(guān)。M也就是h的個數(shù)。
從現(xiàn)在的條件來看，如果M很大甚至無線的話那么Learning是不可行的。

無效的Hypothesis

真實的情況是M一般不會很大，請再仔細看看上一張圖的推導(dǎo)，M是通過把所有的h壞事發(fā)生的概率加起來的，但是其實這些h不是互相獨立的。所以這些h是有重復(fù)的，如下圖。

比如說，我們想學(xué)習(xí)的target function是一條把x1分類成正負的線?，F(xiàn)在h就有無數(shù)個，因為任意一條線都能分類，但是實際有意義的只有兩種，分成正的和負的。
如果是兩個點的話，實際有效的h就有4種，但是3個點就有可能不到8種了，因為會出現(xiàn)三點共線的情況。4個點的話按理說有16種，但是同樣有一種情況不會發(fā)生，請看下圖。

所以現(xiàn)在我們的公式就變成了這樣，大大減小M的個數(shù)

成長函數(shù)的上限

現(xiàn)在我們給上面effective(N)一個稱呼，叫做成長函數(shù)。也就是說，對于某一個輸入D，H最多能夠產(chǎn)生的多少種方程。注意是種類的數(shù)量。
這個所謂的種類我們也給一個定義叫做dichotomy,用來表示H對與D的二元分類情況。
好，現(xiàn)在問題的關(guān)鍵，就是H到底能把D分成多少個dichotomy。也就是它的成長函數(shù)到底是多少？
但是我們很難確定它的成長函數(shù)。但是好在我們擁有一個叫做break point的東西，這就是成長函數(shù)的上限。我們再看回上面分類的例子。

1. 一個點能分成兩種
2. 兩個點分成四種
3. 三個點分成六種或者八種
4. 四個點只有14種(break point)

這里的輸入為三個點就是一個break point。也就是說當輸入N個點，H不能夠把這個N個點的排列組合全部表示出來時(2^N)，N就是一個break point。
當H能把N的全部組合表示出來時，說明這N個點被H給shatter掉了

我們用B(N,k)來表示當輸入N個點時，H可以最多產(chǎn)生多少個dichotomy。
通過數(shù)學(xué)歸納法我們可以證明到

VC BOUND

現(xiàn)在到了最后一步，除了把上邊那個成長函數(shù)的上限代入進去之外，還需要進行一系列的變形，這些變形需要很強的數(shù)學(xué)能力和概率上面的知識，我自己都不太懂，況且我覺得大部分人都不需要了解。這里我就略過，有興趣的強人自己google咯。
最終的式子如下

好了，現(xiàn)在我們終于能說機器學(xué)習(xí)確實可以學(xué)到東西了。但是需要滿足三個條件。

1. 有一個好的H(擁有break point)
2. 足夠多的數(shù)據(jù)
3. 好的算法，能夠使Ein足夠小

這三者的關(guān)系如下圖。

dvc = k - 1，大致上可以把它看出theta的維度加1

上圖很清晰的說明，并不是說你的模型搞得很復(fù)雜，算法弄得很好，就能學(xué)好，反而是取到一個折中的點，這樣的學(xué)習(xí)才最有效。