這邊的章節推導等，會使用到大量的線性代數
可以以 MIT 的 Linear Algebra, Spring 2005 OCW 來作複習教材
------------------------------------------------------------------------------------------------------------
[Youtube 影片34 Linear Regression :: Linear Regression Problem]
前情回顧，學習可以在低 Ein 與 err 的情況，與有著目標分布的情況下進行
VC Bound 也能夠應用在不同的 error measure 上，也能夠應用在有noise的數據上
圖一、前情題要
今天如果已經分類完之後，不需要再考慮客戶是否具備發卡資格(不再是是非題了)
轉而我們想要知道要給某個顧客"多少"信用額度
而我們的 Target function 是一個能夠輸出實數的式子，並且是正的實數
在這邊我們的輸出可以使用迴歸(Regression)分析[1]
實際上Regression輸出空間就是整個實數
圖二、信用卡額度上限問題
那學習演算法該如何進行 ?
與前一個學習筆記20的內容類似
一樣是透過加權的方式算出一個分數，並以該分數來作為評斷依據
我們現在想要的就是這個實數與我們想要的值能夠越接近越好
和先前一樣，在原來的資料加上一個常數項 x0，使得式子能夠以 sigma 表示
圖三、線性迴歸假說
x對應的是實數, y對應的是輸出結果
2D平面上，我們希望得到的這個線，與數據點 o 越接近越好
3D 立體空間上， 一樣希望得到一個平面，與這些數據點 o 越接近越好
同時餘數誤差(residual)越小越好
圖四、線性迴歸圖示
該如何衡量residual是大或小 ?
這邊的衡量方式是使用前面已經學習過的 squared error來進行計算 (採用原因請看統計學)
同樣分成 in-sample 與 out-of-sample 的計算方法，同時可能會有noise在我們的輸入輸出中
圖五、誤差量衡量方法
圖六、In-sample、Out-of-sanple誤差衡量方式
如何將 Ein(w)最小化 ? 如果能夠將Ein(w)變到最小，就可能可以進行機器學習
之後的影片中將會告訴我們如何辦到這件事
圖七、如何最小化Ein(w)
課後練習
Ans: 概念不難，邏輯上收入越高者，環款能力越好，可以給予的信用額度便越高
------------------------------------------------------------------------------------------------------------
[Youtube 影片35 Linear Regression :: Linear Regression :: Linear Regression Algorithm]
為了將整體的Ein算式能夠最簡潔的表達出來，在這邊決定以矩陣的方式進行表達
以下為推導過程：
圖八、Ein(w)矩陣形式
因此，Ein(w)的式子可以轉變成圖八最後的式子
本節的任務就是求得圖九中所說的 min Ein(w)
圖九、Ein 最小值
Ein(w)是一個連續可微分的凸函數 (convex)，存在最小值
這個最小值是凸函數的谷底，也就是最低點的地方，梯度是零(不能夠再往下滾, 即roll down)
我們的任務就是找到合適的 w，使得 Ein(w) 微分為零，便能夠求得Ein(w)的最小值
( 這邊先不考慮局部最小跟全域最小的問題 )
圖十、convex
圖十一列出了Ein(w)的梯度公式，並將它展開，得到主要三項，w的2次式、1次式與常數項
圖十一、Ein(w)的梯度公式
若從一個維度開始推導，相當於將w的2次式進行微分，微分後的結果相當簡單
同樣的，改成對線性代數的部分進行微分
可以發現，即使以矩陣形式來進行表達，從結果來看，其實形式是一樣的
圖十二、線性代數分析
我們的任務只有一個，就是找到合適的w，使得 Ein 的梯度為零，即可得到最小值
圖十三、線性迴歸最佳化的任務
若以psuedo inverse進行運算，可以求得w反矩陣，便能找到唯一解
大部分的情形，通常在資料數N遠大於 d+1的情況可以成立
若有很多組解的情況，便有很多種求解方法
從線性代數或是數值領域，可以知道常用的方法為何
若有現有的函式庫的話，老師建議直接使用
畢竟其他程式撰寫者已經最佳化了，我們不用重複做相同的任務
圖十四、可逆、奇異矩陣
在這邊終於將輸入X與輸出Y進行一個分拆，透過計算psuedo-inverse
我們可以得到線性迴歸的解 !
圖十五、線性迴歸演算法
透過線性代數這個強大的工具，可以輕易且有效的延伸到多維的空間
圖十六、good routine
課後練習
Ans:
推導不出來y head = XWLin這個式子...
------------------------------------------------------------------------------------------------------------
[Youtube 影片36 Linear Regression :: ]
請問 : 線性迴歸 (Linear Rregression) 真的是機器學習嗎???
No = > 就像是一個一步可以求出(instantaneos)的公式化 (Closed-form) 答案
Yes => 從某些角度上，線性迴歸可以說是機器學習的演算法
因為它可以求得最佳化的Ein，同時也有好的Eout
同時透過 Psuedo inverse 就可以算出來，每次隨著 Psuedo inverse 的解而不斷進步
但實際上，求 Psuedo inverse 需要迭代好幾次
只是我們不知道程式在計算過程中發生什麼事情
只要最後的Eout(WLin)結果很不錯，那麼就有學習!
圖十七、
現在來求，抓一把起來之後的資料平均的Ein (Ein上面加一橫的符號)
它又稱作 noise level ，d+1是我們的自由度，N是我們的資料量
利用線性迴歸的特性，將下面的結果推出來 (完整的證明過程並沒有詳細說明)
y hat 是我們的預測結果，從前一講的課後練習可以知道 y hat = X(Xhat)y
統計學家稱XXhat 叫作帽子矩陣 (Hat Matrix)
圖十八、
線性代數 帽子矩陣 Hat Matrix
y是一個在N維空間的向量(y1~yn)
要預測y hat，先讓 y hat 在做線性迴歸前，以X 乘上一個任意的向量W，
將每一個 X 的 column作線性組合，展開(span)成一個空間
而y hat就在該空間中(如圖 紅色區域)
我們希望 y 與 y hat 差異越小越好，
H 是y投影到 y hat 的矩陣
trace是指對角線上的值
----------------------------------------
線性代數知識小補充
同學 :
老師您好
想請問一下在15頁裡為什麼這邊要特別用trace(I-H)來代表residual呢?
因為I-H會投影到span(X)的正交補空間
那麼用rank不是會比較有幾何意義嗎?
還是說trace在後面會有其他運用呢?
林老師回覆 : 在這個例子裡面，建議可以去推導一下，Rank 和 Trace 是有很強的關係
同學 :
推完才想起來投影矩陣對角化的形式會得出rank=trace
圖十九、
理想的target function會落在 X 所展開的區域
因此，我們真正看到的 label 就是目標函數加上 noise 向量 (即y - yhat)
noise 就能夠由 (y-yhat) 轉變成 (I-H)
因此，Ein 與 Eout 的平均就能夠順利得到，如圖二十所示
圖二十、
有多少資料量，Ein 和 Eout 平均值的曲線圖 (VC Bound中的曲線不是平均)
如果資料筆數很大的情況底下，Ein 與 Eout 會收驗到 sigma 的平方
平均的error值會是 2(d+1)/N
圖二十一、
從這邊推導的結果，以及前面推導VC Dimension的結果
我們有理由相信，在noise不大的情況底下，線性迴歸是學習演算法
圖二十二、
選項1，H是對稱的
以下兩個選項可以透過證明得到
? 選項2，做了兩次投影，投影到相同的空間裡面
? 選項3，兩次轉換取餘數與一次轉換取餘數是一樣的
[Youtube 影片37 Linear Regression :: ]
線性分類 vs 線性迴歸
NP-hard (non-deterministic polynomial-time hard) 名詞小解釋 [2]
線性分類 與 線性迴歸 的不同地方在於，它的輸出空間直接是實數，不再是 +1 與 -1
假設的輸出結果是wTx，錯誤量的衡量是(y hat - y)的平方
它是屬於有效率的分析解
圖二十三、
線性迴歸真的能夠這麼快速的把結果算出來嗎? 如何從數學的角度來證明這件事情?
圖二十四、
我們從圖形化的角度來比較兩個不同 error 運算方法之間的差異
可以知道 err 0/1 ≦ err sqr
圖二十五、
從VC Dimension中，可以得到圖二十六的第一個不等式
在從剛剛上面的結論，我們就可以得到第二個不等式
由於err 0/1並不好解，所以我們換成 err sqr，因此我們的err hat是採用 err sqr
以寬鬆一點的Bound，比較容易得找到想要的解
因此，可以先用線性迴歸先取得 WLin 來當作PLA 或 pocket 演算法的初始參數 w0
來加速PLA演算法
圖二十六、
課後練習
Ans:
? 畫圖出來可以得到這題的答案。
這三個答案選項都是機器學習中很重要的上限，之後會針對這個部分進行介紹
總結
介紹了線性迴歸的演算法，以解析的方式求得了線性迴歸的解
同時，新的Eout - Ein 大約等於 2(d+1) / N (d= 維度, N = 資料量)
線性迴歸之後會拿來用在二元分類問題上面，敬請期待 : P
圖二十七、總結
------------------------------------------------------------------------------------------------------------
PS. 如果要打方程式，似乎以 Gitbook 做記錄更好
[1] 演算法筆記 - 迴歸分析
[2] 論P,NP, NP-hard, NP-complete問題
沒有留言:
張貼留言