首頁 > 科技要聞 > 科技> 正文

Transformer打破三十年數學猜想！Meta研究者用AI給出反例，算法殺手攻克數學難題

新智元 整合編輯：太平洋科技 發(fā)布于：2024-11-14 17:22

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題引入

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

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

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

不難發(fā)現(xiàn)，這里面大多數表現(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就是這樣一種方法！

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

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

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

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

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

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

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

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

具體步驟

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

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

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

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

從圖1右側的直方圖中可以看到訓練集的分數分布。

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

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

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

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

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

第二步：訓練Transformer

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

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

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

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

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

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

第三步：從Transformer獲取新結構

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

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

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

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

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

第五步：重復此過程

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

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

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

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

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

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

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

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

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

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

對于這個問題，曾經提出的猜想具體是這樣的：

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

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

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

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

反例的提出

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

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

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

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

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

用AI生成純數學構造

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

涉及到的機器學習技術

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

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

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

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

以下是具體的編碼方法：

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

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

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

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

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

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

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

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

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

本文來源：新智元

網友評論

聚超值•精選

推薦 手機 筆記本 影像 硬件 家居 商用 企業(yè) 出行 未來
二維碼 回到頂部