章節名稱: training versus testing

一 Recap and Preview

複習

複習一下前面的章節，主要可以將學習拆成兩個問題:

1. $E_{in}(g)$ 和 $E_{out}(g)$ 到底接不接近
2. 要怎麼樣讓 $E_{in}(g)$ 變得更小

Hypothesis set 的大小

(Hoeffding’s Inequality)

$\vert{H}\vert = M$ ， 也就是 Hypothesis set 的大小，會影響到上面的兩個問題。

$M$ 太小:

1. $E_{in}(g)$ 和 $E_{out}(g)$ 不接近的機率很小 => GOOD
2. 選擇不夠多，不一定能找到 $E_{in}(g)$ 很小的 => BAD

$M$ 太大:

1. $E_{in}(g)$ 和 $E_{out}(g)$ 不接近的機率比較大 => BAD
2. 選擇夠多 => GOOD

那無限多個 $M$ 就是不好的了嗎？(如 PLA 就是無限大的)

練習

$$\begin{aligned} &2\times {M}e^{-2\epsilon^2N} = \delta = 0.05 \\\\ &e^{-2\epsilon^2N} = \frac {\delta}{2M} \\\\ \end{aligned}$$

兩邊同取 $ln$

$$\begin{aligned} &-2\epsilon^2N = ln {(\frac {\delta}{2M})} \\\\ &N =- \frac {1}{2\epsilon^2}ln {(\frac {\delta}{2M})} = \frac {1}{2\epsilon^2}ln {(\frac {2M}{\delta})}\\\\ \end{aligned}$$

二 Effective Number of Lines

BAD event and M

BAD event: $E_{in}(h) 和 E_{out}(h) 相差很遠$

先回顧一下 Hoeffding’s Inequality 的部分，我們為了讓演算法自由挑選 hypothesis ，所以計算 BAD event 對某個 h 時的機率，再對 M 個發生 BAD 的取聯集，就可知道它們的上限(Union Bound)。

問題在於如果 M 是無限多時，用 union bound 算出來的值可能無限大或非常大，這樣就沒有意義了。

可以用 union bound 去算的假設是，每個 h 它們發生 BAD event 的 data set 是不太一樣的(不太會重疊)。

但事實上在兩個相近的 hypothesis 時，它們發生 BAD event 的 data set 很可能是相近的。
例如 PLA 中兩條相近的線，它們 大部分 的 $E_{in}(h)$ 是一樣的。

它的圖形就像下圖右邊，圈圈是有很多重疊的。而我們的 union bound 並沒有考量到這個，所以造成了 over-estimating ，才會無法處理 M 是無限大的狀況。

而為了計算出重疊的部分，我們可以試著先將 無限多 的 hypothesis 分類成 有限多 的種類。

分類 hypothesis

從最簡單的開始看，資料只有 一 個點，而全部的線(h)可以分成兩種:

• 讓 X 是叉
• 讓 X 是圈

而有 兩 個點時，(O,X),(X,O),(O,O),(X,X) 有四種。

接著來看 三 個點時:

可以發現會因為點的位置不同，種類數也不同。

四 個點:

乘二是因為圈的換成叉的又是另一種了。

我們可以總結出 effective number of lines 也就是有效的種類數:

maximum kinds of lines with respect to N inputs

而很顯然的每個點都有兩種可能，所以 $effective(N) \le 2^N$ ，再把本來式子裡的 M 取代掉。如果 $effective(N)$ 又小於 $2^N$ 很多，且 N 夠大(使 exp 那項下降)，此時式子右邊就會接近零，也就是 BAD event 發生的機率非常小。

這樣在有無限多個 M 時，只要分類成有限的種類，就能學到東西了！

練習

五個點所能分出來最多的種類是？ 22 ($\le 2^5$) 種
可以完成圈或叉再乘二即可。

(往後會再證明如何算出最大的種類)