VC維的來龍去脈

本文轉自：VC維的來龍去脈

目錄：

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

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

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

說說歷史

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

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

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

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

1969年，明斯基和麻省理工學院的另一位教授佩普特合作著作：《感知機：計算幾何學》（Perceptrons: An Introduction to Computational Geometry)。在書中，明斯基和佩普特證明單層神經(jīng)網(wǎng)絡不能解決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）的博士論文證明了在神經(jīng)網(wǎng)絡多加一層，并且利用“后向傳播”（Back-propagation）學習方法，可以解決XOR問題。那時正是神經(jīng)網(wǎng)絡研究的低谷，文章不合時宜。

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

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

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

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

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

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

Hoeffding不等式

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

對于任意δ>0, Hoeffding不等式可以表示為:
更多請參考:Hoeffding不等式，集中不等式

case示例：

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

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

Connection to Learning

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

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

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

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

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

感知器的優(yōu)化目標如下式所示，w_g就是我們要求的最好的假設。
設定兩個變量，如下圖所示，圖中 f(x)表示理想目標函數(shù)，h(x)是我們預估得到的某一個目標函數(shù)，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)?；趆oeffding不等式，我們得到下面式子：

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

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

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

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

學習可行的兩個核心條件

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

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

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

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

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

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

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

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

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

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

那如果在平面上有兩個數(shù)據(jù)點x1,x2，這樣的話，假設空間H中的無數(shù)條直線可以分為4類。那依次類推，3個數(shù)據(jù)點情況下，H中最多有8類直線。4個數(shù)據(jù)點，H中最多有14類直線(注意：為什么不是16類直線)。
從上面在二維假設空間中的分析，我們可以推測到一個結論，假設空間size M是很大，但在樣本集D上，有效的假設函數(shù)數(shù)目是有限的。接下來我們將繼續(xù)推導這個有效的假設函數(shù)值。

Effective Number of Hypotheses

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

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

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


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

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

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

Growth Function

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

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

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

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

Break Point與Shatter

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

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

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

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

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

VC Bound

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

我們將成長函數(shù)的上界，設為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個點產(chǎn)生的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)=？去掉其中的一個數(shù)據(jù)點x4后，考慮到break point=3，余下數(shù)據(jù)(x1,x2,x3)的dichotomies數(shù)目不能超過B(3,3)。當擴展為(x1,x2,x3,x4)時，(x1,x2,x3)上的dichotomies只有部分被重復復制了，設被復制的dichotomies數(shù)量為a，未被復制的數(shù)量為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)

最后利用數(shù)學歸納法，可以證明得到下面的bounding function(N>k)：
這個式子顯然是多項式的，多項式的最高冪次項為：N^(k–1)。

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

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

OK，到目前為止，關于m_H(N)的推導結束?；氐絞rowth function小節(jié)提出的問題，能否用m_H(N)直接替換M?

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

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

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

VC dimension

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

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

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

k = d_vc(H) + 1

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

我們已經(jīng)分析了，對于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)更多的點。

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

一個實踐規(guī)律：VC 維與假設參數(shù)w 的自由變量數(shù)目大約相等。dVC = #free parameters。
我們將原不等式做一個改寫，如下圖所示：
上面式子中的第3項表示模型復雜度。模型越復雜，VC維大，Eout 可能距離Ein 越遠。如下圖所示，隨著d_vc的上升，E_in不斷降低，而模型復雜度不斷上升。

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

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

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

深度學習與VC維

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

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

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

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

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

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

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

小結

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

參考文獻

轉載自火光搖曳，謝謝！^^

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 前幾節(jié)課著重介紹了機器能夠學習的條件并做了詳細的推導和解釋。機器能夠學習必須滿足兩個條件： 1、假設空間H的Siz...
    紅色石頭Will閱讀 1,217評論 0贊 3
  • 自從加入STA，原本忙碌的生活節(jié)奏愈加“充實”得水也潑不進了。以前的五一假期是獻給家人的，今年把我的“第一次”獻給...
    魔力演講閱讀 532評論 0贊 3
  • 【湖濱初見】 前一夜我總是睡不好。一墻之隔的牲畜也仍在依偎入夢，一里以外的幾幢影影綽綽的矮屋在月光下看不真切...
    烤柿君閱讀 1,131評論 1贊 1
  • 對孩子，要“溫和而堅定”！孩子做錯任何事情都不要輕易動怒（一旦發(fā)火，孩子就會知道你發(fā)火的底線，并會不斷挑戰(zhàn)你的底線...
    根本源閱讀 156評論 0贊 0
  • 我的朋友張君自稱是美國“克萊登大學”的博士（雖然我從未發(fā)現(xiàn)這所學校的具體地址），尤其對當代藝術獨具見解，經(jīng)常邀請我...
    伯鐸閱讀 799評論 0贊 1

友情鏈接更多精彩內容