PAC是probably approximately correct 的縮寫。
PAC learning，是機器學習的根基。
（本文根據台大教授林軒田的上課教材來寫）
機器學習的流程：
我們從現實世界中收集資料，並將資料餵給我們的演算法，演算法會從hypothesis set中選出一個function。
我們要的是，從hypothesis set中選出的這個function，能跟真實世界中生成資料的未知函數越接近越好。
[機器學習，不可能？？]
舉個例子，現在我們取得的資料x是用0和1組成的三維向量。
x所對應到的y為圈或叉。
現在我們蒐集的資料如下{0,0,0},{0,0,1},{0,1,0}{0,1,1}{1,0,0}。在supervised learning下，我們對蒐集到的資料做上正確的標記（y）。
將這些(x,y)組成D這個set。
為了要讓演算法選出來的function接近真實世界的function，很直覺的想法是要讓選到的function在Ｄ上能夠正確。
參考上圖，我們可以發現現在候選的function全都是在Ｄ上完全正確的，但在Ｄ以外的資料，我們沒辦法保證哪一個function才會貼近真實世界的函數。
[解救？？]
這是不是代表機器學習是不可能的呢？
我們需要一些新的工具來協助。
我們原先的assumption是“真實世界中的函數是未知的”。而我們要做的是在有限的資料上，選出一個函數接近真實世界的函數。
這讓我們想到在統計上的抽樣。我們透過抽樣，來估計整個群體中的現象大概比例為多少。
假設現在有一個很大的罐子，裡面放了橘色和綠色的彈珠，我們想要知道罐子裡橘色彈珠的比例（未知）。
在統計上，我們可以用抽樣的方法來估計整個罐子裡的橘綠比例。
根據Hoeffding’s Inequality，我們在抽樣上得到的現象，有很大的機率(probably)是很接近(approximately)整體的現象。
[將抽樣套到機器學習上]
罐子中未知的橘彈珠比例 <-> 我們從hypothesis set選出的某hypothesis是否接近真實函數
在罐子裡的彈珠 <->世界中的x
橘彈珠 <-> 某hypothesis在一世界中的x上mapping的情況 和 真實函數mapping的情況不一樣
綠彈珠 <->某hypothesis在一世界中的x上mapping的情況 和 真實函數mapping的情況一樣
抽樣（可以明確得到在取出的彈珠中橘彈珠和綠彈珠的比例） <->某hypothesis在蒐集到的x上的表現（可以明確的知道某hypothesis在Ｄ上錯誤和正確的比例）
根據Hoeffding’s Inequality，我們的某hypothesis在蒐集到的x上的表現（和真實函數一樣不一樣的比例），和在真實世界中的其他x上的表現有很大的機率是很接近的。
根據上面的套法，我們可以得出以下結論：
若選到的hypothesis在蒐集到的資料表現上和真實函數一樣，那麼他有很大的機率在其他x上的表現和真實函數是很接近的。
注意到結論所說的，是一「驗證」，而不是一種學習！！！
真正的學習，是讓演算法在hypothesis set中做選擇，選出某hypothesis，這個hypothesis在蒐集到的資料上表現的跟真實函數一樣（或非常接近），那麼根據Hoeffding’s Inequality，我們可以很有信心的說選出來的hypothesis和真實函數很接近。
學習！！
難道我從hypothesis set中挑出一個hypothesis在Ｄ上的表現和真實函數一樣就可以了嗎？？？
試想有一個公正的銅板（如果丟非常非常多次，正反面的比例為1/2），我丟五次，那麼連續出現五個反面的機率是1/32。
那麼試想有150個公正的銅板，讓150個人每人拿一個，連續丟五次，在這150個人中，至少有一個人丟出連續五個反面的機率是1-(1/32)¹⁵⁰ ＞0.99
把每個人當作一個罐子，罐子裡面正反面比例1：1，因為是公正的銅板。
一個人丟N次這個動作是取樣，當N很大，Hoeffding告訴我們取樣得到的現象和真實現象有很大的機率很接近
當有多個選擇時，我們看到偏誤很多的取樣的機率增加
我們看到，不好的取樣是取出來的反面佔100%，但實際上銅板是公平的，也就是反面佔50％
那回到機器學習上，我們「不好的取樣」是什麼呢？
不好的資料！
不好的資料讓我們看到某hypothesis在這些資料上和真實函數的表現是一樣的。
但走出這些資料卻發現該hypothesis的表現和真實函數差超多。
Hoeffding’s Inequality告訴我們，一個hypothesis遇到不好的資料的機率非常小，也就是它在D上的表現跟真實函數在Ｄ上的表現的差距，有很大的機率跟在Ｄ以外的差距很接近。
但為了要「學習」，現在有多個hypothesis，組成finite的hypothesis set。
每一個hypothesis遇到不好的資料的機率很低，但有多個的時候，遇到的機率就變高了。
假設有一筆資料對其中一個hypothesis是不好的，他就會擋到我們的algorithm挑出最接近真實函數的hypothesis。(阿這筆資料都對他不好了，是要怎麼學，如果其實這個hypothesis最接近真實函數，你被不好的資料搞，最後演算法去選別人，不就ＧＧ；反之亦然)
那我們要處理的就是，在這些「有限」的hypothesis中，他們遇到不好的data的機率究竟為何？如果很小，那麼機器學習就是有可能的！
那就取upper bound吧，如果upper bound很小，那我們這個finite hypothesis set遇到不好的data就很小，機器學習就有可能！
恩..對：）
在有限的hypothesis set的條件下，機器學習可行
那麼infinte的呢？可以先思考假如兩個hypothesis是反的，例如差個正負號，那對其中一個hypothesis是不好的data，對另一個hypothesis也是不好的！
資料來源：
https://www.csie.ntu.edu.tw/~htlin/mooc/doc/04_handout.pdf
https://www.coursera.org/learn/ntumlone-mathematicalfoundations/home/welcome
