北京大学のチームは、ChatGPTにとって頭痛の種であったアルゴリズムの最適化を解決し、普通のラップトップでも実行できるようにした。

ChatGPT ですら首をかしげたアルゴリズムの最適化は、北京大学のチームによって達成されました。

テストでは、新しい研究が、NOIP、Codeforce、Leetcode などのコンテストでの分割統治法や動的プログラミングの問題を含む検証セットの問題の 90% を解決できることが示されています。これらの問題は、多くの大規模モデルでは解決が困難です。

そして、自分の普通のラップトップでも実行できます!

結局のところ、アルゴリズムの最適化は、大規模モデル、さらには AI 全体の機能における盲点です。

Nature 誌に発表された DeepMind AlphaTensor はプログラム合成の分野に衝撃を与えたが、業界の専門家にとってその実際の影響は「まだ十分ではない」という。

では、AIが網羅できないこの分野で、アルゴリズムの最適化を加速し、効率化するにはどうすればいいのでしょうか？

北京大学のチームは、プログラム計算とプログラム列挙を組み合わせて、2セットのアルゴリズム最適化ソフトウェアを作成しました。

1 つのセットは、分割統治法、並列化、増分計算、セグメント ツリーなどのアルゴリズムの最適化を処理でき、もう 1 つのセットは動的プログラミング アルゴリズムの最適化をサポートします。

動的プログラミング アルゴリズムへの包括的なアプローチを紹介する論文 (効率的なメモ化アルゴリズムの合成) が、プログラミング言語分野の 3 大カンファレンスの 1 つである OOPSLA'23 に採択されました。また、分割統治アルゴリズムに関する別の論文も arXiv (2202.12193) に掲載されました。

さらに、これら 2 つのソフトウェア セットに必要なハードウェアのしきい値は高くありません。Intel Core i7-8700 3.2GHz 6 コア プロセッサで実行でき、平均実行時間は 6.53 秒です。

これら2つのソフトウェアは今後オープンソース化され、より使いやすいサービスとなってオンライン化される予定だと報じられている。

不思議なのは、この2つの論文の共著者の1人である北京大学の熊英飛准教授が、以前はAI分野を専門としており、CNNを使用してハースストーンを実装する最初のコードを彼によって書かれたことです。

好奇心から、私たちは熊英菲本人に話を聞いてみました。

写真

AI 設計アルゴリズムがまだ機能しないのはなぜですか?

アルゴリズムの設計では、仕様を満たすプログラムを提供し、時間と空間の複雑さを可能な限り最適化する必要があります。

大規模モデルの進歩は誰の目にも明らかです。そのため、「転換」の前に、Xiong Yingfei氏と彼のチームはアルゴリズム設計にChatGPTを使用することを検討しました。

（Copilotなどのコード補完やその他AI技術を含め、プログラムが書けるAIを全て試した結果、ChatGPTが最も優れていると感じた）

しかし、ChatGPT でもアルゴリズムの設計時にバグが残っています。

たとえば、ChatGPT は、ナップサック問題を解くなどの古典的なタスクをうまく実行できます。ただし、アイテムの重量と価値を他の属性の組み合わせから取得できるようにするなど、古典的な問題に小さな変更を加えると、出力されるコードは「混乱」し、まったく使用できなくなります。

主な理由は、アルゴリズムの設計には、プログラムの構文とセマンティクス、アルゴリズムの設計パターン、アルゴリズムの複雑さの分析などの一連の専門知識に基づいた厳密な論理的推論が必要であるためです。

現在、大規模モデルは主に多数のプログラムでトレーニングされており、トレーニングのみでトップクラスの人間の科学者が何十年も研究してきた知識を再発見することは困難です。

同時に、大規模モデルにはある程度の分析機能があるものの、現在のニューラル ネットワーク アーキテクチャでは複雑で厳密な論理的推論を実行することは依然として困難です。

このように書かれたコードは、「たとえ動作したとしても、会社としてはあえて使わない」、つまりバグを修正するコストがバグを書くコストよりも高くなる可能性があるからです（犬頭）。

それで、この問題を解決する方法はあるのでしょうか?

熊英飛氏は、チームは実際に「AIを使用する」と「AIを使用しない」という2つのアプローチを試していると語った。

一方で、数億のパラメータを持つ小さなモデルをトレーニングし、AIを使ってコードを生成することを試みました。同時に、コードの正確性を確保するために、AIと従来の方法をどのように組み合わせるかについても考えていました。

一方、チームは業界で既存の2つの方法を組み合わせることも試み、その効果は現在のAI方式よりも優れているだけでなく、より高速であることも発見しました。

それで、この魔法のような新しいアイデアとは一体何なのでしょうか?

まず「パターンを見つける」、次に「力ずくで尽くす」

具体的には、Xiong Yingfei 氏のチームが採用した新しいアイデアは、プログラム計算とプログラム列挙という 2 つの方法を組み合わせたものです。

プログラミングの手法は、簡単に言えば「パターンを見つけること」です。

現在、アルゴリズムについてはさまざまなデザイン パターンがまとめられており、これはコード設計の経験のまとめに少し似ています。

デザイン パターンには、アルゴリズムの最適化に関連する多くのプログラム変換ルールが含まれます。方程式を解くのと同様に、これらは項の加算、減算、シフト、両辺の乗算と除算などのテクニックです。

アルゴリズムの最適化は方程式を解くようなものです。さまざまな変換ルールを学ぶことはできますが、複雑な問題を解決する場合は、このルールセットを適用してプログラムを自分で解く必要があります。

この方法は数学の問題を解くのと同じようなもので、ある程度の「プログラマーの知恵」が必要です。しかし、プログラマーがより良い解決策を考え出せなかったらどうなるでしょうか?

そのため、プログラム計算に加えて、以前はプログラム列挙という別のアイデアがありました。これは、名前が示すように「ブルートフォース列挙」です。

この方法では、コンピューターにすべての可能なプログラムを試させ、検証後に常に正しいプログラムが 1 つ見つかります。たとえば、変数 x と y が与えられた場合、コンピューターは x+y、xy などを試します。

しかし、このアプローチにも問題があります。コンピューターは非常に高速ですが、世の中にはプログラムが多すぎて、プログラムの長さが増すにつれて、プログラムの数は基本的に指数関数的に増加します。

したがって、コンピューターによる直接的なブルートフォース列挙も不可能です。

この目的のために、Xiong Yingfei 氏のチームはこれら 2 つのアイデアを組み合わせ、新しいアルゴリズム最適化方法を設計しました。

簡単に言えば、まずはプログラム計算の考え方に基づいて問題を絞り込み、ちょうど「穴埋めテスト」の空欄を埋めていくように、いくつかの重要なプログラムだけをプログラムで埋めていけばよいという状況にすることです。

次に、網羅的な方法を使用して、「空白を埋める」必要があるプログラムをリストし、最後に結果を確認します。

もちろん、ここでもいくつかの同様の手法が使用されています。理論上、形式仕様は「空白を埋める」必要のある部分に完全に対応することはできず、埋める必要のある場所は他の場所と条件関係を持つ必要があるためです。

したがって、この問題に対処するために、チームは、この方法が一定の確率で失敗しないことを保証するいくつかの技術も設計しました。

AIと比較すると、この考え方で設計されたアルゴリズム最適化ソフトウェアは、精度率が高いだけでなく、問題解決プロセスも速くなります。

現在、チームは AutoLifter と SynMem という 2 セットのアルゴリズム最適化ソフトウェアを設計しました。

その中で、AutoLifter は分割統治、並列化、増分計算、単一チャネル、ストリーム アルゴリズム、セグメント ツリーなどのアルゴリズムの最適化をサポートし、SynMem は動的プログラミング アルゴリズムの最適化をサポートします。

では、これら 2 つのアルゴリズム最適化ソフトウェアの効果は何でしょうか?

チームは、Codeforces、NOIP National Youth Informatics Olympiad League、Leetcode からサポートされているアルゴリズムに対応する質問を収集し、2 つの方法をテストしました。

その中で、AutoLifter は 96 個の分割統治アルゴリズム問題のうち 82 個を解決しました。比較すると、他の 2 つの優れたプログラム合成方法では、問題の半分以下しか解決できませんでした。

写真

ハードウェア要件も高くありません。実行には Intel Core i7-8700 3.2GHz 6 コア プロセッサのみが必要で、平均時間は約 6.53 秒です。

チームは、40 個の動的プログラミング問題のうち 37 個を平均わずか 1.87 秒で解きました (他の 2 つの方法ではほとんど問題が解けませんでした)。

写真

チームは将来、これら 2 つのソフトウェア セットをオープンソース化し、サービスをより使いやすくしてオンライン化する予定です。

熊英飛氏は、最終的な目標は、コード内で最適化が必要なアルゴリズムを自動的に検出し、ソフトウェアが自動的に最適化するソフトウェアを作成することだと語った。

アプリを例にとると、何もしなくても、このアルゴリズムを使用すると、対応するアプリの実行速度が大幅に向上します。

もちろん、この目標を達成するには時間がかかるかもしれません。

「ネイチャー誌への掲載により、研究が遅れました」

AutoLifter の研究の背景にある論文は、Xiong Yingfei 氏のチームが 3 年前に開始したアルゴリズム合成プロジェクトで完成させた最初の論文です。

Xiong Yingfei 氏が挙げた理由は、これまでの方法は「包括的な理論集」と呼べるもので、プログラム合成だけでなく、プログラム計算、カテゴリ理論、確率理論、ランダムアルゴリズムなども含まれているということです。つまり、論文全体が数学記号でいっぱいなのです。

「その結果、適切な査読者を見つけるのが難しくなっている」と熊英飛氏は述べた。2年間にわたる削除と改訂を経て、この論文は今や「特定の分野に依存せず、基本的に誰もが理解できるシンボル」になったという。

やり取りの中で、Quantum位は話題から外れた質問をしました。「AlphaTensor は Nature に掲載できますが、私たちの論文は 2 年間トップクラスの会議で受け入れられていません。Nature に投稿することを検討したことがありますか?」

ション先生は冗談めかしてこう答えた。

私は博士課程の学生たちに、トップクラスのプログラミング カンファレンスと競争しないようにアドバイスしています。Nature に掲載された論文は、非常に大きな影響力を持つ可能性があります。投げてみても肉は失われません。

彼らが何と言っているか知っていますか？ 「いいえ、（自分の専門分野で）すぐに出版しないと、来年の奨学金を失うことになります！」

冗談はさておき、AutoLifter と SynMem に関する論文の第一著者を紹介しましょう。2 人ともアルゴリズム競争界ではよく知られた人物です。

Ji Ruyi 氏は、AutoLifter ワーキング ペーパーの第一著者です。

私は北京大学のプログラミング言語研究所（PLL）の博士課程4年生です。私の研究分野はプログラム合成です。指導教員はHu ZhenjiangとXiong Yingfeiです。

2016年、Ji Ruyi氏は全国青少年情報オリンピックの金メダリストとして北京大学情報科学技術学院に入学し、後に北京大学初のチューリングクラスのメンバーとなった。

彼はかつてACM大会で北京大学チームのキャプテンを務め、2度目の大会出場でチームを率いて金メダルを獲得し、世界3位、アジア1位に輝きました。彼は北京大学学生アルゴリズム協会の創設者であり初代会長でもあり、「吉先生」という愛称で呼ばれています。

SynMem の第一著者、Sun Yican 氏。

私は北京大学のプログラミング言語研究所（PLL）の博士課程3年生で、指導教員はXiong Yingfeiです。

彼はまた、全国青少年情報オリンピックで金メダルを獲得し、北京大学に入学しました。

彼の研究対象は、プログラム合成、意思決定プロセス、確率的プログラム検証です。また、パラメータ化された複雑性領域における近似不可能性に関する研究も行っています。

学部生時代、彼は北京大学電気通信学部のチューリングクラスで学びました。彼はトッププログラミング言語カンファレンス PLDI で共同筆頭著者として論文を発表しており、トッププログラミング言語カンファレンス OOPSLA やトップ人工知能カンファレンス AAAI でも他の論文を発表しています。

写真

2つの論文の共著者である熊英飛氏は、上記2人の研究者の博士課程の指導教員です。

彼は北京大学情報科学技術学院ソフトウェア工学研究所の終身在職権を持つ准教授および研究者です。彼は中国電子科技大学、北京大学、日本の東京大学でそれぞれ学士号、修士号、博士号を取得しました。

この記事で述べたプログラム合成に加えて、Xiong Yingfei 氏の主な研究分野の一つは欠陥修復の分野であり、これも彼と彼のチームが長年取り組んできた研究です。

欠陥修復は、一般的にバグ修正として知られていますが、実際には自動的なバグ修正作業です。

具体的には、まずプログラムを読み、プログラムのどの部分を変更する必要があるかを分析し、次に新しいプログラムをどのように記述するかを考えます。

Xiong Yingfei氏と彼のチームが提案した理論、方法、技術の中で、差異ベースの修復モデルは進化的欠陥の分野で広く使用されているモデルの1つになり、統計ベースの欠陥修復技術はプログラム欠陥修復の精度を約40％向上させました。

彼らの成果を採用している企業には、Huawei、Linux Kernel Configuration Project などがあります。

Xiong Yingfei 氏は、この効果を達成できた理由は、同チームが確率を用いて従来のプログラム合成を導いた最初の研究チームの 1 つだったためだと説明しました。

2017 年に発表されたこの研究では、統計的ブートストラップ合成により、バグ修復の最高レベルの精度が 40% から 70% に向上しました。

興味深いことに、それ以来多くの研究機関が確率統計と従来の機械学習の観点からプログラム合成を研究し始めましたが、当時のXiong Yingfei氏のチームは、プログラム合成にディープラーニングを使用する方法を見つけることに目を向けました。

2018年に彼らは文法ベースの構造化CNNコードジェネレーターを提案する論文を発表し、Hearthstoneベンチマークデータセットを使用して実験を実施しました。

結果は、精度が従来の最先端の方法よりも 5 パーセントポイント大幅に優れていることを示しています。

写真

この論文は最終的にAAAI 2019に掲載されました。論文には、彼らがコード生成にCNNデコーダーをうまく使用した最初のチームであると書かれていました。

2019年にチームはCNNデコーダーをTransformerに置き換え、精度が再び約5パーセントポイント向上しました。 Xiong Yingfei 氏は笑いながら、Transformer をコード生成に適用する最初の仕事を偶然に行い、「歴史を目撃した」と語った。

2021年、チームは上記の作業と差異ベース修復モデルを組み合わせて、欠陥修復作業を実施しました。 「ディープラーニングのバグ修正能力が従来の技術を上回ったのはこれが初めてだった」と熊英飛氏は語った。

しかし、少しドラマチックなのは、学術界のほとんどのチームがプログラムの合成と欠陥の修復にディープラーニングを使い始めたときに、Xiong Yingfei のチームが従来の方法に重点を置き始めたことです。その結果、この記事で言及されている 2 セットのアルゴリズム最適化ソフトウェアが誕生しました。

彼らのチームは、プログラム合成の研究に関しては「猫が黒か白かは問題ではない」という精神を持っているようです。

一緒に釣りをすることには伝統的な美徳もあります。

本当はアルゴリズム最適化ソフトは今年の夏の8月にリリースされるはずだったんですが、みんなサボってるんですよ（笑）。