Noise and Error-8 Machine Learning Foundations

Why?

• 延伸之前推論出的VC Dimension，嘗試把適用範圍拓展到不同的問題上。
• 
  雜訊問題：可能答案標錯，可能資料本身有錯，都是雜訊 
• 
  機器學習就像從瓶子裡面拿彈珠，以前彈珠好壞比例固定（deterministic），雜訊存在時彈珠好壞則是隨機的（stochastic）有可能同一個判斷（hypothesis）有時好有時壞，但是依然可以推論VC Dimension是通用的，有雜訊時也是可以學習的。
  
  
• 換一種角度，直覺的思考：
  如果今天好的資料機率0.7，壞的資料0.3（stochastic），那我們可以找出一個mini-target，根據大部分資料的特性來當作學習目標，此時壞的資料就當作雜訊。

Error Measure:

• 
  g: hypothesis function
  f: target function
  先前討論學的好不好是透過評估E-out: g在沒看過得資料發生bad event的數量
  比較常用的是pointwise評估方法
• 
  譬如說分類和逼近兩種的評估方法就不同，並且定義了mini-target f function。
  classification: f = argmax(P(y|x))
  regression: f = E[P(y|x)]

Weighted Classification

• 
  很多時候error會根據不同目標而不同，在選擇學習演算法時，通常我們會選擇一個可行的或者友善的來學習。可行的是指我們對那個data domain的知識人為判斷，友善的是指針對資料特性找出能快速降低錯誤的方法。(err-head: 是我們設計的error measures)
• 
  上圖在討論一個直覺的想法，先前以證明過PLA是可以學習的，但現在學習演算法改變，出現了權重來影響學習，此時可以透過virtual copy來達到reduction效果（把一個問題推論另外一個問題，此時就可以證明在條件下可通用，這是很常看到的方法）
• 另外值得一提的是，weighted classification也可以用來解決data unbalance的問題（譬如說罹患癌症的比例在資料中非常少）

REF

• Noise and Error @ Machine Learning Foundations

The VC Dimension-7 Machine Learning Foundations

Review

• 
• Lecture 6: 總結只要Growth Function出現break point，且N夠大，機器就能有可能學會資料，使的E-out很接近E-in
• Lecture 7: 本節目標是討論VC Dimension
• 
• 統整截至模前的機器學習三步驟：
• 找到一個好的Hypothesis Set （有break point k)
• 資料正確且充足
• 一個好的演算法從訓練資料中找出g function
• （加上一點點運氣）

Terms

• VC Dimension:
• 其實就是k-1（break point - 1），能夠shatter的最大N值（超過N就無法shatter）

Example on 2D PLA

• 
• 左邊紅色部份經過證明，一定會收斂（T:學習夠多次）
• 右邊藍色部份經過證明，E-out接近E-in（N:資料夠多，H:成長函數有upper bound）
• 所以2D PLA可行！！！！！一定可以學習成功（E-out接近E-in接近0）

How about Multi-Dimensions

• D-vc == D(Dimensions) + 1
• eg: 
• 1D PLA: D-vc = 2
• 2D PLA: D-vc = 3
• proof:
• D-vc >= D + 1
  也就是說只要找到一組可以shatter D+1維度即證明
• D-vc <= D + 1
  也就是說必須證明所有D+2維度都不能被Shatter

D-vc 物理意義

• 
• D-vc (VC Dimension): 直覺的想法其實就是DOF（Degree of Freedom），可以操控的維度數量。回顧之前的課程，機器學習不外乎要作兩件事：
• 確保E-in和E-out差不多（可套用學習結果到沒看過得資料上）
• 確保E-in夠小（成功從training data學習）
• 於是D-vc也和之前Hypothesis Set數量M有相當的狀況：
• 太大：學習能力強但是可能會失去一般性
• 太小：學習能力弱但是可容易保有一般性

D-vc 哲學意義

• 透過一些簡單的換算，可以把原本的Hoffding改寫成E-out的upper bound關係式。

• 根據上面的公式，可以推論出一個核心的哲學：

• 下圖舉例，如何根據老闆的需求，概略算出需要的資料量。

• 但實務上需要的資料量和評估出來的資料量會有非常大的落差，通常只需要10倍於VC-Dimension的資料量就很足夠了。

• 實務和理論評估出來的資料量需求會有落差，主要是在推導的過程皆採worse case，找到的upper bound是好幾種upper bound的upper bound...

• 簡言之推出的公式，其實沒什麼實務上的用途，但卻可以大大的了解運作的哲學，提供我們後續機器學習的參考。

• 小複習：
• 定義VC Dimension (其實就是DOF）
• D-vc背後的衍生意義

• NEXT: noise-and-error

REF

• The VC Dimension @ Machine Learning Foundations

Theory of Generalization-6 Machine Learning Foundations

Review

• 
• break point: minimum data could be shattered
• shattered: could represent all dichotomies
• dichotomies: number of set could bi-separate the data
• m(N): growth function, represent maximum of dichotomies given N

Term

• Bounding Function B(N, k): N個點中，任k個不能shattered
  combinatorial quantity:
  Maximum number of length N vectors with (o,x), while no shatter in any length k subvectors
  

Bounding Function: The Theorem

• 
  從B(4, 3)舉例來看，可以發現分成兩組，（橘色）成對，（紫色）單支
  （α部份）
  可以直覺的判斷α中(略去x4不看)必須滿足小於B(3,2)的性質。（x1, x2, x3任2個不能被shattered，否則必無法滿足B(3, 3) ）
  （α + β部份）
  可以直覺的判斷α + β中，必須滿足小於B(3,3)的性質。（x1, x2, x3任3個不能被shattered，否則必無法滿足B(4, 3) ） 
• 下圖舉三個例子：
  
  於是我們找到了一個generalization of upper bound formula，最高的數值大小也不會超過N^(k-1)，和原本的 2^N 相比減少非常多！ 

VC Bound:

• 目前已知mH(N)成長函數，但還是無法估計出upper bound。已知E-in是有限的，但是E-out卻是無限的，於是想辦法把E-out轉換成有限，於是推導出VC Bound。
• 
  H: Hypothesis Set (可能描述資料的所有函數）
• 三步驟概略推導VC由來
• 
  replace E-out by E-in'
  E-in'是D'(validation set)的評估，找有限的資料來作評估依據。這邊因為某些數學的理由，把限制變得更加嚴格 ε -> ε/2。
• decompose H by kind
  透過成長函數mH(N)來算出總共會有幾種Dichotomies -> mH(2N)
• use Hoeffding without replacement
  smaller bin, smaller ε
• 
• 舉例2D perceptrons:
• break point = 4
• mH(N) < N^(k-1) = N^3
• 證明了只要N足夠，是可以學習的

• NEXT: the-vc-dimension

REF

• Theory of Generalization @ Machine Learning Foundations

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

Machine Learning- HW1

HW1-15

• Very simple implementation of PLA algorithm. Really worth to try by anyone interesting to Machine Leaning.
• Though the input x has only 4 features in this problem, we need to add one more feature as bias during learning, meaning that the weight vector should be 5 dimensions too.
• hw1-16, hw1-17 : 調參數實驗

HW1-18

• 如果資料確定是線性可分，使用vanilla PLA，反之使用pocket PLA但會慢很多。
• pocket PLA：weight更新發法同vanilla PLA，但會有一個最佳的res_weight對整個training dataset的 error rate最低，所以每次更新完weight都要檢查現在的是否比之前保存的更好，這時候必須遍歷全部data統計錯誤率，也就是比較慢的原因。
• hw1-19, hw1-20 : 調參數實驗

Ref:

• My Github Implementation of Course Assignment
• NTU Machine Learning Foundations (Coursera)

Sampling Methods

Why Sampling?

• Approximate Expectation
• estimate statistics
• poster inference
• Visualization

Pros and Cons

• Pros
• Easy
• Could figure out very complicated model
• Cons
• Too easy - used inappropriately
• Slow
• insufficient to get "good" samples (which could represent well to the whole data set)
• difficult to assess (you hard to know your approximation is good or not)

Monte Carlo Approximation [History]

• Credits: Con Nevmann, Fermi, Ulam
• Ulam's gambling uncle likes to go to Monte Carlo Casino in Monaco

• The intuition is try to evaluate the expectation of intractable event.
• 直接的作法莫過於把所有的資料取平均（獲取一個unbias的期望值)，但實務上卻往往不可能這樣作的。
• 核心：sample的資料越多，估計出來的期望值就會越接近真實期望值。

Example

• 如何知道黑色點在上圖的分佈期望值？ （Mandelbrot）
• m(A)/m(S) = p(X->A) = EI(X->A)
  A表示在上圖中的黑色點點集合，S表示在上途中的全部點點集合，X表示黑色點點出現的隨機變數，相當於I(indicator)該點是黑色為1否為0的期望值。
  m^(A) = R*1/n sum(I(X->A))
  假設今天上圖範圍面積有R個點點，隨機採樣n個點點，可以來估計分佈～！

Importance Sampling

• 有沒有可能利用不同的Distribution q來作Samping，更好的還原目標的Distribution p？
• YES!!!

• 可以寫成期望值PDF，會發現可以用不同的採樣方式表達同一個分佈期望值
  （原本是從p(x)採樣估計E[f(x)]，現在則是從q(x)來採樣估計E[f(x)*p/q]）
• importance weight = p/q
• 理論上可以找出最佳的q，但現實問題中常常很難作到。如果找的好可以大幅降低variance~! 
• 兩種狀況：
• 如果今天不知道p，會盡可能找出一個最接近p的q
• 已知p，但是想用更好的q來降低 Monte Carlo Approx's Variance 。

• （左圖）找到不好的q
• （右圖）找到較好的q

Ref:

• Sampling methods

Machine Learning-4 Feasibility of Learning

TOPIC

• 機器學習有可能媽？

No Free Lunch

• Training Data訓練出來的Hypothesis g並無法準確地表達沒看過的Testing Data資料

Inference

• Statistics: Sampling（採樣）
  
  抽樣樣本數N越大，樣本的機率 v 和 真實的機率 u 誤差越小。

• 推論：找出一個差不多正確的機率分佈
• 想法：透過Hoeffding's Inequality公式中發現，真實的機率u 並不影響 樣本的機率v 是否多接近 u，換句話說我們是不需要事前知道答案的（知道也就不用算了），可以無限接近的推論出答案。（PAC -> Probably Approximately Correct）
• Verification: 即使在Training Data中 模型v 已經非常接近 真實u 了，還是無法確定 v 是否可以準確運作在真實資料u中，可以透過這個公式來驗證，P(|v-u|>0.001)<=0, N-> infinite。

Data

• E-in: 
• Evaluation on training data
• E-out: 
• Evaluation on un-seen data
• Good Data: 
• E-in 很接近 E-out
• Bad Data: 
• E-in 和 E-out 很不同，容易造成從Hypothesis set照出錯誤的 g。
• Hoeffding's Inequality: 
• 評估抓出一個Bad Data的機率

Hypothesis set

• 定義：一個集合，包含各種可能的g，可以表達X->Y之間的關係。
• 課程中利用了Hoeffding's Inequality證明了如果Hypothesis set集合在"有限"數目，且資料量夠大的條件下，可以透過機器學習找出一個最好的g。
  
  (評估找到一個Bad Data的機率 ＝ 該資料對M個h是否為Bad Data的聯集)

Conclusion

• 
• 如果資料分佈是有統計模型特性的，且有限可能的Hypothesis -> 可以學習的

REF

Feasibility of Learning @ Machine Learning Foundations

Machine Learning-3 Types of Learning

TOPIC

• 除了是非題（二元分類），機器學習還有哪些種類。

Learning Target

• Multi-class Classification Learning
• Regression Learning: output as real number
• Structure Learning: output as structure (huge classes without explicit class definition)
  (舉例像是語音辨識，語音之間就含有隱藏不明顯的關係，是一種structure)
• ...

Learning Type

• Supervised Learning 監督式: all y
  - 全部資料都有標記。
  eg: classification(分類), ...
• Unsupervised Learning 非監督式: no y
  - 沒有資料有標記。
  eg: clustering(分群), density estimation, outlier detection, ...
  (目標較分散，較難衡量好壞)
• Semi-Supervised Learning 半監督式: some y
  - 小部分資料有標記。(可以省下很多標記成本)
• Reinforcement Learning 強化學習:
  - 透過 reward/ punishment來訓練機器: implicit y
  (learn with implicit information, 通常是一個序列/過程)

Learning Method

• Batch Learning
  - 一組資料一次學習完 (常見作法)
  (duck feeding)
• Online Learning
  - 一筆一筆新資料修正的學習
  (passive sequential)
  eg: email filter, reinforcement learning
• Active Learning
  - 標記成本很高的狀況下，希望透過機器主動問問題，減少資料的需求量。
  (question asking)
  eg: "選擇性的"找出驗證老鼠癌症最好的實驗方法。

Features

• Concrete Features
  含有人類智慧預先處理過得輸入資料，對於機器來說是較容易學習。舉例如下：
• 錢幣分類（大小、質量）
• 信用卡評估（客戶資訊）
• Raw Features
  含有最原始的物理意義輸入資料，對於機器來說較難學習。
• 所以獲取好的Concrete Feature是非常重要的議題
• 透過深度學習
• 透過專家設計
• Abstract Features
  沒有物理相關意義的輸入資料，抽象的輸入對於機器來說非常難學習。舉例如下：
• 評分預測（使用者id, 項目id, 分數）
• 以上三種常常會一起出現舉例如下：
• 推薦廣告系統
• Concrete→使用者資料
• Raw→推薦的圖像廣告
• Abstract→使用者編號，廣告編號

REF

Types of Learning :: Learning with Different Output Space @ Machine Learning Foundations

Machine Learning-2 Learning to Answer Yes/No

Perceptrons Learning Algorithm (PLA)

• 就是一種 linear (binary) classifiers （二分學習演算法）

How

• IDEAS: 我們無法一開始就知道正確的hypothesis function g，於是就先找一個g0當作起點，過程不斷透過犯錯的資料來調整，直到錯誤減少到一定程度。
  （A fault confessed is half redressed - 知錯能改善莫大焉）

一定會收斂媽

假設是線性可分的狀況下，確實會收斂

證明：

• 但現實問題中，即使是線性的，資料中也會有雜訊(noise)導致問題變成非線性。可用Pocket PLA來嘗試解決（把最好的留在pocket，但會比PLA慢，因為多了比較的動作）

REF

Learning to Answer Yes/No :: Perceptron Hypothesis Set @ Machine Learning Foundations

Machine Learning-1: The Learning Problem

When can machine learn:

• 有資料
• 沒有明確定義的函式 (有的話就直接寫死更快不用學習了）
• 有可能的pattern （存在潛在的規則）

A takes D and H to get g

Target to learn from ML:

• target function f: 未知，理想的data→label函式
  (如果已知，就不用機器學習了）
• hypothesis function g: 機器學習目標，"盡可能"接近f

Terms:

• Data Mining vs Machine Learning
• DM: 尋找大量資料彼此之間的關係，供給人類參考依據。
• ML: 尋找Hypothesis Function模擬預測資料和答案皆的關係。
• 兩者其實密不可分，但傳統的DM還會研究如何有效的計算管理大量資料庫。
• Artificial Intelligence vs Machine Learning
• ML是實現AI的一種方式
• Statistics vs Machine Learning
• S是實現ML的一種方式
• 傳統的S比較注重在數學公式的推導，但對實際計算方式探討較少。

REF:

Machine Learning Foundations by Hsuan-Tien Lin