[ LFD Note ] Lecture 02 - Is Learning Feasible?

來源自 這裡 
Preface : 
考慮我們手上有一個 容器 裡面有 red/green 彈珠, 而從裡面任意挑出一個彈珠是 red 的機率是 μ : 
 
(圖截自 Caltech LFD online video) 

也就是說我們可以知道下面公式 : 

P[picking a red marble] = μ
P[picking a green marble] = (1-μ)

但問題是 μ 是未知! 因此我們希望透過 ML 找出 Hypothesis 來求出 μ. 考慮我們從容器挑出 N 個彈珠 independently, 則抽出的彈珠是 red 的數目除於 N 並得到 ν. 那麼我們可以說 ν = μ 嗎? 
- No! 

我們有可能從一個幾乎都是 red 的容器抽出都是 green 的結果! (Possible)

- Yes (In the long run) 

如果我們抽的樣本數 N 夠大時, 相信ν ~= μ. (Probable)

Hoeffding's inequality : 
那麼我們怎麼知道 ν ~= μ? 有個不等式告訴我們 : 

In a big sample (large N), ν is probably close to μ (within ε)

而這個不等式就是有名的 "Hoeffding's inequality" : 
 

從這個不等式我們可以知道 ν ~= μ 是 P.A.C (Probability Approximate Correct) 當不等式滿足, 並從不等式可以知道 : 

* Valid for all N and ε
* Bound does not depend on μ -> 這是好消息, 因為 μ 未知!
* 考慮如果我們在同樣的 Bound 時, 在右邊等式的 (ε^2)N 相等下, 如果你希望有較小的誤差 ε, 付出的代價就是要更多的樣本 N!
* 如果 ν ~= μ 可以說 μ ~= ν
* 當 N 等於 0, 右邊式子大於一, 因為你都沒有看到 sample, 自然 P[|ν - μ| > ε] 會很容易發生!
* 當 N 趨近 ∞, 則右邊式子趨近於 0, 可以想像因為 N 無窮大所以你求得的 ν 實際上就是 μ, 自然 |ν - μ| 會趨近於 0. 

Connection to learning : 
說道現在都只是在說 ν 跟 μ 是否相似的 verification. 那我們怎麼應用到 ML 呢? 我們可以做一下 Mapping : 
Bin(容器) : There is a unknown μ to learn. 
Learning : The unknown is a function f: X->Y 
Marble(彈珠) : 每個彈珠都是一個 training instance x ∈ X (Bin) 

那我們的 Hypothesis 可以這麼定義 : 
If x is green: Out Hypothesis got it right. h(x) = f(x) 
If x is red : Our Hypothesis got it wrong. h(x) != f(x) 
 

接著回來我們一開始的 Learning diagram : 
 

我們發現剛剛定義的 Hypothesis h 是 fixed (always guess green!), 因在過程中並沒有所謂的 learning 發生! 因此我們可以需要有多個 h (h1, h2, ... hm) 並找出哪個 h 有最佳的結果, 於是 : 
 

接著我們希望代回原先的 Hoeffding's inequality 來知道是否這樣的 Learning 是 feasible, 在這之前先做一些符號的標記. 我們知道 μ 與 ν 的差別在於一個是母體, 一個是樣本數, 並且不同的 bin 會有不同的 h : 
 
 

或是可以這樣理解 : 
 

當這兩個值(概念接近於統計的期望值)相近時, 我們知道 in 跟 out 的 distribution 分佈相近, 故計算出來的 h 可以說是 feasible, 因為就算是沒出現過在 training sample 的 data (out of sample), 也可以有不錯的 prediction. 

代回原先的不等式得到 : 
 

看起來好像所有事情都完滿結束, 但不幸的是 "Hoeffding's inequality doesn't apply to multiple bins"! 但其實我也不是很懂為什麼><" 但在 video 教授有給一些提示: 
Q1. 考慮我們丟一個 fair coin 十次, 可以得到 10 個 head 的機率為何? 

ANS. 1/(2^10) -> 約等於 0.1%

Q2. 如果你一次丟 1000 個 fair coin 十次, 可以得到 10 個 head 的機率為何? 

ANS, 考慮排列組合 1000 個中有 10 個為 head...約 63%

雖然一樣是求得 10 個 head 的機率, 但是因為進行實驗的流程與步驟不同, 結果自然會不如預期! 因此原先的不等式需要做些修改, 因為一次的 sampling 我們提供了 M 個 h 個 Hypothesis (M 個銅板)來求最佳的 h : 
 

因此我們可以如下推導不等式 : 
 

最終得到了下面的不等式 : 

[ LFD Note ] Lecture 01 - The Learning Problem

Source from here 
Outline of the Course : 
課程有三大類 theory (mathematical), technical (practical) and analysis (conceptual). 章節如下 : 

1. The Learning Problem (link)
2. Is Learning Feasible? (link)
3. The Linear Model 一 (link)
4. Error and Noise (link)
5. Training versus Testing (link)
6. Theory of Generalization (link)
7. The VC Dimension (link)
8. Bias-Variance Tradeoff (link)
9. The Linear Model 二 (link)
10. Neural Networks (link)
11. Overfitting (link)
12. Regularization (link)
13. Validation (link)
14. Support Vector Machines (link)
15. Kernel Methods (link)
16. Radial Basic Functions (link)
17. Three Learning Principles (link)
18. Epilogue (link)

The essence of machine learning : 
要進行 machine learning 必須滿足的幾個要件 : 

* A pattern exist : 你不會期望從亂數產生的資料去學到什麼東西吧, 預期在 data 應該存在某個 pattern 可以被 learning.
* We cannot pin it down mathematically : 如果可以, 那還需要 machine learning 嗎?
* We have data on it : 巧婦難為無米之炊 ><"

Components of learning : 
Machine learning 可以拆解成以下幾個元件的組合 (Formalization) : 

* Input: X (Customer application) 以課程的例子就是那些信用卡用戶身上抽出來的 features. (age, salary etc)
* Output: Y (good/bad customer?) 希望 ML 可以告訴我們的結果.
* Target function: f: X->Y 也就是 ML 學出來的模型, 透過輸入 X; 我們可以推論 Y.
* Data: (x1,y1),(x2,y2),...(xn, yn) 一個 Supervised learning 的一筆紀錄包括 features 與對應該 features 的結果.
* Hypothesis: g: X->Y 這個跟你選用的 ML Algorithm 有關, 每個 ML Algorithm 有自己的 Hypothesis 來告訴我們如何推論結果.

示意圖如下 : 
 
A simple hypothesis set - The 'perceptron' : 
這邊教授舉了一個最簡單的 ML Algorithm 'perceptron' 來講解 Hypothesis set. 而他的定義相當簡潔 : 
 
(截自 wiki) 

簡單來說, 他為每個 feature 定義一個 weighting, 而形成一個 weighting vector, 將 feature vector 與 該 weighting vector 相乘後得到的值如果大於零就是 class1, 反之為 class0. 而在使用這個演算法前有個重要的前提, 就是 data 必須要能夠 linearly separable! 

簡單來說就是希望找出下列公式中粉紅色的 weighting vector, 將平面中的 '+' 與 '-' 能夠分隔開來進而達到分類的用意, 但遺憾的是現實世界的 data 多半不是 linearly separable : 
 

Basic premise of learning : 

"using a set of observations to uncover an underlying process"

如果 mapping 到 ML, observations -> data ; underlying process -> hypothesis (or the learned model). 另外這邊也將 ML 進行簡單分類 : 

- Supervised Learning : 分類器, 根據給定 features 來對 input 進行分類.
- Unsupervised learning : 分群器, 將 features 相近的 input 進行 grouping.
- Reinforcement learning : concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward. 常用在 gambling 的應用.

Q & A : 
在課程最後, 教授還有 Q&A. 有幾個問題還蠻有深度的. 千萬別錯過 ^^. 如 "Data set" 的 size 要多少才能夠讓 ML 訓練出來較正確的 Model? 越多越好? 多半實務上 "Data set" 的 size 不是我們可以決定的 ^^". 

Supplement : 
* Machine Learning course - recorded at a live broadcast from Caltech