Caltech Learning from Data 4 - error and noise

point-wise error measurement

我們要知道hypothesis跟target f的差別到底多少？
所以會有一個error function E(h,f)，嘗試找出h 來 minimize這個function。

每個input點x都會有一個error function:

可能的例子包括之前講過的squared error:

上面的binary error的notation要講一下，意思就是當[ predicate ] predicate為真的時候，回傳1，反之回傳0。所以h(x)與f(x)的分類一致的話， h(x) != f(x)是false，則 [h(x)!=f(x)] 回傳0，這是我們要的，因為這的確就是最小的error分數。

Overall error

定義為 average(all point-wise error)，其實就是之前提到過的in-sample error:

也就是training set的training error。
注意所有in-sample points都來自同一個probability distribution (即便未知，但這是符合Hoeffding Inequality的重要前提），但是我們隨機挑選出training set / test set，這是一個uniform distribution，所以會有上面1/N的weights。

out-of-sample error就是h generalization的能力的好壞，此時的x是out-of-sample，也就是test set或是任何x in sample space：

注意這邊average的定義為expectation，因為任何我們不知道underlying distribution為何。

我們又可以完善我們的learning diagram:

如何挑選error  measurement function?

大哉問！沒有正確答案，因為這是domain-specific decision。
先說有以下兩種error：

對某些application來說，false reject (false negative)是很嚴重的事情，例如一個會員怎麼嘗試都無法通過指紋辨識，那肯定會流失客源，不過在此例中，false accept (false positive)就沒那麼嚴重，而且真的被判斷false accept（假設會員優惠）也留下了指紋，對這些利用系統誤判獲得小便宜的人來說，反而留下了證據。

上面這個matrix是一個 penalize weighting matrix，所以如果我們要penalize false reject，可能的matrix:

同樣的指紋classifier，安全門禁系統反而會不在意false reject (false negative)，反正刷不過就打電話給MIS人員，但是不能錯放一個外人進入公司重地，也就是要penalize false accept (false positive)：

所以完全是domain specific來選擇error function。
繼續來擴充我們的learning diagram:

Noisy targets

一個真實的情況是 target function通常不是一個function (不符合function定義，例如兩個input space的點x1 x2，因為採取了有限的features，使得兩個不同的點卻有相同的input vector x，但是實際上兩者在data中的y卻可能不一樣，例如兩個同樣人種年紀職業的信用卡客戶，一個y1=違約，一個y2=未違約，這是有可能的。

所以同樣一組f(x)卻map到y1和y2，並不符合function的定義，這是由於feature資訊不足造成的，所以真正的y應該是f(x) + 資訊不足造成的noise。 

修正target function成 "target probability distribution" P(y|x)，所以y的機率會隨著不同x而update，則(x,y)出現的機率是一個joint probability:

採用y是conditionally dependent on x的機率觀點的話，我們要找的真正的target function f(x)可以視為 E(y|x) + y值跟f(x)的差距(可以歸類成noise):

講這麼多是因為真實案例中的single data point無法真正反映input space的一個點所有資訊，所以 y != f(x)，我們只能從(x,y) infer出已經被noise污染過的f(x)，也就是來自target distribution P(y|x)：

而我們learning只能找出target distribution，永遠不可能找出真正的f(x)。
這是supervised learning最終定案的diagram。

Machine Learning is feasible (以機率觀點來說）

理論面上，首先利用in-sample X 都來自同一個distribution的基礎上，Hoeffding's Inequality提供我們可以透過 in-sample performance (error) 來 track out-of-sample performance的理論可行性，所以機器學習就是建築在一個generalization的論述：

實務上，我們希望Eout(g) ~= 0 （實務上application-specific requirement)，這樣代表g ~= f，也就是generalization well，或說"learn well"。