幾十年數(shù)學(xué)難題被谷歌研究員意外突破！曾因不想搞數(shù)學(xué)自學(xué)編程 今日熱議

詹士 蕭簫 發(fā)自 凹非寺

量子位 | 公眾號 QbitAI

困擾學(xué)界幾十年的集合難題，竟被圈外人一個月搞定？？？

(相關(guān)資料圖)

是的，你沒看錯。

當(dāng)事人Justin Gilmer，畢業(yè)已7年，目前是谷歌研究員，于數(shù)學(xué)界并無名頭，連其導(dǎo)師也并不看好他所做的研究，以至于成果發(fā)表后——

牛津、普林斯頓等高等學(xué)研機構(gòu)數(shù)學(xué)家們看到名字，紛紛好奇：

這人誰啊？

不僅身份引人好奇，其破題方法也不按圈內(nèi)常規(guī)路數(shù)，個中靈感來自通信祖師爺香農(nóng)的信息論。

這項開創(chuàng)性成果及幕后歷程剛被一些媒體介紹，在Reddit和Hacker News上引來不少網(wǎng)友熱議。

有網(wǎng)友表示：看到信息論在意想不到的領(lǐng)域應(yīng)用，真是酷炸了。

還有網(wǎng)友就著話題，秀了一把自己以信息論解決問題的經(jīng)歷。

所以，這位遠離純數(shù)學(xué)學(xué)術(shù)研究的大哥解決了什么問題？又如何在一個月內(nèi)搞定的？

往下看。

這個猜想究竟是什么？

這位谷歌研究員突破的難題，名叫union-closed sets conjecture（并封閉集合猜想）。

該猜想認為，對于一個包含至少2個集合的、對并運算封閉的有限集合族，至少存在一個元素，使得它在至少一半的集合里出現(xiàn)過。

我們來解讀一下這個猜想說的啥。

首先集合，就是包含了一系列元素的合集，這里面的元素既可以是數(shù)字，也可以是變量等。

例如這是一個我們常見的數(shù)集，而且是有限的（只包括3個元素）：

（至于無限數(shù)集，就像是自然數(shù)集、有理數(shù)集、整數(shù)集這種由無限個元素組成的集合）

當(dāng)然，集合也有集合，它們組合起來，就可以被叫做集族，例如下圖中F就是一個集族：

在這些集族中，有一類特殊的集族對并運算封閉。

對集族中的集合而言，并運算就是對兩個集合求并集；至于并運算封閉，即是指在對任意兩個集合進行并運算后，其結(jié)果仍然在這個集族中。

以下面這個集族為例：

無論是對、求并集，還是對、求并集，還是對、求并集……任意兩個集合求并集，其結(jié)果都會在這個集族中。

所以，上面這個集族就符合并封閉集合這一要求，而并封閉猜想也正是基于此而提出。

值得注意的是，這一猜想中的“一半”是緊致的，畢竟對于任何一個集合的子集族，所有的元素恰好在一半的集合里出現(xiàn)過。

它于1979年被一個叫Péter Frankl的數(shù)學(xué)家提出，所以也一度被叫做Frankl猜想。

看起來似乎不難，然而到實際解決時，一眾數(shù)學(xué)家才發(fā)現(xiàn)這并不簡單。

△Peter Winkler

達特茅斯學(xué)院數(shù)學(xué)教授Peter Winkler曾經(jīng)在1987年就這個猜想給出尖銳的評價：

并封閉集合猜想確實很有名，除了它的起源和它的答案。

△對此有同行表示，起源至少沒答案難orz

為了解決這個問題，數(shù)學(xué)家們也已經(jīng)嘗試過不少方法。

例如有人試著給猜想加上一些限制條件，讓它在這些情況下成立。

像是將它和圖論中的二分圖（Bipartite Graph）聯(lián)系起來，證明具備其中某種性質(zhì)的集族，在這個猜想的條件下成立。

又或是給其中的元素加以限制，再加以證明……

BUT，無論是哪種方法，距離真正需要證明的猜想都還差不少距離。

來自哥倫比亞大學(xué)的助理教授Will Sawin對此評價稱：

它看起來似乎是個不難解決的東西，畢竟長得和那種“容易解決的問題”很像。

然而，如今卻沒有任何一個證明能真正搞定它。

問題就這樣進度緩慢，直到2022年秋天，谷歌研究員Justin Gilmer借著朋友結(jié)婚的契機，回到了羅格斯大學(xué)校園。

用信息論突破了1%

Gilmer回母校的時間是2022年10月，此時距他畢業(yè)離開數(shù)學(xué)學(xué)術(shù)圈，已過去7年。這些年來，他自覺無心專注純數(shù)學(xué)領(lǐng)域，轉(zhuǎn)而自學(xué)編程，投身了IT行業(yè)。

此次返校，他拜訪了導(dǎo)師薩克斯，還四處轉(zhuǎn)了轉(zhuǎn)。

就在散步中，他突然回憶起——當(dāng)年自己徘徊于校園小徑，苦苦思索的一個數(shù)學(xué)問題：

沒錯，就是那個對“并封閉集合猜想”的證明。

讀博期間，Gilmer絞盡腦汁，花了一整年時間卻毫無進展，只是搞明白了為什么這一看似簡單的問題難以解決。

為此，他還去找過導(dǎo)師薩克斯。但導(dǎo)師也曾在該問題上停滯不前，因而他既不看好Gilmer的研究，也不愿重新碰這一領(lǐng)域。據(jù)Gilmer回憶，當(dāng)時導(dǎo)師差點把他趕出房間。

但現(xiàn)在，重回校園轉(zhuǎn)一圈的Gilmer有了個新想法：用信息論及相關(guān)原理解決并封閉猜想問題。

△ 信息論奠基人 克勞德?香農(nóng)

信息論發(fā)源于20世紀(jì)上半葉，其最為出名的論文是香農(nóng)在1948年發(fā)表的《通信的數(shù)學(xué)原理》，其中提出以“消除不確定性”的多少，來評價通信過程中的信息量大小。

這個不確定性要怎么理解呢？

以擲硬幣游戲為例，假設(shè)我們需要擲5次硬幣，然后輸出結(jié)果序列，每次結(jié)果為1比特。

如果現(xiàn)在我們拋擲的是一枚普通硬幣（正反概率各50%），那么我們至少需要5個比特來傳遞信息。

但如果給這枚硬幣做點手腳（讓它正面朝上的概率99%），我們就完全可以提前規(guī)定，在硬幣5次都是正面朝上時，只用1個比特來傳遞信息。

這樣，被用以衡量文本、圖片等內(nèi)容大小的比特，也能成為描述事件發(fā)生不確定性的信息熵單位，而信息論也成為現(xiàn)代通信奠基之作，構(gòu)建起今日的信息社會。

受到信息論的啟發(fā)，Gilmer決心下場再戰(zhàn)。

此后一個月中，他利用下班后的晚上及周末時間，試探性地進行了摸索。有意思的是，由于長時間未接觸理論，他一邊研究還一邊拿著本信息論教科書，以備隨時查閱。

研究過程中，Gilmer還發(fā)現(xiàn)自己研究的問題并非無人關(guān)心，其實幾年前，就有幾位數(shù)學(xué)家在菲爾茲獎得主Tim Gowers博客里探討過該問題。這讓他有了更多信心。

△ Tim Gowers博客的相關(guān)研究內(nèi)容

Gilmer的思路是找反例。

根據(jù)并封閉集合猜想，一個正常的并封閉集族中，至少應(yīng)該有一個元素在多于一半的集合中出現(xiàn)。

既然如此，只要想辦法構(gòu)造一個特殊的集族，里面沒有一個元素出現(xiàn)在超過1%的集合中，這個猜想就會被證偽，反之如果構(gòu)造不出來，那么猜想就可能成立。

現(xiàn)在，我們用信息論視角看這一猜想：

正常來說，如果從集族中任意挑出兩個集合，這兩個集合取并集后，并集中的元素比原來兩個集合更多，其信息熵應(yīng)該比原來的單獨兩個集合更低。

然而如果基于“沒有一個元素出現(xiàn)在超過1%集合”這個限制條件，任意兩個集合取并集后，計算出來的信息熵竟然比原來的單獨兩個集合更高。

這顯然是不可能的，因此不存在這么一個特殊的集族，Glimer的反例也沒有找到。

但這也就意味著在“并封閉”集族中，至少存在一個元素，會出現(xiàn)在超過1%的集合中。

2022年11月16日，Gilmer將這一思路寫成論文，發(fā)表在了arXiv上。

當(dāng)然，他這篇論文還不是“完全體”，也就是說并沒有完全證明并封閉集合猜想——

畢竟這只是至少1%，還不意味著原來的并封閉集合猜想中的至少50%就成立。

但這個新思路已經(jīng)足夠讓學(xué)界震動。

普林斯頓大學(xué)數(shù)學(xué)家Ryan Alweiss評價“引入信息量”這一操作：非常聰明。

僅僅幾天后，就有3個不同的數(shù)學(xué)研究組基于他的研究，先后發(fā)表了研究論文，隨后也有更多研究者跟進，他們所在院校機構(gòu)有牛津、普林斯頓、哥大、布里斯托等。

在后續(xù)研究中，對“并封閉集合猜想”的概率值證明，被推進到了38%。

令這些數(shù)學(xué)家好奇的是，基于Gilmer的研究，他自己上手將概率值推進到38%并不難。

對此，Gilmer表示，自己已經(jīng)五年多沒碰數(shù)學(xué)了，確實不知道如何進行分析工作來將其進一步推進下去。

不過，他也認為，正是因為對相關(guān)數(shù)學(xué)方法的生疏，讓他跳出了常理，用圈外辦法取得突破。

深度學(xué)習(xí)界的萬引大佬

雖說此前在數(shù)學(xué)界沒什么名頭，Justin Gilmer也并非等閑之輩。

他任職于谷歌大腦團隊，Google Scholar上引用破萬，主要研究方向為深度學(xué)習(xí)、組合型、隨機圖論。

從其研究成果看，Justin Gilmer主攻圖神經(jīng)網(wǎng)絡(luò)，高引論文涉及：消息傳遞神經(jīng)網(wǎng)絡(luò)（MPNN）、關(guān)系歸納偏差與圖神經(jīng)網(wǎng)絡(luò)、顯著圖等領(lǐng)域。

上述研究中，最高引用數(shù)為4789，標(biāo)題為：Neural Message Passing for Quantum Chemistry。

該文定義了一種圖上監(jiān)督學(xué)習(xí)框架，消息傳遞神經(jīng)網(wǎng)絡(luò)（MPNN），并將其應(yīng)用于分子特性預(yù)測上。

以量子化學(xué)為例，該框架根據(jù)原子性質(zhì)（對應(yīng)節(jié)點特征）和分子結(jié)構(gòu)（對應(yīng)邊特征）預(yù)測了13種物理化學(xué)性質(zhì)。

這一成果在領(lǐng)域內(nèi)影響深遠，騰訊AI Lab的云深智藥平臺，其框架之一也基于MPNN改進發(fā)展而來。

另值得一提的是，Justin Gilmer還到過中國北京，2007年夏天他在微軟亞研短暫呆過3個月。

根據(jù)其領(lǐng)英賬號，Gilmer當(dāng)時在一個4人團隊，參與構(gòu)建SVM分類器，用于識別句子中人名、地名、機構(gòu)名等各命名實體之間的關(guān)系。

關(guān)鍵詞： 幾十年數(shù)學(xué)難題被谷歌研究員意外突破曾因不想搞數(shù)學(xué)自學(xué)編程