L1正则化比L2正则化易得稀疏解的三种解释

正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项或罚项，正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。例如模型参数向量的范数，正则化的一般形式如下^[1]：

$$\min \limits_{f\in\mathcal{F}} \left( \cfrac{1}{N} \sum_{i=1}^{N} L(y_i,f(\boldsymbol x_i))+\lambda J(f) \right) \qquad (A.1)$$

其中，第1项是经验风险，第2项是正则化项，$\lambda$为调整正则化项权重的系数。常用的正则化项是模型参数向量的$L_1$范数和$L_2$范数，分别称作L1正则化和L2正则化。以线性回归为例，其带L1正则化项的损失函数为：

$$J(\boldsymbol w)=\cfrac{1}{N} \sum_{i=1}^{N} (\boldsymbol w^T\boldsymbol x_i-y_i)^2+\lambda \Vert\boldsymbol w \Vert_1$$

其中$\Vert\boldsymbol w \Vert_1$为$\boldsymbol w$的$L_1$范数。同理可得带L2正则化项的损失函数为：

$$J(\boldsymbol w)=\cfrac{1}{N} \sum_{i=1}^{N} (\boldsymbol w^T\boldsymbol x_i-y_i)^2+\lambda \Vert\boldsymbol w \Vert_2^2$$

其中$\Vert\boldsymbol w \Vert_2$为$\boldsymbol w$的$L_2$范数。使用L1正则化或L2正则化的线性回归也称作LASSO回归^[2]或岭回归^[3]。
L1正则化和L2正则化最主要的不同之处在于前者更易得稀疏解，解释如下^[4]：

从优化问题的角度：

式(A.1)可以看作如下优化问题：

$$\begin{aligned} & \min\limits_{\boldsymbol w} \quad L_{emp}(\boldsymbol w) \\ & s.t. \quad \lambda L_{reg}(\boldsymbol w) \leq \eta \end{aligned}$$

其中$L_{emp}(\boldsymbol w)$是经验风险，$L_{reg}(\boldsymbol w)$是正则化项，$\eta$是自行设定的容忍度，此优化问题可以描述为：把$\boldsymbol w$的解限制一定范围内，同时使得经验风险尽可能小。L1正则化和L2正则化画图表示如下：

其中，左图为L1正则化，右图为L2正则化，$\boldsymbol w^*$是$\boldsymbol w$的解，蓝色等高线为经验风险$L_{emp}(\boldsymbol w)$的取值，红色等高线为正则化项$L_{reg}(\boldsymbol w)$的取值，黄色区域是红色等高线的变化范围，也即$\boldsymbol w^*$的取值范围，默认内环等高线的值更小。从图中可以看出，红色等高线和蓝色等高线的切点即为优化问题的解$\boldsymbol w^*$，而且L1正则化相比于L2正则化更容易使得切点落在$\boldsymbol w$某个维度$w_i$的坐标轴上，从而导致另一个维度$w_j$的取值为0，从而更容易得到具有稀疏性的$\boldsymbol w^*$。

从梯度的角度：

L1正则化的损失函数一般形式为：

$$J(\boldsymbol w)=L(\boldsymbol w)+\lambda \sum \vert w_i \vert \qquad (B.1)$$

L2正则化的损失函数一般形式为：

$$J(\boldsymbol w)=L(\boldsymbol w)+\lambda \sum (w_i)^2 \qquad (B.2)$$

对式(B.1)关于$\boldsymbol w$某个维度$w_i$求偏导可得：

$$\cfrac{\partial J(\boldsymbol w)}{\partial w_i}=\cfrac{\partial L(\boldsymbol w)}{\partial w_i}+\lambda sign (w_i)$$

对式(B.2)关于$\boldsymbol w$某个维度$w_i$求偏导可得：

$$\cfrac{\partial J(\boldsymbol w)}{\partial w_i}=\cfrac{\partial L(\boldsymbol w)}{\partial w_i}+2\lambda w_i$$

当使用梯度下降法等此类根据$\boldsymbol w$的梯度来调整$\boldsymbol w$的算法时，若用L1正则化，$\boldsymbol w$的某个维度$w_i$的更新公式为：

$$w_i:=w_i-\eta\cfrac{\partial J(\boldsymbol w)}{\partial w_i}=w_i-\eta\cfrac{\partial L(\boldsymbol w)}{\partial w_i}-\eta\lambda sign (w_i)$$

其中$\eta$为自行设定的学习率，从上式可以看出，$\eta\lambda sign (w_i)$的取值恒为$\pm\eta\lambda$，与$w_i$的大小无关，所以这就会导致即使$w_i$已经很小了但仍然以较高的梯度在变化，从而容易使得$w_i$取到0；若用L2正则化，则更新公式为：

$$w_i:=w_i-\eta\cfrac{\partial J(\boldsymbol w)}{\partial w_i}=w_i-\eta\cfrac{\partial L(\boldsymbol w)}{\partial w_i}-2\eta\lambda w_i$$

显然此式中的$2\eta\lambda w_i$的大小与$w_i$相关，所以当$w_i$很小时变化的梯度也很小，不容易取到0，也就不容易得到稀疏解。

从最大后验估计的角度：

由于对概率模型来说，其模型的训练过程就是参数估计过程，而对于参数估计，统计学界的两个学派分别提供了不同的解决方案：频率主义学派认为参数虽然未知，但却是客观存在的固定值，因此，可以通过优化似然函数等准则来确定参数值，其主张使用的参数估计方法为极大似然估计（Maximum Likelihood Estimation，MLE）；而贝叶斯学派则认为参数是未观察到的随机变量，其本省也可有分布，因此，可假设参数服从一个先验分布，然后基于观察到的数据来计算参数的后验分布，其主张使用的参数估计方法为最大后验估计（Maximum A Posteriori，MAP）。下面举例对比两种参数估计方法的异同^[5]：假设含有N个独立同分布的样本集合为$D=\{(\boldsymbol x_1,y_1),(\boldsymbol x_2,y_2),…,(\boldsymbol x_N,y_N)\}$，极大似然估计法的思路如下：

$$\hat{\boldsymbol{w}} = \mathop{\arg\max}_{\boldsymbol{w}}P(D|\boldsymbol{w})$$

其中，$P(D|\boldsymbol{w})$表示样本集合$D$中全体样本的联合概率，通常可以用一个关于参数$\boldsymbol{w}$的函数来进行表示，并且将该函数称之为似然函数。最大后验估计法的思路如下：

$$\hat{\boldsymbol{w}} = \mathop{\arg\max}_{\boldsymbol{w}}P(\boldsymbol{w}|D)$$

由贝叶斯公式可知$P(\boldsymbol{w}|D)=\cfrac{P(D|\boldsymbol{w})P( \boldsymbol{w})}{P(D)}$，代入上式可得：

$$\begin{aligned} \hat{\boldsymbol{w}} &= \mathop{\arg\max}_{\boldsymbol{w}}\cfrac{P(D|\boldsymbol{w})P( \boldsymbol{w})}{P(D)}\\ &= \mathop{\arg\max}_{\boldsymbol{w}}P(D|\boldsymbol{w})P( \boldsymbol{w})\\ \end{aligned}$$

其中，$P(\boldsymbol{w})$为对参数$\boldsymbol{w}$的先验估计。显然，如果对$\boldsymbol{w}$的先验估计为均匀分布的话

$$\mathop{\arg\max}_{\boldsymbol{w}}P(D|\boldsymbol{w})P( \boldsymbol{w})=\mathop{\arg\max}_{\boldsymbol{w}}P(D|\boldsymbol{w})$$

最大后验估计等价于极大似然估计，但是如果假设参数$\boldsymbol{w}$的先验估计为均值为0方差为$\sigma^2$的高斯分布的话，最大后验估计等价于极大似然估计+L2正则化项，具体推导如下：

$$\begin{aligned} \hat{\boldsymbol{w}} &= \mathop{\arg\max}_{\boldsymbol{w}}P(D|\boldsymbol{w})P( \boldsymbol{w})\\ &= \mathop{\arg\max}_{\boldsymbol{w}}\ln \left( P(D|\boldsymbol{w})P( \boldsymbol{w}) \right) \\ &= \mathop{\arg\min}_{\boldsymbol{w}}-\ln \left( P(D|\boldsymbol{w})P( \boldsymbol{w}) \right) \\ &= \mathop{\arg\min}_{\boldsymbol{w}}-\ln P(D|\boldsymbol{w})-\ln P( \boldsymbol{w}) \\ &= \mathop{\arg\min}_{\boldsymbol{w}} J(\boldsymbol{w}) \\ \end{aligned}$$

由于

$$\begin{aligned} P(\boldsymbol{w}) &= \prod_{i=1}^{d}P(w_i)=\prod_{i=1}^{d}\cfrac{1}{\sqrt{2\pi}\sigma} \mathrm{exp}\left(-\cfrac{w_i^2}{2\sigma^2}\right) \\ \ln P(\boldsymbol{w}) &= \sum_{i=1}^{d}\ln\cfrac{1}{\sqrt{2\pi}\sigma} \mathrm{exp}\left(-\cfrac{w_i^2}{2\sigma^2}\right) \\ &= d \cdot \ln\cfrac{1}{\sqrt{2\pi}\sigma} -\cfrac{1}{2\sigma^2} \cdot \sum_{i=1}^{d}w_i^2 \\ &= d \cdot \ln\cfrac{1}{\sqrt{2\pi}\sigma} -\cfrac{1}{2\sigma^2} \cdot \Vert\boldsymbol{w}\Vert_2^2 \end{aligned}$$

所以

$$J(\boldsymbol{w}) = -\ln P(D|\boldsymbol{w})-d \cdot \ln\cfrac{1}{\sqrt{2\pi}\sigma} +\cfrac{1}{2\sigma^2} \cdot \Vert\boldsymbol{w}\Vert_2^2$$

由于$d \cdot \ln\cfrac{1}{\sqrt{2\pi}\sigma}$与$\boldsymbol{w}$无关，可以略去，所以

$$J(\boldsymbol{w})= -\ln P(D|\boldsymbol{w})+\cfrac{1}{2\sigma^2} \cdot \Vert\boldsymbol{w}\Vert_2^2$$

同理可得采用拉普拉斯分布先验的最大后验估计=极大似然估计+L1正则化项。观察高斯分布和拉普拉斯分布的概率密度函数图像可知，拉普拉斯分布更为稀疏，也即取到0的概率更大，所以其生成的参数$\boldsymbol{w}$更为稀疏。

图中高斯分布和拉普拉斯分布的均值和方差均相同
L1正则化和L2正则化还有如下不同之处：

• L1正则化自带特征选择的功能，这是由于L1正则化易得稀疏解导致的，因为稀疏解$\boldsymbol w^*$的某些维度$w_i=0$，从而达到了特征选择的功能；
• L1正则化的解不稳定，也即可能会有多个解，这是因为L1正则化的红色等高线容易与经验风险的蓝色等高线产生多个切点，例如上图中的蓝色等高线若不为圆形曲线，而是直线时，此时极有可能与L1正则化的红色等高线重合，从而产生多个解；
• L1正则化不易求解，这是因为绝对值函数通常都不好求解；
• L1正则化相对于L2正则化对异常值敏感度低，这是因为当$\vert w_i \vert>1$时，$\sum\vert w_i \vert < \sum(w_i)^2$，从而对异常值敏感度低。

参考文献：

[1] 李航.《统计学习方法》
[2] Lasso (statistics)
[3] Ridge regression
[4] l1 相比于 l2 为什么容易获得稀疏解？
[5] MLE, MAP, Bayes classification