Stabilized Best-of-$K$ Training for Neural Combinatorial Optimization

巨大で絡まり合った紐の結び目を解こうとしているところを想像してみてください。しかし、全体像を一度に見ることはできません。一本の端を引っ張り、それがどこへ行くかを確認し、それからまたやり直す必要があります。これは、「ニューラル組合せ最適化（Neural Combinatorial Optimization）」という分野における日常的な苦闘です。この分野では、コンピュータ科学者が、巡回セールスマン問題（多くの都市を最短ルートで訪問する方法を見つける問題）のような複雑なパズルを解くために、人工知能に教え込みます。目標はシンプルです。完璧な経路を見つけることです。しかし、その経路は隠されており、コンピュータは推測しなければなりません。

推測の精度を高めるために、これらのコンピュータは「強化学習（Reinforcement Learning）」という手法を用います。これは犬の訓練に似ています。犬が「お座り」をすれば、ご褒美（報酬）がもらえます。もし飛び跳ねたら、何ももらえません。時間が経つにつれて、犬はお座りをすることを学びます。AIの世界では、この「犬」はニューラルネットワークであり、「ご褒美」は、その解がどれほど優れているかに基づくスコアです。POMO（Policy Optimization with Multiple Optima）と呼ばれる人気のある手法は、AIに一度に多くの異なる開始地点からパズルに挑戦させます。これは、最短経路を見つけるために10人の異なる探検家を送り出すようなものです。通常、AIはこれらすべての探検家の平均的なパフォーマンスから学習します。しかし、「リーダー報酬（Leader Reward）」と呼ばれる新しいアイデアは、グループの中のたった一人の最も優れた探検家に特別な注意を払い、その「リーダー」をスター選手として扱うべきだと示唆しました。

さて、あなたがパズルを解くための探検家チームを雇っていると想像してください。ただし、あなたは彼らが持ち帰った中で「最高の地図」だけを残すという厳格なルールを持っています。新しい実験は、興味深い問いを投げかけます。もし、100枚のうち上位8枚の地図しか残さないと分かっている場合、チームを「ただ一人の最高の人」になるよう訓練すべきでしょうか、それとも「トップ8に入り得る誰か」になるよう訓練すべきでしょうか？ これこそが、独立した研究者であるメルヴィーナ・ジョリー（Melveena Jolly）とミドゥン・ザビエル（Midhun Xavier）による最近の研究の核心です。彼らは新しいタイプの探検家を発明したり、新しいパズルを作ったりしたわけではありません。代わりに、既存のAIの訓練ルールを微調整することで、展開時にチームがより賢くなるかどうかを検証したのです。

実験： 「ベスト・オブ・エイト」のための訓練

研究者たちは、TSP-100（100都市を訪問する）という古典的なパズルで訓練された標準的なAIセットアップを使用し、特定のテストを行いました。彼らは、AIがどのようにミスから学ぶかを変更することが、AIが複数の解を生成してその中から最良のものを選択する際に役立つかどうかを確認したいと考えました。

従来の方法（「リーダー報酬」と呼ばれます）では、AIは100回の試行の中で見つけた単一の最高解に執着するように訓練されていました。それはまるで、コーチが「一位になった人だけが重要だ！他の奴らは帰れ！」と叫んでいるようなものです。著者たちが「安定化されたベスト・オブ・K（Stabilized Best-of-K）」と呼ぶ新しい手法は、このコーチの声を変えました。全員を無視して勝者だけを見る代わりに、新しいコーチはこう言いました。「もし君がトップ8に入ったら、ご褒美をあげよう！もし9位以下なら、何もあげないよ」。ここでの「K」は、この数字の「8」を指しています。また、研究者たちは、訓練中の数値が異常になったりノイズが大きくなったりしないようにするための数学的なセーフティネットである「スタビライザー（安定化装置）」も追加しました。

彼らが発見したこと： ゲームによる違い

結果は、「素晴らしいニュース」と「状況による」という混合したものでした。

まず、研究者たちは、新しいシステムが標準的なゲームにおいて旧来のシステムと互角に戦えるかどうかを確認しました。特定のデコーディング（AIの答えを読み取る方法）を用いて、従来の「100回の開始、ベストを一つ選択」という方法を用いたとき、新システムは以前の記録である7.766とほぼ同じスコアである7.7662を記録しました。これにより、彼らが同じルールに従っており、何も壊していないことが証明されました。

しかし、本当の魔法は、新しい訓練に合わせてゲームのルールを変更したときに起こりました。AIに8つの独立した解を生成させ、その中からベストの一つを選ぶ（「ベスト・オブ・8」シナリオ）よう求めたとき、「安定化されたベスト・オブ・K」法が勝利しました。彼らが行ったすべてのテスト実行において、新しい手法は旧来の手法よりも短い経路を見つけ出しました。平均して、新しい手法はコスト（経路の長さ）を約0.25%削減しました。これほど小さく聞こえるかもしれませんが、これらのパズルの世界では、わずかな距離を削ることさえ大きな意味を持ちます。それは、AIのパフォーマンスを理論上の「完璧な」解に近づけたのです。

しかし、ここにひねりがあります。新しい手法は、あらゆる状況における万能薬ではありません。

• もし一つだけ選ぶなら： AIがたった一つの解しか選べない（Best-of-1）場合、従来の「リーダー報酬」法の方が実際には優れていました。
• もし大量に選ぶなら： AIに128個の解を選ばせた場合、新しい手法は依然としてわずかに優れていましたが、選択肢の数が増えるにつれて、その優位性は小さくなりました。
• 異なるデコーダーを使うなら： AIの回答を読み取る別の方法（「オーグメンテッド・グリーディ」と呼ばれます）を使用したとき、再び旧来の方法の方がわずかに優れていました。

結論

では、これらはすべて何を意味しているのでしょうか？ 研究者たちは、もしあなたが少数の選択肢（例えば8つ）を生成してその中からベストを選ぶというAIを使用する計画があるなら、AIに単なる「ナンバーワン」を目指させるのではなく、「トップ8」を目指すよう教えることが賢明な策であることを見出しました。それは、単一のスーパースターではなく、強力なスクワッド（集団）を作るようチームを訓練することに似ています。

しかし、著者たちは過剰な宣伝を避けるよう細心の注意を払っています。彼らは、これがすべてを解決する「最先端（State-of-the-art）」の画期的な進歩ではないことを明示しています。これは、特定のセットアップに対する特定の改善です。彼らは、パターンを見るには十分ですが、それが永遠に機能することを証明するには不十分な、わずか3つの「シード（乱数の開始点）」に対してのみテストを行いました。また、彼らの手法は数学的な完全な証明というよりも、一種の「エンジニアリングのレシピ」であることも認めています。

要約すると、この研究は、もしあなたがルーティングパズルを解くためのAIを構築しており、かつ、勝者を選ぶ前に数回試行させる予定があるなら、AIに「チャンピオン」ではなく「トップクラスの候補者」になるよう教えるべきであることを示唆しています。しかし、もしチャンスが一度しかない場合や、膨大な数の試行を行う場合は、従来の方法が依然として最善である可能性があります。これは、AIの世界の特定の領域における、ニュアンスを含んだ、有用な微調整であり、すべてを変えるような革命ではありません。