从浅层模型到深度模型：概览机器学习优化算法

学习算法一直以来是机器学习能根据数据学到知识的核心技术。而好的优化算法可以大大提高学习速度，加快算法的收敛速度和效果。该论文从浅层模型到深度模型纵览监督学习中常用的优化算法，并指出了每一种优化算法的优点及局限性，同时其还包括了一阶和二阶等各种算法的形式化表达。本文主要对本论文选择性地编译了优化算法的部分，更详细的推导及介绍请查看原论文。

 

 

论文链接：https://arxiv.org/abs/1706.10207

摘要：本篇论文旨在介绍关于将最优化方法应用于机器学习的关键模型、算法、以及一些开放性问题。这篇论文是写给有一定知识储备的读者，尤其是那些熟悉基础优化算法但是不了解机器学习的读者。首先，我们推导出一个监督学习问题的公式，并说明它是如何基于上下文和基本假设产生各种优化问题。然后，我们讨论这些优化问题的一些显著特征，重点讨论 logistic 回归和深层神经网络训练的案例。本文的后半部分重点介绍几种优化算法，首先是凸 logistic 回归，然后讨论一阶方法，包括了随机梯度法(SGD)、方差缩减随机方法(variance reducing stochastic method)和二阶方法的使用。最后，我们将讨论如何将这些方法应用于深层神经网络的训练，并着重描述这些模型的复杂非凸结构所带来的困难。

1 引言

在过去二十年里，机器学习这一迷人的算法领域几乎以史无前例的速度崛起。机器学习以统计学和计算机科学为基础，以数学优化方法为核心。事实上，近来优化方法研究领域中的许多最新理论和实际进展都受到了机器学习和其它数据驱动的学科的影响。然而即使有这些联系，统计学、计算机科学和致力于机器学习相关问题的优化方法研究之间仍存在许多障碍。因此本文试图概述机器学习学习算法而打破这种障碍。

本篇论文的目的是给出与机器学习领域相关的一些关键问题和研究问题的概述。考虑到涉及运筹学领域的知识，我们假设读者熟悉基本的优化方法理论，但是仍将引入在广义机器学习领域使用的相关术语和概念，希望借此促进运筹学专家和其它贡献领域的人员之间的沟通。为了实现这一目的，我们在词汇表 1 中列出了本论文将介绍和使用的最重要的术语。

 

 

表 1 ： 监督机器学习的术语表(监督机器学习的目的之一就是理解输入空间 X 中每个输入向量 x 和输出空间 Y 中相应输出向量 y 之间的关系)

1.1 阐明动机

1.2 学习问题和优化问题

1.3 学习边界、过拟合和正则化

2 解决Logistic回归问题的优化方法(浅层模型的优化方法)

当 L 和 r 是关于 w 的任意凸函数时，可以运用在本节中讨论的方法来解决问题(11)：

 

 

这一类中包含很多机器学习模型，包括支持向量机、Lasso(Least Absolute Shrinkage and Selection Operator)、稀疏逆协方差选择等。有关这些模型的详细信息请参见 [86] 和其中的参考文献。为了每一步都能具体(展现出来)，此处我们指定以二分类的正则化logistic回归为例(进行讲解)。为了简化例子中的符号，我们作不失一般性的假设，令

。(此处省去了偏置项 b0)，这一省略操作可以通过在输入向量上增加一维恒为 1 的特征值来弥补)。当 w 和 x 都是 d 维时就可以令其为特定的凸优化问题。

 

 

 

值得一提的是，对于此类问题，正则化项必不可少。想一想为什么说它必不可少，假设对于所有的 i ∈{1,...,n}，有参数向量 w，满足 yi(wT*xi) > 0 以及(存在)无界射线 {θw : θ > 0}。那问题就很明朗了，在这个例子中，当 θ →∞时，

 

 

也就是说函数(式 12)无法取最小值。另一方面，通过增加(强制)正则化函数 r，可以保证问题(12)将具有最优解。

对于正则化函数 r，我们将会参考常用选择

和 r(w) = ||w||1。不过为了简单起见，我们通常会选择前者，因为它使得公式 12 对于每一个因子是连续可微的。相反，r(w) = ||w||1 会导致非平滑问题，为此，(实现)函数最小化就需要更复杂的算法。

 

2.1 一阶方法

我们首先讨论用一阶方法求解问题(12)，这里的」一阶」仅仅指对函数 F 中的参数进行一阶偏导的数学技巧。

2.1.1 梯度下降法

从概念上讲，最小化光滑凸目标的最简单的方法是梯度下降法，具体分析参见 [ 62 ]。在这种方法中，从初始化估计值 w0 开始，通过下述公式迭代地更新权重估计值。

 

 

其中 αk > 0 是一个步长参数。步长序列 {αk} 的选择直接决定此算法的性能。在优化研究领域，人们普遍认为，在每次迭代中采用线性搜索来确定 {αk }，可以为解决各种类型的问题找到一个性能优越的算法。然而，对于机器学习应用程序来说，这种运算成本高昂，因为每次函数 F 的计算都需要传递整个数据集，如果 n 过大，很可能带来高昂的(训练)成本。

好在当每个αk 都设置为一个正的常数α且它是一个足够小的固定值时，从理论上分析，该算法的收敛性仍可以得到保证。(固定的步长常数在机器学习领域叫做学习率。但即使不是常数，也有人把αK 或整个序列 {αK } 叫做学习率)。该算法的收敛速度取决于函数 f 是强凸函数还是弱凸函数。

用于解决 L1 范数正则化的logistic回归问题的梯度下降和加速梯度下降拓展算法分别被称作 ISTA 和 FISTA。我们观察到，在这种情况下，即使λ> 0，目标函数也不会是强凸函数。只有目标函数为凸时 [5]，ISTA 和 FISTA 具有与其对应的平滑函数相同的次线性收敛速度。

梯度下降在 ML 训练过程中的一个重要特性就是计算出每次迭代中求解函数 F 的梯度的运算成本。在 ML 的训练过程中，单个梯度计算的成本通常是 O(ND)，这个确实可以看到，例如，在正则化项为

的情况中，函数 F 关于每一个特定的 w 的梯度是

 

 

 

2.1.2 随机梯度法

随机梯度法由于其用于最小化随机目标函数而在运筹学领域广为人知，同时也是 ML 社区中的一种特征优化算法。该算法最初由 Robbins 和 Monro [ 67 ] 在解决随机方程组问题时提出，值得注意的是，它可以用于最小化具有良好收敛性的随机目标，而且每次迭代的计算复杂度仅为 O(d)而不是 O(nd)(梯度下降中的计算复杂度)。

在每一次迭代中，随机梯度法都会计算梯度 F(Wk)的无偏估计 GK。该估计可以以及低的代价计算得到;例如，对于公式(12)，某次迭代的随机梯度可被求解为

 

 

其中 Sk 被称作小批量，它的所有元素都是从总数据集 {1,...,n} 中按均匀分布选出来的。接下来的运算类似于梯度下降：

 

 

毫无疑问，该算法的关键在于选择步长序列 {αk}。不同于梯度下降，固定的步长(即学习率)不能保证算法会收敛到强凸函数 F 的最小值，而只保证收敛到最小值的邻域。

SGD 的收敛速度比梯度下降慢。尤其当函数 F 是强凸函数时，该算法只保证当 k ≥ O(1/ε) 时可以得到预期精度的解(即满足 E[F(wk)]-F(w) ≤ ε的解)，而当函数 F 仅仅是凸函数时，只有在 k ≥ O(1/ε^2) [11] 时才能保证得出上述解。

另一方面，正如前文提及的，如果 Sk 的大小由一个常数限定(独立于 n 或 k 的常数)，那么 SGD 的每次的迭代成本都比梯度下降法小 0(n)倍。

然而，在实际运用中，标准的 SGD 并不一定是解决机器学习中优化问题的最有效方法。事实上，机器学习和优化算法领域在开发改进或替代 SGD 方面进行了大量的积极研究。在随后的两部分中，我们将讨论两类方法：方差缩减法和二阶方法。但是在这两类方法以外，还有多种方法。例如，加有动量的 SGD 就是一个实践中被发现的性能好于好于标准 SGD 的拓展版 SGD。见下图算法 1