學習筆記4，機器學習的可行性
知識點1：有時候機器學習是做不到的。
為什麼呢？請看如下的例子：圖1的3張圖檔的y=-1，圖2的3張圖檔y=+1，請問圖3這張圖檔y=?
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖1
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖2
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖3
如果是從對稱性的角度來說圖3中圖檔的y=+1，如果是從左上角是否是黑色塊的角度來說圖3中圖檔的y=-1。好像Learning是不可行的。
我們想要的事情是在資料以外的部分g能不能和f做的一樣好，但是這個例子好像告訴我們”我們想要的事情是做不到的“，在機器學習中這類研究叫做No Free Lunch（天下沒有白吃的午餐）。如果我們給機器資料，機器去學資料，到底資料以外發生什麼事，通常我們是沒有辦法有任何的結論的（即g在我們所看過的資料以外對f好或者不好）。如果需要有結論，就要加上一些假設。
知識點2：Hoeffding不等式
從圖4的例子中來了解什麼是Hoeffding不等式。
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖4
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 代表瓶子中orange marble占整個瓶子的比例，未知，也不需要知道；
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 代表抽樣的樣本中orange marble占樣本的比例，已知；
公式為
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 ，表示
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 和
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 之間的誤差超過
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 的機率是有上限的。我們可以說如果樣本的數量N越大（則上限越小），那
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 =
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 大概差不多是正确的（probably approximately correct PAC），換句話說就是大概能夠通過已知的
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 來推理出未知的
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 。
知識點3：Probability與Learning的關系
| Bin | Learning |
未知的orange marble的Probability，用 Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 來表示 | fixed hypothesis h(x) =? target f(x) |
marble Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 Bin | x Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 X |
| organe marble | h is wrong Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 h(x) Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 f(x) (有一個固定的h) |
| green marble | h is right Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 h(x)= f(x) (有一個固定的h) |
| 來自于Bin中抽取的Sample，Size用N來表示 | Check h on D={( Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 , Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 )} |
由此可以得到：如果我們的資料量足夠的大（large N），并且
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 是獨立取樣的，我們大概可以說：“從資料中得到的h(
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 )
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 的比例，大概可以推導出h(x)
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 f(x)的比例。”
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖5
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 （out of sample error）表示h和f在整個bin中是否一樣，相當于
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 （未知）；
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 （in sample error）表示在資料上h和y是否一樣，相當于
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 （已知）；将
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 和
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 代入Hoeffding不等式，得到如下公式：
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 ，Hoeffding告訴我們這2個東西（
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 ，
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 ）大概差不多。
如果
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 and
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 很小
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 也很小
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 資料繼續從P中産生出來（就是以P的形式的機率分布），那h
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 f（h和f很接近）。
知識點4：Real Learning
從上述的内容來看，我們根本就沒有使用Machine learning alogrithmn，因為h是固定的，沒有從hypothesis set中選擇，而真正的機器學習需要從hypothesis set中選擇h。
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖六
假設我們有10個bin，從中抽取marble，假使有一個bin抽出的全部是green marble，就是
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 =0，我們是否要選擇這個bin？。對應就是我們有10個hypothesis，其中有1個hypothesis在所對應的資料上全部正确，我們是否要選擇這個hypothesis。
Hoeffding不等式告訴我們的是取樣出來的和bin中的大部分是一樣的，隻有小部分是不好的，所謂不好是取樣出來的和bin中的差的很遠，就是
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 和
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 差的很遠。但是在有了選擇的時候，這些選擇會惡化不好的情形。
注意：資料好和不好，就是指
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 和
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 是不是差了很遠。
圖七針對一個hypothesis表示了Hoeffding不等式。
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖七
圖八出現了多個hypothesis，每一行（每一個hypothesis）告訴我們：“Hoeffding說了，不好的機率很小”，但是我們現在需要的是“演算法需要能安心做選擇”，如果資料是D1，演算法會在
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 ,
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 ,
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 上踩到雷。隻有D1126是好的資料。
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 圖八
我們現在需要知道的是“我們演算法在自由自在做選擇的情況下，發生不好的機率是多少？（就是圖八中？處）”
推導公式如下：
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 我們可以得到結論，在H(hypothesis set) M有限 & 資料的數量N足夠大的情況下，取一個g，他的
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 最小，從某種角度說他的
Machine Learning Foundation Lecture 04 Feasuibility of learning 學習筆記 也是最小的。
