機器學習方法:迴歸(一):線性迴歸Linear regression

歡迎轉載,轉載請註明:本文出自Bin的專欄blog.csdn.net/xbinworld

開一個機器學習方法科普系列:做基礎回顧之用,學而時習之;也拿出來與大家分享。數學水平有限,只求易懂,學習與工作夠用。週期會比較長,因為我還想寫一些其他的,呵呵。

content:
linear regression, Ridge, Lasso
Logistic Regression, Softmax
Kmeans, GMM, EM, Spectral Clustering
Dimensionality Reduction: PCA、LDA、Laplacian Eigenmap、 LLE、 Isomap(修改前面的blog)
SVM
ID3、C4.5
Apriori,FP
PageRank
minHash, LSH
Manifold Ranking,EMR
待補充

開始幾篇將詳細介紹一下線性迴歸linear regression,以及加上L1和L2的正則的變化。後面的文章將介紹邏輯迴歸logistic regression,以及Softmax regression。為什麼要先講這幾個方法呢?因為它們是機器學習/深度學習的基石(building block)之一,而且在大量教學視訊和教材中反覆被提到,所以我也記錄一下自己的理解,方便以後翻閱。這三個方法都是有監督的學習方法,線性迴歸是迴歸演算法,而邏輯迴歸和softmax本質上是分類演算法(從離散的分類目標匯出),不過有一些場合下也有混著用的——如果目標輸出值的取值範圍和logistic的輸出取值範圍一致。

ok,廢話不多說。

1、Linear Regression

可以說基本上是機器學習中最簡單的模型了,但是實際上其地位很重要(計算簡單、效果不錯,在很多其他演算法中也可以看到用LR作為一部分)。

先來看一個小例子,給一個“線性迴歸是什麼”的概念。圖來自[2]。

這裡寫圖片描述這裡寫圖片描述
假設有一個房屋銷售的資料如下:
面積(m^2) 銷售價錢(萬元)
123 250
150 320
87 160
102 220
… …

當我們有很多組這樣的資料,這些就是訓練資料,我們希望學習一個模型,當新來一個面積資料時,可以自動預測出銷售價格(也就是上右圖中的綠線);這樣的模型必然有很多,其中最簡單最樸素的方法就是線性迴歸,也就是我們希望學習到一個線性模型(上右圖中的紅線)。不過說是線性迴歸,學出來的不一定是一條直線,只有在變數x是一維的時候才是直線,高維的時候是超平面。

定義一下一些符號表達,我們通常習慣用X=(x1,x2,…,xn)T∈Rn×pX=(x_1, x_2, …,x_n)^T \in \mathbb{R}^{n\times p}表示資料矩陣,其中xi∈Rpx_i \in \mathbb{R}^p表示一個p維度長的資料樣本;y=(y1,y2,…,yn)T∈Rny=(y_1, y_2, …,y_n)^T \in \mathbb{R}^{n}表示資料的label,這裡只考慮每個樣本一類的情況。

線性迴歸的模型是這樣的,對於一個樣本xix_i,它的輸出值是其特徵的線性組合:

f(xi)=∑m=1pwmxim w0=wTxi

\begin{equation}
f(x_i) = \sum_{m=1}^{p}w_m x_{im} w_0={w}^T{x_i}
\end{equation}
其中,w0w_0稱為截距,或者bias,上式中通過增加xi0=1x_{i0}=1把w0w_0也吸收到向量表達中了,簡化了形式,因此實際上xix_i有p 1p 1維度。

線性迴歸的目標是用預測結果儘可能地擬合目標label,用最常見的Least square作為loss function:

J(w)=1n∑i=1n(yi−f(xi))2=1n∥y−Xw∥2

\begin{equation}
J(w)=\frac{1}{n}\sum_{i=1}^{n}(y_i – f(x_i))^2=\frac{1}{n}\|y-Xw\|^2
\end{equation}

從下圖來直觀理解一下線性迴歸優化的目標——圖中線段距離(平方)的平均值,也就是最小化到分割面的距離和。
這裡寫圖片描述

也就是很多中文教材中提到的最小二乘;線性迴歸是convex的目標函式,並且有解析解:

w^=(XTX)−1XTy

\begin{equation}
\hat{w}=(X^{T}X)^{-1}X^{T}y
\end{equation}
線性迴歸到這裡就訓練完成了,對每一個樣本點的預測值是f(xi)=yi^=w^Txif(x_i)=\hat{y_i}=\hat{w}^{T}x_i。所以:

y^=Xw^=X(XTX)−1XTy

\begin{equation}
\hat{y} = X\hat{w} = X(X^{T}X)^{-1}X^{T}y
\end{equation}

接下來看一下我們尋找到的預測值的一個幾何解釋:從上面的解析解w^=(XTX)−1XTy\hat{w}=(X^{T}X)^{-1}X^{T}y可以得到XT(y^−y)=0X^T(\hat{y}-y)=0(垂直的向量相乘=0),因此實際上y^\hat{y}是yy在平面XX(由列向量x1\textbf{x}_1和x2\textbf{x}_2張成,假設只有兩維)上的投影。
預測值的直觀解釋

ok,一般介紹線性迴歸的文章到這裡也就結束了,因為實際使用中基本就是用到上面的結果,解析解計算簡單而且是最優解;當然如果求逆不好求的話就可以不用解析解,而是通過梯度下降等優化方法來求最優解,梯度下降的內容不在本篇中,後面講邏輯迴歸會說到。也可以看我前面寫的今天開始學PRML第5章中有寫到,或者直接翻閱wikipedia:gradient descent

不過在這裡我再稍微提幾個相關的分析,可以參考ESL[3]的第3章中的內容。前面我們對資料本身的分佈是沒有任何假設的,本節下面一小段我們假設觀察值yiy_i都是不相關的,並且方差都是σ2\sigma^2,並且樣本點是已知(且是中心化過了的,均值為0)的。於是我們可以推出協方差矩陣

Var(β^)=(XTX)−1σ2

\begin{equation}
Var(\hat{\beta}) = (X^{T}X)^{-1}\sigma^2
\end{equation}

證明:

Var(β^)=(XTX)−1XTyytX(XTX)−1=(XTX)−1σ2

\begin{equation}
Var(\hat{\beta}) = (X^{T}X)^{-1}X^{T}yy^{t}X(X^{T}X)^{-1}=(X^{T}X)^{-1}\sigma^2
\end{equation}

要估計方差σ2\sigma^2,可以用

σ^2=1n−p−1∑i=1n(yi−y^i)2

\begin{equation}
\hat{\sigma}^2=\frac{1}{n-p-1}\sum_{ i=1}^{n}(y_i-\hat{y}_i)^2
\end{equation}
這裡和一般的方差的形式看起來不同,分母是n−p−1n-p-1而不是nn,是因為這樣的估計才是σ2\sigma^2的無偏估計。
證明:

E(σ^2)=E(1n−p−1∑i=1n(yi−y^i)2)=E(1n−p−1[y−X(XTX)−1XTy]T[y−X(XTX)−1XTy])=E(1n−p−1yT[In−X(XTX)−1XT]y)=nσ2n−p−1−1n−p−1tr(X(XTX)−1XTyyT)=nσ2n−p−1−σ2n−p−1tr(X(XTX)−1XT)=nσ2n−p−1−(p 1)σ2n−p−1=σ2

\begin{equation}
\begin{array}{cc}
E(\hat{\sigma}^2)=E(\frac{1}{n-p-1}\sum_{ i=1}^{n}(y_i-\hat{y}_i)^2)\\
=E(\frac{1}{n-p-1}[y-X(X^{T}X)^{-1}X^{T}y]^T[y-X(X^{T}X)^{-1}X^{T}y])\\
=E(\frac{1}{n-p-1}y^T[I_{n}-X(X^{T}X)^{-1}X^{T}]y)\\
=\frac{n\sigma^2}{n-p-1}-\frac{1}{n-p-1}\text{tr}(X(X^TX)^{-1}X^Tyy^T) \\
=\frac{n\sigma^2}{n-p-1}-\frac{\sigma^2}{n-p-1}\text{tr}(X(X^TX)^{-1}X^T) \\
=\frac{n\sigma^2}{n-p-1}-\frac{(p 1)\sigma^2}{n-p-1} \\
=\sigma^2\\
\end{array}
\end{equation}

好,第一篇就寫到這裡。這個系列是從0開始的基礎複習記錄,力求清晰易懂。下一篇lasso和ridge regression。

參考資料
[1]http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/
[2]http://www.cnblogs.com/LeftNotEasy/archive/2010/12/05/mathmatic_in_machine_learning_1_regression_and_gradient_descent.html
[3]The Elements of Statistical Learning,ch3