三 Effective Number of Hypotheses

Hypothesis 的數量

上一節有講過如果用線，平面上有幾種不同的線。這邊要更延伸探討 hypothesis 的數量。

先定義一下名詞 dichotomy ，其意思是二分，也就是把手上的點分成兩堆，而我們想知道的是 hypothesis set 可以做出多少種不一樣的 dichotomy，例如: (ooxx),(oxox) 等等，而這些就是產生出來的 dichotomy。

我們把這些 dichotomy 放進一個 集合，表示成: $\mathcal{H}(x_1,x_2,\ldots,x_N)$ 。

而這跟 hypothesis set 的差別在於

hypothesis set :

• 每個 hypothesis 可以對空間所有的點來進行取值。
• 其大小可能是無限(例如平面上所有的線)

dichotomy $\mathcal{H}$:

• 只對 N 個特定的點來取值
• 其大小就是 $2^N$

(可回顧上集的內容)

現在我們要來看能不能用 $\vert \mathcal{H}(x_1,x_2,\ldots,x_N)\vert$ 來 取代 Hoeffding’s Inequality 裡的 M。

$2\times {M}e^{-2\epsilon^2N}$

Growth Function

而很明顯的 $\vert \mathcal{H}(x_1,x_2,\ldots,x_N)\vert$ 取決於 $x_1,x_2,\dots,x_n$ ，為了不要依賴它們，我們就改算 最多 有幾種。就好像是每次都抓不同把 x 來算，最後取最大的值，並且把結果表示成: $m_{\mathcal{H}}(N)$ 如圖所示。

就很像先前所講的 線在 2D 的種類數: $2^N$ ，就是 $m_{\mathcal{H}}(N)$，稱為 Growth Function (成長函數)。

1D 的 hypothesis set

也就是在數線上的一些點，而其 hypothesis 就是 門檻值(threshold)，只要超過它就是圈的(+1)，反之是叉(-1)。這個 hypothesis 就叫 Positive Rays。
這也是一半的 1D perceptrons ，少的一半是指向另一個方向是圈的。

而問題就是這樣可以切出幾種不同的 dichotomy？ 稍微算一下就可得知有 N + 1 種。

如果是某一區間呢？

可以當作從中取兩個點當作頭跟尾，但尾巴不算進去，所以為了取到最後一個點，最後面再多加個假設的點。也就是 $\binom{N+1}{2}$。

而最後 $+1$ 則是全部都不取的情況。

也可以用等差級數，每次選一個點開始增加區間長度，每次能增加的區間長度都會減少，總共選 N 次: $N + (N-1) + (N-2) + \cdots + 1 = \frac{(N+1)N}{2}$ 最後再加上全部都不選的 1。

以上兩個 $m_{\mathcal{H}}(N)$ 如果能把 Hoeffding 裡的 $M$ 取代掉，都能藉由讓 N 很大時，讓 Hoeffding 式子的 BAD event 發生機率變很小。

Convex 的 hypothesis set

(Convex: 凸)

凸的集合內是圈圈(藍色)，集合外是叉叉(紅)。

而這樣一個 hypothesis set 的 growth function 要怎算呢？

假設所有的點圍成一個圈。
首先要做出某一組 dichotomy ，我們只需要依照其圈圈(+)個數來做多邊形，像是有 3 個圈，就是三角形；4 個則是四邊形。如下圖的是五個。
而不管幾個，我們都可以用 凸多邊形 做出來，也就可以用 Convex Set 做出來，而其 Growth Function $m_{\mathcal{H}}(N) = 2^N$。

如果可以把這 N 個點的所有情形都做出來(成長函數為 $2^N$ )，我們把它稱作做 shattered (打碎、擊毀)。

我們也就知道成長函數不會無限增加，也就證明學習是可行的了。

練習

如同前面所講 1D perceptrons，而這次可以指向正負 ( positive and negative rays )。問 growth function 為何？

先不管全是圈或叉的，朝向某一方的都可以有 $N-1$ 個 threshold ，而因為指向兩邊，所以是 $2(N-1)$。
最後再加上全是圈或叉的，答案是: $2(N-1)+2=2N$

oooo
xxxx

xooo
xxoo
xxxo

oxxx
ooxx
ooox

四 Break Point

繼續 Growth Function

我們一直在討論著 $m_{\mathcal{H}}(N)$ 來取代 $M$ 這件事。這邊用前面提到的四種 Growth Function 來看看會發生什麼。

如果 Growth Function 是 polynomial ，那 BAD EVENT 的機率會變小，因為後面 exp 是 exponential ，整體下降的速度會比較快。如 positive ray 和 positive intervals 。

但如果今天是像 convex sets exponential 上升，就算後面 exp 是 exponential 下降，就不見得會比較好。

那 2D perceptrons 呢？

Break Point

2D perceptrons 是好還不好。

這邊先解釋個名詞: Break Point 。

k 也就是 input 到達某個情況時，將不再是 shattered ，也就是無法處理點的所有組合( $m_{\mathcal{H}}(N) \lt 2^N$ )。此時我們就稱這個 k 是 Break Point。
而自然 k 以後的也都是 break points，但我們感興趣的是第一個。

舉例來說，先前提到的 2D perceptrons ，在 3 個點時，可以做出所有的 dichotomy 。但在 4 個點時就沒辦法了，我們就稱 4 是 Break Point。

幾種 growth function 的 break point:

這邊先做了一個猜測，除了沒 break point 的外，是不是 break point 會發生在 $m_{\mathcal{H}}(N) = O(N^{k-1})$ 的 k 呢？
也就可以進一步推測 2D perceptrons 的成長速度大約是 $O(N^{4-1})$ ，或許就可以說 2D perceptrons 是好的了(因為不是指數成長了)。

練習與總結

$m_{\mathcal{H}}(N) = 2N$ 它的最小 break point 是？

$k=3$ 時，$m_{\mathcal{H}}(k) = 6$ ，但 $2^k = 8$ 。

總結一下第五章:

大致上就是圍繞在如何讓 BAD event 發生的機率變小，所以要用 $m_{\mathcal{H}}(N)$ 取代掉 Hoeffding 裡無限的 $M$ ，其中的轉換，有效的線數和 hypothesis 的種類，接著繼續探討 $m_{\mathcal{H}}(N)$ 究竟是多項式成長或是指數成長，帶出 break point 的觀念。