30多年的數(shù)學猜想，被AI發(fā)現(xiàn)了一個反例？

就在剛剛，Meta、威斯康星大學麥迪遜分校、伍斯特理工學院、悉尼大學的幾位學者提出PatternBoost，這種全新的方法可以在一些數(shù)學問題中尋找有趣的結構。

圖片

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

其核心思想是交替進行「局部搜索」和「全局搜索」。

在第一個「局部」階段，使用傳統(tǒng)的經(jīng)典搜索算法來生成許多理想的構造。

在第二個「全局」階段，使用Transformer神經(jīng)網(wǎng)絡對這些最優(yōu)構造進行訓練。然后，將訓練好的Transformer樣本用作第一個階段的種子，并重復該過程。

前者類似于貪心算法，比如給定一個圖形，去除包含多個4-圈的邊，直到?jīng)]有4-圈為止。

而后者的一個例子，是讓Transformer生成更多類似于上次篩選中表現(xiàn)前1%的圖。

這種迭代交替，比傳統(tǒng)的貪婪方法或者單獨的非貪婪增強Transformer方法要好得多。

結合Transformers來求解離散優(yōu)化問題的步驟

比起某些問題，它會更擅長解決另一些問題。因此，這篇論文在許多不同的數(shù)學領域測試了相同的協(xié)議。

哪些數(shù)學問題最適用于機器學習技術？或者說，最終我們將證明，所有數(shù)學問題都適合機器學習技術？

這個可能性，實在太令人興奮了。

PatternBoost不僅找到了幾個長期問題的最佳已知解決方案，而且還構造了一個反例，反駁了一個已懸而未決30年的猜想。

比如可以生成網(wǎng)絡拓撲中較為常見的C4-free稠密圖，也就是一幅不存在由4個頂點組成的閉合路徑的稠密圖。

PatternBoost在多個極值組合學問題中表現(xiàn)優(yōu)異，其中一個經(jīng)典應用是，就是無4-圈問題。

圖片

即在給定頂點數(shù)n的情況下，構造盡可能多的邊而不包含4-圈的圖。

此類問題對機器學習方法具有挑戰(zhàn)性，因為其數(shù)學結構較為復雜且解的空間巨大。

研究者是通過以下步驟應用PatternBoost的：首先生成一個初始數(shù)據(jù)集，并使用Transformer模型對其進行訓練以生成新樣本。

將這些新樣本作為局部搜索的起點，經(jīng)過多輪迭代后，PatternBoost在這個無4-圈問題上獲得了比傳統(tǒng)方法更佳的解。

圖片

「許多邊沒有三角形」問題

問題引入

現(xiàn)在讓我們來設想這樣一個問題：在一個n個頂點的圖中，如果沒有任何三個邊形成三角形，那么它最多可以有多少條邊？

第一步，我們可以提出一些有許多邊，且沒有三角形的少量頂點上的圖。

圖片

然后，我們會很幸運地注意到，許多示例實際上是二分圖。

圖片

不難發(fā)現(xiàn)，這里面大多數(shù)表現(xiàn)最優(yōu)的圖形都是二分圖。而這一規(guī)律也被稱為稱為Turán三角定理或Mantel定理。

二分圖（Bipartite Graph）是一種特殊類型的圖，它的頂點可以被分成兩個互不相交的集合，比如說集合A和集合B。

圖片

在二分圖中，每條邊都連接著集合A中的一個頂點和集合B中的一個頂點，也就是說，集合A中和B中各自都不存在將兩個頂點相連接的邊。

但是如果問題變得更加艱難，要求的結構不僅僅只是三角形呢？比如五邊形這樣更為復雜的結構。這時研究者就很難再憑借歸納和直覺去發(fā)現(xiàn)其最優(yōu)結果中蘊含的規(guī)律了。

圖片

所以研究者希望有一種通用的方法，可以幫助發(fā)現(xiàn)或自行逐漸逼近這些結構。

PatternBoost就是這樣一種方法！

首先，研究者需要確定局部搜索方法和評分函數(shù)。

局部搜索法是一種將可能包含也可能不包含三角形的圖形作為輸入的算法，并輸出一個得分至少與輸入得分相同的圖形。

由于研究者想要說明的是局部-全局迭代方法的有效性本身，所以不執(zhí)著于優(yōu)化局部搜索函數(shù)，而是采用了很簡單的辦法。也就是：

- 當搜索到的圖還包含三角形時，就刪掉其中的一條邊

- 一旦圖中已經(jīng)沒有三角形，則在不創(chuàng)建新三角形的情況下，盡可能多地隨機添加新邊

評分函數(shù)則需要體現(xiàn)出當前得到的結構逼近于最優(yōu)結構的程度。

例如，如果圖包含任何三角形，研究者可以決定給出負無窮大的分數(shù)，否則返回邊的數(shù)量。邊的數(shù)量越大，則分數(shù)越高。

需要注意的是，如果圖形中有三角形，研究者也可以從三角形中直接刪除任何邊，以使分數(shù)至少增加1

具體步驟

第一步：創(chuàng)建起始數(shù)據(jù)庫

研究者的步驟如下：從空圖開始，以此為起點運行上述簡單的局部搜索算法(即在不產(chǎn)生三角形的情況下，盡可能長時間地隨機添加邊)。

他們重復了40,000次，每次都從空圖開始，得到的分數(shù)分布如圖1所示（由于局部搜索的輸出永遠不會出現(xiàn)三角形，因此這里的分數(shù)只是邊的數(shù)量）。

大部分圖形分數(shù)的分布都是一個平滑的分布，峰值為66。然后研究者保留了該數(shù)據(jù)集中得分最高的25%；這些圖形將作為訓練集。

從圖1右側(cè)的直方圖中可以看到訓練集的分數(shù)分布。

圖片

訓練集中的每個圖都可以用其鄰接矩陣來表示，該矩陣有n2=202=400個條目。

研究者注意到，鄰接矩陣是對稱的，而且沒有循環(huán)，因此可以使用矩陣的上三角部分而不是整個矩陣，從而將其減少到20×19/2 = 190。

研究者使用的Transformer接受一維輸入；因此，研究者可以將上三角矩陣逐行寫出，并在每行后加上分隔符(在本例中為逗號)，從而將其扁平化，如圖2所示。

圖片

在開始訓練之前，可以通過Byte-Pair Encoding (BPE) Tokenization來標記化數(shù)據(jù)以去進一步的數(shù)據(jù)壓縮。

也就是說，如果研究者發(fā)現(xiàn)字符串「00101」在數(shù)據(jù)集中出現(xiàn)了很多次，那么研究者就引入一個新的字符，比如「2」，來表示這個字符串。

圖片

第二步：訓練Transformer

研究者使用的是Makemore，這是Andrej Karpathy的一個簡單的Transformer實現(xiàn)。

他的代碼的優(yōu)點是，它是公開可用的，并且易于修改，并且它提供了一個穩(wěn)固的基線，因此研究者可以嘗試用更復雜的方法超越它。

研究者使用了一個微小的2層Transformer，包含4個頭部和16的嵌入維度。

他們訓練這個Transformer來生成與初始數(shù)據(jù)集中的「相似」的序列，方法類似于將一個大型英語句子數(shù)據(jù)庫（即序列中的大多數(shù)是單詞）給Transformer進行訓練，使其能夠生成更多的英語句子。

在訓練的每一個階段，都可以讓Transformer預測給定的k個token序列之后的下一個token。特別地，對于每一個k和數(shù)據(jù)集中每個圖G（用token序列表示），可以讓Transformer在給定前k個token的情況下預測第k+1個token。

「損失」衡量了Transformer未能正確預測G中實際下一個token的頻率。經(jīng)過15,000步的訓練后，訓練集的損失降到2.07，測試集的損失為2.09。

第三步：從Transformer獲取新結構

接下來，研究者要求Transformer生成在某種「全局」意義上與研究者迄今為止遇到的最佳圖形(即訓練集中的圖形)相似的新結構。

研究者以這種方式生成了100,000個tokenized的新圖形。在將token序列解碼為矩陣(或嘗試解碼為矩陣)后，研究者得到了37,000個矩陣的條目數(shù)(190)，這與20個頂點圖的鄰接矩陣相符。

第四步：從Transformer中獲得的新結構中，運行本地搜索

研究者把從小模型中得到的37000個有效結構圖，重新輸入到他們的簡單局部搜索算法中。

也就是說，從這37,000個圖形中的每一個中，研究者首先貪婪地刪除邊以去除所有三角形，然后盡可能長時間地隨機添加邊而不產(chǎn)生任何新的三角形。

圖片

第五步：重復此過程

最后，研究者重復提取上一代中最好的10,000個詞組，使用之前相同的token對它們進行分詞，并在這個新的訓練集上微調(diào)Transformer。

請注意，每次迭代都不需要從頭開始訓練。通過再進行5次循環(huán)，模型很快學會只生成完整的二分圖，而且這些二分圖中的大多數(shù)都具有相等的兩部分大小，見圖4。

圖片

可以直觀地發(fā)現(xiàn)，隨著迭代的代數(shù)增加，分數(shù)分布的峰值也逐漸越來越高，從75轉(zhuǎn)移到了最終的滿分100，十分直接地證明了局部+全局聯(lián)合迭代搜索這種流程的有效性。

長期未解決的猜想：d-維超立方體直徑為d的生成子圖

超立方體（Hypercube）是一種常見的網(wǎng)絡拓撲結構，其結構為一個具有高對稱性的n維立方體，每個頂點與其他所有頂點都直接相連。

圖片

在超立方體中，直徑是一個重要的概念，它表示從任意一個頂點到另一個頂點所需的最大步數(shù)。

對于并行計算網(wǎng)絡，如大規(guī)模并行計算機中的處理器網(wǎng)絡，超立方體的直徑是描述其通信效率的關鍵參數(shù)，因為它直接影響到網(wǎng)絡中的通信速度和延遲。

圖片

因此，研究超立方體的直徑以及如何通過改變其結構來優(yōu)化直徑成為了一個重要的研究方向。

在論文中提到的長期未解決的問題是：在不增加其直徑的情況下，可以從d-維超立方體中刪除的最大邊數(shù)是多少？

這個問題最早由Niali Graham和Frank Harary在1992年提出，問題也可以表述為，怎么構造直徑始終是d的d維超立方體的最小生成子圖。

圖片

對于這個問題，曾經(jīng)提出的猜想具體是這樣的：

他們觀察到，如果固定兩個相對的頂點v和v′，并通過為每個頂點u（u不屬于{v, v′}）構建一個子圖G，其中包括一條通向在d-維立方體中更接近v的頂點的邊和一條通向在d-維立方體中更接近v′的頂點的邊，則生成的子圖是全覆蓋的且具有直徑d。這樣的子圖至少有條邊，并且可以通過多種方式實現(xiàn)這樣的構造。

圖片

問題來了：是否存在一種更好的構造，可以用到更少的邊？Graham猜想，這種構造實際上就是最優(yōu)的。

圖片

一個直徑為5的5維超立方體的子圖，包含40條邊。注意，從每個頂點都有一條邊向下和一條邊向上連接，即不存在阻塞頂點

對于PatternBoost，有一種自然的方法來建立這個猜想。一個具有跨度并且直徑為d的子圖的分數(shù)可以定義為其中的邊數(shù)（研究者試圖將其最小化）。

反例的提出

對于局部搜索，最簡單的算法是，給定一個子圖G，向G中隨機添加邊，直到它成為一個具有直徑d的跨度圖，然后在盡可能長的時間內(nèi)隨機移除邊，同時保持直徑為d。

研究者對d=5和6的情況，進行了實驗。

對于d=5，上述構造似乎是最優(yōu)的，但對于d=6，研究者能夠找到一個具有81條邊的圖（而非上述構造中的條邊），見圖10。

這推翻了之前的猜想，并標志著在這個問題上30年來的首次進展。

一個有趣的觀察是，對于較大的d值，下界或上界哪個更接近真實情況。

用AI生成純數(shù)學構造

總的來說，在本文中，研究者介紹并舉例說明了一種稱為PatternBoost的計算方法，用于生成純數(shù)學中有趣的構造。

該方法涉及「局部」與「全局」步驟的反復交替。前者通常是一個簡單的貪婪算法，后者則是一種結合Transformer的遺傳算法，這是一種靈活的機器學習技術，研究者認為其特別適合處理此類問題。

為了理解這種迭代可能的樣子，可以考慮一個集體合作迭代的例子，即自行車的設計。

- 「局部」步驟涉及許多單個自行車制造商各自對他們的設計進行一系列精細調(diào)整，努力使其盡可能地高效和舒適。

- 「全局」步驟則涉及生活在世界各地的人們，他們看到周圍的許多自行車，每一輛都經(jīng)過精心的局部優(yōu)化，然后基于他們觀察到的自行車進而設計開發(fā)出新的自行車設計。

當然，這種新設計隨后會由其設計者和其他人精心優(yōu)化；如果經(jīng)過這些調(diào)整后，新自行車被證明特別舒適和高效，那么它們將被大量銷售，并加入下一位潛在設計者觀察到的一般自行車隊列中……如此周而復始。

數(shù)學對象并非自行車。但人類可以抽象出自行車的特征，并開發(fā)出研究者認知為自行車的新對象，盡管它們與任何現(xiàn)有實例都不完全相同，數(shù)學家對數(shù)學對象也是如此。然而，這個過程通常很難自動化。

研究者對這里描述的方法的希望在于，機器學習的技術（尤其是 Transformer）至少具備某種程度的這種能力——即面對一系列數(shù)學實體時，它們可以產(chǎn)生更多在某些方面「同類」的例子，便于互相參照，進行迭代。

研究者的工作受到第三作者早期工作的強烈影響。在那項工作中，強化學習中的交叉熵方法被用來尋找組合學中幾個問題的反例。

交叉熵方法的問題在于其擴展性：當序列長度超過幾百個Token時，基礎神經(jīng)網(wǎng)絡就會變得難以訓練。

在AI中，當嘗試使用基礎神經(jīng)網(wǎng)絡對長序列的字母或單詞進行下一個Token預測時，也會遇到類似的問題，而Transformer架構正是在這類問題上表現(xiàn)出色。

PatternBoost的主要優(yōu)勢之一，就是其廣泛的適用性。通過添加一個使用Transformer的全局步驟來為局部搜索建議更好的起點，PatternBoost可以改良許多優(yōu)化問題的結果。

PatternBoost可以視為放置在任何局部搜索方法之上的額外層，通常能比單獨使用局部搜索獲得更好的解決方案。

簡單來說，無論研究者使用何種局部搜索算法，PatternBoost 通常都能使其更好。

研究者強調(diào)，研究者的主要目標是為數(shù)學工作者開發(fā)一個有用且簡單的工具，該工具不需要深入的機器學習專業(yè)知識或使用工業(yè)級計算能力。

使用機器學習作為數(shù)學中的實用工具的一個困難在于，機器學習本身很復雜！人們可能會花費大量時間來調(diào)整超參數(shù)、探索不同的Token化方案等。

在研究者看來，PatternBoost的一個優(yōu)點在于其Transformer架構表現(xiàn)得非常具有彈性，通常可以直接使用，而不需要數(shù)學家進行過多的調(diào)整，因為他們的專業(yè)和興趣可能在其他領域。

他們使用了Andrej Kaparthy的Makemore提供的一個美觀且簡單的Transformer實現(xiàn)，在研究者的實驗中，它似乎在廣泛的數(shù)學背景下都生成了有效的輸出。

圖片

這里討論的問題只是他們在開發(fā)PatternBoost時嘗試的最初幾個問題——他們希望并期望其他數(shù)學家會興致盎然地進行進一步的實驗，從而幫助揭開哪些數(shù)學問題適合于機器學習增強方法的這一神秘面紗。

特別是，本文討論的例子主要集中在極值組合數(shù)學領域，其中Transformer被用來構造在某些約束條件下盡可能大的組合例子。

當然，組合結構是最容易作為Transformer輸入呈現(xiàn)的實體；但他們并不認為該方法原則上僅限于數(shù)學的這一領域。

事實上，該方法中沒有任何內(nèi)容是特定于數(shù)學的！他們也十分有興趣了解PatternBoost是否可以應用于數(shù)學之外的問題。

顯而易見的一個挑戰(zhàn)是，在數(shù)學中，一個被提議的例子通常可以被機械地、可靠快速地評估，這對PatternBoost至關重要；而在其他領域，評估可能會比較困難。

涉及到的機器學習技術

模型訓練完成后，研究者會從「空序列」t0 開始生成候選方案，并從訓練模型預測的分布中抽取第一個標記t1。

然后，研究者會向模型輸入t0 t1序列，并從預測的分布中采樣第二個token t2。如此反復，直到生成完整的解決方案。

這將鼓勵模型生成與其訓練數(shù)據(jù)類似的序列（即研究者問題的有希望的解決方案）。

為了將數(shù)學結構（如網(wǎng)格和圖）編碼為Transformer可以處理的形式，需要將這些結構轉(zhuǎn)換為token序列，這一過程稱為「分詞」。

以下是具體的編碼方法：

對于網(wǎng)格編碼來講，一個??×??的網(wǎng)格可以用n^2個二進制條目表示，每個條目表示一個單元格的狀態(tài)（0或1）。

即使n值適中，這種樸素的二進制表示也會導致非常長的序列，增加學習的復雜性。

為了減少序列長度，研究者可以將多個二進制條目編碼為一個標記，從而在詞匯表大小和序列長度之間進行權衡。

例如，可以將4個二進制條目編碼為一個token，這樣詞匯表大小會增加，但序列長度會減少。

而圖編碼則是可以采用鄰接矩陣的表示方法，用二進制表示時，可以采用n(n-1)個二進制條目表示，每個條目表示一條邊的存在狀態(tài)。

類似地，也可以將多個二進制條目編碼為一個token，以減少序列長度。

每個序列始終以特殊的 <start> 標記開始，以 <end> 標記結束，以便模型知道序列的開始和結束位置。

通過將數(shù)學結構（如網(wǎng)格和圖）編碼為Transformer可以處理的標記序列，PatternBoost能夠利用Transformer的強大建模能力來生成復雜的數(shù)學構造。

這種編碼方法不僅減少了序列長度，提高了學習效率，還使得模型能夠生成與訓練數(shù)據(jù)相似的有希望的解決方案。這種方法在多個離散數(shù)學問題中展示了其有效性和靈活性。

參考資料：https://arxiv.org/abs/2411.00566