前幾節(jié)課著重介紹了機器能夠?qū)W習的條件并做了詳細的推導和解釋。機器能夠?qū)W習必須滿足兩個條件：
1逮诲、假設空間H的Size M是有限的，即當N足夠大的時候，那么對于假設空間中任意一個假設g虑凛，Eout≈Ein。
2软啼、利用算法A從假設空間H中桑谍，挑選一個g，使Ein(g)≈0祸挪，則Eout≈0锣披。
這兩個條件，正好對應著test和trian兩個過程贿条。train的目的是使損失期望Ein(g)≈0雹仿；test的目的是使將算法用到新的樣本時的損失期望也盡可能小，即Eout≈0整以。
正因為如此胧辽，上次課引入了break point，并推導出只要break point存在公黑，則M有上界邑商，一定存在Eout≈Ein。
本次筆記主要介紹VC Dimension的概念凡蚜。同時也是總結(jié)VC Dimension與Ein(g)≈0人断，Eout≈0，Model Complexity Penalty（下面會講到）的關(guān)系朝蜘。
一恶迈、Definition of VC Dimension
首先，我們知道如果一個假設空間H有break point k芹务，那么它的成長函數(shù)是有界的蝉绷，它的上界稱為Bound function鸭廷。根據(jù)數(shù)學歸納法，Bound function也是有界的熔吗，且上界為Nk?1辆床。從下面的表格可以看出，N(k?1)比B(N,k)松弛很多桅狠。
則根據(jù)上一節(jié)課的推導讼载，VC bound就可以轉(zhuǎn)換為：
這樣，不等式只與k和N相關(guān)了中跌，一般情況下樣本N足夠大咨堤，所以我們只考慮k值。有如下結(jié)論：
1漩符、若假設空間H有break point k一喘，且N足夠大，則根據(jù)VC bound理論嗜暴，算法有良好的泛化能力
2凸克、在假設空間中選擇一個矩g，使Ein≈0闷沥，則其在全集數(shù)據(jù)中的錯誤率會較低
下面介紹一個新的名詞：VC Dimension萎战。VC Dimension就是某假設集H能夠shatter的最多inputs的個數(shù)，即最大完全正確的分類能力舆逃。（注意蚂维，只要存在一種分布的inputs能夠正確分類也滿足）。
shatter的英文意思是“粉碎”路狮，也就是說對于inputs的所有情況都能列舉出來虫啥。例如對N個輸入，如果能夠?qū)?N種情況都列出來奄妨，則稱該N個輸入能夠被假設集H shatter孝鹊。
根據(jù)之前break point的定義：假設集不能被shatter任何分布類型的inputs的最少個數(shù)。則VC Dimension等于break point的個數(shù)減一展蒂。
現(xiàn)在，我們回顧一下之前介紹的四種例子苔咪，它們對應的VC Dimension是多少：
用dvc代替k锰悼，那么VC bound的問題也就轉(zhuǎn)換為與dvc和N相關(guān)了。同時团赏，如果一個假設集H的dvc確定了箕般，則就能滿足機器能夠?qū)W習的第一個條件Eout≈Ein，與算法舔清、樣本數(shù)據(jù)分布和目標函數(shù)都沒有關(guān)系丝里。
二曲初、VC Dimension of Perceptrons
回顧一下我們之前介紹的2D下的PLA算法，已知Perceptrons的k=4杯聚，即dvc=3臼婆。根據(jù)VC Bound理論，當N足夠大的時候幌绍，Eout(g)≈Ein(g)颁褂。如果找到一個g，使Ein(g)≈0傀广，那么就能證明PLA是可以學習的颁独。
這是在2D情況下，那如果是多維的Perceptron伪冰，它對應的dvc又等于多少呢誓酒？
已知在1D Perceptron，dvc=2贮聂，在2D Perceptrons靠柑，dvc=3，那么我們有如下假設：dvc=d+1寂汇，其中d為維數(shù)病往。
要證明的話，只需分兩步證明：
1骄瓣、dvc≥d+1
2停巷、dvc≤d+1
首先證明第一個不等式：dvc≥d+1。
在d維里榕栏，我們只要找到某一類的d+1個inputs可以被shatter的話畔勤，那么必然得到dvc≥d+1。所以扒磁，我們有意構(gòu)造一個d維的矩陣X能夠被shatter就行庆揪。X是d維的，有d+1個inputs妨托，每個inputs加上第零個維度的常數(shù)項1缸榛，得到X的矩陣：
矩陣中，每一行代表一個inputs兰伤，每個inputs是d+1維的内颗，共有d+1個inputs。這里構(gòu)造的X很明顯是可逆的敦腔。shatter的本質(zhì)是假設空間H對X的所有情況的判斷都是對的均澳，即總能找到權(quán)重W，滿足X?W=y，W=X?1?y找前。由于這里我們構(gòu)造的矩陣X的逆矩陣存在糟袁，那么d維的所有inputs都能被shatter，也就證明了第一個不等式躺盛。
然后證明第二個不等式：dvc≤d+1项戴。
在d維里，如果對于任何的d+2個inputs颗品，一定不能被shatter肯尺，則不等式成立。我們構(gòu)造一個任意的矩陣X躯枢，其包含d+2個inputs则吟，該矩陣有d+1列，d+2行锄蹂。這d+2個向量的某一列一定可以被另外d+1個向量線性表示氓仲，例如對于向量Xd+2，可表示為：
Xd+2=a1?X1+a2?X2+?+ad?Xd
其中得糜，假設a1>0敬扛，a2,?,ad<0.
那么如果X1是正類，X2,?,Xd均為負類朝抖，則存在W啥箭，得到如下表達式：
Xd+2?W=a1?X1?W+a2?X2?W+?+ad?Xd?W>0
因為其中藍色項大于0，代表正類治宣；紅色項小于0急侥，代表負類。所有對于這種情況侮邀，Xd+2一定是正類坏怪，無法得到負類的情況。也就是說绊茧，d+2個inputs無法被shatter铝宵。證明完畢！
綜上證明可得dvc=d+1华畏。
三鹏秋、Physical Intuition VC Dimension
上節(jié)公式中W又名features，即自由度亡笑。自由度是可以任意調(diào)節(jié)的拼岳，如同上圖中的旋鈕一樣，可以調(diào)節(jié)况芒。VC Dimension代表了假設空間的分類能力，即反映了H的自由度，產(chǎn)生dichotomy的數(shù)量绝骚，也就等于features的個數(shù)耐版，但也不是絕對的。
例如压汪，對2D Perceptrons粪牲，線性分類，dvc=3止剖，則W={w0,w1,w2}腺阳，也就是說只要3個features就可以進行學習，自由度為3穿香。
介紹到這亭引，我們發(fā)現(xiàn)M與dvc是成正比的，從而得到如下結(jié)論：
下面焙蚓，我們將更深入地探討VC Dimension的意義。首先洒宝，把VC Bound重新寫到這里：
根據(jù)之前的泛化不等式购公，如果|Ein?Eout|>?，即出現(xiàn)bad壞的情況的概率最大不超過δ雁歌。那么反過來宏浩，對于good好的情況發(fā)生的概率最小為1?δ，則對上述不等式進行重新推導：
?表現(xiàn)了假設空間H的泛化能力靠瞎，?越小比庄，泛化能力越大。
至此较坛，已經(jīng)推導出泛化誤差Eout的邊界印蔗，因為我們更關(guān)心其上界（Eout可能的最大值），即：
上述不等式的右邊第二項稱為模型復雜度丑勤，其模型復雜度與樣本數(shù)量N华嘹、假設空間H(dvc)、?有關(guān)法竞。Eout由Ein共同決定耙厚。下面繪出Eout、model complexity岔霸、Ein隨dvc變化的關(guān)系：
通過該圖可以得出如下結(jié)論：
1薛躬、dvc越大，Ein越小呆细，Ω越大（復雜）型宝。
2、dvc越小，Ein越大趴酣，Ω越欣媸鳌（簡單）。
3岖寞、隨著dvc增大抡四，Eout會先減小再增大。
所以仗谆，為了得到最小的Eout指巡，不能一味地增大dvc以減小Ein，因為Ein太小的時候隶垮，模型復雜度會增加藻雪，造成Eout變大。也就是說岁疼，選擇合適的dvc阔涉，選擇的features個數(shù)要合適。
下面介紹一個概念：樣本復雜度（Sample Complexity）捷绒。如果選定dvc瑰排，樣本數(shù)據(jù)D選擇多少合適呢？通過下面一個例子可以幫助我們理解：
通過計算得到N=29300暖侨，剛好滿足δ=0.1的條件椭住。N大約是dvc的10000倍。這個數(shù)值太大了字逗，實際中往往不需要這么多的樣本數(shù)量京郑，大概只需要dvc的10倍就夠了。N的理論值之所以這么大是因為VC Bound 過于寬松了葫掉，我們得到的是一個比實際大得多的上界些举。
值得一提的是，VC Bound是比較寬松的俭厚，而如何收緊它卻不是那么容易户魏，這也是機器學習的一大難題。但是挪挤，令人欣慰的一點是叼丑，VC Bound基本上對所有模型的寬松程度是基本一致的，所以扛门，不同模型之間還是可以橫向比較鸠信。從而，VC Bound寬松對機器學習的可行性還是沒有太大影響论寨。
本節(jié)課主要介紹了VC Dimension的概念就是最大的non-break point爽茴。然后，我們得到了Perceptrons在d維度下的VC Dimension是d+1贞铣。接著闹啦，我們在物理意義上，將dvc與自由度聯(lián)系起來辕坝。最終得出結(jié)論dvc不能過大也不能過小。選取合適的值荐健，才能讓Eout足夠小酱畅，使假設空間H具有良好的泛化能力。
原文CSDN博客地址：
臺灣大學林軒田機器學習基石課程學習筆記7 -- The VC Dimension
注明：
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程江场。
