Transformer打破三十年数学猜想！Meta研究者用AI给出反例，算法杀手攻克数学难题

新智元报道

编辑：编辑部 HZh

【新智元导读】30多年的数学猜想首次获得了进展！Meta等学者提出的PatternBoost，使用Transformer构造了一个反例，反驳了一个已悬而未决30年的猜想。是否所有数学问题都适合机器学习技术？这样的未来太令人期待了。

30多年的数学猜想，被AI发现了一个反例？

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

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

其核心思想是交替进行「局部搜索」和「全局搜索」。

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

在第二个「全局」阶段，使用Transformer神经网络对这些最优构造进行训练。然后，将训练好的Transformer样本用作第一个阶段的种子，并重复该过程。

前者类似于贪心算法，比如给定一个图形，去除包含多个4-圈的边，直到没有4-圈为止。

而后者的一个例子，是让Transformer生成更多类似于上次筛选中表现前1%的图。

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

结合Transformers来求解离散优化问题的步骤

比起某些问题，它会更擅长解决另一些问题。因此，这篇论文在许多不同的数学领域测试了相同的协议。

哪些数学问题最适用于机器学习技术？或者说，最终我们将证明，所有数学问题都适合机器学习技术？

这个可能性，实在太令人兴奋了。

PatternBoost不仅找到了几个长期问题的最佳已知解决方案，而且还构造了一个反例，反驳了一个已悬而未决30年的猜想。

比如可以生成网络拓扑中较为常见的C4-free稠密图，也就是一幅不存在由4个顶点组成的闭合路径的稠密图。

PatternBoost在多个极值组合学问题中表现优异，其中一个经典应用是，就是无4-圈问题。

即在给定顶点数n的情况下，构造尽可能多的边而不包含4-圈的图。

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

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

将这些新样本作为局部搜索的起点，经过多轮迭代后，PatternBoost在这个无4-圈问题上获得了比传统方法更佳的解。

「许多边没有三角形」问题

问题引入

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

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

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

不难发现，这里面大多数表现最优的图形都是二分图。而这一规律也被称为称为Turán三角定理或Mantel定理。

二分图（Bipartite Graph）是一种特殊类型的图，它的顶点可以被分成两个互不相交的集合，比如说集合A和集合B。

在二分图中，每条边都连接着集合A中的一个顶点和集合B中的一个顶点，也就是说，集合A中和B中各自都不存在将两个顶点相连接的边。

但是如果问题变得更加艰难，要求的结构不仅仅只是三角形呢？比如五边形这样更为复杂的结构。这时研究者就很难再凭借归纳和直觉去发现其最优结果中蕴含的规律了。

所以研究者希望有一种通用的方法，可以帮助发现或自行逐渐逼近这些结构。

PatternBoost就是这样一种方法！

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

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

由于研究者想要说明的是局部-全局迭代方法的有效性本身，所以不执着于优化局部搜索函数，而是采用了很简单的办法。也就是：

- 当搜索到的图还包含三角形时，就删掉其中的一条边

- 一旦图中已经没有三角形，则在不创建新三角形的情况下，尽可能多地随机添加新边

评分函数则需要体现出当前得到的结构逼近于最优结构的程度。

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

需要注意的是，如果图形中有三角形，研究者也可以从三角形中直接删除任何边，以使分数至少增加1

具体步骤

第一步：创建起始数据库

研究者的步骤如下：从空图开始，以此为起点运行上述简单的局部搜索算法(即在不产生三角形的情况下，尽可能长时间地随机添加边)。

他们重复了40,000次，每次都从空图开始，得到的分数分布如图1所示（由于局部搜索的输出永远不会出现三角形，因此这里的分数只是边的数量）。

大部分图形分数的分布都是一个平滑的分布，峰值为66。然后研究者保留了该数据集中得分最高的25%；这些图形将作为训练集。

从图1右侧的直方图中可以看到训练集的分数分布。

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

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

研究者使用的Transformer接受一维输入；因此，研究者可以将上三角矩阵逐行写出，并在每行后加上分隔符(在本例中为逗号)，从而将其扁平化，如图2所示。

在开始训练之前，可以通过Byte-Pair Encoding (BPE) Tokenization来标记化数据以去进一步的数据压缩。

也就是说，如果研究者发现字符串「00101」在数据集中出现了很多次，那么研究者就引入一个新的字符，比如「2」，来表示这个字符串。

第二步：训练Transformer

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

他的代码的优点是，它是公开可用的，并且易于修改，并且它提供了一个稳固的基线，因此研究者可以尝试用更复杂的方法超越它。

研究者使用了一个微小的2层Transformer，包含4个头部和16的嵌入维度。

他们训练这个Transformer来生成与初始数据集中的「相似」的序列，方法类似于将一个大型英语句子数据库（即序列中的大多数是单词）给Transformer进行训练，使其能够生成更多的英语句子。

在训练的每一个阶段，都可以让Transformer预测给定的k个token序列之后的下一个token。特别地，对于每一个k和数据集中每个图G（用token序列表示），可以让Transformer在给定前k个token的情况下预测第k+1个token。

「损失」衡量了Transformer未能正确预测G中实际下一个token的频率。经过15,000步的训练后，训练集的损失降到2.07，测试集的损失为2.09。

第三步：从Transformer获取新结构

接下来，研究者要求Transformer生成在某种「全局」意义上与研究者迄今为止遇到的最佳图形(即训练集中的图形)相似的新结构。

研究者以这种方式生成了100,000个tokenized的新图形。在将token序列解码为矩阵(或尝试解码为矩阵)后，研究者得到了37,000个矩阵的条目数(190)，这与20个顶点图的邻接矩阵相符。

第四步：从Transformer中获得的新结构中，运行本地搜索

研究者把从小模型中得到的37000个有效结构图，重新输入到他们的简单局部搜索算法中。

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

第五步：重复此过程

最后，研究者重复提取上一代中最好的10,000个词组，使用之前相同的token对它们进行分词，并在这个新的训练集上微调Transformer。

请注意，每次迭代都不需要从头开始训练。通过再进行5次循环，模型很快学会只生成完整的二分图，而且这些二分图中的大多数都具有相等的两部分大小，见图4。

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

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

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

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

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

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

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

这个问题最早由Niali Graham和Frank Harary在1992年提出，问题也可以表述为，怎么构造直径始终是d的d维超立方体的最小生成子图。

对于这个问题，曾经提出的猜想具体是这样的：

他们观察到，如果固定两个相对的顶点v和v′，并通过为每个顶点u（u不属于{v, v′}）构建一个子图G，其中包括一条通向在d-维立方体中更接近v的顶点的边和一条通向在d-维立方体中更接近v′的顶点的边，则生成的子图是全覆盖的且具有直径d。这样的子图至少有 条边，并且可以通过多种方式实现这样的构造。

问题来了：是否存在一种更好的构造，可以用到更少的边？Graham猜想，这种构造实际上就是最优的。

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

对于PatternBoost，有一种自然的方法来建立这个猜想。一个具有跨度并且直径为d的子图的分数可以定义为其中的边数（研究者试图将其最小化）。

反例的提出

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

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

对于d=5，上述构造似乎是最优的，但对于d=6，研究者能够找到一个具有81条边的图（而非上述构造中的 条边），见图10。

这推翻了之前的猜想，并标志着在这个问题上30年来的首次进展。

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

用AI生成纯数学构造

总的来说，在本文中，研究者介绍并举例说明了一种称为PatternBoost的计算方法，用于生成纯数学中有趣的构造。

该方法涉及「局部」与「全局」步骤的反复交替。前者通常是一个简单的贪婪算法，后者则是一种结合Transformer的遗传算法，这是一种灵活的机器学习技术，研究者认为其特别适合处理此类问题。

为了理解这种迭代可能的样子，可以考虑一个集体合作迭代的例子，即自行车的设计。

- 「局部」步骤涉及许多单个自行车制造商各自对他们的设计进行一系列精细调整，努力使其尽可能地高效和舒适。

- 「全局」步骤则涉及生活在世界各地的人们，他们看到周围的许多自行车，每一辆都经过精心的局部优化，然后基于他们观察到的自行车进而设计开发出新的自行车设计。

当然，这种新设计随后会由其设计者和其他人精心优化；如果经过这些调整后，新自行车被证明特别舒适和高效，那么它们将被大量销售，并加入下一位潜在设计者观察到的一般自行车队列中……如此周而复始。

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

研究者对这里描述的方法的希望在于，机器学习的技术（尤其是 Transformer）至少具备某种程度的这种能力——即面对一系列数学实体时，它们可以产生更多在某些方面「同类」的例子，便于互相参照，进行迭代。

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

交叉熵方法的问题在于其扩展性：当序列长度超过几百个Token时，基础神经网络就会变得难以训练。

在AI中，当尝试使用基础神经网络对长序列的字母或单词进行下一个Token预测时，也会遇到类似的问题，而Transformer架构正是在这类问题上表现出色。

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

PatternBoost可以视为放置在任何局部搜索方法之上的额外层，通常能比单独使用局部搜索获得更好的解决方案。

简单来说，无论研究者使用何种局部搜索算法，PatternBoost 通常都能使其更好。

研究者强调，研究者的主要目标是为数学工作者开发一个有用且简单的工具，该工具不需要深入的机器学习专业知识或使用工业级计算能力。

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

在研究者看来，PatternBoost的一个优点在于其Transformer架构表现得非常具有弹性，通常可以直接使用，而不需要数学家进行过多的调整，因为他们的专业和兴趣可能在其他领域。

他们使用了Andrej Kaparthy的Makemore提供的一个美观且简单的Transformer实现，在研究者的实验中，它似乎在广泛的数学背景下都生成了有效的输出。

这里讨论的问题只是他们在开发PatternBoost时尝试的最初几个问题——他们希望并期望其他数学家会兴致盎然地进行进一步的实验，从而帮助揭开哪些数学问题适合于机器学习增强方法的这一神秘面纱。

特别是，本文讨论的例子主要集中在极值组合数学领域，其中Transformer被用来构造在某些约束条件下尽可能大的组合例子。

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

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

显而易见的一个挑战是，在数学中，一个被提议的例子通常可以被机械地、可靠快速地评估，这对PatternBoost至关重要；而在其他领域，评估可能会比较困难。

涉及到的机器学习技术

模型训练完成后，研究者会从「空序列」t0 开始生成候选方案，并从训练模型预测的分布中抽取第一个标记t1。

然后，研究者会向模型输入t0 t1序列，并从预测的分布中采样第二个token t2。如此反复，直到生成完整的解决方案。

这将鼓励模型生成与其训练数据类似的序列（即研究者问题的有希望的解决方案）。

为了将数学结构（如网格和图）编码为Transformer可以处理的形式，需要将这些结构转换为token序列，这一过程称为「分词」。

以下是具体的编码方法：

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

即使n值适中，这种朴素的二进制表示也会导致非常长的序列，增加学习的复杂性。

为了减少序列长度，研究者可以将多个二进制条目编码为一个标记，从而在词汇表大小和序列长度之间进行权衡。

例如，可以将4个二进制条目编码为一个token，这样词汇表大小会增加，但序列长度会减少。

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

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

每个序列始终以特殊的 标记开始，以 标记结束，以便模型知道序列的开始和结束位置。

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

这种编码方法不仅减少了序列长度，提高了学习效率，还使得模型能够生成与训练数据相似的有希望的解决方案。这种方法在多个离散数学问题中展示了其有效性和灵活性。

参考资料：

https://arxiv.org/abs/2411.00566