2022/10/05 15:29

机器之心编辑部机器之心报道

排序、搜索、动态规划，DeepMind用一个神经算法学习器给解决了

来自 DeepMind 等机构的研究者提出了一个通用神经算法学习器，其能够学习解决包括排序、搜索、贪心算法、动态规划、图形算法等经典算法任务，达到专家模型平均水平。

近年来，基于深度神经网络的机器学习系统取得了巨大的进步，尤其是在以感知为主的任务方面。这些模型通常需要在分布内泛化，这意味着它们的训练集和验证集需要有输入预期分布。相比之下，想要模型在推理任务上表现出色，这就要求即使在分布外（out-of-distribution, OOD）泛化时模型也能提供合理的输出。

然而，多数神经网络在 OOD 方面表现不佳。事实上，可以进行神经推理的架构需要算法对齐、自监督学习等其他算法的辅助。更进一步讲，这些模型需要在基于观察的基础上，对生成的新知识有一定的稳健性，特别是当这些知识脱离训练数据域时。

本文中，来自 DeepMind 等机构的研究者提出一个通用神经算法学习器：具有单一参数集的 GNN，其能够同时学习解决经典算法任务，包括排序、搜索、贪心算法、动态规划、图形算法、字符串算法和几何算法，达到专家模型平均水平。

具体地，该研究利用 CLRS 基准从实证上表明，就像在感知领域取得的成功一样，通用算法学习器可以通过整合知识来构建。也就是说，只要我们能学会在单任务模式下很好地执行算法，就有可能在多任务模式下有效地学习算法。

受此启发，该研究对 CLRS 的输入表示、训练机制和处理器架构进行一系列改进，与现有技术相比，改进后的平均单任务性能提高了 20% 多。然后，本文利用这些改进对多任务学习器进行消融实验。结果表明，通用学习器能够有效地整合由专家模型捕获的知识。

论文地址：https://arxiv.org/pdf/2209.11142.pdf

可以说这项研究是一个重要的里程碑，表明即使在具有完全不同的控制流任务中，该研究也可以有意义地整合推理能力，并在多个任务中超过相应的单任务专家的 OOD 性能。

正如佐治亚理工学院机器学习博士生 Aran Komatsuzaki 所总结的：「本文构建了一个通用神经算法学习器，能够学习执行各种算法的单个 GNN 处理器，例如排序、搜索、动态规划、路径查找和几何。」

研究介绍

研究者提出的通用神经算法学习器如下图 1 所示。

论文第 3 章是主旨部分，主要介绍了表示、训练机制和架构的改进，使得单个模型的性能明显优于之前在 CLRS-30 上发布的 SOTA 技术。

CLRS 基准定义了五种类型的特性：标量（scalar）、分类、掩码、mask_one 和指针，它们都有自己的编码和解码策略以及损失函数。

本文中具体的改进包括但不仅限于：

数据集和训练：移除 teacher forcing。在评估时，模型无法访问数据集中的 hint，只能依靠已有的 hint 进行预测。在先前的模型中，训练期间提供了概率为 0.5 的 ground-truth hint，在没有 teacher forcing 的情况下，当存在 scalar hints 时，损失倾向于沿轨迹无界增长，从而破坏了训练的稳定性。

这项工作整合了几个重要的稳定变化，足以完全消除 teacher forcing 带来的影响，使训练与评估保持一致。由于 teacher forcing 的存在，排序算法和 Kruskal 算法的性能显著下降。在移除了 teacher forcing 之后，本文还对训练数据进行了扩充，以防止模型过拟合。

Soft hint 传播。本文将 softmax 用于分类，mask_one 、指针类型、logistic sigmoid 用于掩码类型。如果没有这些 soft hints，排序算法的性能会下降（类似于有 teacher forcing 的情况）。

利用编码器初始化和梯度裁剪提高训练稳定性。该研究使用 Xavier 进行初始化，从而有效地减少了输入维度仅为 scalar hint 的初始权重。此外，该研究还对编码器、解码器、网络处理器进行了改进。

对模型改进之后得到一组超参数模型，经过训练，该模型在 CLRS-30 上达到了 SOTA 性能。下表 1 和表 2 显示了包括 Memnet、MPNN、PGN 等模型在内的 micro-F_1 得分。

下图 2 显示了改进模型与 SOTA 模型之间的比较。本文的模型比次优模型（见表 1）平均性能提高了 20% 以上，并且除了一个算法系列之外，所有算法的性能都比其他模型有了显著提高。

从实验可以看出，有两个算法系列具有显著的 OOD 性能改进：第一个是几何算法，现在求解接准确率约 94% OOD ，而之前的最佳结果约为 73%；第二个是字符串算法，模型现在求解准确率超过 49%，而之前的最佳值约为 3%。与之前的 SOTA 相比，本文在 24 种算法中准确率超过 60%，17 种算法的准确率超过 80%，11 种算法的准确率超过 90%。

下图 3 比较了单任务 Triplet-GMPNN 与多任务模型的性能。

为了独立评估模型改进的效果，该研究还进行了消融实验。下图 4a 显示了 vanilla 训练和分块训练在性能上的显著差异；图 4b 显示了累积消融的结果：逐渐删除单个改进部分的结果。

理论DeepMind神经算法学习器

相关数据

排序算法技术

排序算法是将一串数据依照特定排序方式进行排列的算法，最常用到的排序方式是数值顺序以及字典顺序。基本上，排序算法的输出必须遵守下列两个原则：输出结果为递增序列（递增是针对所需的排序顺序而言）；输出结果是原输入的一种排列、或是重组。

来源：维基百科

动态规划技术

动态规划（也称为动态优化），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划将复杂的问题分解成一系列相对简单的子问题，只解决一次子问题并存储它的解决方案（solution），下一次遇到同样的子问题时无需重新计算它的解决方案，而是简单地查找先前计算的解决方案，从而节省计算时间。动态规划适用于有最优子结构（Optimal Substructure）和重叠子问题（Overlapping Subproblems）性质的问题。

来源：Wikipedia

权重技术

线性模型中特征的系数，或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0，则相应的特征对模型来说没有任何贡献。

来源：Google AI Glossary

机器学习技术

机器学习是人工智能的一个分支，是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论，机器学习与推断统计学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

感知技术

知觉或感知是外界刺激作用于感官时，脑对外界的整体的看法和理解，为我们对外界的感官信息进行组织和解释。在认知科学中，也可看作一组程序，包括获取信息、理解信息、筛选信息、组织信息。与感觉不同，知觉反映的是由对象的各样属性及关系构成的整体。

来源：维基百科

基准技术

一种简单的模型或启发法，用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

来源：Google ML Glossary

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

损失函数技术

在数学优化，统计学，计量经济学，决策理论，机器学习和计算神经科学等领域，损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

来源：Wikipedia

超参数技术

在机器学习中，超参数是在学习过程开始之前设置其值的参数。相反，其他参数的值是通过训练得出的。不同的模型训练算法需要不同的超参数，一些简单的算法（如普通最小二乘回归）不需要。给定这些超参数，训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式，并且必须对其进行调整以便模型能够最优地解决机器学习问题。在实际应用中一般需要对超参数进行优化，以找到一个超参数元组（tuple），由这些超参数元组形成一个最优化模型，该模型可以将在给定的独立数据上预定义的损失函数最小化。

来源：Wikipedia

验证集技术

验证数据集是用于调整分类器超参数（即模型结构）的一组数据集，它有时也被称为开发集(dev set)。

来源：Wikipedia

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

准确率技术

分类模型的正确预测所占的比例。在多类别分类中，准确率的定义为：正确的预测数/样本总数。在二元分类中，准确率的定义为：(真正例数+真负例数)/样本总数

来源：Google ML Glossary

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

来源：Wikipedia

参数模型技术

在统计学中，参数模型是可以使用有限数量的参数来描述的分布类型。这些参数通常被收集在一起以形成单个k维参数矢量θ=（θ1，θ2，...，θk）。

来源：Wikipedia

贪心算法技术

贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。