紅色石頭的個人網(wǎng)站：redstonewill.com

上節(jié)課，我們主要介紹了在有noise的情況下，VC Bound理論仍然是成立的。同時，介紹了不同的error measure方法。本節(jié)課介紹機(jī)器學(xué)習(xí)最常見的一種算法：Linear Regression.

一、線性回歸問題

在之前的Linear Classification課程中，講了信用卡發(fā)放的例子，利用機(jī)器學(xué)習(xí)來決定是否給用戶發(fā)放信用卡。本節(jié)課仍然引入信用卡的例子，來解決給用戶發(fā)放信用卡額度的問題，這就是一個線性回歸（Linear Regression）問題。

令用戶特征集為d維的XX，加上常數(shù)項，維度為d+1d+1，與權(quán)重ww的線性組合即為Hypothesis,記為h(x)h(x)。線性回歸的預(yù)測函數(shù)取值在整個實數(shù)空間，這跟線性分類不同。

h(x)=wTXh(x)=wTX

根據(jù)上圖，在一維或者多維空間里，線性回歸的目標(biāo)是找到一條直線（對應(yīng)一維）、一個平面（對應(yīng)二維）或者更高維的超平面，使樣本集中的點更接近它，也就是殘留誤差Residuals最小化。

一般最常用的錯誤測量方式是基于最小二乘法，其目標(biāo)是計算誤差的最小平方和對應(yīng)的權(quán)重w，即上節(jié)課介紹的squared error：

這里提一點，最小二乘法可以解決線性問題和非線性問題。線性最小二乘法的解是closed-form，即X=(ATA)?1ATyX=(ATA)?1ATy，而非線性最小二乘法沒有closed-form，通常用迭代法求解。本節(jié)課的解就是closed-form的。關(guān)于最小二乘法的一些介紹，請參見我的另一篇博文：

最小二乘法和梯度下降法的一些總結(jié)

二、線性回歸算法

樣本數(shù)據(jù)誤差EinEin是權(quán)重ww的函數(shù)，因為XX和yy都是已知的。我們的目標(biāo)就是找出合適的ww，使EinEin能夠最小。那么如何計算呢？

首先，運(yùn)用矩陣轉(zhuǎn)換的思想，將EinEin計算轉(zhuǎn)換為矩陣的形式。

然后，對于此類線性回歸問題，Ein(w)Ein(w)一般是個凸函數(shù)。凸函數(shù)的話，我們只要找到一階導(dǎo)數(shù)等于零的位置，就找到了最優(yōu)解。那么，我們將EwEw對每個wi,i=0,1,?,dwi,i=0,1,?,d求偏導(dǎo)，偏導(dǎo)為零的wiwi，即為最優(yōu)化的權(quán)重值分布。

根據(jù)梯度的思想，對EwEw進(jìn)行矩陣話求偏導(dǎo)處理：

令偏導(dǎo)為零，最終可以計算出權(quán)重向量ww為：

最終，我們推導(dǎo)得到了權(quán)重向量w=(XTX)?1XTyw=(XTX)?1XTy，這是上文提到的closed-form解。其中，(XTX)?1XT(XTX)?1XT又稱為偽逆矩陣pseudo-inverse，記為X+X+，維度是(d+1)xN。

但是，我們注意到，偽逆矩陣中有逆矩陣的計算，逆矩陣(XTX)?1(XTX)?1是否一定存在？一般情況下，只要滿足樣本數(shù)量N遠(yuǎn)大于樣本特征維度d+1，就能保證矩陣的逆是存在的，稱之為非奇異矩陣。但是如果是奇異矩陣，不可逆怎么辦呢？其實，大部分的計算逆矩陣的軟件程序，都可以處理這個問題，也會計算出一個逆矩陣。所以，一般偽逆矩陣是可解的。

三、泛化問題

現(xiàn)在，可能有這樣一個疑問，就是這種求解權(quán)重向量的方法是機(jī)器學(xué)習(xí)嗎？或者說這種方法滿足我們之前推導(dǎo)VC Bound，即是否泛化能力強(qiáng)Ein≈EoutEin≈Eout？

有兩種觀點：1、這不屬于機(jī)器學(xué)習(xí)范疇。因為這種closed-form解的形式跟一般的機(jī)器學(xué)習(xí)算法不一樣，而且在計算最小化誤差的過程中沒有用到迭代。2、這屬于機(jī)器學(xué)習(xí)范疇。因為從結(jié)果上看，EinEin和EoutEout都實現(xiàn)了最小化，而且實際上在計算逆矩陣的過程中，也用到了迭代。

其實，只從結(jié)果來看，這種方法的確實現(xiàn)了機(jī)器學(xué)習(xí)的目的。下面通過介紹一種更簡單的方法，證明linear regression問題是可以通過線下最小二乘法方法計算得到好的EinEin和EoutEout的。

首先，我們根據(jù)平均誤差的思想，把Ein(wLIN)Ein(wLIN)寫成如圖的形式，經(jīng)過變換得到:

Ein(wLIN)=1N||(I?XX+)y||2=1N||(I?H)y||2Ein(wLIN)=1N||(I?XX+)y||2=1N||(I?H)y||2

我們稱XX+XX+為帽子矩陣，用H表示。

下面從幾何圖形的角度來介紹帽子矩陣H的物理意義。

圖中，y是N維空間的一個向量，粉色區(qū)域表示輸入矩陣X乘以不同權(quán)值向量w所構(gòu)成的空間，根據(jù)所有w的取值，預(yù)測輸出都被限定在粉色的空間中。向量y^y^就是粉色空間中的一個向量，代表預(yù)測的一種。y是實際樣本數(shù)據(jù)輸出值。

機(jī)器學(xué)習(xí)的目的是在粉色空間中找到一個y^y^，使它最接近真實的y，那么我們只要將y在粉色空間上作垂直投影即可，投影得到的y^y^即為在粉色空間內(nèi)最接近y的向量。這樣即使平均誤差EˉˉˉˉEˉ最小。

從圖中可以看出，y^y^是y的投影，已知y^=Hyy^=Hy，那么H表示的就是將y投影到y^y^的一種操作。圖中綠色的箭頭y?y^y?y^是向量y與y^y^相減，y?y^y?y^垂直于粉色區(qū)域。已知(I?H)y=y?y^(I?H)y=y?y^那么I-H表示的就是將y投影到y?y^y?y^即垂直于粉色區(qū)域的一種操作。這樣的話，我們就賦予了H和I-H不同但又有聯(lián)系的物理意義。

這里trace(I-H)稱為I-H的跡，值為N-(d+1)。這條性質(zhì)很重要，一個矩陣的 trace等于該矩陣的所有特征值(Eigenvalues)之和。下面給出簡單證明：

trace(I?H)=trace(I)?trace(H)trace(I?H)=trace(I)?trace(H)
=N?trace(XX+)=N?trace(X(XTX)?1XT=N?trace(XX+)=N?trace(X(XTX)?1XT
=N?trace(XTX(XTX)?1)=N?trace(Id+1)=N?trace(XTX(XTX)?1)=N?trace(Id+1)
=N?(d+1)=N?(d+1)

介紹下該I-H這種轉(zhuǎn)換的物理意義：原來有一個有N個自由度的向量y，投影到一個有d+1維的空間x（代表一列的自由度，即單一輸入樣本的參數(shù)，如圖中粉色區(qū)域），而余數(shù)剩余的自由度最大只有N-(d+1)種。

在存在noise的情況下，上圖變?yōu)?#xff1a;

圖中，粉色空間的紅色箭頭是目標(biāo)函數(shù)f(x)，虛線箭頭是noise，可見，真實樣本輸出y由f(x)和noise相加得到。由上面推導(dǎo)，已知向量y經(jīng)過I-H轉(zhuǎn)換為y?y^y?y^，而noise與y是線性變換關(guān)系，那么根據(jù)線性函數(shù)知識，我們推導(dǎo)出noise經(jīng)過I-H也能轉(zhuǎn)換為y?y^y?y^。則對于樣本平均誤差，有下列推導(dǎo)成立：

Ein(wLIN)=1N||y?y^||2=1N||(I?H)noise||2=1N(N?(d+1))||noise||2Ein(wLIN)=1N||y?y^||2=1N||(I?H)noise||2=1N(N?(d+1))||noise||2

即

Eˉˉˉˉin=noiselevel?(1?d+1N)Eˉin=noiselevel?(1?d+1N)

同樣，對EoutEout有如下結(jié)論：

Eˉˉˉˉout=noiselevel?(1+d+1N)Eˉout=noiselevel?(1+d+1N)

這個證明有點復(fù)雜，但是我們可以這樣理解：EˉˉˉˉinEˉin與EˉˉˉˉoutEˉout形式上只差了(d+1)N(d+1)N項，從哲學(xué)上來說，EˉˉˉˉinEˉin是我們看得到的樣本的平均誤差，如果有noise，我們把預(yù)測往noise那邊偏一點，讓EˉˉˉˉinEˉin好看一點點，所以減去(d+1)N(d+1)N項。那么同時，新的樣本EˉˉˉˉoutEˉout是我們看不到的，如果noise在反方向，那么EˉˉˉˉoutEˉout就應(yīng)該加上(d+1)N(d+1)N項。

我們把EˉˉˉˉinEˉin與EˉˉˉˉoutEˉout畫出來，得到學(xué)習(xí)曲線：

當(dāng)N足夠大時，EˉˉˉˉinEˉin與EˉˉˉˉoutEˉout逐漸接近，滿足Eˉˉˉˉin≈EˉˉˉˉoutEˉin≈Eˉout，且數(shù)值保持在noise level。這就類似VC理論，證明了當(dāng)N足夠大的時候，這種線性最小二乘法是可以進(jìn)行機(jī)器學(xué)習(xí)的，算法有效！

四、Linear Regression方法解決Linear Classification問題

之前介紹的Linear Classification問題使用的Error Measure方法用的是0/1 error，那么Linear Regression的squared error是否能夠應(yīng)用到Linear Classification問題？

下圖展示了兩種錯誤的關(guān)系，一般情況下，squared error曲線在0/1 error曲線之上。即err0/1≤errsqrerr0/1≤errsqr.

根據(jù)之前的VC理論，EoutEout的上界滿足：

從圖中可以看出，用errsqrerrsqr代替err0/1err0/1，EoutEout仍然有上界，只不過是上界變得寬松了。也就是說用線性回歸方法仍然可以解決線性分類問題，效果不會太差。二元分類問題得到了一個更寬松的上界，但是也是一種更有效率的求解方式。

五、總結(jié)

本節(jié)課，我們主要介紹了Linear Regression。首先，我們從問題出發(fā)，想要找到一條直線擬合實際數(shù)據(jù)值；然后，我們利用最小二乘法，用解析形式推導(dǎo)了權(quán)重w的closed-form解；接著，用圖形的形式得到Eout?Ein≈2(N+1)NEout?Ein≈2(N+1)N，證明了linear regression是可以進(jìn)行機(jī)器學(xué)習(xí)的，；最后，我們證明linear regressin這種方法可以用在binary classification上，雖然上界變寬松了，但是仍然能得到不錯的學(xué)習(xí)方法。

注明：

文章中所有的圖片均來自臺灣大學(xué)林軒田《機(jī)器學(xué)習(xí)基石》課程

關(guān)注公眾號并輸入關(guān)鍵字“jspdf”獲得該筆記的pdf文件哦～

更多AI資源請關(guān)注公眾號：紅色石頭的機(jī)器學(xué)習(xí)之路（ID：redstonewill）

總結(jié)

以上是生活随笔為你收集整理的台湾大学林轩田机器学习基石课程学习笔记9 -- Linear Regression的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。