l1 相比於 l2 為什麼容易獲得稀疏解？

11-26

google遍了。。還是沒太看懂。請教下。

假設費用函數 L 與某個參數 x 的關係如圖所示：

則最優的 x 在綠點處，x 非零。

現在施加 L2 regularization，新的費用函數（ $L + Cx^2$ ）如圖中藍線所示：

最優的 x 在黃點處，x 的絕對值減小了，但依然非零。

而如果施加 L1 regularization，則新的費用函數（ $L + C|x|$ ）如圖中粉線所示：

最優的 x 就變成了 0。這裡利用的就是絕對值函數的尖峰。

兩種 regularization 能不能把最優的 x 變成 0，取決於原先的費用函數在 0 點處的導數。
如果本來導數不為 0，那麼施加 L2 regularization 後導數依然不為 0，最優的 x 也不會變成 0。
而施加 L1 regularization 時，只要 regularization 項的係數 C 大於原先費用函數在 0 點處的導數的絕對值，x = 0 就會變成一個極小值點。

上面只分析了一個參數 x。事實上 L1 regularization 會使得許多參數的最優值變成 0，這樣模型就稀疏了。

首先你要知道L1範式和L2範式是怎麼來的,然後是為什麼要把L1或者L2正則項加到代價函數中去.
L1,L2範式來自於對數據的先驗知識.如果你認為,你現有的數據來自於高斯分布,那麼就應該在代價函數中加入數據先驗P(x),一般由於推導和計算方便會加入對數似然,也就是log(P(x)),然後再去優化,這樣最終的結果是,由於你的模型參數考慮了數據先驗,模型效果當然就更好.
哦對了,如果你去看看高斯分布的概率密度函數P(x),你會發現取對數後的log(P(x))就剩下一個平方項了,這就是L2範式的由來--高斯先驗.
同樣,如果你認為你的數據是稀疏的,不妨就認為它來自某種laplace分布.不知你是否見過laplace分布的概率密度函數,我貼出一張維基上的圖,

laplace分布是尖尖的分布,是不是很像一個pulse?從這張圖上,你應該就能看出,服從laplace分布的數據就是稀疏的了(只有很小的概率有值,大部分概率值都很小或為0).
那麼,加入了laplace先驗作為正則項的代價函數是什麼?
再看看laplace分布的概率密度函數(還是來自維基百科),

看到沒,如果取對數,剩下的是一個一次項|x-u|,這就是L1範式.
所以用L1範式去正則,就假定了你的數據是laplace分布,是稀疏的.

引用自PRML，說的很清楚。

關於為什麼 $ell_1$ -norm regularization會使得結果稀疏，從幾何角度可以很好的解釋，以Basis Pursuit(BP)為例，最簡單也是最經典的問題。先從BP問題起源說起，假設關於變數 $x in mathbb{R}^n$ ，我們有
$b = Ax,$
其中 $A:mathbb{R}^n o mathbb{R}^m$ 是一個線性運算元(linear operator)， $b in mathbb{R}^m$ 是觀察量(observation)。如下圖所示(2D example)

已知 $b$ 和 $A$ 求 $x$ 的過程稱作最小二乘(least square)，當 $A^TA$ 可逆時，那麼 $x$ 可以由如下顯式表達
$x = (A^TA)^{-1} A^T b.$

但是，對於 $A$ ，很多時候， $m<n$ ，或者 $m=n$ 且 $mathrm{rank}(A)<m$ ，這使得問題時病態的(ill-posed)，並且存在無窮多的解。

對於這類情形，為了得到一些有意義的解，需要對 $x$ 進行正則化(regularization)。下面就對比下，對 $x$ 施加 $ell_1$ ， $ell_2$ 正則時(比如，希望解的 $ell_1$ -norm最小)，會得到怎樣的解。此時我們會得到如下的優化問題
$min_{xinmathbb{R}^n} |x|_{p}~~mathrm{subject~to}~~b=Ax.$
其中 $p=1,2$ 。對於 $p=1$ ，該問題又稱作Basis Pursuit。對兩種情形分別求解，我們會得到如下圖所示的可行點(feasible point)， $x^star_{ell_1}$ 和 $x^star_{ell_2}$ 。很顯然，可行解 $x^star_{ell_1}$ 是稀疏的( $x_1=0$ )，而 $x^star_{ell_2}$ 不是( $x_1 eq 0, x_2 eq 0$ )。

也就是說，對於一個線性約束( $b=Ax$ )，當用 $ell_{p}$ -norm ball與之相切時，只有當 $pleq 1$ 時，切點在該ball的一個頂點(在數軸上)，並且該點是稀疏的(很多元素為零)。

不過這時候你也許會問，如果 $b=Ax$ 與 $1=-x_1+x_2$ 平行，或者與 $x_1$ 軸平行怎麼辦。對於前者，這個時候用 $ell_{p}$ -norm $p<1$ 仍然可以得到稀疏解，但此時解不唯一。對於後者，問題時退化的。實際上，線性運算元 $A$ 是要滿足一定性質的，比如最開始的Restricted Isometry Property (RIP)條件。

還有就是如果observation帶雜訊怎麼辦，對於上面的圖示，唯一的變化就是不再是 $b=Ax$ 一條直線，而是帶有上下屆的一個band，band寬度依雜訊強度決定。

最後，關於稀疏表達的意義，可參考另一個回答
稀疏表達的意義在於？為什麼稀疏表達得到廣泛的應用？ - 知乎用戶的回答

王贇 Maigo的答案特別棒！

我還有幾個理解這個問題的方式，不過自己沒有搞清楚，想拿出來探討一下。
1.假設原先損失函數是C0，那麼在L2和L1正則條件下對參數求導分別是：

可以想像用梯度下降的方法，當w小於1的時候，L2正則項的懲罰效果越來越小，L1正則項懲罰效果依然很大，L1可以懲罰到0，而L2很難。

2.我們假設有兩個完全一樣的特徵，使用L2正則想的話，兩個特徵權重相等的時候懲罰最小，所以L2具有權重平均分配的效果。

3.第三個說法是我聽說的，如果我們使用L0作為正則項，三個係數不為零則懲罰力度 3 alpha，五個不為零則懲罰力度 5 alpha，很容易理解它有讓稀疏稀疏的效果。在某些條件下L0和L1正則項是等價的（不要問我是什麼條件，我查了沒看懂……），所以L1容易得到稀疏解。

以上個人的理解，有錯誤的地方歡迎指正。

可以查查凸優化這本書，書上說，l1對於小值的懲罰，比l2的大。自然求優化的時候，求得小係數的值越小。

因為引入L1-regularization的時候，我們求解問題：
$min:Loss(W)+lambda L_1(W)$
等價於：
$min:Loss(W) \ s.t. L_1(W) = C$
也就是我們求解的是一個帶約束的問題。用Lagrange multiplier來求解。收斂的地方是：
$abla Loss(W) = -k abla L_1(W)$ 。
但是有些地方是不可微的。比如 $L_1$ 的幾個頂點處。所以準確的來說，達到最優解 $W^*$ 的地方是 $- abla Loss(W)$ 落在 $W$ 的normal cone的區域內。

紫色區域就是頂點處的normal cone。而正方形的邊的一點的normal cone只是垂直它的方向，也就只有一條線。然而我們的數據是服從某個分布，Loss function關於W的形狀也就是由數據決定的，那麼所有與約束條件相交的點中，哪個滿足上面的條件的概率最大呢？顯然是頂點。也因此使得我們的模型更加sparse。

更加直觀的來說，有一個球在曲面上，我們把球受到的重力和曲面的支撐力的合力看成一個力，方向也就是曲面的梯度方向。此外我們還受到一個來自於四邊形（上圖）的架子的支撐力，而最優解處就是球能夠靜止平衡的地方，那麼很明顯，是不是在四個頂角處最有可能禁止。

就是拿跟繩子掛點重物，繩子很容易滑倒這個架子的角點處吧。
一般來說，越是non-convex的regularizer越是容易使的我們的模型sparse。比如 $L_p$ 當 $p<1$ 時。

來一點簡單的數學：
考慮標量 $w$ ，希望 $min_w f(w)+ lambda|w|_1$
假設 $f(w)$ 在 $w=0$ 附近為凸，則對充分小的 $Delta$ ，我們有
$f(Delta) geq f(0) + f^prime(0)Delta$

這時候 $w=0$ 為局部最小值的充分必要條件就是：對 $forall Delta$ 接近於0，
$f(Delta) + lambda |Delta| geq f(0)$ ，

由於有凸性質， $w=0$ 的充分條件為：
$f^prime(0)Delta + lambda|Delta| geq 0$
分情況考慮 $Delta$ 正負，得到，
$|f^prime(0)|leq lambda$

而注意如果是l2:
$min_w f(w)+ lambda||w||_2^2$
$w=0$ 為局部最小值的充分必要條件為 $f^prime(0) = 0$ 。

所以感受一下兩個條件的強弱，就知道為什麼l1更容易得到稀疏解了。

（如果知道subgradient的話，0屬於 $f(w)+ lambda|w|_1$ 的subgradient也可以直接得到上面的結論）

-----------
這個推導是本科上機器學習的時候教的，&但是死活翻筆記找不到&，找到了，原來當時不是我這麼推的，是直接用subgradient的，
http://bcmi.sjtu.edu.cn/log/files/lecture_notes/ml_2014_spring_ieee/lecture9.pdf

可能推導中不是特別嚴謹，畢竟是數學渣。但是對於我來說，這個推導比那個直觀的圖更戳中我。
（當然有lasso有更多理論證明。。。。我的level還不到那個層次。。。）

很多人貼PRML書里的那個圖，但是感覺很多人有疑問，原本我要優化的是包含正則項的損失，這兩個應該是一起優化的，為什麼在圖裡把它們拆解了，其實PRML書里也說得很明白，我再說得具體點。

首先，我們要優化的是這個問題 $minlimits_w E_D(w) + lambda E_R(w)$ 。

其次， $minlimits_w E_D(w) + lambda E_R(w)$ 和 $minlimits_w E_D(w) \s.t. E_R(w) leqslant eta$

這個優化問題是等價的，即對一個特定的 $lambda$ 總存在一個 $eta$ 使得這兩個問題是等價的（這個是優化里的知識）。

最後，下面這個圖表達的其實 $minlimits_w E_D(w) \s.t. E_R(w) leqslant eta$

這個優化問題，把 $w$ 的解限制在黃色區域內，同時使得經驗損失儘可能小。

l1在小的時候懲罰力度還很大吧因為
換個角度看
用proximal mapping演算法看的話l1的proximal函數是shrinkage帶有一個閾值，這麼看的話l1優化出來應該很稀疏吧
貝葉斯看法的話原來是Laplace分布所以稀疏吧？不確定

來源：The Elements of Statistical Learning(Second Edition)

我們可以想像一下L0問題：正則化項非0參數，優化這個直接等於求稀疏解。當然這是一個組合優化問題。
L1 norm是包含L0的最小凸區域，也就是說我們既可以用凸優化來求解，同時它也保持了一定程度L0的稀疏性質。
而L2 norm的正則化有closed form解，但是相對來說距離L0就更遠了一些。
（L2正則化的解相當於先對數據做主成分分析，然後對於小的主成分採取比較大的懲罰值之後再做回歸）
更正：是對最後的回歸係數分解在數據的主成分上，再各自進行縮小。（再做回歸不對）

簡單說吧, 加上範數正則化的無約束優化可以等價於某個約束優化問題, 這個約束優化問題的代價函數就是範數. l1範數可以看成是一個菱形球, l2範數就是一個光滑球面. 菱形球更容易在定點處達到最優點.
明天補充兩個圖吧

參考周志華西瓜書253頁
總結一點就是
L1範數有稜角，和優化目標函數相切的點在各分量上要麼有值要麼為0
L2範數比較圓滑，喜歡每個分量上都分一點
參考兩個分量的坐標圖：

首先想贊下 @王贇 Maigo , 我自己從沒想到從這個角度理解過這個問題，對我很有幫助。
其次想說一下自己的理解。
第一種理解方式來自台大林軒田老師的機器學習基石課程，也是我接觸到的第一種理解方式。

首先大家都知道不同的範數定義下的unit-ball是不同的，如下圖。
圖片來自我本學期所選修機器學習課程的ppt。

圖中，藍色的是l1-norm對應的unit-ball，紅色的是l2-norm對應的unit-ball。

我們在解一個最優化問題時，總是想到達它的最小值或者最大值點。

但是正則化，也就是加上約束條件，之後就不能隨心所欲的取到minimizer了，還要保證我們的解滿足這些限制條件。
比如l2-norm對應的限定條件|w|^2&

圖中這個情況我們可以看到，在w到達紅圈邊界的時候最有機會取得極值。對於邊界上得點，該點指向minimizer方向與unit-ball法向量同方向，就找到了滿足條件的。

對於l1-norm 同理。但是這裡我們會發現，很大概率我們的解會落在角上，具體解釋見機器學習基石視頻課程57講。這意味著，某些分量會為零，因此就得到了稀疏解。

第二種理解方式是從概率的角度，這裡思路和 @amnesia 類似，但是我對先驗概率的理解有所不同。

l2 regularisation 相當與假設我們所求解w的分布為高斯分布，l1對應的先驗概率函數則為拉布拉斯分布。概率密度函數如下圖所示：

畫得極端了點兒。

這裡概率我們可以理解為容忍度。概率大就是取到這個值也ok了，小就是絕對忍不了在這地方取值。
可以很容易看出，高斯分布對於大w比較忍不了，但是對於小的w特別能忍。也就是它只panalize w到一個小數，不一定非要是零。
而拉布拉斯分布對於小得w特別不能忍，非常迫切的希望它們都是零。而對於非常大的w容忍度要優於高斯分布。
也就是說，l1正則化更容易獲得稀疏解，並且更容易看出關鍵的feature（大得w對應的）。

最後，由於我本人是學圖像的，在機器學習學了這個之後感覺對tv regularization有一些除了擴散之外的理解。分享在這裡希望有同行一起探討。

這裡應該只是把先驗部分從解本身的信息，換成了解梯度的信息。
tv正則化對應l1正則化，只不過這裡的條件不是關於解本身的了，而是關於解得梯度。但也都是一個道理，最後得到解的梯度是稀疏的，大梯度絕對值得（邊緣）被保留，而小得梯度值部分（細節）梯度值被推向零（細節消失變成了flat area）。這與擴撒理解也對應上了，TV正則化對應的歐拉拉格朗日方程對應著各向同性非線性擴散，這種擴散保存邊緣模糊細節。
tikhonov 正則化對應著 L2正則化，大梯度值被推向小梯度值，小梯度值不一定要被推向0。整幅圖像變模糊，部分細節得以保留，不至於變常數。也對應上了它的擴散方程是各向同性線性擴散方程。

貼一個之前的回答：孫滿：0 範數、1 範數、2 範數有什麼區別？

在這個回答的評論里，我和知友 @文臺有過交流，可能不太準確，但他的視角對我而言很新，很值得再思考，評論如下，這裡也感謝文臺。