编译 | 琰琰
编辑 | 青暮
近日，以色列特拉维夫大学研究团队在预印论文库提交了一篇名为“Constructions in combinatorics via neural networks“的论文，在这篇论文中，研究人员通过机器学习算法证伪了图论（Graph Theory）领域的5个数学猜想。
图论是数学领域的一个重要分支，存在着大量长期无法证实或证伪的数学猜想。论文一作Adam Zsolt Wagner表示，“数学家认为这些猜想是正确的，但无法证明它们，我们尝试使用AI算法来寻找一些示例，发现这些示例将反驳图论中一些长期存在的猜想”。
要证伪一个数学猜想虽然只需要提出一个反例，但不一定是件容易的事情。比如近期被证伪的 单位猜想， 从提出到被证伪，相隔了80年的时间。
论文地址：https://arxiv.org/pdf/2104.14516.pdf
这些猜想包括：
1、关于图的最大特征值和匹配数之和的猜想，由M. Aouchiche 和 P. Hansen在论文“A survey of automated conjectures in spectral graph theory”中提出，论文发表于2010年。
2、Aouchiche–Hansen提出的关于图的距离谱和邻近性的猜想，由M. Aouchiche 和 P. Hansen在论文“Proximity, remoteness and distance eigenvalues of a graph”中提出，论文发表于2016年。
3、K. L. Collins在论文“On a conjecture of Graham and Lov´asz about distance matrices”（发表于1989年）中提出的猜想，作者通过证明树的邻接多项式和距离多项式的系数序列的峰值可以相距很远反驳了这个猜想。
4、L. Hogben and C. Reinhart在论文“Spectra of variants of distance matrices of graphs and digraphs: a survey”（发表于2021年）中提出的猜想，作者证明了在距离拉普拉斯算子的余谱下，图的传输正则性不保持，从而反驳了这个猜想。
5、J. Aaronson, C. Groenland, A. Grzesik, B. Kielak, 和 T. Johnston在论文“Exact hyperplane covers for subsets of the hypercube”（发表于2020年）中提出的猜想，其提出可以用很少的超平面覆盖超立方体的某些子集。
1
交叉熵方法
计算机辅助证明在数学猜想中有着悠久的历史，如Appel和Haken在1976年证明了四色定理，Hales在1998年证明了开普勒猜想。近几年，随着人工智能技术不断取得新突破，机器学习算法，尤其是强化学习逐渐成为数学家们普遍使用的科学工具之一。
在最新的研究中，基于强化学习的AI已经能够在Atari游戏中达到超过人类的水平。这些研究成果，引起了作者的思考：如果不为算法提供任何关于问题的先验知识，它是否可以在组合数学和图论中发现证实或证伪猜想的反例？
在强化学习领域，深度Q网络及其变体，如Double Deep Q-Networks和Dueling Deep Q-Networks已经取得了广泛成功。
这些算法适合小动作空间问题，对于图论问题都是不错的选择。作者表示，在经过尝试后，他们发现这些方法在稀疏奖励设置环节需要很长时间的训练。虽然该问题可以得到有效的解决，如在sessions 期间给予某种人工奖励来指导agent，但这样做会引入其它问题，或者在不知情的下影响反驳猜想的目标。
因此，在有限的计算资源下，作者发现一种名为深度交叉熵（ deep cross-entropy）方法的算法更为成功。虽然该算法不如上述深度Q网络先进，但它具有很好的收敛性，而且对选择合适的超参数的敏感性要低得多。
下面来简单介绍一下如何应用交叉熵方法来寻找结构。
在交叉熵（deep cross-entropy）方法中，神经网络只学习预测给定状态下最佳的移动路径，而不学习状态或状态-动作下的值函数。给定任意一个状态作为神经网络的输入，然后输出该状态下所有可能移动的概率分布，概率最高的代表最佳路径。
用神经网络生成如下结构，首先要求它预测最好的第一个字符应该是什么，然后输出是字符表上的概率分布，从中随机抽取一个元素，并将其反馈到网络中，询问第二个字符的最佳值是多少。
每次迭代都会按照上述方法生成大量的随机sessions（构造）。计算每个奖励，然后扔掉除了y的最高值。接下来再让神经网络从剩下的sessions中学习，这意味着稍微调整一下神经网络的权重，使其更有可能输出在性能最好的sessions中使用的移动路径。这样做的目的是加强我们的神经网络，以执行那些导致良好奖励的行动。
猜想1：关于图的匹配值与最大特征值之和
猜想1：设G是n≥ 3个顶点的连通图，λ_1是最大特征值和µ是匹配数，那么它们满足不等式：
该猜想最初通过使用AutoGraphiX被证实，AutoGraphiX是一种可以用来自动查找各种图形参数之间关系的软件。后来被Stevanovi（n=600）推翻。在本文中，作者通过交叉熵方法找到了一个更小的显性反例，如下：
当n=19，奖励函数为λ_1 + µ时，每个迭代中前10% sessions的平均奖励变化情况：
值得注意的是，它对n≤ 18都是正确的，最小反例是n=19。
如图4所示，它有最大的特征值√ 10和匹配数2，所以λ_1 + µ ≈ 5.16 < 5.24 ≈ √（ 19− 1）+1。
图3显示了最佳sessions是如何随着迭代次数的增加而变化的。虽然有明显的 run-to-run的变化，但通常需要几个小时才能在平均PC上的程序找到反例。
很容易看出树状图是上述猜想最佳反例之一。事实上，给定一个具有最大匹配数M的图G，可以在不将图断开的情况下从E（G）M中重复删除边。这样做不会改变µ（G） 但是减小了最大特征值。有趣的是，如图3所示，网络迅速发现了树状图是最好的，然后它开始减小直径并收敛到图4中的图形。
猜想2：关于图的邻近特征值和距离特征值
猜想2：由于Auchiche–Hansen提出。设G是n≥4个顶点的连通图，直径为D，接近度为π，距离谱为∂1≥ . . . ≥ ∂n，那么它们满足不等式：
驳斥该猜想的策略与上述猜想完全相同，唯一的变化将是改变奖励函数。当n=30时训练神经网络可得到下图：
对于n=30，上图可能不是最优的：当我们中止算法时，最佳图仍然在变化。之所以选择终止学习过程，是因为在这个阶段，迭代前10%的每个图基本上都有相同的结构：一条长路径，中间有一个交点，其邻域被划分为不相交的区域，唯一不同的是这些区域的规模。
给定这些信息，可以简单地增加顶点的数量并改变这个构造中的区域大小，直到最终找到一个反例，如图6所示：
这个反例是在13个顶点上取一条路径，并将n个悬垂顶点附加到与其中相邻顶点来构造的。这幅图的直径为12，经计算机验证，只要n≥ 190，它满足π + ∂8<0。这种图被称为双尾彗星，已被证明在给定阶数和直径的树类上最小化接近度，它可以证明不一定总是正的。从有限的计算机实验来看，203个顶点上的图接近该猜想的最小反例，这似乎是合理的。
猜想3：关于树和邻接多项式峰值的距离
该猜想由Collins提出，非零系数的绝对值序列构成单峰序列，其峰值与CPD（T）的归一化系数的峰值位于同一位置。其中CPD（T）为树状图T的距离矩阵的特征多项式。
这里作者只关注峰值的位置，一旦知道了极值的近似情况，证明如下定理就可以有力地驳斥Collins的猜想。
该定理表明，即使假设两个序列有许多非零项，两个峰值也可能相距很远，这避免了m（T）在何时很小的问题。
第四个猜想
关于各种图矩阵的谱，主要考虑：图的哪些信息可以从这样一个矩阵谱中恢复？作者重点讨论了G的拉普拉斯（Laplacian）距离，用DL(G)表示。
这个问题由来已久，要了解关于这个问题的广泛研究概况，可参见L. Hogben 和 C. Reinhart发表的论文“Spectra of variants of distance matrices of graphs and digraphs: a survey”。在这项研究中，Hogben和Reinhart非常重视透射正则图的谱特性——事实上，如他们调查中的表7.2所示，自然图特性不知是否被DL共谱所保留。
本篇论文主要是通过显示DL余谱不保持传输规律来填补这一研究空白。
得到的结构并不是唯一的，有许多不同的方法可以设计一个奖励函数，与交叉熵方法一起使用产生如下一对共谱图。在之前的实验中，奖励函数的表现不是很好，最后在一次偶然运算中，算法发现了一个结构。这听起来是一种偶然，也很有可能其他算法更适合这个问题。
第五个猜想
猜想5：对于任何B⊂ {0，1}k和n∈ N与N≥ k， 都有：
一旦确定了集合B和整数n、k，找到相关的精确覆盖数就可以用一个整数程序来表达，其中包含{0，1}^n与超平面的所有可能交集的指示符变量。通过根据一些特殊的启发式方法对集合B进行采样并求解得到的线性程序，最终能够找到下面的反例来推测该猜想。
设n=6，k=4，B={1000，1111，1001，1011，0110，0001，0010，0111}。通过一个案例分析可以直接验证不能被两个超平面覆盖，因此
令人惊讶的是，它还可以用四个超平面覆盖
2
结论
本研究的主要贡献在于，作者通过强化学习方法成功地发现了组合数学问题中的显式结构和反例。这些反例全部使用了交叉熵方法，它的主要优点是算法简单，具有良好的收敛性，在不需要学习复杂的多步骤策略的简单环境中良好，这使它成为一个理想的基线方法。
虽然交叉熵方法在一般情况下工作得很好，但是存在大量更复杂的强化学习算法，这些算法可能在某些问题上表现得更好。在组合学，图论或其他数学领域，使用其他强化学习算法发现一些证伪猜想的反例，是一件很有趣的事。