# 7 -- The VC Dimension
前幾節課著重介紹了機器能夠學習的條件并做了詳細的推導和解釋。機器能夠學習必須滿足兩個條件:
* **假設空間H的Size M是有限的,即當N足夠大的時候,那么對于假設空間中任意一個假設g,**。
* **利用算法A從假設空間H中,挑選一個g,使,則**。
這兩個條件,正好對應著test和trian兩個過程。train的目的是使損失期望;test的目的是使將算法用到新的樣本時的損失期望也盡可能小,即。
正因為如此,上次課引入了break point,并推導出只要break point存在,則M有上界,一定存在。
本次筆記主要介紹VC Dimension的概念。同時也是總結VC Dimension與,,Model Complexity Penalty(下面會講到)的關系。
### **一、Definition of VC Dimension**
首先,我們知道如果一個假設空間H有break point k,那么它的成長函數是有界的,它的上界稱為Bound function。根據數學歸納法,Bound function也是有界的,且上界為。從下面的表格可以看出,比B(N,k)松弛很多。

則根據上一節課的推導,VC bound就可以轉換為:

這樣,不等式只與k和N相關了,一般情況下樣本N足夠大,所以我們只考慮k值。有如下結論:
* **若假設空間H有break point k,且N足夠大,則根據VC bound理論,算法有良好的泛化能力**
* **在假設空間中選擇一個矩g,使,則其在全集數據中的錯誤率會較低**

下面介紹一個新的名詞:VC Dimension。VC Dimension就是某假設集H能夠shatter的最多inputs的個數,即最大完全正確的分類能力。(注意,只要存在一種分布的inputs能夠正確分類也滿足)。
shatter的英文意思是“粉碎”,也就是說對于inputs的所有情況都能列舉出來。例如對N個輸入,如果能夠將種情況都列出來,則稱該N個輸入能夠被假設集H shatter。
根據之前break point的定義:假設集不能被shatter任何分布類型的inputs的最少個數。則VC Dimension等于break point的個數減一。

現在,我們回顧一下之前介紹的四種例子,它們對應的VC Dimension是多少:

用代替k,那么VC bound的問題也就轉換為與和N相關了。同時,如果一個假設集H的確定了,則就能滿足機器能夠學習的第一個條件,與算法、樣本數據分布和目標函數都沒有關系。

### **二、VC Dimension of Perceptrons**
回顧一下我們之前介紹的2D下的PLA算法,已知Perceptrons的k=4,即。根據VC Bound理論,當N足夠大的時候,。如果找到一個g,使,那么就能證明PLA是可以學習的。

這是在2D情況下,那如果是多維的Perceptron,它對應的又等于多少呢?
已知在1D Perceptron,,在2D Perceptrons,,那么我們有如下假設:,其中d為維數。
要證明的話,只需分兩步證明:
* 
* 

首先證明第一個不等式:。
在d維里,我們只要找到某一類的d+1個inputs可以被shatter的話,那么必然得到。所以,我們有意構造一個d維的矩陣能夠被shatter就行。是d維的,有d+1個inputs,每個inputs加上第零個維度的常數項1,得到的矩陣:

矩陣中,每一行代表一個inputs,每個inputs是d+1維的,共有d+1個inputs。這里構造的很明顯是可逆的。shatter的本質是假設空間H對的所有情況的判斷都是對的,即總能找到權重W,滿足,。由于這里我們構造的矩陣的逆矩陣存在,那么d維的所有inputs都能被shatter,也就證明了第一個不等式。

然后證明第二個不等式:。
在d維里,如果對于任何的d+2個inputs,一定不能被shatter,則不等式成立。我們構造一個任意的矩陣,其包含d+2個inputs,該矩陣有d+1列,d+2行。這d+2個向量的某一列一定可以被另外d+1個向量線性表示,例如對于向量,可表示為:
其中,假設,.
那么如果是正類,均為負類,則存在,得到如下表達式:
<font color="#0000ff"></font>+<font color="#ff0000"></font>++<font color="#ff0000"></font>
因為其中藍色項大于0,代表正類;紅色項小于0,代表負類。所有對于這種情況,一定是正類,無法得到負類的情況。也就是說,d+2個inputs無法被shatter。證明完畢!

綜上證明可得。
### **三、Physical Intuition VC Dimension**

上節公式中又名features,即自由度。自由度是可以任意調節的,如同上圖中的旋鈕一樣,可以調節。VC Dimension代表了假設空間的分類能力,即反映了H的自由度,產生dichotomy的數量,也就等于features的個數,但也不是絕對的。

例如,對2D Perceptrons,線性分類,,則,也就是說只要3個features就可以進行學習,自由度為3。
介紹到這,我們發現M與是成正比的,從而得到如下結論:

### **四、Interpreting VC Dimension**
下面,我們將更深入地探討VC Dimension的意義。首先,把VC Bound重新寫到這里:

根據之前的泛化不等式,如果,即出現bad壞的情況的概率最大不超過。那么反過來,對于good好的情況發生的概率最小為,則對上述不等式進行重新推導:

表現了假設空間H的泛化能力,越小,泛化能力越大。

至此,已經推導出泛化誤差的邊界,因為我們更關心其上界(可能的最大值),即:

上述不等式的右邊第二項稱為模型復雜度,其模型復雜度與樣本數量N、假設空間H()、有關。由共同決定。下面繪出、model complexity、隨變化的關系:

通過該圖可以得出如下結論:
* **越大,越小,越大(復雜)**。
* **越小,越大,越小(簡單)**。
* **隨著增大,會先減小再增大**。
所以,為了得到最小的,不能一味地增大以減小,因為太小的時候,模型復雜度會增加,造成變大。也就是說,選擇合適的,選擇的features個數要合適。
下面介紹一個概念:樣本復雜度(Sample Complexity)。如果選定,樣本數據D選擇多少合適呢?通過下面一個例子可以幫助我們理解:

通過計算得到N=29300,剛好滿足的條件。N大約是的10000倍。這個數值太大了,實際中往往不需要這么多的樣本數量,大概只需要的10倍就夠了。N的理論值之所以這么大是因為VC Bound 過于寬松了,我們得到的是一個比實際大得多的上界。

值得一提的是,VC Bound是比較寬松的,而如何收緊它卻不是那么容易,這也是機器學習的一大難題。但是,令人欣慰的一點是,VC Bound基本上對所有模型的寬松程度是基本一致的,所以,不同模型之間還是可以橫向比較。從而,VC Bound寬松對機器學習的可行性還是沒有太大影響。
### **五、總結**
本節課主要介紹了VC Dimension的概念就是最大的non-break point。然后,我們得到了Perceptrons在d維度下的VC Dimension是d+1。接著,我們在物理意義上,將與自由度聯系起來。最終得出結論不能過大也不能過小。選取合適的值,才能讓足夠小,使假設空間H具有良好的泛化能力。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale