ML：基礎學習
課程：
機器學習基石
簡介：第六講 Theory of Generalization
Bounding Function
\(B(N,k) = m_H(N)\ 當\ break\ point = k\ 時\)
補滿半邊，然而在對角線上，則為 \(2^N -1\)，那麼剩下的呢？
| \(B(N,k)\)
|
| \(k\) |
| 1 |
2 |
3 |
4 |
5 |
6 |
\(\cdots\) |
|
| \(N\) |
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
| 6 |
| \(\vdots\) |
|
| 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\) |
| \(\vdots\) | \(\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{align*}
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{align*}
$$
推導得知
$$
\begin{align*}
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{align*}
$$
事實上 \(\le\) 可為 \(=\)
| \(B(N,k)\)
|
| \(k\) |
| 1 |
2 |
3 |
4 |
5 |
6 |
\(\cdots\) |
|
| \(N\) |
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
| 6 |
| \(\vdots\) |
|
| 1 | 2 | 2 | 2 | 2 | 2 | \(\cdots\) |
| 1 | 3 | 4 | 4 | 4 | 4 | \(\cdots\) |
| 1 | \(\le4\) | 7 | 8 | 8 | 8 | \(\cdots\) |
| 1 | \(\le5\) | \(\le11\) | 15 | 16 | 16 | \(\cdots\) |
| 1 | \(\le6\) | \(\le16\) | \(\le26\) | 31 | 32 | \(\cdots\) |
| 1 | \(\le7\) | \(\le22\) | \(\le42\) | \(\le57\) | 63 | \(\cdots\) |
| \(\vdots\) | \(\ddots\) |
|
$$B(N,k)\le\sum_{i=0}^{k-1}\binom{N}{i}$$
1. \(N=1:B(1,1)\le\binom{1}{0}=1\)
2. \(假設\ B(N,k)\le\sum_{i=0}^{k-1}\binom{N}{i}\)
3.
$$
\begin{align*}
B(N+1,k)&\le B(N,k)+B(N,k-1)\\
&\le\sum_{i=0}^{k-1}\binom{N}{i}+\sum_{i=0}^{k-2}\binom{N}{i}\\
&=\sum_{i=0}^{k-1}\binom{N}{i}+\sum_{i=1}^{k-1}\binom{N}{i-1}\\
&=1+\sum_{i=1}^{k-1}\left (\binom{N}{i}+\binom{N}{i-1} \right )\\
&=1+\sum_{i=1}^{k-1}\binom{N+1}{i}\\
&=\sum_{i=0}^{k-1}\binom{N+1}{i}
\end{align*}
$$
lemma
$$
\begin{align*}
&\binom{N}{k}+\binom{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!}\\
&=\binom{N+1}{k}
\end{align*}
$$
2D perceptrons break point = 4
$$
m_H(N) \le \frac{1}{6}N^3+\frac{5}{6}N+1
$$
VC bound
$$
\mathbb{P}\left [ \exists h \in H s.t. \left | E_{in}(h)-E_{out}(h) \right | > \epsilon \right ] \le 2 \cdot \color{Orange}{ m_H(N)}\cdot e^{-2\epsilon ^2N}
$$
若 \(N\) 夠大
$$
\mathbb{P}\left [ \exists h \in H s.t. \left | E_{in}(h)-E_{out}(h) \right | > \epsilon \right ] \le 4 \cdot m_H(2N) \cdot e^{-\frac{1}{8}\epsilon^2N}
$$
證明
$$
\mathbb{P}\left [ \exists h \in H s.t. \left | E_{in}(h)-E_{out}(h) \right | > \epsilon \right ] \le 2 \cdot \color{Red} 2 \cdot \color{Orange}{ m_H(2N)}\cdot e^{-2\cdot \color{Purple}{\frac{1}{16}}\epsilon ^2N}
$$
用有限 \({E_{in}}'\) 取代無限的 \(E_{out}\)，詳細證明可參考
此篇
$$
\begin{align*}
&\frac{1}{2}\mathbb{P}\left [ \exists h \in H\ s.t. \left | E_{in}(h)-E_{out}(h) \right | > \epsilon \right ] \\
\leq\ &\mathbb{P}\left [ \exists h \in H\ s.t. \left | E_{in}(h)-{E_{in}}'(h) \right | > \frac{\epsilon}{2} \right ]
\end{align*}
$$
物理意義
如下圖，\(N\) 夠大時，可看作 \(E_{out}\) 在隨機抽取 \(E_{in}\) 整體分佈的中心點
\(|E_{in}-E_{out}|>\epsilon\) 的機率
則會位在兩邊，但因為取一半，所以只有在右邊，也就是需大過紅色區塊，機率必小於鐘形的一半
此時取 \({E_{in}}'\)，\({D}'\)大小為 \(N\)
\(|E_{in}-{E_{in}}'|>\frac{\epsilon}{2}\) 的機率
則會至少包含鐘形另一半的機率，再加上大過綠色區塊的部分，機率則大於原先的 \(|E_{in}-E_{out}|>\epsilon\)
因將 \({E_{in}}'\) 取代 \(E_{out}\)，所以實際上大小已變為 \(D+{D}'=2N\)
此時將
上一講的概念代入，得到 \(m_H(2N)\) 並且 \(h\) 是固定且最大機率的，故得到下式
$$
\begin{aligned}
\mathbb{P}[BAD] &\leq 2\mathbb{P}\left [ \exists h \in H\ s.t. \left | E_{in}(h)-{E_{in}}'(h) \right | > \frac{\epsilon}{2} \right ]\\
&\leq 2 \cdot m_H(2N) \cdot \mathbb{P}\left [ \color{Red}{fixed}\ h \ s.t. \left | E_{in}(h)-{E_{in}}'(h) \right | > \frac{\epsilon}{2} \right ]
\end{aligned}
$$
此時代入 Hoeffding's Inequality，\(\left | E_{in}-{E_{in}}' > \frac{\epsilon}{2}\right | \Leftrightarrow
\left | E_{in}-\frac{E_{in}+{E_{in}}'}{2} > \frac{\epsilon}{4}\right |\)
\(\frac{E_{in}+{E_{in}}'}{2}\) 就是瓶子內的機率，故得到下式
$$
\begin{aligned}
\mathbb{P}[BAD] &\leq 2 \cdot m_H(2N) \cdot \mathbb{P}\left [ \color{Yellow}{fixed}\ h \ s.t. \left | E_{in}(h)-{E_{in}}'(h) \right | > \frac{\epsilon}{2} \right ]\\
&\leq 2 \cdot m_H(2N) \cdot 2e^{-2(\frac{\epsilon}{4})^2N}
\end{aligned}
$$
故得證 Vapnik-Chervonenkis (VC) bound:
$$
\mathbb{P}\left [ \exists h \in H s.t. \left | E_{in}(h)-E_{out}(h) \right | > \epsilon \right ] \le 4 \cdot m_H(2N) \cdot e^{-\frac{1}{8}\epsilon^2N}
$$
所以 2D perceptrons 代入 \(m_H(N) = O(N^3)\) 可收斂之
注意：VC bound 是非常寬鬆的上限
例：在 positive rays, \(m_H(N) = N + 1\)，\(\epsilon = 0.1\ and\ N = 10000\)
得到 \(VC\ bound= 0.298\)
即使是 10000筆資料，錯誤上限機率也有近 30%
把 \(X_4\) 遮掉來看
故
留言
張貼留言