L1和L2范数正则化

L0范数表示向量中非零元素的个数$^{[2]}$
$left|mathbf{x} right|_0=#i,where x_i neq0$
最小化L0范数，就是尽量让$x_i$为0，所以它可以做稀疏编码和特征选择。但是最小化L0范数是一个NP hard问题，难以求解，一般用它的最优凸近似即L1范数代替。

L1范数表示向量中所有元素的绝对值和
$left|mathbf{x} right|_1=sum_{i=1}^nleft|x_iright|$

L2范数表示欧氏距离
$left|mathbf{x} right|_2=sqrt{sum_{i=1}^n x_i^2}$

Lasso回归: $J(mathbf{w})=frac{1}{n}left|mathbf{Xw}-mathbf{y} right|^2+lambdaleft|mathbf{w}right|_1$
Ridge回归: $J(mathbf{w})=frac{1}{n}left|mathbf{Xw}-mathbf{y} right|^2+lambdaleft|mathbf{w}right|_2$
等价于
Lasso回归: $underset{mathbf{w}}{min}frac{1}{n}left|mathbf{Xw}-mathbf{y} right|^2,s.t. left|mathbf{w}right|_1le C$
Ridge回归: $underset{mathbf{w}}{min}frac{1}{n}left|mathbf{Xw}-mathbf{y} right|^2,s.t. left|mathbf{w}right|_2le C$
等价后的问题可以用下图$^{[1]}$表示：

假设参数只有两个：$w_1,w_2$
L1：因为$left|mathbf{w}right|_1le C$，所以$left|w_1right|+left|w_2right|le C$，在图上画出来就是一个菱形。
L2：因为$left|mathbf{w}right|_1le C$，所以$sqrt{w_1^2+w_2^2}le C$，在图上画出来就是一个圆形。

求等价后的问题就是求: 等高线（从中心向外辐射）和约束线（菱形或圆形）的第一个交点。
对于L1来说，交点一般出现在y轴上，这意味着$w_1=0$。所以L1具有稀疏性，可用于特征选择
对于L2来说，交点一般在圆上，这意味着$w_1,w_2$都不为0。

参考：
[1]http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/#0207509841e77ec485b05a8ad73ee5e41f200b57
[2]http://www.cnblogs.com/little-YTMM/p/5879093.html