Machine Learning-5 Training versus Testing

Two Central Questions

• Qa: Can we make sure Eout(g) is close enough to Ein(g) ?
  (in: training data, out: testing data, g:hypothesis function)
• Qb: Can we make Ein(g) small enough ?

Trade-off on M (Hypothesis Set)

• Small M
  Qa: Yes, Qb: No (too few choices/ algorithms)
• Large M
  Qa: No, Qb: Yes
• 找到合適的M，且了解為什麼無限的M是否可以學習 （就像前幾章PLA的問題），是接下來討討論的目標。

Review

• 
• 就是把所有BAD events聯集起來。但當今天M太大，upper bound很可能會變成一個無限大的值，而失去意義。

How can we find finite M?

• 
• 其實不難發現很多的bad events是重疊的。 下面舉例：
• 
  （可能會出現線性不可分的狀況）
• 
  （四筆資料的時候，最多只有14種線性可分狀況）
• 
  （從個無限大的M中分群成較少的集合，直覺是可行的）

Terms

• Dichotomy: 二分，把資料二分後的一種集合。
• 
  （Growth Function: 用來描述利用不同的Hypothesis找出最多有幾種可能的Dichotomy）
  m(N): growth function, x: data, H: hypothesis function
• Shattered: 粉碎擊敗的，Growth Function = 2^n 可以表達所有Dichotomy.
• Break Point: 對多可以達到Shattered的資料數量，超過以後就無法Shattered

Conclusion

• 
  如果今天m(N)是指數，那N變大右邊變小的速度會慢非常多。（也就是說，更容易發生bad event），反之如果是polynomial，那右邊就會隨著資料變大而快速減少。
• 

• NEXT: theory-of-generalization

REF

• Training versus Testing @ Machine Learning Foundations