http://www.flickering.cn/machine_learning/2015/04/vc維的來龍去脈/

• 說說歷史
• Hoeffding不等式
• Connection to Learning
• 學習可行的兩個核心條件
• Effective Number of Hypotheses
• Growth Function
• Break Point與Shatter
• VC Bound
• VC dimension
• 深度學習與VC維
• 小結
• 參考文獻

VC維在機器學習領域是一個很基礎的概念，它給諸多機器學習方法的可學習性提供了堅實的理論基礎，但有時候，特別是對我們工程師而言，SVM，LR，深度學習等可能都已經用到線上了，但卻不理解VC維。

這里，在臺灣大學機器學習基石課程的基礎上，我們簡單聊聊“VC維的來龍去脈”。我們將解決以下問題：為什么某機器學習方法是可學習的？為什么會有過擬合？拿什么來衡量機器學習模型的復雜度？深度學習與VC維的關系？

說說歷史

在講VC維之前，我們不妨來說說VC維的歷史。而說起VC維的歷史，又不得不提起神經網絡，一方面是因為神經網絡與VC維的發明過程是交織在一起的，另一方面是由于神經網絡乏善可陳的泛化控制方法，深度學習在理論基礎上一直被懷疑，甚至神經網絡和VC維的代表SVM還一起爭風吃醋過好多年。

1943年，模擬神經網絡由麥卡洛可（McCulloch）和皮茨（Pitts)提出，他們分析了理想化的人工神經元網絡，并且指出了它們進行簡單邏輯運算的機制。

1957年，康奈爾大學的實驗心理學家弗蘭克·羅森布拉特(Rosenblatt)在一臺IBM–704計算機上模擬實現了一種他發明的叫作“感知機”（Perceptron）的神經網絡模型。神經網絡與支持向量機都源自于感知機（Perceptron）。

1962年，羅森布拉特著作：《神經動力學原理：感知機和大腦機制的理論》（Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms）。

1969年，明斯基和麻省理工學院的另一位教授佩普特合作著作：《感知機：計算幾何學》（Perceptrons: An Introduction to Computational Geometry)。在書中，明斯基和佩普特證明單層神經網絡不能解決XOR（異或）問題。

1971年，V. Vapnik and A. Chervonenkis在論文“On the uniform convergence of relative frequencies of events to their probabilities”中提出VC維的概念。

1974年，V. Vapnik提出了結構風險最小化原則。

1974年，沃波斯（Werbos）的博士論文證明了在神經網絡多加一層，并且利用“后向傳播”（Back-propagation）學習方法，可以解決XOR問題。那時正是神經網絡研究的低谷，文章不合時宜。

1982年，在加州理工擔任生物物理教授的霍普菲爾德，提出了一種新的神經網絡，可以解決一大類模式識別問題，還可以給出一類組合優化問題的近似解。這種神經網絡模型后被稱為霍普菲爾德網絡。

1986年，Rummelhart與McClelland發明了神經網絡的學習算法Back Propagation。

1993年，Corinna Cortes和Vapnik等人提出了支持向量機(support vector machine)。神經網絡是多層的非線性模型，支持向量機利用核技巧把非線性問題轉換成線性問題。

1992~2005年，SVM與Neural network之爭，但被互聯網風潮掩蓋住了。

2006年，Hinton提出神經網絡的Deep Learning算法。Deep Learning假設神經網絡是多層的，首先用Restricted Boltzmann Machine（非監督學習）學習網絡的結構，然后再通過Back Propagation（監督學習）學習網絡的權值。

現在，deep learning的應用越來越廣泛，甚至已經有超越SVM的趨勢。一方面以Hinton，Lecun為首的深度學習派堅信其有效實用性，另一方面Vapnik等統計機器學習理論專家又堅持著理論陣地，懷疑deep learning的泛化界。

Hoeffding不等式

Hoeffding不等式是關于一組隨機變量均值的概率不等式。 如果X1,X2,?,Xn為一組獨立同分布的參數為p的伯努利分布隨機變量，n為隨機變量的個數。定義這組隨機變量的均值為：

對于任意δ>0, Hoeffding不等式可以表示為

更多請參考:Hoeffding不等式，集中不等式

case示例：

在統計推斷中，我們可以利用樣本的統計量(statistic)來推斷總體的參數(parameter)，譬如使用樣本均值來估計總體期望。如下圖所示，我們從罐子里抽球，希望估計罐子里紅球和綠球的比例。

直覺上，如果我們有更多的樣本(抽出更多的球)，則樣本期望ν應該越來越接近總體期望μ。事實上，這里可以用hoeffding不等式表示如下：

從hoeffding不等式可以看出，當n逐漸變大時，不等式的UpperBound越來越接近0，所以樣本期望越來越接近總體期望。

Connection to Learning

接下來，我們希望可以將機器學習關聯到上一節討論的hoeffding不等式。

一個基本的機器學習過程如下圖所示。其中的概念定義為： f 表示理想的方案(可以是一個函數，也可以是一個分布)，H 是該機器學習方法的假設空間，g 表示我們求解的用來預測的假設，g屬于H。

機器學習的過程就是：通過算法A，在假設空間H中，根據樣本集D，選擇最好的假設作為g。選擇標準是 g 近似于 f。

拿perceptron來舉例。

感知機（perceptron）是一個線性分類器(linear classifiers）。 線性分類器的幾何表示：直線、平面、超平面。

perceptron的假設空間，用公式描述，如下所示：

感知器的優化目標如下式所示，w_g就是我們要求的最好的假設。

設定兩個變量，如下圖所示，圖中 f(x)表示理想目標函數，h(x)是我們預估得到的某一個目標函數，h(x)是假設空間H中的一個假設。

Eout(h)，可以理解為在理想情況下(已知f)，總體(out-of-sample)的損失(這里是0–1 loss)的期望，稱作expected loss。

Ein(h)，可以理解為在訓練樣本上(in-of-sample)，損失的期望，稱作expirical loss。

當訓練樣本量N足夠大，且樣本是獨立同分布的，類比于上面“抽球”的例子，可以通過樣本集上的expirical loss Ein(h) 推測總體的expected loss Eout(h)。基于hoeffding不等式，我們得到下面式子：

根據上面不等式，我們可以推斷，當N足夠大時，expected loss和expirical loss將非常接近。

注意在上面推導中，我們是針對某一個特定的解h(x)。在我們的假設空間H中，往往有很多個假設函數(甚至于無窮多個)，這里我們先假定H中有M個假設函數。

那么對于整個假設空間，也就是這M個假設函數，可以推導出下面不等式：

上面式子的含義是：在假設空間H中，設定一個較小的?值，任意一個假設h，它的Ein(h)與Eout(h)的差由該值2Mexp(?2?2N)所約束住。注意這個bound值與 “樣本數N和假設數M” 密切相關。

學習可行的兩個核心條件

在往下繼續推導前，先看一下什么情況下Learning是可行的？

如果假設空間H的size M是有限的，當N足夠大時，那么對假設空間中任意一個g，Eout(g)約等于Ein(g)；

利用算法A從假設空間H中，挑選出一個g，使得Ein(g)接近于0，那么probably approximately correct而言，Eout(g)也接近為0；

上面這兩個核心條件，也正好對應著test和train這兩個過程。train過程希望損失期望(即Ein(g) )盡可能小；test過程希望在真實環境中的損失期望也盡可能小，即Ein(g)接近于Eout(g)。

但往往我們更多在關心，如何基于模型的假設空間，利用最優化算法，找到Ein最小的解g。但容易忽視test這個過程，如果讓學習可行，不僅僅是要在訓練集表現好，在真實環境里也要表現好。

從上述推導出來的不等式，我們看到假設數M 在這兩個核心條件中有著重要作用。

M太小，當N足夠大時，Ein和Eout比較接近，但如果候選假設集太小，不容易在其中找到一個g，使得Ein(g)約等于0，第二項不能滿足。而如果M太大，這時候選集多了，相對容易在其中找到一個g，使得Ein(g)約等于0，但第一項就不能滿足了。所以假設空間H的大小M很關鍵。

對于一個假設空間，M可能是無窮大的。要能夠繼續推導下去，那么有一個直觀的思路，能否找到一個有限的因子m_H來替代不等式bound中的M。

雖說假設空間很大，上述推導里，我們用到了P(h1 or h2 … hm) <= P(h1) + P(h2) + … + P(hm)。但事實上，多個h之間并不是完全獨立的，他們是有很大的重疊的，也就是在M個假設中，可能有一些假設可以歸為同一類。

下面我們以二維假設空間為例，來解釋一下該空間下各假設在確定的訓練樣本上的重疊性。

舉例來說，如果我們的算法要在平面上(二維空間)挑選一條直線方程作為g，用來劃分一個點x1。假設空間H是所有的直線，它的size M是無限多的。但是實際上可以將這些直線分為兩類，一類是把x1判斷為正例的，另一類是把x1判斷為負例的。如下圖所示：

那如果在平面上有兩個數據點x1,x2，這樣的話，假設空間H中的無數條直線可以分為4類。那依次類推，3個數據點情況下，H中最多有8類直線。4個數據點，H中最多有14類直線(注意：為什么不是16類直線)。

從上面在二維假設空間中的分析，我們可以推測到一個結論，假設空間size M是很大，但在樣本集D上，有效的假設函數數目是有限的。接下來我們將繼續推導這個有效的假設函數值。

Effective Number of Hypotheses

對于這個有效的假設函數值，我們嘗試用一個數學定義來說明：

從H中任意選擇一個方程h，讓這個h對樣本集合D進行二元分類，輸出一個結果向量。例如在平面里用一條直線對2個點進行二元分類，輸出可能為{1,–1}，{–1,1}，{1,1}，{–1,–1}，這樣每個輸出向量我們稱為一個dichotomy。

下面是hypotheses與dichotomies的概念對比：

注意到，如果對平面上的4個點來分類，根據前面分析，輸出的結果向量只有14種可能，即有14個dichotomies。

如果有N個樣本數據，那么有效的假設個數定義為： effective(N) = H作用于樣本集D“最多”能產生多少不同的dichotomy。

所以有一個直觀思路，能否用effective(N)來替換hoeffding不等式中的M。接下來我們來分析下effective(N)。

Growth Function

H作用于D“最多”能產生多少種不同的dichotomies？這個數量與假設空間H有關，跟數據量N也有關。將H作用于D“最多”能產生的dichotomies數量(即effective(N) )表示為數學符號：max_H(x1,x2,…,xN)

這個式子又稱為“成長函數”(growth function)。在H確定的情況下，growth function是一個與N相關的函數。

下圖舉4個例子，分別計算其growth function：

對于第一個例子，positive ray，相當于是正向的射線。該假設空間，作用于1個樣本點，可以產生2種dichotomies：(–1)，(+1)。作用于2個樣本點，可以產生3種dichotomies：(–1,+1)，(–1,–1)，(+1,+1)。作用于3個樣本點，可以產生4種dichotomies。依次類推，可以推導出其成長函數 m_H(N)=N+1；

求解出m_H(N)后，那是不是可以考慮用m_H(N)替換M? 如下所示：

Break Point與Shatter

在進一步推導前，再看兩個概念：shatter，break point。

Shatter的概念：當假設空間H作用于N個input的樣本集時，產生的dichotomies數量等于這N個點總的組合數2N是，就稱：這N個inputs被H給shatter掉了。

要注意到 shatter 的原意是“打碎”，在此指“N個點的所有(碎片般的)可能情形都被H產生了”。所以mH(N)=2N的情形是即為“shatter”。

對于給定的成長函數m_H(N)，從N=1出發，N慢慢變大，當增大到k時，出現mH(N)<2k的情形，則我們說k是該成長函數的break point。對于任何N > k個inputs而言，H都沒有辦法再shatter他們了。

舉例來說，對于上面的positive ray的例子，因為m_H(N)=N+1，當N=2時，m_H(2)<22，?所以它的break point就是2。

VC Bound

說完break point的概念后，再回到成長函數。

我們將成長函數的上界，設為B(N,k)，意為：maximum possible m_H(N) when break point = k。

那么我們做一些簡單的推導：

• B(2,2)=3。因為break point=2，任意兩個點都不能被shatter，m_H(2)肯定小于22，所以B(2,2)=3。
• B(3,2)=4。因為任意兩個點都不能被shatter，那么3個點產生的dichotomies不能超過4，所以B(3,2)=4。
• B(N,1)=1。
• B(N,k)=2N?for N < k；B(N,k)=2N–1 for N=k；
• B(4,3)=？去掉其中的一個數據點x4后，考慮到break point=3，余下數據(x1,x2,x3)的dichotomies數目不能超過B(3,3)。當擴展為(x1,x2,x3,x4)時，(x1,x2,x3)上的dichotomies只有部分被重復復制了，設被復制的dichotomies數量為a，未被復制的數量為b。于是有B(3,3) = a+b; B(4,3) = 2a + b。因為a被復制了，表示x4有兩個取值，那么(x1,x2,x3)上的a應該小于等于B(3,2)。所以推導出B(4,3) = 2a + b <= B(3,3) + B(3,2)。
• 對于任意N>k，類推可以得到，B(N,k) ≤ B(N?1,k)+B(N?1,k?1)

最后利用數學歸納法，可以證明得到下面的bounding function(N>k)：

?

這個式子顯然是多項式的，多項式的最高冪次項為：N^(k–1)。

所以我們得到結論：如果break point存在（有限的正整數），生長函數m(N) 是多項式的。

再重復一遍，H作用于數據量為N的樣本集D，方程的數量看上去是無窮的，但真正有效(effective)的方程的數量卻是有限的，這個數量為m_H(N)。H中每一個h作用于D都能算出一個Ein來，一共有m_H(N)個不同的Ein。

OK，到目前為止，關于m_H(N)的推導結束。回到growth function小節提出的問題，能否用m_H(N)直接替換M?

既然得到了m(N)的多項式上界，我們希望對之前的不等式中M 進行替換，用m_H(N)來替換M。這樣替換后，當break point存在時，N足夠大時，該上界是有限的。

然而直接替換是存在問題的，主要問題是：Ein的可能取值是有限個的，但Eout的可能取值是無限的。可以通過將Eout 替換為驗證集(verification set) 的Ein’ 來解決這個問題。 下面是推導過程：

最后我們得到下面的VC bound:

關于這個公式的數學推導，我們可以暫且不去深究。我們先看一下這個式子的意義，如果假設空間存在有限的break point，那么m_H(2N)會被最高冪次為k–1的多項式上界給約束住。隨著N的逐漸增大，指數式的下降會比多項式的增長更快，所以此時VC Bound是有限的。更深的意義在于，N足夠大時，對H中的任意一個假設h，Ein(h)都將接近于Eout(h)，這表示學習可行的第一個條件是有可能成立的。

VC dimension

說了這么多，VC維終于露出廬山真面目了。此概念由Vladimir Vapnik與Alexey Chervonenkis提出。

一個假設空間H的VC dimension，是這個H最多能夠shatter掉的點的數量，記為dvc(H)。如果不管多少個點H都能shatter它們，則dvc(H)=無窮大。還可以理解為：vc-dim就是argmax_n {growth function=power(2,n)}。

根據定義，可以得到一個明顯的結論：

k = d_vc(H) + 1

根據前面的推導，我們知道VC維的大小：與學習算法A無關，與輸入變量X的分布也無關，與我們求解的目標函數f 無關。它只與模型和假設空間有關。

我們已經分析了，對于2維的perceptron，它不能shatter 4個樣本點，所以它的VC維是3。此時，我們可以分析下2維的perceptron，如果樣本集是線性可分的，perceptron learning algorithm可以在假設空間里找到一條直線，使Ein(g)=0；另外由于其VC維=3，當N足夠大的時候，可以推斷出：Eout(g)約等于Ein(g)。這樣學習可行的兩個條件都滿足了，也就證明了2維感知器是可學習的。

總結回顧一下，要想讓機器學到東西，并且學得好，有2個條件：

• H的d_vc是有限的，這樣VC bound才存在。(good H)；N足夠大(對于特定的d_vc而言)，這樣才能保證vc bound不等式的bound不會太大。(good D)
• 算法A有辦法在H中順利的挑選一個使得Ein最小的g。(good A)

回到最開始提出的學習可行的兩個核心條件，嘗試用VC維來解釋：

從上圖可以看出，當VC維很小時，條件1容易滿足，但因為假設空間較小，可能不容易找到合適的g 使得Ein(g)約等于0。當VC維很大時，條件2容易滿足，但條件1不容易滿足，因為VC bound很大。

VC維反映了假設空間H 的強大程度(powerfulness)，VC 維越大，H也越強，因為它可以打散(shatter)更多的點。

定義模型自由度是，模型當中可以自由變動的參數的個數，即我們的機器需要通過學習來決定模型參數的個數。

一個實踐規律：VC 維與假設參數w 的自由變量數目大約相等。dVC = #free parameters。

我們將原不等式做一個改寫，如下圖所示：

上面式子中的第3項表示模型復雜度。模型越復雜，VC維大，Eout 可能距離Ein 越遠。如下圖所示，隨著d_vc的上升，E_in不斷降低，而模型復雜度不斷上升。

它們的上升與下降的速度在每個階段都是不同的，因此我們能夠尋找一個二者兼顧的，比較合適的d_vc，用來決定應該使用多復雜的模型。

模型較復雜時(d_vc 較大)，需要更多的訓練數據。 理論上，數據規模N 約等于 10000*d_vc（稱為采樣復雜性，sample complexity）；然而，實際經驗是，只需要 N = 10*d_vc。 造成理論值與實際值之差如此之大的最大原因是，VC Bound 過于寬松了，我們得到的是一個比實際大得多的上界。

注意在前述討論中，理想的目標函數為f(x)，error measure用的是“0–1 loss”。如果在unknown target上引入噪聲(+noise)，或者用不同的error measure方法，VC theory還有效嗎？這里只給出結論，VC theory對于絕大部分假設空間(or 加入噪聲)和error度量方法，都是有效的。

除此外，我們為了避免overfit，一般都會加正則項。那加了正則項后，新的假設空間會得到一些限制，此時新假設空間的VC維將變小，也就是同樣訓練數據條件下，Ein更有可能等于Eout，所以泛化能力更強。這里從VC維的角度解釋了正則項的作用。

深度學習與VC維

對于神經網絡，其VC維的公式為：

dVC = O(VD)，其中V表示神經網絡中神經元的個數，D表示weight的個數，也就是神經元之間連接的數目。(注意：此式是一個較粗略的估計，深度神經網絡目前沒有明確的vc bound)

舉例來說，一個普通的三層全連接神經網絡：input layer是1000維，hidden layer有1000個nodes，output layer為1個node，則它的VC維大約為O(1000*1000*1000)。

可以看到，神經網絡的VC維相對較高，因而它的表達能力非常強，可以用來處理任何復雜的分類問題。根據上一節的結論，要充分訓練該神經網絡，所需樣本量為10倍的VC維。如此大的訓練數據量，是不可能達到的。所以在20世紀，復雜神經網絡模型在out of sample的表現不是很好，容易overfit。

但現在為什么深度學習的表現越來越好。原因是多方面的，主要體現在：

• 通過修改神經網絡模型的結構，以及提出新的regularization方法，使得神經網絡模型的VC維相對減小了。例如卷積神經網絡，通過修改模型結構(局部感受野和權值共享)，減少了參數個數，降低了VC維。2012年的AlexNet，8層網絡，參數個數只有60M；而2014年的GoogLeNet，22層網絡，參數個數只有7M。再例如dropout，drop connect，denosing等regularization方法的提出，也一定程度上增加了神經網絡的泛化能力。
• 訓練數據變多了。隨著互聯網的越來越普及，相比于以前，訓練數據的獲取容易程度以及量和質都大大提升了。訓練數據越多，Ein越容易接近于Eout。而且目前訓練神經網絡，還會用到很多data augmentation方法，例如在圖像上，剪裁，平移，旋轉，調亮度，調飽和度，調對比度等都使用上了。
• 除此外，pre-training方法的提出，GPU的利用，都促進了深度學習。

但即便這樣，深度學習的VC維和VC Bound依舊很大，其泛化控制方法依然沒有強理論支撐。但是實踐又一次次證明，深度學習是好用的。所以VC維對深度學習的指導意義，目前不好表述，有一種思想建議，深度學習應該拋棄對VC維之類概念的迷信，嘗試從其他方面來解釋其可學習型，例如使用泛函空間（如Banach Space）中的概率論。

更多細節請參考下面鏈接：

• VC Dimension of Multilayer Neural Networks，該文章給出了多層神經網絡的VC bound的相關證明。
• Lecun: What is the relationship between Deep Learning and Support Vector Machines / Statistical Learning Theory?Vapnik really believes in his bounds. He worried that neural nets didn’t have similarly good ways to do capacity control (although neural nets do have generalization bounds, since they have finite VC dimension).Lecun’s counter argument was that the ability to do capacity control was somewhat secondary to the ability to compute highly complex function with a limited amount of computation.

小結

上面仔細分析了VC維的來龍去脈，講述了VC維在機器學習理論中的指導意義。考慮到VC維在機器學習領域雖是基礎，卻也是大坑，所以難免有理解不深或不當之處，敬請諒解。若希望獲得更深理解，請參考下面的參考文獻。

參考文獻

• VC dimension Tutorial Slides by Andrew Moore
• 機器學習基石?筆記?(上文的截圖均出自于該課程的講義)
• vc-dimension in svms
• 機器學習簡史
• Vapnik–Chervonenkis theory
• Deep Learning Tutorial
• 深度學習的研究領域是否有被過度夸大
• VC Theory: Vapnik–Chervonenkis Dimension

總結

以上是生活随笔為你收集整理的VC维学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。