參考筆記: 林軒田教授機器學習基石 第五講學習筆記

Recap and Preview

learning的兩個核心問題

1. 能不能讓 $E_{out}(g)$ 和 $E_{in}(g)$ 非常接近?
2. 能不能讓 $E_{in}(g)$ 非常小?

最後題目 $2\cdot 100\cdot exp(-2\cdot0.1^2\cdot N) = 0.05$ $N = \frac{ln(0.05/200)}{-0.02} \approx 414.702$

Effective Number of Lines

Effective Number of Lines: 對這n個資料點來說的 分隔線種類

• 一定小於等於 $2^n$
• 可以用來取代 $M$ , 不懂為啥可以取代, 這樣不就只看 in-sample的表現了嗎 => 後面week6似乎會講

Effective Number of Hypothesis

• dichotomy

  一個 Dichotomy 就是一種分類組合，在二元分類裡這樣組合的上界就是 2 的 N 次方，我們可以用這個數字來取代無限大的 M。

為了移除掉對 $X$ 的依賴, 我們要計算 $m_H$(Growth Function) , 即對於這個Hypothesis Set 來說最大的 dichotomy set 的大小, 用來取代 $M$

• $m_H$ (Growth Function)

  以這個 Hypothesis set 能切出最多有多少種的 dichotomy

• those $N$ inputs shattered by $H$

  這個 Hypothesis set 可以找出 $x_1$ 到 $x_n$ 的所有dichitomy, 即 $2^N$ 種

Break Point

• 我們可以用 $m_H(N)$ 來取代 $M$
• 如果這個 Hypothesis Set 的 Growth Function 是 N 的多項式, 則在N很大的時候, $2\cdot m_H(N)\cdot exp(-2\epsilon^2N)$ 會變得很小。反之, 若 Growth Function 是 N 的指數成長, 就無法確保 $E_{in}$ 跟 $E_{out}$ 非常接近。

Break Point

給k筆inputs, 導致 $m_H(k)$ 比 $2^k$ 小, 則k就是 break point, 同樣大於k的也都是break point

由上述我們可以推測 在 break point 為 k 時, $m_H(N) = O(N^{k-1})$