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

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

引用

腾讯

1.

https://new.qq.com/rain/a/20241113A07P8X00

Meta等机构学者近日提出了一种名为PatternBoost的全新算法，该算法通过结合Transformer神经网络，在数学问题中寻找有趣结构，并首次在30多年未解的数学猜想上取得重要进展。

PatternBoost算法的核心思想

PatternBoost算法的核心思想是交替进行「局部搜索」和「全局搜索」：

1. 在第一个「局部」阶段，使用传统的经典搜索算法来生成许多理想的构造。
2. 在第二个「全局」阶段，使用Transformer神经网络对这些最优构造进行训练。然后，将训练好的Transformer样本用作第一个阶段的种子，并重复该过程。

这种迭代交替方式比传统的贪婪方法或单独的非贪婪增强Transformer方法表现更优。

PatternBoost在多个数学问题中的应用

研究团队在多个极值组合学问题中测试了PatternBoost算法，其中一个经典应用是「无4-圈问题」。在这个问题中，目标是在给定顶点数n的情况下，构造尽可能多的边而不包含4-圈的图。

研究者通过以下步骤应用PatternBoost：

1. 生成一个初始数据集，并使用Transformer模型对其进行训练以生成新样本。
2. 将这些新样本作为局部搜索的起点，经过多轮迭代后，PatternBoost在这个无4-圈问题上获得了比传统方法更佳的解。

PatternBoost在「许多边没有三角形」问题中的具体应用

研究者首先确定了局部搜索方法和评分函数：

• 局部搜索算法：当搜索到的图还包含三角形时，就删掉其中的一条边；一旦图中已经没有三角形，则在不创建新三角形的情况下，尽可能多地随机添加新边。
• 评分函数：如果图包含任何三角形，给出负无穷大的分数；否则返回边的数量。

具体步骤如下：

1. 创建起始数据库：从空图开始，运行局部搜索算法40,000次，保留得分最高的25%作为训练集。

2. 训练Transformer：使用一个简单的2层Transformer模型，经过15,000步训练后，训练集损失降至2.07，测试集损失为2.09。

3. 从Transformer获取新结构：生成100,000个tokenized的新图形，解码得到37,000个有效矩阵。

4. 从Transformer中获得的新结构中，运行本地搜索：将37,000个有效结构图重新输入简单局部搜索算法。

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

重要突破与未来展望

PatternBoost不仅找到了几个长期问题的最佳已知解决方案，而且还构造了一个反例，反驳了一个已悬而未决30年的猜想。这一突破性进展引发了对未来可能性的期待：是否所有数学问题都适合机器学习技术？这样的未来令人兴奋。

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