正则化
传统学习模型的一般目标函数为：
\[\sum\limits_{i}L(y_{i},f(x_{i};w))+\lambda\Omega(w)\]后面的那一项即正则化项，也是本文主要讨论的项，其中$\lambda$为惩罚系数，$\Omega(w)$，常用的选择是范数。
\[||x||_{p}=(\sum\limits_{i}|x_{i}|^{p})^{\frac{1}{p}}\]L0范数
零范数比较特殊，一个向量的零范数是向量中非零元素的个数：
\[||x||_{0}=\sum\limits_{i}|x_{i}|^{0}\]如果使用L0范数当作正则函数的话，那么肯定是希望参数向量\(w\)中的零元素越多越好。但是因为L0范数是一个计数值，在优化目标时不便运算（如求导），所以一般不选用。
L1范数
\[||x||_{1}=\sum\limits_{i}|x_{i}|\]显而易见L1范数为向量中所有值的绝对值之和，是L0范数的最优凸近似，而且比L0范数要容易优化求解，所以一般不使用L0范数，而是使用L1范数来代替它。
使用L1范数作为正则函数时，优化的目标函数变为：
\[\sum\limits_{i}L(y_{i},f(x_{i};w))+\lambda||w||_{1}\]这也被称为LASSO (Least Absolute Shrinkage and Selection Operator) ，它能够产生稀疏解。下面来看一个直观的解释，我们需要求的最优解为：
\[W=[w_{1}, w_{2},……, w_{n}]=arg\ min(\sum\limits_{i}L(y_{i},f(x_{i};w))) \qquad s.t.||w||_{1}\le{C}\]假设此处用的损失函数为二次函数，那么目标函数的等值线是一个椭圆或圆；而约束条件为L1范数，其等值线为一个菱形。目标函数的等值线与约束边界的图像如下图所示（以二维为例）：
可以看到，在约束条件下的最优解，总是处于约束条件的角上，而约束条件的角上必定会出现一个或多个\(w_{i}=0\)的情况，这就导致了解解稀疏性，在更高维的情况下也是如此。
以L1范数为正则项可以用来筛选特征，得出的非零\(w_{i}\)所对应的特征是关联特征，而那些为零的\(w_{j}\)对应的特征肯定是弱特征。
L2范数
\[||x||_{2}=(\sum\limits_{i}x_{i}^{2})^{\frac{1}{2}}\]L2范数也是应用很广的一种正则化手段，使用L2范数的条件下，目标函数变为：
\[\sum\limits_{i}L(y_{i},f(x_{i};w))+\lambda||w||_{2}\]以上问题也被称为Ridge。在讲L2范数的作用之前，先要了解两个概念：病态(ill-conditioned)矩阵与条件数(condition number)。
下面是一个病态矩阵$Ax=b$的求解示例：
\[\begin{aligned} \begin{bmatrix} 400 & -201\\ -800 & 401 \end{bmatrix} \begin{bmatrix} w_{1}\\ w_{2} \end{bmatrix} = \begin{bmatrix} 200\\ -200 \end{bmatrix} ,\qquad \begin{bmatrix} w_{1}\\ w_{2} \end{bmatrix} = \begin{bmatrix} -100\\ -200 \end{bmatrix}\\ \begin{bmatrix} 401 & -201\\ -800 & 401 \end{bmatrix} \begin{bmatrix} w_{1}\\ w_{2} \end{bmatrix} = \begin{bmatrix} 200\\ -200 \end{bmatrix} ,\qquad \begin{bmatrix} w_{1}\\ w_{2} \end{bmatrix} = \begin{bmatrix} 40000\\ 79800 \end{bmatrix}\\ \end{aligned}\]病态矩阵列向量之间的线性相关性非常高，在稍微改变一下原数据(400 -> 401)的情况下，得出来的解全然不同，这说明病态矩阵的解对$A$与$B$的系数高度敏感，这明显不是我们想要的结果。因为原始数据和真实数据有一定误差，如果因为这些数据中的误差而导致求出来的解与期望解相差巨大，那么这个解就是无用的。
我们用范数来衡量矩阵的病态度。首先假设数据中出现了误差，那么有：
\[A(x+\Delta{x})=b+\Delta{b} \\ Ax+A\Delta{x}=b+\Delta{b} \\ A\Delta{x}=\Delta{b}\]根据范数的三角性质
\[||x*y||\le||x||*||y||\]有：
\[||\Delta{x}||\le||A^{-1}||*||\Delta{b}||\]易得：
\[||A||*||x||\ge||b|| \\ ||x||\ge\frac{||b||}{||A||}\]可得：
\[\frac{||\Delta{x}||}{||x||}\le\frac{||\Delta{b}||}{||b||}*||A^{-1}||*||A||\]同理，对于变化的\(A+\Delta{A}\)，也有：
\[\frac{||\Delta{x}||}{||x+\Delta{x}||}\le\frac{||\Delta{b}||}{||b||}*||A^{-1}||*||A||\]令条件数等于：
\[K(A)=||A||*||A^{-1}||\]它表示了解关于方程系数的敏感度，也侧面体现了矩阵中列向量之间的线性相关强度。
在线性回归中，常用的目标函数是MSE，这种情况下，最优解$w^{*}$可以用正规方程显式地求出来：
\[w^{*}=(X^{T}X)^{-1}X^{T}y\]但是，如果矩阵X的行数要小于列数，在数据上体现为样本数小于特征数，那么$X^{T}X$不满秩且不可求逆，这样就无法求解了。
即使$X^{T}X$满秩可求逆，如果矩阵$X$的条件数$K(X)$很大，即数据的特征之间线性相关性很高，那么求出来的解也是不稳定的，它会因数据集的微小扰动而发生巨大变化。
然后我们看一下加入了L2正则项之后的正规方程(正规方程推导过程待补充)：
\[w^{*}=(X^{T}X+\lambda{I})^{-1}X^{T}y\]因为单位阵是满秩的，所以$X^{T}X+\lambda{I}$一定是可逆的，这样就保证了目标函数一定有最优解。
另一方面，目标函数中加入L2正则项，也将目标函数变成了一个强凸函数(此处没理解)，能加速迭代。
最后来看一个直观的解释，在L2正则下，我们需要求解的最优解为：
\[W=[w_{1}, w_{2},……, w_{n}]=arg\ min(\sum\limits_{i}L(y_{i},f(x_{i};w))) \qquad s.t.||w||_{2}\le{C}\]假设此处用的损失函数为二次函数，那么目标函数的等值线是一个椭圆或圆；而约束条件为L2范数，其等值线为一个圆形。目标函数的等值线与约束边界的图像如下图所示（以二维为例）：
对于L2正则需要注意的几点是：
- L2正则并没有解决数据中特征线性相关的问题
- L2正则引入了偏差，是一种以增加偏差降低方差的方法