Tips：所有沒(méi)有進(jìn)行解釋說(shuō)明的符號(hào)含義均參照之前的章節(jié)Lec～
上一節(jié)介紹了級(jí)聯(lián)上限存在過(guò)分估計(jì)的問(wèn)題诈乒，我們欲尋求一個(gè)多項(xiàng)式mH（N）取代M捡多，并給出了成長(zhǎng)函數(shù)、break point的定義款侵，這節(jié)將證明如果存在break point 馋艺，成長(zhǎng)函數(shù)會(huì)是多項(xiàng)式型的。
Lec 6：Theory of Generalization
先回顧一下四種成長(zhǎng)函數(shù)嘉栓，成長(zhǎng)函數(shù)mH（N）代表dichotomies最大數(shù)量：
1宏榕、Restrict of Break Point
先通過(guò)一個(gè)小栗子感受一下break point會(huì)對(duì)dichotomies的數(shù)量有怎么樣的限制？
在k=2的情況下：
N = 1：顯然mH（N）=2侵佃；
N = 2：mH（N）＜4麻昼，所以最多有3個(gè)dichotomies；
N = 3：k = 2代表不能shatter任意兩個(gè)data趣钱，我們分步驟來(lái)看涌献，
1）顯然胚宦，只有1個(gè)dichotomy時(shí)首有，或有2個(gè)dichotomies時(shí)燕垃，，或有3個(gè)dichotomies時(shí)井联，一定不會(huì)shatter任意兩個(gè)data：
2）但是卜壕，當(dāng)有4個(gè)dichotomies時(shí)，就可能會(huì)shatter兩個(gè)data烙常，如下圖中x2和x3 shattered（可以這樣理解轴捎，shatter就是x2和x3所有可能的二元組合都能出現(xiàn)）
不過(guò)也會(huì)存在4個(gè)dichotomies時(shí)不shatter兩個(gè)data的情況蚕脏，如：
3）接著上面4個(gè)dichotomies不shatter的情況，繼續(xù)加入dichotomy驼鞭，看5個(gè)dichotomies時(shí)會(huì)怎樣秦驯？x1、x2挣棕、x3一共有8種二元組合译隘，所以此時(shí)5個(gè)dichotomies存在3種情況，發(fā)現(xiàn)分別都會(huì)shatter：
所以洛心，在N=3固耘，k=2時(shí)，最多會(huì)有4個(gè)dichotomies.
N = 2時(shí)词身，最多有3個(gè)厅目，比4小一點(diǎn)；N = 3時(shí)偿枕，最多有4個(gè)璧瞬，比8小的多一點(diǎn)！
似乎當(dāng)N＞k時(shí)渐夸，break point k 會(huì)限制mH（N）最大值的大朽惋薄！
所以如果證明存在k限制的mH（N）最大值≤poly（N）就可以說(shuō)明mH（N）是多項(xiàng)式型的墓塌。
2瘟忱、Bounding Function：basic cases
定義一個(gè)新的函數(shù)B（N，K）苫幢，maximum possible mH（N）when break point = k.
bounding function 與 H 的細(xì)節(jié)無(wú)關(guān)访诱，只需要知道k.（個(gè)人是這樣理解的，dichotomies的數(shù)量其實(shí)就是二元組合的種類(lèi)韩肝，h不同時(shí)触菜，可能得到的dichotomies會(huì)有所不同，但是這里我們是表示最大的mH（N）哀峻，所以可以拋開(kāi)H的細(xì)節(jié)涡相，專注于二元組合的最大值哲泊，即只需要知道k）例如B（N，3）可以bound住positive intervals（k=3）催蝗，也可以bound住1D perceptron（k = 3）切威。
所以我們的new goal 是證明 B（N，k）≤ poly（N）丙号？
先列出我們已經(jīng)知道的B（N先朦，k）的值。首先由上節(jié)已知（2,2）=3犬缨，（3,2）=4喳魏；
然后 k＞N時(shí)，會(huì)shatter怀薛，則B（N截酷，k）= 2的N次方；
還有就是對(duì)角線上面的值乾戏，N=k時(shí)迂苛，（2，2）取3時(shí)是選了一個(gè)比2的N次方小1的值（一定比2的N次方小鼓择，我們挑了一個(gè)比2的N次方小的數(shù)中最大的一個(gè)）三幻，其他對(duì)角值也如此取呐能；
最后是第一列的值念搬，一定都是1.至此，我們得到了B（N摆出，k）表上一多半的值朗徊！其他值繼續(xù)看下一節(jié)。
3偎漫、Bounding Function：inductive cases
我們要補(bǔ)全上一節(jié)的表爷恳。
先考慮B（4,3）這一格。猜測(cè)：B（4象踊，3）只是比B（3温亲，3）多了一個(gè)點(diǎn)，也許它們之間有著什么聯(lián)系杯矩？栈虚！
先給出B（4,3）的結(jié)果（這個(gè)結(jié)果完全可以用代碼全遍歷一遍得出），結(jié)果是11：
下面看如何把B（4,3）reduce成B（3,3）史隆？
先重新排列B（4,3）的dichotomies魂务，如下圖所示。可以看出橘色部分的x1粘姜、x2蚣驼、x3是“成雙成對(duì)”存在的，紫色部分是形單影只的相艇。可以表示B（4,3） = 11 = 2 α + β .
下面就是見(jiàn)證奇跡的時(shí)刻纯陨！
遮掉x4坛芽，只剩下x1、x2翼抠、x3咙轩，在(x1,x2,x3)上會(huì)有α + β個(gè)dichotomies，B（4,3）任意3個(gè)點(diǎn)都不會(huì)shatter阴颖，那么α + β個(gè)dichotomies也就不會(huì)shatter x1活喊、x2、x3量愧，所以 α + β ≤ B（3,3）
只看x1 x2 x3的橘色部分钾菊，應(yīng)該任意兩個(gè)點(diǎn)不能shatter，why偎肃？假設(shè)此時(shí) x1 x2 shatter煞烫，那么x1 x2 與 x4組合起來(lái)就會(huì)存在3個(gè)點(diǎn)shatter，就不滿足B（4,3）累颂，所以α不能shatter橘色部分的任意兩個(gè)點(diǎn)滞详，可以得出 α ≤ B（3,2）
綜合上述兩個(gè)結(jié)論，可以得出 B（4,3）= 2α + β = （α + β）+ α ≤ B（3,3）+ B（3,2）紊馏，這樣我們就得到了Bounding Function的upper bound 料饥！（回想一下：從成長(zhǎng)函數(shù)，到成長(zhǎng)函數(shù)的上限朱监，再到上限的上限岸啡，哈哈哈哈~~~）
給出一個(gè)結(jié)論：
B（N，k）的最高次項(xiàng)是k-1次的赫编，這個(gè)結(jié)論可以通過(guò)數(shù)學(xué)歸納法inductive證明凰狞。實(shí)際上≤可以是=，這需要更復(fù)雜的數(shù)學(xué)證明沛慢，這里不給出赡若，我們只需要明白B（N，k）會(huì)被poly（N）bound住 if break point exist :)
4团甲、VC bound
已經(jīng)證明了mH（N）的上限是多項(xiàng)式逾冬，那我們是不是就可以替換M了呢？
并沒(méi)有這么簡(jiǎn)單，實(shí)際上會(huì)是下圖這樣的身腻，多了一些常數(shù)：
這個(gè)的證明很有技巧性产还，我們不深入探究，只介紹這幾個(gè)常數(shù)的含義嘀趟。（首先承認(rèn)這部分筆者看的也不是很懂脐区，希望得到大家指點(diǎn)~互相學(xué)習(xí)）
step 1：replace Eout by Ein '
有了上節(jié)的bound可以知道Ein（h）是有限多個(gè)，但是Eout（h）是無(wú)限多的她按。怎么辦牛隅？之前提過(guò)采樣一個(gè)大小為Ｎ的verification set D ' ?去估計(jì)Eout，稱為Ein ' 酌泰。
由上圖分布可以得出媒佣，Ein ' 和Ein 離得遠(yuǎn)的概率是 Ein和Eout離得遠(yuǎn)的概率的一半多，因此得到下式陵刹，右側(cè)式子的ε/2的1/2是數(shù)學(xué)上更強(qiáng)的約束默伍。
step 2：decompose H by kind
上面的式子是在一個(gè)h上的結(jié)論，現(xiàn)在換成kind得到在H上的結(jié)論：
插播一條舊結(jié)論：
這里有一組很形象的圖展示了union bound on hypothesis 和 union bound on kind的差別衰琐，第一張圖是霍夫丁不等式說(shuō)明對(duì)一個(gè)固定的h來(lái)說(shuō)bad data的概率很小也糊，對(duì)H中的每一個(gè)h使用union bound 會(huì)得到第二張圖，花花綠綠的很多圈就代表了bad data沒(méi)有重疊羡宙，我們后來(lái)進(jìn)行了分類(lèi)kind显设，再對(duì)kind進(jìn)行union bound就得到第三張圖！值得體悟一下~
step 3：use hoeffding without replacement
現(xiàn)在不是無(wú)限多的小球 in bin辛辨，而是2N個(gè)小球捕捂，這是不放回的霍夫丁，但是結(jié)論和原來(lái)的霍夫丁還是一樣的斗搞。這時(shí)計(jì)算的不是Ein和Eout的差指攒，而是Ein和均值的差，均值即（Ein + Ein '）/2僻焚，由|Ein - Ein'|＞ε/2可以得到
至此允悦，得到：
其實(shí)這就是著名的Vapnik-Chervonenkis(VC) bound！虑啤！
所以現(xiàn)在就可以真正說(shuō)learning with 2D perceptrons（break point is 4隙弛，mH（N）的最高次是3） is feasible！
有木有長(zhǎng)舒一口氣的感覺(jué)呢狞山？全闷！下一章告訴你力氣不會(huì)白費(fèi)！
