內(nèi)容
一铐懊、學(xué)習(xí)VC維前概念介紹
二狮鸭、breakPoint對(duì)growth function的限制
三浇冰、邊界函數(shù)Bounding Function（growth function的限制）
四浆西、VC bound的圖形化定義
################################################################################
一曾掂、學(xué)習(xí)VC維前概念介紹
? ? ? ? ? 1.growth function
? ? ? ? ? ?growth function也是我們前面學(xué)得effective(N)，表示對(duì)數(shù)據(jù)D分類的最大結(jié)果數(shù)壁顶。比如說(shuō)現(xiàn)在數(shù)據(jù)集有兩個(gè)數(shù)據(jù)點(diǎn)珠洗，考慮一種二分類的情況，可以將其分類成A或者B若专，則可能的值有：AA许蓖、AB、BA和BB调衰，所以這里增長(zhǎng)函數(shù)的值為4膊爪。
注：紅色方框代表成長(zhǎng)函數(shù)的數(shù)目，假設(shè)空間H在M上最大的數(shù)目嚎莉。當(dāng)N=1時(shí)米酬，有兩種h;當(dāng)N=2時(shí)，4種h趋箩；當(dāng)N=3時(shí)赃额，如果3個(gè)點(diǎn)都是散開(kāi)的那么有8種可能劃分，如果3個(gè)點(diǎn)排成直線那么有6中劃分阁簸，故根據(jù)公式取值8爬早；當(dāng)N=4時(shí)哼丈，有兩種是不能線性可分的启妹，這樣只有14個(gè)結(jié)果。所以不是所有結(jié)果都是2^n醉旦。這樣使得m=effective(n)<M,使p小于的結(jié)果不是無(wú)窮的饶米。
? ? ? ? 四種growth function
注：舉例子在劃分2個(gè)點(diǎn)的時(shí)候，growth function的個(gè)數(shù)是4個(gè)车胡。因?yàn)闆](méi)有限制(positive是正向必須為0)檬输，所以這是為N+1=2+1=3。去除了（o,x）的情況匈棘。（具體四種gf的描述過(guò)程見(jiàn)lin的第五節(jié)）
? ? ? ? ? 2.dichotomy（對(duì)分）? ? ? ??
? ?????????對(duì)于二分類問(wèn)題來(lái)說(shuō)（二分類）丧慈，H中的假設(shè)對(duì)D中m個(gè)示例賦予標(biāo)記的每種可能結(jié)果稱為對(duì)D的一種對(duì)分（dichotomy）。?????
? ? ? ? ? 3.shatter（打散）?
? ? ? ? ? ?打散指的是假設(shè)空間H能實(shí)現(xiàn)數(shù)據(jù)集D上全部示例的對(duì)分主卫，即增長(zhǎng)函數(shù)=?2^n逃默。
? ? ? ? ? ?4.Break Point (斷點(diǎn))
? ??????????如果按照2^m這種趨勢(shì)增長(zhǎng)那簡(jiǎn)直是沒(méi)天理了。上面說(shuō)道了簇搅，隨著m的增大完域，一定會(huì)出現(xiàn)一個(gè)m使假設(shè)空間無(wú)法shatter。這種不滿足2^n的情況說(shuō)明增長(zhǎng)函數(shù)從這個(gè)點(diǎn)開(kāi)始變緩了瘩将，是一個(gè)可喜可賀的重大突破吟税，所以我們把第一個(gè)不滿足shatter的m值稱為break point凹耙。（這里翻譯成突破點(diǎn)）
二、Break Point對(duì)growth function的限制
? ? ? ? 1.growth function的個(gè)數(shù)是最大的對(duì)分個(gè)數(shù)（這里有breakpoint的限制）
? ? ? ? ? ? ? ? ? ? ? ? ? 注：breakpoint這個(gè)點(diǎn)表示此是時(shí)growth function的個(gè)數(shù)不是2^n肠仪。
? ? ? ? 2.假設(shè)對(duì)于一個(gè)問(wèn)題肖抱，minimum break point k = 2（對(duì)于任意2個(gè)輸入，H不能窮盡所有劃分）藤韵，基于該條件我們做出推論：
解釋：當(dāng)N=1時(shí)虐沥，growth function 的個(gè)數(shù)為2；當(dāng)N=2時(shí)泽艘，growth function 的個(gè)數(shù)為3欲险，此時(shí)2是BreakPoint。
? ? ? ? 3.那么當(dāng)N=3時(shí)匹涮，growth function是多少呢天试？
? ?????????任意3個(gè)輸入（x1, x2, x3），我們一定能找到以下3個(gè)合法的劃分：
????????????Step 1：一個(gè)對(duì)分時(shí)然低，觀察是否任意兩個(gè)點(diǎn)被shatter（否）
????????????Step 2：兩個(gè)對(duì)分時(shí)喜每，觀察是否任意兩個(gè)點(diǎn)被shatter（否）
????????????Step 3：三個(gè)對(duì)分時(shí)，觀察是否任意兩個(gè)點(diǎn)被shatter（否）
????????????Step 3：四個(gè)對(duì)分時(shí)雳攘，觀察是否任意兩個(gè)點(diǎn)被shatte
? ? ? ? ? ? 在尋找更多劃分之前带兜，我們要明確一點(diǎn)就是因?yàn)閗=2，所以（x1, x2, x3）中任意2個(gè)點(diǎn)都不 ????????????能被shatter吨灭，所以下面這個(gè)劃分不可能出現(xiàn)刚照，因?yàn)椋▁2, x3）所有4種可能的劃分被窮盡了：
? ? ? ? ? ? ? ? ? ? ? ? ? ?但是接下來(lái)的劃分就可能了：
????????????????????????????再之后，你發(fā)現(xiàn)不論再尋找什么劃分喧兄，總有兩個(gè)點(diǎn)被shatter无畔，所以，N=3時(shí)成長(zhǎng)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 函數(shù)的maximum possible value就是 4 了吠冤。而且 4 << 2^3=8浑彰。綜上我們發(fā)現(xiàn)，當(dāng)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?N > break point k拯辙，成長(zhǎng)函數(shù)的maximum possible value顯著下降并遠(yuǎn)小于 2^N郭变。
????????????Step 4：得出結(jié)論
? ? ? ? 4.猜想
三、邊界函數(shù)Bounding Function（growth function的限制）
? ? ? ?1.邊界函數(shù)Bounding Function?B(N,k)：當(dāng)BreakPoint=k時(shí)涯保，最大的可能growth function的個(gè)? ??????????數(shù)诉濒。
? ? ? ? ? ? ? ? ? ? ? ? ? ? 所以有：
? ? ? ? ? ? ? ? ? ? ? ? ? ?當(dāng)k=1時(shí)，給定任意N個(gè)輸入遭赂，只能有一種劃分的可能循诉，因?yàn)槿魏蔚诙N劃分都會(huì)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?導(dǎo)致有一個(gè)點(diǎn)被shatter，這與k=1相悖撇他，所以：
????????????????????????????當(dāng) N<k 時(shí)茄猫，N個(gè)輸入一定都能被shatter狈蚤，所以 B(N,k)=2^N：
? ? ? ? ? ? ? ? ? ? ? ? ? ?當(dāng) N=k時(shí)，首次出現(xiàn)N個(gè)輸入不能被Shatter划纽，所以 B(N,k)=2^N - 1 一定沒(méi)錯(cuò)：
? ? ? ? ? ? ? ? ? ? ? ? ?綜上脆侮，在確定B(N,k)的過(guò)程中我們已經(jīng)把軟柿子都捏了，現(xiàn)在討論N>k的情況勇劣。我們猜測(cè)?B(N,k) 與 B(N-1, k-1) + B(N-1, k)?也許有關(guān)系靖避。以B(4,3)為例，4個(gè)輸入中任意3個(gè)都不能被shatter比默，用一個(gè)簡(jiǎn)單的程序遍歷所有2^16個(gè)劃分組合得到B(4,3)=11幻捏。故得出下表：
? ? ? ? ? ? ? ? ? ? ? ? ? ?注：生成的表說(shuō)明BP對(duì)growth function的限制，當(dāng)N一定且K不同時(shí)命咐， 產(chǎn)生growth function的個(gè)數(shù)不一樣篡九。在我們沒(méi)有引入breakpoint前,舉個(gè)例子，當(dāng)N=3時(shí)醋奠，最大growth fnction的個(gè)數(shù)是8榛臼；當(dāng)引入breakpoint，k>=4時(shí)窜司，最大growth fnction的個(gè)數(shù)是8沛善。
? ? ? ? ? ? ? ? ? ? ? ? ? ?最終（邊界函數(shù)的成長(zhǎng)性為O(N^(k-1))）
四、VC bound的圖形化定義
? ? ? ?1.把備選函數(shù)集H中備選函數(shù)的數(shù)量M用成長(zhǎng)函數(shù)代替塞祈，我們得到：
? ? ? ? ? ? ? ? ? ? ? ? ? ? 注：證明過(guò)程見(jiàn) https://blog.csdn.net/songzitea/article/details/43112233
