论文标题:Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers 论文地址:https://arxiv.org/pdf/2410.08304
三体问题与李雅普诺夫函数
数据生成
本文模型是在成对稳定系统和相关 Lyapunov 函数的大型数据集上进行训练和测试的。对此类稳定系统进行采样会遇到两个难题:首先,大多数动态系统都是不稳定的,没有通用的方法来判断一个系统是否稳定;其次,一旦对稳定系统进行采样,除了特殊情况外,没有找到 Lyapunov 函数的通用技术。
对于一般情况,研究者这里采用了后向生成法 ,即采样求解并生成相关问题;而对于小程度的可控多项式系统,研究者采用前向生成法,即采样系统并用求解器计算其解。
研究者生成了 2 个后向数据集和 2 个前向数据集用于训练和评估,并生成了一个较小的前向数据集用于评估。
后向数据集 BPoly 包含 100 万个非退化多项式系统 S,其系数为整数,等式数为 2 到 5(比例相同)。研究者还创建了 BNonPoly,一个包含 100 万个非退化非多项式系统、2 至 5 个等式的数据集。在这个数据集中,f 的坐标是通用函数的多项式,对于这类系统,目前还没有发现 Lyapunov 函数的方法。
两个前向数据集都是使用 Python 的 SumOfSquares 软件包中的求解器生成的,并采用了与 SOSTOOLS 类似的技术。这些数据集中的所有系统都是具有 2 到 3 个方程的非零整数多项式和整数多项式 Lyapunov 函数,这些方法只能求解这些系统。FLyap是一个包含 10 万个系统的数据集,这些系统的 Lyapunov 函数都是非同次多项式;FBarr 是一个有 30 万个以非均质多项式作为障碍函数的系统。这些数据集规模较小的原因在于 SOS 方法的计算成本以及发现 Lyapunov 或障碍函数的难度。
为了与发现多项式系统 Lyapunov 函数的最先进方法 SOSTOOL 进行比较,研究者还生成了一个测试集,其中包含 SOSTOOLS 可以求解的 1500 个具有整数系数的多项式系统(FSOSTOOLS)。
结果
研究者在不同数据集上训练的模型,在held-out测试集上达到了近乎完美的准确性,且在分布外测试集上则有非常高的性能,尤其是在用少量前向样本丰富训练集时。这些模型的性能大大优于此前最先进的技术,而且还能发现新系统的 Lyapunov 函数。
分布内/分布外准确率
表2展示了 4 个数据集上训练的模型性能。在它们所训练的数据集的保留测试集上进行测试时,所有模型都达到了很高的域内准确率。在前向数据集上,障碍函数的预测准确率超过 90%,Lyapunov 函数的预测准确率超过 80%。在后向数据集上,基于 BPoly 训练的模型的准确率接近 100%。可以注意到,集束搜索,即允许对解法进行多次猜测,能显著提高性能(对于性能较低的模型,束大小为 50 时,性能提高 7% 至 10%)。研究者在所有进一步的实验中都使用了束大小 50。
检验在生成数据上训练模型的试金石是它们在分布外(OOD)的泛化能力。表 3 展示了后向模型在前向生成集上的评估结果。在使用平方和 Lyapunov 函数(FLyap)对前向生成的随机多项式系统进行测试时,所有后向模型都达到了很高的准确率(73% 到 75%)。非多项式系统(BNonPoly)是最多样化的训练集,其性能也最好。在前向生成的具有障碍函数(FBarr)的系统集上,后向模型的精度较低,这可能是由于许多障碍函数并不一定是 Lyapunov 函数。在这些测试集上,后向模型必须应对不同的分布和(略微)不同的任务。另一方面,前向模型在后向测试集上的性能较低。这可能是由于这些训练集的规模较小。
总的来说,这些结果似乎证实了后向训练模型并没有学会反转其生成过程。如果是这样的话,它们在前向测试集上的表现就会接近于零。
丰富训练分布以提高性能
为了提高后向模型的 OOD 性能,研究者在其训练集中加入了极少量的前向生成的样本,带来了性能的显著提高,如表4所示。将 FBarr 中的 300 个样本添加到 BPoly 中,FBarr 的准确率从 35% 提高到 89%(尽管训练集中前向样本的比例仅为 0.03%),而 FLyap 的 OOD 准确率提高了 10 个百分点以上。增加 FLyap 中的样本带来的改进较小。这些结果表明,通过在训练集中添加少量(几十个或几百个)我们知道如何求解的样本,可以大大提高根据后向生成数据训练的模型的 OOD 性能。在这里,额外的样本解决了一个较弱但相关的问题:发现障碍函数。由于提高性能所需的样本数量很少,因此这种技术特别具有成本效益。
与baseline的对比
如表 5所示,在 FSOSTOOLS 上,一个以 BPoly 为基础并辅以 500 个 FBarr 系统训练的模型(PolyMixture)达到了 84%的准确率,证实了混合模型的高 OOD 准确率。在所有生成的测试集上,PolyMixture 的准确率都超过了 84%,而 findlyap 在后向生成的测试集上的准确率仅为 15%。这表明,在多项式系统上,与以前的技术水平相比,通过后向生成数据训练的Transformer取得了非常出色的结果。
平均而言,基于Transformer的模型也比 SOS 方法快得多。当尝试求解一个包含 2 至 5 个方程的随机多项式系统时,findlyap 平均需要 935.2 秒(超时 2400 秒)。对于本文模型,使用greedy decoding时,推理和验证一个系统平均需要 2.6 秒,使用束大小为 50 时需要 13.9 秒。
发现新数学
表 6 列出了本文模型发现的正确解的百分比。在多项式数据集上,最佳模型(PolyM)分别在 11.8%和 10.1%的(degree 3和degree 5)系统中发现了 Lyapunov 函数,是 findlyap 的 10 倍。对于非多项式系统,有 12.7% 的样本发现了 Lyapunov 函数。这些结果表明,从生成的系统数据集和 Lyapunov 函数中训练出来的语言模型确实可以发现未知的 Lyapunov 函数,其性能远远高于最先进的 SOS 求解器。
专家迭代
鉴于表 6 中模型的性能,可以利用新解决的问题来进一步微调模型。具体来说,研究者创建了一个针对多项式系统的经过验证的模型预测样本 FIntoTheWild,并将其添加到原始训练样本中,然后继续训练模型。他们还测试了对模型进行微调的不同策略,并在表 7 中总结了正向基准和「wild」的性能。
在 100 万个训练集的基础上增加 1000 个经过验证的预测后,「to into wild」测试集的性能提高了约 15%,而其他测试集(n4)的性能则没有受到影响。增加更多样本似乎是有害的,因为这会降低在其他基准(n5 和 n6)上的性能。研究者还注意到,使用来自其他分布的混合数据进行微调并不高效(结果 n1 和 n2),而使用少量数据已经有助于获得一些改进(结果 n3)。最后,使用来自 FIntoTheWild 的数据从头开始预训练模型并不高效(结果 n7)。
更多研究细节,可参考原论文。