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 性能與體驗更好，不過價格就是貴！