http://www.flickering.cn/machine_learning/2015/04/vc%E7%BB%B4%E7%9A%84%E6%9D%A5%E9%BE%99%E5%8E%BB%E8%84%89/
目錄：
- 說說歷史
- 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維的來龍去脈，講述了VC維在機器學習理論中的指導意義。考慮到VC維在機器學習領域雖是基礎，卻也是大坑，所以難免有理解不深或不當之處，敬請諒解。若希望獲得更深理解，請參考下面的參考文獻。
參考文獻