# 林軒田機器學習基石筆記 - 第八講
###### tags: `林軒田` `Maching Learning` `機器學習基石`

---

>* **本文為一系列課程之筆記，建議從" [機器學習基石筆記-1](https://hackmd.io/s/ryxzB7LwN) "開始閱讀**
>>
>* **本文討論內容請參考:
機器學習基石第八講 : Noise and Error**
>
>* **本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義**
>

---

## Noise

在「[機器學習基石筆記-2](https://hackmd.io/s/S1U_sR-O4)」中有一段我是這麼寫的 :

> 我們手中有的 dataset 的取得以及分布、雜訊的生成、Model對未來資料的擬合精確度…等也都跟機率有關，所以在機器學習的研究進程中會將機率引入相對來說算是合情而且合理的。有了機率的概念，這表示不會百分之百精準，這時error的概念也會隨之而生。
>

這樣的概念便在林軒田課程的第八講中有延伸性的討論。
<br>
在前面幾講中，對於機率分布，我們僅討論到 $\mathbb{X}$ 應該會來自於某個 $distribution\ \mathbb{P}$，記做 $\mathbb{X}\overset{i.i.d}{\sim}\mathbb{P}(\mathbb{X})$，有了機率分布，也便有了 $Noise$。


但 $Noise$ 是無所不在的[^1]，它也會出現在 $y$，也就是說，我們也可以把 $y$ 視為是 $f$ 作用在 $\mathbb{X}\overset{i.i.d}{\sim}\mathbb{P}(\mathbb{X})$之下的產物，記做 $y\overset{i.i.d}{\sim}\mathbb{P}(y\mid \mathbb{X})$
( $\mathbb{P}(y\mid \mathbb{X})$ 我們可以解讀成，在 $\mathbb{X}$ 條件下，$y$ 發生的機率分布 )

[^1]: 就機率論的角度而言，或許根本不存在這種 determinate 的狀態，所有的事件都帶有隨機性。所以在機率論中 0% 機率不代表絕對不會發生，100% 也不代表絕對會發生。

---

上面的概念還是很難理解嗎 ?

我們用幾個面向來試圖解釋這樣的隨機性 :
1. **我們可以將隨機性視為每一顆球顏色狀態會一直不斷的改變 :**
如下圖所示，在Bin中的球顏色會一直變動，直至我們抽出來的那一瞬間才會確定顏色狀態。


2. **我們也可以將隨機性視為翻轉結果的機率 :**
舉例來說，某樣本 $\mathbb{X}$ 在理想狀態中 label 為 +1 ( 意即$f(\mathbb{X})=y=+1$ )，但因為 $noise$ 存在，這樣的隨機性會有一定的機率使 $\mathbb{X}$ 的 label 被翻轉 ( $f(\mathbb{X})\neq y=-1$ )
在這樣的解釋下，我們也可以將真實的狀態 ( $f(\mathbb{X})=1$ )視為是這樣隨機性下的特例。

---

當我們可以瞭解這樣的隨機性必須考慮在Machine Learning當中，我們想要知道的事情是 : **我們前面的所有討論是否仍然成立 ? 也就是說，在有 Noise 的情況下VC Bound是否仍然存在 ?**

其實如果將上圖 $flipping\ noise\ level$ 的概念加入 $E_{in}(h)$ 與 $E_{out}(h)$ 之中，經由[機器學習基石筆記-2](https://hackmd.io/s/S1U_sR-O4)的證明之中，應該也是可以找到一個 finite upper bound。[^2]

[^2]: 這是一個比較直觀的想法，但目前尚未看到比較嚴謹的數學證明，待找到後再行補上。

## Error

終於來到機器學習演算法中，最後一個元素，也是最重要的元素 -- Error
既然所有的資料均充滿了隨機性，那麼量測 error 便是一個很重要的工作，這項工作不僅可以讓我們可以評估 $g$ 與 $f$ 的近似程度，對於簡單如 PLA 或困難如 Deep Learning 來說都非常重要，因為它可以做為每一次迭代調整的依據。

對某一個 hypothesis $g$，任一資料 $\mathbb{X}$， 我們常見的 Error Measure 有 :

* **0/1 error :** $err([\![ \ g(\mathbb{X})\neq f(\mathbb{X})\ ]\!])=err(\tilde{y}-y)=\begin{cases}1 & \mbox{if}\ g(\mathbb{X})\neq f(\mathbb{X})\\0&\mbox{if}\ g(\mathbb{X})=f(\mathbb{X})\end{cases}$
* **Squere error :** $err(\tilde{y}-y)=(\tilde{y}-y)^2$
* **Absolute error :** $err(\tilde{y}-y)=\mid\tilde{y}-y\mid$

$\Longrightarrow$ 我們也可以藉此定義出 in-sample error $E_{in}(g)=\frac{1}{N}\sum\limits_{n=1}^{N}err(\tilde{y},y_n)$ 以及 out-of-smaple error $E_{out}(g)=\mathbb{E}(err(\tilde{y},y_n))\ where\ \mathbb{E}\ is\ Expected\ value$
<br>
以下給出一個例子 :

當我們使用不同的 error measure ，勢必會找出不同的 error 值，也因此，也會影響到我們最後形塑出來的 $f$ 會有所不同。

## Weight Classification


我們從上述例子可以發現，當分類錯誤的情況發生時，隨著不同事件，應該會有不同成本上的 COST ，因次，我們的分類器必須也將這些 " weight " 考慮進去。說是簡單，但是在真正實務上，我們根本無法將這些 cost比例 ( weight )很精準的量化出來，那當然我們會無法把真正理想中的 error 計算出來。

所以我們有幾個方向可以考慮 :
1. 我們可能可以利用 0/1 error 或 square error，將分類錯誤的點視為 noise ，讓演算法找出使 noise最小的 model。但這樣的方式在 0/1 error上會是一個 NP-Hard 問題。

2. 或者我們乾脆找出比較容易讓演算法好運作的解，close-form solution ( analystic ) 或是 convex object solution ( like Gradient Descent )。

不管是上述哪一種，都並非是真正的 error ，在日後課程我們會記做 $\hat {err}$

若我們拿上圖 CIA 例子來看，從 VC Theory 的角度，就是希望讓 $E^\mathbb{W}_{in}(h)=\frac{1}{N}\sum\limits_{n=1}^{N}\begin{Bmatrix}
1, & y_n\neq+1 \\1000, & y_n=-1\end{Bmatrix}\cdot[\![y_n\neq h(\mathbb{X})]\!]$ 盡量最小化

$\Longrightarrow$ PLA ? 資料不一定是 Linear Separable。
$\Longrightarrow$ Pocket ? 可經由迭代不停找出更好的 $\mathbb{W}$ 作為 $\hat{\mathbb{W}}$ ?
$\Longrightarrow$ Pocket Algorithm 在一般 0/1 error 中的確可以確定能找到 $\min E_{in}$，但在 weight error 中也能有這樣的保證嗎?
<br>

我們可以將每一個權重視為資料的複製次數，然後再來做 0/1 error 的 Pocket Algorithm。

**PS : 在實務上我們並不會真的複製這麼多份數，如此太耗費計算成本，因此我們會將這樣的概念延伸成為相應資料被抽中檢查的機率**