首頁>Club>
6
回覆列表
  • 1 # 初見山風

    淺談L0,L1,L2範數及其應用

    線上性代數,函式分析等數學分支中,範數(Norm)是一個函式,其賦予某個向量空間(或矩陣)中的每個向量以長度或大小。對於零向量,另其長度為零。直觀的說,向量或矩陣的範數越大,則我們可以說這個向量或矩陣也就越大。有時範數有很多更為常見的叫法,如絕對值其實便是一維向量空間中實數或複數的範數,而Euclidean距離也是一種範數。

    範數的一般化定義:設p≥1的實數,p-norm定義為:

    ||x||p:=(∑i=1n∣∣xi∣∣p)1p(1)

    此處,當p=1時,我們稱之為taxicab Norm,也叫Manhattan Norm。其來源是曼哈頓的計程車司機在四四方方的曼哈頓街道中從一點到另一點所需要走過的距離。也即我們所要討論的l1範數。其表示某個向量中所有元素絕對值的和。 而當p=2時,則是我們最為常見的Euclidean norm。也稱為Euclidean distance。也即我們要討論的l2範數。 而當p=0時,因其不再滿足三角不等性,嚴格的說此時p已不算是範數了,但很多人仍然稱之為l0範數。 這三個範數有很多非常有意思的特徵,尤其是在機器學習中的正則化(Regularization)以及稀疏編碼(Sparse Coding)有非常有趣的應用。

    下圖給出了一個Lp球的形狀隨著P的減少的視覺化圖。

    1- L0 範數

    雖然L0嚴格說不屬於範數,我們可以採用等式1來給出l0-norm得定義:

    ||x||0:=0∑i=0nx0i‾‾‾‾‾‾⎷(2)

    上面的公式仍然讓人不是很明白,0的指數和平方根嚴格意義上是受限條件下才成立的。因此在實際應用中,多數人給出下面的替代定義:

    ||x||0=#(i)withxi≠0(3)

    其表示向量中所有非零元素的個數。正是L0範數的這個屬性,使得其非常適合機器學習中稀疏編碼,特徵選擇的應用。透過最小化L0範數,來尋找最少最優的稀疏特徵項。但不幸的是,L0範數的最小化問題在實際應用中是NP難問題。因此很多情況下,L0最佳化問題就會被relaxe為更高維度的範數問題,如L1範數,L2範數最小化問題。

    2- L1 範數

    對於向量X,其L1範數的定義如下:

    ||x||1:=∑i=1n∣∣xi∣∣(4)

    其應用範圍非常的廣泛。如在計算機視覺中的Sum of Absolute Differents,Mean Absolute Error,都是利用L1正規化的定義。

    L1最最佳化問題的解是稀疏性的,其傾向於選擇很少的一些非常大的值和很多的insignificant的小值。而L2最最佳化則更多的非常少的特別大的值,卻又很多相對小的值,但其仍然對最最佳化解有significant的貢獻。但從最最佳化問題解的平滑性來看,L1範數的最優解相對於L2範數要少,但其往往是最優解,而L2的解很多,但更多的傾向於某種區域性最優解。

    但由於L1範數並沒有平滑的函式表示,起初L1最最佳化問題解決起來非常困難,但隨著計算機技術的到來,利用很多凸最佳化演算法使得L1最最佳化成為可能。

    3- L2 範數

    當然範數中最常見,也最著名的非L2範數莫屬。其應用也幾乎包括科學和工程的各個領域。定義公式如下:

    ||x||2:=∑i=1nx2i‾‾‾‾‾‾⎷(5)

    也Euclidean Norm,如果用於計算兩個向量之間的不同,即是Euclidean Distance.

    歐幾里德範數的最最佳化問題可以用如下公式表述:

    min||x||2subjecttoAx=b(6)

    藉助拉格朗日乘子,我們便可以解決該最最佳化問題。由L2衍生,我們還可以定義無限norm,即l-infinity norm:

    ||x||∞:=∞∑i=1nx∞i‾‾‾‾‾‾⎷(7)

    一眼看上去上面的公式還是有點tricky的。我們透過一個簡單的數學變換,假設X_j是向量中最大的元素,則根據無限大的特性,我們可以得到:

    x∞j>>x∞i∨j≠i

    則可知

    ∑i=1nx∞i=x∞j

    則根據公式(7)的定義,我們可以得到:

    ||x||∞=∞∑i=1nx∞i‾‾‾‾‾‾⎷=∞x∞j‾‾‾√=∣∣xj∣∣

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

    ||x||∞=max(∣∣xj∣∣)(8)

  • 中秋節和大豐收的關聯?
  • 因父母不同意分手了一個月,但是現在想見面,應該主動約見面嗎?