# VC Dimension

$\mathcal{H}$ 可以擊敗 (shatter) 的最大 N，換句話說就是 break point 減 1。

上次的最後結論：

$$
\mathbb{P}[\exists h \in \mathcal{H} \ s.t.|E_{in}(h)-E_{out}(h)|>\epsilon]\le 4m_{\mathcal{H}}(2N)e^{-\frac{1}{8}\epsilon^{2}N}
$$

只要當 $N\ge2,K\ge3$，則：

$$
m_{\mathcal{H}}(N)\le B(N,K)=\sum_{i=0}^{k-1}\binom{N}{i}\le N^{k-1}
$$

所以就可以把 k-1 替換成 VC Dimension

$$
m_{\mathcal{H}}(N)\le N^{d_{vc}}
$$

# PLA 的 $d_{vc}$

在簡單的維度中：

- 1D perceptron (pos/neg rays)
- $d_{vc}=2$
- 2D perceptrons
- $d_{vc}=3$

並且有個漂亮的結論：

$$
\text{for N D perceptrons}\\
d_{vc}=N+1
$$

# 證明

## $d_{vc}\ge d+1$

證明存在某 d+1 個 input，我們可以創造出 $2^{d+1}$ 種可能。

我們可以夠見出特殊的 $\mathbf{X}$：

$$
\mathbf{X}=\begin{bmatrix}
-\ \mathbf{x}_{1}^{T} - \\
-\ \mathbf{x}_{2}^{T} - \\
\vdots \\
-\ \mathbf{x}_{d+1}^{T} -
\end{bmatrix}=
\begin{bmatrix}
1 & 0 & 0 & \cdots & 0\\
1 & 1 & 0 & \cdots & 0\\
\vdots & \vdots & & \ddots & 0\\
1 & 0 & \cdots & 0 & 1
\end{bmatrix}
$$

也就是對角線全都是 1，並且第一行也都是 1 的矩陣，而這個矩陣是可逆的，因此：

$$
\mathbf{X}\mathbf{w}=\mathbf{y}\\
\Rightarrow \mathbf{w} =\mathbf{X}^{-1}\mathbf{y}
$$

而我們可以創造出 $2^{d+1}$ 種 $\mathbf{y}$，也就代表這個 $\mathcal{H}$ 確實可以有這麼多種 $\mathbf{w}$ 來創造出 $2^{d+1}$ 種 $\mathbf{y}$。

## $d_{vc}\le d+1$

也就是要證明我們無法擊敗任何種 d+2 個 inputs。

對於任意一個 $\mathbf{X}$：

$$
\mathbf{X}=\begin{bmatrix}
-\ \mathbf{x}_{1}^{T} - \\
-\ \mathbf{x}_{2}^{T} - \\
\vdots \\
-\ \mathbf{x}_{d+1}^{T} -
\end{bmatrix}
$$

根據線性獨立的關係，可以知道：

$$
\mathbf{x}_{d+2}=a_{1}\mathbf{x}_{1}+a_{2}\mathbf{x}_{2}...+a_{d+1}\mathbf{x}_{d+1}
$$

在等號右邊的每個項，其係數 a 跟其所對應的 y 同號，也就是右邊的項總和大於 0。

如果兩邊都對 $\mathbf{w}$ 內積，會得到：

$$
\mathbf{w}^{T}\mathbf{x}_{d+2}=a_{1}\mathbf{w}^{T}\mathbf{x}_{1}+a_{2}\mathbf{w}^{T}\mathbf{x}_{2}...+a_{d+1}\mathbf{w}^{T}\mathbf{x}_{d+1}\\
\Rightarrow \mathbf{w}^{T}\mathbf{x}_{d+2} > 0
$$

也就是說我們無法產生出 $(\mathbf{x}_{d+2},-1)$ 這個點。

這樣就證明了 $\mathbf{X}$ 無法擊敗任意一種 d+2 個點。

---

# Degrees of Freedom 自由度

- $h$ 的參數(parameters) $\mathbf{w}=(w_{0},w_{1},...,w_{d})$ 創造了自由度
- $h$ 的量(quantity) $M=|\mathcal{H}|$ 大概模擬出了自由度
- $h$ 的力量(power) $d_{vc}$ 有效的自由度
- 在 PLA 的例子中是「有效的二元(binary)自由度」

:::warning
在實務上，通常來說：
$$
d_{vc} \approx \text{# free parameters}
$$
:::

# $M$ 和 $d_{vc}$

回顧前面 ML 的兩個重要問題：

1. 我們能否確保 $E_{in}(g) \approx E_{out}(g)$
2. 我們能否讓 $E_{in}(g)$ 夠小

- small $M$
1. 可以，因為小的 $M$ 代表 $\mathbb{P}[BAD]\le 2Me...$ 的機率小
2. 不行，因為選擇 choices 太少
- small $d_{vc}$
1. 可以，因為小的 $d_{vc}$ 代表 $\mathbb{P}[BAD]\le 4(2N)^{d_{vc}}e...$ 的機率小
2. 不行，因為力量 power 太小
- large $M$
1. 不行，因為大的 $M$ 代表 $\mathbb{P}[BAD]\le 2Me...$ 的機率大
2. 可以，因為選擇 choices 很多
- large $d_{vc}$
1. 不行，因為大的 $d_{vc}$ 代表 $\mathbb{P}[BAD]\le 4(2N)^{d_{vc}}e...$ 的機率大
2. 可以，因為力量 power 很強

# Model Complexity

$$
\mathbb{P}_{\mathcal{D}}[|E_{in}(g)-E_{out}(g)|>\epsilon]\le 4(2N)^{d_{vc}}e^{-\frac{1}{8}\epsilon^{2}N}
$$

因為通常是給一個固定的壞事情機率，所以會令不等式右邊為：

$$
\delta=4(2N)^{d_{vc}}e^{-\frac{1}{8}\epsilon^{2}N}\\
\Rightarrow \epsilon = \sqrt{\frac{8}{N}ln\left(\frac{4(2N)^{d_{vc}}}{\delta}\right)}
$$

這樣就可以知道 $\epsilon$ 跟 $\delta$ 的關係。

在一開始提到 Hoeffding 的時候，有提到可以反著看該不等式，也就是說發生好事情的機會很大：

$$
\mathbb{P}_{\mathcal{D}}[|E_{in}(g)-E_{out}(g)|\le\epsilon]>1 - \delta
$$

加上上面，就可以把 Hoeffding 裡面拆成：

$$
|E_{in}(g)-E_{out}(g)|\le \epsilon\\
\Rightarrow E_{out}(g) \le E_{in}(g) + \sqrt{\frac{8}{N}ln\left(\frac{4(2N)^{d_{vc}}}{\delta}\right)}
$$

根號那坨就是所謂的模型複雜度 model complexity。

:::warning
- 從該不等式可以發現，有很大的機會，$E_{out}(g)$ 會隨著 $d_{vc}$ 的上升而上升。
- 在前面 $d_{vc}$ 跟 $M$ 比較的地方，有提到 $d_{vc}$ 越大則 $E_{in}(g)$ 越小。

兩個合在一起看就會發現：
- 如果 $d_{vc}$ 太大，會讓 $E_{out}(g)$ 跟 $E_{in}(g)$ 差太遠
- 如果 $d_{vc}$ 太小，會讓 $E_{in}(g)$ 太大

也就是說需要合適的 $d_{vc}$
:::

# Sample Complexity

理論上，$N \approx 10000d_{vc}$ 才會使機率夠小。

但是實務上，$N \approx 10d_{vc}$ 就夠了。

:::success
原因是因為 Hoeffding 是個很寬鬆的邊界：
- 使用 Hoeffding 來推論未知的 $E_{out}(g)$
- 適用任何分布，任何目標函數
- 使用 $m_{\mathcal{H}}(N)$ 替換了 $|\mathcal{H}(\mathbf{x}_{1}...,\mathbf{x}_{N})|$
- 適用任何資料
- 使用 $N^{d_{vc}}$ 替換了$m_{\mathcal{H}}(N)$
- 適用任何具有相同 $d_{vc}$ 的 $\mathcal{H}$
- 在壞資料的發生機率情況使用 Union Bound
- 適用任何 $\mathcal{A}$ 所做出的任何選擇
:::