4 L1和l2正则化详解（花书7.1 参数范数惩罚）
7.1 参数范数惩罚
许多正则化方法通过对目标函数 J 添加一个 参数范数惩罚 \Omega (\theta) ，限制模型（如神经网络、线性回归和逻辑回归）的学习能力。将正则化后的目标函数记为：
\tilde{J}(\theta;X,y)=J(\theta;X,y)+\alpha\Omega(\theta) \\
其中 \alpha\in[0,\infty) 是权衡范数惩罚项 \Omega 和标准目标函数 J 相对贡献的超参数。
在神经网络中，参数包括每一层仿射变换的权重和偏置，我们通常只对权重做惩罚而不对偏置做正则惩罚。
- 精确拟合偏置所需的数据通常比拟合权重少得多
- 每个权重会指定两个变量如何相互作用。而每个偏置仅控制一个单变量。这意味着不对偏置进行正则化也不会导致太大的方差
- 正则化偏置参数可能会导致明显的欠拟合。
因此，我们使用向量 w 表示所有应受范数惩罚的权重，而 \theta 表示所有参数（包括 w 和无须正则化的参数）。
7.1.1 \boldsymbol{L^2} 参数正则化
权重衰减 （weight decay）： L^2 参数范数惩罚。向目标函数添加一个正则项 \Omega(\theta)=\frac{1}{2}||w||_2^2 ，使权重更加接近原点。在其他学术圈， L^2 又被称为岭回归或Tikhonov正则。
通过研究正则化后目标函数的梯度，洞察一些权重衰减的正则化表现。
\tilde{J}(w;X,y)=\frac{\alpha}{2}w^{\top}w+J(w;X,y) \\
对应梯度为：
\nabla_w\tilde{J}(w;X,y)=\alpha w+\nabla_wJ(w;X,y) \\
使用单步梯度下降更新权重，即执行以下更新：
w\leftarrow w-\epsilon(\alpha w+\nabla_wJ(w;X,y)) \\
换种写法：
w\leftarrow (1-\epsilon\alpha)w-\epsilon\nabla_wJ(w;X,y) \\
我们可以看到，加入权重衰减后会引起学习规则的修改，即在每步执行通常的梯度更新之前先 收缩 权重向量（将权重向量乘以一个常数因子 \epsilon\alpha<1 ）。这是单个步骤发生的变化。在训练的整个过程会发生什么呢？
1. w^* 未正则化的目标函数最小训练误差时的权重向量
令 w^* 为 未正则化的目标函数 取得最小训练误差时的权重向量，即
w^*=\arg \min_wJ(w)；J最小时的w值 \\
并在 w^* 的领域对 未正则化的目标函数 做二次近似 [1] 。如果目标函数确实是二次的（如以均方误差拟合线性回归模型的情况），则该近似是完美的。近似的 \hat J(\theta) 如下：
\hat J(\theta)=J(w^*)+\frac{1}{2}(w-w^*)^\top H(w-w^*) \\ f(x)=f(x_0)+f'(x_0)x+\frac{f''(x_0)}{2!}(x-x_0)^2
其中 H 是 J 在 w^* 处计算的Hessian矩阵（关于 w ）。
- 因为 w^* 被定义为最优，即梯度消失为 0 ，所以该二次近似中没有一阶项。
- 同样地，因为 w^* 是 J 的一个最优点，我们可以得出 H 是半正定 [2] 的结论。
当 \hat J 取最小时，其梯度 \nabla_w\hat J(w)=H(w-w^*) \\
为0。
2. \tilde{w} 正则化后的目标函数最小训练误差时 的权重向量
\nabla_w\hat J(w)=\alpha w+H(w-w^*)=0 \\ \alpha \tilde w+H(\tilde w-w^*)=0 \\ (\alpha I+H)\tilde w=Hw^* \\ \tilde w=(\alpha I+H)^{-1}Hw^*
当 \alpha 趋向于 0 时，正则化的解 \tilde w 会趋向于 w^*
当 \alpha 增加时会发生什么呢？ 开始高危操作： 因为Hessian H 是实对称 [3] 的，所以可以分解为一个对角矩阵 \Lambda 和一组特征向量的标准正交基 Q 。并且有 H=Q\Lambda Q^\top ，所以：
\begin{align} &\tilde w=(H+\alpha I)^{-1}Hw^* \\ &=(Q\Lambda Q^\top+\alpha I)^{-1} Q\Lambda Q^\top w^* \\ &=(Q\Lambda Q^\top+Q\alpha I Q^\top)^{-1} Q\Lambda Q^\top w^* \\ &=(Q(\Lambda+\alpha I) Q^\top)^{-1} Q\Lambda Q^\top w^* \\ &=Q(\Lambda+\alpha I )^{-1} \Lambda Q^\top w^* \end{align} \\
注意：
- 推导过程需要严谨，待确认
- (\Lambda+\alpha I )^{-1} \Lambda
我们可以看到权重衰减的效果是沿着 H 的特征向量所定义的轴缩放 w^* 。具体来说，我们会根据 \frac{\lambda_i}{\lambda_i+\alpha} 因子缩放与 H 第 i 个特征向量对齐的 w^* 的分量。（可查看图2.3，回顾这种缩放的原理）
7.1.2 \boldsymbol{L^1} 正则化
L^2 权重衰减是 权重衰减最常见的形式；
L^1 限制参数的规模；
形式地，对模型参数 w 的 L^1 正则化定义为，即各个参数的绝对值之和：
\Omega(\theta)=||w||_1=\sum_i|w_i| \\
正则化的目标函数：
\tilde J(w;X,y)=\alpha||w||_1+J(w;X,y) \\
对应的梯度（实际上是次梯度）
\nabla_w\tilde J(w;X,y)=\alpha\;\rm{sign} (w)+\nabla_wJ(w;X,y) \qquad\qquad\qquad(7.20)\\
其中 \mathrm{sign}(w) 只是简单地取 w 各个元素的正负号，例如： \alpha \mathrm{sign} (w)=+\alpha+\alpha -\alpha 。
观察式(7.20)，我们立刻发现 L^1 的正则化效果与 L^2 大不一样。具体来说，正则化对梯度的影响不再是线性地缩放每个 w_i ；而是添加了一项与 \mathrm {sign} (w_i) 同号的常数。使用这种形式的梯度之后，我们不一定能得到 J(w;X,y) 二次近似的直接算术解（ L^2 正则化时可以）。
假设1： 简单的线性模型具有二次代价函数，我们可以通过泰勒级数表示。或者我们可以设想，这是逼近更复杂模型的代价函数的阶段泰勒级数。在这个 设定 下，梯度由下式给出：
\nabla_w\hat J(w)=H(w-w^*)；同样，H是J在w^*处关于w的Hessian矩阵 \\
假设2： 由于 L^1 惩罚项在完全一般化的Hessian的情况下，无法得到直接清晰的代数表达式，因此我们将进一步简化假设Hessian是对角的，即 H=\mathrm{diag}([H_{1,1},...,H_{n,n}]) ，其中每个 H_{i,i}>0 。如果线性回归问题中的数据已被预处理（如可以使用PCA），去除了输入特征之间的相关性，那么这一 假设 成立。
将 L^1 正则化目标函数的二次近似分解成关于参数的求和：
\tilde J(w;X,y)=J(w^*;X,y)+\sum_i[\frac{1}{2}H_{i,i}(w_i-w_i^*)^2+\alpha|w_i|] \\
其中： J(w^*;X,y) 是常数项
如下列形式的解析解（对每一维 i ）可以最小化上面这个近似代价函数 \tilde J ：
w_i=\mathrm{sign}(w_i^*)max\left \{|w_i^*|-\frac{\alpha}{H_{i,i}},0\right \} \\
\begin{align} &\sum_i[\frac{1}{2}H_{i,i}(w_i-w_i^*)^2+\alpha|w_i|] \\ & \Rightarrow\frac{1}{2}(w_i-w_i^*)^2+\frac{\alpha}{H_{i,i}}|w_i| \\ &=\frac{1}{2}[(w_i)^2-2w_iw_i^*+(w_i^*)^2]+\frac{\alpha}{H_{i,i}}|w_i| \\ &=\frac{1}{2}[(w_i)^2+(w_i^*)^2]+\frac{\alpha}{H_{i,i}}|w_i|-w_iw_i^* \end{align}
如果:
- w_i>0 ， \frac{\alpha}{H_{i,i}}|w_i|-w_iw_i^*=(\frac{\alpha}{H_{i,i}}-w_i^*)w_i
- w_i<0 ， \frac{\alpha}{H_{i,i}}|w_i|-w_iw_i^*=-\frac{\alpha}{H_{i,i}}w_i-w_iw_i^*=-(\frac{\alpha}{H_{i,i}}+w_i^*)w_i
- 推导过程需要严谨，待确认
\frac{\alpha}{H_{i,i}}|w_i|-w_iw_i^*=a|w_i|-bw_i ，求 a|w_i|-bw_i 最小值，去掉绝对值号，无非两种情况：
- a|w_i|-bw_i=aw_i-b_wi=(a-b)w_i
- a|w_i|-bw_i=a(-w_i)-bw_i=-(a+b)w_i
- a肯定大于0
- 对b分情况讨论
- b>0
- a-b>0，最为值 w_i=0
- a-b<0，
- b<0
- a+b>0
- a_b<0
相比 L^2 正则化， L^1 正则化会产生更 稀疏（sparse） 的解。 L^1 正则化有可能通过足够大的 \alpha 实现稀疏。由 L^1 正则化导出的稀疏性质已经被广泛地用于 特征选择 。
正则化的目标函数： \tilde J(w;X,y)=\alpha||w||_1+J(w;X,y)
标准目标函数： J(w;X,y)
正则化目标函数的近似： \hat J(w;X,y)
泰勒级数
定义 ：如果 f(x) 在点 x=x_0 具有任意阶导数，则幂级数
\sum_{n=0}^\infty \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n=f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+...+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+...
称为 f(x) 在点 x_0 处的泰勒级数。
在泰勒公式中，取 x_0=0 ，得到的级数 \sum_{n=0}^{\infty}\frac{f^{(n)}(0)}{n!}x^n 称为 麦克劳林 级数。函数 f(x) 的麦克劳林级数是 x 的 幂级数 ，那么这种展开是唯一的，且必然与 f(x) 的麦克劳林级数一致。
半正定
在线性代数里，正定矩阵 (positive definite matrix) 有时会简称为正定阵。在 线性代数 中，正定矩阵的性质类似 复数 中的 正 实数 。
- 复数：我们把形如 z=a+bi （ a，b 均为实数）的数称为复数。
- 实数：实数，是有理数和无理数的总称。数学上，实数定义为与数轴上的实数，点相对应的 数 。
- 正定矩阵 广义定义：设 M 是 n 阶方阵，如果对任何非零向量 \mathbb z ，都有 \mathbb z^\top M \mathbb z>0 ，其中 \mathbb z^\top 表示 \mathbb z 的转置，就称 M 为正定矩阵。
- 半正定矩阵 ：是 正定矩阵 的推广。实对称矩阵 M 称为半正定的，如果二次型 \mathbb z^\top M\mathbb z 半正定，即对于任意不为0的实列向量 \mathbb z ，都有 \mathbb z^\top M\mathbb z\geq0 。
