机器学习与优化问题的不同在于：机器学习的目标是在测试集上有较小的泛化误差（generalization error），优化问题是将当前问题最优解决。 为了保证模型在测试集上有较小的误差，甚至有可能增加训练误差，所采取的策略统称正则化（regularization）。正则化有一下两种形式：
- 将限制条件加到模型上
- 将限制条件加到目标函数上
Bias-Variance tradeoff
在模型训练后，最终的模型有如下三种情况：
- 没有得到数据生成过程，欠拟合的，包含偏差（bias）
- 得到了正确的数据生成过程（Perfect!）
- 得到了正确的数据生成过程，同时包含噪声的生成过程即过拟合，方差（variance）主导了估计误差
正则化的作用就是将模型从3转变为2，为什么不直接找到2呢？问题是我们基本不可能知道数据产生的真正模型，能做的是得到一个大的模型但是被恰当地正则化了。
这些限制条件的作用：
- 等价于模型的先验Bayes原理：比如L2正则等价于在权重w是高斯分布先验时，计算MAP (Max a Posterior)
- 用于选择更简单的模型提高泛化能力，即奥卡姆剃刀原理：
如无必要，勿增实体；Bias-variance tradeoff - 用于将欠定的问题（underdetermined）变成determined（正定）例子
- 类似于集成方法（ensemble method），使用不同的假设来解释训练数据
基于参数范数的惩罚项
通过在目标函数上加入一个参数范数的处罚项来限定模型：
$$ \tilde{J}(\theta;X,y)=J(\theta;X,y)+\alpha\Omega(w) $$
其中 $\alpha\in[0, \inf)$ 作为超参数（hyperparameter）平衡惩罚项 $\Omega$相对于 $J$所起的作用。 在深度学习中，一个全连接层可以表达为 $y=wX+b$，其中权重 $w$影响两个变量的相互作用，而 $b$只影响一个变量$y，约束 $b$ 有可能导致欠拟合，所以没对 $b$ 作约束。在以下分析中，$\theta$包含所有参数，$w$是去除bias之后的参数。
L2范数正则
L2正则项定义如下:
$$ \Omega(w)=\frac{1}{2}||w||_2^2 $$
L2范数正则通常称为权重衰减（weight decay），L2即向量的2阶范数是表象，weight decay是其本质名字。
一个简单的解释
使用一阶梯度优化目标问题时，梯度中增加了一项
$$ \frac{\partial{\tilde{J}(w)}}{\partial w}=\frac{\partial{J(w)}}{\partial w}+\alpha w=gradient + \alpha w $$
在做梯度更新时,
$$ w \to (1-e\alpha)w-gradient $$
每一步梯度更新时，之前在权重都要缩小一定比例。
更深入的解释
在无约束问题$J$取得最小值$w^*$处做泰勒展开，使用二阶近似（：如果J恰好是二阶，就不是近似了'_>'
$$ \tilde{J}(w)=J(w^*)+0+\frac{1}{2}(w-w^*)^TH(w-w^*) $$
其中 $H$ 是 $J$ 关于 $w$的Hessian矩阵在 $w^*$的取值。 因为在 $J$ 在展开值 $w^*$处是最小值，所以此处一阶梯度为0，$H$是半正定阵，实对称阵（TODO：为什么？）。我们计算这个近似表达式的最小值，即对参数 $w$求梯度使其为0：
$$ \frac{\partial{\tilde{J}}}{\partial{w}}=H(w-w^*)=0 $$
如果$J$加上正则项，则对应的近似式的梯度
$$ \alpha{w}+H(w-w^*)=0 $$
求解可得：
$$ w=(\alpha{I}+H)^{-1}Hw^* $$
因为$H$是实对称阵可以做特征值分解 $H=Q\Lambda{Q^T}$，代入上式后
$$ w=Q(\Lambda+\alpha{I})^{-1}\Lambda{Q^{T}}w^* $$
这就是对 $w^*$ 中的变量，在$i$-th方向被缩放 $\frac{\lambda_i}{\lambda_i+\alpha}$，这是一个小于1的值，L2 正则式就是要权重衰减。从中我们可以看出，当特征值大时,衰减的幅度要小于特征值小的方向。当 $\lambda_i \ll \alpha$ 时，变量会缩小的接近于0。
In the first dimension, the eigenvalue of the Hessian of $J$ is small. The objective function does not increase much when moving horizontally away from $w^∗$. Because the objective function does not expressa strong preference along this direction, the regularizer has a strong effect on this axis.The regularizer pulls w1 close to zero.
Note：特征值小与函数取值的椭圆等高线可不是一个概念，具体例子参考ipython notebook。
具体的应用: 线性回归
基本分析是一样的，针对此问题关键点的理解 $X^TX$可以类比特征的协方差矩阵，所以特征值对应特征的方差：特征方差越大，其对应的权重就不容易被 weight decay。
L1范数正则
L1正则项定义:
$$ \Omega(x)=\alpha ||w||_{1} =\alpha \sum_i{|w_i|} $$
一个简单解释
对目标函数计算子梯度（sub-gradient）：
$$ \partial_{w}{\tilde{J}(w;X,y)}=\alpha \cdot {sign(w)}+\partial_{w}{J(w;X,y)} $$
（实际上当$w\neq0$时，其梯度为$sign(w)$；当$w=0$时，子梯度的取值为$[-1, 1]$，参考XXX）。 我们可以看到：现在梯度更新时，不再像L2正则更新一个$w$的比例，而是一个固定的大小，方向与原权重有关。
更深入的解释
类比L2正则的分析方法，我们同样可以对目标函数做泰勒级数展开，只取二阶做近似。 即使如此，对于一般的Hessian矩阵$H$也不好分析，此处做进一步的简化；假定$H$是一个对角阵，$H=diag([H_{1,1},...,H_{n,n}])$，其中 $H_{i,i}>0$，此假设成立的条件是输入的特征之前没有相关性。这样目标函数可以简化为
$$ \tilde{J}(w;X,y)=J(w^*;X,y) +\sum_i\left[\frac{1}{2}H_{i,i}(w_i-w_i^*)^2+sign|w_i|\right] $$
最小化这个目标函数是有解析解的，因为$l1-norm$ 是可分解的，对每一个$w_i$可得
$$ w_i=sign(w_i^*) \cdot \max \left( |w_i^*| -\frac{\alpha}{H_{i,i}},0 \right) $$
从上式中，我们可以看到 $w_i$ 在一定情况下会被压缩为0，另外的情况是只是有一定的缩小，
对比L2正则，在L2中如果 $w_i$不为0更新后也不为0，但在L1中有可能更新为0，所以L1能得到一个更稀疏（sparse）的解。这个特性可以用来做为一个feature selection方法，比如LASSO模型（least abssolute shrinkage and selection operator）：一个线性模型及最小平方损失函数结合一个L1惩罚项。
同样，L1 正则也可以理解为Bayes里的MAP Bayes inference，对应先验是isotropic Laplace distribution，Refer XXX。