机器学习中的正则化[一]

监督学习（利用标号信息）的本质就是规则化参数的同时最小化误差（minimize  error while regularizing  parameters）。最小化误差是为了让我们的模型拟合我们的训练数据，而规则化参数是防止我们的模型过分拟合我们的训练数据。

因为参数太多，会导致我们的模型复杂度上升，容易过拟合，也就是我们的训练误差会很小。但训练误差小并不是我们的最终目标，我们的目标是希望模型的测试误差小，也就是能准确的预测新的样本。所以，我们需要保证模型“简单”的基础上最小化训练误差，这样得到的参数才具有好的泛化性能（也就是测试误差也小），而模型“简单”就是通过规则函数来实现的。规则项的使用还可以约束我们的模型的特性。这样就可以将人对这个模型的先验知识融入到模型的学习当中，强行地让学习到的模型具有人想要的特性，例如稀疏、低秩、平滑等等。从贝叶斯估计的角度来看，规则化项对应于模型的先验概率。民间还有个说法就是，规则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项(regularizer)或惩罚项(penalty term)。

1、范数与优化问题

$l_{\infty}$范数:  向量各个元素绝对值最大那个元素的绝对值，

$l_{1}$范数：向量各个元素绝对值之和

$l_{0}$范数：向量中非0的元素的个数

首先让我们看一个优化问题，$D=[d_{1},...,d_{p}]$为一组基列向量（对应于人脸识别问题，可以是不同人脸同一位置的图像块组成的像素值形成的列向量），对于一个输入列向量$x$（输入人脸这一位置的图像块），通过寻找一个稀疏向量$\alpha\in R_{p}$使得$x$为这些基向量的稀疏线性组合，表达如下：

$min_{\alpha\in R^{p}} \frac{1}{2} \lVert x-D\alpha\rVert _{2}^{2} \quad s.t.\lVert \alpha\rVert_{0} \leq k$              1）

当$D=[d_{1},...,d_{p}]$为一组正交小波基即$D^{T}D=I$，式1）等价于

$min_{\alpha\in R^{p}} \frac{1}{2} \lVert D^{T}x-\alpha \rVert _{2}^{2} \quad s.t.\lVert \alpha\rVert_{0} \leq k$

定义向量$\beta\doteq D^{T}x$ $\in R_{p}$，所以$x= D\beta$ 因为$D$是一个正交阵。为了获得最佳的稀疏近似，取$k$个最大的系数$\{\lvert \beta[1]\rvert,...,\lvert \beta[p]\rvert\}$的值。

但是1）L0范数很难优化求解（NP难问题），2）L1范数是L0范数的最优凸近似，而且它比L0范数要容易优化求解。上述问题转化为：

$min_{\alpha\in R^{p}} \frac{1}{2} \lVert x-D\alpha\rVert _{2}^{2} \quad s.t.\lVert \alpha\rVert_{1} \leq \mu$         2）

这个也就是著名的LASSO。$l_{1}$范数保证解的稀疏性，参数$\mu$控制数据拟合与稀疏度间的tradeoff。实际上，减小$\mu$值大小会导致解更为稀疏即有更多零项。

• Basis Pusuit:

$min_{\alpha\in R^{p}} \frac{1}{2} \lVert x-D\alpha\rVert _{2}^{2} +\lambda \lVert \alpha\rVert_{1}$             3）

在这里，$l_{1}$范数作为惩罚项而非约束项。

Fig.1 Two examples of regularization paths for the Lasso/Basis Pursuit

如图，当$\lambda=0$，solution is dense；而增大$\lambda$，越来越多的变量被置0，但是$\lambda$与解的稀疏度间并不一定是单调关系。有些情况下增大$\lambda$ 会产生一个denser solution。

这里如果我们采用重构误差作为约束条件来寻求一个稀疏重构系数，表达形式如下：

$min_{\alpha\in R^{p}} \lVert \alpha\rVert_{1} \quad s.t.\lVert x-D\alpha\rVert _{2}^{2} \leq \epsilon$                4）

这种表达形式非常有用，如果我们对误差分布有先验知识，参数$\epsilon$较为容易选择。对于无噪声的问题(noiseless），上式改写如下：

$min_{\alpha\in R^{p}} \lVert \alpha\rVert_{1} \quad s.t. x=D\alpha$      5）

式3）的解集收敛于式5）的解当$\lambda$ 趋于$0^{+}$时。

这里损失函数并不定义是在最小二乘（平方）意义下，如下：

$min_{\alpha\in R^{p}} f(\alpha) +\lambda \lVert \alpha\rVert_{1}$      6）

where $f:R^{p}\rightarrow R$ 为损失函数。

说了这么多，我们还是想知道$l_{1}$范数为什么会导致稀疏性，$l_{0}$范数的稀疏性显而易见。

首先引出一个说法：任何的规则化算子，如果他在W_i=0的地方不可微，并且可以分解为一个“求和”的形式，那么这个规则化算子就可以实现稀疏。这说是这么说，$\alpha$的$l_{1}$范数是绝对值，|w|在w=0处是不可微，但这还是不够直观。

2、$l_{1}$范数的稀疏性

临界点角度分析

对于正交阵$D$，$l_{1}$分解问题可以通过"soft-thresholding"保证封闭形式的解析解。

对于$d_{i}^{T}x$内积小于$\lambda$，其对应的$\alpha^{*}[i]$等于0。所以解$\alpha^{*}$的零项随着$\lambda$单调递增。

对于非正交阵$D$，这种单调关系并不一定保证。但是实际中，$l_{1}$范数的稀疏性仍旧有效。对于泛化的$l_{1}$正则化问题进一步了解，$min_{\alpha\in R^{p}} f(\alpha) +\lambda \lVert \alpha\rVert_{1}$  ，$f$可微，有以下定理：

当$\lambda\ge \lVert\bigtriangledown f(0)\rVert_{\infty}$时，该最优性条件满足对于$\alpha^{*}=0$，所以可以得到最稀疏的解。

物理意义分析

在图像处理或计算机视觉领域，能量代表着一个最小化问题的目标函数。负的能量梯度代表着一种趋势。考虑一维$l_{1}$正则化问题

$min_{\alpha\in R} \frac{1}{2} (\beta-\alpha)^{2}+\lambda \lvert \alpha\rvert$             7）

从能量最小化的角度出发，$l_{1}$惩罚项可以看作为驱动$\alpha$以常值$\lambda$朝$\beta$前进。

利用平方$l_{2}$惩罚项或者岭回归惩罚项代替，表达如下：

$min_{\alpha\in R} \frac{1}{2} (\beta-\alpha)^{2}+\frac{\lambda}{2} \alpha^{2}$             8）

二次能量$\frac{\lambda}{2} \alpha^{2}$  的微分为$\lambda\alpha$，$l_{2}$惩罚项可以看作为驱动$\alpha$以$\lambda\alpha$朝$\beta$前进。

所以$l_{2}$惩罚项最大的劣势就在于当$\alpha\rightarrow 0$时，相对应的force就很小，从而无法保证稀疏性。

从解析角度，式7)的解为0当$\lvert \beta\rvert\leq \lambda$时。而式8保证闭集解$\alpha^{*}=\beta/(1+\lambda)$。显然，这个解永远不会为0。

弹簧的弹性势能为二阶形式，而重力势能在地球表面近似线形。

几何形式分析

$l_{1}$norm 可以理解为$l_{1}$-ball $\{\alpha \in R^{p}:\lVert\alpha\rVert_{1}\leq \mu\}$

$min_{\alpha\in R^{p}} \frac{1}{2} \lVert \beta-\alpha\rVert _{2}^{2} \quad s.t.\lVert \alpha\rVert_{1} \leq \mu$ where $\beta\doteq D^{T}x$。如果D为非正交阵，经典解法为projected gradient method。