[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}}$
$$\begin{gathered} E_{out}(g)\approx E_{in}(g)\mathrm{當}{d}_{VC}\mathrm{有}\mathrm{限} \\ \mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 4\cdot (2N{)}^{d_{VC}}\cdot e^{-\frac{1}{8}{ϵ}^{2}N} \end{gathered}$$

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

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

• 1D perceptron : $d_{VC}=2$
• 2D perceptron : $d_{VC}=3$
• d-D perceptron : $d_{VC}\stackrel{?}{=}d+1$

證明兩個方向皆符合

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

假設有輸入資料 $\mathbf{X}$ 如下 $$\mathbf{X}=\left[\begin{array}{c}{\mathbf{x}}_1^T\\ {\mathbf{x}}_2^T\\ ⋮\\ {\mathbf{x}}_{d+1}^T\end{array}\right]=\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ 1& 1& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & 0\\ 1& 0& \cdots & 0& 1\end{array}\right]\mathrm{存}\mathrm{在}\mathrm{反}\mathrm{矩}\mathrm{陣}$$ 輸出資料 $\mathbf{y}$ 如下 $$\mathbf{y}=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_{d+1}\end{array}\right]$$ 令 $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}\iff \mathbf{w}={\mathbf{X}}^{-1}\mathbf{y}$
故得證 $d_{VC}\ge d+1$

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

d-D 維度下
$$\mathbf{X}=\left[\begin{array}{c}{\mathbf{x}}_1^T\\ {\mathbf{x}}_2^T\\ ⋮\\ {\mathbf{x}}_{d+1}^T\\ {\mathbf{x}}_{d+2}^T\end{array}\right]=\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ 1& 1& 0& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & 0\\ 1& 0& \cdots & 0& 1\\ 1& ?& \cdots & ?& ?\end{array}\right]$$ $$\begin{gathered} {\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\} \end{gathered}$$ 必定存在線性相依，故不存在反矩陣，無法完全 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}}^T{a}_1{\mathbf{x}}_1+{\mathbf{w}}^T{a}_2{\mathbf{x}}_2+\cdots +{\mathbf{w}}^T{a}_{d+1}{\mathbf{x}}_{d+1}$$

VC dimension 在二元分類中的意義

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

$$\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 4\cdot (2N{)}^{d_{VC}}\cdot e^{-\frac{1}{8}{ϵ}^{2}N}$$

	讓 $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}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 4\cdot (2N{)}^{d_{VC}}\cdot e^{-\frac{1}{8}{ϵ}^{2}N}$$ $$\begin{array}{rl}\delta & =4\cdot (2N{)}^{d_{VC}}\cdot e^{-\frac{1}{8}{ϵ}^{2}N}\\ \frac{\delta }{4\cdot (2N{)}^{d_{VC}}}& =e^{-\frac{1}{8}{ϵ}^{2}N}\\ ln\left(\frac{4\cdot (2N{)}^{d_{VC}}}{\delta }\right)& =\frac{1}{8}{ϵ}^{2}N\\ \sqrt{\frac{8}{N}ln\left(\frac{4\cdot (2N{)}^{d_{VC}}}{\delta }\right)}& =ϵ\end{array}$$ $$\begin{gathered} |E_{in}(g)-E_{out}(g)|\le \sqrt{\frac{8}{N}ln\left(\frac{4\cdot (2N{)}^{d_{VC}}}{\delta }\right)} \\ {E}_{in}(g)-\sqrt{\frac{8}{N}ln\left(\frac{4\cdot (2N{)}^{d_{VC}}}{\delta }\right)}\le E_{out}(g)\le E_{in}(g)+\sqrt{\frac{8}{N}ln\left(\frac{4\cdot (2N{)}^{d_{VC}}}{\delta }\right)} \\ \mathrm{\Omega }(N,H,\delta )=\sqrt{\frac{8}{N}ln\left(\frac{4\cdot (2N{)}^{d_{VC}}}{\delta }\right)} \end{gathered}$$

$\mathrm{\Omega }(N,H,\delta )$ 為 Model 複雜度的代價

$d_{VC}$ 的最佳解位在中間

實際例子

假設 $ϵ=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}$ 的最大化