版權(quán)歸原作者所有,如有侵權(quán),請聯(lián)系我們

[科普中國]-vc維

科學(xué)百科
原創(chuàng)
科學(xué)百科為用戶提供權(quán)威科普內(nèi)容,打造知識科普陣地
收藏

VC維(外文名Vapnik-Chervonenkis Dimension)的概念是為了研究學(xué)習(xí)過程一致收斂的速度和推廣性,由統(tǒng)計學(xué)理論定義的有關(guān)函數(shù)集學(xué)習(xí)性能的一個重要指標(biāo)。

定義傳統(tǒng)的定義是:對一個指示函數(shù)集,如果存在H個樣本能夠被函數(shù)集中的函數(shù)按所有可能的2的H次方種形式分開,則稱函數(shù)集能夠把H個樣本打散;函數(shù)集的VC維就是它能打散的最大樣本數(shù)目H。若對任意數(shù)目的樣本都有函數(shù)能將它們打散,則函數(shù)集的VC維是無窮大,有界實函數(shù)的VC維可以通過用一定的閾值將它轉(zhuǎn)化成指示函數(shù)來定義。

VC維反映了函數(shù)集的學(xué)習(xí)能力,VC維越大則學(xué)習(xí)機器越復(fù)雜(容量越大),遺憾的是,尚沒有通用的關(guān)于任意函數(shù)集VC維計算的理論,只對一些特殊的函數(shù)集知道其VC維。例如在N維空間中線性分類器和線性實函數(shù)的VC維是N+1。

如果一個假設(shè)空間存在突破點,則一定存在成長函數(shù) 被某個上限函數(shù)B(N,k)所約束,而上限函數(shù)等于一個組合的求和形式 ,易知該形式的最高次項是 。圖左和右分別是以上限函數(shù)為上限的情況和以為 上限的情況。

可以得出:

若輸入數(shù)據(jù)量N小于VC維,則有可能輸入數(shù)據(jù)D會被完全的二分類。

如果輸入數(shù)據(jù)量N(或者用k表示)大于VC維,則有k一定是假設(shè)空間H的突破點。

在N≥2, 時,可得:

一個有限的VC維總是能夠保證尋找到的近似假設(shè)g是泛化的,即近似假設(shè)g滿足 。沒有必要知道具體的VC維的值,只需要知道它是有限的就可以得出這一結(jié)論。

同時這一結(jié)論與下述部分沒有關(guān)系:1.使用的算法,即使使用某種算法使得 很大,也依然能滿足上述的性質(zhì);2.輸入數(shù)據(jù)的分布P;3.未知的目標(biāo)函數(shù)f。

即VC維可應(yīng)對任意的假設(shè)空間,任意的數(shù)據(jù)分布情況,任意的目標(biāo)函數(shù)。滿足這一性質(zhì)可以得到如圖所示的流程圖,其中灰色的部分表示上述幾個不會影響 這一結(jié)果的部分:

對于假設(shè)集合,這是一個由人工產(chǎn)生的集合,而VC維會告訴我們哪一個可以泛化,而哪一些不行。

對于數(shù)據(jù)集,VC維只能用一種概率性的說法解釋,它只能告訴你在高概率下可以泛化;而如果恰好用了一個非常不好的數(shù)據(jù)集,就沒有必要去對其進(jìn)行泛化1。

感知器的VC維以下兩個條件保證了2維線性可分的數(shù)據(jù)是可以學(xué)習(xí)的:

1.線性可分的數(shù)據(jù)通過PLA算法運行足夠長的時間(T步驟足夠大),則會找出一條可以正確分類的直線,使得樣本中沒有產(chǎn)生分錯類的情況,即 ;

2.在訓(xùn)練樣本和整個數(shù)據(jù)集都服從同一分布P的前提下,有VC限制保證了,在 且訓(xùn)練樣本N足夠大時, 。

由VC維的定義知:只要求出 是一個有限數(shù),則可以使用VC限制來保證 。那么在維數(shù)大于二維時,感知器的dvc能否表示成一個有限數(shù)。已知,1維感知器的VC維: =2;2維感知器的VC維: =3。猜想,d維感知器的VC維: =d+1。

證明:1. ≥d+1

取出N=d+1個在 的樣本點,得到了如下的可逆矩陣(滿秩矩陣):

對于任意的 ,我們需要找到一個向量 ,且 滿足sign(X )=y。

因為y向量可以是任意一種形式的二分類,如果我們能夠?qū)θ我庖粋€y向量都能找到對應(yīng)的 ,那么我們就可以得到所有的二分類,即實現(xiàn)完全二分類。令讓X =y。同時因為X是可逆的,我們得到 =X?1y,因此我們可以解得 的值2。

因此我們證明了 ≥d+1。

2. ≤d+1

對于任意d+2個樣本點,X1,X2,…,Xd+1,Xd+2的維度均為d+1。那么當(dāng)維度大于點的個數(shù)的時候,可以知道他們一定線性相關(guān),即,其中不是所有的都為0(因為任意xj的第一維都是1,所以權(quán)重不可能全是0)。

構(gòu)造一組,且對于Xj,讓yj=?1,其余權(quán)重為零的Xi對應(yīng)的yi可以任意取值。

,那么對于每一個非零的ai,可以得到和(ai)的符號是相同的,即,。

因此(因為ai=0時,累加無效),同時可得>0。則可以得到

假設(shè)不成立,因此在任何d+2個輸入數(shù)據(jù)集中必然都存在不能滿足的二分類,即。

證明了。2

理解VC維如果從假設(shè)空間的數(shù)量|H|角度上描述,則自由度是無限大的;但是從感知器在二元分類上這一限制條件入手,則可以使用VC維作為自由度的衡量1。

VC維和假設(shè)空間參數(shù)之間的關(guān)系:

當(dāng)dvc=1時,假設(shè)空間有1個參數(shù),即閾值。

當(dāng)dvc=2時,假設(shè)空間有2個參數(shù),即左右邊界點。因此在大部分情況下,dvc大致等于假設(shè)空間參數(shù)的個數(shù)。

將一個1D的感知器輸出連接到下一個1D感知器的輸入,如下圖所示,這樣就得到了8個參數(shù),然而它的自由度并沒有增加。根據(jù)dvc,我們可以得出只需要一個感知器就足夠的結(jié)論。

本詞條內(nèi)容貢獻(xiàn)者為:

何星 - 副教授 - 上海交通大學(xué)