困擾數(shù)學(xué)家25年的“切蘋果”難題，被一位華人統(tǒng)計(jì)學(xué)博士解決了
與計(jì)算機(jī)隨機(jī)采樣問題有關(guān)
邊策 楊凈 發(fā)自 凹非寺?量子位 報(bào)道 | 公眾號(hào) QbitAI
請(qǐng)聽題：
如何將蘋果平均一分為二，還能保證它長(zhǎng)時(shí)間的新鮮？
這是一個(gè)嚴(yán)肅的科學(xué)問題，已經(jīng)困擾了人類數(shù)學(xué)家25年之久。
根據(jù)常識(shí)，就是要保證果肉暴露在外面的面積最小，也就是切片的面積最小。如果跨越到更高的維度，是否依然成立？
這就是1995年，由三位數(shù)學(xué)家提出的一個(gè)幾何學(xué)猜想。
現(xiàn)在，這個(gè)難題被一位華人統(tǒng)計(jì)學(xué)博士，解決了。
成果一經(jīng)發(fā)布，就迅速引起了數(shù)學(xué)、理論計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)等多個(gè)領(lǐng)域的科學(xué)家的關(guān)注。
他們一致認(rèn)為，數(shù)學(xué)大師、菲爾茲獎(jiǎng)得主，原本猜想的提出者Jean Bourgain（讓·布爾甘）一定會(huì)對(duì)這一進(jìn)展感到興奮。
畢竟，在他去世前（2018年）的幾個(gè)月里還在關(guān)心這一問題進(jìn)展，但終其一生都未能解決。
困擾數(shù)學(xué)家25年的幾何問題
1984年，著名數(shù)學(xué)家讓·布爾甘提出了一個(gè)猜想。
一個(gè)任意維度的凸體，用低一維的平面去平分，那么存在一個(gè)常數(shù)c，讓凸體至少存在一個(gè)切面的面積大于c。
換句話說，如果你一刀平分“任意維度空間的西瓜”，隨便你怎么劈，總有一個(gè)切面總大于c。
（Ps：以往的科學(xué)家用的是蘋果的例子。但準(zhǔn)確來說不能選蘋果，因?yàn)樘O果上下是凹的。）
在3維空間中，這個(gè)結(jié)論似乎很好理解，因?yàn)闊o論西瓜長(zhǎng)成什么奇形怪狀，總不可能在每個(gè)角度都細(xì)長(zhǎng)。
像下面這樣的長(zhǎng)西瓜，豎直切下去，切面很小，可以你也可以水平切開平分它，這樣切面就會(huì)很大。
但在3維世界中正確的事情，到了高維空間卻不一定成立。
這個(gè)問題后來被布爾甘自己證明，但數(shù)學(xué)家們并不滿足于用平面切西瓜，而是希望能找到一個(gè)更小的切面，它可以是曲面。
而這恰好是1995年Kannan、Lovász和Simonovits三人提出的KLS猜想關(guān)心的問題：用來平分的最小曲面面積是多少？
以二維空間里的一個(gè)三角形為例。
這個(gè)最小的“曲面”是一段圓弧。用圓弧來平分一個(gè)三角形，中間的線長(zhǎng)度最短，而最佳“平面”——直線——的效果略差。
△?如何用最小“切面”平分三角形（來源：Quanta Magazine）
到了更高維度的空間中，二等分的最佳平面和最佳曲面差距會(huì)變大嗎？切面的面積是否和維度d有關(guān)？
這個(gè)問題已經(jīng)不再是純粹的數(shù)學(xué)問題。
普林斯頓大學(xué)數(shù)學(xué)系教授Assaf Naor表示，KLS猜想在純粹的數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)中都很重要。
KLS猜想的結(jié)果，直接關(guān)系到隨機(jī)行走算法的運(yùn)行時(shí)間，如機(jī)器學(xué)習(xí)模型中采樣問題。
所以最后解決這個(gè)幾何問題的學(xué)者，都并非幾何學(xué)的專家，而是來自計(jì)算機(jī)界。
用統(tǒng)計(jì)方法解決他
經(jīng)過數(shù)學(xué)家的抽象，KLS猜想就像一個(gè)封裝著氣體的容器，找到最佳切面就是尋找容器的“瓶頸”。
想象一個(gè)啞鈴形狀的容器，里面有一個(gè)氣體分子在隨機(jī)運(yùn)動(dòng)，啞鈴中間連接部分越細(xì)，分子就越難跑到另一側(cè)。
△啞鈴形的平分切面很?。▉碓矗篩in Tat Lee論文）
現(xiàn)在人們想知道，在高維空間，這個(gè)凸的容器最細(xì)的地方有多細(xì)。（當(dāng)然，啞鈴并非是凸的。）
2012年，Eldan通過引入一種稱為隨機(jī)定位的技術(shù)，來降低這個(gè)問題與維度上界。（到底是維度d的幾次冪。）
2015年末，華盛頓大學(xué)的Vempala和Yin Tat Lee改進(jìn)了Eldan的隨機(jī)定位，以進(jìn)一步將KLS因子（用于描述瓶頸是否存在）降低到維度的四次根d1/4。
△?KLS猜想的上界不斷降低（來源：同上）
甚至，他們還將冪指數(shù)降低到幾乎為0，由于d的0次冪總是等于1，Lee和Vempala似乎證明了KLS因子是一個(gè)與維度無關(guān)的常數(shù)。
他們?cè)赼rXiv上發(fā)布了他們的論文。但是幾天后，這篇文章就被人發(fā)現(xiàn)了一個(gè)缺陷，他們關(guān)于d0的證明是錯(cuò)的。
之后，二人修改了文章，把界限重新調(diào)整到d1/4。幾年來，研究人員認(rèn)為KLS猜想的探索已經(jīng)到此終結(jié)了。
不過他們還在論文中，保留了d0證明的一些想法。這也為后來的突破埋下伏筆。
他們的論文引起了另一位統(tǒng)計(jì)學(xué)者Yuansi Chen的注意。
Chen當(dāng)時(shí)是加州大學(xué)伯克利分校的統(tǒng)計(jì)學(xué)研究生，他正在研究隨機(jī)采樣方法的混合率。而隨機(jī)抽樣是許多類型統(tǒng)計(jì)推斷中的關(guān)鍵，例如貝葉斯統(tǒng)計(jì)。
Chen深入研究文學(xué)，花了數(shù)周時(shí)間試圖填補(bǔ)Lee和Vempala的證明中的空白，但依然沒有解決。
于是他轉(zhuǎn)變了思路，在Lee和Vempala的思想指導(dǎo)下，他找到了一種方法，采用遞歸來降低KLS因子上界。
經(jīng)過反復(fù)迭代，這種方法將KLS猜想問題再次拉回到d0的上界。
這一結(jié)果意味著，高維凸形物體不會(huì)有啞鈴那樣的結(jié)構(gòu)。
該定理的結(jié)果意味著，在n維凸體中隨機(jī)行走，遍歷整個(gè)圖形的速度比我們之前預(yù)想得要快得多。
這將有助于計(jì)算機(jī)科學(xué)家對(duì)不同的隨機(jī)采樣算法進(jìn)行優(yōu)先級(jí)排序。
三個(gè)計(jì)算機(jī)相關(guān)的科學(xué)家
雖然表面看上去，這三位學(xué)者似乎跟數(shù)學(xué)沒什么關(guān)系。
但仔細(xì)翻看他們的履歷，他們都曾跟數(shù)學(xué)結(jié)下了不小的緣分。
首先，直接與研究相關(guān)的這位統(tǒng)計(jì)學(xué)博士后——Yuansi Chen?（陳遠(yuǎn)思，音譯）。
今年年初，他開始在杜克大學(xué)統(tǒng)計(jì)科學(xué)系擔(dān)任助理教授的職位。
主要研究方向是統(tǒng)計(jì)機(jī)器學(xué)習(xí)、優(yōu)化以及在神經(jīng)科學(xué)中的應(yīng)用，尤其對(duì)其中域適應(yīng)性、穩(wěn)定性、MCMC采樣算法、卷積神經(jīng)網(wǎng)絡(luò)和計(jì)算神經(jīng)科學(xué)中出現(xiàn)的統(tǒng)計(jì)問題感興趣。
2019年，他在加州大學(xué)伯克利分校統(tǒng)計(jì)系獲得博士學(xué)位。
其博士生導(dǎo)師是著名華裔統(tǒng)計(jì)學(xué)家、UC伯克利統(tǒng)計(jì)系和電子工程與計(jì)算機(jī)科學(xué)系終身教授郁彬。
在攻讀博士之前，他還在法國(guó)Ecole Polytechnique獲得了應(yīng)用數(shù)學(xué)專業(yè)的工程師文憑。
隨后，前往在蘇黎世聯(lián)邦理工學(xué)院ETH Foundations of Data Science（ETH-FDS）做博士后研究。
而啟發(fā)Yuansi Chen數(shù)學(xué)靈感的，是兩位計(jì)算機(jī)科學(xué)家。
Yin Tat Lee?（李賢達(dá)，音譯）和Santosh S. Vempala。
李賢達(dá)，目前是華盛頓大學(xué)助理教授，本科畢業(yè)于香港中文大學(xué)。
2012年從港中文大學(xué)畢業(yè)后，前往麻省理工學(xué)院攻讀博士學(xué)位，隨后前往微軟研究院做博士后研究。
他的研究方向主要在算法方面，包括凸優(yōu)化、凸幾何、譜圖理論和在線算法等廣泛的課題。
以往的研究里，他曾結(jié)合連續(xù)數(shù)學(xué)和離散數(shù)學(xué)的思想，大幅提升了在計(jì)算機(jī)科學(xué)和優(yōu)化中許多基本問題的算法，比如線性編程和最大流量問題。
他曾獲得SODA最佳論文獎(jiǎng)、NeurIPS 2018最佳論文獎(jiǎng)、NSF職業(yè)獎(jiǎng)。
去年他還獲得了有“諾獎(jiǎng)風(fēng)向標(biāo)”之稱的斯隆獎(jiǎng)，以及美國(guó)最大的非政府獎(jiǎng)學(xué)金之一——帕卡德獎(jiǎng)學(xué)金。
再來看Santosh S. Vempala，佐治亞理工學(xué)院計(jì)算機(jī)科學(xué)教授。
主要研究領(lǐng)域是理論計(jì)算機(jī)科學(xué)，還抽樣、學(xué)習(xí)、優(yōu)化和數(shù)據(jù)分析的算法工具；隨機(jī)線性代數(shù)，高維幾何。
他曾在卡內(nèi)基梅隆大學(xué)攻讀博士學(xué)位，本科畢業(yè)于印度理工學(xué)院的計(jì)算機(jī)專業(yè)，曾獲NSF職業(yè)獎(jiǎng)、斯隆獎(jiǎng)等獎(jiǎng)項(xiàng)。
在來到佐治亞理工學(xué)院之前，他曾擔(dān)任MIT應(yīng)用數(shù)學(xué)系擔(dān)任教授、UC伯克利米勒研究員。
數(shù)學(xué)家：不可思議
隨著陳遠(yuǎn)思論文一發(fā)布，迅速就引起了數(shù)學(xué)界的學(xué)者關(guān)注。
不光是因?yàn)榇饲暗腻e(cuò)誤證明，還由于陳遠(yuǎn)思這個(gè)名字在數(shù)學(xué)界十分陌生，研究人員對(duì)待這一成果十分謹(jǐn)慎。
但他的方法很容易被驗(yàn)證。
早期研究過KLS猜想的以色列數(shù)學(xué)家BoázKlartag，就在第一時(shí)間看了論文。
我基本上立即停止了我正在做的一切事情，并檢查了這篇論文。
這篇論文是100%正確的，這一點(diǎn)毫無疑問。
除了一眾數(shù)學(xué)家關(guān)注之外，還引起了理論數(shù)學(xué)家、統(tǒng)計(jì)學(xué)等領(lǐng)域的注意。
哈佛大學(xué)計(jì)算機(jī)科學(xué)教授、微軟研究院前新英格蘭首席研究員Boaz Barak則發(fā)推祝賀。
并表示這是一個(gè)非常重要的突破，加速了對(duì)近似凸體體積的研究。
但點(diǎn)贊祝賀之余，也有不少學(xué)者表示十分遺憾。
因?yàn)樘岢鲞@一猜想的人菲爾茲獎(jiǎng)得主布爾甘已于2018年去世，如果他還在的話，一定會(huì)為這一進(jìn)展感到興奮。
據(jù)QuantaMagazine報(bào)道，布爾甘曾在去世前幾個(gè)月，聯(lián)系了他的朋友、特拉維夫大學(xué)教授Vitali Milman，詢問這一猜想是否有任何進(jìn)展，想在離開之前知道答案。
但Vitali Milman說，布爾甘在這一問題上，花費(fèi)的時(shí)間和投入的精力比任何其他問題多得多。沒想到，最后這個(gè)問題卻被統(tǒng)計(jì)學(xué)解決了。
參考鏈接： [1] https://www.quantamagazine.org/statistics-postdoc-tames-decades-old-geometry-problem-20210301/ [2] https://www.cc.gatech.edu/~vempala/papers/kls_survey.pdf [3] https://arxiv.org/abs/2011.13661 [4] http://yintat.com/ [5] https://people.math.ethz.ch/~chenyua/ [6] https://www.cc.gatech.edu/news/604802/computer-scientists-make-kls-conjecture-breakthrough
版權(quán)所有，未經(jīng)授權(quán)不得以任何形式轉(zhuǎn)載及使用，違者必究。
相關(guān)閱讀
MIT數(shù)學(xué)最強(qiáng)本科生：2年半畢業(yè)，20多篇論文在手，還推動(dòng)了停滯幾十年的數(shù)學(xué)研究
師從MIT華裔教授，曾獲阿里巴巴數(shù)學(xué)競(jìng)賽銀獎(jiǎng)
十三2020-12-05
陶哲軒轉(zhuǎn)發(fā)、菲爾茲獎(jiǎng)得主領(lǐng)銜：AI正在顛覆數(shù)學(xué)家的工作方式 | 美國(guó)數(shù)學(xué)學(xué)會(huì)特刊
陶哲軒：“這個(gè)領(lǐng)域發(fā)展太快了”
夢(mèng)晨2024-04-08
