腾讯AI Lab现场陈述论文：训练L1稀疏模型的象限性消极下降算法

腾讯 AI Lab 共有 12 篇论文入选在美国新奥尔良举行的国际人工智能领域顶级学术会议 AAAI 2018。腾讯技术工程官方号独家编译了论文《训练 L1 稀疏模型的象限性消极下降算法》(Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms)，该论文被 AAAI 2018 录用为现场陈述论文 (Oral Presentation)，由腾讯 AI Lab 独立完成，王倪剑桥为论文唯一作者。

论文地址：https://arxiv.org/abs/1704.07987

中文概要

L1 范数正则模型是一种常用的高维数据的分析方法。对于现代大规模互联网数据上的该模型，研究其优化算法可以提高其收敛速度，进而在有限时间内显著其模型准确率，或者降低对服务器资源的依赖。经典的随机梯度下降 (SGD) 虽然可以适用于神经网络等多种模型，但对于 L1 范数不可导性并不适用。

在本文中，我们提出了一种新的随机优化方法，随机象限性消极下降算法 (OPDA)。本算法的出发点是 L1 范数函数在任何一个象限内是连续可导的，因此，模型的参数在每一次更新之后被投影到上一次迭代时所在的象限。我们使用随机方差缩减梯度 (SVRG) 方法产生梯度方向，并结合伪牛顿法 (Quasi-Newton) 来使用损失函数的二阶信息。我们提出了一种新的象限投影方法，使得该算法收敛于一个更加稀疏的最优点。我们在理论上证明了，在强凸和光滑的损失函数上，该算法可以线性收敛。在 RCV1 等典型稀疏数据集上，我们测试了不同参数下 L1/L2 范数约束 Logistic 回归下该算法性能，其结果显著超越了已有的线性收敛算法 Proximal-SVRG，并且在卷积神经网络 (CNN) 的实验上超越 Proximal-SGD 等算法，证明了该算法在凸函数和非凸函数上均有很好的表现。

演讲

大家好，我是王倪剑桥，来自腾讯 AI Lab。

引言：学习稀疏表征一直都是一个非常重要的数据分析任务。比如说，在生物学领域，为了对单个个体进行基因分析，常常涉及到数百万个基因，然而其中真正对某任务，比如帮助预测某种稀有癌症，有用的基因片段并不多。在金融序列预测和网络广告等领域，也有很多数据数量甚至比数据维度还小的情况。这本身是一个病态 (ill-condition) 的问题，然而如果对解有一个稀疏先验的话，问题则是可解的。通信领域的压缩感知中的核心部分也是如何高效求解稀疏模型。目前，这些方法包括 Lasso (Robert Tibshirani), Dantzig Selector (Emmanuel Candes, Terrence Tao), OMP (Joel A. Tropp, Tong Zhang), FoBa (Tong Zhang) 等。

首先，我们给一个直观的例子，为什么 L1 范数正则项（绝对值的和）适用于求解稀疏模型。下图中，蓝色区域是约束内的可行解区域，左边是 L1 范数球（norm ball），右边是 L2 范数球，红色圈是均方损失函数（average-of-square-loss）的等高线。这些球和等高线之间的交点是模型的解。我们可以看到 L1 正则化模型的解接近 Y 轴，这意味着其 X 维元素更接近于 0。这是一个简单的例子，可以看出来 L1 正则项比 L2 正则项更适合于学习稀疏模型。

我们可以把大部分问题统一为最小化一个正则化函数 P(x)= F(x)+R(x)，其中 F(x) 是 N 个损失函数的平均，其中每个都依赖于一个数据样本，R 是 L1 正则项。我们还假设每个损失函数都满足二次可导 (twice differentiable)、强凸 (strongly-convex) 和光滑 (smooth)。由于该 L1 范数是不可导的（在零点），目前最通用的优化方法是近端方法 (proximal method)，通过迭代式地采取梯度下降步骤，然后在当前点上优化一个 proximal 问题。

相关文献介绍：我们的主要参考方法是象限性伪牛顿法 (OWL-QN: Galen Andrew, Jianfeng Gao)，这种方法基于 L-BFGS (Jorge Nocedal)，一种最常用的伪牛顿法。该方法 OWL-QN 将更新后的参数限制在一个特定的象限内，因为在每个单个象限中，其绝对值函数实际上是可微分的。OWL-QN 的一个关键创新点与在零点的次梯度 (subgradient) 有关。这里 L1 正则项 R(x) 的次梯度既可以是正λ，也可以是负 λ，那么如何选择次梯度会影响收敛速度。以下面大括号内第三个分支为例：我们研究的是当前点 X 的第 i 维 X_i，和梯度 V_i。如果 X_i 等于 0 且 X_i 加上 λ 为负，那么该次梯度就设为 V_i 加上正 λ，因为在减去这个次梯度之后，X_i 将会是一个正值，那么 R(x) 的次梯度将仍然为正 λ，这会使 L1 范数的次梯度在一次迭代中保持一致。

为了处理大规模互联网数据，研究者提出了很多用于加速训练过程的优化方法，比如随机梯度下降法 (SGD)。但是，SGD 通常需要衰减步长才能收敛，而且它的收敛率是次线性的 (sublinear)。近期出现了 SVRG (Rie Johnson, Tong Zhang) 和 SAGA (Aaron Defazio, Francis Bach) 等一些随机方差缩减方法，可以无需降低步长就能收敛，而且可以在光滑和强凸的模型上实现线性收敛率 (linear convergence rate)。在 SGD 方法中，第 k 步的下降方向 v_k 是在该数据集的一个随机子集 S_k 上进行评估的。在 SVRG 方法中，我们需要周期性地在一些参考点（比如 tilde-X）上计算一个准确梯度。这个准确梯度构成了 SVRG 的 v_k 的第三项，然后我们必须通过在 tilde-X 上减去一个随机梯度（这是在同一子集 S_k 上计算的）来平衡它的期望。

受 SVRG 和 OWL-QN 的启发，我们开发了一种针对 L1 正则化模型的随机优化方法。在第一步时，我们计算损失函数 F(x) 的 SVRG，然后我们使用来自 OWL-QN 的思想来计算一个参考方向，尽量使下降方向以在一次迭代后维持同一个象限。而我们的实际下降方向 V_k 是用这里的第三个等式计算的。

现在我们可以计算解前进的方向了。我们可以通过计算当前点上的 Hessian 矩阵或估计近似的 Hessian 矩阵（伪牛顿法）来使用该损失函数的二阶信息，从而加速其收敛。然后我们可以通过在当前点附近的 Taylor 二次展开来计算最优下降方向 D_k。如果我们使用 L-BFGS，我们可以绕开耗时的矩阵求逆运算，只通过快速的矩阵向量乘法就可以做到。我们也可以直接将 V_k 分配给 D_k，这样就是一个典型的一阶方法。在这个步骤之后，方向 D_k 的象限必须与参考方向保持一致，这意味着：如果 D_k 的某些维度与参考方向的符号不同，它们就必须被分配为 0，我们将这个对齐后的版本记为 P_k。

除了对齐参考，上述计算梯度并没有涉及到 L1 正则化 R(x) 的偏导数，因为我们要避免对随机梯度的引入额外方差。为了使解是稀疏的，我们提出了一种全新的对齐算子来激励零元素。这个算子作用在 X,Y 两个元素上，如果 X 和 Y 符号不同或 X 的绝对值小于一个阈值，就强制 X 为零。通过这个对齐算子，每次在我们完成了之前的计算之后，我们就检查下一个点是否与当前点在同一个象限，如果不在，下一个点的某些维度就会被强制为零。在这一步之后，显然 X_k 的更多维度应该为零，而不是绝对值很小的非零值。

收敛性分析：在这篇论文中，我们证明在平滑性和强凸性的假设下，我们的方法将以一个线性速率收敛。

为了进行可视化，我们在这张图中绘制了在一个简单的二维合成函数的优化轨迹。我们的方法 OPDA 用红线标识，作为基准的 Proximal-Gradient Descent 算法用蓝线标识。在迭代了同样多次数之后，我们看到 OPDA 用更快的速度收敛到了等高线中更低的区域。

在凸函数上的实验：我们还使用 L2/L1 regularized Logistic 回归上进行了一些实验。在这一部分，我们将我们的方法与一个线性收敛算法 Prox-SVRG (Lin Xiao, Tong Zhang) 进行了比较。在这张图中，Y 轴表示解的次优性 (suboptimality)，即当前目标函数与最小值之间的间隔；X 轴表示完整扫过数据集的次数。我们发现使用不同的步长以及 L2 和 L1 正则化系数时，OPDA 的速度稳定地超越了 Prox-SVRG 算法。

在深度学习上的实验：我们使用 L1 正则化稀疏卷积神经网络 (sparse-CNN) 进行了实验，以表明我们的方法在非凸函数的有效性。下图中红线表示我们的方法，蓝线表示近端 SVRG。我们测试了不同规模的 L1 正则化。我们看到 OPDA 收敛速度比近 Prox-SGD 更快。而且在 L1 正则项更强的情况下，这种差异更大。

总结：我们提出的 OPDA 算法可以适用于快速优化 L1 正则的稀疏模型。实际上，由于我们的方法的象限性本质，下降方向和更新后的点的许多维度都会在对齐过程中被强制变为零，这会使等效步长变小很多；但是，在同等步长条件下，我们方法的速度仍然远远快于近端方法。这证明我们提出的对齐算子确实能将方向调校得更好，使其整体框架更为有效，而且在每次迭代中所需额外运算量接近可以忽略不计。