前幾節課着重介紹了機器能夠學習的條件并做了詳細的推導和解釋。機器能夠學習必須滿足兩個條件：
假設空間H的Size M是有限的，即當N足夠大的時候，那麼對于假設空間中任意一個假設g，E_{out}\approx E_{in}。
利用算法A從假設空間H中，挑選一個g，使E_{in}(g)\approx0，則E_{out}\approx0。
這兩個條件，正好對應着test和trian兩個過程。train的目的是使損失期望E_{in}(g)\approx0；test的目的是使将算法用到新的樣本時的損失期望也盡可能小，即E_{out}\approx0。
正因為如此，上次課引入了break point，并推導出隻要break point存在，則M有上界，一定存在E_{out}\approx E_{in}。
本次筆記主要介紹VC Dimension的概念。同時也是總結VC Dimension與E_{in}(g)\approx0，E_{out}\approx0，Model Complexity Penalty（下面會講到）的關系。
首先，我們知道如果一個假設空間H有break point k，那麼它的成長函數是有界的，它的上界稱為Bound function。根據數學歸納法，Bound function也是有界的，且上界為N^{k-1}。從下面的表格可以看出，N(k-1)比B(N,k)松弛很多。
則根據上一節課的推導，VC bound就可以轉換為：
這樣，不等式隻與k和N相關了，一般情況下樣本N足夠大，是以我們隻考慮k值。有如下結論：
若假設空間H有break point k，且N足夠大，則根據VC bound理論，算法有良好的泛化能力
在假設空間中選擇一個矩g，使E_{in}\approx0，則其在全集資料中的錯誤率會較低
下面介紹一個新的名詞：VC Dimension。VC Dimension就是某假設集H能夠shatter的最多inputs的個數，即最大完全正确的分類能力。（注意，隻要存在一種分布的inputs能夠正确分類也滿足）。
shatter的英文意思是“粉碎”，也就是說對于inputs的所有情況都能列舉出來。例如對N個輸入，如果能夠将2^N種情況都列出來，則稱該N個輸入能夠被假設集H shatter。
根據之前break point的定義：假設集不能被shatter任何分布類型的inputs的最少個數。則VC Dimension等于break point的個數減一。
現在，我們回顧一下之前介紹的四種例子，它們對應的VC Dimension是多少：
用d_{vc}代替k，那麼VC bound的問題也就轉換為與d_{vc}和N相關了。同時，如果一個假設集H的d_{vc}确定了，則就能滿足機器能夠學習的第一個條件E_{out}\approx E_{in}，與算法、樣本資料分布和目标函數都沒有關系。
回顧一下我們之前介紹的2D下的PLA算法，已知Perceptrons的k=4，即d_{vc}=3。根據VC Bound理論，當N足夠大的時候，E_{out}(g)\approx E_{in}(g)。如果找到一個g，使E_{in}(g)\approx 0，那麼就能證明PLA是可以學習的。
這是在2D情況下，那如果是多元的Perceptron，它對應的d_{vc}又等于多少呢？
已知在1D Perceptron，d_{vc}=2，在2D Perceptrons，d_{vc}=3，那麼我們有如下假設：d_{vc}=d+1，其中d為維數。
要證明的話，隻需分兩步證明：
d_{vc}\geq d+1
d_{vc}\leq d+1
首先證明第一個不等式：d_{vc}\geq d+1。
在d維裡，我們隻要找到某一類的d+1個inputs可以被shatter的話，那麼必然得到d_{vc}\geq d+1。是以，我們有意構造一個d維的矩陣X能夠被shatter就行。X是d維的，有d+1個inputs，每個inputs加上第零個次元的常數項1，得到X的矩陣：
矩陣中，每一行代表一個inputs，每個inputs是d+1維的，共有d+1個inputs。這裡構造的XX很明顯是可逆的。shatter的本質是假設空間H對X的所有情況的判斷都是對的，即總能找到權重W，滿足X\ast W=y，W=X^{-1}\ast y。由于這裡我們構造的矩陣X的逆矩陣存在，那麼d維的所有inputs都能被shatter，也就證明了第一個不等式。
然後證明第二個不等式：d_{vc}\leq d+1。
在d維裡，如果對于任何的d+2個inputs，一定不能被shatter，則不等式成立。我們構造一個任意的矩陣X，其包含d+2個inputs，該矩陣有d+1列，d+2行。這d+2個向量的某一列一定可以被另外d+1個向量線性表示，例如對于向量X_{d+2}，可表示為：
X_{d+2}=a_1\ast X_1+a_2\ast X_2+\cdots+a_{d+1}\ast X_{d+1}
其中，假設a1>0，a2,⋯,ad+1<0
那麼如果X_1是正類，X_2,\cdots,X_{d+1}均為負類，則存在W，得到如下表達式： X_{d+2}\ast W=a_1\ast X_1\ast W+a_2\ast X_2\ast W+⋯\cdots+a_{d+1}\ast X_{d+1}\ast W>0
因為其中藍色項大于0，代表正類；紅色項小于0，代表負類。所有對于這種情況，X_d+2一定是正類，無法得到負類的情況。也就是說，d+2個inputs無法被shatter。證明完畢！
綜上證明可得d_{vc}=d+1。
上節公式中W又名features，即自由度。自由度是可以任意調節的，如同上圖中的旋鈕一樣，可以調節。VC Dimension代表了假設空間的分類能力，即反映了H的自由度，産生dichotomy的數量，也就等于features的個數，但也不是絕對的。
例如，對2D Perceptrons，線性分類，d_{vc}=3，則W=\{w_0,w_1,w_2\}，也就是說隻要3個features就可以進行學習，自由度為3。
介紹到這，我們發現M與d_{vc}是成正比的，進而得到如下結論：
下面，我們将更深入地探讨VC Dimension的意義。首先，把VC Bound重新寫到這裡：
根據之前的泛化不等式，如果|E_{in}-E_{out}|>\epsilon，即出現bad壞的情況的機率最大不超過δ。那麼反過來，對于good好的情況發生的機率最小為1-\delta，則對上述不等式進行重新推導：
ϵ表現了假設空間H的泛化能力，ϵ越小，泛化能力越大。
至此，已經推導出泛化誤差E_{out}的邊界，因為我們更關心其上界（E_{out}可能的最大值），即：
上述不等式的右邊第二項稱為模型複雜度，其模型複雜度與樣本數量N、假設空間H(d_{vc})、ϵ有關。E_{out}由E_{in}共同決定。下面繪出E_{out}、model complexity、E_{in}随d_{vc}變化的關系：
通過該圖可以得出如下結論：
d_{vc}越大，E_{in}越小，Ω越大（複雜）。
d_{vc}越小，E_{in}越大，Ω越小（簡單）。
随着d_{vc}增大，E_{out}會先減小再增大。
是以，為了得到最小的E_{out}，不能一味地增大d_{vc}以減小E_{in}，因為E_{in}太小的時候，模型複雜度會增加，造成E_{out}變大。也就是說，選擇合适的d_{vc}，選擇的features個數要合适。
下面介紹一個概念：樣本複雜度（Sample Complexity）。如果標明d_{vc}，樣本資料D選擇多少合适呢？通過下面一個例子可以幫助我們了解：
通過計算得到N=29300，剛好滿足δ=0.1的條件。N大約是d_{vc}的10000倍。這個數值太大了，實際中往往不需要這麼多的樣本數量，大概隻需要d_{vc}的10倍就夠了。N的理論值之是以這麼大是因為VC Bound 過于寬松了，我們得到的是一個比實際大得多的上界。
值得一提的是，VC Bound是比較寬松的，而如何收緊它卻不是那麼容易，這也是機器學習的一大難題。但是，令人欣慰的一點是，VC Bound基本上對所有模型的寬松程度是基本一緻的，是以，不同模型之間還是可以橫向比較。進而，VC Bound寬松對機器學習的可行性還是沒有太大影響。
本節課主要介紹了VC Dimension的概念就是最大的non-break point。然後，我們得到了Perceptrons在d次元下的VC Dimension是d+1。接着，我們在實體意義上，将d_{vc}與自由度聯系起來。最終得出結論d_{vc}不能過大也不能過小。選取合适的值，才能讓E_{out}足夠小，使假設空間H具有良好的泛化能力。
注明：
文章中所有的圖檔均來自中國台灣大學林軒田《機器學習基石》課程