vc維與模型復雜度、樣本復雜度
引言
上一小節，我們引入了VC維的概念，用它來描述假設集合的表達能力。這一小節中，我們將從VC維的物理意義出發，進一步學習如何根據VC維傳達的信息來選擇模型和假設集合。
VC維的物理意義
如果我們將假設集合的數量|H|比作假設集合的自由度，那么VC維就是假設集合在做二元分類的有效的自由度，即這個假設空間能夠產生多少Dichotomies的能力（VC維說的是，到什么時候，假設集合還能shatter，還能產生最多的Dichotomies）。
VC維、真實錯誤率、訓練錯誤率
在上一節中，我們討論要做到好的預測要滿足兩個條件，第一是訓練誤差要接近真實誤差，即Ein(g)約等于Eout(g)；第二是訓練誤差要盡量接近0，即Ein(g)約等于0。
現在，我們用VC維這個工具來描述。
- 如果VC維很小，那么發生預測偏差很大的壞事情的可能性也就很小，那這有利于Ein(g)接近Eout(g)；但是，這是我們的假設空間的表達能力受到了限制，這樣Ein(g)可能就沒有辦法做到很小。
- 如果VC維很大，那么假設空間的表達能力很強，我們很有可能選到一個Ein(g)很小的假設，但是Ein(g)和Eout(g)之差很大的壞事情 發生的情況發生的可能性就變得很大，這樣Ein(g)和Eout(g)根本不接近，我們就無法確定選擇的假設在測試數據的時候表現的很好。
這時，VC維變成了我們一個重要的選擇，我們可以用VC維提供的信息來選擇更好的模型和假設空間。
模型復雜度（Model Complexity）
我們可以根據VC Bound公式，設發生壞事情的概率是δ，將其恒等變換可以得到訓練誤差和測試誤差的差別ε。所以反過來講，好事情（訓練誤差和測試誤差的差別小于ε）發 生時，Eout(g)被限制在一個范圍內。這里根號內的式子定義為**Ω(N,Η,δ)，稱作模型復雜度,這個參數描述的意義是，我們的假設空間H有多么 的強，使得我們的算法在泛化能力上需要付出多少代價。通俗的來講，假設空間的容量越大，VC維越大，那么模型就越難學習。**
VC維傳遞的信息
如下圖所示，我們可以看出隨VC維變化，Ein、Eout、模型復雜度都是如何變化的。
這里一個很直接的信息就是模型復雜度隨著VC維的變大不斷變大，呈正相關趨勢。
因為VC維變大時，數據中可以shatter的點就變多了，那么假設空間的容量就變大了，如果是一個合理的學習算法的話，就有機會找到一個更好的假設，使得Ein更小。
而Eout呢？在一開始的時候，Eout隨著Ein的下降也下降，但是到某個點，因為我們要付出的代價變大了，Eout開始上升，所以最好的Eout是在中間的某個位置。
這里得到一個重要的結論，VC維越大或者假設空間能力越強大，雖然可以使得訓練誤差很小，但不見得是最好的選擇，因為要為模型復雜度付出代價。
