原文作者鏈接

L0,L1,L2范數(shù)及其應(yīng)用

在線性代數(shù)碉咆，函數(shù)分析等數(shù)學(xué)分支中洲敢，范數(shù)（Norm）是一個(gè)函數(shù)，其賦予某個(gè)向量空間（或矩陣）中的每個(gè)向量以長度或大小劈愚。對于零向量瞳遍，另其長度為零。直觀的說菌羽，向量或矩陣的范數(shù)越大掠械，則我們可以說這個(gè)向量或矩陣也就越大。有時(shí)范數(shù)有很多更為常見的叫法注祖，如絕對值其實(shí)便是一維向量空間中實(shí)數(shù)或復(fù)數(shù)的范數(shù)猾蒂，而Euclidean距離也是一種范數(shù)。

范數(shù)的一般化定義：設(shè)p≥1p≥1的實(shí)數(shù)是晨，p-norm定義為：

p-范數(shù)

此處婚夫，當(dāng)p=1時(shí)，我們稱之為taxicab Norm署鸡，也叫Manhattan Norm案糙。其來源是曼哈頓的出租車司機(jī)在四四方方的曼哈頓街道中從一點(diǎn)到另一點(diǎn)所需要走過的距離。也即我們所要討論的l1范數(shù)靴庆。其表示某個(gè)向量中所有元素絕對值的和时捌。?

而當(dāng)p=2時(shí)，則是我們最為常見的Euclidean norm炉抒。也稱為Euclidean distance奢讨。也即我們要討論的l2范數(shù)。?

而當(dāng)p=0時(shí)焰薄，因其不再滿足三角不等性拿诸，嚴(yán)格的說此時(shí)p已不算是范數(shù)了扒袖，但很多人仍然稱之為l0范數(shù)。 這三個(gè)范數(shù)有很多非常有意思的特征亩码，尤其是在機(jī)器學(xué)習(xí)中的正則化（Regularization）以及稀疏編碼（Sparse Coding）有非常有趣的應(yīng)用季率。

下圖給出了一個(gè)Lp球的形狀隨著P的減少的可視化圖。

1- L0 范數(shù)

雖然L0嚴(yán)格說不屬于范數(shù)描沟，我們可以采用等式11來給出l0-norm得定義：

0-范數(shù)

上面的公式仍然讓人不是很明白飒泻，0的指數(shù)和平方根嚴(yán)格意義上是受限條件下才成立的。因此在實(shí)際應(yīng)用中吏廉，多數(shù)人給出下面的替代定義：

0-范數(shù)

其表示向量中所有非零元素的個(gè)數(shù)泞遗。正是L0范數(shù)的這個(gè)屬性，使得其非常適合機(jī)器學(xué)習(xí)中稀疏編碼席覆，特征選擇的應(yīng)用史辙。通過最小化L0范數(shù)，來尋找最少最優(yōu)的稀疏特征項(xiàng)佩伤。但不幸的是髓霞，L0范數(shù)的最小化問題在實(shí)際應(yīng)用中是NP難問題。因此很多情況下畦戒，L0優(yōu)化問題就會(huì)被relaxe為更高維度的范數(shù)問題方库，如L1范數(shù)，L2范數(shù)最小化問題障斋。

2- L1 范數(shù)

對于向量X纵潦，其L1范數(shù)的定義如下：

1-范數(shù)

其應(yīng)用范圍非常的廣泛。如在計(jì)算機(jī)視覺中的Sum of Absolute Differents垃环，Mean Absolute Error邀层，都是利用L1范式的定義。

L1最優(yōu)化問題的解是稀疏性的遂庄，其傾向于選擇很少的一些非常大的值和很多的insignificant的小值寥院。而L2最優(yōu)化則更多的非常少的特別大的值，卻又很多相對小的值涛目，但其仍然對最優(yōu)化解有significant的貢獻(xiàn)秸谢。但從最優(yōu)化問題解的平滑性來看，L1范數(shù)的最優(yōu)解相對于L2范數(shù)要少霹肝，但其往往是最優(yōu)解估蹄，而L2的解很多，但更多的傾向于某種局部最優(yōu)解沫换。

L1 VS L2

但由于L1范數(shù)并沒有平滑的函數(shù)表示臭蚁，起初L1最優(yōu)化問題解決起來非常困難，但隨著計(jì)算機(jī)技術(shù)的到來，利用很多凸優(yōu)化算法使得L1最優(yōu)化成為可能垮兑。

3- L2 范數(shù)

當(dāng)然范數(shù)中最常見冷尉，也最著名的非L2范數(shù)莫屬。其應(yīng)用也幾乎包括科學(xué)和工程的各個(gè)領(lǐng)域系枪。定義公式如下：

2-范數(shù)

也Euclidean Norm雀哨，如果用于計(jì)算兩個(gè)向量之間的不同，即是Euclidean Distance.

歐幾里德范數(shù)的最優(yōu)化問題可以用如下公式表述：

最優(yōu)化

借助拉格朗日乘子嗤无，我們便可以解決該最優(yōu)化問題。由L2衍生怜庸，我們還可以定義無限norm当犯，即l-infinity norm：

無窮范數(shù)

無窮范數(shù)

一眼看上去上面的公式還是有點(diǎn)tricky的。我們通過一個(gè)簡單的數(shù)學(xué)變換割疾，假設(shè)X_j是向量中最大的元素嚎卫，則根據(jù)無限大的特性，我們可以得到：

則根據(jù)公式無窮范數(shù)的定義宏榕，我們可以得到：

因此我們便可以說l-infinity norm是X向量中最大元素的長度拓诸。

無窮范數(shù)

4- 機(jī)器學(xué)習(xí)中的應(yīng)用

不知道有多少人是因?yàn)闄C(jī)器學(xué)習(xí)中的正則化和特征選擇等才開始了解這些范數(shù)的，至少我是麻昼。L0范數(shù)本身是特征選擇的最直接最理想的方案奠支，但如前所述，其不可分抚芦，且很難優(yōu)化倍谜，因此實(shí)際應(yīng)用中我們使用L1來得到L0的最優(yōu)凸近似。L2相對于L1具有更為平滑的特性叉抡，在模型預(yù)測中尔崔，往往比L1具有更好的預(yù)測特性。當(dāng)遇到兩個(gè)對預(yù)測有幫助的特征時(shí)褥民，L1傾向于選擇一個(gè)更大的特征季春。而L2更傾向把兩者結(jié)合起來。

4-1 正則化

在機(jī)器學(xué)習(xí)中正則化是指在損失函數(shù)中通過引入一些額外的信息消返，來防止ill-posed問題或過擬合問題载弄。一般這些額外的信息是用來對模型復(fù)雜度進(jìn)行懲罰（Occam's razor）。其一般形式如下：

||w||||w||便可以選取L1或是L2范數(shù)來作為懲罰項(xiàng)撵颊，不同的模型侦锯，其損失函數(shù)也不同，對于線性回歸而言秦驯，如果懲罰項(xiàng)選擇L1尺碰，則是我們所說的Lasso回歸，而L2則是Ridge回歸。下面我們列出了不同模型中的正則化的損失函數(shù)（來自Andrew Ng的Machine Learning課程）：

Regularized Logistic Regression

Regularized Neural Network

Soft Margin SVM

從上面可以看出常用的正則化項(xiàng)多是L2范數(shù)亲桥，除了防止過擬合的問題洛心，還有一個(gè)好處就是能否改善ill-posed(condition)問題。尤其是當(dāng)訓(xùn)練樣本相對于特征數(shù)非常少時(shí)题篷，其矩陣便是非滿秩的词身，往往傾向于有無數(shù)個(gè)解，且是不可逆的番枚。其condition num便會(huì)很大法严。一方面，根據(jù)此得到的最優(yōu)化值很不穩(wěn)定葫笼，往往某個(gè)特征變量很小的變動(dòng)都會(huì)引發(fā)最終結(jié)果較大的偏差深啤。另外通過矩陣求逆從而求的最優(yōu)解就會(huì)變的非常困難。如對于線性回歸而言路星，求的最優(yōu)解析解為：

而加上L2正則項(xiàng)后溯街，其變?yōu)椋?/p>

從而可以直接求逆，改善了condition number洋丐。

而對于無解析解呈昔，通過迭代優(yōu)化的算法，L2正則化通過將目標(biāo)函數(shù)變?yōu)棣?strongly convex（λ強(qiáng)凸）友绝，有效的加快了其收斂速度堤尾。

4-2 貝葉斯先驗(yàn)

正則化項(xiàng)從貝葉斯學(xué)習(xí)理論的角度來看，其相當(dāng)于一種先驗(yàn)函數(shù)迁客。即當(dāng)你訓(xùn)練一個(gè)模型時(shí)哀峻，僅僅依靠當(dāng)前的訓(xùn)練集數(shù)據(jù)是不夠的，為了實(shí)現(xiàn)更好的預(yù)測（泛化）效果哲泊，我們還應(yīng)該加上先驗(yàn)項(xiàng)剩蟀。而L1則相當(dāng)于設(shè)置一個(gè)Laplacean先驗(yàn)，去選擇MAP（maximum a posteriori）假設(shè)切威。而L2則類似于 Gaussian先驗(yàn)育特。如下圖所示：

從上圖可以看出，L1先驗(yàn)對大值和小值的tolerate都很好先朦，而L2先驗(yàn)則傾向于均勻化大值和小值缰冤。

4-3 特征選擇與稀疏編碼

機(jī)器學(xué)習(xí)社區(qū)里通常把特征選擇的方法分為三種。一種是基于統(tǒng)計(jì)學(xué)的一些方法喳魏，對特征進(jìn)行預(yù)篩選棉浸，選出子集作為模型輸入。如統(tǒng)計(jì)推理使用的假設(shè)檢驗(yàn)刺彩，P值迷郑。另一種是采用某種成熟的學(xué)習(xí)算法進(jìn)行特征選擇枝恋，如決策樹中采用信息增益來選擇特征。還有一種便是在模型算法中進(jìn)行自動(dòng)特征選擇嗡害。而L1范數(shù)作為正則化項(xiàng)焚碌，其特征選擇的圖譜傾向于spiky，實(shí)現(xiàn)了有效的特征選擇霸妹。

稀疏編碼也是想通過尋找盡可能少的特征表達(dá)某個(gè)輸入的向量X十电。

其中?i?i是所要尋找的基向量，a(j)iai(j)是我們要優(yōu)化的各個(gè)基向量的權(quán)重叹螟。最右邊的表達(dá)式便是其正則化懲罰項(xiàng)鹃骂，在這里也稱Sparse Cost。實(shí)際中我們通常便用L1范數(shù)罢绽。

加入兩個(gè)題目

題目1

題目2

L1最優(yōu)化問題的解是稀疏性的畏线，其傾向于選擇很少的一些非常大的值和很多的insignificant的小值。而L2最優(yōu)化則更多的非常少的特別大的值有缆，卻又很多相對小的值象踊，但其仍然對最優(yōu)化解有significant的貢獻(xiàn)温亲。但從最優(yōu)化問題解的平滑性來看棚壁，L1范數(shù)的最優(yōu)解相對于L2范數(shù)要少，但其往往是最優(yōu)解栈虚，而L2的解很多袖外，但更多的傾向于某種局部最優(yōu)解。

5 參考

[1.]Wiki: Norm.

[2.]Rorasa's blog.

[3.]MaxJax.

[4.]機(jī)器學(xué)習(xí)中的范數(shù)規(guī)范化.

[5.]Difference between l1 and l2.

[6.]gradient-descent-wolfe-s-condition-and-logistic-regression.