上一節(jié)課芝加，我們主要探討了當M的數(shù)值大小對機器學習的影響。如果M很大，那么就不能保證機器學習有很好的泛化能力癞谒，所以問題轉換為驗證M有限藤滥，即最好是按照多項式成長鳖粟。然后通過引入了成長函數(shù)mH(N)和dichotomy以及break point的概念，提出2D perceptrons的成長函數(shù)mH(N)是多項式級別的猜想拙绊。這就是本節(jié)課將要深入探討和證明的內容向图。
我們先回顧一下上節(jié)課的內容标沪，四種成長函數(shù)與break point的關系：
下面引入一個例子榄攀，如果k=2，那么當N取不同值的時候金句，計算其成長函數(shù)mH(N)是多少檩赢。很明顯，當N=1時违寞，mH(N)=2,贞瞒；當N=2時偶房，由break point為2可知，任意兩點都不能被shattered（shatter的意思是對N個點憔狞，能夠分解為2^N種dichotomies）蝴悉；mH(N)最大值只能是3；當N=3時瘾敢，簡單繪圖分析可得其mH(N)=4拍冠，即最多只有4種dichotomies。
所以簇抵，我們發(fā)現(xiàn)當N>k時庆杜，break point限制了mH(N)值的大小，也就是說影響成長函數(shù)mH(N)的因素主要有兩個：
1. 抽樣數(shù)據集N
2. break point k（這個變量確定了假設的類型）
那么碟摆，如果給定N和k晃财，能夠證明其mH(N)的最大值的上界是多項式的，則根據霍夫丁不等式典蜕，就能用mH(N)代替M断盛，得到機器學習是可行的。所以愉舔，證明mH(N)的上界是poly(N)钢猛，是我們的目標。
二轩缤、Bounding Function: Basic Cases
現(xiàn)在命迈，我們引入一個新的函數(shù)：bounding function，B(N,k)火的。Bound Function指的是當break point為k的時候壶愤，成長函數(shù)mH(N)可能的最大值。也就是說B(N,k)是mH(N)的上界馏鹤，對應mH(N)最多有多少種dichotomy征椒。那么，我們新的目標就是證明：
這里值得一提的是湃累，B(N,k)的引入不考慮是1D postive intrervals問題還是2D perceptrons問題勃救，而只關心成長函數(shù)的上界是多少，從而簡化了問題的復雜度脱茉。
求解B(N,k)的過程十分巧妙：
當k=1時剪芥，B(N,1)恒為1垄开。
當N < k時琴许，根據break point的定義，很容易得到B(N,k)=2^N溉躲。
當N = k時榜田，此時N是第一次出現(xiàn)不能被shatter的值益兄，所以最多只能有2^N?1個dichotomies，則B(N,k)=2^N?1箭券。
到此净捅，bounding function的表格已經填了一半了，對于最常見的N>k的情況比較復雜辩块，推導過程下一小節(jié)再詳細介紹蛔六。
三、Bounding Function: Inductive Cases
N > k的情況較為復雜废亭，下面給出推導過程：
以B(4,3)為例国章，首先想著能否構建B(4,3)與B(3,x)之間的關系。
首先豆村，把B(4,3)所有情況寫下來液兽，共有11組。也就是說再加一種dichotomy掌动，任意三點都能被shattered四啰，11是極限。
對這11種dichotomy分組粗恢，目前分成兩組柑晒，分別是orange和purple，orange的特點是适滓，x1,x2和x3是一致的敦迄，x4不同并成對，例如1和5凭迹，2和8等罚屋，purple則是單一的，x1,x2,x3都不同嗅绸，如6,7,9三組脾猛。
將Orange去掉x4后去重得到4個不同的vector并成為α，相應的purple為β鱼鸠。那么B(4,3)=2α+β猛拴，這個是直接轉化。緊接著蚀狰，由定義愉昆，B(4,3)是不能允許任意三點shatter的，所以由α和β構成的所有三點組合也不能shatter（alpha經過去重）麻蹋，即α+β≤B(3,3)跛溉。
另一方面，由于α中x4是成對存在的，且α是不能被任意三點shatter的芳室，則能推導出α是不能被任意兩點shatter的专肪。這是因為，如果α是不能被任意兩點shatter堪侯，而x4又是成對存在的嚎尤，那么x1、x2伍宦、x3芽死、x4組成的α必然能被三個點shatter。這就違背了條件的設定次洼。這個地方的推導非常巧妙收奔，也解釋了為什么會這樣分組。此處得到的結論是α≤B(3,2)
由此得出B(4,3)與B(3,x)的關系為：
最后滓玖，推導出一般公式為：
根據推導公式坪哄，下表給出B(N,K)值
根據遞推公式，推導出B(N,K)滿足下列不等式：
上述不等式的右邊是最高階為k-1的N多項式势篡，也就是說成長函數(shù)mH(N)的上界B(N,K)的上界滿足多項式分布poly(N)翩肌，這就是我們想要得到的結果。
得到了mH(N)的上界B(N,K)的上界滿足多項式分布poly(N)后禁悠，我們回過頭來看看之前介紹的幾種類型它們的mH(N)與break point的關系：
我們得到的結論是念祭，對于2D perceptrons，break point為k=4碍侦，mH(N)的上界是N^(k?1)粱坤。推廣一下，也就是說瓷产，如果能找到一個模型的break point站玄，且是有限大的，那么就能推斷出其成長函數(shù)mH(N)有界濒旦。
我們已經知道了成長函數(shù)的上界是poly(N)的，下一步尔邓，如果能將mH(N)代替M晾剖，代入到Hoffding不等式中，就能得到Eout≈Ein的結論：
實際上并不是簡單的替換就可以了梯嗽，正確的表達式為：
該推導的證明比較復雜齿尽，我們可以簡單概括為三個步驟來證明：
這部分內容，我也只能聽個大概內容灯节，對具體的證明過程有興趣的童鞋可以自行研究一下循头，研究的結果記得告訴一下我哦缠俺。
最終，我們通過引入成長函數(shù)mH贷岸，得到了一個新的不等式，稱為Vapnik-Chervonenkis(VC) bound：
對于2D perceptrons磷雇，它的break point是4偿警，那么成長函數(shù)mH(N)=O(N^3)。所以唯笙，我們可以說2D perceptrons是可以進行機器學習的螟蒸，只要找到hypothesis能讓Ein≈0，就能保證Ein≈Eout崩掘。
本節(jié)課我們主要介紹了只要存在break point，那么其成長函數(shù)mH(N)就滿足poly(N)苞慢。推導過程是先引入mH(N)的上界B(N,k)诵原，B(N,k)的上界是N的k-1階多項式，從而得到mH(N)的上界就是N的k-1階多項式挽放。然后绍赛，我們通過簡單的三步證明，將mH(N)代入了Hoffding不等式中辑畦，推導出了Vapnik-Chervonenkis(VC) bound吗蚌，最終證明了只要break point存在，那么機器學習就是可行的纯出。
原文CSDN博客地址：
臺灣大學林軒田機器學習基石課程學習筆記6 -- Theory of Generalization
注明：
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程蚯妇。
