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

1,384 0 0

文章摘要

【关键词】 PatternBoost、数学突破、神经网络、组合学、机器学习

最近，Meta、威斯康星大学麦迪逊分校、伍斯特理工学院和悉尼大学的学者们提出了一种名为PatternBoost的新方法，该方法在解决某些数学问题上取得了突破性进展。PatternBoost通过结合局部搜索和全局搜索，交替使用经典搜索算法和Transformer神经网络，以寻找数学问题中的有趣结构。这种方法不仅找到了多个长期问题的最优解，还反驳了一个悬而未决30年的数学猜想。

PatternBoost的核心在于迭代交替的两个阶段：局部搜索阶段和全局搜索阶段。在局部搜索阶段，使用传统算法生成理想构造；而在全局搜索阶段，利用Transformer神经网络对最优构造进行训练，并将其作为种子反馈到局部搜索阶段。这种迭代交替的方法在多个极值组合学问题中表现出色，尤其是在无4-圈问题上，PatternBoost通过生成C4-free稠密图，即不存在由4个顶点组成的闭合路径的稠密图，取得了比传统方法更佳的解。

研究者们还探讨了PatternBoost在其他数学问题上的潜力，例如在不增加直径的情况下，从d-维超立方体中删除的最大边数问题。通过PatternBoost，研究者们发现了一个反例，推翻了之前关于这个问题的猜想，标志着在这个问题上30年来的首次进展。

PatternBoost的优势在于其广泛的适用性和灵活性。它可以作为任何局部搜索方法的额外层，通常能比单独使用局部搜索获得更好的解决方案。研究者们希望PatternBoost能成为数学工作者的一个有用工具，不需要深入的机器学习专业知识或使用工业级计算能力。他们期待其他数学家能够进一步实验，探索PatternBoost在哪些数学问题上适用，甚至可能扩展到数学之外的问题。