A*を超えて: Transformerを活用したより優れた計画立案

 (arxiv.org)
2 ポイント 投稿者 GN⁺ 2024-02-25 | 1件のコメント | WhatsAppで共有
  • TransformerとLLMは対話・画像理解・コード補完では強力だが、多段階計画と高次推論では安定した性能を出しにくい
  • この論文は、計画課題と最適解法をトークン列にし、A*が問題を解く実行トレースまで学習データに含める
  • SearchformerはA*の探索過程をまず模倣した後、最適計画を維持しつつ、より短い探索シーケンスを生成するよう微調整される
  • Sokoban実験でSearchformer系列モデルはテスト課題の93.7%を解決し、A*基準実装より平均26.8%少ない探索ステップを使用した
  • 実行トレースは生成シーケンスを**10×~100×**増やす負担があるが、より大きなsolution-onlyモデルより少ない学習シーケンスでも未知の課題で最適計画をより頻繁に生成する

Transformerが得意なことと弱い計画課題

  • Transformerベースのアーキテクチャは複数のタスクで高い性能を示す
    • 人間レベルの対話
    • 高品質な画像理解
    • 動画生成
    • マルチモーダル生成
    • コード補完
  • インターネット規模のデータで学習されたLLMのようなモデルは、実際のユースケースでうまく汎化できる
  • しかし、計画および推論課題では依然として限界が残っている
    • LLMは多段階計画課題で不十分な面を見せる
    • 高次推論の実行でも困難が現れる

段階的思考プロンプトの限界

  • 最近のアプローチは、Transformerが中間の「思考」を生成してから答えるよう促し、性能向上を図っている
  • **Chain-of-Thought(CoT)プロンプティングとTree-of-thoughts(ToT)**は、モデルが段階的に「考える」ことを促進する
  • こうした手法はしばしば効果的だが、self-enforcingのような理由で、かえって性能を下げることもある
  • あるデータセットでうまくいった方法が、別のデータセットでは失敗することがある
    • 空間推論と数学推論のように、必要な推論の種類が変わる場合がその例である
  • TransformerとLLMに計画、多段階意思決定、推論を安定して実行させる方法は、依然として活発な研究テーマである

A*探索ダイナミクスを学習データに入れる方法

  • このアプローチは、Transformerが複雑な計画課題をより堅牢に解けるよう学習させることに焦点を当てる
  • モデルはLLMのように、単語列が与えられたとき次の単語を予測するよう学習される
  • 実験は、合成言語と合成語彙を用いる合成生成データセットで行われる
  • 計画課題と最適解法計画は、トークンと呼ばれる単語列として表現される
  • A*が実行した計算過程は、実行トレーストークン列として記録される
    • 実行トレースは、A*の探索ダイナミクスを含むシーケンスデータセットを構成する
    • Transformerは、探索で拡張されたシーケンスを通じて、A*の探索ダイナミクスと最適計画を同時にエンコードしたトークン列を生成するよう学習される

Searchformerの学習手順

  • 最終モデルであるSearchformerは2段階で作られる
    • まずTransformerがA*の探索過程を模倣するよう学習される
    • その後、最適計画を出力しつつ、より少ない探索ステップで計画を見つけるよう微調整される
  • この過程はsearch dynamics bootstrappingと呼ばれる
  • 目標は、A*基準実装より少ない探索ステップで複雑な計画課題を解くTransformerを得ることである

Sokoban実験と汎化性能

  • SokobanパズルでSearchformer系列モデルは、全テスト課題の**93.7%**を解決した
  • 平均探索ステップはA*基準実装より26.8%少ない
  • 課題の複雑さ、データセット規模、モデル規模を統制した実験で、実行トレースを含める効果が確認された
  • 実行トレースを学習データに入れると、生成シーケンス長は**10×~100×**増加する
  • それでも独立したテスト課題セットでは性能が向上する
  • search-augmentedモデルは、より大きなsolution-onlyモデルより学習シーケンスが10分の1でも、未知の課題で最適計画をより頻繁に生成する
    • search-augmentedモデルは、課題記述、解法、実行トレースを含むデータで学習される
    • solution-onlyモデルは、課題記述と課題解法のみを含むシーケンスで学習される
  • この結果は、A*の探索ダイナミクスをTransformerの学習過程に含めると、計画課題の性能を高められることを示している

関連記事

1件のコメント

 
GN⁺ 2024-02-25
Hacker News の意見

  • ロボットのモーションプランニングにトランスフォーマーを使う、さらに興味深い研究もあった 0
    ロボットアームを A 地点から B 地点へ移動させつつ衝突を避ける問題は、高次元かつ連続的なので非常に難しく、従来のプランニング手法は計算量が大きいわりに性能もあまり良くない
    そのためロボットの動きが「不自然」に見えたり、ロボットが私たちの望むさまざまな作業をうまくこなせなかったりする理由の一つになっているが、このアプローチはほぼ最適な経路をより速く計画でき、他の手法ともかなり競争力がありそうに見える

  • 研究の方向へ進む前に、ゲームグラフ／経路探索向けの A* 最適化である修正 J* アルゴリズムを試したのか気になる
    興味がある人は Game AI Pro 2 に載っている 0

    • 関連して https://github.com/anvaka/ngraph.path もある
    • 公平に見れば、論文の終盤で彼らの経路探索器はまだ最先端手法と競える水準ではないと述べている
      この論文は、トランスフォーマーが実行トレースをどれだけうまく予測できるか、たとえば JIT コンパイラのような場合に、そしてそれが経路探索のような場面でヒューリスティック改善に役立つかをテストしている
      ただしトランスフォーマーは遅いので、慎重に見ることになる
    • これらの本は好きだし、Steve Rabin が作業を続けているのもうれしいが、電子書籍が 120 ドルというのは予想外だ

  • 計画問題はすでにグラフ探索、SAT ソルバー、オペレーションズ・リサーチ、Prolog のような確立された手法がうまく扱っている
    通常の核心は、複数の可能な代替案の間での最適化だが、トランスフォーマーがそこに適しているのかはよく分からない
    LLM 系の手法の役割は、自然言語の説明を実行可能なプログラムへ翻訳する側によりありそうだが、Prolog もそもそも古典的な自然言語処理のために設計されたものなので、すでにかなり近い

    • 似た目的で Prolog と LLM を比較してみると面白そうだ

  • 機械翻訳は以前、探索を使う複雑な文法デコーディングを必要としていたが、今でははるかに単純で、事実上探索を必要としないデコーディングとしてトランスフォーマーを使っている
    いまや完全な再帰構造にまで進めるかもしれない
    現在最高水準の予測モデルでニューラルアーキテクチャ探索（NAS）のヒューリスティックを学習し、transformer や mamba より優れた新しいニューラルネットワークブロックを見つけようという話だ

    • 「言語学者を解雇するたびに、音声認識器の性能は上がる。」— Frederick Jelinek
    • 結局、技術を開発する人々でさえ、もはや動作原理を理解できない世界に入っていくことになるかもしれない
      シンギュラリティが来る…

  • Sokoban 系のゲームに興味があるなら https://thinky.gg を見るとよい
    Sokopath という面白いSokoban の変種と、A 地点から B 地点まで最短手数で行くことを目標にした Pathology という別の NP 困難な変種がある
    コミュニティでは複数のソルバーを作ろうとしていたが、グリッドが 5x5 を超えると非常に難しくなり、thinky コミュニティは simulated annealing によって最大手数が非常に大きい興味深いレベルも見つけ出した

  • 「標準 A* 探索より探索ステップを 26.8% 削減」
    つまり Sokoban では、最先端からは程遠い A* より少し良い程度ということだ（[https://festival-solver.site/](https://festival-solver.site/））
    この論文の何が印象的なのか、なぜ Hacker News に上がったのか分からない

    • A* は、自分が明示した特定の制約の下では最適な探索アルゴリズムなので、それ以上よくすることはできない
      しかし探索対象のドメインに利用可能な別の制約があれば、A* より良くできる
      たとえば Jump Point Search は、特定の方法でしか移動できないグリッド探索の性質を利用する
      基盤となるドメインの特殊な性質を人間が手作業で分析しなくても、「自動的に」効果的に活用する汎用探索アルゴリズムを作れるなら、有用ではないかと思う
    • トランスフォーマーで標準的な A* 探索より良い、まずまずの解法に到達したからだ
      A* は「素朴な」ベースラインに近く、彼らはアルゴリズム設計を直接考えたわけではない
      単純なエンコーダー・デコーダー型トランスフォーマーがこれほどできるという点はかなり印象的だ
    • 要旨の最初の行にすぐ出ている
      “Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ...”
      この論文は意思決定にトランスフォーマーを使う例なので興味深く、今すぐ A 水準*かどうかにはあまり関心がない
    • HN に上がったのは、コミュニティが気に入ったからだ
    • トランスフォーマーが次トークン予測だけでなく、あらゆる学習課題に適用可能な完全に汎用的なアプローチだという、トランスフォーマーの不合理な有効性を裏付ける証拠がまた一つ出たということだ
      もちろんその仮説には強い版と弱い版があり、強い版はおそらく事実ではないだろうが、自然が物事を学ぶ「一つの真の方法」に近づいているように見える限り、重要なニュースに見える

  • トランスフォーマーが計画できるなら、汎用人工知能にはより良い教育だけが必要だという意味かもしれない

    • 全探索を近似することは論理や因果性ではない
    • 必要なピースははるかに多く、エージェンシーが大きな部分を占める
      オンライン学習も必要だし、そのほかにも複数の層がさらに必要だ
    • 予測可能な未来は、ますます多くのデータを与えて幻覚を防ごうとする方向である可能性が高い

  • 聴覚型の学習者向けに、この論文を要約オーディオブック形式にしたものがある
    https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f

  • A* や Focal search、各種整数線形計画法系のような離散アルゴリズムに、学習されたヒューリスティックを使うことには非常に楽観的だ
    CPLEX のような現代の離散最適化ライブラリのほとんどで、性能差はヒューリスティックとチューニングによって説明される
    よく理解された最適探索ルーチンをエンドツーエンドの学習アプローチで置き換えるのはあまり納得できないが、それは余計な心配かもしれない
    ただ、著者たちはその機会を逃したように見える

    • 単にトランスフォーマーと AI 周辺のバブル／誇張効果のように見える
      自分もトランスフォーマーで三目並べを解いて、VC の資金を申請してみようかと思う
      数年後には、実際のコードが AI よりどれほど効率的かを、みんなが記事にしているかもしれない ;)
    • 同意する
      許容可能なヒューリスティックを学習すれば最悪ケースの性能を維持でき、これこそが常にこれらのアルゴリズムの基準だった
      平均や p99 のケースではより速いが、最悪ケースの保証を提供できない解法を見つけることは、まったく珍しくない

  • ディープラーニングによってよりよく実行できるようになった古典的アルゴリズムや NP 完全問題の一覧を、誰かが整理しているのか気になる

    • 参考までに、「AI」が最悪ケースで最先端手法よりうまくやるNP 完全問題の一覧を書いてみると:
    • 私の理解では、まだ非常に活発な研究段階であり、本番環境にデプロイされた明確な勝利はまだない