Machine Learning 共筆 Week 5
Training versus Testing
Published in
4 min readApr 29, 2018
Recap and Preview
前四周的課程我們已經有了一些基本知識跟假設，有一個在使用機器學期的前提假設是： Machine Learning的Hypothesis與Data的分布相似，當Hypothesis不會太多且N夠大時，我們就可以放心的挑選E_in
以下是前四周的簡短回顧
- Week1: 希望能夠找到一個g來趨近於f
- Week2: 找到一個真的能夠趨近於0的E_in(g)
- Week3: 用了Batch & Supervised 的分類方式來學習
- Week4: 確實證明了E_in與E_out是足夠接近的
而上方的四周lecture也將Learning主要拆成以下兩個問題：
- E_out跟E_in是有關聯的
- E_in(g)是否足夠小
但Hypothesis Set(M)的數量會影響學習的成效，也造成了上方兩個主要問題的權衡：
- M小的時候，E_out與E_in是接近的，但不一定能夠找到一個讓E_in足夠小的g
- M大的時候，兩個問題剛好就會是相反的結果。
找到一個有限的小m，且能夠順利的取代大M，達成Machine Learning的可行性。Effective Number of Lines
Week4的時候提到了bad data的union bound是考慮所有機率的相加，這在m無限大時將會大於1而失效，因此這個bound實際上是高估的，因為實際上兩個hypothesis之間的差異並沒有那麼大，使得他們的union bound是需要用相加的；而我們也希望能夠找到某些hypothesis是相似的，歸在同一類降低bad event的機率。
PLA原本可以分類的線是無線多條，但當看到一個資料點的時候，線其實就只剩下兩種，兩個資料點四種，三個資料點≤8種，四個資料點≤14種 → Effective Number of Lines
Effective Number of Hypotheses
- Dichotomy(二分)：一個Hypothesis只對N個特定的點，可以做出多少個二分的Hypothesis的組合，最多就只有2的N次方種
- 因為Dichotomy set會因為取的N個x所影響，因此這邊就直接先取”最大的”，意思是說取的某種N個x的組合會讓Dichotomy set最大 → m_H
- Growth Function for Positive Rays: Dichotomy只有N+1種
- Growth Function for Positive Intervals: Dichotomy同時還是會遠小於2^N
- Growth Function for Convex Sets: Dichotomy set 為 2^N
Break Point
不過最終，我們仍是希望growth function的結果可以是多項式(polynomial)而非指數次的。
- 這邊出現了一個Break Point的定義，第一個可以找到hypothesis數量比2^k小的資料點k，則k+1, k+2, k+3都會無法得到2^k種hypothesis
