LASSO（least absolute shrinkage and selection operator）回歸中如何用梯度下降法求解？

01-05

即求解在|βi|&

首先你要知道l-1 norm的導數是連續不光滑的，所以沒有辦法直接求導利用梯度下降來求解。可以考慮最簡單的情況，即x只有一維

f(x) = (x-a)^2 + c |x|

我們首先需要定義|x|在0點的梯度，我們叫做subgradient。

像上面圖裡畫的，直觀理解，函數在某一點的導數可以看成函數在這一點上的切線，那麼在原點，因為這一點不是光滑的（左右導數不一樣），所以可以找到實線下方的無數條切線，形成一個曲線族。我們就把這些切現斜率的範圍定義為這一點的subgradient.

也就是 |x|在0點的導數是在-1到1範圍內的任意值。具體的數據推到在這裡就不寫了。

那麼我們可以寫出f(x)的導數

2(x-a) + cx when x&>0

f"(x) = 2a + d when x=0 and -c &< d &< c

2(x-a) - cx when x&<0

我們可以發現，當 -c &< 2a &< c，x=0時， f『(x)恆等於0，也就是f(x)到達極值點。這也就解釋了為什麼在l_1 penalty下得到的解會稀疏，因為當c在一定範圍內時，只要x為0，f』(x)就為0。當然，上面的式子也可以用梯度下降方法去優化。

但是，當x擴展為多維向量的時候，問題就變得更複雜了，因為導數方向的變化範圍更大。下面有幾種常見的思路解這個問題，只說一下基本的思想，具體的演算法可以看相關paper。

1. 貪心演算法，每次先找跟目標最相關的feature，然後固定其他的係數，優化這一個feature的係數，具體的求導也要用到上面的subgradient。代表演算法有LARS，feature-sign search等。

2. 逐一優化。就每次固定其他的dimension，選擇一個dimension進行優化。因為只有一個方向有變化，所以都可以轉化為上面簡單的subgradient問題。最後反覆迭代所有的dimension，達到收斂。代表演算法有 coordinate descent，block coordinate descent等。

3. 還有一類演算法，就是proximal及其擴展方法。這類演算法可以解決一系列的sparse norm優化問題，基本思想就是不斷的迭代需要優化的稀疏。每一次迭代上上一次優化結果的鄰域找一個新的點，而且新的點需要在優化目標的限定區域內。這個限定區域可以通過找到原始優化問題的對偶問題得到。

寫了一篇關於用 臨近梯度法（ Proximal Gradient） 求解 Lasso 問題的完整推導求解過程，有興趣的可以仔細看下一下，比較偏理論推導。另外還補充了對嶺回歸方法的推導求解。

Lasso Problem by Proximal Gradient Methond

謝邀。

你可以看看TFOCS，一個用proximal gradient演算法解convex cone optimization的模版，lasso是其中一個特例。

http://tfocs.stanford.edu/

我胡說幾句吧，其實這個題目應該請Hastie的Phd學生趙卿元同學來回答的。

Firedman的GPS是一個很好的思路，具體看Friedman, Jerome H. "Fast sparse regression and classification." International Journal of Forecasting 28, no. 3 (2012): 722-738。

Friedman上課好像提到gps有一段時間是最快的演算法，但是google的演算法現在超過很多。我專業不是這個，有沒有人介紹一下？

論文方向……

占坑，畢設做這個。。做完看看能否一知半解。。

你好，請問lasso是一種特殊的回歸方法嗎？與線性回歸有關係嗎？與非參回歸又有什麼聯繫呢？

LASSO（least absolute shrinkage and selection operator） 回歸中 如何用梯度下降法求解？

LASSO（least absolute shrinkage and selection operator）回歸中如何用梯度下降法求解？