1.前言

带有约束条件的最小二乘学习法和交叉验证的组合，在实际应用中是非常有效的回归方法。然而，当参数特别多的时候，求解各参数以及学习得到的函数的输出值的过程，都需要耗费大量的时间。

这篇博客主要介绍可以把大部分都设置为0的稀疏学习算法，因为大部分参数都设置为0，所以就可以快速地求解各参数以及学习得到的函数。

2.L1约束的最小二乘学习法

在L2约束的最小二乘学习法中，L2范数有一定的约束作用。而在稀疏学习中，则使用L1来进行相应的条件约束。如下所示：

向量Θ=（Θ1，...,Θb）'的L1范数||Θ||1是作为向量Θ的各元素的绝对值和来进行定义的：

满足||Θ||1≤R的范围如下图所示：

在个参数的轴上以角的形式加以表示。

而在实际应用中，上述的角就是得到稀疏解（含有大量0的解）的秘诀。

对于参数的线性模型：

训练平方误差Jls是关于Θ的向下的二次凸函数。因此，训练平方误差Jls在参数空间内具有椭圆状的等高线，其底部就是最小二乘解，如下图所示：

L2约束的最小二乘学习法

椭圆状的等高线和圆周的交点，就是L2约束的最小二乘学习法的解，我们记为L2cls（L2-constrained least squares）。

另一方面，L1约束的最小二乘学习法的解所在的范围，在各个参数的轴上都有角，如下图所示：

一般L1约束的最小二乘学习法

大体上是在该范围内的交点与椭圆的等高线是相交的。因此，一般L1约束的最小二乘学习法的解都是位于参数的轴上。像这样在参数轴上的点中，有若干个为零的话，我们就把它称为稀疏（本例中，Θ1=0）.

3.L1约束的最小二乘学习的求解方法

因为L1范数中包含再远点处不能微分的绝对值，如下所示：

因此不能像L2范数约束那样简单地进行求解（Θ=0时不可微分）。然而，近些年来关于稀疏学习的最优化研究已经取得了较大的发展，产生了很多可以高效求解L1约束的最小二乘学习算法。特别是当参数b是非常大的数值的时候，L1约束的最小二乘学习法可以获得比L2约束的最小二乘学习法更高的求解速度。

这里，仅仅介绍一种近似的方法进行L1约束求解。

和L2约束的最小二乘学习法一样，这里使用由L1约束的上限R决定的拉格朗日待定因子λ，来考虑下式的正则化形式的最优化问题：

另外，对于L1范数中包含的不能进行微分的绝对值函数，可以使用微分的二次函数来进行控制。

上面的二次函数就是该绝对值函数的上界，与绝对值函数在点Θ=±c处相切。

在这里，通过反复迭代对其进行求解，可以用当前的解Θ'来代替c，以构成上街约束。

在上式中，当Θ=0的时候，一般认为|Θ|=0.如果使用广义逆矩阵的话，上面的计算过程可以表示为：

那么对于上面的目标函数，可以得到下述L2正则化最小二乘学习法的一般表达式：

所以可以求解参数Θ：

现在的解Θ=Θ'的情况下，绝对值函数也是与二次函数的上界相外切的，因此，J(Θ')=J'(Θ')是成立的。另外，Θ^是J'为最小的时候取到的，J'(Θ')≥J'(Θ^)也是成立的。所以，更新后的Θ^并不会比当前的解Θ'更差，具体如下图所示：

更新后的解Θ^并不会比现在的解Θ'更差

通过给定适当的初始值反复对这个解进行更新，L1约束的最小二乘学习法的解就可以使用一般L2约束的最小二乘学习法来求得。具体算法流程如下所示：

• 给初始值Θ以适当的值。
• 通过现在的解Θ来计算矩阵Θ：

其中，diag(a,b,...,c)是以a,b,...,c为顶角元素的对角矩阵。

• 使用矩阵Θ来计算解Θ：

• 直到解Θ达到收敛精度为止，重复上述2,3步的计算。

对于高斯核模型：

执行L1约束的最小二乘学习法的实例，如下图所示：

L1约束的最小二乘学习法

虽然表面上看学习结果并没有太大的区别，但是L2约束的最小二乘学习法中50个参数的值全部为非零值，而在L1约束的最小二乘学习法中，50个参数中有37个设置为0，学习结果仅仅使用了13个核函数的线性组合。

下面结果展示的是50个核函数的L2约束结果，我们可以与上图进行对比：

L2约束的最小二乘学习法

注意：虽然表面上看，学习结果并没有太大的区别，但是L2约束的最小二乘学习法的50个参数全部都是非零值，而在L1约束的最小二乘学习法的50个参数中有37个为0。

4.通过稀疏学习进行特征选择

使用基函数向量：

则与参数Θ相关的线性模型对于x而言也是线性的。

如果对这样的输入为线性的模型进行稀疏学习，那么与设为0的参数的值Θj相对应的输入变量xj，在模型的输入计算过程中是完全不是用的，也就是说，通过稀疏学习进行特征选择。

例如，我们可以通过下面的模型对某人的收入进行预测：

Θ1*学历+Θ2*年龄+Θ3*能力+Θ4*父母收入

这个模型的参数就可以通过稀疏学习进行训练。假设得到的结果Θ4=0，那么我们就可以得出结论，此人的收入与父母的收入没有任何关系。

假设进行随机的特征选择的话，对于d个特征值x1,x,x3,...,xd的2^d次维组合的优劣，一定要实现进行评估。在这个时候，计算时建十一输入维度d为基数呈指数增长的，因此，当d很大时，计算往往不堪重负，会起到适得其反的效果。因此，一个特征提个特征的依稀增加的向前选择法和一个特征一个特征地减少的向后删除法，在实际中有着广泛的应用。然而，这样逐次试错的范式，并不能重返考虑到各个特征之间的关系，所以很多时候并不能一定找到特征的最优组合。

另一方面，使用L1约束的稀疏学习进行特征选择，在实际应用中，比起向前选择法和向后删除法，往往能够得到更好的特征组合。

5.Lp约束的最小二乘学习法

先下一个定义，Lp范数约束是指：

但是，当p=∞的时候：

就变成了上式的情况，也就是说，L∞范数表示的是限量元素绝对值中的最大值。因此，L∞范数也被称为最大值范数。另一方面，当p=0时，就变成了下面的情况：

也就是说，L0表示的是非零的向量元素的个数。

下图表示的是Lp范数的单位球（R=1）。当p≤1时，Lp范数的单位球在坐标轴上程有单值的尖行；当p≥1的时候，则呈现凸型。

Lp范数的单位球

就像上图展示的那样，在坐标轴上呈有峰值的尖形是存在稀疏解的秘诀。另一方面，满足约束条件的空间如果不是凸型的话，可能存在局部最优解，但是最优化工作就会变得异常艰难。因此，当p=1时是稀疏解存在的唯一的凸型，由此可知，L1约束的最小二乘学习法是非常特殊的一种学习方法。

满足Lp范数的约束条件的空间性质

6.L1+L2约束的最小二乘学习法

虽然L1约束的最小二乘学习法是非常有效的学习方法，但是在实际应用中，经常会遇到些许限制。

当参数b比训练样本n还要多的时候，L1约束的最小二乘学习法的非零参数个数最大为n。

还有，当参数b比训练样本n少的时候，L1约束的最小二乘学习法的通用性能要比L2约束的最小二乘学习法稍差。

解决上面问题的方案，就是使用L1+L2约束的最小二乘学习法。这个方法就是利用L1+L2范数的凸结合来进行约束的。

L1+L2范数的单位球如下图所示：

从上面我们可以看出，L1+L2范数约束也会像L1翻书那样容易求得稀疏解。

另外，即使参数b比训练样本数n还要多，L1+L2约束的最小二乘学习法也可以拥有n个以上的非零参数。另外，当基函数为集合构造的时候，经常会以集合为单位对基函数进行选择，实验证明：L1+L2约束的最小二乘学习法比L1约束的最小二乘学习法具有更高的精度。然而，除了加入正则化参数λ之外，为了调整L1范数和L2范数的平衡，还需要引入参数T，这也是L1+L2约束最小二乘学习法在实际中所面临的问题。