新智元報(bào)道
編輯：編輯部 HZh【新智元導(dǎo)讀】30多年的數(shù)學(xué)猜想首次獲得了進(jìn)展！Meta等學(xué)者提出的PatternBoost，使用Transformer構(gòu)造了一個(gè)反例，反駁了一個(gè)已懸而未決30年的猜想。是否所有數(shù)學(xué)問題都適合機(jī)器學(xué)習(xí)技術(shù)？這樣的未來太令人期待了。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ò)對這些最優(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-圈的圖。此類問題對機(jī)器學(xué)習(xí)方法具有挑戰(zhàn)性，因?yàn)槠鋽?shù)學(xué)結(jié)構(gòu)較為復(fù)雜且解的空間巨大。研究者是通過以下步驟應(yīng)用PatternBoost的：首先生成一個(gè)初始數(shù)據(jù)集，并使用Transformer模型對其進(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就是這樣一種方法！首先，研究者需要確定局部搜索方法和評分函數(shù)。局部搜索法是一種將可能包含也可能不包含三角形的圖形作為輸入的算法，并輸出一個(gè)得分至少與輸入得分相同的圖形。由于研究者想要說明的是局部-全局迭代方法的有效性本身，所以不執(zhí)著于優(yōu)化局部搜索函數(shù)，而是采用了很簡單的辦法。也就是：- 當(dāng)搜索到的圖還包含三角形時(shí)，就刪掉其中的一條邊- 一旦圖中已經(jīng)沒有三角形，則在不創(chuàng)建新三角形的情況下，盡可能多地隨機(jī)添加新邊評分函數(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ù)庫研究者的步驟如下：從空圖開始，以此為起點(diǎn)運(yùn)行上述簡單的局部搜索算法(即在不產(chǎn)生三角形的情況下，盡可能長時(shí)間地隨機(jī)添加邊)。他們重復(fù)了40,000次，每次都從空圖開始，得到的分?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è)條目。研究者注意到，鄰接矩陣是對稱的，而且沒有循環(huán)，因此可以使用矩陣的上三角部分而不是整個(gè)矩陣，從而將其減少到20×19/2 = 190。研究者使用的Transformer接受一維輸入；因此，研究者可以將上三角矩陣逐行寫出，并在每行后加上分隔符(在本例中為逗號)，從而將其扁平化，如圖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。特別地，對于每一個(gè)k和數(shù)據(jù)集中每個(gè)圖G（用token序列表示），可以讓Transformer在給定前k個(gè)token的情況下預(yù)測第k+1個(gè)token�！笓p失」衡量了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對它們進(jìn)行分詞，并在這個(gè)新的訓(xùn)練集上微調(diào)Transformer。請注意，每次迭代都不需要從頭開始訓(xùn)練。通過再進(jìn)行5次循環(huán)，模型很快學(xué)會(huì)只生成完整的二分圖，而且這些二分圖中的大多數(shù)都具有相等的兩部分大小，見圖4。
