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"。

Caltech Learning from Data 3 - Linear models

Raw input representation

課程先從real data著手，用的是郵遞區號碼辨識的application。
以下是一個16x16 pixel的數字影像：

256 pixel，可以用256-vector來表現input vector:

如果用perceptron linear model的話，事實上要找出256-weight vector + bias w0:

這是huge weight vector，計算量可能難以實現。
以上是把每個pixel value都當作input vector一部分，所以稱為raw input，事實上我們要選出某些代表性的feature來當作input vector，這樣才能簡化計算量。

Feature vector

例如
intensity: 黑色部分佔比可能暗示不同數字
symmetry: 這的確是有分類意義

我們縮減出3-vector (including x0 for bias):

所以Perceptron model 也只有3d vector weights:

如果把兩個數字(1 , 5 )畫在2d feature (x軸intensity, y軸symmetry) 座標上，可以發現這兩個數字是可以almost畫出一條直線分開的：

PLA iterations

先看下圖：

首先這個1和5的數字input事實上不是100% linear separable，所以PLA永遠不會converge，我們設定一個iteration數量的上限，假設是1000次，取第一千次時的in sample error (Ein)的hypothesis當作final hypothesis function g。

此圖只是示意，因為現實中，不可能知道out of sample error是多少（test set不算嗎？），所以這是讓我們知道說，iteration下來，Ein的確很好的track Eout，兩者間的高度差就是epsilon。

這不是這1000次中的最佳解，其實可以永遠記錄比目前小的epsilon就好 ：

看起來好一些了。

Linear Regression

regression就是real value output的意思，而其weights形式也是linear，也就是h(w)是線性的function。

regression跟classification不一樣的地方在於，classification明確知道正確與否，所以衡量error是簡單的binary value，但是regression就要定義什麼是好的in sample error Ein?
常見的in sample error是用squared error:

注意我們不知道f，但是我們知道f(xi)，因為regression data一定有歷史資料yi，例如歷史房價，這就是f(xi)。

這是對單一input x在hypothesis h作用下，對所有in sample point來說，取其square error平均值代表in sample error整體error:

一個regression演算法就是要找出最小的in sample error的h。

2d feature vector (hyperplane is linear in 3d space):

Minimizing Linear Regression Ein

原本的Ein(h)寫成Ein(w):

如果把每一個xn vector全部放入一個matrix的每個row，並且把所有yn放入一個matrix:

Xw - y是一個vector，而且vector norm的定義如下：

所以我們可以重新表達Ein(w)用vector form:

平方用來抵銷norm的根號，北七ㄌ，就是一個簡寫而已，搞好久。

所以我們找出w使得Ein(w)最小：

此時X和y都是常數，實務上就是training set X和training set label y。

寫成vector form好處就是找出最小值的過程中，需要微分matrix，這簡單很多：

解出w:

X上的十字符號稱為X-dagger，稱為pseudo-inverse，因為X-dagger * X = I
psuedo-inverse有很多numeric library可以解決，我們是幾乎不用也不該自己去implement。

這是computational approach，不用經過iteration去收斂，不過有一個先決條件就是：X^T*X要有inverse，不過幸好在real world data invertible的機率趨近於100%，因為#@$#$#@$，好吧他解釋的我聽不懂 XD。

所以基本上只要有X和y就可以做出linear regression:

如果data non-linear separable?

一個可能性就是把data做transformation，例如2d-feature (x1,x2)變成 (x1^2, x2^2)，有點像是變成從某個圓心測量每個點的距離，這樣transform過後的points是可能linear separable，當然這樣的nonlinear transformation不能改變h(w)的linearity，也就是w vector與h(w)必須保持線性關係：

相關筆記為polynomial feature transformation。

上面說到可以先做一個phi nonlinear transformation，把data轉到另一個feature space，然後可能可以apply linear models，不過我們終究是在原來的input space工作，所以再做一個inverse transformation (如果有的話）轉換回原本的input space:

詳細過程：
1. 單一input vector x (國民車）被nonlinear transformation phi轉換到z space （高階卡車）
2. 所有的x in x space都被phi轉換成z space中的點
3. 所有的y都不改變
4. training發生在z space，所以weight vector我們特別標注為w~ (w tilda)，用來註明這是在transformed過的feature space z learning出來的weights:

5. final hypothesis function g 得在z space運算，所以任何input x得先轉換成z再apply g:

結論

Linear models被用來比喻是國民車，省油好開，但是不會有最佳體驗，不過值得在面對一個問題的時候，先嘗試看看能否達到可接受的方案，因為這是很經濟的選擇。

豪車例如svm當然比linear models 性能與體驗更好，不過價格就是貴！

Caltech Learning from Data 2 - Can machine really learn？

Learning真的能做到嗎？

一個unknown target function真的能靠有限的data input來逼近嗎？
這需要證明，要不然learning只是火雞的體重：一千天之前都是線性成長，一千天到了歸零，但是卻learn出了線性target function。

這其實是大哉問。我上了這麼多ML課程，只有caltech這個老師把這個大哉問問了出來，真的是很棒的課！！！！

機率實驗

從某個桶子內只有兩種顏色的球，抽中任一顏色的機率如下：

miu是未知常數，也就是說如果真的有一個underlying probability distribution的話，機器是否能infer或逼近這個miu?

定義sample = 從這個桶子拿N個球出來的此N個球
定義nu = 每次sample中紅球佔的比例，這是一個random number

如果獨立的多次sampling，能否nu可以infer or 逼近miu? YES
統計學證明：nu (sample frequency) 逼近miu (population frequency)的誤差epsilon，其機率跟N成exponential衰退：

所以N越大，nu和mu的誤差大於容忍區間epislon的機率越小！

但是事實上，這只是一半的故事，完整的公式如下：

哈！ 其實機率衰退的幅度雖然是exponentially，但是卻被epsilon^2 控制，我們一方面希望epsilon越小越好，但越小的epsilon又會減低negative exponential的威力，變成要更大的N。

此不等式稱為 Hoeffding's Inequality。

上面實驗與Machine learning關係？

其實很好類推。
我們要找出未知miu，相當於就是learning中要找出那個ideal target function，現在不是一個常數了，而是一個input vector mapping to output value的 UNKNOWN function:

不過上面的實驗中，桶子內的球抽出是呈現機率分布的，所以原本的learning diagram可以擴充如下：

用這個桶子的類比，桶子就是整個input space，每一個球就是input space中的特定一點。
如果把桶子內的球假設根據我們選的hypothesis function h來上色，如果h(x)和f(x)一致，則上綠色，反之上紅色，則對input space中所有的點來說，不同的h會把同一個input space中的所有點畫出不同的顏色：

所以每一個h其實都類比為對桶子內紅球頻率miu的猜測，透過sampling用nu來逼近或是說infer miu，這邊受惠於Hoeffing's Inequality，所以我們不需要真的知道miu（廢話）就能透過nu infer miu。

這些hypothesis組成了hypothesis set，learning過程其實就是一一比對這些hypothesis，看哪一組sampling最好。所謂的好當然就是紅球越少的越好，因為我們上色的根據是h(x) != f(x)的話，上紅色。不過這邊有個疑問，我們不知道f，要怎麼比對？

這就要用到Hoeffding's Inequality，見下段。

In sample performance and out of sample performance

這個從桶子裡面sampling的動作，其中紅球比例nu，其實在learning過程中實際上就是h判斷錯誤的比例，類比成in sample performance (error) E_in(h):

Hoeffding's Inequality可以改寫如下：

所以我們不需要知道f(x)，只要知道in sample error以及epsilon就能知道這個in sample error與out of sample error被bound在某個跟f(x)無關的數字，這樣就能知道h(x)的好壞。

Hoeffding's Inequality不適用於多次sampling

擲一個銅板10次 （相當從桶子中於做一次sampling)，全部都是 head的機率  = 0.5^10 ~= 0.1%

但是1000個銅板，一樣每個擲10次，出現至少一次全部是head的機率?
對每個銅板來說，擲出10個head的機率 = 0.5^10，所以擲不出10個head的機率 = 1-0.5^10
做了1000次（1000個銅板相當於1000次independent實驗）都擲不出10個head的機率 = (1-0.5^10)^1000

所以至少出現一次10個head的機率為 1 - (1 - 0.5^10)^1000 = 62.3%

做了一千次，至少有一次拿到滿分！！！！這就是機率的描述，做大量嘗試總會有一次狗屎運成功。

Hoeffding's Inequality只對任何一次sampling成立，如果是大量嘗試sampling，則需要修正如下：

假設我們最後挑選出的final hypothesis g，它的Hoefdding's Inequality一定小於等於其他hpothesis的Hoefdding's Inequality，所以worst case bounded by sum of all others:

簡單化減後：

這邊的intuition是：M越大代表你的model越複雜，結果反而in sample error跟out of sample error差距的可能性越大，似乎是指overfitting的問題？
靜待下回分解。