Regularization and Variable Selection via the Elastic Net

关键词：group effects, p ≫ n problem, LASSO, variable selection

---

常规的线形回归有两个比较重要的视角

1. 未知数据的预测精度：预测精度的问题 如果响应变量和预测变量之间有比较明显的线性关系，最小二乘回归会有很小的偏倚，特别是如果观测数量n远大于预测变量p时，最小二乘回归也会有较小的方差。但是如果n和p比较接近，则容易产生过拟合；如果n<p，最小二乘回归得不到有意义的结果。

2. 模型的解释性：大家都倾向于选择一个简单的模型能让大家更专注在自变量及因变量之间的关系上

Hoerl & Kennard 1988 提出岭回归的方式，在L2正则权重的约束下对RSS目标进行最小化。岭回归因其固有弱点，并不会舍弃变量，并不能提供一个精简的模型。Tibshirani (1996) 提出了L1罚项的正则方式(lasso).正因为L1的稀疏表示，lasso出现在了更多的现代数据分析的变量选择中。但L1依然有它的弱点(limitations)

1. 在变量远大于样本数的任务中(p ≫ n problem). 由于L1的凸优化问题，

---

Review:

L0范数

L0范数表示向量中非零元素的个数：

也就是如果我们使用L0范数，即希望w的大部分元素都是0. （w是稀疏的）所以可以用于ML中做稀疏编码，特征选择。通过最小化L0范数，来寻找最少最优的稀疏特征项。但不幸的是，L0范数的最优化问题是一个NP hard问题，而且理论上有证明，L1范数是L0范数的最优凸近似，因此通常使用L1范数来代替。

L1范数 -- (Lasso Regression)

L1范数表示向量中每个元素绝对值的和：

L1范数的解通常是稀疏性的，倾向于选择数目较少的一些非常大的值或者数目较多的insignificant的小值。

L2范数 -- (Ridge Regression)

L2范数即欧氏距离：

L2范数越小，可以使得w的每个元素都很小，接近于0，但L1范数不同的是他不会让它等于0而是接近于0.

L1的稀疏解释：

https://www.zhihu.com/question/37096933/answer/70426653

https://blog.csdn.net/b876144622/article/details/81276818

两种 regularization 能不能把最优的 x 变成 0，取决于原先的损失函数在 0 点处的导数。

如果本来导数不为 0，那么施加 L2 regularization 后导数依然不为 0，最优的 x 也不会变成 0。

引入L2正则项，在0处的导数 ：

而施加 L1 regularization 时，只要 regularization 项的系数 C 大于原先损失函数在 0 点处的导数的绝对值，x = 0 就会变成一个极小值点。

---

NP-hard 问题

售货员旅行问题 (traveling salesman problem)，是最具有代表性的NP问题之一。假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销 C 块钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？ 

推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排! 这将是个天文数字。 

这个天文数字到底有多大？目前的方法接近一个一个的排着试，还没有找到更好可以寻得最短路径的方法。对七个城而言，共有 6!=720 个排法，还比较简单；，但若有 20 个城，则排法就有 19! 种。因故在排列组合里 n! 写起来轻松。但 1.21∗10171.21∗1017 是一个大得不得了的数字。若每秒钟排一次，要排 3.84∗1093.84∗109 年（一年约为 3.15∗1073.15∗107 秒），即使使用计算器，每秒排一百万次（不容易做到）也得重做三千年才能找到答案。「生也有涯，知也无涯」，想不到区区二十个城，要三十个世纪才能找到答案。