《機器學習基石》課程學習總結（二）

作者：milter

原文鏈接：https://www.jianshu.com/p/2cded7baa802

查看更多的專業文章、課程信息、產品信息，請移步至「人工智慧LeadAI」公眾號，或移步至全新打造的官網：www.leadai.org.

正文共4333個字，15張圖，預計閱讀時間11分鐘。

01

尋找函數g的pocket演算法

前文提到，PLA演算法有效的前提是D要是線性可分的，D中的數據可以看做由f產生而來。這樣的假設過於理想化，現實中，D裡面總會摻雜一些雜訊數據（noise data），這些數據並不是從理想的f產生而來。

這些雜訊數據會帶來哪些影響？有了雜訊數據，D可能就不是線性可分了，PLA演算法也就不再有效，而且，即使D還是線性可分的，雜訊數據也會對最後選擇的g產生干擾，影響g與f的相似度。

怎麼解決雜訊數據帶來的干擾？

答案是對PLA演算法進行改進，不求對D中每一個數據都有g(X)=y=f(X),只求犯錯儘可能少的W_g，如下所示：

這個想法貌似不錯，很遺憾，找到這樣的W_g是一個NP-hard問題，所以我們只能退而求其次，找到一個我們自己感覺犯錯足夠少的W_g，這樣的演算法叫做Pocket演算法，偽代碼如下：

02

反思，機器真的可以學習嗎？

現在回顧一下我們目前了解的機器學習的過程：

演算法A利用D，從H中挑出一個最好的函數g，使得g儘可能地像f。

我們找函數g的標準是，使它在D上儘可能地像f，可是，我們怎麼知道這樣的函數g，在D之外的數據上也像f呢？

假如我們用E_in(g)表示

也就是函數g在D上犯錯誤的比例（與f不一致的比例）。可見，我們目前的演算法只是讓E_in(g)儘可能地接近0，也就是在D上使g和f很像。

我們用E_out(g)表示在D之外的數據上，g與f不一致的比例。假如我們能夠證明E_out(g)與E_in(g)大致相等，又可以使E_in(g)儘可能接近0，也就能夠使E_out(g)儘可能地接近0，此時，我們就可以自豪地說，我們找到的函數g確實與f很像！

現在，找最好的函數g實際上包含著兩個問題：

• 如何使E_in(g)儘可能小？
• 如何確保E_out(g)與E_in(g)大致相等

PLA和Pocket演算法都只專註解決第一個問題，第二個問題怎麼解決？答案是用數學來證明。

課程的第4,5,6,7課就是用來證明第二個問題的。本課程一共才16課，竟然用4課來證明一個問題，可見該問題的重要性。

為什麼這個問題如此重要？因為只有證明了這個問題，才能從根本上說清楚，為什麼機器可以學習，機器學習才能有堅實的理論基礎支撐。

通俗地講，假如你說，我可以用方法A來解決問題B，那麼，若要人信服你，僅僅說明怎麼用方法A來解決問題B是不夠的，你必須證明給別人看，為什麼方法A可以解決問題B，我們證明E_out(g)與E_in(g)大致相等就是解決機器學習中為什麼的問題。

下面我們簡單快速地瀏覽一下證明過程：

1、從簡單的抓彈珠受到的啟發

如圖所示，

一個罐子里裝了許多彈珠，有橙黃和綠兩種顏色，如何估計橙黃色彈珠佔總彈珠數量的比例μ呢？

統計學告訴我們，可以進行抽樣統計，我們可以從裡面隨手抓一把彈珠出來，統計這把彈珠中橙黃色彈珠所佔的比例v，那麼v就會近似等於μ，即v≈μ。

當然，如果非常點背，v和μ還是可能相差很多的，例如罐子里只有很少的橙黃色彈珠，可是我們抓的那一把中恰好有很多的橙黃色彈珠。如果出現這種情況，我們稱抓到的那把彈珠是BAD的，也就是我們的樣本集D是BAD的。

但是數學上可以證明，如果我們只抓一把，這一把彈珠是BAD 的概率會很小，這就是Hoeffding不等式告訴我們的事情：

既然概率很小，我們就可以說，v和μ相等是很可能差不多正確的，注意這個表述，差不多是指v和μ近似相等，很可能是指v和μ近似相等的概率很大。實際上，很可能差不多正確的這一說法被稱為PAC（Probably Approximately Corret）。

現在，用專業點的話來講，我們說v和μ相等是一個PAC表述。

類似的道理，假如我們現在有數據集D，如果在D上，函數g和f很像，那麼我們也就可以證明，g和f在所有的數據上也很可能是很像的，不過這裡要加一個條件，那就是我們的輸入X應當是服從某個分布的隨機變數。

但是，正如隨手抓一把彈珠可能是BAD的一樣，我們的D也可能是BAD的，就是說，有可能我們用演算法A挑出的函數g在D上和f確實非常像，但在D之外卻與f非常不一樣，即E_in(g)很小，但E_out(g)卻很大。

顯然，如果是這樣的話，我們的機器學習就失靈了，因為沒法挑出和f很像的g。所幸，對於任意一個函數h，D是BAD的概率同樣是很小的，這也是由Hodffding不等式給我們做出的保證。

現在我們的機器學習流程變成了這個樣子：

讓我們看看這個圖，我們的D中的x是從某個分布P中產生的，對於任意一個確定的函數h 如果在D上，h和f非常像，那麼我們就可以說，對於一個D之外的x，我們就可以說，h(x)和f(x)相等是一個PAC表述，即它們很大概率上是比較接近的。

現在，你覺得我們的問題解決了嗎？好像解決了，但實際上，證明才剛剛開始。

2、H是有限情況下的證明

仔細觀察，我們的機器學習演算法和抓彈珠估計橙黃色彈珠比例有一個不同的地方。

在抓彈珠中，我們就抓了一把，然後就用它來估計橙黃色彈珠的比例，Hoeffding不等式告訴我們，如果你只抓一把，那麼這一把是BAD的概率是很小的。

但在機器學習演算法中，我們雖然也是只有一把，即只有一個D，但是我們卻有不止一個函數h，我們的H是一個函數的集合，演算法正是要從這一個集合中挑出一個和f很像的函數g。類似於抓一把彈珠，對H中的任意一個函數h，D是BAD的概率是很小的，但是對於一個有很多函數的函數集合H，很可能有一個函數b，對它來說D是BAD的，也就是說對函數b來說，它在D上與f很像，但在D之外，卻與f大相徑庭。

這就好比，讓你丟五次硬幣，五次全是正面的可能性很小，如果讓200個人同時各丟五次硬幣，其中有一個人五次全丟正面的可能性就會很大很大，真是上山上多了總會碰到虎，夜路走了總會碰到鬼。

而我們的演算法挑選函數g的標準就是看它們誰與f在D上最像，那豈不是很可能會挑中函數b作為最後的g？如果這樣的話，機器學習就又失靈了，細思極恐！

怎麼破？

既然問題出在H上，我們當然就從H入手，我們把H分成兩類，一類是有限的H，一類是無限的H，有限的H就是說裡面可供我們挑選的函數數量是有限的，比如只有M個函數。

本著先易後難的原則，我們先解決H中只有M個函數的情形。

此時，如果D對M個函數中任一個函數來說是BAD的，我們就說D對整個H是BAD的，所幸的是，只要M是有限的，D中的樣本數量N足夠大，這一概率仍然是很小的，證明如下：

由此我們證明了，對於H是有限的情況，我們的演算法A最後挑選的函數g與f相等是一個PAC表述。

3、H是無限情況下的證明

更難的問題來了！如果H中有無限數量個函數，豈不是必然有一個函數b，D對它來說是BAD的？

實事求是講，這個證明是很複雜的，很難簡略地說清楚，我也是盡我所能，如果你看不懂，很可能是我沒說清，推薦你看林老師的視頻，裡面講的極棒。

我們以銀行發放信用卡為例，銀行中的數據是這樣的D：{（x_i，y_i）|x_i

∈d維向量空間，y_i∈{+1，-1}}

x表示用戶的個人特徵信息向量，是d維的，y為+1表示給這個人發卡後很好，y為-1表示給這個人發卡後很差。為便於分析，這裡我們假設d=2。x向量就是這樣的(x1,x2)，

將這些數據可視化，就是這樣的：

圈圈表示y = +1，叉叉表示y=-1 。

我們的H中的每個函數就是這個平面上的一條線，如下所示：

我們要找的函數g實際上就是一條將圖中的圈圈叉叉完全分開的直線。如上圖中右面所示。

回到我們的問題中，現在有一個D，裡面的樣本數是N，H是無數條直線,我們希望能夠證明，D對H來說是BAD的概率很小，這是我們努力的方向。

仔細觀察上面的圖，我們可以發現，雖然H中直線的數量是無限的，但是其「種類」卻是有限的，什麼意思？

假設我們只有一個點，這個點非常牛逼，它說：「在我眼中只有兩條直線，一條直線把我劃為叉叉，一條直線把我劃為圈圈。」

是不是很有哲學意味？世界上有多少人？答曰兩人，一為男人，一為女人。

假設我們現在有兩個點，在這兩個點看來，縱然有無數條直線，也不過只有四種，如下所示：

最終我們可以證明，對於N個點來說，直線的種類m(N)是一個關於N的多項式。

至此，雖然H中函數數量是無限的，但函數的種類卻可看做N的多項式，對這個種類m(N)稍加變換，就可以用來代替上面H有限情況下的不等式中的M，我們可以得到：

這就是著名的VC-bound不等式，這是一個在機器學習中非常非常重要的公式。

上面的說明實在過於簡略，下面我準備用一個圖來簡單表示課程中的證明過程，可以結合視頻進行理解。整個證明以二元線性分類為例進行，但是結論卻具有一般性。這是哲學觀點共性寓於個性之中的很好體現。

實際上，完整地證明這個公式非常難，課程中也沒有給出詳細的證明。但這並不妨礙我們對這個公式表達的意義的理解。

下面是一些關於vc dimension的簡單結論：

vc dimension是對假設集H的power的衡量，在我們的perceptrons 假設集中，它的vc dimension就是d+1，即模型中參數變數的個數。實際上，在大多數情況下，假設集H的vc dimension與它的模型中參數變數的數量是相等的。從物理的意義上看，這些參數變數代表了模型的自由度，參數變數數量越多，模型的自由度越大，power就會越強，vc dimension自然就會越大。

但是，只要假設集H的vc dimension是一個有限的值，vc bound就可以確保，找到一個函數小g，如果它有較小的E_in，那麼它很大概率上也將擁有較小的E_out，即「學習」這件事發生了。

推薦閱讀：