HOEFFDING 不等式 筆記
Intro.
現在想像我們有一個裡面有很多橘色和綠色彈珠的罐子，無法知道橘色彈珠的真實比例，但可以用抽樣方法去推估出橘色彈珠出現的機率。
Chapter1. HOEFFDING 不等式
由 Hoeffding's Inequality 這個定理，可以證明說抽樣出來的比率有多少多少的可能性接近於原本的比例。
當 N 很大（取樣的數字），那 v - u 就會是一個很小的數字，也就是預估的 g 跟真實的 f 的差距很小。而當 ε 很大(容忍的誤差很大)，那就可以很容易地說 g 跟真實的 f 的差距很小。只要符合了這個不等式，那就叫做 probably approximately correct（PAC）。
但通常無法容忍誤差很大，所以會取 N 很大來推估 g 是否接近 f 的真實情況。
Chapter2. HOEFFDING 不等式 與 ML結合
Ein 代表在已知取樣的中 h(x) 跟 f(x) 的誤差，Eout 代表其他未知的資料中 h(x) 跟 f(x) 的誤差，這在 Hoeffding 不等式的定理下，我們知道 N 很大時，Ein 與 Eout 的誤差很接近，所以我們可以說 Ein 與 Eout 是 PAC。
這常常會被機器學習用在驗證得出來的 h(x) 好不好，只要 N 夠大，取樣的分佈一致，是可以很明確地用部分已知資料來推估假設在其他未知資料表現得好不好。
Chapter3. 多重假設
如果是有限個 h，如 M 個 h，一樣可以用取樣的資料來說明 h(x) 是否跟 f(x) 接近。
如果 H 這個集合只有 M 個，然後取樣的 N 夠大，利用 A 取出 g，如果 Ein(g) 接近 0，那麼 g 就是一個 PAC 的答案了
Chapter4. Training vs Testing
機器學習有兩個核心問題。
希望後來測試學習的結果，會跟訓練時得到的結果很接近，這樣我們才能說機器有學習到技能。（Eout 跟 Ein 是很接近的）
另一個就是希望 Ein 很小，也就是訓練的過程中，希望誤差很小。
而在Ch3裡面的M值，在這裡會發生兩難情況。
如果假設集合 M 很小，可以保證 Eout 可以接近 Ein。但是因為假設集合小，可以挑選的選擇就少，也因此 Ein 可能會是一個不小的值，也就是誤差會大。 如果假設集合 M 很大，會得到一個比較好的 Ein，也就是誤差比較小，但是 M 太大就無法保證 Eout 會跟 Ein 接近（無法保證學習的結果）。
從Hoffding證明中，可以得知 M 是從當較大的誤差發生的情況累積出來的，所以假設集合越大，那累積出來的就一個越大的數字，如果是無限集合，那就沒有上限。
但大誤差的上限值很有可能是高估的，因為許多種大誤差發生的情況都可能是很相似的情況，所以大誤差發生的情況有很大一部份是重疊的。
所以如果把無限的假設集合依照它們的類型來分類嗎，這樣就可以轉換成一個有限的集合。
Chapter5. DICHOTOMIES
在二元分類上的問題，一個超平面上可能會有無限多的線。而分類的過程就是將原本無限多的線，轉換成分種類的線 Dichotomies，一個 Dichotomy 就是一種分類組合，在二元分類裡這樣組合的上界就是 2 的 N 次方，可以用這個數字來取代無限大的 M。
而只要證明成長函數是不會無限增加的時候，那就代表機器學習是可行的。
Chapter5. Break Point
Break Point 指的是，當下一個輸入出現時，Dichotomies 組合不再是指數型成長的的那個點，在 2D perceptrons 這邊從我們剛剛的例子可以知道 break point 出現在 4 個輸入時。 成長函數至少會小於 2 的 N 次方，且如果 break point 在k取到了，那 k+1, k+2,... 都會是 break point。 如果 H 有Break Point k，那當 N 大於 k 時，mH(N) 成長函數會快速縮減（以 binary classification 這個問題來說，所有的 H 為 2 的 N 次方個）。
Chapter 6. Bounding Function
Bounding Function 的意義：
為了看在 N 個樣本點的情況下，如果 Break Point 為 K，那 mH(N) 會縮減到什麼程度的一個函式。
Bounding Function B(N, K) 只與 N 和 K 有關，與假設集合 H 無關。
這樣在 Binary Classification 這個問題下，無論是 positive intervals 還是 1D perceptrons 他們的 Bounding Function 就都會是一樣的，如果能得到 Bounding Function 的結果，就可以推廣到各個 Binary Classification 的問題。
Bounding Function --> B(N, k) <= B(N-1, k)+B(N-1, k-1)
只要 Break Point 存在，那 mH(N) 成長函數一定能夠被一個多項式包含住。
Chapter 7. BOUND FUNCTION 引入 HOEFFDING 不等式
當知道 mH(N) 成長函數 是可以在某種條件下（Break Point k）被 Bound 住。再回到 Hoeffding 不等式的 union bound 形式，把 Bound Function 的定理概念引入這個 Hoeffding 不等式可以慢慢推導出投影片中下面的式子。
Chapter 8. VAPNIK-CHERVONENKIS（VC）BOUND
將 VC Bond 簡化的成長函數 N 的 k-1 次方帶進霍夫丁不等式裡，式子可以簡化成下圖。這個式子告訴我們：
1. 當成長函數有 break point k，也就是說假設集合很好
2. N 的資料量夠大，也就是說有足夠的好資料集
3. 如果有一個演算法可以找出一個 g 讓 Ein 很小，也就是說有好的演算法，那麼大概就可以說讓機器可以學到技巧了。
VC Dimension就是最大的非 break point 的維度 。所以 d＿vc 就是 k-1。
Chapter 9. 模型複雜度
將霍夫丁不等式做一些轉換，將右式表示成 δ（壞事情發生的機率），那 1-δ 就代表是好事情發生的機率，就就是 Ein(g) - Eout(g) <= ε，我們可以知道 d＿vc 會影響壞事情（Ein 與 Eout 差距大）發生的機率，d＿vc 越高，就代表假設集合模型複雜度越高，但也可能讓壞事情發生的機率變高。
