|
|
原标题：几十年数学困难被谷歌钻研员不测冲破！曾因不想搞数学自学编程，当年差点被导师赶出门
詹士 萧箫 发自 凹非寺
量子位 | 大众号 QbitAI
困扰学界几十年的聚拢困难，竟被圈外人一个月搞定？？？
是的，你没看错。
当事人Justin Gilmer，结业已7年，目前是谷歌钻研员，于数学界并没有名头，连其导师也其实不看好他所做的钻研，以致于效果颁发后——
牛津、普林斯顿等初等学研机构数学家们看到名字，纷纭猎奇：
此人谁啊？
iaemdbltldh.jpg
不只身份惹人猎奇， 其破题办法也不按圈内惯例路数，个中灵感来自通讯祖师爷香农的信息论。
这项创始性效果及幕后历程刚被一些媒体引见，在Reddit和Hacker News上引来不少网友热议。
xatihpsn14c.jpg
展开全文 有网友表现：看到信息论在乎想不到的畛域运用，真是酷炸了。
还有网友就着话题，秀了一把本人以信息论解决问题的阅历。
fvfkz0zk4u4.jpg
所以，这位阔别纯数学学术钻研的大哥解决了甚么问题？又如安在一个月内搞定的？
往下看。
这个料想到底是甚么？
这位谷歌钻研员冲破的困难，名叫 union-closed sets conjecture（并关闭聚拢料想）。
该料想以为，关于一个包孕最少2个聚拢的、对并运算关闭的无限聚拢族，最少存在 一个元素，使得它在 最少一半的聚拢里泛起过。
咱们来解读一下这个料想说的啥。
首先 聚拢，就是包孕了一系列元素的合集，这外面的元素既能够是数字，也能够是变量等。
例如这是一个咱们常见的数集，并且是 无限的 （只包罗3个元素）：
5zqzowfqpru.jpg
（至于有限数集，就像是天然数集、有理数集、整数集这类由有限个元素组成的聚拢）
固然，聚拢也有聚拢，它们组合起来，就能被叫做 集族，例如下图中F就是一个集族：
在这些集族中，有一类特殊的集族对 并运算关闭。
对集族中的聚拢而言， 并运算就是对两个聚拢求并集；至于并运算 关闭，便是指在对恣意两个聚拢进行并运算后，其后果依然在这个集族中。
下列面这个集族为例：
无论是对{1}、{1,2}求并集，仍是对{2,3,4}、{1}求并集，仍是对{1,2}、{2,3,4}求并集……恣意两个聚拢求并集，其后果都会在这个集族中。
所以，下面这个集族就合乎并关闭聚拢这一要求，而并关闭料想也恰是基于此而提出。
值得留意的是，这一料想中的“一半”是紧致的，毕竟关于任何一个聚拢的子集族，一切的元素刚好在一半的聚拢里泛起过。
它于1979年被一个叫Péter Frankl的数学家提出，所以也一度被叫做Frankl料想。
看起来似乎不难，但是到实际解决时，一众数学家才发现这其实不简略。
cizcg3b1dab.jpg
△Peter Winkler
达特茅斯学院数学传授Peter Winkler已经在1987年就这个料想给出锋利的评估：
并关闭聚拢料想的确颇有名， 除了它的发源和 它的谜底。
并关闭聚拢料想的确颇有名， 除了它的发源和 它的谜底。
为理解决这个问题，数学家们也曾经尝试过不少办法。
例如有人试着给料想加之一些限度前提，让它在这些状况下成立。
像是将它和图论中的二分图 （Bipartite Graph）分割起来，证实具备其中某种性质的集族，在这个料想的前提下成立。
又或是给其中的元素加以限度，再加以证实……
BUT，无论是哪一种办法，间隔真正需求证实的料想都还差不少间隔。
来自哥伦比亚大学的助理传授Will Sawin对此评估称：
它看起来似乎是个不难解决的货色，毕竟长得和那种“容易解决的问题”很像。
但是，如今却没有任何一个证实能真正搞定它。
它看起来似乎是个不难解决的货色，毕竟长得和那种“容易解决的问题”很像。
但是，如今却没有任何一个证实能真正搞定它。
问题就这样进度迟缓，直到2022年秋季，谷歌钻研员Justin Gilmer借着敌人结婚的契机，回到了罗格斯大学校园。
用信息论冲破了1%
Gilmer回母校的时间是2022年10月，此时距他结业分开数学学术圈，已过来7年。这些年来，他盲目无心专一纯数学畛域，转而自学编程，投身了IT行业。
此次返校，他造访了导师萨克斯，还到处转了转。
就在漫步中，他忽然回想起——当年本人徘徊于校园小径，苦苦思索的一个数学识题：
没错，就是阿谁对“并关闭聚拢料想”的证实。
读博期间，Gilmer绞尽脑汁，花了一整年时间却毫无停顿，只是搞明确了为何这一看似简略的问题难以解决。
为此，他还去找过导师萨克斯。但导师也曾在该问题上停滞不前，于是他既不看好Gilmer的钻研，也不肯从新碰这一畛域。据Gilmer回想，过后导师差点把他赶出房间。
但当初，重回校园转一圈的Gilmer有了个新设法：用信息论及相干原了解决并关闭料想问题。
tn3thvr1fwb.jpg
△信息论奠基人 克劳德?香农
信息论起源于20世纪上半叶，其最为知名的论文是香农在1948年颁发的《通讯的数学原理》，其中提出以“打消不肯定性”的多少，来评估通讯过程当中的信息量大小。
这个 不肯定性要怎么了解呢？
以掷硬币游戏为例，假定咱们需求掷5次硬币，而后输入后果序列，每次后果为1比特。
假如当初咱们抛掷的是一枚普通硬币 （正反几率各50%），那末咱们最少需求5个比特来传递信息。
但若给这枚硬币做点手脚 （让它侧面朝上的几率99%），咱们就彻底能够提前规则，在硬币5次都是侧面朝上时，只用1个比特来传递信息。
cwxbn3gplnn.jpg
这样，被用以权衡文本、图片等外容大小的比特，也能成为形容事情产生不肯定性的信息熵单位，而信息论同样成为古代通讯奠基之作，构建起今日的信息社会。
遭到信息论的启示，Gilmer信心下场再战。
尔后一个月中，他利用上班后的晚上及周末时间，摸索性地进行了试探。无意思的是，因为长期未接触实践，他一边钻研还一边拿着本信息论教科书，以备随时查阅。
钻研过程当中，Gilmer还发现本人钻研的问题并不是无人关怀，其实几年前，就有几位数学家在菲尔兹奖得主Tim Gowers博客里讨论过该问题。这让他有了更多决心。
△Tim Gowers博客的相干钻研内容
Gilmer的思绪是 找反例。
按照并关闭聚拢料想，一个正常的并关闭集族中，最少应该有一个元素在多于一半的聚拢中泛起。
既然如斯，只有想方法结构一个特殊的集族，外面没有一个元素泛起在超过1%的聚拢中，这个料想就会被证伪，反之假如结构不出来，那末料想就 可能成立。
当初，咱们用信息论视角看这一料想：
正常来讲，假如从集族中恣意挑出两个聚拢，这两个聚拢取并集后，并集中的元素比原来两个聚拢更多，其信息熵应该比原来的独自两个聚拢更低。
但是假如基于“没有一个元素泛起在超过1%聚拢”这个限度前提，恣意两个聚拢取并集后，计算出来的信息熵居然比原来的独自两个聚拢更高。
这显然是不成能的，因此不存在这么一个特殊的集族，Glimer的反例也没有找到。
但这也就象征着在“并关闭”集族中，最少存在一个元素，会泛起在超过1%的聚拢中。
2022年十一月16日，Gilmer将这一思绪写成论文，颁发在了arXiv上。
固然，他这篇论文还不是“彻底体”，也就是说并无彻底证实并关闭聚拢料想——
毕竟这只是 最少1%，还不料味着原来的并关闭聚拢料想中的 最少50%就成立。
但这个新思绪曾经足够让学界触动。
普林斯顿大学数学家Ryan Alweiss评估“引入信息量”这一操作：十分聪明。
仅仅几天后，就有3个不同的数学钻研组基于他的钻研，前后颁发了钻研论文，随后也有更多钻研者跟进，他们所在院校机构有牛津、普林斯顿、哥大、布里斯托等。
在后续钻研中，对“并关闭聚拢料想”的几率值证实，被推动到了38%。
nk5a5ojqsmq.jpg
令这些数学家猎奇的是，基于Gilmer的钻研，他本人上手将几率值推动到38%其实不难。
对此，Gilmer表现，本人曾经五年多没碰数学了，的确不知道如何进行剖析任务来将其进一步推动上来。
不外，他也以为，恰是由于对相干数学办法的陌生，让他跳出了常理，用圈外方法取得冲破。
深度学习界的万引大佬
虽然说此前在数学界没甚么名头，Justin Gilmer也并不是轻易之辈。
他任职于谷歌大脑团队，Google Scholar上援用破万，次要钻研标的目的为深度学习、组合型、随机图论。
从其钻研效果看，Justin Gilmer主攻图神经网络，高引论文波及：动静传递神经网络 （MPNN）、瓜葛归结偏差与图神经网络、明显图等畛域。
lo5yu5w3cgv.jpg
上述钻研中，最高援用数为4789，标题为：Neural Message Passing for Quantum Chemistry。
该文定义了一种图上监视学习框架，动静传递神经网络 （MPNN），并将其运用于份子特性预测上。
以量子化学为例，该框架按照原子性质 （对应节点特点）和份子构造 （对应边特点）预测了13种物理化学性质。
这一效果在畛域内影响深远，腾讯AI Lab的云深智药平台，其框架之一也基于MPNN改进开展而来。
wrutsvdazjs.jpg
另值得一提的是，Justin Gilmer还到过中国北京，2007年夏天他在微软亚研长久呆过3个月。
— 完—
「人工智能」、「智能汽车」微信社群邀你参加！
欢送关注人工智能、智能汽车的小火伴们参加交流群，与AI从业者交流、切磋，不错过最新行业开展&技术停顿。
PS. 加好友请务必备注您的姓名-公司-职位噢 ~
点这里 ?关注我，记得标星哦～
一键三连「分享」、「点赞」和「在看」
科技前沿停顿日日相见 ~ |
|
注册会员