技術要約：学習と探索を通じた人間のような解の理解

1. 問題提起

ユークリッド型巡回セールスマン問題（TSP）のような組合せ最適化問題は、計算量的に困難（NP困難）である一方で、人間は厳しい時間的・認知的制約の下で、最適解に近い効率でこれらを解決している。人間は通常、数学的な最適解よりわずか10%程度長いツアーしか生成しないが、この「人間らしい」パフォーマンスの背後にある具体的な認知アルゴリズムや幾何学的原理は依然として不明である。既存の計算モデルは、多くの場合、徹底的な探索（計算コストが高い）か、あるいは単純なヒューリスティック（しばしば劣悪であり、人間の構造的パターンを捉えきれない）のいずれかに依存している。中心となる課題は、TSPを効率的に解くだけでなく、人間特有の幾何学的シグネチャや系統的な偏差を再現できる計算フレームワークを特定することである。

2. 手法

2.1 大規模行動データ収集 (tsp150k)

著者らは、人間のTSPパフォーマンスに関するこれまでで最大の行動実験を実施し、tsp150kデータセットを生成した。

• 参加者: 1,107名。
• 規模: 150,000件のユニークなTSPインスタンスと、2,000万件以上の人間が生成したツアー。
• 複雑度レベル: 都市数に基づいた5つのレベル（10, 12, 15, 19, 24都市）。
• プロトコル: WeChat統合プラットフォームを介してオンラインでTSPインスタンスを解いた。制限時間は都市数の2倍に設定された（例：10都市の場合は20秒）。タスク実行中にツアーの長さにフィードバックは与えられなかった。
• データの密度: 各インスタンスには92から207の人間によるツアー（平均139）が割り当てられ、人間行動の堅牢な統計的特性化を可能にした。

2.2 計算モデリング・フレームワーク

本研究では、探索のみの手法と学習と探索のハイブリッド手法に分類される、広範な仮説空間としての計算モデルを評価した。

• 探索のみのベースライン:

  • 厳密解: Concorde (branch-and-cut) による最適解。
  • ヒューリスティック: 最近傍探索 (Nearest Neighbor)、凸包最小挿入法 (Convex Hull Cheapest Insertion)、最大内角法 (Largest Interior Angle)。
  • 緩和法: エラスティックネット (変形可能なリングに対する勾配降下法)。

• ニューラルネットワークモデル (Pointer Networks):
  著者らは、有効なツアーに対する確率分布を定義するために、アテンション機構を用いたPointer Networks（RNNの一種）を利用した。以下の4つの異なる学習レジメンをテストした：

  1. $p_{optimal}$: 最適ツアー（Concordeの解）を用いた教師あり学習。
  2. $p_{RL}$: 負のユークリッド距離を報酬として用いる強化学習 (RL)。
  3. $p_{optimal+RL}$: 最適ツアーによる教師あり事前学習に続く、RLによる微調整。
  4. $p_{human}$: 人間のツアーを直接用いた教師あり学習（経験的な上限として機能）。

• デコーディング戦略:
  訓練された方策からツアーを生成するために、3つの探索戦略を適用した：

  1. 貪欲デコーディング (Greedy Decoding): 最も確率の高い次の都市を逐次的に選択。
  2. ビームサーチ (Beam Search): 最も確率の高い完全なシーケンスの近似。
  3. Best-of-$N$ サンプリング: ランダムに$N$個の完全なツアーをサンプリングし、その中で最短のものを選択。

2.3 評価指標

モデルの性能は、モデルのツアーと人間のツアーを比較する5つのペアワイズ類似度指標を用いて、ホールドアウトテストセット（50,000インスタンス）に対して評価された：

1. エッジ重複比 (EOR): 共有されるエッジの割合。
2. 最長共通部分文字列 (LCS): 共有される連続した都市シーケンスの最長部分。
3. レーベンシュタイン距離 (LD): 一方のツアーを他方に変換するための最小編集回数。
4. フレシェ距離 (FD): 巡回順序における対応する点間の空間的隔たり。
5. ケンドールのタウ ($\tau$): 訪問順序のランク相関。

• 幾何学的分析: 人間の解の「幾何学的盆地」を特徴付けるために、8つの特定の幾何学的特徴（滑らかさ、回転角エントロピー、凸包保存、2-opt最適性など）を抽出した。

3. 主な結果

3.1 人間のパフォーマンス特性

• 人間のツアーは最適に近いが、系統的な偏差を示しており、「最適に近い幾何学的盆地」を占めている。
• 人間は初期位置での検討に有意に多くの時間を費やしており、「考えてから実行する」戦略を示唆している。
• 既訪の都市を無視した後、人間の次の都市の選択は高いレベルの局所的最適性で安定する。

3.2 モデルの性能比較

• 探索のみのモデル: 最適ツアー (Concorde) およびエラスティックネットは、単純なヒューリスティックやランダムな人間ベースラインを上回り、人間のツアーに対して高い類似性を達成した。しかし、これらは特定の人間的な劣最適性のシグネチャ（例：数学的最適解よりも低い滑らかさや弱い凸包保存）を捉えることには失敗した。
• 純粋な教師あり学習 ($p_{human}$): 人間のツアーで直接訓練されたモデルをビームサーチでデコードした場合、最も高い全体的な整合性（集計スコア: 0.600）を達成し、経験的な上限を確立した。
• 最も汎用性の高いモデル ($p_{optimal+RL}$): 人間のデータで訓練されていないモデルの中で、最適ツアーで事前学習を行い、RLで微調整したPointerNetを、Best-of-$N$ サンプリング ($N=100$) でデコードしたものが、最強の人間らしさ（集計スコア: 0.600）を達成した。
  • このモデルは、8つの特徴量において幾何学的特徴を密接に一致させ（ピアソンの $r = 0.583$）、最小の平均絶対誤差（MAE = 0.021）を達成した。
  • これにより、純粋な最適化ソルバーが見逃してしまう、人間特有の劣最適性（例：完璧ではない凸包保存）を再現することに成功した。

3.3 幾何学的盆地分析

• 人間のツアーは純粋な最適ツアーとは異なり、滑らかさや2-opt局所最適性が低いという特徴を持つ。
• $p_{optimal}$ モデルは、最適幾何領域に急速に収束しすぎてしまい、人間の偏差を見逃す。
• $p_{RL}$ モデルは、報酬の高い狭い集合に過度に集中してしまい、テスト時の探索において人間のような多様性を発見するための多様性が欠如している。
• $p_{optimal+RL}$ はバランスを取っている：教師あり事前学習が広範な幾何学的近傍のツアーに対するサポートを提供し、RLによる微調整が、多様性を排除することなく経路を短縮するよう分布をバイアスさせる。これにより、Best-of-$N$ サンプリングが人間行動と一致する領域へと収束することが可能になる。

4. 主な貢献

1. tsp150k データセット: 150,000件のTSPインスタンスと2,000万件以上の人間によるツアーを含む、大規模で高品質なデータセットの作成。これにより、人間の行動の体系的な特性化が可能となった。
2. 人間らしいメカニズムの特定: 人間のような解は、単なる最適ツアーの模倣ではなく、構造化された教師あり学習（幾何学的知識の獲得）、強化学習（効率性の最適化）、およびテスト時の探索（Best-of-$N$ サンプリング）の特定の組み合わせから生じることを示した。
3. 幾何学的特性化: 人間の解のための「幾何学的盆地」を定義し、人間が最適解と構造的特性を共有しつつも、標準的なヒューリスティックや純粋な最適化ソルバーが捉えられない系統的な偏差（滑らかさや凸包保存におけるもの）を保持していることを示した。
4. 認知モデリング・フレームワーク: 複雑な組合せ空間における人間の問題解決は、2段階のプロセスとしてモデル化できることを提案した：高品質な例からの構造的知識の獲得（模倣）と、経験に基づくフィードバックによる洗練（RL）、そしてテスト時における熟考（探索）。

5. 意義と主張

本論文は、組合最適化における人間のようなパフォーマンスは、固定された手作りのヒューリスティックからではなく、学習と探索を統合した計算アーキテクチャから生じるものであると主張している。具体的には：

• 学習と探索の相乗効果: 人間の行動を最も正確にモデル化できるのは、人間のデータを直接模倣したモデルではなく、最適データで訓練され、RLによって洗練され、探索によってデコードされたモデルである。これは、人間が質の高い例への露出を通じて広範な幾何学的知識を獲得し、経験に基づくフィードバックを通じてこれらの表現を洗練させている可能性を示唆している。
• テスト時計算の役割: 本研究は、「テスト時計算」（例：Best-of-$N$ サンプリング）が認知モデリングにおいて極めて重要であり、しばか見落とされているコンポーネントであることを強調している。これにより、静的なニューラルネットワークが、重みを変更することなく、人間のような解の多様性を生成することが可能となり、これは大規模言語モデルにおけるChain-of-Thought（思考の連鎖）推論のようなメカニズムと並行している。
• 汎用性: 本研究の結果は、AIの「苦い教訓（bitter lesson）」、すなわち固定されたヒューリスティックよりも学習と計算に依存するという教訓が、人間の認知にも適用されることを示唆している。複雑な問題に対する人間の解は、経験から学習し、探索を通じて計算を活用する汎用的な手法の認知的アナロジーを反映している可能性がある。

著者らは、彼らのモデルが人間のツアーを直接訓練することなく人間の幾何学を再現しているものの、人間の教師あり学習のための「最適デモンストレーション」の源泉は未解決の問いであり、より単純なインスタンスからのカリキュラム学習などが関わっている可能性があると控えめに述べている。