Lec 7：The VC Dimension
tips：符號含義主要參照lec 1踪蹬，部分需要參照其他lec
上一節(jié)介紹了機器學(xué)習(xí)可行性的重要理論保障VC Bound骇两，基于此污尉，這節(jié)將介紹VC Dimension.
1胯甩、Definition of VC Dimension
上一節(jié)講到上限函數(shù)B（N枪孩，k）的最高次項是k的N - 1次方蝶防。
這里將B（N甚侣，k）與k的N-1次方做部分比較：
可以看出N的k-1次方已經(jīng)比B（N，k）大了间学，實際上我們可以用N的k-1次方bound住B（N殷费，k），可以簡化bound：
所以bad data的概率上限現(xiàn)在可以更加簡化低葫，不過详羡，要加上上面的條件N≥2 && k≥3：
小summary: H存在k并且N足夠大時，可以保證Eout ≈ Ein嘿悬，所以這時候當(dāng)A選擇一個Ein小的h作為g就probably learned（當(dāng)然也是需要一點luck的）实柠！
下面進入本節(jié)的重點，先給出VC Dimension 的定義善涨。很簡單窒盐，VC Dimension就是最大的那個非break-point草则。
稍正式點的定義：表示為dvc(H)，為 largest N for which mH（N）= 2的N次方
vc dimension 是H的一個性質(zhì)蟹漓，還可以從下面兩點看待炕横，一是dvc就是H可以shatter的最大inputs數(shù)量；二是dvc = min（k） - 1.
結(jié)合上面的內(nèi)容葡粒，成長函數(shù)的上限又可以表示為：
所以dvc有限就可以說H是good份殿！有限的dvc就可以保障 Eout（g）≈ Ein（g）.
2、Perceptrons Revisited
已知2D的Perceptrons的dvc=3嗽交，當(dāng)N足夠大時卿嘲，learning可行！那當(dāng)更一般化的轮纫、更高維的PLA會怎樣呢腔寡？
回顧一下，1D的PLA的dvc = 2掌唾；2D的PLA的dvc = 3. 猜測：dvc = d + 1放前？？糯彬？恩凭语，猜對了，哈哈哈撩扒，這里先給出結(jié)論再給出證明似扔。
證明這個結(jié)論可以從兩方面證明：一方面dvc ≥ d + 1；一方面 dvc ≤ d + 1
1）dvc ≥ d + 1
這一條代表什么搓谆？就是可以找出能夠被shatter的d + 1 個inputs .
這里用一組特別的input炒辉，用矩陣表示，此矩陣存在反矩陣泉手；y也用矩陣表示黔寇，y表示任意的二元組合。能夠shatter就表示對于任意的y都能得到sign（Xw）= y .顯然可以斩萌，所以成立缝裤。
2）dvc ≤ d + 1
這一條代表對于“任意”d+2維的inputs都不能shatter.
先看簡單的例子 2D PLA. x4 可以被x1 x2 x3的線性組合表示，所以x1 x2 x3的正負確定后颊郎，x4的正負也就確定了憋飞！下圖中x4 必然是正的。這里基本可以得出一個結(jié)論：線性依賴（linear dependence）關(guān)系限制了dichotomy的最大kind數(shù)量姆吭！
更一般的情況榛做，X矩陣有d+2個rows、d+1個columns.row＞col，所以會有線性依賴检眯。前d+1個確定則d+2個自然就確定了升敲，所以自然不能shatter！所以結(jié)論成立轰传。
所以 dvc = d + 1.線性依賴限制了dichotomy的kind數(shù)量~
3驴党、Degree of Freedom
dvc = d + 1，d是perceptron的維度获茬，每個w對應(yīng)一個h港庄，w =（w0,w2,w3，...恕曲，wd）鹏氧，dvc代表的是有效的binary分類的自由度（就像調(diào)節(jié)按鈕的調(diào)節(jié)范圍）。自由度也代表了H的powerfulness（就是H能夠做多少事情）佩谣。
在實際中把还，通常dvc ≈ 可以調(diào)節(jié)的參數(shù)的個數(shù)（but not always）
回想一下關(guān)于M的trade off，現(xiàn)在同樣dvc有一樣的問題（這是自然的茸俭，因為我們千辛萬苦用N的dvc次方取代了M）：
所以吊履，使用合適大小的dvc是很重要的。
這一節(jié)的fun time有點意思调鬓，這里提一下：
答案是2.這里林老師的目的并不是讓我們?nèi)プC明艇炎，而是這樣理解：w0已經(jīng)固定，則可以調(diào)節(jié)的自由度就少了1個腾窝，則dvc是d +１－１．
4缀踪、進一步了解dvc的意義
回顧一下vc bound
vc bound限制了發(fā)生bad data 的概率，則good 的概率是 1 - δ虹脯。good即|Ein（g）- Eout（g）|≤ ε.經(jīng)過下面的計算可以得到ε的表達式驴娃。
見下圖，所以循集，Eout和Ein的差異的大小與dvc是有關(guān)的唇敞。gen是generalization的縮寫。我們通常只需要關(guān)注右側(cè)的bound就好了暇榴，左側(cè)灰色在此可忽略厚棵。dvc大自由度高蕉世，但是需要付出更大的代價 ε. 右側(cè)用Ω（N蔼紧，H，δ） 表示狠轻，稱為model complexity（ 模型復(fù)雜度）奸例，這里的model可以理解為H.
根據(jù)上圖中Eout和Ein的關(guān)系，我們要給出一個非常非常重要的圖！２榈酢谐区！
dvc ↑：Ein ↓（有更多機會找到好的g）；但是Ω ↑ 逻卖；
dvc ↓：Ω ↓ 宋列，但是 Ein ↑
通常最好的dvc在中間位置。
從這張圖可以看出H并不是越powerful越好的评也！（太powerful就會overfiting炼杖，后面章節(jié)介紹）
之前我們只是想著把Ein變小，其實我們還要考慮需要付出的代價盗迟！
一直說需要足夠多的data坤邪，那N是多少合適呢？根據(jù)vc bound 式子以及需求大致可以計算出需要的N的大小罚缕。理論上艇纺，我們需要 N = 10000 * dvc，太多了太難找到這么多data了邮弹。實際中 10 * dvc的data often enough 黔衡！
why？
因為vc bound 很寬松（looseness）腌乡，寬松的來源是什么员帮？四點：
1）霍夫丁對任意分布的data以及f都適用；
2）mH（N）成長函數(shù)是采樣出的any data 對應(yīng)的dichotomy的最大值导饲；
3）用N的dvc次方是成長函數(shù)的上限的上限的上限捞高，我們只用一個值dvc去計算上限，可以忽略H的細節(jié)渣锦；
4）union bound是考慮了最壞的情況硝岗；
其實一路推導(dǎo)都很寬松，所以理論和實際差了很多袋毙。
講了這么多型檀，其實最重要的并不是它的理論部分，而是明白vc bound里面的“哲學(xué)”（都在最后一張圖里了）听盖。
