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
• 學(xué)習(xí)可行的兩個(gè)核心條件
• Effective Number of Hypotheses
• Growth Function
• Break Point與Shatter
• VC Bound
• VC dimension
• 深度學(xué)習(xí)與VC維
• 小結(jié)
• 參考文獻(xiàn)

VC維在機(jī)器學(xué)習(xí)領(lǐng)域是一個(gè)很基礎(chǔ)的概念，它給諸多機(jī)器學(xué)習(xí)方法的可學(xué)習(xí)性提供了堅(jiān)實(shí)的理論基礎(chǔ)，但有時(shí)候，特別是對(duì)我們工程師而言，SVM，LR，深度學(xué)習(xí)等可能都已經(jīng)用到線上了，但卻不理解VC維。

這里，在臺(tái)灣大學(xué)機(jī)器學(xué)習(xí)基石課程的基礎(chǔ)上，我們簡單聊聊“VC維的來龍去脈”。我們將解決以下問題：為什么某機(jī)器學(xué)習(xí)方法是可學(xué)習(xí)的？為什么會(huì)有過擬合？拿什么來衡量機(jī)器學(xué)習(xí)模型的復(fù)雜度？深度學(xué)習(xí)與VC維的關(guān)系？

說說歷史

在講VC維之前，我們不妨來說說VC維的歷史。而說起VC維的歷史，又不得不提起神經(jīng)網(wǎng)絡(luò)，一方面是因?yàn)樯窠?jīng)網(wǎng)絡(luò)與VC維的發(fā)明過程是交織在一起的，另一方面是由于神經(jīng)網(wǎng)絡(luò)乏善可陳的泛化控制方法，深度學(xué)習(xí)在理論基礎(chǔ)上一直被懷疑，甚至神經(jīng)網(wǎng)絡(luò)和VC維的代表SVM還一起爭風(fēng)吃醋過好多年。

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

1957年，康奈爾大學(xué)的實(shí)驗(yàn)心理學(xué)家弗蘭克·羅森布拉特(Rosenblatt)在一臺(tái)IBM–704計(jì)算機(jī)上模擬實(shí)現(xiàn)了一種他發(fā)明的叫作“感知機(jī)”（Perceptron）的神經(jīng)網(wǎng)絡(luò)模型。神經(jīng)網(wǎng)絡(luò)與支持向量機(jī)都源自于感知機(jī)（Perceptron）。

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

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

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

1974年，V. Vapnik提出了結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則。

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

1982年，在加州理工擔(dān)任生物物理教授的霍普菲爾德，提出了一種新的神經(jīng)網(wǎng)絡(luò)，可以解決一大類模式識(shí)別問題，還可以給出一類組合優(yōu)化問題的近似解。這種神經(jīng)網(wǎng)絡(luò)模型后被稱為霍普菲爾德網(wǎng)絡(luò)。

1986年，Rummelhart與McClelland發(fā)明了神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法Back Propagation。

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

1992~2005年，SVM與Neural network之爭，但被互聯(lián)網(wǎng)風(fēng)潮掩蓋住了。

2006年，Hinton提出神經(jīng)網(wǎng)絡(luò)的Deep Learning算法。Deep Learning假設(shè)神經(jīng)網(wǎng)絡(luò)是多層的，首先用Restricted Boltzmann Machine（非監(jiān)督學(xué)習(xí)）學(xué)習(xí)網(wǎng)絡(luò)的結(jié)構(gòu)，然后再通過Back Propagation（監(jiān)督學(xué)習(xí)）學(xué)習(xí)網(wǎng)絡(luò)的權(quán)值。

現(xiàn)在，deep learning的應(yīng)用越來越廣泛，甚至已經(jīng)有超越SVM的趨勢。一方面以Hinton，Lecun為首的深度學(xué)習(xí)派堅(jiān)信其有效實(shí)用性，另一方面Vapnik等統(tǒng)計(jì)機(jī)器學(xué)習(xí)理論專家又堅(jiān)持著理論陣地，懷疑deep learning的泛化界。

Hoeffding不等式

Hoeffding不等式是關(guān)于一組隨機(jī)變量均值的概率不等式。 如果X1,X2,⋯,Xn為一組獨(dú)立同分布的參數(shù)為p的伯努利分布隨機(jī)變量，n為隨機(jī)變量的個(gè)數(shù)。定義這組隨機(jī)變量的均值為：

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

更多請(qǐng)參考:Hoeffding不等式，集中不等式

case示例：

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

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

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

Connection to Learning

接下來，我們希望可以將機(jī)器學(xué)習(xí)關(guān)聯(lián)到上一節(jié)討論的hoeffding不等式。

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

機(jī)器學(xué)習(xí)的過程就是：通過算法A，在假設(shè)空間H中，根據(jù)樣本集D，選擇最好的假設(shè)作為g。選擇標(biāo)準(zhǔn)是 g 近似于 f。

拿perceptron來舉例。

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

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

感知器的優(yōu)化目標(biāo)如下式所示，w_g就是我們要求的最好的假設(shè)。

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

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

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

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

根據(jù)上面不等式，我們可以推斷，當(dāng)N足夠大時(shí)，expected loss和expirical loss將非常接近。

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

那么對(duì)于整個(gè)假設(shè)空間，也就是這M個(gè)假設(shè)函數(shù)，可以推導(dǎo)出下面不等式：

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

學(xué)習(xí)可行的兩個(gè)核心條件

在往下繼續(xù)推導(dǎo)前，先看一下什么情況下Learning是可行的？

1. 如果假設(shè)空間H的size M是有限的，當(dāng)N足夠大時(shí)，那么對(duì)假設(shè)空間中任意一個(gè)g，Eout(g)約等于Ein(g)；
2. 利用算法A從假設(shè)空間H中，挑選出一個(gè)g，使得Ein(g)接近于0，那么probably approximately correct而言，Eout(g)也接近為0；

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

但往往我們更多在關(guān)心，如何基于模型的假設(shè)空間，利用最優(yōu)化算法，找到Ein最小的解g。但容易忽視test這個(gè)過程，如果讓學(xué)習(xí)可行，不僅僅是要在訓(xùn)練集表現(xiàn)好，在真實(shí)環(huán)境里也要表現(xiàn)好。

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

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

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

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

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

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

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

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

Effective Number of Hypotheses

對(duì)于這個(gè)有效的假設(shè)函數(shù)值，我們嘗試用一個(gè)數(shù)學(xué)定義來說明：

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

下面是hypotheses與dichotomies的概念對(duì)比：

注意到，如果對(duì)平面上的4個(gè)點(diǎn)來分類，根據(jù)前面分析，輸出的結(jié)果向量只有14種可能，即有14個(gè)dichotomies。

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

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

Growth Function

H作用于D“最多”能產(chǎn)生多少種不同的dichotomies？這個(gè)數(shù)量與假設(shè)空間H有關(guān)，跟數(shù)據(jù)量N也有關(guān)。將H作用于D“最多”能產(chǎn)生的dichotomies數(shù)量(即effective(N) )表示為數(shù)學(xué)符號(hào)：max_H(x1,x2,…,xN)

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

下圖舉4個(gè)例子，分別計(jì)算其growth function：

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

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

Break Point與Shatter

在進(jìn)一步推導(dǎo)前，再看兩個(gè)概念：shatter，break point。

Shatter的概念：當(dāng)假設(shè)空間H作用于N個(gè)input的樣本集時(shí)，產(chǎn)生的dichotomies數(shù)量等于這N個(gè)點(diǎn)總的組合數(shù)2N是，就稱：這N個(gè)inputs被H給shatter掉了。

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

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

舉例來說，對(duì)于上面的positive ray的例子，因?yàn)閙_H(N)=N+1，當(dāng)N=2時(shí)，m_H(2)<2^2， 所以它的break point就是2。

VC Bound

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

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

那么我們做一些簡單的推導(dǎo)：

• B(2,2)=3。因?yàn)閎reak point=2，任意兩個(gè)點(diǎn)都不能被shatter，m_H(2)肯定小于2^2，所以B(2,2)=3。
• B(3,2)=4。因?yàn)槿我鈨蓚€(gè)點(diǎn)都不能被shatter，那么3個(gè)點(diǎn)產(chǎn)生的dichotomies不能超過4，所以B(3,2)=4。
• B(N,1)=1。
• B(N,k)=2^N for N < k；B(N,k)=2^N–1 for N=k；
• B(4,3)=？去掉其中的一個(gè)數(shù)據(jù)點(diǎn)x4后，考慮到break point=3，余下數(shù)據(jù)(x1,x2,x3)的dichotomies數(shù)目不能超過B(3,3)。當(dāng)擴(kuò)展為(x1,x2,x3,x4)時(shí)，(x1,x2,x3)上的dichotomies只有部分被重復(fù)復(fù)制了，設(shè)被復(fù)制的dichotomies數(shù)量為a，未被復(fù)制的數(shù)量為b。于是有B(3,3) = a+b; B(4,3) = 2a + b。因?yàn)閍被復(fù)制了，表示x4有兩個(gè)取值，那么(x1,x2,x3)上的a應(yīng)該小于等于B(3,2)。所以推導(dǎo)出B(4,3) = 2a + b <= B(3,3) + B(3,2)。
• 對(duì)于任意N>k，類推可以得到，B(N,k) ≤ B(N−1,k)+B(N−1,k−1)

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

 

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

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

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

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

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

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

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

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

VC dimension

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

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

根據(jù)定義，可以得到一個(gè)明顯的結(jié)論：

k = d_vc(H) + 1

根據(jù)前面的推導(dǎo)，我們知道VC維的大小：與學(xué)習(xí)算法A無關(guān)，與輸入變量X的分布也無關(guān)，與我們求解的目標(biāo)函數(shù)f 無關(guān)。它只與模型和假設(shè)空間有關(guān)。

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

總結(jié)回顧一下，要想讓機(jī)器學(xué)到東西，并且學(xué)得好，有2個(gè)條件：

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

回到最開始提出的學(xué)習(xí)可行的兩個(gè)核心條件，嘗試用VC維來解釋：

從上圖可以看出，當(dāng)VC維很小時(shí)，條件1容易滿足，但因?yàn)榧僭O(shè)空間較小，可能不容易找到合適的g 使得Ein(g)約等于0。當(dāng)VC維很大時(shí)，條件2容易滿足，但條件1不容易滿足，因?yàn)閂C bound很大。

VC維反映了假設(shè)空間H 的強(qiáng)大程度(powerfulness)，VC 維越大，H也越強(qiáng)，因?yàn)樗梢源蛏?shatter)更多的點(diǎn)。

定義模型自由度是，模型當(dāng)中可以自由變動(dòng)的參數(shù)的個(gè)數(shù)，即我們的機(jī)器需要通過學(xué)習(xí)來決定模型參數(shù)的個(gè)數(shù)。

一個(gè)實(shí)踐規(guī)律：VC 維與假設(shè)參數(shù)w 的自由變量數(shù)目大約相等。dVC = #free parameters。

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

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

它們的上升與下降的速度在每個(gè)階段都是不同的，因此我們能夠?qū)ふ乙粋€(gè)二者兼顧的，比較合適的d_vc，用來決定應(yīng)該使用多復(fù)雜的模型。

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

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

除此外，我們?yōu)榱吮苊鈕verfit，一般都會(huì)加正則項(xiàng)。那加了正則項(xiàng)后，新的假設(shè)空間會(huì)得到一些限制，此時(shí)新假設(shè)空間的VC維將變小，也就是同樣訓(xùn)練數(shù)據(jù)條件下，Ein更有可能等于Eout，所以泛化能力更強(qiáng)。這里從VC維的角度解釋了正則項(xiàng)的作用。

深度學(xué)習(xí)與VC維

對(duì)于神經(jīng)網(wǎng)絡(luò)，其VC維的公式為：

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

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

可以看到，神經(jīng)網(wǎng)絡(luò)的VC維相對(duì)較高，因而它的表達(dá)能力非常強(qiáng)，可以用來處理任何復(fù)雜的分類問題。根據(jù)上一節(jié)的結(jié)論，要充分訓(xùn)練該神經(jīng)網(wǎng)絡(luò)，所需樣本量為10倍的VC維。如此大的訓(xùn)練數(shù)據(jù)量，是不可能達(dá)到的。所以在20世紀(jì)，復(fù)雜神經(jīng)網(wǎng)絡(luò)模型在out of sample的表現(xiàn)不是很好，容易o(hù)verfit。

但現(xiàn)在為什么深度學(xué)習(xí)的表現(xiàn)越來越好。原因是多方面的，主要體現(xiàn)在：

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

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

更多細(xì)節(jié)請(qǐng)參考下面鏈接：

• VC Dimension of Multilayer Neural Networks，該文章給出了多層神經(jīng)網(wǎng)絡(luò)的VC bound的相關(guān)證明。
• 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.

小結(jié)

上面仔細(xì)分析了VC維的來龍去脈，講述了VC維在機(jī)器學(xué)習(xí)理論中的指導(dǎo)意義。考慮到VC維在機(jī)器學(xué)習(xí)領(lǐng)域雖是基礎(chǔ)，卻也是大坑，所以難免有理解不深或不當(dāng)之處，敬請(qǐng)諒解。若希望獲得更深理解，請(qǐng)參考下面的參考文獻(xiàn)。

參考文獻(xiàn)

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