1. 什么是L1正则化

$L^2$权重衰减是权重衰减最常见的形式，我们还可以使用其他的方法限制模型参数的规模。 一个选择是使用$L^1$正则化。

形式地，对模型参数$w$的$L^1$正则化被定义为：

$\begin{aligned} \Omega(\theta) = ||{ w }||_1 = \sum_i | w_i | \end{aligned}$

即各个参数的绝对值之和。

2. L1正则化对简单线性回归模型的影响

接着我们将讨论$L^1$正则化对简单线性回归模型的影响，与分析$L^2$正则化时一样不考虑偏置参数。
我们尤其感兴趣的是找出$L^1$和$L^2$正则化之间的差异。 与$L^2$权重衰减类似，我们也可以通过缩放惩罚项$\Omega$的正超参数$\alpha$来控制$L^1$权重衰减的强度。 因此，正则化的目标函数 $\tilde{J}(w;X, y)$如下所示

$\begin{aligned} \tilde{J}(w;X, y) = \alpha \| w \|_1 + J(w;X, y) && (7.20) \end{aligned}$

对应的梯度(实际上是次梯度)：

[success] 次梯度

$\begin{aligned} \nabla_{w} \tilde{J}(w; X, y) = \alpha \text{sign}(w) + \nabla_{w} J(w; X, y) \end{aligned}$

其中$\text{sign}(w)$只是简单地取w各个元素的正负号。

观察公式（7.20），我们立刻发现$L^1$的正则化效果与$L^2$大不一样。 具体来说，我们可以看到正则化对梯度的影响不再是线性地缩放每个$w_i$；而是添加了一项与$\text{sign}(w_i)$同号的常数。 使用这种形式的梯度之后，我们不一定能得到$J(X, y;w)$二次近似的直接算术解（$L^2$正则化时可以）。

[warning] 为什么不能得到$J(X, y;w)$二次近似的直接算术解？使用什么形式的$\tilde J$不应该影响J的计算。

简单线性模型具有二次代价函数，我们可以通过泰勒级数表示。 或者我们可以设想，这是逼近更复杂模型的代价函数的截断泰勒级数。

[success] 泰勒公式
泰勒公式由常数项、一项导数项、二阶导数项、。。。等组成。
如果一个简单模型是二次的，那么它最多只有前三项。
如果一个复杂模型高于二次，那么它除了前三项还会有后面的项。
假设二阶以上的项忽略不计，只保留前三项。那就得到的就是近似这个复杂模型的截断泰勒级数。

在这个设定下，梯度由下式给出

$\begin{aligned} \nabla_{w} \hat{J}(w) = H (w - w^*) && (7.21) \end{aligned}$

[success] 问：这个公式与上一节是一样的。为什么这次有个前提设定？
答：因为正则化项不同。
上文说过，如果目标函数是二次的，那么它的泰勒展开最多二阶，对它的泰勒展开做二阶截断得到的函数与原函数相同。
如果目标函数高于二次，那么它的泰勒展开也多于二阶，对它的泰勒展开做二阶截断得到的函数与原函数的逼近。
这一节是关于正则化的影响，因此J是否是二次不在考虑范围内，只考虑正则化项部分。
L2正则化项$\frac{1}{2}\alpha w^\top w$是二次的，所以可以直接把它泰勒展开，然后根据二次函数的计算公式求它的极值。
L1正则化项是$\alpha ||w||_1$，它是高于二次的。不能直接使用二次函数求极值的公式。因此要先把它近似成二次函数。近似成二次函数的方法就是把它泰勒展开并二阶截断。
文中所谓的“前提设定”就是把泰勒展开并二阶截断。如果没有这个前提设定，它就不是二次函数。无法使用二次函数求极值的公式，也就无法得出公式7.21。

同样，H是J在$w^*$处的Hessian矩阵(关于w)。

由于$L^1$惩罚项在完全一般化的Hessian的情况下，无法得到直接清晰的代数表达式，因此我们将进一步简化假设Hessian是对角的，即$H = \text{diag}([H_{1,1}, ... , H_{n,n}])$，其中每个$H_{i,i}>0$。

[warning] Hessian矩阵是关于导数的矩阵，而L1正则项不是处处可导，所以在某些情况下求不到Hessian需要的导数。但是为什么Hessian的对角线一定能求出来呢？
Hessian是目标函数的关于参数的二阶导数，但也会遇到不是处处可导的问题。
另外即使可导部分，它的二阶导数应该都是0。对角矩阵就成了全0矩阵了。

如果线性回归问题中的数据已被预处理（如可以使用PCA），去除了输入特征之间的相关性，那么这一假设成立。

[success] PCA
PCA可用于去除输入特征之间的相关性。
如果输入特征之间是独立的，那么Hessian的非对角线位置的元素肯定都是0。

[warning] 是不是意味着L1正则化之前最好先对数据做PCA？

我们可以将$L^1$正则化目标函数的二次近似分解成关于参数的求和：

$\begin{aligned} \hat J(w; X, y) = J(w^*; X, y) + \sum_i \Bigg [\frac{1}{2} H_{i,i} (w_i - w_i^*)^2 + \alpha |w_i| \Bigg] \end{aligned}$

[danger] 这次的$\hat J$代表L1正则化目标函数的二次近似，而不是像上一节那样代表基本代价函数的二次近似。

[success] $\tilde J$的二次近似 = J的二次近似 + L1正则项
J的二次近似 = $J(w^*) + \frac{1}{2}(w-w^*)^\top H(w - w^*)$
由于H是对角矩阵，可写成$J(w^*) + \frac{1}{2}H_{i,i}(w-w^*)^2$

如下列形式的解析解（对每一维i）可以最小化这个近似代价函数：

$\begin{aligned} w_i = \text{sign}(w_i^*) ax\Big\{ |w_i^*| - \frac{\alpha}{H_{i,i}} , 0\Big\} \end{aligned}$

[warning] [?]分别对每个wi求导并令导数为0？我没推出这个结果。

对每个i,考虑$w_i^* > 0$的情形，会有两种可能结果：
（1）$w_i^* \leq \frac{\alpha}{H_{i,i}}$的情况。 正则化后目标中的$_i$最优值是$w_i = 0$。 这是因为在方向i上$(w; X, y)$对$\hat J(w; X, y)$的贡献被抵消，$L^1$正则化项将$w_i$推至0。 （2）$w_i^* > \frac{\alpha}{H_{i,i}}$的情况。在这种情况下，正则化不会将$w_i$的最优值推至0，而仅仅在那个方向上移动$\frac{\alpha}{H_{i,i}}$的距离。
$_i^* < 0$的情况与之类似，$L^1$惩罚项使$w_i$接近0(增加$\frac{\alpha}{H_{i,i}}$)或者为0。

3. L1 VS L2

相比$L^2$正则化，$L^1$正则化会产生更稀疏的解。 此处稀疏性指的是最优值中的一些参数为0。 和$^2$正则化相比，$L^1$正则化的稀疏性具有本质的不同。

[info] L2没有稀疏性。所以这句正确的翻译是“L2和L1具有本质的不同”。

公式7.13给出了$L^2$正则化的解$\tilde w$。

[info] 公式12：
$\tilde w = Q(\Lambda+\alpha I)\Lambda Q^\top w^*$

如果我们使用Hessian矩阵$H$为对角正定矩阵的假设（与$L^1$正则化分析时一样），重新考虑这个等式，我们发现 $\tilde{w_i} = \frac{H_{i,i}}{H_{i,i} + \alpha} w_i^*$。 如果$w_i^*$不是零，那么$\tilde{w_i}$也会保持非零。 这表明$L^2$正则化不会使参数变得稀疏，而$L^1$正则化有可能通过足够大的$\alpha$实现稀疏。

[success]
L2中w是按比例缩小，如果w本来就小，那么它的变化也会小，最后也不会到0。
而L1中w是缩小一个定值。与w本身的大小无关。一定次数后，w就变成0了。

由$L^1$正则化导出的稀疏性质已经被广泛地用于特征选择机制。 特征选择从可用的特征子集选择出有意义的特征，化简机器学习问题。 著名的LASSO（Least Absolute Shrinkage and Selection Operator）模型将$L^1$惩罚和线性模型结合，并使用最小二乘代价函数。

[success]
最小二乘代价函数 = 二次代价函数 = 均方误差代价函数

$L^1$惩罚使部分子集的权重为零，表明相应的特征可以被安全地忽略。

在第5.6.1节，我们看到许多正则化策略可以被解释为MAP贝叶斯推断，

[warning] 为什么"许多正则化策略相当于权重是高斯先验的MAP贝叶斯推断"?
MAP贝叶斯推断

特别是$L^2$正则化相当于权重是高斯先验的MAP贝叶斯推断。

[warning] 为什么"$L^2$正则化相当于权重是高斯先验的MAP贝叶斯推断"?

对于$L^1$正则化，用于正则化代价函数的惩罚项$\alpha \Omega(w) = \alpha \sum_i |w_i |$与通过MAP贝叶斯推断最大化的对数先验项是等价的（$w \in R^n$并且权重先验是各向同性的拉普拉斯分布（公式3.26）：

[warning] 为什么"$L^1$正则化相当于权重是高斯先验的MAP贝叶斯推断"? [?] 各向同性的拉普拉斯分布?

$\begin{aligned} \log p(w) = \sum_i \log \text{Laplace}(w_i;0,\frac{1}{\alpha}) = -\alpha ||{w}||_1 + n \log \alpha - n \log 2 \end{aligned}$

因为是关于w最大化进行学习，我们可以忽略$\log \alpha - \log 2$项，因为它们与w无关。