在新的數(shù)學(xué)證明中，人工智能取勝

來源：ScienceAI
本文約2000字，建議閱讀9分鐘
一個以 AlphaGo 等人工智能系統(tǒng)為原型的新計(jì)算機(jī)程序解決了組合學(xué)和圖論中的幾個未解決問題。

去年 3 月，愛荷華州立大學(xué)（Iowa State University）的數(shù)學(xué)家 Leslie Hogben 和 Carolyn Reinhart 收到了一個驚喜。特拉維夫大學(xué)的博士后研究員 Adam Wagner 通過電子郵件告訴他們，他已經(jīng)回答了他們一周前發(fā)表的一個問題——盡管不是通過任何通常的數(shù)學(xué)或蠻力計(jì)算技術(shù)。相反，他使用了游戲機(jī)。

論文鏈接：https://arxiv.org/pdf/2103.00647.pdf

「我很高興這個問題得到了回答。很高興 Adam 用 AI 做到了這一點(diǎn)?！笻ogben 說。

Hogben 和 Reinhart 的問題是 Wagner ?使用人工智能解決的四個問題之一。雖然 AI 以前對數(shù)學(xué)做出了貢獻(xiàn)，但 Wagner 對它的使用卻不同尋常：他將尋找 Hogben 和 Reinhart 問題的解決方案變成了一種競賽，使用了其他研究人員在國際象棋等流行策略游戲中成功應(yīng)用過的方法。

「我看到了很多關(guān)于 DeepMind 這樣的公司的文章，他們創(chuàng)建了這些程序，可以在真正超人的水平下玩國際象棋、圍棋和 Atari 游戲，」Wagner 說?！肝蚁?，如果你能以某種方式使用這些自學(xué)習(xí)算法，這些強(qiáng)化學(xué)習(xí)算法，并找到一種在數(shù)學(xué)中使用它們的方法，那該多好？」

Wagner 開始嘗試使用類似的策略來提出反例——與數(shù)學(xué)假設(shè)相矛盾（或「反」）的例子，從而證明它是錯誤的。他將尋找反例重新想象成一場猜謎游戲，然后在數(shù)十個開放的數(shù)學(xué)問題上嘗試了他的程序。

「我真的認(rèn)為這是一項(xiàng)非常漂亮的工作?！瓜つ岽髮W(xué)教授 Geordie Williamson 說，他也將機(jī)器學(xué)習(xí)與數(shù)學(xué)研究相結(jié)合。

機(jī)器學(xué)習(xí)程序「教」計(jì)算機(jī)特定的能力。強(qiáng)化學(xué)習(xí)模型——Wagner 和 DeepMind 都使用的類型——對指令采取不干涉的方法，讓計(jì)算機(jī)反復(fù)練習(xí)一項(xiàng)任務(wù)（如游戲）。該模型只是為了評估計(jì)算機(jī)的工作而進(jìn)行干預(yù)。作為回應(yīng)，計(jì)算機(jī)會在了解哪些方法會導(dǎo)致更好的分?jǐn)?shù)時調(diào)整其策略。

強(qiáng)化學(xué)習(xí)已被證明是在復(fù)雜策略游戲中訓(xùn)練模型的有效方法。Wagner 將其應(yīng)用于數(shù)學(xué)研究的愿景非常簡單。

要了解如何使用強(qiáng)化學(xué)習(xí)來發(fā)現(xiàn)反例，考慮一下這個場景。假設(shè)有一個數(shù)學(xué)猜想，預(yù)測表達(dá)式 2x – x^2 對于 x 的任何實(shí)數(shù)值都是負(fù)的。這個猜想是不正確的——你可以通過產(chǎn)生一個 x 的值（一個反例）來證明它是錯誤的。（0 到 2 之間的任何數(shù)字都是反例，2x – x^2 的值在 x = 1 處達(dá)到峰值。）

為了使用強(qiáng)化學(xué)習(xí)做到這一點(diǎn)，Wagner 可能會讓他的模型在一個由猜測實(shí)數(shù) x 組成的游戲中自由發(fā)揮。玩完游戲之后，模型會收到它的分?jǐn)?shù)：2x – x^2 的值。最初，由于不知道什么數(shù)字可以使分?jǐn)?shù)最大化，該模型會瘋狂地猜測。但是一旦模型玩了足夠多的時間，一個模式就會變得明顯：x 越接近 1，得分越高。通過遵循這種模式，模型一旦猜到 0 到 2 之間的數(shù)字，就不可避免地會遇到反例。

Wagner 將相同的基本方案應(yīng)用于數(shù)十個問題，只是改變了計(jì)算機(jī)允許進(jìn)行的分?jǐn)?shù)和移動類型。所有的問題都來自離散數(shù)學(xué)，它處理分離和不同的對象——想想整數(shù)，而不是連續(xù)的數(shù)軸。

問題的離散性使 Wagner 更容易建立模型。例如，Richard Brualdi 和 Lei Cao 在 2020 年提出了一個關(guān)于矩陣的問題，其數(shù)值為 0 。計(jì)算機(jī)可以通過循環(huán)遍歷每個可用點(diǎn)并選擇 0 或 1。

「所有這些游戲都只是有限決策的有限序列，」Wagner 說。（允許無限多步驟的游戲會引入新的復(fù)雜性。）

Brualdi 和 Cao 的問題涉及一組特定的 0-1 矩陣，他們稱之為 312 模式避免（312-pattern avoiding），參考 3 x 3，「312 矩陣」，它表示混合三維向量的元素，使（a ,b,c) 變?yōu)?(c,a,b)。0-1 矩陣是 312 模式，如果無法刪除它的一些行和列并最終得到 312 矩陣，則可以避免。

更具體地說，Brualdi 和 Cao 的問題是關(guān)于矩陣的一個屬性，稱為「permanent」（積和式），這是一個通過復(fù)雜公式獲得的數(shù)字，該公式涉及所有矩陣項(xiàng)的相加和相乘。他們想知道哪些 312 模式避免矩陣的「permanent」值最大，以及「permanent」值可能達(dá)到多大，從而對任意大小的方陣進(jìn)行猜測。

為了回答他們的問題，Wagner 為他的模型設(shè)計(jì)了一個游戲：猜一個 0-1 矩陣。一項(xiàng)接著一項(xiàng)，它選擇 0 或 1?！竝ermanent」值越大，模型的分?jǐn)?shù)越高，因?yàn)闆]有避開 312 矩陣而被扣分。一旦矩陣為 4 x 4 或更大，該模型就會發(fā)現(xiàn)擊敗 Brualdi 和 Cao 猜測的示例。

這項(xiàng)新工作是一個令人興奮的概念證明，盡管到目前為止它對數(shù)學(xué)的實(shí)際貢獻(xiàn)并不大。

「 [模型解決的問題] 都不是超級重要的猜想?！筗agner 說。

在數(shù)學(xué)研究的許多重要方面，計(jì)算機(jī)仍然無法與人腦的能力相匹敵。在試圖反駁新論文的一個猜想時，Wagner 的模型碰壁了。它的計(jì)算能力太少，無法自行找到反例。盡管如此，它還是產(chǎn)生了一系列猜測，使 Wagner 自己很容易找到一個。

Wagner 說：「只要看看它構(gòu)建的最好的東西，如果你把它帶到任何數(shù)學(xué)家那里，它不一定是圖論家，你應(yīng)該嘗試的東西是非常明顯的?！?/span>

即使對于 Brualdi 和 Cao 的示例，一旦矩陣變得太大，模型也需要一點(diǎn)幫助。

在數(shù)學(xué)家將他們的領(lǐng)域讓給機(jī)器之前，如果有的話，還需要很長時間。與此同時，那些想要利用人工智能的人需要睜大眼睛尋找將其納入研究的機(jī)會。Williamson 說，這就是其他新技術(shù)（例如電力）最終揭示其潛力的方式，他認(rèn)為人工智能沒有理由與眾不同。

「我們沒有發(fā)現(xiàn)問題，然后說，[我們必須用電來解決這個問題。] 我們更多的是在說，[我們能做哪些簡單的小事？] 」

https://www.quantamagazine.org/in-new-math-proofs-artificial-intelligence-plays-to-win-20220307/

編輯：黃繼彥

校對：林亦霖