哪些常用的分類器是有VC維的，他們的VC維如何計算？

線性分類器，例如感知機、線性核SVM的VC維是維度加一，那其他有哪些常用的分類器是有VC維的，或者在某些限制條件下是有VC維的？

我嘗試著回答一下：

1，先說一些結論：

線性分類器：(所有的線性分類器成立）

使用高斯核的分類器

由上可知：線性SVM的維為，而 高斯核函數的為（關於SVM的VC-d的內容可以參考 http://research.microsoft.com/pubs/67119/svmtutorial.pdf）

最近鄰：

NN（Neural Networks ）：

3節點的decision tree ：，8節點的decision tree ：

,

2，從VC維的來源來看VC維有什麼作用：

如果假設空間中的hypothesis數是固定的，經過證明可以得到：

其中，是我們給定model 之後，訓練數據的誤差。而是model真實的誤差，也就是我們最終關心的誤差。上式中可以得出真實誤差上界，所以此公式證明了在machine learning 真的具有學習能力。

但是，當H的個數為無窮的時候，上式就失效了，因為是無限大的，因此科學家們有證明了如下公式：

結論是可以不依賴而依賴於，而就是樓主提到的VC維，VC維是用來證明誤差的上界的，知道常用的分類器的誤差上界，就會對分類器的分類效果有進一步的認識，從而選擇最優的分類器。

但是，實際使用中，VC維在模型選擇中別不是特別特別常用（因為他僅僅是提供了誤差上界的理論證明，而且此理論誤差上界限有時候和真實誤差聯繫並不緊密），而常用的模型選擇方法有：

• CV（Cross-validation），應該是最常用的，也最容易理解的
• AIC（Akaike Information Criterion）
• BIC（Bayesian information Criterion）

3，最後說一下VC維定義以及簡單證明過程

先給定一些相關定義：

• dichotomy : 把給定集S分成不想交的兩個子集。
• shattered ：我們說給定集S被一個假設空間（hypothesis space ）shattered，當且僅當：對於S任意的dichotomy，在中都存在一個特定的滿足此dichotomy。
• VC dimension： 定義為假設空間（hypothesis space ）能夠shatter的最大的集合的維度，例如，2維感知機（一種線性分類器）的。

VC 維的證明過程一般分為兩步，第一步證明VC 維至少是多大（例如最小是p），第二步證明VC維最大是多大（例如還是p），因為可以得出。

給一個最近鄰VC維非常直觀的一個解釋：