機器學習基石系列(4) — VC dimension和模型複雜度

在前一篇我們推演出VC theory，用以說明機器學習的可行性。回顧一下最後得到的不等式：

把它稍微整理一下。現在，我們知道若m_H具有break point k，其bounding function的上限，也就是m_H上限的上限，根據

得知，為一N^(k-1)次方的多項式。把係數稍微整理一下，並且用N^(k-1)取代m_H，得到

式1.

到這裡為止，機器能夠學習的條件，建立在

1. m_H具有break point k。如果m_H是像系列(2)裡提到的，為一個convex function(凸函數)，則他沒有break point，任意筆資料都可以被shatter，就無法收斂了。
2. N夠大，使E_in和E_out接近。
3. 機器(演算法A)選到一個好的g使E_in很小。

我們已經可以比較具體的描述機器能學習好的條件了，但還不夠。例如，怎麼讓機器選到好的g?或者說，怎麼知道他是好的g?到目前為止，我們的所知只能讓機器去碰運氣。另外，如果遇到資料分布難以分割的時候怎麼辦?所以，這事兒還沒完。

這篇要講第二個重點：VC dimension和其所衍伸的涵義。

VC dimension

指的是最大的non-break point。如果break point是k，則VC dimension就是k-1。無論是break point或VC dimension，性質上都是針對hypothesis set說的；換成資料的角度，就是到(k-1)筆資料時都還能被shatter。而對hypothesis set裡的h而言，VC dimension k-1表示有h可以對最多k-1筆資料shatter，這k-1筆必須是資料中的某些特定組合；如果多於k-1筆則無法shatter。給予VC dimension符號d_vc，則

這個k是break point，也就是「使h無法把資料全部shatter的最小數量」，所以也可以在k前面加個"minimum"。式1用N^(k-1)取代m_H，可以再寫成

做個小結：資料數量N≤VC dimension時，有機會被全部shatter，但非一定。資料數量>VC dimension時，一定無法被全部shatter。

回來看在系列(2)裡提到的幾個例子：

1. positive rays：break point是2，VC dimension是1。
2. positive intervals：break point為3，VC dimension是2。
3. convex set：凸函數沒有break point，VC dimension為∞。
4. 2D perceptron：break point為4，VC dimension為3。

可以發現VC dimension吻合我們之前推導出的多項式，其內最高次方項。

由於VC dimension是從dichotomy和shatter的概念延伸的，所以套用系列(3)在做break point時的解釋，它和資料分布無關。同時，它可以收斂VC theory的不等式，使E_in和E_out接近，可是和選擇的演算法也無關。即，若E_in高，E_out也高。當然，和target function沒有關係。這樣獨立的性質，讓我們可以在未知target function、未知資料分布、未知演算法的選擇之下仍然可以使用，是非常關鍵的。

高維度的資料適用VC dimension嗎?

我們回到2D的PLA。現在，我們有兩條敘述：

1. 如果資料是線性可分，則PLA可以收斂，在給予足夠的訓練次數之後，可以找到g使E_in趨近0。
2. 不知道資料分布和target function，但因為知道它的VC dimension是3，根據VC theory可以收斂，使E_in和E_out接近。

將這兩個敘述連接起來，可以得到「2D PLA在線性可分的資料下，給予足夠的訓練次數之後，E_out能趨近0，達到訓練目標」的結論。

接著，我們來看看這樣的概念是否能推廣到高維度。首先，我們知道1D perceptron的VC dimension是2，2D則是3。如果維度是d，我們是否能歸納其VC dimension為d+1?

這個推論需要證明。分兩部分執行：從兩個方向，VC dimension≥ d+1，以及VC dimension≤ d-1。證明過程中會用到一些線性代數的概念。

VC dimension≥ d+1：存在h可把某d+1筆資料shatter

現在假設一組特殊的資料，這組資料有d+1筆：如下

第一筆資料只有原點，全部向量都是0；第二筆只有在第一維度有個分量，其他都是0；第三筆則在第二維有分量，其他是0…一直到第d+1筆，是在第d維有分量，其他是0。如此總共有d+1筆。另外，我們在全部的資料前面再加一項1，作為閾值。(個人把它想成常數項的概念)

這組資料在二維空間的長相是這樣：

圖1. 2D的狀況

原點，(0,1)和(1,0)三個點。在之前的驗證中，這是可以被shatter的。

值得注意的是，這個資料排出的矩陣X存在反矩陣且唯一，因為它是一個d+1的方陣。欄數：d個維度+最前面的1，共d+1；列數：d+1筆資料，共d+1。此外，det(X)≠0(可以直接用程式算)。有反矩陣為何如此重要?因為我們shatter的數學式是存在一組y

可以找到w，使sign(wX)=y。式子翻譯的結果就是可以找到一個h，其向量表為w，和x相乘後取其正負號，會和y吻合。這是基於2D PLA的概念延伸出來的。

要讓這個式子成立，其中一個方法就是乾脆讓wX=y。有沒有辦法?有!我可以找到w滿足這個條件，只要w=yX^(-1)就可以了。X的反矩陣就用在這邊。如此，就證明VC dimension≥ d+1。

VC dimension≤ d+1：任何d+2筆資料都不能被所有h shatter

剛剛看過這組資料在2D的狀況(圖1)。假如我們只保留這三筆，並加入第四筆，就在(1,1)的地方；所以變成這樣：

加入了這個點。並假設(0,0)是╳，(0,1)和(1,0)都是○。如果要能shatter，這新加的點該是○還是╳?答案應該很明顯，必須是○。這時發現一件事情：這筆資料的╳或○會限制dichotomy，而本身又受到另外三筆資料的影響。我們可以這樣寫：

式2.

驗證一下：(1,0)+(0,1)-(0,0)=(1,1)，沒問題。

那我們在兩邊同時乘上代表h的各權重之組合w，因為是矩陣乘法，w要轉置才能相乘。

這個也沒問題。因為wx_2為正、wx_3為正、wx_1為負，負負得正，所以wx_4只能為正。這就是如果要shatter的話x_4會被其他三筆資料限制的數學表示法。

式2這樣把一種向量表示成其他三種向量組合的方法，叫做線性組合。這個等式表示有線性相依的性質。線性依賴會限制dichotomy的數量。

這畢竟是一個特例，我們還是要證明對於全部任意d+2筆資料都成立才行。另外取一組資料，共有d+2筆，使其共有d+1欄，d+2列。因為向量維數>向量個數，此矩陣內的向量必線性相依。所以在第d+2筆向量，可以用前面第1~第d+1的向量組合來表示：

這a_1,a_2,…a_d+1有些為正，有些為負，有些為0。此時讓一個w，其內的元素剛好和a同號。例如a_1為正，則w^Tx_1的結果為○；a_2為負，則w^Tx_2結果為╳，以此類推。

這樣一來，全部的項都是正的，相加之後，w^Tx_d+2只能是正的。結果和2D的時候一樣。什麼意思呢?這時如果讓w^Tx_d+2結果是╳，則無法完成dichotomy，資料也就無法被shatter。所以不管什麼資料，任意的d+2筆，只要有線性相依，就能讓它無法被shatter，也就證明VC dimension≤ d+1了。

結合這兩個項目，我們可以知道：VC dimension就是維度+1。而高維度的資料，也可以使用VC dimension的概念。

VC dimension和自由度

所以VC dimension中的"dimension"指的是什麼維度?誰的維度?指的是perceptron的維度；或者我們上面提到的w，它是h裡面的參數組合，影響到hypothesis裡面的變化性，所以也可以說dimension是hypothesis set裡面的自由度(degree of freedom)。

假設一個hypothesis set的自由度無限大，那它就可以有無限的組合，無限的可能，其數量為無限大，就像他有好多個旋鈕，每一個都可以作用。VC dimension=d+1則可以看成一個二元分類的有效自由度。(目前的演算法還設定在二元分類的問題上)「有效」的意思就是有些旋鈕是沒有作用的。因為VC dimension是告訴我們最大能shatter的資料數，所以也可以看成hypothesis set能做到多少…它的能力如何。

例如在positive rays的時候，決定點在一個點，往右就是正，另外一邊是0。它的VC dimension是1，也剛好只有一個旋鈕。到了positive interval，決定點有兩個，兩個點的範圍內是正的，其它是負的。它的VC dimension是2，也是兩個旋鈕。從這兩個例子可以大概知道VC dimension約等於旋鈕，也就是參數的數目；這個概念基本上正確，但並非總是正確。如果要估計一個模型的VC dimension，可以先評估「旋鈕」有多少，某種程度上還是有相關的。

在系列(2)中，我們一開始用M來描述hypothesis set的大小。那時候還假設壞資料對於每個h的發生是彼此獨立的。M大表示hypothesis set的選擇多，可以做到的事情多；但也表示壞資料發生的機會增加。換句話說，就是E_in變小的機會增加，但E_in和E_out落差變大的機會也增加。如果M小，則壞資料發生機率減少，但因為選擇有限，可能也不容易找到E_in低的hypothesis。那現在已經可以用VC dimension來取代M；那就是(2N)^d_vc。

所以一樣的，VC dimension大，就是M大；反之亦然。所以現在重點轉移到VC dimension上了，它的變化攸關學習的效果。

泛化誤差和模型複雜度

VC dimension還有其他意義。我們先回到VC bound：

這是壞資料發生的機率。反過來說，如果我想看好資料發生的機率呢?

式3.

式4.

把式4做移項，可以得到

式5.

然後代回式3，只取不等號左邊：

這是「好資料」發生的機率。E_in和E_out的落差我們從整個系列一開始就在討論了，這邊正式給他一個專有名詞泛化偏差(generalization error)，表示現實和抽樣資料的差距是多少，要拿這個演算法去一般的(外面的)資料做預測，落差是多少。把絕對值解開並展開不等式，得到

E_out落在一個區間，類似信賴區間的概念。不等式的右邊又比左邊值得重視，因為右側牽涉到E_out會多大。根號項，也就是式5，裡面有N、d_vc、δ，分別對應到資料量、hypothesis set強度，以及挑到的演算法。這三項被合稱為模型的複雜度，以Ω表示。他們可以決定hypothesis set的能力，同時，也要付出E_in對E_out的差 — 也就是generalization error — 增加的風險。對於這個風險，可以視為是增加hypothesis set強度的代價，因此在這邊稱作penalty(of model complexity)。

VC dimension還透漏什麼訊息?

模型複雜度越高越好嗎?

可以把E_in、E_out、model complexity化成圖表。橫軸是VC dimension，縱軸是error。

圖片來源：林軒田<機器學習基石>第七講，第29段，第22張

E_in隨著VC dimension增加，hypothesis set的能力越強，越有可能做到dichotomy而下降。反之，VC dimension上升也會讓模型複雜度(Ω)增加。E_out是E_in和model complexity的和，所以呈現一個凹狀線：在一理想的VC dimension下可以最低，但小於此值時因為E_in高，大於此值則因為model complexity高，而使E_out上升。

這是第一個訊息：不要一昧的追逐VC dimension，或模型複雜度。在某些狀況，他所付出的代價可能造成結果比低的VC dimension還要差，必須三思。

資料量要多少才夠達到有效的機器學習?

這句話的意思就是要多少資料量才能有效降低壞資料發生的機率。例如現在用一個2D PLA跑資料，目標設定這機率只能低於0.1，同時演算法δ使E_in和E_out差0.1。PLA的VC dimension是3，我們可以代入

計算。結果如下：

圖片來源：林軒田<機器學習基石>第七講，第29段，第23張

到10萬筆資料時，機率可以壓到非常非常小。事實上，約三萬筆資料時可以滿足我們的要求。

這是VC dimension透漏的第二個訊息：它和需要讓機器有效學習的資料量有關。理論上，此資料量大小約為VC dimension的10萬倍。例如，在這裡VC dimension是3，算出來的資料量接近30000。

實務上，其實只要VC dimension的10倍就夠了。

這落差也太大了吧?沒錯，因為VC bound建基於Hoffeding’s inequality，而且在推導時使用近似法，本來就是寬鬆的。在替代M時使用的m_H，或者是bounding function，都是抓上限。在最後，雖然只用了一次，但還是用的union bound，本身就是一個最大化的設定。因此，造就一件非常寬鬆的褲子~~~

儘管如此，但VC bound對於所有模型的預測都是寬鬆的，是均衡的放大。因此，若要比較模型間的差異，VC dimension仍然是個不錯的工具，因為它不會讓比例失真。

總結

我們從VC bound進到VC dimension，並探討它的多層涵義。它的涵義如下：

1. 能被shatter的最高資料筆數
2. 是模型的dimension，也是hypothesis set的自由度
3. 影響泛化偏差和模型複雜度。追求低的E_in有可能付出代價(penalty)。
4. 承3.，不要過度追求模型複雜度。
5. 某種程度可以透漏需要達到有效機器學習的資料量。

這樣，VC theory的介紹就基本告一段落了。接下來，要討論其他影響機器學習的因素。