三體問題，竟被Transformer解決了？

發(fā)現(xiàn)全局李雅普諾夫函數(shù)，已經(jīng)困擾了數(shù)學(xué)家們132年。

作為分析系統(tǒng)隨時間穩(wěn)定性的關(guān)鍵工具，李雅普諾夫函數(shù)有助于預(yù)測動態(tài)系統(tǒng)行為，比如著名的天體力學(xué)三體問題。

它是天體力學(xué)中的基本力學(xué)模型，指三個質(zhì)量、初始位置和初始速度都是任意的可視為質(zhì)點(diǎn)的天體，在相互之間萬有引力作用下的運(yùn)動規(guī)律問題。

現(xiàn)在已知，三體問題不能精確求解，無法預(yù)測所有三體問題的數(shù)學(xué)情景。（「三體人」的困境，就是三體問題的一個極端案例。）

現(xiàn)在，Meta AI解決了這個問題。目前，論文已被NeurIPS 2024接收。

論文地址：https://arxiv.org/abs/2410.08304

今天，論文發(fā)布十幾天后，AI社區(qū)再度被它刷屏。

就在前一陣，蘋果的一項研究引起廣泛熱議：LLM不具備推理能力，可能只是復(fù)雜的模式匹配器而已。

有趣的是，這篇論文在結(jié)尾呼應(yīng)了這個問題，做了極其精彩的論述——

從邏輯和推理的角度來看，有人認(rèn)為規(guī)劃和高層次的推理可能是自回歸Transformer架構(gòu)的固有限制。然而，我們的研究結(jié)果表明，Transformer確實(shí)可以通過精心選擇訓(xùn)練樣本，而非更改架構(gòu)，來學(xué)會解決一個人類通過推理解決的復(fù)雜符號數(shù)學(xué)問題。我們并不認(rèn)為Transformer是在進(jìn)行推理，而是它可能通過一種「超級直覺」來解決問題，這種直覺源自對數(shù)學(xué)問題的深刻理解。

雖然這個系統(tǒng)化的方法仍是一個黑箱，無法闡明Transformer的「思維過程」，但解決方案明確，且數(shù)學(xué)正確性可以得到驗證。

Meta研究者表示：生成式AI模型可以用于解決數(shù)學(xué)中的研究級問題，為數(shù)學(xué)家提供可能解的猜測。他們相信，這項研究是一個「AI解決數(shù)學(xué)開放問題」的藍(lán)圖。

無論如何，陶哲軒和今天的這項研究都已證明，無論LLM究竟會不會推理，它都已經(jīng)徹底改變數(shù)學(xué)這類基礎(chǔ)科學(xué)的研究范式。

那些在歷史長河中的未解數(shù)學(xué)之謎，破解答案的一天或許已經(jīng)離我們無比接近。

Transformer解決132年前數(shù)學(xué)難題

全局李亞普諾夫函數(shù)，控制著動力系統(tǒng)的穩(wěn)定性。它會衡量一個開始接近平衡的系統(tǒng)，是否會始終保持接近平衡（或偏離平衡）？

其中最著名的案例，就是「三體問題」了。

軌跡可能很復(fù)雜，但只要從紅球開始，它們最終都會留在藍(lán)球的位置

1892年，李亞普諾夫證明，如果可以找到一個函數(shù)V，在平衡時具有嚴(yán)格的最小值，在無窮大時具有無限大，并且梯度始終指向遠(yuǎn)離系統(tǒng)梯度的方向，那么全局穩(wěn)定性就能得到保證。

遺憾的是，他未能提供尋找函數(shù)V的方法。

好在，一百多年后，大模型出現(xiàn)了。

以前，不存在尋找李亞普諾夫函數(shù)的通用方法，現(xiàn)在LLM是否能解決？

研究者們驚喜地發(fā)現(xiàn)，自己的模型發(fā)現(xiàn)了兩個穩(wěn)定系統(tǒng)，以及相關(guān)的李雅普諾夫函數(shù)。

為此，Meta AI研究者引入一種后向生成技術(shù)來訓(xùn)練模型。這項技術(shù)根據(jù)Lyapunov函數(shù)創(chuàng)建動力系統(tǒng)，而這些系統(tǒng)的分布與我們實(shí)際想要解決的問題不同。

盡管模型必須在分布外進(jìn)行泛化，但使用逆向生成數(shù)據(jù)訓(xùn)練的模型，在可以用數(shù)值工具求解的多項式系統(tǒng)測試集上仍能取得良好的性能。

通過向后向訓(xùn)練集中添加少量（0.03%）簡單且可解決的“前向”示例，性能就得到極大提高。這種「啟動模型」大大優(yōu)于最先進(jìn)的方法。

在穩(wěn)定性未知的一組隨機(jī)動力系統(tǒng)上，研究者測試了自己的模型，發(fā)現(xiàn)在10%到13%的情況下，都能找到新的新的李亞普諾夫函數(shù)。

在這項任務(wù)上，這些增強(qiáng)的模型在各種基準(zhǔn)測試中大大超越了最先進(jìn)的技術(shù)和人類表現(xiàn)。

它們的準(zhǔn)確率超過80%，但碩士生級別的人類數(shù)學(xué)家在這項任務(wù)上的準(zhǔn)確率不到10%。

最后，研究者測試了模型在隨機(jī)生成系統(tǒng)中發(fā)現(xiàn)未知李雅普諾夫函數(shù)的能力。

在多項式系統(tǒng)中（當(dāng)前方法唯一能解決的系統(tǒng)），模型為10.1%的系統(tǒng)找到了李雅普諾夫函數(shù)，而最先進(jìn)的技術(shù)僅為2.1%。

在非多項式系統(tǒng)中（當(dāng)前沒有已知算法），最佳模型為12.7%的系統(tǒng)發(fā)現(xiàn)了新的李雅普諾夫函數(shù)。

系統(tǒng)穩(wěn)定性與李雅普諾夫函數(shù)

發(fā)現(xiàn)控制動力系統(tǒng)全局穩(wěn)定性的李雅普諾夫函數(shù)，是一個長期存在但易于形式化的數(shù)學(xué)開放問題。

這個函數(shù)代表著當(dāng)時間趨于無窮時，其解相對于平衡點(diǎn)或軌道的有界性。

動力系統(tǒng)的穩(wěn)定性是一個復(fù)雜的數(shù)學(xué)問題，吸引了許多代數(shù)學(xué)家的興趣，從18世紀(jì)的牛頓和拉格朗日，到20世紀(jì)研究三體問題的龐加萊。

評估穩(wěn)定性的主要數(shù)學(xué)工具是由李雅普諾夫提出的，他在1892年證明，如果可以找到一個遞減的類似熵的函數(shù)——李雅普諾夫函數(shù)，那么系統(tǒng)就是穩(wěn)定的。

系統(tǒng)穩(wěn)定性

全局漸進(jìn)穩(wěn)定性

后來，李雅普諾夫函數(shù)的存在被證明是大系統(tǒng)穩(wěn)定性的必要條件。

不幸的是，目前尚無已知方法可以在一般情況下推導(dǎo)出李雅普諾夫函數(shù)，已知的李雅普諾夫函數(shù)僅適用于少數(shù)系統(tǒng)。

事實(shí)上，130年后，系統(tǒng)推導(dǎo)全局李雅普諾夫函數(shù)的方法僅在少數(shù)特殊情況下已知，而在一般情況下的推導(dǎo)仍然是一個著名的開放問題。

為此，研究者提出了一種從隨機(jī)采樣的李雅普諾夫函數(shù)中生成訓(xùn)練數(shù)據(jù)的新技術(shù)。

在這些數(shù)據(jù)集上訓(xùn)練的大語言模型中的序列到序列Transformer，在保留測試集上實(shí)現(xiàn)了接近完美的準(zhǔn)確率（99%），并在分布外測試集上表現(xiàn)出很高的性能（73%）。

實(shí)驗設(shè)置

在這項工作中，研究者訓(xùn)練了序列到序列的Transformer，來預(yù)測給定系統(tǒng)的李雅普諾夫函數(shù)（如果存在）。

他們將問題框定為翻譯任務(wù)：問題和解決方案被表示為符號token的序列，模型從生成的系統(tǒng)和李雅普諾夫函數(shù)對中進(jìn)行訓(xùn)練，以最小化預(yù)測序列與正確解決方案之間的交叉熵。

為此，研究者訓(xùn)練了具有8層、10個注意力頭和嵌入維度為640的Transformer，批大小為16個樣本，使用Adam優(yōu)化器，學(xué)習(xí)率為10^?4，初始線性預(yù)熱階段為10,000次優(yōu)化步驟，并使用反平方根調(diào)度。

所有實(shí)驗在8個32GB內(nèi)存的V100 GPU上運(yùn)行，每個epoch處理240萬樣本，共進(jìn)行3到4個epoch。每個GPU的訓(xùn)練時間在12到15小時之間。

數(shù)據(jù)生成

研究者將模型在大型數(shù)據(jù)集上進(jìn)行訓(xùn)練和測試，這些數(shù)據(jù)集由穩(wěn)定系統(tǒng)及其相關(guān)的李雅普諾夫函數(shù)對組成。

采樣此類穩(wěn)定系統(tǒng)有兩個難點(diǎn)。

首先，大多數(shù)動力系統(tǒng)是不穩(wěn)定的，并且沒有通用的方法可以決定一個系統(tǒng)是否穩(wěn)定。

其次，一旦采樣到一個穩(wěn)定系統(tǒng)，除了特定情況下，沒有通用的技術(shù)可以找到李雅普諾夫函數(shù)。

在本文中，研究者依賴于反向生成，通過采樣解決方案并生成相關(guān)問題來處理一般情況，以及正向生成，通過采樣系統(tǒng)并使用求解器計算其解決方案，來處理小度數(shù)的可處理多項式系統(tǒng)。

反向生成

反向生成方法，從解決方案中采樣問題，只有在模型能夠避免學(xué)習(xí)逆轉(zhuǎn)生成過程或“讀取”生成問題中的解決方案時才有用。

例如，當(dāng)訓(xùn)練模型解決求整數(shù)多項式根的難題時，人們可以輕松從其根（3、5、7）生成多項式：

然而，如果模型是從P(X)的因式分解形式進(jìn)行訓(xùn)練的，它將學(xué)會讀取問題的根，而非計算它們。

另一方面，簡化形式

也并未提供任何線索。

反向生成的第二個困難是，對解決方案而非問題進(jìn)行采樣，會使訓(xùn)練分布產(chǎn)生偏差。

為此，研究者提出了一種從隨機(jī)李雅普諾夫函數(shù)V生成穩(wěn)定系統(tǒng)S的過程。

經(jīng)過以上六步，產(chǎn)生了一個穩(wěn)定系統(tǒng)S：?=f(x)，其中V作為其Lyapunov函數(shù)。

正向生成

盡管在一般情況下穩(wěn)定性問題尚未解決，但當(dāng)多項式系統(tǒng)的李雅普諾夫函數(shù)存在并可以寫成多項式的平方和時，已有方法可以計算這些函數(shù)。

這些多項式復(fù)雜度的算法對于小型系統(tǒng)非常高效，但隨著系統(tǒng)規(guī)模的增長，其CPU和內(nèi)存需求會急劇增加。

研究者利用這項算法，來生成前向數(shù)據(jù)集。

這種方法也有幾個局限性，限制了該方法可以解決的多項式系統(tǒng)的類別。

數(shù)據(jù)集

研究者生成了兩個用于訓(xùn)練和評估目的的反向數(shù)據(jù)集和兩個正向數(shù)據(jù)集，以及一個較小的正向數(shù)據(jù)集用于評估目的。

結(jié)果

研究者在不同數(shù)據(jù)集上訓(xùn)練的模型，在保留測試集上取得了接近完美的準(zhǔn)確率，并且在分布外測試集上表現(xiàn)非常出色，特別是在用少量正向示例增強(qiáng)訓(xùn)練集時。

它們大大超越了當(dāng)前最先進(jìn)的技術(shù)，并且還能發(fā)現(xiàn)新系統(tǒng)的李雅普諾夫函數(shù)。以下是這些結(jié)果的詳細(xì)信息。

分布內(nèi)和分布外的準(zhǔn)確率

在本節(jié)中，研究者展示了在4個數(shù)據(jù)集上訓(xùn)練的模型的性能。

所有模型在域內(nèi)測試中都取得了高準(zhǔn)確率，即在它們訓(xùn)練所用數(shù)據(jù)集的留出測試集上進(jìn)行測試時。

在正向數(shù)據(jù)集上，障礙函數(shù)預(yù)測的準(zhǔn)確率超過90%，李雅普諾夫函數(shù)的準(zhǔn)確率超過80%。

在反向數(shù)據(jù)集上，訓(xùn)練于BPoly的數(shù)據(jù)集的模型幾乎達(dá)到了100%的準(zhǔn)確率。

研究者注意到，束搜索，即允許對解進(jìn)行多次猜測，顯著提高了性能（對于表現(xiàn)較差的模型，束大小為50時提升了7到10%）。

在所有后續(xù)實(shí)驗中，研究者都使用了50的束大小。

對生成數(shù)據(jù)訓(xùn)練的模型的試金石，是其分布外（OOD）泛化能力。

所有反向模型在測試正向生成的隨機(jī)多項式系統(tǒng)（具有平方和李雅普諾夫函數(shù)）時，都取得了高準(zhǔn)確率（73%到75%）。

最佳性能由非多項式系統(tǒng)（BNonPoly）實(shí)現(xiàn)，這是最多樣化的訓(xùn)練集。

反向模型在具有障礙函數(shù)的正向生成系統(tǒng)集（FBarr）上的較低準(zhǔn)確率，可能是因為許多障礙函數(shù)不一定是李雅普諾夫函數(shù)。在這些測試集上，反向模型必須應(yīng)對不同的分布和略有不同的任務(wù)。

另一方面，正向模型在反向測試集上的表現(xiàn)較差。這可能是由于這些訓(xùn)練集的規(guī)模較小。

總體而言，這些結(jié)果似乎證實(shí)了反向訓(xùn)練的模型并未學(xué)習(xí)反轉(zhuǎn)其生成過程。如果是這樣，它們在正向測試集上的表現(xiàn)將接近于零。它們還顯示了良好的OOD準(zhǔn)確率。

通過豐富訓(xùn)練分布來提高性能

為了提高反向模型的OOD性能，研究者在其訓(xùn)練集中加入了一小部分正向生成的示例。

值得注意的是，這帶來了顯著的性能提升。

將300個來自FBarr的示例添加到BPoly中后，F(xiàn)Barr的準(zhǔn)確率從35%提高到89%（盡管訓(xùn)練集中正向示例的比例僅為0.03%），并使FLyap的OOD準(zhǔn)確率提高了10多個百分點(diǎn)。從FLyap添加示例帶來的改進(jìn)較小。

這些結(jié)果表明，在反向生成數(shù)據(jù)上訓(xùn)練的模型的OOD性能，可以通過在訓(xùn)練集中加入少量我們知道如何解決的示例（幾十或幾百個）來大大提高。

在這里，額外的示例解決了一個較弱但相關(guān)的問題：發(fā)現(xiàn)障礙函數(shù)。因為所需示例數(shù)量很少，因而這種技術(shù)特別具有成本效益。

與當(dāng)前最先進(jìn)的基線比較

為了給模型提供基線，研究者開發(fā)了findlyap，這是MATLAB的SOSTOOLS中的李雅普諾夫函數(shù)查找器的Python對應(yīng)版本。

他們還引入了FSOSTOOLS，這是一個包含1500個整數(shù)系數(shù)多項式系統(tǒng)的測試集，具有SOSTOOLS可以求解的整數(shù)系數(shù)。

研究者還測試了基于AI的工具，例如Fossil 2、ANLC v2和LyzNet。

這些方法在測試集上取得了較低的準(zhǔn)確率。這可能是因為這些工具旨在解決不同的問題：發(fā)現(xiàn)局部或半全局李雅普諾夫函數(shù)（并可能尋找控制函數(shù)），而研究者的目標(biāo)是全局李雅普諾夫函數(shù)。

表5比較了findlyap和基于AI的工具以及研究者模型在所有可用測試集上的表現(xiàn)。

一個在BPoly上訓(xùn)練并補(bǔ)充了500個來自FBarr的系統(tǒng)的模型（PolyMixture）在FSOSTOOLS上達(dá)到了84%的準(zhǔn)確率，證實(shí)了混合模型的高OOD準(zhǔn)確率。

在所有生成的測試集上，PolyMixture的準(zhǔn)確率都超過了84%，而findlyap在反向生成的測試集上僅達(dá)到了15%。

這表明，在多項式系統(tǒng)上，從反向生成數(shù)據(jù)訓(xùn)練的Transformer模型，相比于之前的最先進(jìn)技術(shù)取得了非常強(qiáng)的結(jié)果。

平均而言，基于Transformer的模型也比SOS方法快得多。

當(dāng)嘗試解決一個包含2到5個方程的隨機(jī)多項式系統(tǒng)時，findlyap平均需要935.2秒（超時為2400秒）。

對于研究者的模型，使用貪婪解碼進(jìn)行一個系統(tǒng)的推理和驗證平均需要2.6秒，使用束大小為50時需要13.9秒。

探索未知領(lǐng)域：發(fā)現(xiàn)新的數(shù)學(xué)

這次研究的最終目標(biāo)，就是發(fā)現(xiàn)新的李雅普諾夫函數(shù)。

為了測試模型發(fā)現(xiàn)新的李雅普諾夫函數(shù)的能力，研究者生成了三個隨機(jī)系統(tǒng)的數(shù)據(jù)集：

- 包含2或3個方程的多項式系統(tǒng)（Poly3）

- 包含2到5個方程的多項式系統(tǒng)（Poly5）

- 包含2或3個方程的非多項式系統(tǒng)（NonPoly）

對于每個數(shù)據(jù)集，生成100,000個隨機(jī)系統(tǒng)，并消除那些在x^? = 0處局部指數(shù)不穩(wěn)定的系統(tǒng)，因為系統(tǒng)的雅可比矩陣具有實(shí)部嚴(yán)格為正的特征值。

然后，將findlyap和基于AI的方法與兩個在多項式系統(tǒng)上訓(xùn)練的模型進(jìn)行比較：FBarr和PolyM（ixture）——BPoly與來自FBarr的300個示例的混合——以及一個在BPoly、BNonPoly和來自FBarr的300個示例的混合上訓(xùn)練的模型（NonPolyM）。

在多項式數(shù)據(jù)集上，最佳模型（PolyM）為11.8%和10.1%的（3階和5階）系統(tǒng)發(fā)現(xiàn)了李雅普諾夫函數(shù)，比findlyap多出十倍。對于非多項式系統(tǒng)，李雅普諾夫函數(shù)在12.7%的示例中被找到。

這些結(jié)果表明，從生成的數(shù)據(jù)集和李雅普諾夫函數(shù)訓(xùn)練的大語言模型確實(shí)能夠發(fā)現(xiàn)尚未知的李雅普諾夫函數(shù)，并且表現(xiàn)遠(yuǎn)高于當(dāng)前最先進(jìn)的SOS求解器。

模型找到正確解決方案的百分比

專家迭代

接下來，研究者為多項式系統(tǒng)創(chuàng)建了一個經(jīng)過驗證的模型預(yù)測樣本，F(xiàn)IntoTheWild，將其添加到原始訓(xùn)練樣本中，并繼續(xù)訓(xùn)練模型。

n1：添加20,600個樣本，分別來自BPoly（20,000）、FBarr（50）、FLyap（50）和FIntoTheWild（500）

n2：添加2,000個樣本，分別來自FLyap（1,000）和FIntoTheWild（1,000）

n3：添加50個來自FIntoTheWild的樣本

n4：添加1,000個來自FIntoTheWild的樣本

n5：添加2,000個來自FIntoTheWild的樣本

n6：添加5,000個來自FIntoTheWild的樣本

此外，研究者還從頭開始重新訓(xùn)練一個模型（n7），使用BPoly（1M）、FBarr（500）、FLyap（500）和FIntoTheWild（2,000）的混合。

不同微調(diào)策略下，模型在前向基準(zhǔn)和「探索未知領(lǐng)域」中的表現(xiàn)

可以看到，向100萬訓(xùn)練集添加1,000個經(jīng)過驗證的預(yù)測可將「探索未知領(lǐng)域」測試集的性能提高約15%，同時不會影響其他測試集（n4）。

而添加更多樣本似乎是有害的，因為它降低了其他基準(zhǔn)的性能（n5和n6）。

此外，使用來自其他分布的混合數(shù)據(jù)進(jìn)行微調(diào)效率不高（n1和n2），而少量貢獻(xiàn)已經(jīng)有助于取得一些改進(jìn)（n3）。

最后，從頭開始使用FIntoTheWild的數(shù)據(jù)預(yù)訓(xùn)練模型效率不高（n7）。

Transformer不會推理，但有「超級直覺」

這項研究已經(jīng)證明，模型可以通過生成的數(shù)據(jù)集進(jìn)行訓(xùn)練，以解決發(fā)現(xiàn)穩(wěn)定動力系統(tǒng)的李雅普諾夫函數(shù)。

對于隨機(jī)多項式系統(tǒng)，研究者的最佳模型可以在五倍于現(xiàn)有最先進(jìn)方法的情況下，發(fā)現(xiàn)李雅普諾夫函數(shù)。

它們還可以發(fā)現(xiàn)非多項式系統(tǒng)的李雅普諾夫函數(shù)（目前尚無已知算法），并且能夠重新發(fā)現(xiàn)由Ahmadi等人發(fā)現(xiàn)的多項式系統(tǒng)的非多項式李雅普諾夫函數(shù)。

研究者也承認(rèn)，工作仍有一些局限性。

由于沒有已知的方法來判斷隨機(jī)系統(tǒng)是否穩(wěn)定，他們?nèi)狈Ψ嵌囗検较到y(tǒng)的良好基準(zhǔn)。

此外，本文研究的所有系統(tǒng)都相對較小，多項式系統(tǒng)最多為5個方程，非多項式最多為3個方程。

他們相信，擴(kuò)展到更大的模型應(yīng)該有助于處理更大、更復(fù)雜的系統(tǒng)。

最后，這項工作可以擴(kuò)展到考慮非多項式系統(tǒng)的定義域。

總之，這項工作在兩個方向上具有更廣泛的影響：Transformer的推理能力，以及AI在科學(xué)發(fā)現(xiàn)中的潛在作用。