黃志毅：沖向算法“險峰”最高“巖點”攀登者！

哪怕是沒有攀登的日子，香港大學（簡稱“港大”）計算機科學系副教授黃志毅的思緒也會圍繞著“巖點”——思考如何完美地調(diào)動指尖、腳掌、身體核心，想象動作的姿態(tài)與前后的銜接。熱愛攀巖，很大程度上因為這項運動與他從事的事業(yè)——理論計算機科學領域里不確定信息下的優(yōu)化問題研究有異曲同工之妙。

一面面陡峭的巖壁，就像一道道充滿挑戰(zhàn)的開放問題，都需要大腦和身體的密切配合，恰到好處地應用工具、審慎地規(guī)劃總結、針對性地攻克多個困難點。然后，在一次次的墜落懸停中，忍受挫敗、自我懷疑，提升情緒彈性、身體意志力和抵達終點的信念感；在種種不確定信息下，條分縷析、不斷試煉，以實現(xiàn)微妙的平衡與優(yōu)化，回應來自廣闊世界的真實需求。

▲黃志毅

2014年加入港大以來，憑借不懈努力，黃志毅已陸續(xù)解決了圖靈獎得主理查德·卡普（Richard Karp）提出的三十年開放問題（涵蓋智能出行、器官捐贈等應用），以及線上廣告中顯示廣告、廣告關鍵字兩個十幾年開放問題。迄今為止，他已發(fā)表40余篇頂會論文。2015年，他獲得算法和架構并行性年會（SPAA）最佳論文獎，是亞洲院校的首位獲獎者；2020年，他獲得計算機科學基礎年會（FOCS）最佳論文獎，是近14年來首次、亞洲院校第二位獲獎者。

無限風光在險峰，無限風光在前方。算法世界的攀登之旅從來沒有真正的終點。對黃志毅來說，攀登的妙處在于遍尋而得的完美路線、登臨之后的短暫喜悅，更在于歷經(jīng)艱辛觸摸最高“巖點”后繼續(xù)走向下一面未知峭壁的無畏勇氣，以及因此而錘煉出來的不斷開闊視野、不斷向上進取的蓬勃生命力。

向不確定的未知進發(fā)

對理論計算機科學家而言，每個平靜時刻都可能蘊藏著“頭腦風暴”。有時，周末坐在地上陪伴孩子玩游戲，黃志毅不知不覺就神游別處，回想起某個算法問題。對理論計算機科學的這種癡迷，還要從他十幾年前在清華大學（簡稱“清華”）“姚班”讀書的經(jīng)歷說起。

2004年，圖靈獎得主姚期智院士全職回到清華，講授計算機與科學技術系課程。其間，他萌生了創(chuàng)立“清華學堂計算機科學實驗班”的想法，并于次年通過選拔考試，正式組建了一個包括30名數(shù)學和計算機尖子生的班級，這便是第一屆“姚班”。黃志毅進入第一屆“姚班”時正讀大三。早前因在高中數(shù)學競賽中表現(xiàn)優(yōu)異，他被保送清華計算機系；之后又出于對數(shù)學和物理的興趣，上過學院“數(shù)理實驗班”的課程。這些無意中為他考入“姚班”打下了一定基礎。

“姚班”致力于培養(yǎng)與美國麻省理工學院、普林斯頓大學等世界一流高校本科生具有同等，甚至更高競爭力的領跑國際的拔尖創(chuàng)新計算機科學人才。姚期智院士為班內(nèi)學生專門制訂培養(yǎng)方案，尤其是他開設的理論算法課程，令人耳目一新。同時，他還邀請微軟亞洲研究院的研究員為學生教授分布式計算、操作系統(tǒng)等課程，教材、習題在當時都十分先進。集結優(yōu)秀的老師、聰明的同學，“姚班”內(nèi)部形成了熱烈向學的氛圍，黃志毅深受熏陶，并逐漸對姚期智院士研究的理論計算機科學產(chǎn)生了興趣。理論計算機科學，即計算機科學的數(shù)學基礎，包括各種計算問題的算法設計及其時間復雜度、空間復雜度等方面的數(shù)學分析，十分契合黃志毅的興趣和專長。

2008年畢業(yè)后，黃志毅前往美國賓夕法尼亞大學讀博深造。導師薩姆帕斯·坎南（Sampath Kannan）是美國計算機學會會士；另一位導師亞倫·羅斯（Aaron Roth）是斯隆獎得主，兩位導師都在各自的研究領域造詣非凡。其間，黃志毅展開了積極的學術交流，接觸了理論計算機科學領域的多個方向，并對其中的在線算法和算法博弈論進行了較多研究，與谷歌研究院和微軟研究院進行了合作。不僅如此，博士期間，他還提出了“把算法轉化為激勵相容機制的一般性方法”的代表性成果，接連獲得了2012年西蒙斯理論計算機科學獎學金（全美一共有5名獲獎者）、2013年拉比諾夫博士論文獎等重要獎項。

取得博士學位后，黃志毅又在斯坦福大學跟隨哥德爾獎得主蒂姆·拉夫加登（Tim Roughgarden）做了一年博士后研究，在這期間他認真思考了接下來的科研規(guī)劃。彼時的中國，理論計算機科學研究剛剛興起。作為第一屆“姚班”學子，學成以后像姚期智院士當初一樣回國效力，一直是黃志毅的期望所在。于是，2014年他選擇回國，并加入緊鄰家鄉(xiāng)廣東、歷史悠久的香港大學（以下簡稱“港大”）任教。剛入職，他就從359名杰出青年學者計劃申請者中脫穎而出，成為2014—2015年度香港研究資助局所頒發(fā)的22個杰出青年學者獎（Early Career Award）獲獎者之一。在港大學術氛圍濃厚的校園中，黃志毅由此開啟了不確定信息下的優(yōu)化問題研究。

不確定信息下的優(yōu)化問題，是一個有別于傳統(tǒng)算法研究的方向。傳統(tǒng)算法研究考慮的是如何在時間、存儲空間等計算資源的限制條件下解決不同的計算問題；而不確定信息下的優(yōu)化問題則是在把信息本身視作一種計算資源的同時，在信息不充足的限制條件下設計算法解決問題。以搜索引擎上匹配搜索請求和廣告商的問題為例：一方面，算法在匹配某個搜索請求時無法準確預知將來還有什么樣的請求，因此這類問題需要處理將來的不確定性；另一方面，為找到好的匹配，算法想要知道廣告商對于不同關鍵字的價值衡量，而這個信息只有廣告商自己知道，于算法而言是不確定的。

▲2017年黃志毅（前排左三）參加以“不確定信息下的算法與優(yōu)化”為主題的日本湘南會議

根據(jù)信息不確定性的種類及實際考量，黃志毅主要對在線算法與算法博弈論兩個方向進行了深研。在這兩大算法領域，又矗立著數(shù)不清的科研險峰，每座險峰天然形成多面峭壁。幾十年來，其間荊棘叢生、云霧繚繞、神秘莫測，引得鐘情理論計算機科學的“探險家”“攀登者”不遠萬里前來拜謁，苦思冥想、身體力行，尋找登頂?shù)南Ｍ?。黃志毅興致勃勃投身其中，向不確定的未知正式進發(fā)。

破解問題與推進應用

在線算法領域，黃志毅先后聚焦非線性目標函數(shù)在線優(yōu)化問題、傳統(tǒng)在線匹配問題、完全在線匹配問題開展研究。算法博弈論方面，他對近年來的一個研究熱點——如何在買家價值的概率分布信息不足的場景中進行機制設計——進行了一系列創(chuàng)新研究，論文發(fā)表于理論計算機科學的旗艦會議計算理論年會（STOC）和計算機科學基礎年會（FOCS）。

調(diào)度和資源分配是非線性目標函數(shù)的在線優(yōu)化的兩類經(jīng)典問題。2014年，黃志毅針對如何實時調(diào)整處理器速度，以達到能源消耗與工作處理效能間的最優(yōu)平衡的問題展開研究。這當中有個關鍵點在于，能耗往往是處理器速度的二次或三次函數(shù)而并非線性，對此黃志毅提出了一套基于Fenchel對偶性的算法設計和分析框架，并以此為基礎設計了此問題的理論最優(yōu)算法。2015年，他進一步把結果擴展到無法準確預測處理每個工作所需計算資源之數(shù)量的短視模型，并在此模型下提出了一個新算法去模仿非短視模型下的算法決策。相關論文獲得了高性能計算理論方面的頂會算法和架構并行性年會（SPAA）頒發(fā)的最佳論文獎。2016年，黃志毅從Fenchel對偶性框架中提煉出一般性的理論方法，從而一次性地解決了一大類非線性目標函數(shù)的覆蓋及裝箱問題?！睹绹嬎銠C學會算法與計算理論通訊》（ACM SIGACT News）在線算法專欄的2016年總結中認為這篇論文“統(tǒng)一、簡化，并改進了許多現(xiàn)有結果”，并稱這一論文為“此年度最引人矚目的結果”。

匹配是最基礎的優(yōu)化問題之一，而它的在線版本也是在線算法中最受關注的方向之一。傳統(tǒng)在線匹配模型在器官移植、在線廣告匹配等應用場景的建模中十分常見。由于理論計算機科學中常用的最壞情形分析框架在這些場景下往往不能很好地刻畫實際問題的特點，所以近年在線匹配的熱點和難點之一是在模型中引入一定的隨機性并在此前提下設計算法。此外，傳統(tǒng)在線匹配中有一些經(jīng)過10年以上研究仍未有突破的開放性問題。2020年，經(jīng)過多年積累和思考，黃志毅針對2005年提出的廣告關鍵字問題和2009年提出的顯示廣告問題提出了名為在線相關選擇的新算法技巧，一舉突破了這兩個開放性問題的瓶頸。尤其值得一提的是，他關于解決顯示廣告問題的工作獲得了2020年度計算機科學基礎年會（FOCS）的會議最佳論文獎，是歷史上第二次有亞洲院校的學者獲獎，也是近14年來的首次。

傳統(tǒng)的在線匹配理論只處理二分圖匹配，比如搜索請求和廣告商的匹配。而在包括叫車、拼車服務在內(nèi)的一些新應用場景中，算法所需要處理的往往是一般圖的在線匹配。從實際場景出發(fā)，2018年黃志毅提出了完全在線匹配模型及相應的算法分析框架，從而使一般圖的在線匹配理論研究成為可能，這被認為是“首次把圖靈獎得主理查德·卡帕等提出的算法推廣到一般圖并取得好于0.5的近似比”。由于研究頗具價值，后續(xù)叫車平臺Lyft、麻省理工學院、斯坦福大學等研究組都參考使用了這個模型。

此外，在算法博弈論方面，關于“如何在貝葉斯模型下從數(shù)據(jù)中學習出貝葉斯先驗概率分布的近似形式，從而用較少的數(shù)據(jù)得出利潤最大化的近似最優(yōu)機制”的問題，針對算法的采樣復雜度，自2015年起，黃志毅接連產(chǎn)出了一系列研究成果。

——2015年，黃志毅發(fā)現(xiàn)了這一問題與統(tǒng)計機器學習理論及信息論之間的聯(lián)系，其中前者能用于分析采樣復雜度的上界，而后者能用于分析采樣復雜度的下界。基于這些工具，他解決了單個買家單個物品情形下的采樣復雜度問題，在業(yè)內(nèi)引起廣泛關注。

——2016年，黃志毅把基于統(tǒng)計機器學習理論的算法思路及分析的方法推廣到了多個買家的情形，從而改進了其采樣復雜度上界。

——2017年，黃志毅注意到實際場景中的算法需要不斷利用新的數(shù)據(jù)更新所學到的機制和定價，這可以視作一種在線學習。通過提出一套新的多尺度在線學習理論，他設計了新的算法并獲得了最優(yōu)的理論結果。這套新理論后來在傳統(tǒng)機器學習理論的模型選擇問題中也得到了應用。

——2018年，黃志毅注意到此前的相關研究中一般假設買家并不會針對賣家的算法對自身行為進行策略性的調(diào)整，而一些后續(xù)研究指出這個假設過度簡化了問題，并證明了買家的策略性行為可能大幅降低賣家算法所獲得的利潤。據(jù)此，他提出了一套基于差分隱私的算法工具，這套工具在所需要學習的機制結構相對簡單時可以有效地降低買家的策略性行為。

——2019年，黃志毅基于此前研究，重新提出了一套與之前框架截然不同的基于信息學的新方法，從而徹底解決了多個買家情形下采樣復雜度問題，被學界視為采樣復雜度方向的一個“突破性結果”。

——2020年，黃志毅進一步將這一系列采樣復雜度理論應用到更困難的市場劃分問題上，并獲得了這個問題的首個多項式采樣復雜度上界。

以上相關成果獲得了包括算法博弈論的奠基者及理論計算機科學領域高規(guī)格獎哥德爾獎得主諾姆·尼桑（Noam Nisan）、蒂姆·拉夫加登，以及奈望林納獎得主康斯坦丁諾斯·達斯卡拉基斯（Constantinos Daskalakis）、圖靈獎得主姚期智等在內(nèi)的著名學者的引用研究。

▲黃志毅在中國計算機協(xié)會（CCF）啟智會上以“數(shù)據(jù)驅動的拍賣機制設計”為主題開展講座

從講臺下聆聽基礎課的懵懂學子，到成為與諸位恩師、學界前輩娓娓而談的學術同行，黃志毅的成長肉眼可見?！拔业倪M步除了離不開姚院士的指引，也深深受益于我的博士生導師薩姆帕斯·坎南和亞倫·羅斯，以及博士后導師蒂姆·拉夫加登、微軟研究院實習時的導師尼基爾·德瓦馬塔爾（Nikhil Devanur）。鄧小鐵、滕尚華、孫曉明等學界前輩，亦多次提攜指教，給予我寶貴的建議?！币荒暧忠荒?，現(xiàn)實世界的諸多問題凝于腦海，伴隨一次次復雜的推演、解題，黃志毅的算法險峰攀登之旅漸入佳境。

明德格物 探索不止

港大的?；丈乡澘讨懊鞯赂裎铩?個字。“明德”就是彰顯德行，“格物”就是探究事物原理。在快節(jié)奏的香港，港大給師生營造了一個安靜舒適的學術天堂，去除了浮躁，并不一味追求論文產(chǎn)出。在近10年的港大生涯中，黃志毅體會最大的就是這種讓人富有尊嚴的學術自由度。

“理論計算機科學研究的成果產(chǎn)出周期相對較長，但是學院并沒有一刀切地下達硬性任務指標，而是尊重了大家的學科特點。學院領導還很注重培養(yǎng)年輕教師的獨立科研能力，鼓勵我們先發(fā)展自己的團隊和感興趣的科研方向，而不是與資深的教授合作盡快產(chǎn)出成果?！闭窃谶@種氛圍下，黃志毅沒有跟風選擇熱門方向，而是堅持自己的研究興趣，逐漸帶領團隊步入正軌，順理成章地形成了一系列有影響力的學術成果。

目前，黃志毅團隊平均每年招收1名博士研究生，課題組的博士研究生一般為4到5名。此外，每年夏天，他還會指導2到6名來自國內(nèi)外的本科生做研究。短期的師生緣分結束后，如果互相考察滿意，將會繼續(xù)進行為期一年的合作研究。而這些本科生中的一部分便是來自清華的“姚班”?！耙Π嗳恕币贿厒鞒兄ζ谥窃菏康膶W術衣缽，一邊協(xié)作創(chuàng)新，人才輩出。

在黃志毅看來，理論計算機科學的研究模式，某種意義上是一種學徒制?！拔腋鷮W生是合作關系。我們的區(qū)別可能主要在于我經(jīng)驗更豐富、資歷更深。在日常研究中，他們會通過課題研究，學習我的選題思路、解題思路、提問思路等。這種研究模式，沒有一套完整的教材，導師更需要對學生進行言傳身教。”

為此，黃志毅對學生提出了他認為最重要的幾點要求。一是要培養(yǎng)對高價值選題、高品位選題的認知?！笆嗄昵?，我去賓夕法尼亞大學讀博，系主任在簡介會上講了許多話，我至今唯一記得的一句就是‘讀博這幾年，最重要的一件事就是形成研究的品位，知道選題的好與壞’?！倍亲隼碚撚嬎銠C科學研究，需要在數(shù)學思維的運行、數(shù)學工具的使用上有足夠的成熟度，能夠隨機應變，想方設法推進研究。三是養(yǎng)成好習慣?！拔医?jīng)常跟學生強調(diào)，要保持良好的閱讀論文的習慣，除了自己小方向的論文外，還要盡可能了解一些其他相關領域的前沿學術成果，拓展知識儲備、學術視野?！敝劣冢芏嗳岁P心的論文發(fā)表，黃志毅反而對此抱著輕松的態(tài)度，“論文發(fā)表有一定的運氣成分在，看學生個人造化就好，急不來”。

即便當了多年老師，黃志毅也始終謹記自己的學生身份。在姚期智院士眾多的提點之語中，那句“做研究的人，不需要在同一個問題上反復證明自己”曾如一顆石子投入湖水，在黃志毅的心里激起圈圈漣漪，后來成為他時時勉勵自己的格言，激勵著他不斷嘗試、不斷挑戰(zhàn)，每隔一段時間便停下來回顧總結。而決定攀登成功與否的，往往就是微末的細節(jié)、一念的猶豫。如今，相比獲得“最佳論文”，做出新穎的科研探索、踐行美好的科研品位，更讓黃志毅心向往之。

在線算法研究的問題根源于未來將發(fā)生的不確定性，算法博弈論關注的是與自私主體私人信息的不確定性相關的問題。未來，在不確定性下優(yōu)化的廣泛背景下，黃志毅希望對相關方向上未解決的挑戰(zhàn)繼續(xù)展開探索。在戰(zhàn)略環(huán)境中的學習、在線優(yōu)化的線性程序層次結構、融合來自不同領域的在線決策策略……一座座險峰、一面面峭壁，也正向這位勇敢的攀登者發(fā)出盛情邀約。