上節課，我們主要介紹了在有noise的情況下，VC Bound理論仍然是成立的。同時，介紹了不同的error measure方法。本節課介紹機器學習最常見的一種算法：Linear Regression。
一、線性回歸問題在之前的Linear Classification課程中，講了信用卡發放的例子，利用機器學習來決定是否給用戶發放信用卡。本節課仍然引入信用卡的例子，來解決給用戶發放信用卡額度的問題，這就是一個線性回歸（Linear Regression）問題。
令用戶特徵集為d維的X，加上常數項，維度為d+1與權重w的線性組合即為Hypothesis,記為h(x)。線性回歸的預測函數取值在整個實數空間，這跟線性分類不同。
根據上圖，在一維或者多維空間裡，線性回歸的目標是找到一條直線（對應一維）、一個平面（對應二維）或者更高維的超平面，使樣本集中的點更接近它，也就是殘留誤差Residuals最小化。
一般最常用的錯誤測量方式是基於最小二乘法，其目標是計算誤差的最小平方和對應的權重w，即上節課介紹的squared error：
二、線性回歸算法樣本數據誤差Ein是權重w的函數，因為X和y都是已知的。我們的目標就是找出合適的w，使Ein能夠最小。那麼如何計算呢？
首先，運用矩陣轉換的思想，將Ein計算轉換為矩陣的形式。
然後，對於此類線性回歸問題，Ein(w)一般是個凸函數。凸函數的話，我們只要找到一階導數等於零的位置，就找到了最優解。那麼，我們將Ew對每個wi,i=0,1,⋯,d求偏導，偏導為零的wi，即為最優化的權重值分布。
根據梯度的思想，對Ew進行矩陣話求偏導處理：
令偏導為零，最終可以計算出權重向量w為：
三、泛化問題現在，可能有這樣一個疑問，就是這種求解權重向量的方法是機器學習嗎？或者說這種方法滿足我們之前推導VC Bound，即是否泛化能力強Ein≈Eout？
有兩種觀點：1、這不屬於機器學習範疇。因為這種closed-form解的形式跟一般的機器學習算法不一樣，而且在計算最小化誤差的過程中沒有用到迭代。2、這屬於機器學習範疇。因為從結果上看，Ein和Eout都實現了最小化，而且實際上在計算逆矩陣的過程中，也用到了迭代。
其實，只從結果來看，這種方法的確實現了機器學習的目的。下面通過介紹一種更簡單的方法，證明linear regression問題是可以通過線下最小二乘法方法計算得到好的Ein和Eout的。
首先，我們根據平均誤差的思想，把Ein(wLIN)寫成如圖的形式，經過變換得到:
下面從幾何圖形的角度來介紹帽子矩陣H的物理意義。
圖中，y是N維空間的一個向量，粉色區域表示輸入矩陣X乘以不同權值向量w所構成的空間，根據所有w的取值，預測輸出都被限定在粉色的空間中。向量y^就是粉色空間中的一個向量，代表預測的一種。y是實際樣本數據輸出值。
機器學習的目的是在粉色空間中找到一個y^，使它最接近真實的y，那麼我們只要將y在粉色空間上作垂直投影即可，投影得到的y^即為在粉色空間內最接近y的向量。這樣即使平均誤差E¯最小。
從圖中可以看出，y^是y的投影，已知y^=Hy，那麼H表示的就是將y投影到y^的一種操作。圖中綠色的箭頭y-y^是向量y與y^相減，y−y^垂直於粉色區域。已知(I−H)y=y−y^那麼I-H表示的就是將y投影到y-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轉換為y−y^，而noise與y是線性變換關係，那麼根據線性函數知識，我們推導出noise經過I-H也能轉換為y−y^。則對於樣本平均誤差，有下列推導成立：
即
同樣，對EoutEout有如下結論：
我們把E¯in與E¯out畫出來，得到學習曲線：
當N足夠大時，E¯in與E¯out逐漸接近，滿足E¯in≈E¯out，且數值保持在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理論，Eout的上界滿足：
從圖中可以看出，用代替，Eout仍然有上界，只不過是上界變得寬鬆了。也就是說用線性回歸方法仍然可以解決線性分類問題，效果不會太差。二元分類問題得到了一個更寬鬆的上界，但是也是一種更有效率的求解方式。
五、總結本節課，我們主要介紹了Linear Regression。首先，我們從問題出發，想要找到一條直線擬合實際數據值；然後，我們利用最小二乘法，用解析形式推導了權重w的closed-form解；接著，用圖形的形式得到，證明了linear regression是可以進行機器學習的，；最後，我們證明linear regressin這種方法可以用在binary classification上，雖然上界變寬鬆了，但是仍然能得到不錯的學習方法。
歡迎關注公眾號學習交流～