[ML] 機器學習基石：第七講 The VC Dimension

ML：基礎學習
課程：機器學習基石
簡介：第七講 The VC Dimension

\(H\) 的 VC dimension

\(d_{VC}(H)\ \Rightarrow \) 最大的 \(N\) 當滿足 \(m_H(N) = 2^N\)
換句話說，\(d_{VC} = k_{min}-1\)

且在資料為二分法時

對於任意 \(g = A ( D ) \in H\) 跟 統計上足夠大的 \(D\)
若 \(N \ge 2, d_{VC} \ge 2\)
則 \(m_H(N) \le N^{d_{VC}} \)
$$ E_{out}(g)\approx E_{in}(g)\ 當\ d_{VC}\ 有限\\ \mathbb{P}\left [ \left | E_{in}(g)-E_{out}(g) \right | > \epsilon \right ]\leq 4\cdot \color{Orange}{(2N)^{d_{VC}}}\cdot e^{-\frac{1}{8}\epsilon ^2N}\\ $$

• 無論任何演算法 \(A\)
• 無論任何機率分佈 \(P\)
• 無論任何目標函數 \(f\)

目前 Perceptron 只證明至二維可適用，那麼多維呢？

• 1D perceptron : \(d_{VC}=2\)
• 2D perceptron : \(d_{VC}=3\)
• d-D perceptron : \(d_{VC}\overset{?}{=}d+1\)

證明兩個方向皆符合

$$ d_{VC}\ge 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 & \vdots & \ddots & 0\\ 1 & 0 & \cdots & 0 & 1 \end{bmatrix} \ 存在反矩陣 $$ 輸出資料 \(\mathbf{y}\) 如下 $$ \mathbf{y}= \begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_{d+1}\\ \end{bmatrix} $$ 令 \(sign(\mathbf{X}\mathbf{w}) = \mathbf{y} \) 的其中一個方式即為 \(\mathbf{X}\mathbf{w} = \mathbf{y} \)
此時使得任意 \(\mathbf{y}\) 皆可找到對應的 \(\mathbf{w}\) 便是可 shatter
因 \(\mathbf{X}\) 存在反矩陣，故 \(\mathbf{X}\mathbf{w} =\mathbf{y} \Leftrightarrow \mathbf{w} =\mathbf{X}^{-1}\mathbf{y}\)
故得證 \(d_{VC}\ge d+1\)

$$ d_{VC}\le d+1 $$

d-D 維度下
$$ \mathbf{X}= \begin{bmatrix} \mathbf{x}_1^T\\ \mathbf{x}_2^T\\ \vdots\\ \mathbf{x}_{d+1}^T\\ \mathbf{x}_{d+2}^T\\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 \\ 1 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & 0\\ 1 & 0 & \cdots & 0 & 1 \\ 1 & ? & \cdots & ? & ? \end{bmatrix} $$ $$ \mathbf{x}_{d+2} = a_1\mathbf{x}_{1}+a_2\mathbf{x}_{2}+\cdots +a_{d+1}\mathbf{x}_{d+1}\\ a_n \in \{1,0,-1\} $$ 必定存在線性相依，故不存在反矩陣，無法完全 shatter \(d > d+2\)，得證 \(d_{VC}\le d+1\)
或換句話說
如下，\(\mathbf{w}^T\mathbf{x}_{n}\) 已固定，且 \(a_n \in \{1,0,-1\}\)，故 \(\mathbf{w}^T\mathbf{x}_{d+2}\) 也被固定，導致無法產生另一組相反的結果，使得無法 shatter
$$ \mathbf{w}^T\mathbf{x}_{d+2} = \mathbf{w}^Ta_1\mathbf{x}_{1}+\mathbf{w}^Ta_2\mathbf{x}_{2}+\cdots +\mathbf{w}^Ta_{d+1}\mathbf{x}_{d+1} $$

VC dimension 在二元分類中的意義

\(H\) 的有效自由度 \(d_{VC}(H)\): powerfulness of \(H\)
大概為可調整的參數數目，但不全然對，猜測參數需各自獨立才對

$$\mathbb{P}\left [ \left | E_{in}(g)-E_{out}(g) \right | > \epsilon \right ]\leq 4\cdot \color{Orange}{(2N)^{d_{VC}}}\cdot e^{-\frac{1}{8}\epsilon ^2N}$$

	讓 \(E_{out}(g)\to E_{in}(g)\)	讓 \(E_{in}(g) \to 0 \)
小 \(d_{VC}\)	Yes	No，自由度太少
大 \(d_{VC}\)	No	Yes

Model 複雜度的代價

假設發生好事情的機率為 \(1-\delta\)

$$ \mathbb{P}\left [ \left | E_{in}(g)-E_{out}(g) \right | > \epsilon \right ]\leq 4\cdot \color{Orange}{(2N)^{d_{VC}}}\cdot e^{-\frac{1}{8}\epsilon ^2N} $$ $$ \begin{align*} {\color{Purple} \delta} &= 4\cdot \color{Orange}{(2N)^{d_{VC}}}\cdot e^{-\frac{1}{8}\epsilon ^2{\color{Cyan} N}}\\ \frac{{\color{Purple} \delta}}{4\cdot \color{Orange}{(2N)^{d_{VC}}}} &= e^{-\frac{1}{8}\epsilon ^2{\color{Cyan} N}}\\ ln\left (\frac{4\cdot \color{Orange}{(2N)^{d_{VC}}}}{{\color{Purple} \delta}} \right ) &= \frac{1}{8}\epsilon ^2{\color{Cyan} N}\\ \sqrt{\frac{8}{{\color{Cyan} N}}ln\left (\frac{4\cdot \color{Orange}{(2N)^{d_{VC}}}}{{\color{Purple} \delta}} \right )} &= \epsilon\\ \end{align*} $$ $$ |E_{in}(g)-E_{out}(g)| \le \sqrt{\frac{8}{{\color{Cyan} N}}ln\left (\frac{4\cdot \color{Orange}{(2N)^{d_{VC}}}}{{\color{Purple} \delta}} \right )}\\ E_{in}(g)-\sqrt{\frac{8}{{\color{Cyan} N}}ln\left (\frac{4\cdot \color{Orange}{(2N)^{d_{VC}}}}{{\color{Purple} \delta}} \right )} \le E_{out}(g) \le E_{in}(g)+\sqrt{\frac{8}{{\color{Cyan} N}}ln\left (\frac{4\cdot \color{Orange}{(2N)^{d_{VC}}}}{{\color{Purple} \delta}} \right )}\\ \Omega ({\color{Cyan} N},{\color{Orange} H},{\color{Purple} \delta})= \sqrt{\frac{8}{{\color{Cyan} N}}ln\left (\frac{4\cdot \color{Orange}{(2N)^{d_{VC}}}}{{\color{Purple} \delta}} \right )} $$

\(\Omega ({\color{Cyan} N},{\color{Orange} H},{\color{Purple} \delta})\) 為 Model 複雜度的代價

\(d_{VC}\) 的最佳解位在中間

實際例子

假設 \(\epsilon=0.1,\delta=0.1,d_{VC}=3\) 那麼 \(N\) 至少需要多少筆？

• N=      100 => \(\delta=2.82 \cdot 10^7\)
• N=    1000 => \(\delta=9.17 \cdot 10^9\)
• N=  10000 => \(\delta=1.19 \cdot 10^8\)
• N=100000 => \(\delta=1.65 \cdot 10^{-38}\)
• N=  29300 => \(\delta=9.99 \cdot 10^{-2}\) 
• \(N \approx 10000 \cdot d_{VC}\)

實務上 \(N \approx 10 \cdot d_{VC}\) 已足夠

所以 VC Bound 其實是相當的寬鬆
正因為對每個 model 都差不多寬鬆，所以可以用來比較不同 model
並且取其哲學意義，像是不要一昧追求 \(d_{VC}\) 的最大化