為什么機器學習真的可以學到東西

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

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

機器學習流程

下面是一個粗略的機器學習流程圖

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

Hoeffding’s inequality

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

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

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

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

壞事的發生

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

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

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

無效的Hypothesis

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

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

所以現在我們的公式就變成了這樣，大大減小M的個數

成長函數的上限

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

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可以最多產生多少個dichotomy。
通過數學歸納法我們可以證明到

VC BOUND

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

好了，現在我們終于能說機器學習確實可以學到東西了。但是需要滿足三個條件。

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

這三者的關系如下圖。

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

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