引言

上一小節(jié)猾封，我們引入了VC維的概念澄耍，用它來(lái)描述假設(shè)集合的表達(dá)能力。這一小節(jié)中忘衍，我們將從VC維的物理意義出發(fā)逾苫，進(jìn)一步學(xué)習(xí)如何根據(jù)VC維傳達(dá)的信息來(lái)選擇模型和假設(shè)集合。

VC維的物理意義

如果我們將假設(shè)集合的數(shù)量|H|比作假設(shè)集合的自由度枚钓，那么VC維就是假設(shè)集合在做二元分類的有效的自由度铅搓，即這個(gè)假設(shè)空間能夠產(chǎn)生多少Dichotomies的能力（VC維說(shuō)的是，到什么時(shí)候搀捷，假設(shè)集合還能shatter星掰，還能產(chǎn)生最多的Dichotomies）。

VC維嫩舟、真實(shí)錯(cuò)誤率氢烘、訓(xùn)練錯(cuò)誤率

在上一節(jié)中，我們討論要做到好的預(yù)測(cè)要滿足兩個(gè)條件家厌，第一是訓(xùn)練誤差要接近真實(shí)誤差播玖，即Ein(g)約等于Eout(g)；第二是訓(xùn)練誤差要盡量接近0饭于，即Ein(g)約等于0蜀踏。
現(xiàn)在维蒙，我們用VC維這個(gè)工具來(lái)描述。

• 如果VC維很小果覆，那么發(fā)生預(yù)測(cè)偏差很大的壞事情的可能性也就很小颅痊，那這有利于Ein(g)接近Eout(g)；但是局待，這是我們的假設(shè)空間的表達(dá)能力受到了限制斑响，這樣Ein(g)可能就沒(méi)有辦法做到很小。
• 如果VC維很大钳榨，那么假設(shè)空間的表達(dá)能力很強(qiáng)舰罚，我們很有可能選到一個(gè)Ein(g)很小的假設(shè)，但是Ein(g)和Eout(g)之差很大的壞事情發(fā)生的情況發(fā)生的可能性就變得很大重绷，這樣Ein(g)和Eout(g)根本不接近沸停，我們就無(wú)法確定選擇的假設(shè)在測(cè)試數(shù)據(jù)的時(shí)候表現(xiàn)的很好。

這時(shí)昭卓，VC維變成了我們一個(gè)重要的選擇，我們可以用VC維提供的信息來(lái)選擇更好的模型和假設(shè)空間瘟滨。

模型復(fù)雜度（Model Complexity）

我們可以根據(jù)VC Bound公式候醒，設(shè)發(fā)生壞事情的概率是δ，將其恒等變換可以得到訓(xùn)練誤差和測(cè)試誤差的差別ε杂瘸。所以反過(guò)來(lái)講倒淫，好事情（訓(xùn)練誤差和測(cè)試誤差的差別小于ε）發(fā)生時(shí)，Eout(g)被限制在一個(gè)范圍內(nèi)败玉。這里根號(hào)內(nèi)的式子定義為Ω(N,Η,δ)敌土，稱作模型復(fù)雜度,這個(gè)參數(shù)描述的意義是，我們的假設(shè)空間H有多么的強(qiáng)运翼，使得我們的算法在泛化能力上需要付出多少代價(jià)返干。通俗的來(lái)講，假設(shè)空間的容量越大血淌，VC維越大矩欠，那么模型就越難學(xué)習(xí)。

model_complexity

VC維傳遞的信息

如下圖所示悠夯，我們可以看出隨VC維變化癌淮，Ein、Eout沦补、模型復(fù)雜度都是如何變化的乳蓄。
這里一個(gè)很直接的信息就是模型復(fù)雜度隨著VC維的變大不斷變大，呈正相關(guān)趨勢(shì)夕膀。
因?yàn)閂C維變大時(shí)虚倒，數(shù)據(jù)中可以shatter的點(diǎn)就變多了美侦，那么假設(shè)空間的容量就變大了，如果是一個(gè)合理的學(xué)習(xí)算法的話裹刮，就有機(jī)會(huì)找到一個(gè)更好的假設(shè)音榜，使得Ein更小。
而Eout呢捧弃？在一開(kāi)始的時(shí)候赠叼，Eout隨著Ein的下降也下降，但是到某個(gè)點(diǎn)违霞，因?yàn)槲覀円冻龅拇鷥r(jià)變大了嘴办，Eout開(kāi)始上升，所以最好的Eout是在中間的某個(gè)位置买鸽。
這里得到一個(gè)重要的結(jié)論涧郊，VC維越大或者假設(shè)空間能力越強(qiáng)大，雖然可以使得訓(xùn)練誤差很小眼五，但不見(jiàn)得是最好的選擇妆艘，因?yàn)橐獮槟Ｐ蛷?fù)雜度付出代價(jià)。

VC_message

樣本復(fù)雜度（Sample Complexity）

根據(jù)理論而言看幼，樣本復(fù)雜度大約是VC維的10000倍批旺，而實(shí)際應(yīng)用中，只需要VC維的10倍的量就夠了。
我們這里介紹的VC Bound的條件是非常寬松的，這使得在樣本復(fù)雜度的估計(jì)上可以和理論值相差很大店枣，原因如下：

• 我們利用Hoeffding對(duì)任何的分布和任何的目標(biāo)函數(shù)來(lái)推測(cè)真實(shí)的錯(cuò)誤率
• 我們利用成長(zhǎng)函數(shù)mH(N)來(lái)代替假設(shè)集合的數(shù)量力惯，確保可以使用任何數(shù)據(jù)
• 用VC維表示的多項(xiàng)式來(lái)代替成長(zhǎng)函數(shù)，使得我們只通過(guò)VC維就可以了解某個(gè)假設(shè)空間的性質(zhì)
• 使用union bound來(lái)避免最差的狀況

以上有關(guān)VC Bound傳遞的哲學(xué)信息可以很好的指導(dǎo)我們進(jìn)行機(jī)器學(xué)習(xí)算法的實(shí)踐。

最后一句話

最后總結(jié)一句話，如果我們假設(shè)集合的VC維是有限的鞋囊，并且有足夠多的數(shù)據(jù)，我們的算法又可以找到一個(gè)假設(shè)使得訓(xùn)練錯(cuò)誤率很低的話摆寄，我們就可以學(xué)習(xí)到有效的模型或知識(shí)失暴。

參考資料

機(jī)器學(xué)習(xí)基石課程，林軒田微饥，臺(tái)灣大學(xué)

轉(zhuǎn)載請(qǐng)注明作者Jason Ding及其出處
Github主頁(yè)(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡(jiǎn)書(shū)主頁(yè)(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)