幾十年數(shù)學(xué)難題被谷歌研究員意外突破！曾因不想搞數(shù)學(xué)自學(xué)編程，當(dāng)年差點(diǎn)被導(dǎo)師趕出門

詹士 蕭簫 發(fā)自 凹非寺
量子位 | 公眾號(hào) QbitAI

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

是的，你沒(méi)看錯(cuò)。

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

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

這人誰(shuí)啊？

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

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

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

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

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

往下看。

這個(gè)猜想究竟是什么？

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

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

我們來(lái)解讀一下這個(gè)猜想說(shuō)的啥。

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

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

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

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

在這些集族中，有一類特殊的集族對(duì)并運(yùn)算封閉。

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

以下面這個(gè)集族為例：

無(wú)論是對(duì){1}、{1,2}求并集，還是對(duì){2,3,4}、{1}求并集，還是對(duì){1,2}、{2,3,4}求并集……任意兩個(gè)集合求并集，其結(jié)果都會(huì)在這個(gè)集族中。

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

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

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

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

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

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

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

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

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

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

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

來(lái)自哥倫比亞大學(xué)的助理教授Will Sawin對(duì)此評(píng)價(jià)稱：

它看起來(lái)似乎是個(gè)不難解決的東西，畢竟長(zhǎng)得和那種“容易解決的問(wèn)題”很像。

然而，如今卻沒(méi)有任何一個(gè)證明能真正搞定它。

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

用信息論突破了1%

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

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

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

沒(méi)錯(cuò)，就是那個(gè)對(duì)“并封閉集合猜想”的證明。

讀博期間，Gilmer絞盡腦汁，花了一整年時(shí)間卻毫無(wú)進(jìn)展，只是搞明白了為什么這一看似簡(jiǎn)單的問(wèn)題難以解決。

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

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

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

這個(gè)不確定性要怎么理解呢？

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

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

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

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

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

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

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

Gilmer的思路是找反例。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

他任職于谷歌大腦團(tuán)隊(duì)，Google Scholar上引用破萬(wàn)，主要研究方向?yàn)樯疃葘W(xué)習(xí)、組合型、隨機(jī)圖論。

從其研究成果看，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ù)測(cè)上。

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

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

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

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

參考鏈接：
[1]https://www.quantamagazine.org/long-out-of-math-an-ai-programmer-cracks-a-pure-math-problem-20230103/
[2]https://news.ycombinator.com/item?id=34236889
[3]https://mp.weixin.qq.com/s/lj-jTonC2sqwWKgZZBXVVw
[4]https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.081/Henning/UCSurvey.pdf