🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

本論文は、大規模なケイリーグラフ上の経路探索を効率的に解決するために強化学習と拡散距離法を組み合わせ、GAP などの古典的なツールを凌駕し、対称群の直径に関する OEIS-A186783 予想に対する強力な証拠を提供するとともに、新たな理論的限界を確立し、Kaggle 課題を通じてコミュニティ参加を促す CayleyPy プロジェクトを提示する。

原著者： A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

公開日 2026-05-19

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

以下は、論文「CayleyPy RL: Pathfinding and reinforcement learning on Cayley graphs」の解説を、平易な言葉と創造的な比喩を用いて翻訳したものです。

全体像：鏡の迷路で最短の帰宅経路を見つけること

あなたは巨大で無限の迷路にいると想像してください。しかし、これは壁でできた普通の迷路ではなく、ルールでできた迷路です。一歩踏み出すたびに、特定のルールに従って位置が変化します。数学的には、これをケイリーグラフと呼びます。

この論文の目的は、特定の種類の迷路、すなわちLRX 迷路を解くことです。この迷路は、カードのシャッフル（あるいは数字の順列）のルールに基づいて構築されています。

ルール L: すべてを 1 つ左にシフトする。
ルール R: すべてを 1 つ右にシフトする。
ルール X: 最初の 2 つのアイテムを入れ替える。

課題はこうです：カードが乱雑な順序で並んでいる場合、それらを完璧な順序に戻すための、左・右・入れ替えの動きの最短の列は何か？

問題：迷路が大きすぎて人間（そして古いコンピュータ）には手に負えない

小さなカードの束であれば、人間や標準的なコンピュータプログラム（有名な数学ソフトウェアGAPなど）は解決策を見つけ出すことができます。しかし、カードの数（ $n$ ）が増えるにつれて、可能な配列の数は爆発的に増加します。

$n=20$ の場合、迷路は巨大です。
$n=100$ の場合、迷路はあまりにも大きく、その経路の数は宇宙にある原子の数よりも多くなります。

古いコンピュータプログラムは行き詰まります。彼らはすべての経路をマッピングしようとし、メモリを使い果たして諦めてしまいます。著者たちは、**人工知能（AI）**がすべての寸法をマッピングすることなく、これらの巨大な迷路を抜け出すための賢い探検家として機能するかどうかを確認したかったのです。

解決策：AI に「推測」するよう教えること

著者たちはCayleyPy RLと呼ばれるシステムを構築しました。これは迷路をナビゲートするロボットを訓練するようなものです。彼らは**強化学習（RL）**という手法を使用しました。

以下は、簡単な比喩を用いたロボットを訓練する方法です：

1. 「ウォーミングアップ」（拡散距離）
ガラスのコップにインクのしずくを落とすと想像してください。インクはランダムに広がります。特定の場所が中心からどれくらい離れているかを知りたい場合、インクがそこに到達するまでの時間を見ればわかります。

AI はまず、数百万の「ランダムウォーク」（インクの広がるようなもの）を観察して学習しました。それは最短経路を知っているわけではありませんでしたが、「距離感」を学びました。「ここにいるなら、帰宅するには通常、約 50 回のランダムなステップがかかる」というような感覚です。
これにより AI は大まかな地図を得ましたが、完璧ではありませんでした。

2. 「賢いトレーニング」（強化学習）
次に、彼らは AI をより賢くすることにしました。ランダムウォークに基づいて推測するだけでなく、深層 Q 学習という手法を使用しました。

AI がゲームをプレイしていると想像してください。一歩進むたびに「ペナルティ」が課されます。AI は、最も少ないペナルティでゴールに到達したいと考えています。
AI は異なる動きを試み、どれがゴールに近づけるかを確認し、より良い推測を行うために脳（ニューラルネットワーク）を調整しました。
革新点: 彼らは「インクの広がり」に基づく直感と「ゲームプレイ」の論理を組み合わせました。これにより、AI は単純なアルゴリズムが通常陥る行き止まり（局所最適解）に陥るのを防ぐことができました。

3. 「ビームサーチ」（探検家のチーム）
これが最も重要な部分です。1 人の探検家を迷路に送り込むと想像してください。もし間違った方向に行けば、失敗です。

代わりに、著者たちはチーム（「ビーム」）を送り出しました。
すべての交差点で、チームは分裂します。彼らは最も有望な経路 1 万本を維持し、悪い経路は捨てます。
巨大なチーム（場合によっては数百万の経路）を維持することで、たとえほとんどの探検家が迷子になったとしても、少なくとも 1 人が完璧な最短経路を見つけることを AI が保証します。

「マジックトリック」（X トリック）

著者たちは、ちょっとした面白いショートカットを発見しました。彼らのコードには、1 行のロジックが追加されました：

最初の 2 枚のカードがすでに正しい順序にある場合、それらを入れ替えない。

人間にとっては自明に思えることですが、コンピュータにとってはゲームチェンジャーでした。彼らが**「X トリック」と呼んだこの小さなルールにより、AI は100 枚**（ $n=100$ ）のカードでできた迷路を解くことができました。

トリックなしの場合: AI は約 40 枚のカードしか処理できませんでした。
トリックありの場合: 100 枚以上のカードを処理でき、約 20 枚のカードでクラッシュする古いコンピュータソフトウェア（GAP）を凌駕しました。

彼らが証明したもの（数学の部分）

単に高速なソルバーを構築するだけでなく、彼らはその AI を用いてこれらの迷路の数学に関する発見を行いました：

「神の数」の予想: 数学には、 $n$ 枚のカードの最も難しいシャッフルは、正確に $n(n-1)/2$ 回の移動を必要とするという有名な予想があります。AI は巨大な数についてこれをテストし、この予想よりも難しいシャッフルは見つかりませんでした。これは、この式が絶対的な限界であるという考えを強く支持しています。
「最長」のシャッフル: 彼らは、可能な限り最もカオスなシャッフル（「最長要素」）を特定し、それを移動に分解する方法を正確に証明しました。
新しい境界: 彼らは数学的に、迷路が特定のサイズより小さくはなり得ず、また別のサイズより大きくはなり得ないことを証明し、答えを大幅に絞り込みました。
迷路の形状: 彼らは、スタートからの距離ごとのシャッフルの数を数えると、その数は完全なベルカーブ（正規分布）に従わないことを発見しました。代わりに、それらはグンベル分布と呼ばれる奇妙で偏った形状に従います。

結果：AI と旧来の守旧派の対決

この論文は、新しい AI 手法を標準的なコンピュータ代数システムGAPと比較しています：

GAP: 約 20 枚のカードまでしか解けません。数時間から数日かかります。発見する経路はしばしば長く、非効率的です。
CayleyPy RL（AI）: 約 100 枚のカードまで解けます。はるかに高速です。理論的に可能な最短経路に非常に近い経路を見つけ出します。

まとめ

著者たちは、複雑な数学の問題を巨大な迷路として扱う賢い AI システムを構築しました。ランダムな推測と賢い学習を組み合わせ、膨大な数の「仮想探検家チーム」を送り出すことで、従来のコンピュータでは扱いきれない迷路をナビゲートすることができます。彼らはさらに、以前よりも 5 倍大きな問題を解決することを可能にする小さな「チートコード」（X トリック）を見つけ出し、同時にこれらの迷路の構造に関する新しい数学的事実を証明しました。

彼らはまた、コードと課題をKaggleというプラットフォームに公開し、他の人々に彼らの記録を破り、これらのパズルのより困難なバージョンの解決に協力するよう招待しています。

技術概要：CayleyPy 強化学習：Cayley グラフ上の経路探索と強化学習

問題定義
本論文は、極めて大規模な有限 Cayley グラフ上の経路探索問題に取り組み、特に左巡回シフト（L）、右巡回シフト（R）、および最初の 2 要素の転置（X）によって生成される対称群 $S_n$ に焦点を当てている。この構成、すなわち LRX Cayley グラフは、OEIS シーケンス A186783 に対応する。核心的な数学的課題は、群元を生成元の最短の積に分解すること（グラフにおける最短経路の発見）である。この問題は、一般的な有限 Cayley グラフに対して NP 困難である。GAP などの古典的なコンピュータ代数システムは、Schreier-Sims アルゴリズムに依存しており、これはしばしば指数関数的に長い経路を生成し、 $10^{30}$ を超えるサイズの群（ $S_n$ の場合、おおよそ $n \approx 20$ ）を処理できない。著者らは、 $10^{70}$ までのサイズ（例： $n \approx 40$ から $100$）のグラフを処理でき、かつ最適または準最適の経路を生成できる効率的な人工知能ベースのアプローチの開発を目指す。

手法
著者らは、拡散距離に基づく事前学習戦略と、特に Deep Q-Learning（DQN）を組み合わせたハイブリッド手法を提案する。

強化学習フレームワーク: 経路探索問題は、状態 $s$ から単位元 $e$ への最短経路の発見として定式化される。これはベルマン方程式を用いてモデル化され、距離関数 $d(s)$ は $d(s) = 1 + \min_{t \in N(s)} d(t)$ を満たす。標準的な DQN は、この値関数をニューラルネットワークを用いて近似するように適応される。
拡散距離による事前学習: 「スパースな報酬」問題と、標準的な DQN 初期化に内在するノイズに対処するため、著者らは「ウォームアップ」段階を導入する。ターゲットから開始するランダムウォーク（拡散）を通じて訓練データを生成する。まず、ニューラルネットワークを、これらのランダムウォークにおけるステップ数（拡散距離）を予測するように訓練する。
修正 DQN: 事前学習されたネットワークは、修正された DQN アルゴリズムを用いて微調整される。重要なのは、ベルマン更新のターゲットが、ランダムウォーク生成中に状態が初めて訪問された時点 $k$ に基づいてクリップされる点である。これにより、ネットワークが距離を過大評価することを防ぎ、訓練を安定させる。
誘導ビームサーチ: ニューラルネットワークが距離を推定するように訓練されると、それはビームサーチアルゴリズムのためのヒューリスティック関数として機能する。ビームサーチは、各ステップで最も有望な状態を固定数（ $W$ ）保持し、それらの隣接点を展開して、ネットワークの予測に基づき上位 $W$ 個を選択する。これにより、貪欲法で一般的に発生する局所最適解に陥ることを回避する。
「X 技」: LRX 生成元に対する特定のヒューリスティック修正が導入される。置換の最初の 2 要素がすでにソートされている場合、それらを交換する生成元 $X$ は隣接集合から除外される。この単一行の修正により、探索空間が劇的に減少し、混合時間が改善される。
バックトラッキングの回避: 距離推定値の分散を低減し、局所最適解での停滞を防ぐため、ランダムウォーク生成とビームサーチの両方にバックトラッキング回避の制約を組み込んでいる。

主要な貢献

アルゴリズムの進展: 本論文は、拡散距離による事前学習と修正 DQN の新奇な組み合わせを提示する。このアプローチは、標準的な DQN の限界（スパースな報酬、ノイズの多いターゲット）を克服し、古典的な手法を上回る。
性能ベンチマーク: 提案された手法は、事前知識なしに $n \approx 44$ までの LRX Cayley グラフの経路を、また「X 技」を利用することで $n \approx 100$ までの経路を成功裏に見つける。これは $n \approx 20$ に制限される GAP の能力を大幅に超える。AI 手法は、同様の $n$ において、より短い経路を生成し、GAP よりも高速に実行される。
数学的結果と仮説:
- 直径仮説: 著者らは、LRX Cayley グラフの直径が $n(n-1)/2$ であるという OEIS-A186783 の仮説を強く支持する。 $n \le 15$ については総当たり BFS により、 $n$ 最大 200 については（Kaggle 課題を通じて）AI 分解により検証され、仮説された長さより短い分解は見つからなかった。
- 最長元: 彼らは、一意の「最長元」 $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ を特定し、長さ $n(n-1)/2$ の明示的な分解を提供する。
- 境界: 本論文は、構成アルゴリズムを通じて直径の下限 $n(n-1)/2 - n/2 - 1$ と上限 $n(n-1)/2 + 3n$ を証明する。経験的アルゴリズムは、より tight な境界 $n(n-1)/2 + n/2$ を示唆する。
- 成長分布: 数値実験は、大きな $n$ において LRX グラフの成長関数が、隣接転置グラフで観測されるガウス分布とは対照的に、左に歪んだギューベル分布に従うことを示唆する。
- 混合時間: 標準的なランダムウォークの混合時間は $O(n^3)$ から $O(n^3 \log n)$ の間にあるが、著者らは「X 技」で修正されたランダムウォークはより速く混合し、時間計算量が $O(n^2)$ であると仮説する。
- スペクトル: LRX グラフのスペクトルは、一様分布に従うように見える。
オープンソースとクラウドソーシング: 著者らは「CayleyPy」プロジェクトを公開し、最長元の分解と最適アルゴリズムの発見のための Kaggle 課題を作成し、AI 界と数学界の間の協力を促進した。

結果

効率性: $n=20$ の場合、GAP は長さ 217,944 の経路を見つけるのに 41 分以上を要するのに対し、拡散距離法は最適経路（長さ 190）を 4 分未満で見つける。
スケーラビリティ: 「X 技」を用いると、システムは単一 GPU で約 8.5 時間以内に $n=100$ （グラフサイズ $\approx 10^{157}$ ）のインスタンスを解決し、長さ 16,632 の経路（仮説された直径 4,950 に対して）を見つけた。
モデル性能: 単純なモデル（多層パーセプトロン：MLP、勾配ブースティング：CatBoost/XGBoost）は、この特定のタスクにおいて、Transformer や CNN などの複雑なアーキテクチャよりもよく機能することが多い。
ビームサーチ: 経路発見の成功率はビーム幅に強く依存しており、ビームサイズが増加するにつれて超線形的な改善を示す。これは研究コミュニティにおける「アイデアの交換」に類似している。

重要性
本論文は、特に AI を活用した計算実験が、Cayley グラフに関する数学的研究を大幅に進展させ得ると主張する。AI 手法は、スケーラビリティ（はるかに大きな $n$ の処理）と解の質（より短く、準最適の経路の発見）の両面で、古典的なコンピュータ代数システムを「凌駕」し得ることを実証する。この研究は、理論的群論と実用的 AI の間のギャップを埋め、厳密な境界、成長と混合時間に関する新たな仮説、および以前は扱いが困難だった極めて大規模な状態空間における経路探索問題を解決するための枠組みを提供する。著者らはこれを、理論科学における他の複雑な計画問題への AI の応用に向けた一歩として位置づけている。