# 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上,雖然上界變寬松了,但是仍然能得到不錯的學習方法。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale