首位超越國(guó)際奧林匹克競(jìng)賽金牌得主的AI，剛剛誕生了！

印度理工學(xué)院海得拉巴分校、圖賓根AI中心、劍橋大學(xué)的研究者發(fā)現(xiàn)——

通過(guò)「吳方法」，可以讓AI變成和人類數(shù)學(xué)奧賽銀牌得主同樣的水平，而「AI數(shù)學(xué)大師」AlphaGeometry，則直接超越了IMO金牌得主。

圖片

吳方法，是吳文俊在1970年代提出的開(kāi)創(chuàng)性算法。

經(jīng)過(guò)改進(jìn)后，它變得非常強(qiáng)大，可以解決國(guó)際數(shù)學(xué)奧林匹克競(jìng)賽30個(gè)問(wèn)題中的27個(gè)！直接秒殺人類。

相比之下，之前的AlphaGeometry，僅能解決25個(gè)。

圖片

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

項(xiàng)目地址：https://huggingface.co/datasets/bethgelab/simplegeometry

之前曾有人估計(jì)，到2026年代，AI才能達(dá)到IMO人類金牌得主的水平。而如今，這個(gè)時(shí)間表再次被打破了。

圖片

AI做IMO奧數(shù)題，有新SOTA了

證明幾何定理是視覺(jué)推理的重要表現(xiàn)，它融合了直覺(jué)和邏輯思維。

因此，自動(dòng)化證明奧林匹克級(jí)別的幾何題目，代表著人類級(jí)自動(dòng)推理的一個(gè)重要里程碑。

此前推出的AlphaGeometry，是一個(gè)通過(guò)1億個(gè)合成樣本訓(xùn)練的神經(jīng)符號(hào)模型，代表了一個(gè)重大的突破。

圖片

論文地址：https://www.nature.com/articles/s41586-023-06747-5

它成功解決了國(guó)際數(shù)學(xué)奧林匹克（IMO）30個(gè)問(wèn)題中的25個(gè)，而傳統(tǒng)的基于吳方法的系統(tǒng)，僅能解決10個(gè)。

但這一次，研究者們重新評(píng)估了AlphaGeometry引入的IMO-AG-30挑戰(zhàn)，有了新的發(fā)現(xiàn)——

吳方法異常強(qiáng)大！

僅靠吳方法，就能解決15個(gè)問(wèn)題，其中一些問(wèn)題是靠其他方法根本無(wú)法解決的。

圖片

而這就帶來(lái)了兩個(gè)關(guān)鍵發(fā)現(xiàn)：

1. 通過(guò)將「吳方法」和經(jīng)典的演繹數(shù)據(jù)庫(kù)（DD）以及角度、比率和距離追蹤（AR）的合成方法相結(jié)合，僅使用一臺(tái)配備CPU的筆記本，在每個(gè)問(wèn)題的5分鐘限時(shí)內(nèi)，就能解決30個(gè)問(wèn)題中的21個(gè)。

這種經(jīng)典組合方法（Wu&DD+AR）僅比AlphaGeometry少解決了4個(gè)問(wèn)題，并建立了第一個(gè)完全基于符號(hào)的基準(zhǔn)，其性能足以與國(guó)際數(shù)學(xué)奧林匹克（IMO）銀牌得主媲美。

2. 吳方法還解決了AlphaGeometry未能解決的5個(gè)問(wèn)題中的2個(gè)。

因此，現(xiàn)在IMO-AG-30有新的SOTA了！

通過(guò)將AlphaGeometry與吳方法結(jié)合產(chǎn)生的新AI，直接解決了30個(gè)問(wèn)題中的27個(gè)，一舉超越IMO金牌得主，成為世上首個(gè)達(dá)此成就的AI。

歐氏幾何，AI推理能力的試金石

如何測(cè)試AI的推理能力強(qiáng)不強(qiáng)？歐幾里得幾何就是一個(gè)很好的標(biāo)準(zhǔn)。

因?yàn)椋瑲W幾里得幾何已經(jīng)被有限地公理化了，而且這么多年來(lái)，有許多非常適合自動(dòng)定理證明的歐幾里得幾何證明系統(tǒng)被提了出來(lái)。

圖片

此外證明的搜索可以通過(guò)圖形表示、概率驗(yàn)證，或是使用人類設(shè)計(jì)的啟發(fā)式方法，來(lái)對(duì)角度、面積和距離進(jìn)行大量推理引導(dǎo)。

國(guó)際數(shù)學(xué)奧林匹克中，這些方法被參賽者戲稱為「三角破解」和「重心破解」。

還有一件有趣的事，就是這個(gè)領(lǐng)域的缺陷——它需要定義特定的證明系統(tǒng)來(lái)指定問(wèn)題，缺乏訓(xùn)練數(shù)據(jù)，問(wèn)題時(shí)常涉及復(fù)雜的退化情況。

這些困難非常棘手，由此坊間有這樣一句戲言——「幾何問(wèn)題永遠(yuǎn)不會(huì)解決退化問(wèn)題。」

圖片

在幾何自動(dòng)推理領(lǐng)域，可以將方法分為代數(shù)方法和合成方法。

演繹數(shù)據(jù)庫(kù)（DD）這個(gè)合成方法就頗受關(guān)注。

它會(huì)模仿人類的證明技巧，通過(guò)將定理證明視為依據(jù)一組幾何公理進(jìn)行的逐步搜索問(wèn)題，從而生成易于理解的證明。

比如，DD會(huì)采用一組固定的、由專家策劃的幾何規(guī)則，這些規(guī)則會(huì)不斷地應(yīng)用到初始的幾何配置上，直至系統(tǒng)達(dá)到一個(gè)狀態(tài)，即用現(xiàn)有規(guī)則無(wú)法推導(dǎo)出新的事實(shí)為止。

圖片

而神經(jīng)符號(hào)證明器AlphaGeometry在這一領(lǐng)域取得了突破性的進(jìn)展。

在DD的基礎(chǔ)上，它增加了新的規(guī)則，用于進(jìn)行角度、比率和距離的追蹤（AR），并通過(guò)大模型（DD+AR+LLM-構(gòu)造）提出的構(gòu)建方法，進(jìn)一步增強(qiáng)了由此生成的符號(hào)引擎。該模型是基于1億個(gè)合成證明訓(xùn)練的。

而吳方法和Gr?bner基方法之類的代數(shù)方法，能夠?qū)缀渭僭O(shè)，轉(zhuǎn)換成多項(xiàng)式系統(tǒng)，來(lái)驗(yàn)證結(jié)論。

這些方法已被證實(shí)，能夠有效處理廣泛的幾何問(wèn)題。

其中，對(duì)于所有假設(shè)和結(jié)論都能用代數(shù)方程表示的問(wèn)題，吳方法都能處理，并且還能自動(dòng)產(chǎn)生非退化條件。

而這就表明，吳方法不僅適用于平面幾何問(wèn)題，也適用于固體和更高維的幾何問(wèn)題。

5秒解決14個(gè)問(wèn)題

今年1月，谷歌DeepMind團(tuán)隊(duì)同時(shí)推出了新的基準(zhǔn)測(cè)試IMO-AG-30。

這是團(tuán)隊(duì)從2000年至2022年間競(jìng)賽題中，篩選出30道經(jīng)典幾何問(wèn)題組成的測(cè)試集，目的是為了展示AlphaGeometry的性能。

基準(zhǔn)中，問(wèn)題的解決數(shù)量與IMO選手的平均解題數(shù)量相對(duì)應(yīng)。

如下圖，灰色水平線所示，銅牌、銀牌和金牌得主平均分別解決了19.3個(gè)、22.9個(gè)和25.9個(gè)問(wèn)題。

所有參賽者平均解題數(shù)為15.2。

IMO-AG-30收集的具體問(wèn)題集在圖1（B）的左列中有所列出。

圖片

（A）在IMO-AG-30問(wèn)題集上，符號(hào)系統(tǒng)和增強(qiáng)型大模型（LLM-Augmented）的表現(xiàn)，以及與人類表現(xiàn)的對(duì)比

（B）展示了不同方法在解決IMO-AG-30問(wèn)題集時(shí)的情況

實(shí)驗(yàn)

研究人員根據(jù)Trinh等人提供的基線和數(shù)據(jù)集，使用IMO-AG-30基準(zhǔn)進(jìn)行性能評(píng)估。

他們通過(guò)JGEX軟件手動(dòng)將IMO-AG-30問(wèn)題轉(zhuǎn)換成兼容格式，并重新實(shí)現(xiàn)了吳方法。

同時(shí)，研究者也從AlphaGeometry代碼庫(kù)中成功重現(xiàn)了必要的DD+AR基線。

經(jīng)過(guò)手動(dòng)驗(yàn)證了自己翻譯的幾個(gè)問(wèn)題，團(tuán)隊(duì)確認(rèn)JGEX生成的假設(shè)和結(jié)論方程是正確的。

吳方法解決了AlphaGeometry未能解決的兩個(gè)問(wèn)題，方案插圖如下所示。

2008-P1B（JGEX）：

圖片

生成的答案：

圖片

圖片

2021-P3（JGEX）：

圖片

生成的答案：

圖片

結(jié)果

研究結(jié)果與的先前結(jié)果，已經(jīng)在圖1中進(jìn)行了展示。

圖1（A）比較了解決問(wèn)題的數(shù)量，圖1（B）展示了各種方法解決的具體問(wèn)題，以此可視化不同方法之間的重疊或互補(bǔ)性。

具體來(lái)說(shuō)，研究人員將吳方法與DD+AR結(jié)合，創(chuàng)建了一個(gè)新的符號(hào)性能基準(zhǔn)（Wu&DD+AR），該基準(zhǔn)比所有傳統(tǒng)方法多解決了6個(gè)問(wèn)題。

這種組合解決了IMO-AG-30問(wèn)題中的21個(gè)，與圖2中未經(jīng)微調(diào)（僅FT-9M）的AlphaGeometry的表現(xiàn)相匹配。

圖片

（A）展示了在IMO-AG-30問(wèn)題集上，符號(hào)方法和LLM增強(qiáng)（LLM-Augmented）方法的表現(xiàn)，以及與人類表現(xiàn)的對(duì)比

（B）展示了不同方法在IMO-AG-30問(wèn)題上的表現(xiàn)

吳方法在非常低的計(jì)算需求下實(shí)現(xiàn)了這一表現(xiàn)。

在一臺(tái)裝有AMD Ryzen 7 5800H處理器和16 GB RAM的筆記本上，研究人員在5秒內(nèi)解決了15個(gè)問(wèn)題中的14個(gè)，其中一個(gè)問(wèn)題（2015 P4）需要耗時(shí)3分鐘。

在實(shí)驗(yàn)中，吳方法要么幾乎立即解決問(wèn)題，要么在5分鐘內(nèi)使筆記本內(nèi)存耗盡。

值得一提的是，研究者通過(guò)吳方法解決的15個(gè)問(wèn)題中的2個(gè)（2021 P3, 2008 P1B），原本是AlphaGeometry難以解決的5個(gè)問(wèn)題之中的2個(gè)。

因此，通過(guò)簡(jiǎn)單地將Wu的方法與AlphaGeometry結(jié)合，實(shí)現(xiàn)了在IMO-AG-30基準(zhǔn)上解決了27個(gè)問(wèn)題，這一成就在圖1的綠色/橙色條形（Wu&AG）中有所展示。

代數(shù)方法攻克IMO

代數(shù)方法，在自動(dòng)化幾何推理中解決IMO幾何問(wèn)題中，蘊(yùn)藏著巨大的潛力。

這項(xiàng)研究恰恰印證了這一點(diǎn)，吳方法也從過(guò)往能夠解決10個(gè)問(wèn)題，增加到了15個(gè)問(wèn)題。

而這些問(wèn)題中，有幾個(gè)對(duì)于目前流行的合成方法，以及增強(qiáng)LLM的方法，也具有非常高的挑戰(zhàn)性。

研究者表示，其設(shè)立的符號(hào)基線，是首個(gè)在性能上超越一般IMO參賽者，并接近銀牌水平。

此外，AlphaGeomtery和吳方法結(jié)合的系統(tǒng)，也是首個(gè)在IMO幾何問(wèn)題上超越人類金牌得主的AI系統(tǒng)。

這一成就證明了，代數(shù)方法與合成方法在這一領(lǐng)域的互補(bǔ)性。特別是，2008 P1B和2021 P3這兩個(gè)問(wèn)題目前僅有吳方法能解決，顯示了代數(shù)方法的獨(dú)特價(jià)值。

圖片

盡管代數(shù)方法以其理論保證而著稱，但之前因速度慢和難以為人理解而受到質(zhì)疑。

而最新的研究觀察顯示，吳方法在多個(gè)問(wèn)題上的效率遠(yuǎn)超預(yù)期，作者認(rèn)為不應(yīng)僅因其無(wú)法生成人類可讀的證明而忽視它。

目前，研究還在進(jìn)行中，受限于現(xiàn)有實(shí)現(xiàn)的不足，包括結(jié)構(gòu)的限制和性能不佳。

研究者相信，傳統(tǒng)方法有可能超越AlphaGeometry的證明能力，并希望這份研究能促進(jìn)這一領(lǐng)域經(jīng)典計(jì)算方法軟件的改進(jìn)。

另一方面，最新方法取得的顯著成功表明，盡管IMO幾何問(wèn)題對(duì)人類具有挑戰(zhàn)性，但可能并未充分挑戰(zhàn)現(xiàn)代計(jì)算求解器的極限。

解題的成功更多依賴于，重復(fù)使用人定義的啟發(fā)式方法和有限的構(gòu)造，而不是深入探索復(fù)雜的組合可能性。

這與國(guó)際象棋殘局的情況類似，其相對(duì)較早就被暴力求解器掌握了。

而研究人員希望這份研究，能激勵(lì)開(kāi)發(fā)幾何領(lǐng)域自動(dòng)定理證明器的新基準(zhǔn)。

參考資料：

https://arxiv.org/abs/2404.06405