Transformer打破三十年数学猜想！算法杀手攻克数学难题

新智元

2024-11-13 18:25发布于北京新智元官方账号

全文2981字，阅读约需9分钟，帮我划重点

划重点

01Meta等学者提出的PatternBoost算法在数学问题中寻找有趣的结构，首次获得了30多年数学猜想的进展。

02PatternBoost算法通过交替进行局部搜索和全局搜索，利用Transformer神经网络进行训练。

03在多个极值组合学问题中，PatternBoost表现优异，如无4-圈问题。

04除此之外，PatternBoost还构造了一个反例，反驳了一个已悬而未决30年的猜想。

05未来可能性令人期待，PatternBoost算法可能适用于所有数学问题。

以上内容由腾讯混元大模型生成，仅供参考

新智元报道

编辑：编辑部 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。

查看原图 75K