笨蛋，問題在DATA 3: Probably Approximately Correct (PAC)
此篇文章在記錄我看PAC相關資料的筆記
1. Probably Approximately Correct — a Formal Theory of Learning
2. Machine Learning 2021 Spring-HUNG-YI LEE (李宏毅): Theory of ML (Prof. Pei-Yuan Wu)
在Prof. Pei-Yuan Wu的投影片中，吳老師用了一個很簡易的對話作為開題，我這邊重新將圖片的內容打出來，
大家在看這個對話會發現，對話會圍繞著我們前幾篇資料相關的文章，
裡面都有提到一點「我們需要多少訓練資料來訓練模型」
之前我的回答都是無法知道，但在PAC上，PAC給了可依據「理論假設下預期錯誤率為多少%下，推論出來的樣本數需要多少」。
PAC裡面有一些字眼，一般機器學習介紹比較少看到，我盡量用白話的方式來講述。
Supervised learning的一般程序:
在統計或是機器學習演算法，大家都知道會有訓練資料(training set)和測試資料(test set)，在
1. Training過程中: 在給定的訓練資料(training set)，利用任一個學習演算法(Learning algorithm)訓練出一個Hypothesis。
2. Test 過程: 利用訓練好的Hypothesis來評估測試資料(Test data)。
Test的結果將用來評估我們訓練的Hypothesis是「好」還是「不好」。
問題是: 測試資料的結果真的能表示所有的case嗎? 我們有辦法肯定地確認這個「訓練出的Hypothesis」的穩健性(魯棒性robustness)嗎?
答案是: 我們必須測試過世界上所有的資料才能回答上面的問題，但是實際上是不可行的。
在1984年的時候，Leslie Valiant提出Computational Learning Theory (PAC learning)利用機率的方式來評估確定性和正確性(degree of certainty and correctness) 。
Note: Hypothesis 可以想像成你找一組訓練資料搭配一個演算法，訓練出來的結果就是一個Hypothesis；如果換一組訓練資料搭配同一個演算法就是另一個Hypothesis。
Probability to measure degree of certainty and correctness
下圖為一個範例，假設我們要利用體脂肪率來區隔男女生，我們收集一些訓練資料並假設訓練資料和測試資料來自同一種分布，根據男和女生的體脂肪率資料分別建立出分布圖，
學習演算法在分類上的目標就是希望訓練好的Hypothesis的機率可以逼近One-hot encode的結果，如下圖。
我們可以發現我們幾乎不太可能正確學習到實際的目標，比如mix-area的部分，或是體脂肪很高的男生和很瘦的女生，如果用這個Hypothesis，此類型的例子就會容易判錯，為什麼?
Note:我們先屏除用來分類的特徵是否有選得很好這個問題。
因為 (一般女性因生理關係體脂肪都比較高)
1. 演算法是從「抽樣(sampling)」的「訓練資料」來學習，這些資料可能為特定類別的Hypothesis。
比如抽到的男生都很胖，女生都很瘦，這樣就可能造成Hypothesis有偏誤。
2. 一個有效的演算法很有可能會學習到隱藏目標概念(hidden target concept)的Hypothesis。
(這段話我覺得超難解釋，後面的例子可以說明出什麼是 hidden target concept。但可以想像下圖的實際的資料分布就是hidden target concept，但因為實際上這個分布是未知，是我想像出來的，所以需要透過抽樣來估計)
出現抽樣(sampling)的字眼就會衍生出
- 少量的資料資料比較有可能會學習出錯誤的Hypothesis。(下圖中)
- 大量的訓練資料通常比較能學習出較一致的Hypothesis。(下圖右)
由此上圖可知，資料越多理論上建立的樣本分布會近似母體(當然不考慮人工抽樣造成的偏誤)。
這段滿廢話的，實務上還是衍生出怎麼抽(選)資料才會很隨機，才夠滿足母體，達到小而廣的數據(這部分技術可以follow吳恩達Andrew Ng這幾年主推的 The Data-Centric AI)，這部分我覺得還滿難的，但還好這幾年學術和工業界都還有在研發一些深度主動學習(deep active learning)技術可以幫助在已經有一些資料的狀態下，後續如果繼續收集資料怎麼收到(抽到)有用的資料，避免收到太多無用資料。
Learning Intervals一個簡單的猜數字遊戲
文獻1(Probably Approximately Correct — a Formal Theory of Learning)舉了一個範例Learning Intervals一個簡單的猜數字遊戲。
當 a≤x≤b，A則回答這個數字正確判斷(1)，不然就是錯誤(0)，這程序就是標註(label/target)。每回答一次就產生一組sample (x, label )。
A產生了n筆資料給B，讓B去猜答案。
假設B的猜測方式為:
a’為判為0的最大值和判為1最小值的平均數。
b’為判為0的最小值和判為1最大值的平均數。
第一次: A第一次產生10筆資料，B可以根據這10筆資料去猜，錯誤率為ε1
第二次: A延續第一次結果再產生5筆資料(總共15筆)，B可以根據這15筆資料去猜，錯誤率為 ε2。
第三次: A延續第二次結果再產生5筆資料(總共20筆)，B可以根據這20筆資料去猜，錯誤率為 ε3。
…
第十次: A延續第九次結果再產生5筆資料(總共40筆)，B可以根據這40筆資料去猜，錯誤率為ε4 。
我們可以發現 A產生出來的資料越多，B越能猜到A在腦中想的範圍，錯誤會越來越低，學習到後面，如果B總是贏比賽(越學越好)，我們就會稱這個問題為PAC-Learnable。
大家小時候如果有玩就「幾A幾B」的遊戲概念是一樣的。
從這個例子我們將Probably Approximately Correct Learning的字拆開看:
Approximately correct: 代表sample估計的interval(B猜的答案)跟真實的interval (A的答案) 非常接近，所以新的樣本發生錯誤判斷的可能性很低。
Probably : 如果一次又一次玩這個遊戲，我們依舊可以得到很好的近似結果。
PAC-Learnable : 所以我們有很高的機率可以找到非常近似答案的interval。
簡單說就是資料越多，我們越能找到近似實際答案的答案(Approximately correct)，而且不管重複幾次實驗都可以得到很好的近似實際答案的答案(Probably)。
Distributions and Hypotheses
X : 資料集(有限/無限，並沒有限制)，根據固定但未知的分布(D)，隨機生成資料(樣本xi)，每個樣本都是獨立且同分布(iid)
A 利用某種的方式隨機(D)產生一個數字
- A挑選一函數(c)(此範例為a≤x≤b )去判斷這個x屬於什麼(正確(1)、錯誤(0)) →這個程序稱為concept or target。
- B的目標: 利用資料集(X)學習出一個函數(h)去滿足A的函數(c)。
B所學習出的函數稱為hypothesis(h)。(a’ 和 b’為B找出來的答案)
「B利用A從分布D生成的X來進行演算法學習出來的hypothesis」和「A挑選一函數(c)(concept)」，我們計算他們之間差異度並量化為機率，
PAC-learnable
假設給定一組獨立且同分佈(分布D和concept(c))的樣本下，透過一個演算法A進行學習得到的hypothesis，有很高可能性這個hypothesis判斷錯誤率很低，那這個問題就是PAC-learnable。
我自己覺得上面那段話很難懂，但他只是在定義什麼是PAC-learnable。
我們想看看上面的例子，A利用隨機分佈D產生一個數字 ，A挑選一函數(c)
函數(c)是我們給定的“[a,b]範圍”來判斷生成函數，我們可以發現在給定隨機分佈D和函數(c)下，B透過猜測的方式(見範例)，B越能猜到A在腦中想的範圍，錯誤會越來越低，學習到後面，如果B總是贏比賽(越學越好)，所以Learning Intervals是 PAC-Learnable。
但函數(c)一般是隨機的(範例是我們給定“[a,b]範圍”來判斷生成函數)。
你可以想像我們看著一張人的圖我們要判斷男生還是女生，這時候函數(c)為「眼睛看到圖經由大腦運作得到的判斷結果」，這樣的過程你有辦法利用一函數理解大腦怎麼運作的嗎?
而B就是要找一個演算法能學習(模仿)「眼睛看到圖經由大腦運作得到的判斷結果」(得到的結果稱為hypothesis)，所以預期B要能學習出合理的hypothesis本身就是一個不合理的事情。
Concept Classes: 在標註資料的時候可以手動給定答案，假設答案為y，背後隱含的函數(concept)
y=c(x)
因為我們在學習演算法的目標是找到Hypothesis(h)去逼近concept(c)。
實際上背後隱含的函數(concept)是未知的且複雜的。
Note: 假設我們的資料特徵數為d，這個concept複雜度為 如果我們選擇簡單的方式，這個特徵是否要採用)。
Generalization Error v.s. Empirical Error (這段內容來自文獻2)
Generalization Error:
Hypothesis: h ∈ H.
Target concept: c ∈ C.
Underlying distribution: D
Generalization error (true error, risk) of h
Empirical Error:
Hypothesis: h ∈ H.
Target concept: c ∈ C.
Samples: S=(x1,…,xn)
Empirical error or risk of h
一般我們在「抽樣後的訓練資料(n筆)」產生的錯誤皆屬於Empirical error，所以你可以看到在Empirical error上是從i=1,…,n筆資料的錯誤和，而Generalization Error是在Underlying distribution (D)下錯誤的期望值。
一般來說，Empirical error is an unbiased estimate (不偏估計) of generalization error
Probably Approximately Correct Learning
PAC learning目標是找到Hypothesis(hS)，並且讓這個Hypothesis有很高的機率讓錯誤率低於 ε，
ε越小代表我們演算法複雜度會更高。
我們同時希望ε越小，也希望δ越小。
Note: 我們希望抽樣後的資料能有有1 − 𝛿的信心水準(confidence Level)來講Hypothesis的錯誤率低於ε。
1 − 𝛿很常用在統計推論上，一般統計學會用α來表示這個𝛿，我不知道為什麼PAC的文章都用𝛿表示。
α 叫做顯著水準 (Significance level): 抽樣資料在進行統計估計後，有多少百分比的機率會判斷錯誤。例如α = 0.05 (5%) 表示 100 次估計中有等於或小於 5 次會判斷錯誤。顯著水準和假設檢定有關，因此又稱做檢定大小。(細節可以看我的書機器學習的統計基礎：深度學習背後的核心技術第四章)
Definition: PCA-learning
A concept class 𝐶 is said to be PAC-learnable, if there exists an algorithm 𝔸 and a polynomial function 𝑝𝑜𝑙𝑦(∙,∙) such that for any ε>0 and δ>0, for all distributions 𝐷 on 𝒳, and for any target concept c ∈ C , the following holds for any sample size n ≥ 𝑝𝑜𝑙𝑦(1/ε,1/δ)
hS: learned by an algorithm 𝔸 from sample S. We say 𝔸 is a PAC-learning algorithm for 𝐶.
但我們關心的是有沒有一個演算法，在給定的random data下可以產生出好的hypotheses，相較於大數據不斷抽取樣本，我們比較希望演算法能夠決定它需要多少資料。
我們回到前面的遊戲(Learning Intervals一個簡單的猜數字遊戲)
假設A利用D選出n個樣本，
所以 I ∈ J。
我們將上面這段文字畫成圖(下圖(右))。
所以假設猜測的範圍(I=[a ̂,b ̂])和實際的Target concept(J=[a,b])會產生誤差Error A和Error B，假設
基於PAC定義，我們希望發生錯誤發生(左邊Error A+右邊Error)的機率小於ε
Recall: PAC
我們預期任何一邊(左邊Error A或是右邊Error B)都小於ε/2
我們先觀察左邊A的部分，(後續公式乘上2就可以表示兩邊)
我們只要抽出的樣本落在A'的範圍(膚色線)內，基本上Error A部分的錯誤發生機率就小於ε/2。
因為抽一筆樣本落在A’的機率是ε/2，抽一筆樣本出來沒有落在A’的機率是1 - ε/2，很不幸運的抽出n個樣本都沒在A’的機率是
所以我們希望 A’⊂A 的機率很小，因為我們不希望 A’⊂A
回到前面的問題: 我們關心的是有沒有一個演算法，在給定的random data下可以產生出好的hypotheses，相較於大數據不斷抽取樣本，我們比較希望演算法能夠決定它需要多少資料。
此問題的回答為:
這樣的話是不是所有的問題都是用這個解哩?
在文獻2 吳老師的投影片舉的範例是Learning axis-aligned rectangles
所以可以發現當問題為2維度矩形的時候
如果將問題衍生為多維的空間
證明可以看文獻2 的page 16。
雖然PAC Boundary基本上可以基於設定的(1)錯誤率ε和 (2) 1 − 𝛿的信心水準(confidence Level)推論出所需的最小樣本數，但在現今深度學習的問題上並不是真的這麼合適，因為深度學習的參數(維度數d)基本上都是幾百萬以上甚至到幾十億的等級，我們收集的樣本數很難超過幾百萬甚至幾十億，但在深度學習的任務上我們依舊能在有限的樣本數下訓練出很神奇能運作的模型，甚至在有 pre-train weight的狀況下，利用少量的樣本也能進行transfer learning，所以理論歸理論，在深度學習的世界依舊有很多研究課題需要被研究，早期的一些理論雖然在深度學習出現後慢慢被打破，但我們還是要學習過去的方法和想法，這樣可以多幫助思維。
文獻
1. Probably Approximately Correct — a Formal Theory of Learning
2. Machine Learning 2021 Spring-HUNG-YI LEE (李宏毅): Theory of ML (Prof. Pei-Yuan Wu)
