跳至內容

VC維

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

瓦普尼克-澤范蘭傑斯維(Vapnik-Chervonenkis Dimension),簡稱VC維,由弗拉基米爾·瓦普尼克亞歷克塞·澤范蘭傑斯提出。在VC理論中,VC維是對一個可學習分類函數空間的能力(複雜度,表示能力等)的衡量。它定義為算法能「打散」的點集的勢的最大值。 直觀地,一個分類模型的能力與其複雜程度相關。例如,考慮一個高次多項式的分類模型:若函數值大於0則分類為正,反之則分類為負。高次多項式能夠「擺動」的範圍很大,所以能夠很好地擬合給定的點集。當然因此,這樣的模型也很可能會在其他符合原點集趨勢的點集上分類錯誤。我們說這一多項式是高能力的。如果考慮一個簡單的線性分類模型,就不一定能夠很好地擬合給定的點集。

定義

集合族的VC維

給定一集合族與一集合,定義其為如下的集合族:

能打散,若且唯若包含的所有子集,即

的VC維定義為能被打散的勢最大的集合的勢。

分類模型的VC維

對一個參數記為的分類模型,稱模型能夠打散一點集,若且唯若對任意標籤集都存在參數使得上分類完全正確。

模型的VC維定義為能被打散的勢最大的點集的勢,或等價地,滿足存在使得能打散的最大的

參見