4.3　Lasso回归

岭回归使用系数的平方和来计算类表示的复杂度，该复杂度对系数进行整体收缩，但当变量个数很多时，我们当然会关心哪些变量或特征与回归目标最相关，一旦找出这些变量会使得回归的结果更具有解释性。这时，系数的平方和来计算类表示的复杂度并不合适，系数中非零值的个数来计算类表示的复杂度更为合理。如果系数是零，对应的变量与回归目标无关。但是，直接用系数中非零值的个数来测度类表示的复杂度将给算法带来极高的复杂度。为了减少计算量，通常使用系数绝对值的和来代替系数中非零值的个数。在这种情形下，类表示的复杂度定义为。

综合以上考虑，使用类一致性准则和奥卡姆剃刀准则，就可以得到lasso回归的目标函数（4.21）：

对比式（4.21）与式（4.19），不难发现，lasso回归较岭回归的最主要区别在于对系数w的收缩方式。Lasso回归用系数的l1－范数（即绝对值的和）代替了岭回归中系数的平方和。我们通常使用图4.2给出这两种收缩方式的差异。图4.2的灰色区域表明两种回归的可行域|w1|+|w2| < t和，椭圆为最小二乘误差的等高线。等高线与可行域的交点为问题的解。可以看出，相对于岭回归的圆形（二维情况）可行域，lasso回归的可行域为菱形，若交点落在菱形的顶点上，则对应的wj为0。若是高维情况，则lasso回归的可行域将有更多的顶点，对应的系数也就有更多的机会为0，因此可以获得更加稀疏的解，这一特性是岭回归所不具备的。与式（4.11）和式（4.12）类似，可以获得问题（4.21）的矩阵形式：

求解问题（4.22）的难点在于l1－范数在0点位置不可导，因此不能像岭回归那样直接求导给出闭解。目前已经有很多针对l1－范数的优化算法，如最小角度回归（least angle regression）等。这里我们使用一个在机器学习领域非常流行的优化算法，快速迭代收缩阈值（fast iterative shrinkage thresholding，FIST）算法。该算法用于解型如下式的目标函数：

其中g（x）为连续的凸函数，可以不光滑。f（x）为光滑凸函数，其导数应Lipschitz连续，表示为存在常数L（f）>0，满足：

∇f（x）为f（x）的梯度。可以证明：

为方便起见，L（f）用L代替。令，g（w）=λ‖w‖1，把f（w）在w（t）处展开，有

可以看出FIST方法最小化的并不是原函数，而是原函数的一个上界函数。这有什么好处呢？这样转化后式（4.26）仍然不可导。去掉式（4.26）的常数项，最优化问题变为

至此推导出w的迭代公式，但并没有解决l1范数求导的问题，这样做的真正目的在于问题（4.28）具有闭式解形式：

其中Sλ（a）为软阈值收缩算子（soft-thresholding shrinkage operator），定义为

这里，（Sλ（a））i表示向量Sλ（a）的第i个分量。由式（4.27）和式（4.28）可得

其中，于是有

根据式（4.24）和式（4.31），有，即的谱范数。到此该算法可以称为iterative shrinkage thresholding（IST）算法，其收敛速度为O（t-1）。它的加速算法FIST引入辅助变量序列a（t），在每次迭代中用a（t）计算w（t），再通过w（t）与w（t-1）生成下次迭代时用到的a（t+1），从而保证收敛速度为O（t-2），算法具体过程如下。

算法4.1　通过FIST求解问题（4.22）

输入：数据矩阵A

1：初始化a（1）=w（0）=（0，0，…，0）T，m（1）=1，є=103，T=100（T代表最大迭代次数）

2：while（t<T）do

3：

4：

5：

6：如果（‖w（t）-w（t-1）‖∞> є），t ← t+1。否则，w ← w（t），结束程序

7: end while

输出：w