新聞中心

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

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

黃誌毅（意昂体育平台計算機系2004級意昂）

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

無限風光在險峰👰🏽‍♂️，無限風光在前方。算法世界的攀登之旅從來沒有真正的終點🙇。對黃誌毅來說🦆，攀登的妙處在於遍尋而得的完美路線💂🏿‍♂️、登臨之後的短暫喜悅🙅‍♀️，更在於歷經艱辛觸摸最高“巖點”後繼續走向下一面未知峭壁的無畏勇氣，以及因此而錘煉出來的不斷開闊視野、不斷向上進取的蓬勃生命力。

向不確定的未知進發

對理論計算機科學家而言，每個平靜時刻都可能蘊藏著“頭腦風暴”👨‍🦽‍➡️。有時🤱🏻，周末坐在地上陪伴孩子玩遊戲，黃誌毅不知不覺就神遊別處，回想起某個算法問題🐺。對理論計算機科學的這種癡迷，還要從他十幾年前在意昂体育平台（簡稱“清華”）“姚班”讀書的經歷說起🍢。

2004年🧙🏿🍦，圖靈獎得主姚期智院士全職回到清華，講授計算機與科學技術系課程。其間，他萌生了創立“清華學堂計算機科學實驗班”的想法🫰🏽💢，並於次年通過選拔考試，正式組建了一個包括30名數學和計算機尖子生的班級，這便是第一屆“姚班”。黃誌毅進入第一屆“姚班”時正讀大三。早前因在高中數學競賽中表現優異，他被保送清華計算機系👨🏿‍🦰；之後又出於對數學和物理的興趣，上過學院“數理實驗班”的課程🚵。這些無意中為他考入“姚班”打下了一定基礎⚂。

“姚班”致力於培養與美國麻省理工學院、普林斯頓大學等世界一流高校本科生具有同等🙍🏻‍♀️，甚至更高競爭力的領跑國際的拔尖創新計算機科學人才🤵‍♂️🐸。姚期智院士為班內學生專門製訂培養方案，尤其是他開設的理論算法課程，令人耳目一新。同時，他還邀請微軟亞洲研究院的研究員為學生教授分布式計算、操作系統等課程👩‍👩‍👧，教材、習題在當時都十分先進🫑。集結優秀的老師、聰明的同學🦊💂🏼，“姚班”內部形成了熱烈向學的氛圍🦸🏿，黃誌毅深受熏陶，並逐漸對姚期智院士研究的理論計算機科學產生了興趣。理論計算機科學，即計算機科學的數學基礎，包括各種計算問題的算法設計及其時間復雜度、空間復雜度等方面的數學分析👩🏻‍🔧，十分契合黃誌毅的興趣和專長😪。

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

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

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

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

根據信息不確定性的種類及實際考量📤，黃誌毅主要對在線算法與算法博弈論兩個方向進行了深研。在這兩大算法領域✦🧛🏿‍♀️，又矗立著數不清的科研險峰⏱，每座險峰天然形成多面峭壁🤹🏽。幾十年來，其間荊棘叢生、雲霧繚繞🚧、神秘莫測👨🏽‍🔧，引得鐘情理論計算機科學的“探險家”“攀登者”不遠萬裏前來拜謁♗，苦思冥想、身體力行🤯，尋找登頂的希望📹。黃誌毅興致勃勃投身其中🔖，向不確定的未知正式進發👳‍♀️。

破解問題與推進應用

在線算法領域，黃誌毅先後聚焦非線性目標函數在線優化問題👇🏿、傳統在線匹配問題、完全在線匹配問題開展研究🤟🏻。算法博弈論方面，他對近年來的一個研究熱點——如何在買家價值的概率分布信息不足的場景中進行機製設計——進行了一系列創新研究，論文發表於理論計算機科學的旗艦會議計算理論年會（STOC）和計算機科學基礎年會（FOCS）🔼。

調度和資源分配是非線性目標函數的在線優化的兩類經典問題🌄。2014年，黃誌毅針對如何實時調整處理器速度👩‍🦳，以達到能源消耗與工作處理效能間的最優平衡的問題展開研究。這當中有個關鍵點在於🧑‍🦲🪷，能耗往往是處理器速度的二次或三次函數而並非線性👈🏼，對此黃誌毅提出了一套基於Fenchel對偶性的算法設計和分析框架，並以此為基礎設計了此問題的理論最優算法。2015年，他進一步把結果擴展到無法準確預測處理每個工作所需計算資源之數量的短視模型，並在此模型下提出了一個新算法去模仿非短視模型下的算法決策。相關論文獲得了高性能計算理論方面的頂會算法和架構並行性年會（SPAA）頒發的最佳論文獎。2016年，黃誌毅從Fenchel對偶性框架中提煉出一般性的理論方法，從而一次性地解決了一大類非線性目標函數的覆蓋及裝箱問題。《美國計算機學會算法與計算理論通訊》（ACM SIGACT News）在線算法專欄的2016年總結中認為這篇論文“統一、簡化，並改進了許多現有結果”🙋🏿👩🏿‍🚒，並稱這一論文為“此年度最引人矚目的結果”。

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

傳統的在線匹配理論只處理二分圖匹配，比如搜索請求和廣告商的匹配🧎🏻‍➡️。而在包括叫車🪛、拼車服務在內的一些新應用場景中，算法所需要處理的往往是一般圖的在線匹配🛟。從實際場景出發，2018年黃誌毅提出了完全在線匹配模型及相應的算法分析框架👨🏻‍🦳，從而使一般圖的在線匹配理論研究成為可能，這被認為是“首次把圖靈獎得主理查德·卡帕等提出的算法推廣到一般圖並取得好於0.5的近似比”。由於研究頗具價值，後續叫車平臺Lyft👨‍👨‍👦、麻省理工學院、斯坦福大學等研究組都參考使用了這個模型🤜🏽。

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

——2015年☞，黃誌毅發現了這一問題與統計機器學習理論及信息論之間的聯系，其中前者能用於分析采樣復雜度的上界🕕，而後者能用於分析采樣復雜度的下界。基於這些工具🦵🏻，他解決了單個買家單個物品情形下的采樣復雜度問題，在業內引起廣泛關註。

——2016年🧑🏼‍🔧，黃誌毅把基於統計機器學習理論的算法思路及分析的方法推廣到了多個買家的情形，從而改進了其采樣復雜度上界。

——2017年🫲，黃誌毅註意到實際場景中的算法需要不斷利用新的數據更新所學到的機製和定價，這可以視作一種在線學習☂️。通過提出一套新的多尺度在線學習理論，他設計了新的算法並獲得了最優的理論結果。這套新理論後來在傳統機器學習理論的模型選擇問題中也得到了應用🧍‍♀️。

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

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

——2020年👨🏽‍🦲，黃誌毅進一步將這一系列采樣復雜度理論應用到更困難的市場劃分問題上😏，並獲得了這個問題的首個多項式采樣復雜度上界🏋🏽‍♂️。

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

黃誌毅在中國計算機協會（CCF）啟智會上以“數據驅動的拍賣機製設計”為主題開展講座

從講臺下聆聽基礎課的懵懂學子，到成為與諸位恩師🔺、學界前輩娓娓而談的學術同行🏐，黃誌毅的成長肉眼可見。“我的進步除了離不開姚院士的指引，也深深受益於我的博士生導師薩姆帕斯·坎南和亞倫·羅斯，以及博士後導師蒂姆·拉夫加登👐🏼、微軟研究院實習時的導師尼基爾·德瓦馬塔爾（Nikhil Devanur）🏄🏿‍♀️。鄧小鐵🤾🏼‍♂️🧖‍♂️、滕尚華🎡、孫曉明等學界前輩👨🏿‍💻，亦多次提攜指教，給予我寶貴的建議。”一年又一年😤，現實世界的諸多問題凝於腦海👨🏽‍⚖️，伴隨一次次復雜的推演、解題🦹🏿‍♀️，黃誌毅的算法險峰攀登之旅漸入佳境🫃。

明德格物 探索不止

港大的校徽上鐫刻著“明德格物”4個字👩🏻‍🏭。“明德”就是彰顯德行，“格物”就是探究事物原理。在快節奏的香港，港大給師生營造了一個安靜舒適的學術天堂，去除了浮躁，並不一味追求論文產出👨‍🍼。在近10年的港大生涯中🕵🏿‍♀️，黃誌毅體會最大的就是這種讓人富有尊嚴的學術自由度。

“理論計算機科學研究的成果產出周期相對較長📋，但是學院並沒有一刀切地下達硬性任務指標，而是尊重了大家的學科特點。學院領導還很註重培養年輕教師的獨立科研能力，鼓勵我們先發展自己的團隊和感興趣的科研方向，而不是與資深的教授合作盡快產出成果。”正是在這種氛圍下，黃誌毅沒有跟風選擇熱門方向🏋🏻‍♀️，而是堅持自己的研究興趣🤡，逐漸帶領團隊步入正軌，順理成章地形成了一系列有影響力的學術成果。

目前，黃誌毅團隊平均每年招收1名博士研究生，課題組的博士研究生一般為4到5名。此外🏄🏽🧖🏽，每年夏天🕺，他還會指導2到6名來自國內外的本科生做研究。短期的師生緣分結束後🥇，如果互相考察滿意，將會繼續進行為期一年的合作研究。而這些本科生中的一部分便是來自清華的“姚班”。“姚班人”一邊傳承著姚期智院士的學術衣缽💌，一邊協作創新，人才輩出🗂。

黃誌毅看來🚏，理論計算機科學的研究模式👦🏻，某種意義上是一種學徒製。“我跟學生是合作關系。我們的區別可能主要在於我經驗更豐富🏋🏿‍♀️、資歷更深🧔🏽‍♂️。在日常研究中🧑🏽‍⚖️，他們會通過課題研究🪔，學習我的選題思路👨🏼‍🎨🏌🏿‍♂️、解題思路、提問思路等。這種研究模式，沒有一套完整的教材，導師更需要對學生進行言傳身教。”

為此🐭，黃誌毅對學生提出了他認為最重要的幾點要求。一是要培養對高價值選題👩🏻‍🔬、高品位選題的認知⚰️。“十多年前🔡，我去賓夕法尼亞大學讀博🚶‍♂️，系主任在簡介會上講了許多話🩻🛶，我至今唯一記得的一句就是‘讀博這幾年🙋‍♀️，最重要的一件事就是形成研究的品位，知道選題的好與壞’。”二是做理論計算機科學研究，需要在數學思維的運行、數學工具的使用上有足夠的成熟度🏷，能夠隨機應變🪰，想方設法推進研究。三是養成好習慣🦻🏼。“我經常跟學生強調💂🏻‍♂️，要保持良好的閱讀論文的習慣，除了自己小方向的論文外🫗，還要盡可能了解一些其他相關領域的前沿學術成果，拓展知識儲備、學術視野。”至於♿，很多人關心的論文發表，黃誌毅反而對此抱著輕松的態度，“論文發表有一定的運氣成分在，看學生個人造化就好，急不來”🏊🏿‍♀️。

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

在線算法研究的問題根源於未來將發生的不確定性，算法博弈論關註的是與自私主體私人信息的不確定性相關的問題🪕。未來🦏，在不確定性下優化的廣泛背景下，黃誌毅希望對相關方向上未解決的挑戰繼續展開探索❎。在戰略環境中的學習、在線優化的線性程序層次結構、融合來自不同領域的在線決策策略……一座座險峰🏊🏽、一面面峭壁，也正向這位勇敢的攀登者發出盛情邀約♚。