VC維(外文名Vapnik-Chervonenkis Dimension)的概念是為了研究學習過程一致收斂的速度和推廣性,由統計學理論定義的有關函式集學習性能的一個重要指標。
基本介紹
- 中文名:vc維
- 外文名:Vapnik-Chervonenkis Dimension
- 目的:為了研究學習過程一致收斂
- 原理:統計學理論
定義,感知器的VC維,理解VC維,
定義
傳統的定義是:對一個指示函式集,如果存在H個樣本能夠被函式集中的函式按所有可能的2的H次方種形式分開,則稱函式集能夠把H個樣本打散;函式集的VC維就是它能打散的最大樣本數目H。若對任意數目的樣本都有函式能將它們打散,則函式集的VC維是無窮大,有界實函式的VC維可以通過用一定的閾值將它轉化成指示函式來定義。
VC維反映了函式集的學習能力,VC維越大則學習機器越複雜(容量越大),遺憾的是,尚沒有通用的關於任意函式集VC維計算的理論,只對一些特殊的函式集知道其VC維。例如在N維空間中線性分類器和線性實函式的VC維是N+1。
如果一個假設空間存在突破點,則一定存在成長函式
被某個上限函式B(N,k)所約束,而上限函式等於一個組合的求和形式
,易知該形式的最高次項是
。圖左和右分別是以上限函式為上限的情況和以為
上限的情況。
![](/img/7/ae2/0bd215fcc7f03d63bb094e5f6d3b.jpg)
![](/img/4/a47/8359e35bef6f8f93a3dc9b822640.jpg)
![](/img/3/c72/33dadd1f69f767bf9ea2165a9da2.jpg)
![](/img/d/c86/e3b677ed63c689f5364b90760325.jpg)
![圖1 圖1](/img/7/b8e/nBnauQTMjVWOxkjZxUDMiJWMmJ2YmJjY2kjNjRGOzczMwYjZwkTY0EDM4I2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
可以得出:
![](/img/b/a4f/96ee8304c1711f9a8c1cef467e14.jpg)
如果輸入數據量N(或者用k表示)大於VC維,則有k一定是假設空間H的突破點。
在N≥2,
時,可得:
![](/img/d/b7c/e31235430be01f25decfbbbc5f1b.jpg)
![](/img/9/456/0fc965c287808e34c5d794db5eb3.jpg)
一個有限的VC維總是能夠保證尋找到的近似假設g是泛化的,即近似假設g滿足
。沒有必要知道具體的VC維的值,只需要知道它是有限的就可以得出這一結論。
![](/img/3/37d/59fc45c5c6acb29a88862cac8775.jpg)
同時這一結論與下述部分沒有關係:1.使用的算法,即使使用某種算法使得
很大,也依然能滿足上述的性質;2.輸入數據的分布P;3.未知的目標函式f。
![](/img/d/f26/428b31bdf393ad695b237579a052.jpg)
即VC維可應對任意的假設空間,任意的數據分布情況,任意的目標函式。滿足這一性質可以得到如圖所示的流程圖,其中灰色的部分表示上述幾個不會影響
這一結果的部分:
![](/img/3/37d/59fc45c5c6acb29a88862cac8775.jpg)
![圖2 圖2](/img/0/a5a/nBnauAzMmJjMxkjYwEzN0IGOldjZmNDN3E2M5ADMxQ2YkhjZkNjZ5czYhNzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
- 對於假設集合,這是一個由人工產生的集合,而VC維會告訴我們哪一個可以泛化,而哪一些不行。
- 對於數據集,VC維只能用一種機率性的說法解釋,它只能告訴你在高機率下可以泛化;而如果恰好用了一個非常不好的數據集,就沒有必要去對其進行泛化。
感知器的VC維
以下兩個條件保證了2維線性可分的數據是可以學習的:
1.線性可分的數據通過PLA算法運行足夠長的時間(T步驟足夠大),則會找出一條可以正確分類的直線,使得樣本中沒有產生分錯類的情況,即
;
![](/img/f/ab1/0a2ea908e23500b5fe985a03c0fd.jpg)
2.在訓練樣本和整個數據集都服從同一分布P的前提下,有VC限制保證了,在
且訓練樣本N足夠大時,
。
![](/img/9/3fe/7f4bdfcfeee727d6ce0b5f0ddc51.jpg)
![](/img/3/37d/59fc45c5c6acb29a88862cac8775.jpg)
由VC維的定義知:只要求出
是一個有限數,則可以使用VC限制來保證
。那么在維數大於二維時,感知器的dvc能否表示成一個有限數。已知,1維感知器的VC維:
=2;2維感知器的VC維:
=3。猜想,d維感知器的VC維:
=d+1。
![](/img/e/f98/f16b18028474f1be1e57a1d9cffa.jpg)
![](/img/3/37d/59fc45c5c6acb29a88862cac8775.jpg)
![](/img/e/f98/f16b18028474f1be1e57a1d9cffa.jpg)
![](/img/e/f98/f16b18028474f1be1e57a1d9cffa.jpg)
![](/img/e/f98/f16b18028474f1be1e57a1d9cffa.jpg)
證明:1.
≥d+1
![](/img/e/f98/f16b18028474f1be1e57a1d9cffa.jpg)
取出N=d+1個在
的樣本點,得到了如下的可逆矩陣(滿秩矩陣):
![](/img/c/fe8/ba3808b8e001f7d5f28eea62a6dc.jpg)
![可逆矩陣 可逆矩陣](/img/d/24b/nBnauIzMwEjNyIDO5E2M0UDNiJWYyE2NxETZlVTNhBTMzkzNzMmZhZzM2Y2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
對於任意的
,我們需要找到一個向量
,且
滿足sign(X
)=y。
![](/img/1/37c/995dab73d5c35d4dc4eb68c88e01.jpg)
![](/img/5/742/9e06598f06afd9444e72519ff31e.jpg)
![](/img/5/742/9e06598f06afd9444e72519ff31e.jpg)
![](/img/5/742/9e06598f06afd9444e72519ff31e.jpg)
因為y向量可以是任意一種形式的二分類,如果我們能夠對任意一個y向量都能找到對應的
,那么我們就可以得到所有的二分類,即實現完全二分類。令讓X
=y。同時因為X是可逆的,我們得到
=X−1y,因此我們可以解得
的值。
![](/img/5/742/9e06598f06afd9444e72519ff31e.jpg)
![](/img/5/742/9e06598f06afd9444e72519ff31e.jpg)
![](/img/5/742/9e06598f06afd9444e72519ff31e.jpg)
![](/img/5/742/9e06598f06afd9444e72519ff31e.jpg)
因此我們證明了
≥d+1。
![](/img/e/f98/f16b18028474f1be1e57a1d9cffa.jpg)
2.
≤d+1
![](/img/e/f98/f16b18028474f1be1e57a1d9cffa.jpg)
對於任意d+2個樣本點,X1,X2,…,Xd+1,Xd+2的維度均為d+1。那么當維度大於點的個數的時候,可以知道他們一定線性相關,即
,其中不是所有的
都為0(因為任意xj的第一維都是1,所以權重
不可能全是0)。
![](/img/0/a15/94125aae0e948bf6151aa56a3951.jpg)
![](/img/f/2b2/43372eb345158a4612acfc6dac16.jpg)
![](/img/f/2b2/43372eb345158a4612acfc6dac16.jpg)
構造一組
,且對於Xj,讓yj=−1,其餘權重為零的Xi對應的yi可以任意取值。
![](/img/7/0df/fe1cffe353fa689dedf0c40f2047.jpg)
![](/img/8/044/03ab1144bfd0e76cc0498d7a20b8.jpg)
令
,那么對於每一個非零的ai,可以得到
和(ai)的符號是相同的,即,
。
![](/img/6/62b/247e42759814abd1a96c3affcaf5.jpg)
![](/img/7/658/fc43eec0c18e8e1b0fc9b168eb83.jpg)
![](/img/f/b9d/029e76dac6fcd30320b0dd8a364c.jpg)
因此
(因為ai=0時,累加無效),同時可得
>0。則可以得到
![](/img/3/d58/2a8404d4a270b3065bb96400f94c.jpg)
![](/img/7/658/fc43eec0c18e8e1b0fc9b168eb83.jpg)
![](/img/b/378/082cf99580e5b847ac35549a7771.jpg)
假設不成立,因此在任何d+2個輸入數據集中必然都存在不能滿足的二分類,即
。
![](/img/f/af8/9704b6eab3909a6398634744d9fa.jpg)
證明了
。
![](/img/7/bde/9c811f4c5129146d6d39a4994f77.jpg)
理解VC維
如果從假設空間的數量|H|角度上描述,則自由度是無限大的;但是從感知器在二元分類上這一限制條件入手,則可以使用VC維作為自由度的衡量。
VC維和假設空間參數之間的關係:
當dvc=1時,假設空間有1個參數,即閾值。
![dvc=1 dvc=1](/img/0/ad0/nBnauQzY1EjM4IGO3ETZxMmZzMGOjJWMiJmYxUDN3IGNjJWZ5EzMiVTNiBzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
當dvc=2時,假設空間有2個參數,即左右邊界點。因此在大部分情況下,dvc大致等於假設空間參數的個數。
![dvc=2 dvc=2](/img/9/3af/nBnauIDZzMjN2MTNkZmNiJGZ1MTNygTMyY2M2QzYkRWZ2QWY1QmYxQjZmBzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
將一個1D的感知器輸出連線到下一個1D感知器的輸入,如下圖所示,這樣就得到了8個參數,然而它的自由度並沒有增加。根據dvc,我們可以得出只需要一個感知器就足夠的結論。
![1D感知器輸入 1D感知器輸入](/img/1/530/nBnauAjY3cDN1gDNzEjYjFjYxgTMzczYkJjMjBjNjVTMzMmY1ITO5UmZxU2LtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)