論文の概要: Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error

• arxiv url: http://arxiv.org/abs/2509.22023v1
• Date: Fri, 26 Sep 2025 07:57:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.286431
• Title: Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error
• Title（参考訳）: 効果的な試行錯誤による組合せ問題の解法をトランスフォーマーに教える
• Authors: Panagiotis Giannoulis, Yorgos Pantis, Christos Tzamos,
• Abstract要約: 本研究では,従来のニューロシンボリックアプローチと比較して,スドクのパラダイム的課題に着目し,最先端の精度(99%)を達成する。 提案手法は,単純なスドク規則の模倣学習と,Depth-First Search(DFS)探索戦略を統合する。
• 参考スコア（独自算出の注目度）: 18.209374823705446
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Despite their proficiency in various language tasks, Large Language Models (LLMs) struggle with combinatorial problems like Satisfiability, Traveling Salesman Problem, or even basic arithmetic. We address this gap through a novel approach for solving problems in the class NP. We focus on the paradigmatic task of Sudoku and achieve state-of-the-art accuracy (99\%) compared to prior neuro-symbolic approaches. Unlike prior work that used custom architectures, our method employs a vanilla decoder-only Transformer (GPT-2) without external tools or function calling. Our method integrates imitation learning of simple Sudoku rules with an explicit Depth-First Search (DFS) exploration strategy involving informed guessing and backtracking. Moving beyond imitation learning, we seek to minimize the number of guesses until reaching a solution. We provide a rigorous analysis of this setup formalizing its connection to a contextual variant of Min-Sum Set Cover, a well-studied problem in algorithms and stochastic optimization.
• Abstract（参考訳）: 様々な言語タスクに習熟しているにもかかわらず、Large Language Models (LLM) は、満足度、トラベルセールスマン問題、あるいは基本的な算術といった組合せ問題に悩まされている。 クラスNPの問題を解くための新しいアプローチによって、このギャップに対処する。 本研究では,従来のニューロシンボリックアプローチと比較して,スドクのパラダイム的課題に着目し,最先端の精度(99\%)を達成する。 カスタムアーキテクチャを使った以前の作業とは異なり、当社の手法では外部ツールや関数呼び出しを使わずに、バニラデコーダのみのトランスフォーマー(GPT-2)を採用している。 提案手法は,単純な数独規則の模倣学習と,情報的推測とバックトラッキングを含む明示的な深度ファーストサーチ(DFS)探索戦略を統合する。 模倣学習を超えて、ソリューションに到達するまで推測の数を最小化しようとします。 アルゴリズムと確率的最適化においてよく研究された問題であるMin-Sum Set Coverの文脈変種への接続を形式化したこのセットアップの厳密な解析を行う。

関連論文リスト

• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• Learning to Configure Mathematical Programming Solvers by Mathematical Programming [0.8075866265341176]
  本稿では,与えられた問題の特定の事例に対して,優れた数学的プログラミング解法構成を求める問題について論じる。 優れたソルバ構成を学ぶことの難しさは、パラメータ設定がすべて独立しているとは限らないことである。 このアプローチの第2段階でこの問題に対処し、学習した情報を用いて最適化問題を構築し、解決する。
  論文  参考訳（メタデータ） (2024-01-10T10:02:01Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Gradient Backpropagation Through Combinatorial Algorithms: Identity with Projection Works [20.324159725851235]
  ゼロあるいは未定義の解法に対する意味のある置き換えは、効果的な勾配に基づく学習に不可欠である。 本稿では, 離散解空間の幾何学を応用して, 後方パス上の負の同一性として処理する原理的手法を提案する。
  論文  参考訳（メタデータ） (2022-05-30T16:17:09Z)
• Compositional federated learning: Applications in distributionally robust averaging and meta learning [31.97853929292195]
  本稿では,新しい構成フェデレートラーニング(FL)フレームワークを解くための,効率的かつ効率的な合成フェデレートラーニング(ComFedL)アルゴリズムを提案する。 我々はComFedLアルゴリズムが$O(frac1sqrtT)$の収束率を達成することを証明した。
  論文  参考訳（メタデータ） (2021-06-21T17:08:09Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  我々は,様々なタスクを解くことを目的とした回帰関数の集合を適合させることで,マルチタスク学習と呼ばれる問題を考える。 我々の新しい定式化では、これらの関数のパラメータを2つに分けて、互いに近づきながらタスク固有のドメインで学習する。 これにより、異なるドメインにまたがって収集されたデータが、互いのタスクにおける学習パフォーマンスを改善するのに役立つ、クロス・ファーティライズが促進される。
  論文  参考訳（メタデータ） (2020-10-24T21:35:57Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)
• Meta Cyclical Annealing Schedule: A Simple Approach to Avoiding Meta-Amortization Error [50.83356836818667]
  循環型アニーリングスケジュールとMMD基準を用いた新しいメタレギュラー化目標を構築した。 実験の結果,本手法は標準的なメタ学習アルゴリズムよりもかなり優れていることがわかった。
  論文  参考訳（メタデータ） (2020-03-04T04:43:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。