1700537017
“L1正则化与稀疏性”是一道在算法工程师面试时非常流行的题目。这道题能够从细节入手，考察面试者对于机器学习模型各个相关环节的了解程度。很多面试者能给出一些大概的理解，但是要想深入且清晰的解答这道题也并非易事。下面我们尝试从不同角度给出该问题的解答。
1700537018
1700537019
在正式开始之前，我们对问题做进一步的解释。有一些初学者可能会对问题本身存在疑问——为什么希望模型参数具有稀疏性呢？稀疏性，说白了就是模型的很多参数是0。这相当于对模型进行了一次特征选择，只留下一些比较重要的特征，提高模型的泛化能力，降低过拟合的可能。在实际应用中，机器学习模型的输入动辄几百上千万维，稀疏性就显得更加重要，谁也不希望把这上千万维的特征全部搬到线上去。如果你真的要这样做的话，负责线上系统的同事可能会联合运维的同学一起拿着板砖来找你了。要在线上毫秒级的响应时间要求下完成千万维特征的提取以及模型的预测，还要在分布式环境下在内存中驻留那么大一个模型，估计他们只能高呼“臣妾做不到啊”。知道了面试官为什么要问这个问题后，下面进入正题，寻找L1正则化产生稀疏解的原因。
1700537020
1700537021
知识点
1700537022
1700537023
微积分，线性代数
1700537024
1700537025
问题 L1正则化使得模型参数具有稀疏性的原理是什么？
1700537026
1700537027
难度：★★★☆☆
1700537028
1700537029
分析与解答
1700537030
1700537031
■ 角度1：解空间形状
1700537032
1700537033
机器学习的经典之作给出的解释无疑是权威且直观的[16]，面试者给出的答案多数也是从这个角度出发的。在二维的情况下，黄色的部分是L2和L1正则项约束后的解空间，绿色的等高线是凸优化问题中目标函数的等高线，如图7.6所示。由图可知，L2正则项约束后的解空间是圆形，而L1正则项约束的解空间是多边形。显然，多边形的解空间更容易在尖角处与等高线碰撞出稀疏解。
1700537034
1700537035
1700537036
1700537037
1700537038
图7.6 L2正则化约束与L1正则化约束
1700537039
1700537040
上述这个解释无疑是正确的，但却不够精确，面试者往往回答过于笼统，以至于忽视了几个关键问题。比如，为什么加入正则项就是定义了一个解空间约束？为什么L1和L2的解空间是不同的？面试官如果深究下去，很多面试者难以给出满意的答案。其实可以通过KKT条件给出一种解释。
1700537041
1700537042
事实上，“带正则项”和“带约束条件”是等价的。为了约束w的可能取值空间从而防止过拟合，我们为该最优化问题加上一个约束，就是w的L2范数的平方不能大于m：
1700537043
1700537044
1700537045
1700537046
1700537047
（7.55）
1700537048
1700537049
为了求解带约束条件的凸优化问题，写出拉格朗日函数
1700537050
1700537051
1700537052
1700537053
1700537054
（7.56）
1700537055
1700537056
若w*和λ*分别是原问题和对偶问题的最优解，则根据KKT条件，它们应满足
1700537057
1700537058
1700537059
；
1700537060
1700537061
（7.57）
1700537062
1700537063
仔细一看，第一个式子不就是w*为带L2正则项的优化问题的最优解的条件嘛，而λ*就是L2正则项前面的正则参数。
1700537064
1700537065
这时回头再看开头的问题就清晰了。L2正则化相当于为参数定义了一个圆形的解空间（因为必须保证L2范数不能大于m），而L1正则化相当于为参数定义了一个棱形的解空间。如果原问题目标函数的最优解不是恰好落在解空间内，那么约束条件下的最优解一定是在解空间的边界上，而L1“棱角分明”的解空间显然更容易与目标函数等高线在角点碰撞，从而产生稀疏解。
1700537066