正则化（Regularization）是机器学习中常用的技术，它可以控制模型的复杂度，减少模型的过拟合。最基本的正则化方法是在代价函数中添加对参数$w$的惩罚项：
其中$J(w; X, y)$是原来的代价函数，$\alpha\Omega(w)$是正则化添加的惩罚项。比较常见的$\Omega(w)$函数有$L_1$范数和$L_2$范数，即：
$L_1$、$L_2$正则化的理解
基于约束条件最优化
对模型系数$w$的求解是通过最小化代价函数$J(w;X,y)$来实现的。一个直观的理解是，参数向量$w$中非0元素越多，模型越复杂，所以为了减少模型复杂度，可以限制参数向量$w$中非0元素的个数，于是就等价于下面的优化条件：
$L_0$范数表示向量中非0元素的个数，而$L_0$范数求解是一个NP问题，为了能够求解，可以放宽约束条件，不严格要求参数向量$w$中的某些元素为0，而是让它们尽量接近0，这样就可以用$L_1$和$L_2$范数来近似$L_0$范数。所以问题就变成了：
利用拉格朗日算子，可以将上述带约束的优化问题转化为不带约束项的优化问题（$L_2$范数进行平方之后比较好处理）：
其中$\alpha > 0$，假设$\alpha$的最优解为$\alpha^\star$，则对上述拉格朗日函数求最小化等价于：
可以发现，上面的最优化问题与最小化$\tilde{J}(w; X, y)$是等价的，因此：
- $L_1$正则化相当于在原代价函数中增加约束条件$|w|_1 \leq C$
- $L_2$正则化相当于在原代价函数中增加约束条件$|w|_2^2 \leq C$
基于最大后验概率
在最大似然估计中，假设参数$w$是未知的，从而最大化如下对数似然函数：
而在最大后验概率中，将参数$w$看作随机变量，也具有某种分布，从而最大化后验概率$P(y|X, w) P(w)$，写成对数形式如下：
所以最大后验概率MAP相比于最大似然估计MLE，多了一项$logP(w)$，而$P(w)$是对参数$w$的先验假设。
如果假设参数$w$服从均值为0、参数为a的拉普拉斯分布，即$P(w_i) = \frac{1}{\sqrt{2a}}exp(\frac{-|w_i|}{a})$，则有：
可以看到与$L_1$正则化相同，所以假设参数$w$服从拉普拉斯分布相当于使用$L_1$正则化。
同理，如果假设参数$w$服从均值为0的高斯分布，即$w_i \backsim N(0, \sigma^2)$，则有：
可以看到与$L_2$正则化相同，所以假设参数$w$服从正态分布相当于使用$L_2$正则化。
综上：
- $L_1$正则化可以通过假设$w$服从拉普拉斯分布，由最大后验概率导出
- $L_2$正则化可以通过假设$w$服从正态分布，由最大后验概率导出
$L_1$、$L_2$正则化的效果
直观理解
为了简化，假设参数向量$w$只有两个分量，$w_1$和$w_2$，并且原始的代价函数是平方误差和。将$w_1$和$w_2$作为坐标轴，可以画出$L_1$范数、$L_2$范数、原始平方误差的等值线。带$L_1$或者$L_2$正则项的目标函数的解就是平方误差项等值线与范数等值线的交点。
从上图可以看出，$L_1$范数的等值线与平方误差项等值线的交点有较大几率出现在坐标轴上，对应于某个$w_i$为0；而$L_2$范数的等值线与平方误差项等值线的交点有较大几率出现在某个象限中，即$w_i$均不为0。因此$L_1$范数更容易得到稀疏解，而$L_2$范数会让$w_i$都趋向于0。
理论分析
假设原目标函数$J(w)$的最优解是$w^\star$，并且二阶可导，则将$J(w)$在$w^\star$进行二阶泰勒展开：
式中H为$J(w)$在$w^\star$处的Hessian矩阵，因为$w^\star$是$J(w)$的最优解，所以其一阶导数为0，所以上式子不含一阶项。当$\hat{J}(w)$取得最小值时，有：
下面分别讨论加入$L_1$和$L_2$正则化时的情况。
对于$L_1$正则化，有：
其最优解满足$H(\tilde{w} - w^\star) + \alpha sign(\tilde{w}) = 0$。假设$H$为对角矩阵，即$H = diag[H_{11}, H_{22},…, H_{nn}], H_{jj} > 0$。此时$w$的不同分量之间没有相关性，$\tilde{w}$的解为：
当$|w_j^\star| \leq \frac{\alpha}{H_{jj}}$时，可知$\tilde{w}_j = 0$，因此$L_1$正则化会使最优解的某些元素为0，从而产生稀疏性；当$|w_j^\star| > \frac{\alpha}{H_{jj}}$时，$\tilde{w}_j$会在原有最优解上偏移一个常数值。
对于$L_2$正则化，有：
设其最优解为$\tilde{w}$，则$H(\tilde{w} - w^\star) + \alpha \tilde{w} = 0$，即$\tilde{w} = (H + \alpha I)^{-1} H w^\star$。由于H是对称矩阵，可对其做特征值分解，即$H = Q \Lambda Q^T$，其中$Q$为正交矩阵，且每一列为$H$的特征向量，代入$\tilde{w}$的表达式可得：$\tilde{w} = Q(\Lambda + \alpha I)^{-1} \Lambda Q^T w^\star$，其中$\Lambda$为对角矩阵，且对角线元素为$H$的特征值$\lambda_j$。
$w^\star$可在$Q$为正交基上作线性展开，并且$\tilde{w}$为$w^\star$在$H$的每个特征向量上的分量以$\frac{\lambda_j}{\lambda_j + \alpha}$比例缩放得到。若$\lambda_j \gg \alpha$，则$w_j^\star$受正则化的影响较小；若$\lambda_j \ll \alpha$，则$w_j^\star$受正则化影响较大，将收缩到接近于0的值。同时，若$w_j^\star \ne 0$，则$\tilde{w}_j \ne 0$，因此不会产生稀疏解的效果。
参考
- 拉普拉斯先验与L1正则化
- L1正则化及其推导
- 深入理解L1、L2正则化
- 《机器学习》周志华