30多年的数学猜想被AI发现作为反例？

刚刚，来自Meta、威斯康星大学麦迪逊分校、伍斯特理工学院和悉尼大学的几位学者提出了PatternBoost，一种全新的方法，可以在一些数学问题中找到有趣的结构。

论文地址：

核心思想是交替“局部搜索”和“全局搜索”。

在第一个“局部”阶段，使用传统的经典搜索算法来生成许多理想的结构。

在第二个“全局”阶段，使用 Transformer 神经网络训练这些最佳结构。然后，将经过训练的 Transformer 样本用作第一阶段的种子，并重复该过程。

前者类似于贪心算法。例如，给定一个图，删除包含多个 4 循环的边，直到没有 4 循环。

后者的一个例子是让 Transformer 生成更多类似于最后一个过滤器的前 1% 的图像。

这种迭代交替比传统的贪婪方法或单独的非贪婪增强 Transformer 方法要好得多。

使用 Transformer 解决离散优化问题的步骤

它会比其他问题更能解决某些问题。因此，本文在许多不同的数学领域测试了相同的协议。

哪些数学问题最适合机器学习技术？或者我们最终会证明所有数学问题都适合机器学习技术吗？

这种可能性是如此令人兴奋。

PatternBoost 不仅为几个长期存在的问题找到了最著名的解决方案，还构建了一个反例，驳斥了一个 30 年来悬而未决的猜想。

例如，它可以生成网络拓扑中比较常见的无C4稠密图，即不具有由4个顶点组成的闭合路径的稠密图。

PatternBoost 在多种极端组合问题上都有出色的表现。其经典应用之一是四循环问题。

也就是说，给定顶点数 n，构造一个具有尽可能多的边且不包含 4 环的图。

此类问题因其复杂的数学结构和巨大的解决空间而对机器学习方法具有挑战性。

研究人员通过以下步骤应用PatternBoost：首先生成初始数据集，并使用Transformer模型对其进行训练以生成新样本。

使用这些新样本作为局部搜索的起点，经过多轮迭代，PatternBoost 获得了比传统方法更好的解决这个 4 周期问题的方法。

“有很多边没有三角形”问题介绍

现在让我们想象这样一个问题：在一个有n个顶点的图中，如果没有三条边可以组成一个三角形，那么它最多可以有多少条边？

第一步，我们可以提出具有许多边且在少量顶点上没有三角形的图。

那么，我们会很幸运地注意到，许多示例实际上都是二分图。

不难发现，这里大多数表现最好的图都是二分图。该定律也称为图兰三角定理或曼特尔定理。

二分图是一种特殊类型的图，其顶点可以分为两个不相交的集合，例如集合 A 和集合 B。

在二部图中，每条边都连接集合 A 中的一个顶点和集合 B 中的一个顶点。也就是说，集合 A 或集合 B 中不存在连接两个顶点的边。

但如果问题变得更棘手并且需要的不仅仅是三角形怎么办？例如五边形等更复杂的结构。此时，研究人员将很难依靠归纳和直觉来发现其最优结果中包含的规律。

因此，研究人员希望有一种通用的方法可以帮助自己发现或逐渐近似这些结构。

PatternBoost就是这样的方法！

首先，研究人员需要确定局部搜索方法和评分函数。

局部搜索方法是一种将可能包含或不包含三角形的形状作为输入，并输出得分至少与输入得分相同的形状的算法。

由于研究人员想要说明局部-全局迭代方法本身的有效性，因此他们并没有坚持优化局部搜索函数，而是采用了一种非常简单的方法。那是：

- 当搜索到的图形中也包含三角形时，删除其中一条边。

- 一旦图中不再有三角形，随机添加尽可能多的新边，而不创建新三角形

评分函数需要反映当前获得的结构接近最优结构的程度。

例如，如果图形包含任何三角形，研究人员可以决定给出负无穷大的分数，否则返回边的数量。边数越多，得分越高。

需要注意的是，如果图中存在三角形，研究者也可以直接删除三角形中的任意一条边来将分数增加至少1

具体步骤

第 1 步：创建起始数据库

研究人员的步骤如下：从一个空图开始，并以此为起点运行上述简单的局部搜索算法（即随机添加尽可能长的边而不生成三角形）。

他们重复了 40,000 次，每次都从一个空图开始，结果分数分布如图 1 所示（因为三角形永远不会出现在本地搜索的输出中，所以这里的分数只是边的数量）。

大多数图形分数的分布是平滑分布的，峰值为 66。然后研究人员保留了数据集中前 25% 的分数；这些图表作为训练集。

训练集的得分分布如图1右侧的直方图所示。

训练集中的每个图都可以用其邻接矩阵表示，该矩阵有 n² = 20² = 400 个条目。

研究人员注意到，邻接矩阵是对称的并且没有环，因此可以使用矩阵的上三角部分代替整个矩阵，将其减少到 20×19/2 = 190。

研究人员使用的 Transformer 接受一维输入；因此，研究人员可以通过逐行写出上三角矩阵并在每行后添加分隔符（本例中为逗号）来展平上三角矩阵，如图 2 所示。

在开始训练之前，可以通过字节对编码 (BPE) 标记化对数据进行标记，以进一步压缩数据。

换句话说，如果研究人员发现字符串“00101”在数据集中出现了很多次，那么研究人员就会引入一个新的字符，例如“2”来表示这个字符串。

第 2 步：训练 Transformer

研究人员使用了 Makemore，这是 Andrej Karpathy 的一个简单的 Transformer 实现。

他的代码的优点是公开可用且易于修改，并且提供了坚实的基线，以便研究人员可以尝试用更复杂的方法超越它。

研究人员使用了一个微型 2 层 Transformer，有 4 个头和 16 个嵌入尺寸。

他们训练这个 Transformer 生成与初始数据集中的序列“相似”的序列，类似于给 Transformer 一个大型的英语句子数据库（即大部分序列都是单词）来训练它生成更多的英语句子。 。

在训练的每个阶段，可以要求 Transformer 预测给定的 k 个标记序列之后的下一个标记。特别是，对于数据集中的每个 k 和每个图 G（由令牌序列表示），可以要求 Transformer 在给定前 k 个令牌的情况下预测第 k+1 个令牌。

“损失”衡量 Transformer 未能正确预测 G 中实际下一个标记的频率。经过 15,000 步训练后，训练集上的损失降至 2.07，测试集上的损失为 2.09。

第 3 步：从 Transformer 获取新结构

接下来，研究人员要求 Transformer 生成新的结构，这些结构在某种“全局”意义上与研究人员迄今为止遇到的最佳图（即训练集中的图）相似。

研究人员通过这种方式生成了 100,000 个标记化的新图形。将 token 序列解码为矩阵（或尝试将其解码为矩阵）后，我们得到了 37,000 个矩阵条目（190），这与 20 顶点图的邻接矩阵一致。

步骤 4：从 Transformer 获得的新结构中运行本地搜索

研究人员将从小型模型中获得的 37,000 个有效结构图重新输入到他们简单的本地搜索算法中。

也就是说，从这 37,000 个图形中的每一个中，研究人员首先贪婪地删除边缘以删除所有三角形，然后尽可能长时间地随机添加边缘，而不创建任何新三角形。

第 5 步：重复此过程

最后，研究人员反复从上一代中提取最好的 10,000 个短语，使用与之前相同的标记对它们进行分段，并在这个新的训练集上对 Transformer 进行微调。

请注意，每次迭代不需要从头开始训练。通过另外 5 个循环，模型很快学会仅生成完整的二分图，并且大多数二分图具有相等的两部分大小，请参见图 4。

可以直观地发现，随着迭代次数的增加，分数分布的峰值逐渐变得越来越高，从75分转变为最终满分100分，这直接证明了局部+全局联合迭代搜索的有效性过程。

一个长期未解的猜想：直径为 d 的 d 维超立方体的生成子图

超立方体是一种常见的网络拓扑结构。其结构是一个高度对称的n维立方体，每个顶点都直接与所有其他顶点相连。

在超立方体中，直径是一个重要的概念，因为它表示从任何顶点到另一个顶点所需的最大步数。

对于并行计算网络，例如大规模并行计算机中的处理器网络，超立方体的直径是描述其通信效率的关键参数，因为它直接影响网络中的通信速度和延迟。

因此，研究超立方体的直径以及如何通过改变其结构来优化直径已成为一个重要的研究方向。

论文中提到的长期未解决的问题是：在不增加直径的情况下，d 维超立方体最多可以去除多少条边？

该问题由 Niali Graham 和 Frank Harary 于 1992 年首次提出。该问题也可以表示为如何构造直径始终为 d 的 d 维超立方体的最小生成子图。

针对这个问题，目前提出的猜想如下：

他们观察到，如果固定两个相反的顶点v和v′，并通过为每个顶点u（u不属于{v，v′}）构造一个子图G，其中包括一条通向d维立方体的路径生成的子图被完全覆盖并且直径为 d。这样的子图至少有

条带边缘，并且这种构造可以通过多种方式实现。

问题出现了：是否有一种使用更少边缘的更好的结构？格雷厄姆推测这种结构实际上是最优的。

直径为 5 的 5 维超立方体的子图，包含 40 条边。请注意，每个顶点都有一条向下的边和一条向上的边，即不存在阻挡顶点。

对于PatternBoost来说，有一种很自然的方式可以成立这个猜想。具有跨度和直径 d 的子图的分数可以定义为其中的边数（研究人员试图最小化边数）。

举个反例

对于局部搜索，最简单的算法是，给定一个子图G，随机向G添加边，直到它成为直径为d的跨度图，然后在保持直径为d的情况下尽可能长时间地随机去除边。

研究人员对d=5和6的情况进行了实验。

对于 d=5，上述构造似乎是最佳的，但对于 d=6，研究人员能够找到一张具有 81 条边的图（而不是上述构造中的边）。

边缘），见图 10。

这推翻了之前的猜测，标志着该问题30年来首次取得进展。

一个有趣的观察是，对于较大的 d 值，下限或上限是否更接近真实情况。

使用人工智能生成纯数学结构

总之，在本文中，研究人员介绍并说明了一种称为 PatternBoost 的计算方法，用于在纯数学中生成有趣的结构。

该方法涉及“局部”和“全局”步骤的迭代交替。前者通常是简单的贪心算法，后者是遗传算法与 Transformer 相结合，这是一种灵活的机器学习技术，研究人员认为特别适合处理此类问题。

要了解这种迭代可能是什么样子，请考虑集体协作迭代的示例，即自行车的设计。

-“本地”步骤涉及许多单独的自行车制造商，每个制造商都对其设计进行了一系列微调，以使其尽可能高效和舒适。

- “全球”步骤涉及生活在世界各地的人们看到他们周围有许多自行车，每辆自行车都经过仔细的本地优化，然后根据他们观察到的自行车开发新的自行车设计。

当然，这个新设计随后将由其设计师和其他人仔细优化；如果经过这些调整，新自行车被证明特别舒适和高效，它们将被大量出售，并由下一位潜在设计师加入。在自行车的大队列中……它一直在继续。

数学对象不是自行车。但人类可以抽象出自行车的特征，并开发出研究人员认为是自行车的新物体，即使它们与任何现有的实例都不相同，数学家的数学对象也是如此。然而，这个过程通常很难自动化。

研究人员对这里描述的方法的希望是，机器学习技术（尤其是 Transformer）至少具有某种程度的这种能力——也就是说，当面对一系列数学实体时，它们可以生成更多“在某些方面”的例子相同的类型可以很容易地互相引用和迭代。

该研究人员的工作深受第三作者早期工作的影响。在这项工作中，强化学习中的交叉熵方法被用来寻找组合学中几个问题的反例。

交叉熵方法的问题在于其可扩展性：当序列长度超过几百个标记时，底层神经网络变得难以训练。

在人工智能中，当尝试使用基本神经网络来预测一长串字母或单词的下一个标记时，也会遇到类似的问题，而 Transformer 架构在此类问题上表现良好。

PatternBoost 的主要优点之一是其广泛的适用性。 PatternBoost 可以通过添加一个全局步骤来改进许多优化问题的结果，该全局步骤使用 Transformer 为本地搜索建议更好的起点。

PatternBoost 可以被认为是放置在任何本地搜索方法之上的额外层，通常可以获得比单独使用本地搜索更好的解决方案。

简而言之，无论研究人员使用哪种本地搜索算法，PatternBoost 通常都会使其变得更好。

研究人员强调，他们的主要目标是为数学家开发一种有用且简单的工具，不需要深厚的机器学习专业知识或使用工业级计算能力。

使用机器学习作为数学实用工具的一个困难是机器学习本身很复杂！人们可能会花费大量时间调整超参数、探索不同的标记化解决方案等。

在研究人员看来，PatternBoost 的优点之一是其 Transformer 架构非常灵活，通常可以直接使用，不需要数学家进行太多调整，因为他们的专业和兴趣可能在其他领域。

他们使用了 Andrej Kaparthy 的 Makemore 提供的漂亮且简单的 Transformer 实现，在研究人员的实验中，该实现似乎可以在广泛的数学环境中产生有效的输出。

这里讨论的问题只是他们在开发 PatternBoost 时尝试的前几个问题 - 他们希望并期望其他数学家有兴趣进行进一步的实验，以帮助揭示哪些数学问题适合机器学习增强方法。神秘。

特别是，本文讨论的示例集中于极端组合领域，其中 Transformer 用于构造在某些约束下尽可能大的组合示例。

当然，组合结构是最容易渲染为 Transformer 输入的实体；但他们并不认为该方法原则上仅限于这个数学领域。

事实上，这个方法中没有任何内容是特定于数学的！他们也非常有兴趣了解 PatternBoost 是否可以应用于数学之外的问题。

一个明显的挑战是，在数学中，通常可以机械、可靠且快速地评估所提出的示例，这对于 PatternBoost 至关重要；而在其他领域，评估可能会更加困难。

涉及的机器学习技术

模型训练完成后，研究人员将从“空序列”t0开始生成候选解，并从训练模型预测的分布中提取第一个标记t1。

然后，研究人员将 t0 t1 序列输入到模型中，并从预测分布中采样第二个标记 t2。重复此过程直到生成完整的解决方案。

这将鼓励模型生成与其训练数据相似的序列（即，有希望解决研究人员的问题）。

为了将数学结构（例如网格和图形）编码为 Transformer 可以处理的形式，需要将这些结构转换为标记序列。这个过程称为“分词”。

下面是具体的编码方法：

对于网格编码，×网格可以由n^2个二进制条目表示，每个条目代表一个单元的状态（0或1）。

即使 n 的值适中，这种简单的二进制表示也可能导致序列非常长，从而增加学习复杂性。

为了减少序列长度，研究人员可以将多个二进制条目编码为单个标记，从而权衡词汇量大小和序列长度。

例如，可以将 4 个二进制条目编码为一个标记，这会增加词汇量，但会减少序列长度。

图编码可以采用邻接矩阵的表示方法。当用二进制表示时，可以用n(n-1)个二进制条目来表示，每个条目代表一条边的存在状态。

类似地，可以将多个二进制条目编码为单个令牌以减少序列长度。

每个序列始终以特殊标记开始并以标记结束，以便模型知道序列在哪里开始和结束。

通过将数学结构（例如网格和图形）编码为 Transformer 可以处理的标记序列，PatternBoost 能够利用 Transformer 强大的建模功能来生成复杂的数学结构。

这种编码方法不仅减少了序列长度并提高了学习效率，而且使模型能够生成与训练数据相似的有前途的解决方案。该方法在几个离散数学问题中证明了其有效性和灵活性。

参考：

本文来自微信公众号“新智元”，编辑：HZh编辑部，36氪授权发布。