[其他] AI攻克李雅普諾夫函數謎題

https://www.jiqizhixin.com/articles/2024-10-20-3 132年未解開的李雅普諾夫函數謎題，被Symbolic Transformer攻克了 牛頓沒解決的問題，AI給你解決了？ AI的推理能力一直是研究的焦點。作為最純粹、要求最高的推理形式之一，能否解決高階 的數學問題，無疑是衡量語言模型推理程度的一把尺。 雖然我們已經見證過來自GoogleDeepMind的Al以一分之差痛失IMO金牌，也從 陶哲軒頻頻 更新的動態中 得知，AI工具已經在幫助數學家解決像「紐結理論」和「 海狸難題 」這 樣困擾數學家幾個世紀的難題。 但是這些成果大多需要數學家作大量的前期工作，對於沒有已知通用解法的開放性問題， AI也是一個小白。 最近的一項研究打破了這個局面。 Meta和巴黎理工學院的研究人員共同探討了一個困擾 數學界長達132年的問題：李雅普諾夫函數。簡單來說，李雅普諾夫函數用來判斷一個動 力系統相對於其平衡點或軌道，隨著時間無限延長後是否能保持全局穩定。 論文已經入 選了NeurIPS 2024。 論文標題：全局李亞普諾夫函數：數學中長期存在的開放問題，具有符號變換器 論文網址：https://arxiv.org/pdf/2410.08304 這類問題中，最出名的可能就是三體問題了：兩個物體在沒有其他引力的影響下相互繞行 ，如果再添加一個物體，在大多數情況下，這三個物體的運動都會變得混亂起來。 三體問題與李雅普諾夫函數 三體問題是經典力學中最著名的未解問題之一。牛頓提出了萬有引力定律，並通過微積分 為兩個物體之間的引力相互作用提供了精確的解。然而，當系統中增加第三個物體時，系 統的覆雜性顯著增加，傳統方法無法應對。 18世紀，拉格朗日做出了突破性的貢獻：拉格朗日點。三體系統將在拉格朗日點達到平衡 。然而，他的發現仍無法解決三體系統在長時間尺度下的整體穩定性問題。 到了19世紀末，龐加萊透過發展拓樸學和混沌理論，證明了某些條件下，三體系統會出現 不可預測的混沌行為。這顯示三體問題的複雜程度遠超人們的想像，也意味著不存在普適 的解。 1892年，李雅普諾夫又將這個世紀難題向前邁進了一步。判斷三體系統是否穩定，可以藉 助李雅普諾夫函數。 李雅普諾夫函數V(x)需要滿足以下條件才能確保系統的穩定性： 1.穩定平衡點 https://reurl.cc/34nmN0 2.全域漸近穩定平衡點 https://reurl.cc/NlMDr6 不過，李雅普諾夫只提供了理論上的證明，想要實際計算出一個系統的函數解極為困難。 雖然像SOSTOOLS 這樣的運算工具可以輔助，但它們的能力僅限於處理小型的多項式系統 ，對於更複雜的情況往往無能為力。 在這項工作中，研究者訓練序列到序列Transformer 來預測給定係統的Lyapunov 函數。 他們將這個問題定義為一個翻譯任務：問題和解決方案以符號Token序列的形式表示，模 型從生成的系統和Lyapunov 函數對中訓練，以最小化預測序列和正確解決方案之間的交 叉熵。研究者使用學習率為10^-4 的Adam 優化器，在16 個樣本的批上訓練具有8 層、 10 個注意力頭和640 嵌入維度的Transformer，初始線性熱身階段為10000 個優化步驟， 並進行反平方根調度。所有實驗都在8 個V100 GPU 和32 GB 記憶體上運行，每個GPU 的 訓練時間為12 到15 小時。 數據生成 本文模型是在成對穩定係統和相關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。 https://reurl.cc/oyMXxD 檢驗在生成資料上訓練模型的試金石是它們在分佈外（OOD）的泛化能力。表3 展示了後 向模型在前向生成集上的評估結果。在使用平方和Lyapunov 函數（FLyap）對前向產生的 隨機多項式系統進行測試時，所有後向模型都達到了很高的準確率（73% 到75%）。非多 項式系統（BNonPoly）是最多樣化的訓練集，其性能也最好。在前向產生的具有障礙函數 （FBarr）的系統集上，後向模型的精度較低，這可能是由於許多障礙函數並不一定是 Lyapunov 函數。在這些測試集上，後向模型必須應對不同的分佈和（略微）不同的任務 。另一方面，前向模型在後向測試集上的表現較低。這可能是由於這些訓練集的規模較小 。 https://reurl.cc/MjQDk4 總的來說，這些結果似乎證實了後向訓練模型並沒有學會反轉其生成過程。如果是這樣的 話，它們在前向測試集上的表現就會接近零。 豐富訓練分佈以提高性能 為了提高後向模型的 OOD 性能，研究者在其訓練集中加入了極少量的前向生成的樣本， 帶來了性能的顯著提高，如表4所示。將 FBarr 中的 300 個樣本添加到 BPoly 中， FBarr 的準確率從 35% 提高到 89%（盡管訓練集中前向樣本的比例僅為 0.03%），而 FLyap 的 OOD 準確率提高了 10 個百分點以上。增加 FLyap 中的樣本帶來的改進較小。 這些結果表明，通過在訓練集中添加少量（幾十個或幾百個）我們知道如何求解的樣本， 可以大大提高根據後向生成數據訓練的模型的 OOD 性能。在這里，額外的樣本解決了一 個較弱但相關的問題：發現障礙函數。由於提高性能所需的樣本數量很少，因此這種技術 特別具有成本效益。 與baseline的對比 https://reurl.cc/jyEpkM 如表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 解算器。 https://reurl.cc/7d8le5 專家迭代 鑑於表6 中模型的效能，可以利用新解決的問題來進一步微調模型。具體來說，研究者創 建了一個針對多項式系統的經過驗證的模型預測樣本FIntoTheWild，並將其添加到原始訓 練樣本中，然後繼續訓練模型。他們也測試了對模型進行微調的不同策略，並在表7 中總 結了正向基準和「wild」的表現。 在100 萬個訓練集的基礎上增加1000 個經過驗證的預測後，「to into wild」測試集的 效能提高了約15%，而其他測試集（n4）的表現則沒有受到影響。增加更多樣本似乎是有 害的，因為這會降低在其他基準（n5 和n6）上的效能。研究者也注意到，使用其他分佈 的混合數據進行微調並不高效（結果n1 和n2），而使用少量數據已經有助於獲得一些改 進（結果n3）。最後，使用來自FIntoTheWild 的資料從頭開始預訓練模型並不高效（結 果n7）。 更多研究細節，可參考原論文。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.253.176.75 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1729488650.A.AA6.html