機器學習基石筆記4：機器學習可行性論證上

02-27

前記：第三講的部分偏基礎和概念，故沒有單獨成文，一併記錄在機器學習筆記1內。

第一部分：證明適用於訓練集的g同樣適用於整個輸入空間

首先：學習可能是做不到的，在訓練集中可以求得一個最佳假設g，但是在訓練集外的樣本中，g可能和目標函數f相差甚遠。

先從統計學出發，以從罐子中拿球為例：

罐子中橙球比例u，綠球比例1-u，抽樣樣本N中橙球比例v，綠球比例1-v；可以想像到，v在很大幾率上接近u，但是到底有多大的可能性兩者接近呢？在此引入霍夫丁不等式：

$P[| u-mu|>varepsilon] leq 2exp(-2varepsilon^2N)$ 其中：

再總結：

從罐子取球轉換到機器學習（先確定一個假設h）

用 $E_{in}(h) 、E_{out}(h)$ 表示一個確定的假設函數h在訓練樣本的錯誤率和整個輸入空間的錯誤率，則有： $P[|E_{in}(h)-E_{out}(h)|>varepsilon] leq 2exp(-2varepsilon^2N)$

如果求得一個 $h$ ，使得 $E_{in}(h)$ 很小，則可以推出 $E_{out}(h)$ 很小，即 $happrox f$ ，則機器學習演算法選一個最小的 $E_{in}(h)$ ，將 $gleftarrow h$

以上證明了機器學習在訓練樣本中學習得到的g在整個輸入空間中也可行。

第二部分：證明訓練樣本的誤差不會導致選擇到的g對整個輸入空間有誤差

訓練樣本分為好的和不好的，如果存在h使得Ein和Eout相差很遠，那就是不好的訓練樣本。

上圖包含了M個假設h，而不好的D不是由單一假設就能確定的，而是只要有一個假設在此抽樣D上表現不好則該抽樣被標記為不好的。現在求訓練樣本不好的幾率是多少：

當訓練樣本足夠多，h個數有限大，則可以說每一個假設h都是安全的，即Ein ~ Eout

所以如果通過機器學習找出了g滿足 $E_{in}(g) approx 0$ ，則PAC規則可以保證 $E_{out}(g) approx 0$

一切看上去都是那麼美好，但是忽略了一個問題，那就是如果h的個數無限多呢？請見下一篇講解分析。

題圖：2017年11月2日15:29:49

機器學習基石筆記4：機器學習可行性論證 上