原文地址: https://www.csie.ntu.edu.tw/~cjlin/papers/l1.pdf.
这篇文章主要讲L1正则化下的线性分类算法。由于L1正则化项不可微的性质，提出该问题的优化算法也比较困难。作者在这里列举了当前(2012年以及之前)的L1正则化的线性分类算法，最后作者提出坐标下降法的扩展算法，它在文本分类这种大且稀疏数据上十分有效。
显然问题还是无约束最小化问题
\[\min_{\pmb w}\quad f(\pmb w)=\Vert\pmb w\Vert_1+C\sum_{i=1}^l\xi(\pmb w;\pmb x_i,y_i)\tag{1}\]L1正则化让问题倾向于生成稀疏解，有助于我们进行特征选择；在此基础上可以减少预测时间。此外，L1正则化的存在等价于参数先验分布为Laplace分布时最大化后验。前面提到，不管损失函数性质多好，该问题不是一阶可微的，因此有很多工作是去克服问题的不可微性。如果$\xi$是对数损失函数:
\[\xi_{\log}(\pmb w;\pmb x,y)=\log(1+\exp(-y\pmb w^T\pmb x))\]这个损失函数是二阶可微的，其余两个常用的损失函数是L1-loss和L2-loss:
\[\xi_{L1}(\pmb w;\pmb x,y)=\max(0,1-y\pmb w^T\pmb x)\\ \xi_{L2}(\pmb w;\pmb x,y)=\max(0,1-y\pmb w^T\pmb x)^2\\\]上面两个损失函数分别是不可微、一阶可微但二阶不可微的，以上三种损失函数与L1正则化一起，分别构成了L1正则的对率回归问题、L1正则的L1-loss SVM问题和L1正则的L2-loss SVM问题。
这篇论文是LIBLINEAR的前作之一，LIBLINEAR所支持的L1正则模型只有L2-loss SVM和对率回归(LR)，所以本文不会过多提及L1正则化的L1-loss SVM。
不同于L2正则下的优化问题只有一个全局最优解，L1正则下的优化问题通常有多个最优解。在损失函数是非负且凸且可微的前提下，目标函数$f(\pmb w)$是凸的，因此上述多个最优解必然有相同 的函数值。我们设其中一个最优解为$\pmb{w}^*$，显然有下面充要条件:
\[\begin{cases}\tag{2} \nabla_jL(\pmb w^*)+1=0&\text{if }w_j^*>0,\\ \nabla_jL(\pmb w^*)-1=0&\text{if }w_j^*<0,\\ -1\leq\nabla_jL(\pmb w^*)\leq 1&\text{if }w_j^*=0. \end{cases}\]其中$L(\pmb w)$就是(1)式中的损失函数项。
本文常用记号和含义:
两种子向量写法:
\[\pmb v_{t:s}=[v_t,\cdots,v_s]^T,\qquad\pmb v_I=[v_{i_1},\cdots,v_{i_{\vert l\vert}}]^T\]其中$I=\{i_1,\cdots,i_{\vert l\vert}\}$是一个下标集合。类似的有子矩阵(截取特定行):
\[X_{I,:}=\begin{bmatrix} \pmb x_{i_1}^T\\ \vdots\\ \pmb x_{i_1}^T\\ \end{bmatrix}\]设函数
\[\tau(\pmb s)=\frac1{1+e^{-s}}\]也就是Sigmoid函数；定义指示向量$\pmb e_j$
\[\pmb e_j=[\underbrace{0,\cdots,0}_{j-1},1,0\cdots,0]^T\]这一部分是对L1正则问题算法的综述，前三节针对分类问题，最后一节针对回归问题。
分解方法就是通过逐次求解子问题实现目标函数的优化，比如坐标下降等。
其实就是朴素的坐标下降，逐坐标求解子问题
\[\min_{z}\quad g_j(z)=f(\pmb w+z\pmb e_j)-f(\pmb w)\tag{3}\]可以发现问题(3)只有一个不可微点$z=-w_j$。有一些方法想去求解L1正则的对率回归问题，困难在于没有闭式解。Goodman(2004)在假定特征值非负($x_{ij}=0,\forall i,j$)的情况下，通过优化一个上界函数实现目标函数的优化，前提是$w_j\geq0$，但他的方法可以拓展到实数域。Genkin等人(2007)提出了BBR算法，在求解子问题时采用置信域牛顿法。本文作者对BBR算法进行改进，加入线搜索，提出更有效的坐标下降法CDN。
如果我们随机选择坐标进行更新，那么算法就成为了是随机坐标下降法。Duchi和Singer(2009)用这样的思想去求解最大熵模型。
我们可以用梯度信息帮助我们选择更有“前景”的坐标分量，被称作Gauss-Southwell规则。这样选择变量使得算法收敛的迭代次数减少，但每次迭代的代价增加。Shevade和Keerthi(2003)提出一个基于Gauss-Southwell的分解方法，该方法在每次迭代中选择一个最优的变量进行更新。Hsieh等人(2008)年发现在L2正则化下的线性分类问题中，维护梯度向量但每轮只更新一个变量是不值得的。因此若利用一阶信息来筛选变量，一次迭代选择多个变量进行更新是更好的选择。
在上述问题框架下，应当近似求解而不是精确求解子问题。这种方法被作者称为CGD-GS，也就是使用Gauss-Southwell规则(GS)的坐标梯度下降法(Coordinate Gradient Descent, CGD)。
激活集方法(Active set methods)常用于线性约束问题，在每轮迭代中，算法需要判断$\pmb w$中的元素哪些是0哪些不是，激活集是$\pmb w$中所有非0元素，下一轮更新坐标只会从激活集中选取。Perkins等人(2003)用激活集方法求解L1正则化的对率回归问题，用一阶信息(梯度)判断元素是否为0。
这一类方法是将(1)转化成带约束优化问题求解，可以分为两类：平滑约束和非平滑约束。
将原$\pmb w$向量用两个非负向量$\pmb w^+$和$\pmb w^-$，从而问题(1)等价于
\[\begin{aligned} \min_{\pmb w^+,\pmb w^-}\quad&\sum_{j=1}^nw_j^++\sum_{j=1}^nw_j^-+C\sum_{i=1}^n\xi(\pmb w^+-\pmb w^-;\pmb x_i,y_i)\\ \text{s.t.}\quad& w_j^+\geq0,w_j^-\geq0,\forall j. \end{aligned}\tag{4}\]上述问题的约束条件是平滑的，所以这个问题可以用标准的优化方法求解。Schmidt等人(2009)提出ProjectionL1方法去解这个问题。L-BFGS方法的实现，比如LBFGS-B和BLMVM在有限内存下近似Hessian矩阵，迭代求解该问题。带置信域的牛顿法(TRON)也可以解决该问题。TRON开始是被用于求解L2正则的对率回归，性能超过了经典的LBFGS方法，但目前没有证据表明TRON在L1正则化的问题上奏效，因此作者在后面会讨论这一问题。
Koh等人(2007)使用内点法求解L1正则对率回归，他们将原问题(1)转换成
\[\begin{aligned} \min_{\pmb w,\pmb u}\quad&\sum_{j=1}^nu_j+C\sum_{i=1}^l\xi(\pmb w;\pmb x_i,y_i)\\ \text{s.t.}\quad&-u_j\leq w_j\leq u_j,j=1,\cdots,n \end{aligned}\tag{5}\]下面的变换说明问题(5)和问题(4)是等价的:
\[w_j^+=\frac{u_j+w_j}{2},w_j^-=\frac{u_j-w_j}{2}\]为了确保$\pmb w$和$\pmb u$都在可行域里面，Koh等人在(13)加上对数障碍函数，然后使用牛顿法求解。
带L1正则化的无约束问题等价于下面的带约束问题
\[\begin{aligned} \min_{\pmb w}\quad&\sum_{i=1}^l\xi(\pmb w;\pmb x_i,y_i)\\ \text{s.t.}\quad&\Vert \pmb w\Vert\leq K \end{aligned}\]显然$K$是随罚参数$C$的选取而变化的。虽然约束条件不平滑，但是要考虑的变量比前面的问题少得多。Lee等人(2006)提出用最小角回归算法(LARS)去寻找牛顿方向，再用回溯线搜索去优化目标函数。
其他用于求解L1正则化的对率回归或L2-loss SVM的方法包括
优化过程中使用的信息越高阶(一阶梯度信息，二阶Hessian矩阵)，收敛速度越快。但随之而来的是单步迭代的代价增加。比如TRON和内点法(IPM)在每轮迭代中都有解一个Hessian矩阵相关的线性系统(即线性方程组)，相反的，如果用相对低阶的信息，比如梯度，虽然迭代会变慢，但是在算法早期可以快速的下降。
使用越高阶优化信息的算法，在实现上也就越困难。比如牛顿法要考虑线性方程组的求解。相反，坐标下降和随机梯度下降等算法相比而言易于实现，因为只涉及到向量运算。EM算法实现属于前两种中间。
对于大规模数据，尤其是多特征数据下，牛顿法要求解$n$阶的线性方程组，显然计算量过大，不能用高斯消元法求解(复杂度$O(n^3)$)，TRON和IPM都是用共轭梯度法求解的。对于EM算法，因为要常常求$n\times n$矩阵的逆，因此它不能用于大规模数据的场景。
对于选择多个变量进行一次更新的算法，当选择的变量对应的特征相互独立时，下降的效果最好；但它在特征高度相关的情况下，收敛效果会衰减。
没有一种方法是最适合于所有的数据类型的。对一种应用程序有效的方法对另一种应用程序来说可能较慢。本文重点研究了文档分类，必须有一种可行的方法能够方便地处理大而稀疏的特征。
这一部分讲的是L1正则的回归问题，也就是LASSO，与本文核心内容关系不大，故略去。读者若有兴趣可阅读原文。
在论文的后半部分，是作者对当前L1正则优化领域最高水平的软件中的算法的解读，包括
以上软件算法可用于处理稀疏大数据，这也是为什么作者选择这些算法的原因。然后作者提供了两种实现: 坐标下降(CDN)和带置信域的牛顿法(TRON)。由于论文篇幅过长，笔者将在后面的文章里对这些算法进行选择性讲解。
