所谓的L1正则化优化问题,就是如下带$L_1$正则化的最小化问题:

因为$L_1$正则项的不可微性,使得利用梯度相关方法直接求解上面的优化问题有困难。下面介绍的方法,是把这个$L_1$优化问题,变换为多个$L_2$正则化优化问题逐步迭代求解。

把不等式$|ab| \leq \frac12 \left( a^2 + b^2 \right)$应用到$\theta$向量中的每个元素:

就有:

其中$\mathbf{C}\triangleq \text{diag}(c)$为对角值为$c_j$的对角矩阵,而$\mathbf{C}^{-1}$表示它的逆矩阵。此不等式在所有的$|\theta_j| = c_j$时成为等式。

记:

根据前面的不等式,有$F(\theta) \leq \tilde{F}(\theta; c)$。所以可以通过最小化$\tilde{F}(\theta; c)$来达到降低$F(\theta)$的目的。

总结下,我们可以通过以下的迭代求解方法来最小化$F(\theta)$:

  1. 选定初始的参数$\theta^{(0)}$;
  2. 对于第$k$次($k \geq 1$)迭代,求解下面的$L_2$正则优化问题来获得新的$\theta_k$:

    也就是把前面不等式中的$c$取为迭代前一步的解的绝对值$|\theta^{(k-1)}|$。因为$\theta^{(k-1)}$的元素可能为0,所以$\tilde{F}(\theta; |\theta^{(k-1)}|)$中的逆对角矩阵$\mathbf{\Theta^{(k-1)}}^{-1}$要替换为$\mathbf{\Theta^{(k-1)}}^{\dagger}$,也即$\mathbf{\Theta^{(k-1)}}$的广义逆矩阵1。因为$\mathbf{\Theta^{(k-1)}}$是对角矩阵,所以$\mathbf{\Theta^{(k-1)}}^{\dagger}$也是对角矩阵,而且它的第$j$个对角元素为:

  3. 重复上一步迭代过程,直到收敛。

因为有:

所以上面的迭代算法能保证目标函数$F(\theta)$单调下降。下面的图给出了直观理解:

迭代算法直观解释

当然,因为是迭代求解,整个求解算法可能效率并不高。欢迎有经验的同学给出更详细的说明。

更详细的资料可见参考文献2

References

  1. 广义逆矩阵。 

  2. 杉山将,《图解机器学习》第5.2节,2015。