黄志怡：アルゴリズムの「危険峰」の最高「岩峰」へ突進する登山家！

香港大学（HKU）のコンピューターサイエンス准教授である黄志怡氏は、登山をしていない日でも、「岩のホールド」について考えています。つまり、指先、足の裏、体幹を完璧に動かし、動きの姿勢や前後のつながりをイメージすることです。彼がロッククライミングを愛するのは、主にこのスポーツが彼のキャリア、つまり理論計算機科学の分野における不確実な情報に基づく最適化問題の研究に似ているからです。

それぞれの険しい岩壁は、脳と身体の緊密な連携、道具の適切な使用、慎重な計画と要約、そして複数の困難に対する的を絞った攻撃を必要とする、一連の挑戦的な未解決問題のようなものなのです。そして、何度も落下したり宙に浮いたりしながら、挫折や自信喪失に耐え、感情的な回復力、肉体的な意志力、そして最後までやり遂げるという信念を高めます。あらゆる不確実な情報の下で、慎重に分析し、絶えずテストすることで微妙なバランスと最適化を実現し、広大な世界からの真のニーズに応えます。

▲黄志怡

黄志怡氏は、2014年に香港大学に着任して以来、たゆまぬ努力により、チューリング賞受賞者のリチャード・カープ氏が提唱した30年来の未解決問題（スマートトラベルや臓器提供などのアプリケーションをカバー）と、オンライン広告における10年以上も未解決だったディスプレイ広告と広告キーワードという2つの問題を次々と解決してきました。これまでに、彼はトップクラスの会議で40以上の論文を発表しています。 2015年、アルゴリズムとアーキテクチャにおける並列処理に関する年次会議（SPAA）で最優秀論文賞を受賞し、アジアの機関から初の受賞者となった。 2020年、彼はコンピューターサイエンスの基礎に関する年次会議（FOCS）で最優秀論文賞を受賞し、アジアの機関からの受賞者としては14年ぶり、アジアの機関からの受賞者としては2人目となりました。

最も美しい景色は危険な山頂にあり、最も美しい景色はその先にあります。アルゴリズムの世界への登りは、決して終わることはありません。黄智怡にとって、登山の素晴らしさは、長い探索の末に見つけた完璧なルート、頂上に到達した後のつかの間の喜び​​、そして苦難を乗り越えて最高の「岩峰」に触れた後に次の未知の崖に向かって歩き続ける恐れのない勇気、そしてその結果として鍛えられ、絶えず視野を広げて上を目指す旺盛な生命力にあります。

不確かな未知への道

理論計算機科学者にとって、静かな瞬間には必ず「ブレインストーミング」が起こる可能性があります。週末に床に座って子供たちとゲームをしているとき、黄志怡さんは気づかないうちに心がどこか別のところへさまよい、アルゴリズムの問​​題について考えてしまうことがありました。彼が理論計算機科学にこだわるようになったのは、10年以上前に清華大学（略称「清華」）の「姚クラス」で学んだ経験に遡ります。

2004 年、チューリング賞を受賞した院士の姚其志氏が清華大学に戻り、コンピューター科学と科学技術学部でフルタイムで教鞭をとりました。この時期に、彼は「清華学院コンピュータサイエンス実験クラス」を設立するというアイデアを思いつきました。翌年、彼は選抜試験に合格し、数学とコンピュータサイエンスの優秀な学生30人からなるクラスを正式に編成しました。これが最初の「ヤオクラス」でした。黄志怡は最初の「ヤオクラス」に入学したとき、まだ高校3年生だった。彼は高校の数学コンテストで優秀な成績を収めたため、清華大学のコンピュータサイエンス学部に入学しました。その後、数学と物理学に興味を持ち、大学の「数学・物理学実験クラス」の講義を受講しました。これらは、彼が「ヤオクラス」に入学するための一定の基盤を意図せずに築いたのです。

「ヤオクラス」は、マサチューセッツ工科大学やプリンストン大学などの世界トップクラスの大学の学部生と同等かそれ以上の競争力を持ち、世界をリードする一流の革新的なコンピュータサイエンスの人材を育成することに注力しています。姚其志院士は、特に彼が指導した理論アルゴリズムのコースを中心に、クラスの学生のために特別にトレーニング プログラムを開発し、新鮮な印象を残しました。同時に、マイクロソフト リサーチ アジアの研究者を招き、分散コンピューティングやオペレーティング システムなどのコースを学生に教えてもらいました。当時の教材や演習は非常に先進的でした。 「ヤオクラス」は優秀な教師と賢いクラスメイトによって、温かい学習環境を形成しています。黄志怡はこれに深く影響を受け、次第に院士姚其之が研究する理論計算機科学に興味を持つようになった。理論計算機科学、つまり計算機科学の数学的基礎には、さまざまな計算問題のアルゴリズム設計と、それらの時間計算量、空間計算量などの数学的分析が含まれており、これは黄智怡の関心と専門知識と非常に一致しています。

黄志怡氏は2008年に卒業後、さらに博士課程を修了するため米国のペンシルベニア大学に進学した。私の指導者であるサンパス・カンナンは、アメリカコンピュータ協会の会員です。私のもう一人の指導者であるアーロン・ロスはスローン賞受賞者です。両指導者はそれぞれの研究分野で素晴らしい業績を残しました。この期間中、黄志怡は積極的に学術交流を行い、理論計算機科学の分野で多方面と接触し、オンラインアルゴリズムやアルゴリズムゲーム理論に関する広範な研究を行い、Google ResearchやMicrosoft Researchと協力しました。それだけでなく、博士課程では「アルゴリズムをインセンティブ互換メカニズムに変換する一般的な方法」という代表的な成果も提案し、2012年シモンズ理論計算機科学奨学金（米国で計5名受賞）や2013年ラビノフ博士論文賞など重要な賞を相次いで受賞しました。

黄志怡氏は博士号を取得後、ゲーデル賞受賞者のティム・ラフガーデン氏の指導の下、スタンフォード大学で1年間のポスドク研究を行い、その間に次の科学研究計画を真剣に検討しました。当時、中国では理論的なコンピュータサイエンスの研究が始まったばかりでした。黄智怡さんは、第一期「姚クラス」の学生として、姚其志院士のように卒業後に中国に帰国して奉仕することをずっと望んでいた。そこで、2014年に彼は中国に戻り、故郷の広東省に隣接する長い歴史を持つ大学である香港大学（以下、「HKU」）で教鞭をとることを選択しました。入社後すぐに、彼は優秀若手研究者プログラムの応募者359名の中から抜きん出て、2014年から2015年にかけて香港研究助成協議会から授与される早期キャリア賞の受賞者22名のうちの1人となりました。香港大学のキャンパスの強い学術的雰囲気の中で、黄志怡は不確実な情報の下での最適化問題の研究を始めました。

不確実な情報の下での最適化問題は、従来のアルゴリズム研究とは異なる方向性を持っています。従来のアルゴリズム研究では、時間やストレージスペースなどのコンピューティングリソースの制約下でさまざまなコンピューティング問題を解決する方法を検討します。一方、不確実な情報下での最適化問題とは、情報自体を計算リソースとして扱いながら、不十分な情報という制約の下で問題を解決するアルゴリズムを設計することです。検索エンジンでの検索リクエストと広告主のマッチングの問題を例に挙げてみましょう。一方では、特定の検索リクエストをマッチングさせる際に、アルゴリズムは将来どのようなリクエストがあるかを正確に予測することはできないため、この種の問題では将来の不確実性に対処する必要があります。一方、適切なマッチを見つけるために、アルゴリズムはさまざまなキーワードに対する広告主の価値評価を知る必要がありますが、この情報は広告主自身のみが知っているため、アルゴリズムにとっては不確実です。

▲黄志怡氏（前列左から3人目）は2017年に「不確実な情報下でのアルゴリズムと最適化」をテーマに日本で開催された湘南カンファレンスに参加した。

情報の不確実性の種類と実際的な考慮に基づいて、黄志怡は主にオンラインアルゴリズムとアルゴリズムゲーム理論という2つの方向で詳細な研究を行いました。これら 2 つの主要なアルゴリズム分野には、無数の科学研究のピークがあり、それぞれが自然に複数の崖で形成されています。この地域は数十年にわたって、いばらと霧と謎に囲まれており、理論計算機科学に情熱を傾ける「探検家」や「登山家」が、頂上到達を夢見て、遠方から訪れ、思索し、実践してきた。黄志怡は大きな関心を持ってそれに飛び込み、不確かな未知の世界へと正式に向かった。

問題の解決とアプリケーションの促進

オンライン アルゴリズムの分野では、黄志怡は、非線形目的関数のオンライン最適化問題、従来のオンライン マッチング問題、および完全オンライン マッチング問題に重点を置いてきました。アルゴリズムゲーム理論の分野では、近年の研究のホットスポットである、買い手の価値の確率分布に関する情報が不十分なシナリオでメカニズムを設計する方法に関して、一連の革新的な研究を実施しました。彼の論文は、理論計算機科学の主要会議である Annual Conference on the Theory of Computing (STOC) および Annual Conference on the Foundations of Computer Science (FOCS) で発表されました。

スケジューリングとリソース割り当ては、非線形目的関数のオンライン最適化における 2 つの典型的な問題です。 2014 年、黄志怡は、エネルギー消費と作業処理パフォーマンスの最適なバランスを実現するために、プロセッサ速度をリアルタイムで調整する方法の研究を始めました。ここで重要な点は、エネルギー消費はプロセッサ速度の線形関数ではなく、2 次関数または 3 次関数になることが多いということです。これに対して、黄志怡はフェンシェル双対性に基づくアルゴリズム設計と分析のフレームワークを提案し、これに基づいてこの問題に対する理論的に最適なアルゴリズムを設計しました。 2015 年に、彼は結果を、各タスクの処理に必要なコンピューティング リソースの量を正確に予測できない近視眼的なモデルにさらに拡張し、このモデルの下で、非近視眼的なモデルの下でのアルゴリズムによる意思決定を模倣する新しいアルゴリズムを提案しました。関連論文は、高性能コンピューティング理論の分野でトップクラスの会議であるアルゴリズムとアーキテクチャの並列処理に関する年次会議 (SPAA) で最優秀論文賞を受賞しました。 2016 年、黄志怡はフェンチェル双対フレームワークから一般的な理論的手法を抽出し、それによって大規模なクラスの非線形目的関数の被覆およびパッキング問題を一度に解決しました。計算機協会のアルゴリズムと計算理論に関するニュースレター (ACM SIGACT News) のオンライン アルゴリズム コラムの 2016 年の概要では、この論文は「多くの既存の結果を統合、簡素化、改善した」と述べられており、この論文は「今年最も注目を集めた結果」と呼ばれています。

マッチングは最も基本的な最適化問題の 1 つであり、そのオンライン バージョンはオンライン アルゴリズムで最も人気のある方向性の 1 つでもあります。従来のオンライン マッチング モデルは、臓器移植やオンライン広告のマッチングなどのアプリケーション シナリオのモデリングで非常に一般的です。理論計算機科学で一般的に使用される最悪ケース分析フレームワークでは、これらのシナリオにおける実際の問題の特性をうまく特徴づけることができないことが多いため、近年のオンラインマッチングにおけるホットスポットと難しさの 1 つは、この前提の下でモデルに一定のランダム性を導入し、アルゴリズムを設計することです。さらに、従来のオンラインマッチングには、10年以上の研究を経ても解決されていない未解決の問題がいくつかあります。黄志怡氏は、長年の蓄積と思考を経て、2020年に、2005年に提起された広告キーワード問題と2009年に提起されたディスプレイ広告問題に対して、オンライン関連性選択と呼ばれる新しいアルゴリズム手法を提案し、これら2つの未解決問題のボトルネックを一挙に突破しました。特に注目すべきは、ディスプレイ広告問題の解決に関する彼の研究が、2020 年のコンピューターサイエンスの基礎に関する年次会議 (FOCS) で最優秀論文賞を受賞したことです。アジアの大学の学者がこの賞を受賞するのは史上2度目であり、約14年ぶりとなる。

従来のオンライン マッチング理論では、検索リクエストと広告主のマッチングなど、二部グラフ マッチングのみを扱います。タクシー配車や相乗りサービスなどの新しいアプリケーション シナリオでは、アルゴリズムで一般的なグラフのオンライン マッチングを処理する必要があることがよくあります。黄志怡は、実用的なシナリオから始めて、2018年に完全なオンラインマッチングモデルと対応するアルゴリズム分析フレームワークを提案し、一般的なグラフのオンラインマッチングに関する理論研究を可能にしました。これは、「チューリング賞受賞者のリチャード・キャパらが提案したアルゴリズムが一般グラフに拡張され、0.5 を超える近似率を達成した初めての事例」と考えられています。この研究は価値があったため、配車プラットフォームのLyft、MIT、スタンフォード大学などのその後の研究グループはすべてこのモデルを参考にしました。

また、アルゴリズムゲーム理論の分野では、「ベイジアンモデルの下でデータからベイジアン事前確率分布のおおよその形を学習し、より少ないデータで利益を最大化するおおよその最適メカニズムを導き出す方法」という問題に関して、黄志怡は2015年からアルゴリズムのサンプリング複雑性を対象にした一連の研究成果を発表している。

--2015年、黄志怡氏はこの問題と統計的機械学習理論および情報理論との関連性を発見しました。前者はサンプリング複雑度の上限を分析するために使用でき、後者はサンプリング複雑度の下限を分析するために使用できます。これらのツールに基づいて、彼は単一の購入者と単一の商品の場合のサンプリング複雑性の問題を解決し、業界で広く注目を集めました。

——2016年、黄志怡は統計的機械学習理論に基づくアルゴリズムのアイデアと分析方法を複数の購入者の状況に拡張し、それによってサンプリングの複雑さの上限を改善しました。

——2017年、黄志怡氏は、実際のシナリオにおけるアルゴリズムは、学習したメカニズムと価格設定を更新するために常に新しいデータを使用する必要があり、これはオンライン学習の一形態とみなすことができることに気づきました。彼は新しいマルチスケールオンライン学習理論を提案することで、新しいアルゴリズムを設計し、最適な理論的結果を得ました。この新しい理論は、後に従来の機械学習理論におけるモデル選択問題に適用されました。

--2018年、黄志怡氏は、これまでの関連研究では、買い手は売り手のアルゴリズムに基づいて戦略的に行動を調整することはないと一般的に想定されていたことに気づきました。しかし、その後の研究では、この仮定は問題を単純化しすぎており、買い手の戦略的行動によって売り手のアルゴリズムによって得られる利益が大幅に減少する可能性があると指摘されました。これを踏まえて、彼は差分プライバシーに基づく一連のアルゴリズムツールを提案しました。これは、学習するメカニズム構造が比較的単純な場合に、購入者の戦略的行動を効果的に削減することができます。

--2019年、黄志怡氏はこれまでの研究に基づき、これまでの枠組みとは全く異なる新たな情報科学ベースの手法を再提案し、複数の購入者の状況下でのサンプリングの複雑さの問題を完全に解決しました。これは学術界からはサンプリングの複雑さの方向における「画期的な成果」とみなされました。

——2020年、黄志怡氏はこの一連のサンプリング複雑度理論をさらに難解な市場細分化問題に適用し、この問題に対する初の多項式サンプリング複雑度上限値を獲得した。

上記の関連成果は、アルゴリズムゲーム理論の創始者であり理論計算機科学の分野で高名な賞であるゲーデル賞を受賞したノアム・ニサン、ティム・ラブガーデン、ネヴァンリンナ賞を受賞したコンスタンティノス・ダスカラキス、チューリング賞を受賞したヤオ・キジなど著名な学者によって引用されています。

▲黄志怡氏は中国コンピュータ連盟（CCF）啓蒙会議で「データ駆動型オークションメカニズム設計」をテーマに講演した。

教壇で基礎講座を聞いている無知な学生から、指導者や学問上の先輩たちと雑談する学術的同僚へと、黄志怡の成長は肉眼で見てとれる。 「私の進歩は、ヤオ院士の指導、そして博士課程の指導教官であるサムパット・カンナン氏とアーロン・ロス氏、博士課程の指導教官であるティム・ラブガーデン氏、そしてマイクロソフト リサーチでのインターンシップ中のメンターであるニキル・デヴァヌール氏のおかげです。鄧小鉄氏、滕尚華氏、孫暁明氏などの学術上の先輩たちも、何度も私に貴重な指導とアドバイスを与えてくれました。」年々、現実世界の多くの問題が彼の心の中に凝縮されてきました。複雑な推論と問題解決を繰り返し、アルゴリズムの危険な頂点を登る黄智怡の旅は徐々に進歩しました。

ミンデの探求は止まらない

香港大学の校章には「明德葛物」という4文字が刻まれている。 「明徳」は徳を示すことを意味し、「格武」は物事の理を探求することを意味します。ペースの速い香港において、HKU は衝動性を排除し、盲目的に論文のアウトプットを追求することなく、教師と学生のための静かで快適な学術の楽園を創り出しました。香港大学での約10年間のキャリアの中で、黄志怡氏が最も経験したのは、尊厳ある学問の自由だった。

「理論コンピュータサイエンス研究の成果サイクルは比較的長いですが、大学は一律に厳格なタスク指標を発行せず、各人の専門分野の特徴を尊重しました。大学の指導者は、若い教師の独立した科学研究能力の育成にも注意を払っており、できるだけ早く結果を出すために上級教授と協力するのではなく、まず自分のチームと興味のある科学研究の方向性を開発することを奨励しています。」このような雰囲気の中で、黄志怡は流行の方向を選ぶという流行に従わず、自分の研究関心を主張し、徐々にチームを正しい軌道に導き、自然に影響力のある一連の学術的業績を形成していった。

現在、黄志怡氏のチームは毎年平均1人の博士課程の学生を採用しており、研究グループには通常4～5人の博士課程の学生がいます。さらに、毎年夏には国内外から集まった2～6名の学部生を指導し、研究を行っています。短期間の師弟関係が終了した後、双方がお互いの評価に満足すれば、1年間共同研究を継続します。これらの学部生の中には、清華大学の「姚クラス」出身者もいる。 「姚クラス」は、姚其之院士の学問的伝統を継承しながら、協力と革新を進め、多くの優秀な人材を輩出しています。

黄志怡氏の見解では、理論計算機科学の研究モデルは、ある意味では見習い制度である。 「私と生徒は協力的な関係にあります。私たちの違いは、私の方が経験と資格が豊富だということです。日々の研究で、生徒は研究プロジェクトを通じて、トピックの選択、問題の解決、質問の仕方に関する私の考えを学びます。この研究モデルには完全な教材セットがないため、講師は実例を挙げて生徒に教える必要があります。」

この目的のために、黄志怡は学生たちに、最も重要だと信じるいくつかの要求を提示しました。まず、価値が高く、質の高いトピックに対する認識を高める必要があります。 「10年以上前、私は博士号を取得するためにペンシルベニア大学に留学しました。学部長は説明会で多くのことを話しました。私が覚えているのは、『博士課程で最も重要なことは、研究に対する好みを養い、テーマの良し悪しを判断することです』という一文だけです。」第二に、理論計算機科学研究を行うには、数学的思考の運用と数学的ツールの使用において十分な成熟度を持ち、状況に適応し、研究を進める方法を見つける能力が必要です。 3つ目は良い習慣を身につけることです。 「私は学生たちに、論文を読む習慣をつけるようにとよく強調しています。自分の専門分野の論文だけでなく、関連分野における最先端の学術成果についても学び、知識の蓄えと学問の視野を広げるように努めるべきです。」多くの人が懸念している論文の発表に関しては、黄志怡氏は比較的寛容な姿勢を示している。 「論文の出版にはある程度の運の要素が関わってきます。それは学生個人の運次第であり、急ぐ必要はありません。」

黄志怡さんは長年教師を務めた後も、常に生徒としてのアイデンティティを念頭に置いています。姚其之院士の数々の提案の中でも、「研究する人は同じ問題で何度も自分自身を証明する必要はない」という一節は、湖に投げ込まれた石のように、黄智怡の心に波紋を呼んだ。その後、時々自分自身を励まし、挑戦し続ける意欲をかき立て、常に自分自身に挑戦し、時々立ち止まって見直し、まとめることが彼のモットーになりました。登山が成功するかどうかを決めるのは、多くの場合、小さな詳細と一瞬の躊躇です。現在、黄智怡氏は「最優秀論文賞」の受賞よりも、斬新な科学研究の探求と美しい科学研究の趣味の実践に熱心に取り組んでいます。

オンライン アルゴリズム研究における問題は、将来何が起こるかという不確実性に根ざしており、アルゴリズム ゲーム理論は、利己的なエージェントに関する個人情報の不確実性に関連する問題に焦点を当てています。今後、黄志怡氏は不確実性下での最適化という幅広い文脈において、関連方向における未解決の課題の探求を継続したいと考えています。戦略的な環境での学習、オンラインで最適化された線形計画階層、さまざまな分野のオンライン意思決定戦略の統合... 次々と現れる危険な山頂、次々と現れる険しい崖も、この勇敢な登山者に温かい招待状を送っています。