1.1.3 VC維理論

統(tǒng)計(jì)學(xué)習(xí)理論的一個重要內(nèi)容是VC維理論，它是建立在點(diǎn)集被“打散”的基礎(chǔ)上，是關(guān)于函數(shù)集學(xué)習(xí)性能的指標(biāo)。假設(shè)集合T是一個由X上取值為1或者-1的函數(shù)值組成的集合，則集合T的VC維定義為

式中，當(dāng){m:N（T,m）=2m}是一個無限集合時，其VC維等于無窮大。

由VC維的定義知，對于一個假設(shè)函數(shù)集，如果存在h個樣本可以被函數(shù)集中的函數(shù)按所有可能的2h種形式分開，那么就認(rèn)為函數(shù)集可以把h個樣本打散，函數(shù)的VC維就是它能夠打散的最大樣本數(shù)目h。若存在h個樣本能被打散，但任意h+1個樣本不能夠被打散，則函數(shù)集的VC維就是h。若對于任意數(shù)目的樣本都存在函數(shù)能將其打散，則稱VC維是無窮大。

由Vapnik和Chervonenkis提出的VC維理論反映了函數(shù)集的學(xué)習(xí)能力，一個函數(shù)集的VC維越大，則學(xué)習(xí)機(jī)器就會越復(fù)雜，學(xué)習(xí)能力就會越強(qiáng)。但到目前為止，還沒有確定的計(jì)算函數(shù)集VC維的理論。只一些特殊函數(shù)集的VC維可以準(zhǔn)確知道；對于復(fù)雜的學(xué)習(xí)機(jī)器，其VC維的確定還是一個待研究的問題。