0範數，1範數，2範數的區別

05-23

0範數，1範數，2範數的區別

以下分別列舉常用的向量範數和矩陣範數的定義。

向量範數

1-範數：

$||x||_1 = sum_{i=1}^N|x_i|$ ，即向量元素絕對值之和，matlab調用函數norm(x, 1) 。

2-範數：

$|| extbf{x}||_2 =sqrt{sum_{i=1}^Nx_i^2}$ ，Euclid範數（歐幾里得範數，常用計算向量長度），即向量元素絕對值的平方和再開方，matlab調用函數norm(x, 2)。

$infty$ -範數： $|| extbf{x}||_infty = max_{i}|x_i|$ ，即所有向量元素絕對值中的最大值，matlab調用函數norm(x, inf)。

$-infty$ -範數： $|| extbf{x}||_{-infty}=min_i|x_i|$

，即所有向量元素絕對值中的最小值，matlab調用函數norm(x, -inf)。

p-範數： $|| extbf{x}||_p = (sum_{i=1}^N|x_i|^p)^{frac{1}{p}}$

，即向量元素絕對值的p次方和的1/p次冪，matlab調用函數norm(x, p)。

矩陣範數

1-範數： $||A||_1 = max_jsum_{i=1}^m|a_{i,j}|$

，列和範數，即所有矩陣列向量絕對值之和的最大值，matlab調用函數norm(A, 1)。

2-範數： $||A||_2 = sqrt{lambda_1}$ ， $lambda<br/>$ 為 $A^TA$ 的最大特徵值。

，譜範數，即AA矩陣的最大特徵值的開平方。matlab調用函數norm(x, 2)。

$infty$ -範數： $||A||_infty = max_isum_{j=1}^N|a_{i,j}|$

，行和範數，即所有矩陣行向量絕對值之和的最大值，matlab調用函數norm(A, inf)。

F-範數： $||A||_F=left(sum_{i=1}^msum_{j=1}^n|a_{i,j}|^2 ight)^{frac{1}{2}}$

，Frobenius範數，即矩陣元素絕對值的平方和再開平方，matlab調用函數norm(A, 』fro『)。

核範數： $||A||_* = sum_{i=1}^{n}lambda_i, lambda_i$ 是A的奇異值。

即奇異值之和

我們從最簡單的最小二乘線性模型開始。最開始，最小二乘的loss(需優化的目標函數)如下：

式中，tn是目標變數，xn是觀測量（自變數），phi 是基函數（後期推導與核化相關），是w是參數。此式有閉式解，解為：

但是我們都知道，矩陣求逆是一個病態問題，即矩陣並不是在所有情況下都有逆矩陣。所以上述式子在實際使用時會遇到問題。為了解決這個問題，可以求其近似解。可以用SGD(梯度下降法)求一個近似解，或者加入正則項（2範數）。加入正則項是我們這裡要說的。加入2範數的正則項可以解決這個病態問題，並且也可以得到閉式解，在實際使用時要比用SGD快，並且加入正則化後的好處並不僅僅是這些。加入正則項（2範數）的loss如下：

其閉式解為：

此式在 lambda 不為零時，總是有解的，所以是一個非病態的問題，這在實際使用時很好。除了這一點，2範數的正則項還有其他好處，比如控制方差和偏差的關係，得到一個好的擬合，這裡就不贅述了，畢竟這裡講的是範數，有興趣可以參閱相關資料。

加入正則項後一般情況下的loss為：

好了，我們終於可以專註於範數了。不同範數對應的曲線如下圖：

（圖來源於參考書PRML）

上圖中，可以明顯看到一個趨勢，即q越小，曲線越貼近坐標軸，q越大，曲線越遠離坐標軸，並且稜角越明顯。那麼 q=0 和 q=oo 時極限情況如何呢？猜猜看。

bingio, 你猜對了，答案就是十字架和正方形。除了圖形上的直觀形象，在數學公式的推導中，q=0 和 q=oo 時兩種極限的行為可以簡記為非零元的個數和最大項。即0範數對應向量或矩陣中非零元的個數，無窮範數對應向量或矩陣中最大的元素。具體推導可以參考維基百科。至此為止，那麼他們用在機器學習里有什麼區別呢？

以1範數和2範數為例：

（圖來自PRML）

上圖中，藍色的圓圈表示原問題可能的解範圍，橘色的表示正則項可能的解範圍。而整個目標函數（原問題+正則項）有解當且僅當兩個解範圍相切。從上圖可以很容易地看出，由於2範數解範圍是圓，所以相切的點可能有很多個，絕大部分不在坐標軸上，而由於1範數是菱形，其相切的點大多在坐標軸上，而坐標軸上的點有一個特點，其只有一個坐標分量不為零，其他坐標分量為零，即是稀疏的。所以有如下結論，1範數可以導致稀疏解，2範數導致稠密解。那麼為什麼不用0範數呢，理論上它是求稀疏解最好的規範項了。然而在機器學習中，特徵的維度往往很大，解0範數又是NP-hard問題，所以在實際中不可行。但是用1範數解是可行的，並且也可以得到稀疏解，所以實際稀疏模型中用1範數約束。

至此，我們總結一下，在機器學習中，以0範數和1範數作為正則項，可以求得稀疏解，但是0範數的求解是NP-hard問題; 以2範數作為正則項可以得到稠密解，並且由於其良好的性質，其解的定義很好，往往可以得到閉式解，所以用的很多。

另外，從距離的角度說一下範數。1範數對應街區距離，2範數對應大家熟知的歐式距離，無窮範數對應棋盤距離（切比雪夫距離）。

參考資料：

1. PRML: Pattern recognition and machine learning, Christopher M. Bishop.

2. USTC 圖像分析課程ppt，統計學習課程ppt.