原文鏈接：解讀機器學習基礎概念：VC維來去

?

??????? 作者：vincentyao

目錄：

• 說說歷史
• 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的泛化界。

......................................

..............................................

..............................................

?

?

深度學習與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

?

后記：

??? ? ? 不管是深度學習還是淺層組合學習，其本質上是人力抽取規則的堆積固化，只是DL的彈性和復用性更強，且融合消融較小，且可以貌似無邊界擴充。不可迷戀VC維，系統的完備性不能以底層的參數來表述，因為可操控性極差，遠離直觀是科學最危險的表達方式。

總結

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

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