Recap

|500 source: https://www.csie.ntu.edu.tw/~htlin/course/ml24fall/doc/08u_handout.pdf p.2

如果資料有 noise 怎麼辦？

Noise and Probabilistic Target

VC bound on Noise

先來說說什麼是 noise，一樣以 credit approval 為例:

noise in $y$ : good customer mislabeled as bad, same customer but different labels
noise in $\bf x$ : incorrect customer information

在有 noise 的情況下，VC bound 還能正常運作嗎？

在 Lecture 4 的時候，我們用罐子取球來當例子，假設罐子內球的分布是 $P({\bf x})$ ，想要知道拿到紅色球的機率，也就是 $[[f({\bf x}) \ne h({\bf x})]]$

現在如果罐子內的球會變色，也就是有 noise，在我們取 $\bf x$ 的當下罐子分布是 $P({\bf x})$ ，但之後罐子裡的分布會改變，因此拿到紅色球的機率就會變成 $[[y \ne h({\bf x})]]\quad\text{with}\quad y \sim P(y\ |\ {\bf x})$

如果這時候 $x, y$ 都是 i.i.d. (independent and identically distributed) 的話，則實際上 $({\bf x},y)\overset{\mathrm{i.i.d.}}{\sim}P({\bf x},y)$ 和 ${\bf x}\overset{\mathrm{i.i.d.}}{\sim}P({\bf x}), y\overset{\mathrm{i.i.d.}}{\sim}P(y\ |\ {\bf x})$ 的概念是一樣的，所以 VC bound 仍是成立的。

Target Distribution

在這裡 $P(y\ |\ {\bf x})$ 被稱為 target distribution，我們用一個例子來解釋它的概念。

假設現在我們知道 $P({\color{blue}\text{o}}\ |\ {\bf x}) = 0.7, P({\color{red}\text{x}}\ |\ {\bf x}) = 0.3$ ，也就是說真正的 $f({\bf x})$ 是 $\color{blue}\text{o}$ 的機率是 70%。還記得我們學習的目的是「預測真正的 $f({\bf x})$ 是什麼」，如果我們將理想的 $f'({\bf x})$ 設定成 $\color{blue}\text{o}$ 當作學習目標的話，則

$g({\bf x}) = \color{blue}\text{o}$ 的機率是 100%
真正的 $f({\bf x}) = \color{blue}\text{o}$ 的機率是 70%，因此我們預測成功 ( $g(x) = f'(x) = \color{blue}\text{o}$ ) 的機率就是 70%
反之，noise 出現的機率 (noise level) 就是 30%。

我們通常都會以出現機率較高的那個結果 (in this case, $\color{blue}\text{o}$ ) 當作理想的結果來做訓練，因此 target distribution 的概念其實就是 ideal mini-target (理想的 $f'({\bf x})$ ) + noise。

原本(沒有考慮 noise)的 target function $f$ 其實就是 noise level = 0% 的 $P(y\ |\ {\bf x})$ :

$P(y\ |\ {\bf x}) = 1$ for $y = f({\bf x})$
$P(y\ |\ {\bf x}) = 0$ for $y \ne f({\bf x})$

小結，在原本(沒有考慮 noise)的情況下，我們的學習目標是: 在 $P({\bf x})$ 的分布下，找出模型 $g$ 來逼近真實的 target function $f$ 。

現在如果考慮 noise，則變成了: 在 $P({\bf x})$ 的分布下，找出模型 $g$ 來逼近理想的 mini-target function $f$ (有 noise)，用 mini-target function 來逼近真實的 target function。

|500 source: https://www.csie.ntu.edu.tw/~htlin/course/ml24fall/doc/08u_handout.pdf p.6

Erorr Measure

在這個章節，我們要討論如何知道 $g$ 和 $f$ 有多接近。在前面的章節，我們其實已經用了 ${\color{blue}E_{\text{out}}(g)} = \mathbb{E}_{{\bf x} \sim P}[[g({\bf x}) \ne f({\bf x})]]$ 來在 out-of-sample 的 unknown ${\bf x}$ 內衡量 $g$ 和 $f$ 的「平均誤差」，也就是平均出錯的機率。我們一般將這個方法稱為 error measure ${\color{blue}E(g, f)}$ ，而接下來我們要討論的是另一種在單一 ${\bf x}$ 上衡量誤差的方法。

Pointwise Error Measure

我們可以先把 $E(g, f)$ 表達成 averaged $\text{err}(g({\bf x}),f({\bf x}))$ ，因此 $E_{\text{out}}(g) = \mathbb{E}_{{\bf x} \sim P}\underbrace{[[g({\bf x}) \ne f({\bf x})]]}_{\text{err}(g({\bf x}),f({\bf x}))}$ 而 $\text{err}$ 被稱為 pointwise error measure。

因此原本的 $E_{\text{in}}$ 和 $E_{\text{out}}$ 就變成了: $E_{\text{in}}(g) = {1\over N}\sum^{N}_{n=1}\text{err}(g({\bf x}_n),f({\bf x}_n))$ $E_{\text{out}}(g) = \mathbb{E}_{{\bf x} \sim P}\ \text{err}(g({\bf x}),f({\bf x}))$

那實際上 $\text{err}$ 內部是怎麼衡量誤差的？

Two Pointwise Error Measures

現在我們將 $g({\bf x}) = \tilde{y}$ 和 $f({\bf x}) = y$

0/1 error

$\text{err}(\tilde{y}, y) = [[\tilde{y} \ne y]]$ 檢查 $\tilde{y}$ 是否正確，通常用在 classification 上。

squared error

$\text{err}(\tilde{y}, y) = (\tilde{y} - y)^2$ 檢查 $\tilde{y}$ 距離 $y$ 有多遠，通常用在 regression 上。

How Error Function Guide Learning?

我們要找的 ideal mini-target $f({\bf x})$ 實際上是可以由 $P(y|{\bf x})$ 和 $\text{err}$ 來定義的。

|500 source: https://www.csie.ntu.edu.tw/~htlin/course/ml24fall/doc/08u_handout.pdf p.11

從圖中我們可以發現在同一個 $P(y|{\bf x})$ 下，使用不同的 $\text{err}$ 會產出不同的 $f({\bf x})$ 。

Choice of Error Measure

假設我們現在要實作指紋辨識機器，則機器在判斷時可能會有四種情況:

|400

如果我們使用 0/1 error 的話，則學習過程中我們給予 false reject 和 false accept 的 penalty 會是一樣的 (因為 0/1 error 只知道它分類錯誤而已)。

然而，在不同的應用情境，false reject 和 false accept 造成的後果可能相當不同。

舉例來說，如果我們將指紋辨識用來幫超市顧客做打折，則

false reject: 代表該顧客有優惠，但機器拒絕給優惠 → 顧客很不開心，爛超市
false accept: 代表該顧客沒有優惠，但機器卻給了優惠 → 沒啥影響，賺到了很明顯的，對超市來說，false reject 的後果比較嚴重，所以應該要把 false reject 的 penalty 加重，來讓減少機器產生 false reject 的可能:

|400

第二個例子，如果我們將指紋辨識用來做 CIA 的出入管制，則

false reject: 代表該人員有認證，但機器拒絕給其進入 → 該人員很不開心，然後呢
false accept: 代表該人員沒有認證，但機器卻放其通行 → 出事了因此，在這個情境下，false accept 的後果嚴重很多，因此我們應該將 false accept 的 penalty 加重:

|400

從上面的例子我們知道 $\text{err}$ 的挑選和使用情境有非常大的關係，然而實際上即便我們設計了一個完全符合情境的 $\text{err}$ ，這個 $\text{err}$ 可能在學習的過程中很難去 optimize，因此我們需要使用另外的，可能沒那麼符合情境但是比較容易 optimize 的 algorithmic error function: $\widehat{\text{err}}$ 。這個 $\widehat{\text{err}}$ 需要是 plausible，而且要 easy to optimize for $\mathcal{A}$ 。

至此，我們已經完整的介紹整個 learning flow 了。

|500 source: https://www.csie.ntu.edu.tw/~htlin/course/ml24fall/doc/08u_handout.pdf p.18