---
tags: 機器學習基石上：數學篇
---

Ch8 Noise and Error
===

## Content
[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [Noise and Probabilistic Target](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/ySOFV/noise-and-probabilistic-target)

### Recap: The Learning Flow
- 我們有 unknown 的 $P(\mathcal X)$，跟 unknown 的 target function $f:\mathcal{X\rightarrow Y}$，從這樣的 distribution 和 function 裡面抽出 training examples $D:(x_1,y_1),...,(x_N,y_N)$ 來做 ML
- 那麼在 target function 加上了 noise 會不會有什麼問題呢?

### Noise
- noise 可能的各種來源

### Probabilistic Marbles
- 現在 data 有 noise，對應到之前彈珠跟罐子的比喻，那就是彈珠的顏色現在加入了一些隨機性，它有一定機率是橘色，一定機率是綠色的。
- 我們還是可以抽一把彈珠出來估計整個罐子裡的橘色彈珠比例是多少。
- **現在，target function $f(x)$ 變成了 target distribution $y\sim P(y|x)$**
- 就算這樣重新證明一次，VC bound 還是會 work。
- 所以現在把兩個部分(marble & probabilistic color)整合起來，我們可以說，只要我的 $(x,y)$ 是 i.i.d. 的從 joint distribution $P(x,y)$ 抽樣出來，那麼 VC bound 就還是會 work。

### Target Distribution
- **mini-target 就是指在某個 $x$ 上面最理想的預測是什麼。**
- target distribution 可以從兩種觀點看
- 最好的預測 (即mini-target) 是什麼? 有多少比例的雜訊?
- 也可以用我們之前 deterministic 的觀點看，那就是 P(y|x)=1或0，沒有雜訊
- 在常見的 data point 上做得好，就是 ML 在做的事情。

### The New Learning Flow

### Fun Time: Noise
- 如果我們的資料是 linear separable，是不是代表我們的 f 就一定要是一條線? 不一定啊，為什麼，因為有可能你的 f 是彎彎曲曲的，只是因為取樣的過程，所以剛好得到一個 linear separable 的資料，或者你的 f 其實是 noisy 的，不過你的運氣很好，你完全沒有碰到那些 noise，所以你得到linear separable 的資料，所以從資料的性質，不見得我們一定能夠說 f 的性質是怎麼樣，**VC 給我們的保證 並不是從資料性質我們就知道 f 的性質是怎麼樣，而是從資料如果我們得到很低的 Ein，配合上 小的VC dimension的話，我們就得到很低的 Eout，但這不是完全代表說我們的 f 一定要是線性的，或者不是線性的，這是一個很重要的觀念，我們希望大家能夠知道。**

## [Error Measure](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/i48Ww/error-measure)

### Error Measure
- 一般而言會考慮
- out-of-sample：在未見過的 sample 上評估
- pointwise：可以在單一個 sample 上評估 (再去做平均
- classification 的 case 來說會用最簡單的 0/1 error

### Pointwise Error Measure

### Two Important Pointwise Error Measures
- 簡化起見，$g(x)$ 我們叫它 $\tilde y$
- > Q: 怎麼不是 $\hat y$ ?
- 現在我們有兩種 error
- 0/1 error (通常用在 classification)
- squared error (通常用在 regression)

### Ideal Mini-Target
- 來看看分別用這不同 error function 來選擇 hypothesis 會發生什麼事
- 當 $y$ 是 discrete 的 (只有 3 種值)
- 用 0/1 error 的話
- 若 hypothesis 說 $\tilde y$ 是 1，則 error function 平均會是 0.8，依此類推
- 根據平均會犯的錯誤，我們最後會選擇 $\tilde y=2$ 的 hypothesis
- 用 squared error 的話
- 根據平均會犯的錯誤，我們最後會選擇 $\tilde y=1.9$ 的 hypothesis (這樣好像就是一個不太合理的 hypothesis?)
- **上述可以得知，從 target distribution $P(y|x)$ 和 error function $\text{err}$ 就定義了我們理想的 mini-target (最好的預測 or 想要的輸出)**
- 如果用 0/1 error，那麼我最好的 mini-target 就是選最大的 P 得到的 y $\arg\max_\limits{y\in\mathcal Y}P(y|x)$
- 如果用 squared error，那麼最好的 mini-target 就是機率的加權平均值 $\sum_\limits{y\in\mathcal Y} y\cdot P(y|x)$ (就 $y|x$ 的期望值嗎?)
- 上面的這兩個東西可以花一點力氣證出來

### Learning Flow with Error Measure
- 這裡比之前多了錯誤衡量
- 另外，希望大家心裏有一個概念說在一些不同的問題上(例如 regression) 我們可以再定義它的VC dimension，這些不一樣的方式定義VC dimension 我們可以得到類似的VC bound，這類似的VC bound對於不同的 錯誤衡量方式不只是classification這個zero one的方式，其他的方式我們也可以有類似的這個VC bound。 至少這個精神我希望大家能夠記得

### Fun Time: Error Measure
- weighted median，也就是機率大約在一半的時候的那個數字
- > Q: 這個要怎麼證明是 median 啊 @@

## [Algorithmic Error Measure](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/ncMcU/algorithmic-error-measure)

### Fingerprint Verification



### 從前面兩個例子我們可以知道 error function 其實根據 application 而有不同
- 但有時候很難量身打造出一個真正的 error function，很多時候沒辦法直接把 user 心裡所想的東西數學化到 error function 裡面。
- 這時候我們就要用一些替代方案 $\widehat {err}$ 例如：
- 可以說服自己的方式(plausible)，例如找到 noise 最小的地方
- 或者設計一些讓演算法好做的方式
- closed-form 一下就可以解出來
- convex objective function

### Fun Time: error function
- 多了 $\widehat{err}$

## [Weighted Classification](https://www.coursera.org/learn/ntumlone-mathematicalfoundations/lecture/YUDi7/weighted-classification)

- **不同的 error 有不同的重要性，我們就叫它 weighted classification**
- **我們前面列的那個表就叫 cost matrix / loss matrix / error matrix**

- 假設在 cost matrix 中某種 error(例如false accept)的成本是1000倍(相較於其他error)，那要怎麼改變我們的 pocket PLA 呢?
- 可能會想說，我們把計算 $E_{in}$ 的方式改成納入 cost matrix 的 $E_{in}^w$ 就好，但這樣得不到理論的保證說 pocket PLA 可以做得好。
- 將此種類別的資料(label為-1)複製成1000筆再丟進去train也可實現, 但記憶體代價高
- 
- 將演算法修改成 拜訪那些資料點的機率變成1000倍
- 
- **這是一個 systematic route (又稱 reduction)，就是說有系統地把一個方法延伸到可以在另外一個問題使用，就是問題的互相轉換。**

### Fun Time: Cost Matrix
- 但是在 unbalance 的資料也會造成 error 估算問題, 因此又要調整權重(把1000改掉?)