用强化学习搜索优化算法的机遇与挑战

自从去年 UC Berkeley 论文《Learning to Optimize》发表以来，有关优化器学习（optimizer learning）的研究就引起了人们的重视。在本文中，BAIR 在读博士 Ke Li 将向我们介绍这一工作的进展，并分享这一领域的机遇和挑战。

近年来，机器学习已经取得了巨大的成功，它已被应用在了很多不同领域中。这种成功可以归功于由数据驱动的机器学习方法，该方法能在使用专业知识手动设计的系统上自动挖掘数据中的模式。

然而，目前的范式仍存在一个悖论：由算法驱动的机器学习仍然是手动设计的。这就引出了一个问题：我们能否让算法自我学习？这将开启惊人的可能性，即自动寻找可以比手动设计更加完美的新算法，并且新算法能显著地提升学习能力。

要想这么做，我们需要克服一个巨大的障碍：如何参数化算法空间，让它们同时具有表现力（expressive）和搜索有效性？很多种已有算法都在两者之间进行着取舍。例如，如果算法空间代表了一小组已知算法，则其中可能不包含最佳算法，但我们可以通过简单枚举集合中的算法来有效地进行搜索。另一方面，如果算法空间代表了所有可能的程序，其中必然包含了最佳算法，但这种情况缺乏有效的搜索，因为枚举时间将呈指数级增长。

连续优化（continuous optimization）算法是机器学习最为常见的算法之一，其中包含一系列已知流行的算法，包括梯度下降、动量法、AdaGrad 和 ADAM 方法。我们考虑过自动设计这些优化算法的问题，这么做有两个原因：首先，很多优化算法是在凸假设下设计的，但被应用到非凸目标函数上；通过在实际使用环境下学习，优化算法有望实现更好的性能。第二，手动设计新的优化算法通常费时费力，可能需要数月或数年之久；学习优化算法可以减少手动设计的劳动量。

学习如何优化

在去年的论文《Learning to Optimize》中，UC Berkeley 的研究者们提出了一种学习优化算法的框架，它被称之为「Learning to Optimize」。在论文出现后，我们很快注意到 DeepMind 等机构的研究者也在论文《Learning to learn by gradient descent by gradient descent》中提出了类似的想法（读者可以挑战一下这篇论文标题如何翻）。

考虑到现有的连续优化算法通常的工作方式：它们通常以迭代的方式运行，并保持一定程度的迭代数量，并且每一次迭代都选取目标函数域内的一个点以搜索全局最小。在每个迭代中，算法都会使用固定的更新公式来计算步长向量，然后用它来修正迭代方向与下降步长。更新公式通常是在当前和过去的迭代中所评估历史梯度的函数，这些梯度都是目标函数对不同参数所求的偏导数。例如，在梯度下降中，更新公式是一些加权的负梯度（所加权为学习率）；在动量法中，更新公式是一些加权的指数移动均值。

这种更新公式是区别不同算法的基础。所以，如果我们可以学习更新公式，我们就可以学习优化算法。我们将更新公式建模为神经网络。这样，通过学习神经网络的权重，我们就可以学习出一个优化算法。将更新公式参数化为神经网络的同时满足了前面提到的两个特质：首先，它具有表达性，因为神经网络是通用函数的近似，它在本质上可以模拟具有足够容量的任何更新公式。

为了学习优化算法，我们需要先定义一个性能指标，我们将其称之为「元损失（meta-loss）」，它会奖励表现好的优化器，并惩罚不好的优化器。因为好的优化器可以快速收敛，正常的元损失是所有迭代中的目标函数值的总和（假设期望是最小化目标函数），或相当于缺失值累积（cumulative regret）。直观地说，这对应于曲线下面积，当优化器收敛速度较慢的时候，它的曲线下面积就会增大。

学习如何学习

考虑到目标函数是训练其他模型的损失函数这一特殊情况。在这种情况下，优化器的学习可以描述为「学习如何学习」。为清楚起见，我们将使用优化器训练过的模型称为「base-model」，并加上「base-」和「meta-」前缀分别排除与 base-model 和优化器相关的概念歧义。

「学习如何学习」是什么意思？虽然这个术语在近年来的论文中不时会出现，但不同的作者给它赋予了不同的意义，我们并没有对这段话的精确含义达成共识。通常，它也可以与术语「元学习」互换使用。

这个术语可以追溯到元认知的概念（亚里士多德，公元前 350 年），它描述了人类不仅理性，也对于自己产生理性的过程保持理性。「学习如何学习」从这一理念中寻求启发，并试图将其转化为具体的算法。通俗地说，「学习如何学习」仅仅意味着学习一些关于学习的方法。在元层面上（meta-level）存在不同方法，我们可以通过元知识将它分为三类：

• 学习要学习的目标
  
• 学习要学习哪个模型
  
• 学习如何学习
  

学习要学习的目标

这些方法旨在学习 base-model 参数中的一些特定值，使其对应相关任务时效率更高。元知识捕捉整个族中的共同特征，这样一来，base-learning 在遇到族中的新任务时就能训练和推断得更快。其中的例子包含迁移学习方法、多任务学习和 few-shot 学习。早期方法通过将 base-model 的参数分为两组（用于特定任务的和在任务中通用的参数）的方式来运行。例如，在基于神经网络的模型里有一种流行的方法是在所有任务中的低层分享权重，这样就可以捕获跨越任务的共同特征。参见《与模型无关的元学习，UC Berkeley 提出一种可推广到各类任务的元学习方法》。

学习要学习哪个模型

这些方法旨在学习哪些 base-model 可以适用于特定任务。元知识捕获不同 base-model 之间的相关性及其在不同任务上的表现。它面临的挑战在于通过表达和有效搜索的方式参数化 base-model 空间，以及在参数化任务空间中泛化到未见过的新任务上。不同的方法在表达性和可搜索性问题上有着不同的取舍。在《Ranking Learning Algorithms: Using IBL and Meta-Learning on Accuracy and Time Results》中，Brazdil 等人使用预定义的 base-model 和示例任务的数据库，并输出在最近示例任务上执行最佳的 base-model。虽然这个 base-model 空间是可搜索的，但它可能不包含十分优秀但却未被发现的 base-model。Jürgen Schmidhuber 等人在论文《Optimal Ordered Problem Solver》中提出了让每个 base-model 都作为通用程序的方法。虽然空间非常具有表达性，但这个空间的搜索时间和目标算法的数量成指数型增长。Hochreiter 等人的《Learning to Learn Using Gradient Descent》提出了一种将 base-model 训练为黑箱函数的算法，该算法可以将训练示例的序列绘制成预测序列并将其建模为循环神经网络。这样，自训练就被简化成为了训练神经网络的过程。因为 base-model 编码到循环神经网络的记忆状态中，所以它的容量受到内存的限制。与之相关的领域还有超参数调优，其目标较弱，即搜索由预定义的一组超参数参数化的 base-model。它是跨超参数的设置（通过延展、base-model），但非跨任务的泛化，因为超参数优化是在不同超参数下对同一个任务进行测试。

学习如何学习

前两个方向集中于学习之外，第三个方向则有关学习的过程，即元知识捕获学习算法行为共同特征的过程。这种方法有三个部分：base-model、用于训练 base-model 的 base-algorithm 以及学习 base-algorithm 的 meta-algorithm。其中学到的不是 base-model 本身，而是在某个任务中训练 base-model 的 base-algorithm。因为 base-model 和任务都是由用户提供的，学习到的 base-algorithm 必须可以在多种不同的 base-model 和任务中使用。由于大多数学习算法优化了一些目标函数，因此在许多情况下学习 base-algorithm 难以学到优化算法。这个学习优化算法的问题曾被 Ke Li 与 Jitendra Malik 的《Learning to Optimize》和 Marcin Andrychowicz 等人的《Learning to learn by gradient descent by gradient descent》等论文研究过。与之最接近的论文则是 Bengio 等人在 1991 年发表的《Learning a synaptic learning rule》，其中研究人员试图学习了 Hebb 式的触突学习规则（learning rule）。学习规则取决于编码相邻神经元活动的当前迭代的维度的子集，但不依赖于目标函数，因此不具有将其推广到不同的目标函数的能力。

泛化

任何形式的学习都要求在有限的样本上进行训练，并泛化至样本所属的总体分布中。因此，考虑用于训练 base-model 的优化器学习，及其使用的样本和所属类别是很有用处的。每个样本就代表一个目标函数，即一个任务中用于训练 base-model 的损失函数。该任务的特点是一系列样本和目标预测，换言之，目标函数就是用于训练 base-model 的数据集。元训练集（meta-training set）包括多个目标函数，元测试集包括同一个类别的不同目标函数。目标函数的不同之处体现在两个方面：即它们对应不同的 base-model 或不同的任务。因此，本文所指泛化指在不同 base-model 和／或不同任务上运行的学习优化器。

泛化为何如此重要？

假设我们不关心泛化，那么我们要在用于训练优化器的同一个目标函数上评估优化器。如果我们仅使用一个目标函数，那么最佳优化器就是记忆最优解的那个优化器：该优化器通常可在一个迭代步内收敛到最优，并且在任意初始化状态下都能一步到达。在本文中，目标函数对应在特定任务中训练特定 base-model 的损失函数，因此本质上，该优化器记忆了 base-model 的最优权重。即使我们使用了很多目标函数，学习的优化器仍然能够确定它运行了哪个目标函数，并尽快跳转至记忆的最优解。

这又存在什么问题？记忆最优需要先找到最优，因此学习一个优化器需要的时间比运行传统的优化器如梯度下降的时间要长。那么，为了找到最优目标函数，执行传统的优化器要更快一些。因此，如果我们不关心泛化，学习优化器就没有意义。

因此，要使学习优化器具备实用性，必须使它可以泛化到不同的新目标函数上，且也能有优秀的表现。

泛化的内容应该是什么？

如果我们对于泛化的要求是在类似任务上达到类似 base-model 的效果，那么学习的优化器能够记忆 base-model 和一般任务的部分最优权重，如神经网络较低层级的权重。这在本质上与学习要学习的内容构想相同，正如迁移学习那样。

与学习要学习的内容不同的是，学习如何学习的目标不是学习什么是最优，而是如何找到最优。因此，我们必须把目标设置为更强大的泛化能力，即在不类似任务上泛化到类似的 base-model 中。能够泛化至不类似任务的优化器无法部分地记忆最优权重，因为不类似任务的最优权重可能会完全不同。如在 MNIST（包括手写体数字的黑白图像数据集）和 CIFAR-10（包括自然场景中常见物体的彩色图像数据集）上训练的神经网络较低层级的权重甚至有可能完全不同。

我们应该把目标定为比这更强的泛化，即是否能在不类似任务上泛化到不类似的 base-model 中？由于这些对应的目标函数与训练优化器所用的目标函数完全不同，所以这实际上是在问学习优化器是否可泛化至完全不同的目标函数。

答案是不可以。给定任意优化器，我们考虑在特定目标函数上优化器后的轨迹。由于优化器仅依赖前一次迭代的信息，所以我们可以调整最后一次迭代的目标函数，使之发散（arbitrarily bad），同时维持前面所有迭代中目标函数的几何结构。因此，任何优化器都有表现很差的目标函数，没有优化器能够泛化至所有目标函数。

如果没有表现普遍良好的优化器，我们还能够期待学习有用的优化器吗？答案是 yes：由于我们在实践中通常对优化特定类别的函数感兴趣，所以学习在这些类别中性能良好的优化器还是可以的。一个类别中的目标函数可以共享几何结构中的规则，如：它们可以具有共同的几何特性，如凸性（convexity）、分段线性、Lipschitz 连续或其他未命名的特性。在学习如何学习的背景下，每个类别能够对应一种 base-model。例如，带 ReLU 激活单元的神经网络是一个类别，因为它们都是分段线性。注意，在学习优化器的时候，没必要明确地描述几何规则的形式，因为优化器可以在该类别的目标函数上进行训练时，自动获取。

如何学习优化器

我们尝试的第一个方法是将该问题当作一个标准的监督学习问题：我们仅区分与更新公式相关的元损失（meta-loss），使用标准的基于梯度的优化方式学习这些参数。（我们不是唯一这么想的人；（Andrychowicz et al., 2016）也使用了类似的方法。）

这看起来是非常自然的方法，但并不奏效：尽管我们尽了最大的努力，还是无法用这种方式训练出可泛化至未知目标函数的优化器，即使未知目标函数是从训练优化器所用目标函数的同分布中选取的。在几乎所有未知目标函数上，学习的优化器开始的时候保持正确的收敛趋势，但很快就发散了。另一方面，在训练的目标函数上没有这样的问题，效果很好。这是什么原因造成的呢？

学习优化器并不是看上去那么简单的学习问题。标准的监督学习假设所有的训练样本都是独立同分布的（i.i.d.）；在我们的设置中，优化器在每次迭代中采用的迭代步向量都会影响到优化器在所有后续迭代中经历的梯度。迭代步向量影响后续迭代中梯度的方式尚不可知，因为这依赖于目标函数的局部几何结构，而在元测试时，这种几何结构仍是未知的。监督学习不能在该设置中运行，必须假设未知目标函数的局部几何结构与训练目标函数在所有迭代中的局部几何结构相同。

考虑一下如果使用监督学习方式训练的优化器，并用于未知的目标函数上会发生什么。优化器迭代一步，就能发现下一个迭代中的梯度与它期望的不同。然后当优化器遇到这样的梯度时，它就会记忆在训练目标函数时遇到这种梯度该如何处理，该记忆可能在空间中完全不同的区域发生，优化器会据此采取下降步。不幸的是，优化器会发现下一个迭代的梯度与它期望的更加不同，因此这种循环不断重复，优化器造成的误差随着时间越来越大，也就导致了快速发散。

文献中将这一现象称作「复合误差」（compounding error）。我们都知道监督学习器的误差总量是迭代数量的二倍，而不是独立同分布设置中的线性情况（Ross and Bagnell, 2010）。本质上，使用监督学习训练的优化器势必会与训练目标函数的几何结构产生过拟合。解决该问题的一种方式是使用强化学习。

强化学习的背景

考虑一种环境（environment），该环境的状态（state）根据采取的动作（action）以一种未知的方式发展。我们有一个可以与这种环境互动的智能体（agent），它连续选择动作，并在每个动作之后收到关于新状态是好是坏的反馈。强化学习的目标是找到一种方法，使智能体根据当前状态选择动作，使状态在期望上保持优秀。更准确地说，强化学习问题具备以下组件：

• 一个状态空间：所有可能状态的集合；
  
• 一个动作空间，所有可能动作的集合；
  
• 一个成本函数，用来评估状态有多糟糕；
  
• 一个时间范围，代表时间步的数量；
  
• 一个初始状态概率分布，指定最初采取任何动作之前不同状态的出现频率；
  
• 一个状态转换概率分布，指定特定动作之后状态的（可能）改变。
  

即使学习算法意识到上面 5 个组件的内容，它也不知道最后一个组件：状态如何根据选择的动作发生变化。在训练中，学习算法可以与环境互动。尤其是，在每个时间步上，它可以根据当前状态选择动作。然后，根据选择的动作以及当前的状态，环境采样了一种新状态，该状态由学习算法在后续的时间步上观察到。采样的状态序列和动作序列就是轨迹。采样过程引入了一种依赖于初始状态和转换概率的轨迹分布，以及根据当前状态选择动作的方式，后者叫作策略（policy）。该策略通常建模为一个神经网络，在当前状态中作为输入，并输出动作。该学习算法的目标是找到一个策略，使所有时间步上状态的期望累计成本最小化，期望与轨迹分布有关。

形式化为强化学习问题

回到我们上文中介绍的学习框架，其目标是找到使元损失最小化的更新公式。直观来看，我们将智能体看作一个优化算法，将环境看作由我们想让学习的优化器面对的目标函数集合。状态包括当前迭代和目前优化轨迹的一些特征，这可以是历史梯度、迭代数和目标值的统计。动作是用于更新迭代的迭代步向量。

在该公式中，策略实际上是计算动作（即迭代步向量）的步骤，依赖于当前迭代和历史梯度、迭代数和目标值。换言之，特定的策略代表特定的更新公式。

因此，学习该策略等于学习更新公式以及优化算法。初始状态概率分布是初始迭代、梯度和目标值的联合分布。状态转换概率分布记录了在当前状态和动作下一个可能的状态。由于该状态包括梯度和目标值，因此状态转换概率分布能够捕捉到梯度和目标值在任意给定的迭代步向量下的变化趋势。换言之，它对感兴趣的目标函数的局部几何关系进行编码。关键是，这种强化学习算法不能直接访问状态转换概率分布，因此它学习的策略不会与训练目标函数的几何结构产生过拟合。

我们选择一个状态的代价函数作为当前迭代评估的目标函数值。由于强化学习使所有时间步上的累计成本最小化，因此它本质上使所有迭代中的目标值总数（即元损失）最小化。

结果

我们就如同在 MNIST 上训练一个神经网络而训练优化算法，并就在 Toronto Faces Dataset（TFD）、CIFAR-10 和 CIFAR-100 上训练不同的神经网络的问题对优化算法进行测试。这些数据集互相没有任何相似性：MNIST 包括手写体数字的黑白图像，TFD 包括人脸的灰度图像，CIFAR-10/100 包括自然场景常见物体的彩色图像。因此学习的优化算法不可能逃避使用记忆，比如说，MNIST 上较低层的权重，并且在 TFD 和 CIFAR-10/100 上仍然表现不错。

如图所示，使用我们的算法在 MNIST（浅红色）数据集上训练的优化算法可泛化至 TFD、CIFAR-10 和 CIFAR-100，且表现优于其他优化算法。

为了理解使用我们的方法学习的优化算法的行为，我们在二维 logistic 回归问题上训练一个优化算法，并在参数空间中可视化其轨迹。值得注意的是，优化算法在低维和高维中的行为不同，因此下图中的可视化未必表示优化算法在高维中的行为。但是，它们提供了一些有用的关于可以学到的行为类型的经验。

上图显示出两个不同的未知 logistic 回归问题上不同算法的优化轨迹。每个箭头代表优化算法的一次迭代。如图所示，使用我们的方法学到的算法（浅红色）比其他算法的步长更大，在两次迭代后超过其他算法，但是没有振荡，而是采用更小的步长来逐渐回收。在第二个示例中，由于梯度消失，传统的优化算法步长较小，并因此收敛较慢。另一方面，学得的算法步长更大，收敛更快。