[ML] 機器學習基石：第六講 Theory of Generalization

ML：基礎學習
課程：機器學習基石
簡介：第六講 Theory of Generalization

Bounding Function

$B(N,k)=m_H(N)\mathrm{當}breakpoint=k\mathrm{時}$

補滿半邊，然而在對角線上，則為 $2^N-1$，那麼剩下的呢？

$B(N,k)$	$k$ 1 2 3 4 5 6 $\cdots$
$N$ 1 2 3 4 5 6 $⋮$	1 2 2 2 2 2 $\cdots$ 1 3 4 4 4 4 $\cdots$ 1 7 8 8 8 $\cdots$ 1 15 16 16 $\cdots$ 1 31 32 $\cdots$ 1 63 $\cdots$ $⋮$ $\ddots$

先看 $B(4,3)$，如下圖，用程式跑出左邊的組合，再分類成右邊

將成雙的定義為 $2\alpha$ 個，單個的定義為 $\beta$

把 $X_4$ 遮掉來看
因 $B(4,3)$ 任意三個點不能 shatter，那麼只剩下三個點也不能 shatter，故 $\alpha +\beta \le B(3,3)$
此時若只單看橘色的部分，若有兩個點 shatter，此時也會造成 $B(4,3)$ shatter，故 $\alpha \le B(3,2)$

故

$$\begin{array}{rl}B(4,3)& =2\alpha +\beta \\ \alpha +\beta & \le B(3,3)\\ \alpha & \le B(3,2)\\ \Rightarrow B(4,3)& \le B(3,3)+B(3,2)\end{array}$$

推導得知

$$\begin{array}{rl}B(N,k)& =2\alpha +\beta \\ \alpha +\beta & \le B(N-1,k)\\ \alpha & \le B(N-1,k-1)\\ \Rightarrow B(N,k)& \le B(N-1,k)+B(N-1,k-1)\end{array}$$

事實上 $\le$ 可為 $=$

$B(N,k)$	$k$ 1 2 3 4 5 6 $\cdots$
$N$ 1 2 3 4 5 6 $⋮$	1 2 2 2 2 2 $\cdots$ 1 3 4 4 4 4 $\cdots$ 1 $\le 4$ 7 8 8 8 $\cdots$ 1 $\le 5$ $\le 11$ 15 16 16 $\cdots$ 1 $\le 6$ $\le 16$ $\le 26$ 31 32 $\cdots$ 1 $\le 7$ $\le 22$ $\le 42$ $\le 57$ 63 $\cdots$ $⋮$ $\ddots$

$$B(N,k)\le \sum _{i=0}^{k-1}(\genfrac{}{}{0ex}{}{N}{i})$$

1. $N=1:B(1,1)\le (\genfrac{}{}{0ex}{}{1}{0})=1$
2. $\mathrm{假}\mathrm{設}B(N,k)\le \sum _{i=0}^{k-1}(\genfrac{}{}{0ex}{}{N}{i})$
3. $$\begin{array}{rl}B(N+1,k)& \le B(N,k)+B(N,k-1)\\ & \le \sum _{i=0}^{k-1}(\genfrac{}{}{0ex}{}{N}{i})+\sum _{i=0}^{k-2}(\genfrac{}{}{0ex}{}{N}{i})\\ & =\sum _{i=0}^{k-1}(\genfrac{}{}{0ex}{}{N}{i})+\sum _{i=1}^{k-1}(\genfrac{}{}{0ex}{}{N}{i-1})\\ & =1+\sum _{i=1}^{k-1}((\genfrac{}{}{0ex}{}{N}{i})+(\genfrac{}{}{0ex}{}{N}{i-1}))\\ & =1+\sum _{i=1}^{k-1}(\genfrac{}{}{0ex}{}{N+1}{i})\\ & =\sum _{i=0}^{k-1}(\genfrac{}{}{0ex}{}{N+1}{i})\end{array}$$ lemma $$\begin{array}{rl}& (\genfrac{}{}{0ex}{}{N}{k})+(\genfrac{}{}{0ex}{}{N}{k-1})\\ & =\frac{N\cdot (N-1)\cdots [N-(k-1)]}{k!}+\frac{N\cdot (N-1)\cdots [N-(k-2)]}{(k-1)!}\\ & =\frac{N\cdot (N-1)\cdots [N-(k-1)]}{k!}+\frac{N\cdot (N-1)\cdots [N-(k-2)]\cdot k}{(k-1)!\cdot k}\\ & =\frac{N\cdot (N-1)\cdots [N-(k-1)]}{k!}+\frac{N\cdot (N-1)\cdots [N-(k-2)]\cdot k}{k!}\\ & =\frac{N\cdot (N-1)\cdots [N-(k-2)]\cdot (N+1)}{k!}\\ & =\frac{(N+1)\cdot N\cdot (N-1)\cdots [N+1-(k-1)]}{k!}\\ & =(\genfrac{}{}{0ex}{}{N+1}{k})\end{array}$$

2D perceptrons break point = 4

$$m_H(N)\le \frac{1}{6}{N}^3+\frac{5}{6}N+1$$

VC bound

$$\mathbb{P}[\mathrm{\exists }h\in Hs.t.|E_{in}(h)-E_{out}(h)|>ϵ]\le 2\cdot m_H(N)\cdot e^{-2{ϵ}^{2}N}$$

若 $N$ 夠大

$$\mathbb{P}[\mathrm{\exists }h\in Hs.t.|E_{in}(h)-E_{out}(h)|>ϵ]\le 4\cdot m_H(2N)\cdot e^{-\frac{1}{8}{ϵ}^{2}N}$$

證明

$$\mathbb{P}[\mathrm{\exists }h\in Hs.t.|E_{in}(h)-E_{out}(h)|>ϵ]\le 2\cdot 2\cdot m_H(2N)\cdot e^{-2\cdot \frac{1}{16}{ϵ}^{2}N}$$

用有限 ${E_{in}}^{\prime }$ 取代無限的 $E_{out}$，詳細證明可參考此篇
$$\begin{array}{rl}& \frac{1}{2}\mathbb{P}[\mathrm{\exists }h\in Hs.t.|E_{in}(h)-E_{out}(h)|>ϵ]\\ \le & \mathbb{P}[\mathrm{\exists }h\in Hs.t.|E_{in}(h)-{E_{in}}^{\prime }(h)|>\frac{ϵ}{2}]\end{array}$$

物理意義
如下圖，$N$ 夠大時，可看作 $E_{out}$ 在隨機抽取 $E_{in}$ 整體分佈的中心點
$|E_{in}-E_{out}|>ϵ$ 的機率
則會位在兩邊，但因為取一半，所以只有在右邊，也就是需大過紅色區塊，機率必小於鐘形的一半

此時取 ${E_{in}}^{\prime }$，$D^{\prime }$大小為 $N$
$|E_{in}-{E_{in}}^{\prime }|>\frac{ϵ}{2}$ 的機率
則會至少包含鐘形另一半的機率，再加上大過綠色區塊的部分，機率則大於原先的 $|E_{in}-E_{out}|>ϵ$

因將 ${E_{in}}^{\prime }$ 取代 $E_{out}$，所以實際上大小已變為 $D+D^{\prime }=2N$
此時將上一講的概念代入，得到 $m_H(2N)$ 並且 $h$ 是固定且最大機率的，故得到下式

$$\begin{array}{rl}\mathbb{P}[BAD]& \le 2\mathbb{P}[\mathrm{\exists }h\in Hs.t.|E_{in}(h)-{E_{in}}^{\prime }(h)|>\frac{ϵ}{2}]\\ & \le 2\cdot m_H(2N)\cdot \mathbb{P}\left[fixedhs.t.|E_{in}(h)-{E_{in}}^{\prime }(h)|>\frac{ϵ}{2}\right]\end{array}$$

此時代入 Hoeffding's Inequality，$|E_{in}-{E_{in}}^{\prime }>\frac{ϵ}{2}|\iff |E_{in}-\frac{E_{in}+{E_{in}}^{\prime }}{2}>\frac{ϵ}{4}|$
$\frac{E_{in}+{E_{in}}^{\prime }}{2}$ 就是瓶子內的機率，故得到下式

$$\begin{array}{rl}\mathbb{P}[BAD]& \le 2\cdot m_H(2N)\cdot \mathbb{P}\left[fixedhs.t.|E_{in}(h)-{E_{in}}^{\prime }(h)|>\frac{ϵ}{2}\right]\\ & \le 2\cdot m_H(2N)\cdot 2e^{-2(\frac{ϵ}{4}{)}^{2}N}\end{array}$$

故得證 Vapnik-Chervonenkis (VC) bound:

$$\mathbb{P}[\mathrm{\exists }h\in Hs.t.|E_{in}(h)-E_{out}(h)|>ϵ]\le 4\cdot m_H(2N)\cdot e^{-\frac{1}{8}{ϵ}^{2}N}$$

所以 2D perceptrons 代入 $m_H(N)=O(N^3)$ 可收斂之

注意：VC bound 是非常寬鬆的上限

例：在 positive rays, $m_H(N)=N+1$，$ϵ=0.1andN=10000$
得到 $VCbound=0.298$
即使是 10000筆資料，錯誤上限機率也有近 30%