[ 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 : 
 

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

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