# Course 5 -- VC Dimension

## 甚麼是 VC Dimension 呢 ?

==**它是能夠用來判斷統計分類演算法上空間複雜度的依據**==

以一個問題範例來說，
當有個 data point x 需要被分類再 + 和 -這兩個 class 裏頭，

而有個 H 為 function 的集合，其中有個 h function，
此 h function 能夠用來分類 data point。

譬如，h(x) > 0 時，將此分類於 class +
反之，分類於 class -

而分類出 N 個 data points，為正確分類的類別數即為 VC dimension

### Example


Reference : https://www.ycc.idv.tw/ml-course-foundations_2.html

以此圖示來舉例，其 dichotomy(二分法)的值，代表能夠在有幾個 data points 下分類出兩種不同類別。

但超過 break point 時，便無法達成。在此時 break point 為 4。

而其 VC Dimension 的值等同於 break point - 1，所以此問題的 VC Dimension 為 3。


以為此範例，此 rectangle function 的 VC Dimension 為 4。
因為當有個 x 在此方框內部時，且無法透過 rectangle function 來進行區分時，
5 個 data points 即為此 function 的 break point，故 VC Dimension 為 4。

### Dichotomy

Reference :
https://medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92%E5%9F%BA%E7%9F%B3%E7%B3%BB%E5%88%97/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92%E5%9F%BA%E7%9F%B3-4-vc-dimension%E5%92%8C%E6%A8%A1%E5%9E%8B%E8%A4%87%E9%9B%9C%E5%BA%A6-5398ed1c8a5e

二分法指的是將一個整體事物分割成兩部分。也即是說，這兩部分必須是互補事件，即所有事物必須屬於雙方中的一方，且互斥，即沒有事物可以同時屬於雙方。

而由上方範例能推出一個結論，VC Dimension = Dimension + 1
以下證明，分兩部分執行：

**1. VC dimension ≥ d+1**
==**存在h可把某d+1筆資料shatter**==

現在假設一組特殊的資料，這組資料有d+1筆。

第一筆資料只有原點，全部向量都是 0 ;
第二筆只有在第一維度有個分量，其他都是 0 ;
第三筆則在第二維有分量，其他是 0 …
一直到第 d+1 筆，是在第 d 維有分量，其他是 0。

另外在全部的資料前面再加一項1，作為閾值。

原點，(0,1)和(1,0)三個點。

$X = \begin{bmatrix}1&0&0&\dots&0\\1&1&0&\dots&0\\1&0&1&\dots&0\\\dots&\dots&\dots&\dots&\dots\\1&0&0&\dots&1\end{bmatrix}$

而這個資料排出的矩陣 X 存在反矩陣且唯一，因為它是一個 d+1 的方陣。

而由此反矩陣可推出 shatter ，代表存在一組 y 可以找到 w，使得 $sign(wX)=y$
就是可以找到一個 function h，其向量表為 w，和 x 相乘後取其正負號，會和 y 吻合。

要讓這個式子成立，其中一個方法就是讓 $wX=y$。
找到 w 滿足這個條件，只需要讓 $w=yX^{-1}$就可以了。
X 的反矩陣就用在這邊。如此，就證明 VC dimension ≥ d+1。

**2. VC dimension ≤ d-1**
==**任何d+2筆資料都不能被所有h shatter**==

假如只保留這三筆，並加入第四筆，就在(1,1)的地方。

加入了這個點。並假設(0,0)是 ╳，(0,1)和(1,0)都是 ○。
如果要能shatter，這新加的點該是 ○ 還是 ╳ ?

答案應該很明顯，必須是 ○。

設式子如下 $x_{4} = x_{2} + x_{3} - x_{1}$
表示 $(1,0)+(0,1)-(0,0)=(1,1)$

兩邊同時乘上代表 h 的各權重之組合 w，
$w^{T}x_{4}= w^{T}x_{2} + w^{T}x_{3} - w^{T}x_{1}$
而上式符合線性相依(L.D)之特質，限制dichotomy的數量。

但若要嚴謹證明，得證明在全部任意 d+2 筆資料都成立，
設此情況如下，$x_{d+2} = a_{1}x_{1}+a_{2}x_{2}+...+a_{d+1}x_{d+1}$。

但這些$a_{1},a_{2},...a_{d+1}$，不一定全為正，所以另外設 w 使其與之 a 同號，讓全部項皆為正，如此一來，$w^{T}x_{d+2}$必須為正，若為負，則無法完成dichotomy。
$w^{T}x_{d+2} = a_{1}w^{T}x_{1}+a_{2}w^{T}x_{2}+...+a_{d+1}w^{T}x_{d+1}$

此時便證明出，任意的d+2筆，只要有線性相依，就能讓它無法被shatter，也就證明 VC dimension ≤ d+1了。

以放兩種情況便能得出：==**VC dimension就是維度+1**==。
而高維度的資料，也可以使用 VC dimension 的概念。

## 關於 VC Dimension 的應用

### $E_{in}, E_{out}$
通常較高 VC Dimension 的 function 能夠降低 training error $E_{in}$
但若 VC Dimension 過高，當$N >> VC \ Dimension$，便可能不成立，$E_{in} ≠ E_{out}$
即表示 testing error 不一定會隨著 training error 降低而降低，而會增長，也可說是 overfitting。

下方為確保$E_{in} = E_{out}$大致成立的通式:


### Neural network
Neural network 其 VC Dimension 為 $O(W)$