新智元報道
編輯：編輯部 HZh【新智元導讀】30多年的數(shù)學猜想首次獲得了進展！Meta等學者提出的PatternBoost，使用Transformer構(gòu)造了一個反例，反駁了一個已懸而未決30年的猜想。是否所有數(shù)學問題都適合機器學習技術(shù)？這樣的未來太令人期待了。30多年的數(shù)學猜想，被AI發(fā)現(xiàn)了一個反例？就在剛剛，Meta、威斯康星大學麥迪遜分校、伍斯特理工學院、悉尼大學的幾位學者提出PatternBoost，這種全新的方法可以在一些數(shù)學問題中尋找有趣的結(jié)構(gòu)。
論文地址：https://arxiv.org/abs/2411.00566其核心思想是交替進行「局部搜索」和「全局搜索」。在第一個「局部」階段，使用傳統(tǒng)的經(jīng)典搜索算法來生成許多理想的構(gòu)造。在第二個「全局」階段，使用Transformer神經(jīng)網(wǎng)絡對這些最優(yōu)構(gòu)造進行訓練。然后，將訓練好的Transformer樣本用作第一個階段的種子，并重復該過程。前者類似于貪心算法，比如給定一個圖形，去除包含多個4-圈的邊，直到?jīng)]有4-圈為止。而后者的一個例子，是讓Transformer生成更多類似于上次篩選中表現(xiàn)前1%的圖。這種迭代交替，比傳統(tǒng)的貪婪方法或者單獨的非貪婪增強Transformer方法要好得多。
結(jié)合Transformers來求解離散優(yōu)化問題的步驟比起某些問題，它會更擅長解決另一些問題。因此，這篇論文在許多不同的數(shù)學領(lǐng)域測試了相同的協(xié)議。哪些數(shù)學問題最適用于機器學習技術(shù)？或者說，最終我們將證明，所有數(shù)學問題都適合機器學習技術(shù)？這個可能性，實在太令人興奮了。PatternBoost不僅找到了幾個長期問題的最佳已知解決方案，而且還構(gòu)造了一個反例，反駁了一個已懸而未決30年的猜想。比如可以生成網(wǎng)絡拓撲中較為常見的C4-free稠密圖，也就是一幅不存在由4個頂點組成的閉合路徑的稠密圖。PatternBoost在多個極值組合學問題中表現(xiàn)優(yōu)異，其中一個經(jīng)典應用是，就是無4-圈問題。
即在給定頂點數(shù)n的情況下，構(gòu)造盡可能多的邊而不包含4-圈的圖。此類問題對機器學習方法具有挑戰(zhàn)性，因為其數(shù)學結(jié)構(gòu)較為復雜且解的空間巨大。研究者是通過以下步驟應用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中各自都不存在將兩個頂點相連接的邊。但是如果問題變得更加艱難，要求的結(jié)構(gòu)不僅僅只是三角形呢？比如五邊形這樣更為復雜的結(jié)構(gòu)。這時研究者就很難再憑借歸納和直覺去發(fā)現(xiàn)其最優(yōu)結(jié)果中蘊含的規(guī)律了。
所以研究者希望有一種通用的方法，可以幫助發(fā)現(xiàn)或自行逐漸逼近這些結(jié)構(gòu)。PatternBoost就是這樣一種方法！首先，研究者需要確定局部搜索方法和評分函數(shù)。局部搜索法是一種將可能包含也可能不包含三角形的圖形作為輸入的算法，并輸出一個得分至少與輸入得分相同的圖形。由于研究者想要說明的是局部-全局迭代方法的有效性本身，所以不執(zhí)著于優(yōu)化局部搜索函數(shù)，而是采用了很簡單的辦法。也就是：- 當搜索到的圖還包含三角形時，就刪掉其中的一條邊- 一旦圖中已經(jīng)沒有三角形，則在不創(chuàng)建新三角形的情況下，盡可能多地隨機添加新邊評分函數(shù)則需要體現(xiàn)出當前得到的結(jié)構(gòu)逼近于最優(yōu)結(jié)構(gò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ù)分布。
訓練集中的每個圖都可以用其鄰接矩陣來表示，該矩陣有n=20=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獲取新結(jié)構(gòu)接下來，研究者要求Transformer生成在某種「全局」意義上與研究者迄今為止遇到的最佳圖形(即訓練集中的圖形)相似的新結(jié)構(gòu)。研究者以這種方式生成了100,000個tokenized的新圖形。在將token序列解碼為矩陣(或嘗試解碼為矩陣)后，研究者得到了37,000個矩陣的條目數(shù)(190)，這與20個頂點圖的鄰接矩陣相符。第四步：從Transformer中獲得的新結(jié)構(gòu)中，運行本地搜索研究者把從小模型中得到的37000個有效結(jié)構(gòu)圖，重新輸入到他們的簡單局部搜索算法中。也就是說，從這37,000個圖形中的每一個中，研究者首先貪婪地刪除邊以去除所有三角形，然后盡可能長時間地隨機添加邊而不產(chǎn)生任何新的三角形。
第五步：重復此過程最后，研究者重復提取上一代中最好的10,000個詞組，使用之前相同的token對它們進行分詞，并在這個新的訓練集上微調(diào)Transformer。請注意，每次迭代都不需要從頭開始訓練。通過再進行5次循環(huán)，模型很快學會只生成完整的二分圖，而且這些二分圖中的大多數(shù)都具有相等的兩部分大小，見圖4。
