機器學習方法:迴歸(二):稀疏與正則約束ridge regression,Lasso

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

“機器學習方法“系列,我本著開放與共享(open and share)的精神撰寫,目的是讓更多的人瞭解機器學習的概念,理解其原理,學會應用。希望與志同道合的朋友一起交流,我剛剛設立了了一個技術交流QQ群:433250724,歡迎對演算法、技術、應用感興趣的同學加入,在交流中拉通——演算法與技術,讓理論研究與實際應用深度融合;也希望能有大牛能來,為大家解惑授業,福澤大眾。推廣開放與共享的精神。如果人多我就組織一些讀書會,線下交流。

本節的內容需要依賴上一節已經講了的機器學習:概念到理解(一):線性迴歸,線性迴歸的模型是這樣的,對於一個樣本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}
可以直接求出最優解:

w∗=(XTX)−1XTy

\begin{equation}
w^*=(X^{T}X)^{-1}X^{T}y
\end{equation}
看起來似乎很簡單,但是在實際使用的過程中會有不少問題,其中一個主要問題就是上面的協方差矩陣不可逆時,目標函式最小化導數為零時方程有無窮解,沒辦法求出最優解。尤其在p>np>n時,必然存在這樣的問題,這個時候也存在overfitting的問題。這個時候需要對ww做一些限制,使得它的最優解空間變小,也就是所謂的regularization,正則。

ridge regression

最為常見的就是對ww的模做約束,如ridge regression,嶺迴歸,就是線上性迴歸的基礎上加上l2l_2-norm的約束,loss function是(習慣上一般會去掉前面線性迴歸目標函式中的常數項1n\frac{1}{n},同時為了後面推導的簡潔性會加上一個12\frac{1}{2}):

JR(w)=12∥y−Xw∥2 λ2∥w∥2

\begin{equation}
J_R(w)=\frac{1}{2}\|y-Xw\|^2 \frac{\lambda}{2}\|w\|^2
\end{equation}
有解析解:

w^R=(XTX λI)−1XTy

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

其中λ>0\lambda >0是一個引數,有了正則項以後解就有了很好的性質,首先是對ww的模做約束,使得它的數值會比較小,很大程度上減輕了overfitting的問題;其次是上面求逆部分肯定可以解,在實際使用中ridge regression的作用很大,通過調節引數λ\lambda,可以得到不同的迴歸模型。

實際上ridge regression可以用下面的優化目標形式表達:

minw12∥y−Xw∥2,s.t.∥w∥2<θ

\begin{equation}
\min_{w} \frac{1}{2}\|y-Xw\|^2, \quad s.t. \|w\|_2<\theta
\end{equation}
也就是說,我依然優化線性迴歸的目標,但是條件是ww的模長不能超過限制θ\theta。上面兩種優化形式是等價的,可以找到一 一對應的λ\lambda和θ\theta。

稀疏約束,Lasso

先看一下幾種正規化(norm)的定義,

∥w∥2=(∑iwi2)1/2

\begin{equation}
\|w\|_2=(\sum_{i}{w_i}^{2})^{1/2}
\end{equation}

∥w∥1=∑i|wi|

\begin{equation}
\|w\|_1=\sum_{i}|w_i|
\end{equation}

∥w∥0=∑i1(wi≠0)

\begin{equation}
\|w\|_0=\sum_i 1(w_i \neq 0)
\end{equation}
如前面的ridge regression,對ww做2正規化約束,就是把解約束在一個l2l_2-ball裡面,放縮是對球的半徑放縮,因此ww的每一個維度都在以同一個係數放縮,通過放縮不會產生稀疏的解——即某些ww的維度是0。而實際應用中,資料的維度中是存在噪音和冗餘的,稀疏的解可以找到有用的維度並且減少冗餘,提高迴歸預測的準確性和魯棒性(減少了overfitting)。在壓縮感知、稀疏編碼等非常多的機器學習模型中都需要用到稀疏約束。

稀疏約束最直觀的形式應該是約束0正規化,如上面的正規化介紹,ww的0正規化是求ww中非零元素的個數。如果約束∥w∥0≤k\|w\|_0\leq k,就是約束非零元素個數不大於k。不過很明顯,0正規化是不連續的且非凸的,如果線上性迴歸中加上0正規化的約束,就變成了一個組合優化問題:挑出≤k\leq k個係數然後做迴歸,找到目標函式的最小值對應的係陣列合,是一個NP問題。

有趣的是,l1l_1-norm(1正規化)也可以達到稀疏的效果,是0正規化的最優凸近似,借用一張圖[1]:
L1andL0

很重要的是1正規化容易求解,並且是凸的,所以幾乎看得到稀疏約束的地方都是用的1正規化。

回到本文對於線性迴歸的討論,就引出了Lasso(least absolute shrinkage and selection operator) 的問題:

minw12∥y−Xw∥2,s.t.∥w∥1<θ

\begin{equation}
\min_{w} \frac{1}{2}\|y-Xw\|^2, \quad s.t. \|w\|_1<\theta
\end{equation}
也就是說約束在一個l1l_1-ball裡面。ridge和lasso的效果見下圖:

lasso

紅色的橢圓和藍色的區域的切點就是目標函式的最優解,我們可以看到,如果是圓,則很容易切到圓周的任意一點,但是很難切到座標軸上,因此沒有稀疏;但是如果是菱形或者多邊形,則很容易切到座標軸上,因此很容易產生稀疏的結果。這也說明了為什麼1正規化會是稀疏的。

Lasso稀疏性的進一步理解:

類似Ridge,我們也可以寫出Lasso的優化目標函式:

JL(w)=12∥y−Xw∥2 λ∑i|wi|

\begin{equation}
J_L(w)=\frac{1}{2}\|y-Xw\|^2 \lambda\sum_{i}|w_i|
\end{equation}
根據一般的思路,我們希望對JL(w)J_L(w)求導數=0求出最優解,即▽JL(w)=0\bigtriangledown J_L(w)=0,但是l1l_1-norm在0點是連續不可導的,沒有gradient,這個時候需要subgradient:

定義1:記f:U→Rf:U→ R是一個定義在歐式空間凸集RnR^n上的實凸函式,在該空間中的一個向量vv稱為ff在點x0∈Ux_0\in U的次梯度(subgradient),如果對於任意x∈Ux\in U,滿足f(x)−f(x0)≥v⋅(x−x0)f(x)-f(x_0)\geq v\cdot(x-x_0)成立。

其中⋅\cdot是向量的點積。由在點x0x_0處的所有subgradient所組成的集合稱為x0x_0處的subdifferential,記為∂f(x0)\partial f(x_0)。注意subgradient和subdifferential只是對凸函式定義的。例如一維的情況,f(x)=|x|f(x)=|x|,在x=0x=0處的 subdifferential就是[−1,1][-1,1]這個區間(集合)。又例如下圖中,在x0x_0點不同紅線的斜率就是表示subgradient的大小,有無窮多。

subgradient
圖 subgradient

注意在xx的gradient存在的點,subdifferential 將是由gradient構成的一個單點集合。這樣就將 gradient 的概念加以推廣了。這個推廣有一個很好的性質(condition for global minimizer)。以下部分參考了[3],是浙大畢業去MIT的一個牛人的部落格,看了以後自己再照著重寫了一遍。

性質1:點x0x_0是凸函式ff的全域性最小值,當且僅當0∈∂f(x0)\textbf{0}\in\partial f(x_0)。

很容易理解,看上面的圖,在x0x_0點不是全域性最小值,因為subgradient不包含0,而原點0就是全域性最小值。如果要證明也很顯然,將0∈∂f(x0)0\in\partial f(x_0)帶入前面的定義1中,就得到f(x)≥f(x0)f(x)\geq f(x_0)。

為了方便說明,需要做一個簡化假設,即資料XX的列向量是orthonormal的[2,3],即XTX=IX^TX=I(當然沒有這個假設Lasso也是可以運作的)。於是線性迴歸的最優解是

w∗=XTy

\begin{equation}
w^* =X^{T}y
\end{equation}
假設lasso問題JL(w)J_L(w)的全域性最優解是w¯∈Rn\bar{w}\in R^n,考察它的任意一個維度w¯j\bar{w}^j,需要分別討論兩種情況:

情況1:gradient存在的區間,即w¯j≠0\bar{w}^j\neq 0
由於gradient在最小值點=0,所以

∂JL(w)∂wj∣∣∣w¯j=0

\begin{equation}
{\left.\begin{matrix}
\frac{\partial J_L(w)}{\partial w^j}
\end{matrix}\right|_{\bar{w}^j}}=0
\end{equation}

所以

−(XTy−XTXw¯)j λ⋅sgn(w¯j)=0

\begin{equation}
-(X^{T}y-X^{T}X\bar{w})_j \lambda\cdot \text{sgn}(\bar{w}^j)=0
\end{equation}

其中λ≥0\lambda \geq 0。所以

w¯j=w∗j−λ⋅sgn(w¯j)

\begin{equation}
\bar{w}^j=w^{*j} – \lambda\cdot\text{sgn}(\bar{w}^j)
\end{equation}

很容易看出,w¯j和w∗j\bar{w}^j和w^{*j}是同號的,因此可以得出

w¯j=w∗j−λ⋅sgn(w¯j)=sgn(w∗j)(|w∗j|−λ)(|w∗j|−λ)=|w¯j|≥0

\begin{equation}
\bar{w}^j=w^{*j} – \lambda\cdot\text{sgn}(\bar{w}^j)=\text{sgn}(w^{*j})(|w^{*j}|-\lambda)\\
(|w^{*j}|-\lambda)=|\bar{w}^j|\geq 0
\end{equation}

最後得到

w¯j=sgn(w∗j)(|w∗j|−λ)

\begin{equation}
\bar{w}^j=\text{sgn}(w^{*j})(|w^{*j}|-\lambda)_ \\
\end{equation}

其中(x) (x)_ 表示取xx的正數部分;(x) =max(x,0)(x)_ =\max(x,0)。

情況2:gradient不存在,即w¯j=0\bar{w}^j= 0
根據前面的性質1,如果w¯j\bar{w}^j是最小值,則

0∈∂JL(w¯)=−(XTy−XTXw¯) λ⋅e=w¯−w∗ λ⋅e

\begin{equation}
\textbf{0} \in \partial J_L(\bar{w})=-(X^{T}y-X^{T}X\bar{w}) \lambda\cdot \textbf{e} = \bar{w} – w^{*} \lambda\cdot \textbf{e}
\end{equation}
其中e\textbf{e}是一個向量,每一個元素ej∈[−1,1]e^j\in [-1,1],使得0=−w∗j λ⋅ej0=-w^{*j} \lambda\cdot e^j成立。因此

|w∗j|=λ|ej|≤λ

\begin{equation}
|w^{*j}|=\lambda |e^j|\leq \lambda
\end{equation}
所以和情況(1)和(2)可以合併在一起。所以呢,如果在這種特殊的orthonormal情況下,我們可以直接寫出Lasso的最優解:

w¯j=sgn(w∗j)(|w∗j|−λ)

\begin{equation}
\bar{w}^j=\text{sgn}(w^{*j})(|w^{*j}|-\lambda)_ \\
\end{equation}

OK,再回顧一下前面的ridge regression,如果也考慮上面說的orthonormal情況下,可以很容易得出最優解為

w^R=11 λw∗

\begin{equation}
\hat{w}_R=\frac{1}{1 \lambda}w^*\\
\end{equation}

很容易得出結論,ridge實際上就是做了一個放縮,而lasso實際是做了一個soft thresholding,把很多權重項置0了,所以就得到了稀疏的結果!
lasso&ridge

除了做迴歸,Lasso的稀疏結果天然可以做機器學習中的另外一件事——特徵選擇feature selection,把非零的係數對應的維度選出即可,達到對問題的精簡、去噪,以及減輕overfitting。

上面是做了簡化後的討論,實際中lasso求解還要複雜的多。在下一篇文章中,將描述和Lasso非常相關的兩種方法,forward stagewise selection和最小角迴歸least angle regression(LARS),它們三者產生的結果非常接近(幾乎差不多),並且都是稀疏的,都可以做feature selection。有的時候就用Lars來作為Lasso的目標的解也是可以的。

參考資料

[1] http://blog.csdn.net/zouxy09/article/details/24971995
[2] The elements of statistical learning, ch3
[3] http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/
[4] http://en.wikipedia.org/w/index.php?title=Subderivative&redirect=no#The_subgradient