太平洋科技要聞

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

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

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

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

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

其核心思想是交替進(jìn)行「局部搜索」和「全局搜索」。

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

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

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

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

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

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

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

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

這個(gè)可能性，實(shí)在太令人興奮了。

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

比如可以生成網(wǎng)絡(luò)拓?fù)渲休^為常見的C4-free稠密圖，也就是一幅不存在由4個(gè)頂點(diǎn)組成的閉合路徑的稠密圖。

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

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

此類問題對(duì)機(jī)器學(xué)習(xí)方法具有挑戰(zhàn)性，因?yàn)槠鋽?shù)學(xué)結(jié)構(gòu)較為復(fù)雜且解的空間巨大。

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

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

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

問題引入

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

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

然后，我們會(huì)很幸運(yùn)地注意到，許多示例實(shí)際上是二分圖。

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

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

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

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

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

PatternBoost就是這樣一種方法！

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

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

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

- 當(dāng)搜索到的圖還包含三角形時(shí)，就刪掉其中的一條邊

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

評(píng)分函數(shù)則需要體現(xiàn)出當(dāng)前得到的結(jié)構(gòu)逼近于最優(yōu)結(jié)構(gòu)的程度。

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

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

具體步驟

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

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

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

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

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

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

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

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

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

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

第二步：訓(xùn)練Transformer

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

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

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

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

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

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

第三步：從Transformer獲取新結(jié)構(gòu)

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

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

第四步：從Transformer中獲得的新結(jié)構(gòu)中，運(yùn)行本地搜索

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

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

第五步：重復(fù)此過程

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

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

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

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

超立方體（Hypercube）是一種常見的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其結(jié)構(gòu)為一個(gè)具有高對(duì)稱性的n維立方體，每個(gè)頂點(diǎn)與其他所有頂點(diǎn)都直接相連。

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

對(duì)于并行計(jì)算網(wǎng)絡(luò)，如大規(guī)模并行計(jì)算機(jī)中的處理器網(wǎng)絡(luò)，超立方體的直徑是描述其通信效率的關(guān)鍵參數(shù)，因?yàn)樗苯佑绊懙骄W(wǎng)絡(luò)中的通信速度和延遲。

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

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

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

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

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

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

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

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

反例的提出

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

研究者對(duì)d=5和6的情況，進(jìn)行了實(shí)驗(yàn)。

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

這推翻了之前的猜想，并標(biāo)志著在這個(gè)問題上30年來的首次進(jìn)展。

一個(gè)有趣的觀察是，對(duì)于較大的d值，下界或上界哪個(gè)更接近真實(shí)情況。

用AI生成純數(shù)學(xué)構(gòu)造

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

該方法涉及「局部」與「全局」步驟的反復(fù)交替。前者通常是一個(gè)簡單的貪婪算法，后者則是一種結(jié)合Transformer的遺傳算法，這是一種靈活的機(jī)器學(xué)習(xí)技術(shù)，研究者認(rèn)為其特別適合處理此類問題。

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

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

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

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

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

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

研究者的工作受到第三作者早期工作的強(qiáng)烈影響。在那項(xiàng)工作中，強(qiáng)化學(xué)習(xí)中的交叉熵方法被用來尋找組合學(xué)中幾個(gè)問題的反例。

交叉熵方法的問題在于其擴(kuò)展性：當(dāng)序列長度超過幾百個(gè)Token時(shí)，基礎(chǔ)神經(jīng)網(wǎng)絡(luò)就會(huì)變得難以訓(xùn)練。

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

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

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

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

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

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

在研究者看來，PatternBoost的一個(gè)優(yōu)點(diǎn)在于其Transformer架構(gòu)表現(xiàn)得非常具有彈性，通�？梢灾苯邮褂茫恍枰獢�(shù)學(xué)家進(jìn)行過多的調(diào)整，因?yàn)樗麄兊膶I(yè)和興趣可能在其他領(lǐng)域。

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

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

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

當(dāng)然，組合結(jié)構(gòu)是最容易作為Transformer輸入呈現(xiàn)的實(shí)體；但他們并不認(rèn)為該方法原則上僅限于數(shù)學(xué)的這一領(lǐng)域。

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

顯而易見的一個(gè)挑戰(zhàn)是，在數(shù)學(xué)中，一個(gè)被提議的例子通�？梢员粰C(jī)械地、可靠快速地評(píng)估，這對(duì)PatternBoost至關(guān)重要；而在其他領(lǐng)域，評(píng)估可能會(huì)比較困難。

涉及到的機(jī)器學(xué)習(xí)技術(shù)

模型訓(xùn)練完成后，研究者會(huì)從「空序列」t0 開始生成候選方案，并從訓(xùn)練模型預(yù)測的分布中抽取第一個(gè)標(biāo)記t1。

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

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

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

以下是具體的編碼方法：

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

即使n值適中，這種樸素的二進(jìn)制表示也會(huì)導(dǎo)致非常長的序列，增加學(xué)習(xí)的復(fù)雜性。