# 9 -- Linear Regression 上節課，我們主要介紹了在有noise的情況下，VC Bound理論仍然是成立的。同時，介紹了不同的error measure方法。本節課介紹機器學習最常見的一種算法：Linear Regression. ### **一、線性回歸問題** 在之前的Linear Classification課程中，講了信用卡發放的例子，利用機器學習來決定是否給用戶發放信用卡。本節課仍然引入信用卡的例子，來解決給用戶發放信用卡額度的問題，這就是一個線性回歸（Linear Regression）問題。  令用戶特征集為d維的，加上常數項，維度為，與權重的線性組合即為Hypothesis,記為。線性回歸的預測函數取值在整個實數空間，這跟線性分類不同。  根據上圖，在一維或者多維空間里，線性回歸的目標是找到一條直線（對應一維）、一個平面（對應二維）或者更高維的超平面，使樣本集中的點更接近它，也就是殘留誤差Residuals最小化。 一般最常用的錯誤測量方式是基于最小二乘法，其目標是計算誤差的最小平方和對應的權重w，即上節課介紹的squared error：  這里提一點，最小二乘法可以解決線性問題和非線性問題。線性最小二乘法的解是closed-form，即，而非線性最小二乘法沒有closed-form，通常用迭代法求解。本節課的解就是closed-form的。關于最小二乘法的一些介紹，請參見我的另一篇博文： [最小二乘法和梯度下降法的一些總結](http://blog.csdn.net/red_stone1/article/details/70306403) ### **二、線性回歸算法** 樣本數據誤差是權重的函數，因為和都是已知的。我們的目標就是找出合適的，使能夠最小。那么如何計算呢？ 首先，運用矩陣轉換的思想，將計算轉換為矩陣的形式。  然后，對于此類線性回歸問題，一般是個凸函數。凸函數的話，我們只要找到一階導數等于零的位置，就找到了最優解。那么，我們將對每個求偏導，偏導為零的，即為最優化的權重值分布。  根據梯度的思想，對進行矩陣話求偏導處理：  令偏導為零，最終可以計算出權重向量為：  最終，我們推導得到了權重向量，這是上文提到的closed-form解。其中，又稱為偽逆矩陣pseudo-inverse，記為，維度是(d+1)xN。 但是，我們注意到，偽逆矩陣中有逆矩陣的計算，逆矩陣是否一定存在？一般情況下，只要滿足樣本數量N遠大于樣本特征維度d+1，就能保證矩陣的逆是存在的，稱之為非奇異矩陣。但是如果是奇異矩陣，不可逆怎么辦呢？其實，大部分的計算逆矩陣的軟件程序，都可以處理這個問題，也會計算出一個逆矩陣。所以，一般偽逆矩陣是可解的。 ### **三、泛化問題** 現在，可能有這樣一個疑問，就是這種求解權重向量的方法是機器學習嗎？或者說這種方法滿足我們之前推導VC Bound，即是否泛化能力強？  有兩種觀點：1、這不屬于機器學習范疇。因為這種closed-form解的形式跟一般的機器學習算法不一樣，而且在計算最小化誤差的過程中沒有用到迭代。2、這屬于機器學習范疇。因為從結果上看，和都實現了最小化，而且實際上在計算逆矩陣的過程中，也用到了迭代。 其實，只從結果來看，這種方法的確實現了機器學習的目的。下面通過介紹一種更簡單的方法，證明linear regression問題是可以通過線下最小二乘法方法計算得到好的和的。  首先，我們根據平均誤差的思想，把寫成如圖的形式，經過變換得到: 我們稱為帽子矩陣，用H表示。 下面從幾何圖形的角度來介紹帽子矩陣H的物理意義。  圖中，y是N維空間的一個向量，粉色區域表示輸入矩陣X乘以不同權值向量w所構成的空間，根據所有w的取值，預測輸出都被限定在粉色的空間中。向量就是粉色空間中的一個向量，代表預測的一種。y是實際樣本數據輸出值。 機器學習的目的是在粉色空間中找到一個，使它最接近真實的y，那么我們只要將y在粉色空間上作垂直投影即可，投影得到的即為在粉色空間內最接近y的向量。這樣即使平均誤差最小。 從圖中可以看出，是y的投影，已知，那么H表示的就是將y投影到的一種操作。圖中綠色的箭頭是向量y與相減，垂直于粉色區域。已知那么I-H表示的就是將y投影到即垂直于粉色區域的一種操作。這樣的話，我們就賦予了H和I-H不同但又有聯系的物理意義。 這里trace(I-H)稱為I-H的跡，值為N-(d+1)。這條性質很重要，一個矩陣的 trace等于該矩陣的所有特征值(Eigenvalues)之和。下面給出簡單證明：     介紹下該I-H這種轉換的物理意義：原來有一個有N個自由度的向量y，投影到一個有d+1維的空間x（代表一列的自由度，即單一輸入樣本的參數，如圖中粉色區域），而余數剩余的自由度最大只有N-(d+1)種。 在存在noise的情況下，上圖變為：  圖中，粉色空間的紅色箭頭是目標函數f(x)，虛線箭頭是noise，可見，真實樣本輸出y由f(x)和noise相加得到。由上面推導，已知向量y經過I-H轉換為，而noise與y是線性變換關系，那么根據線性函數知識，我們推導出noise經過I-H也能轉換為。則對于樣本平均誤差，有下列推導成立： 即 同樣，對有如下結論： 這個證明有點復雜，但是我們可以這樣理解：與形式上只差了項，從哲學上來說，是我們看得到的樣本的平均誤差，如果有noise，我們把預測往noise那邊偏一點，讓好看一點點，所以減去項。那么同時，新的樣本是我們看不到的，如果noise在反方向，那么就應該加上項。 我們把與畫出來，得到學習曲線：  當N足夠大時，與逐漸接近，滿足，且數值保持在noise level。這就類似VC理論，證明了當N足夠大的時候，這種線性最小二乘法是可以進行機器學習的，算法有效！ ### **四、Linear Regression方法解決Linear Classification問題** 之前介紹的Linear Classification問題使用的Error Measure方法用的是0/1 error，那么Linear Regression的squared error是否能夠應用到Linear Classification問題？  下圖展示了兩種錯誤的關系，一般情況下，squared error曲線在0/1 error曲線之上。即.  根據之前的VC理論，的上界滿足：  從圖中可以看出，用代替，仍然有上界，只不過是上界變得寬松了。也就是說用線性回歸方法仍然可以解決線性分類問題，效果不會太差。二元分類問題得到了一個更寬松的上界，但是也是一種更有效率的求解方式。 ### **五、總結** 本節課，我們主要介紹了Linear Regression。首先，我們從問題出發，想要找到一條直線擬合實際數據值；然后，我們利用最小二乘法，用解析形式推導了權重w的closed-form解；接著，用圖形的形式得到，證明了linear regression是可以進行機器學習的，；最后，我們證明linear regressin這種方法可以用在binary classification上，雖然上界變寬松了，但是仍然能得到不錯的學習方法。 **_注明：_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程