論文の概要: Primal-Dual Neural Algorithmic Reasoning

• arxiv url: http://arxiv.org/abs/2505.24067v1
• Date: Thu, 29 May 2025 23:20:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-02 19:47:52.700822
• Title: Primal-Dual Neural Algorithmic Reasoning
• Title（参考訳）: 原始2次元ニューラルアルゴリズム推論
• Authors: Yu He, Ellen Vitercik,
• Abstract要約: NAR(Neuralic Reasoning)は、ニューラルネットワークをトレーニングして古典的なアルゴリズムをシミュレートし、アルゴリズムデータに対する構造化および解釈可能な推論を可能にする。 本稿では,古典近似アルゴリズムである原始双対パラダイムを基盤としたフレームワークを提案する。 その結果,本モデルはシミュレーションだけでなく,複数のタスクに対する近似アルゴリズムよりも優れていることがわかった。
• 参考スコア（独自算出の注目度）: 14.433843795079083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural Algorithmic Reasoning (NAR) trains neural networks to simulate classical algorithms, enabling structured and interpretable reasoning over complex data. While prior research has predominantly focused on learning exact algorithms for polynomial-time-solvable problems, extending NAR to harder problems remains an open challenge. In this work, we introduce a general NAR framework grounded in the primal-dual paradigm, a classical method for designing efficient approximation algorithms. By leveraging a bipartite representation between primal and dual variables, we establish an alignment between primal-dual algorithms and Graph Neural Networks. Furthermore, we incorporate optimal solutions from small instances to greatly enhance the model's reasoning capabilities. Our empirical results demonstrate that our model not only simulates but also outperforms approximation algorithms for multiple tasks, exhibiting robust generalization to larger and out-of-distribution graphs. Moreover, we highlight the framework's practical utility by integrating it with commercial solvers and applying it to real-world datasets.
• Abstract（参考訳）: Neural Algorithmic Reasoning (NAR)は、ニューラルネットワークを訓練して古典的なアルゴリズムをシミュレートし、複雑なデータに対する構造化された解釈可能な推論を可能にする。 従来の研究は主に多項式時間解問題に対する正確なアルゴリズムの学習に重点を置いてきたが、NARを難しい問題に拡張することは未解決の課題である。 本研究では,効率的な近似アルゴリズムを設計するための古典的手法である原始双対パラダイムに基づく汎用NARフレームワークを提案する。 原始変数と双対変数の両部表現を利用することで、原始双対アルゴリズムとグラフニューラルネットワークのアライメントを確立する。 さらに、モデルの推論能力を大幅に向上させるために、小さなインスタンスからの最適解を組み込んだ。 実験結果から,本モデルは複数のタスクに対する近似アルゴリズムよりも優れており,より大きく分布しないグラフへの頑健な一般化が示されることがわかった。 さらに、商用のソルバと統合し、現実世界のデータセットに適用することで、フレームワークの実用性を強調します。

関連論文リスト

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
  我々は、中間的監督に訴えることなく、入出力ペアからのみニューラルネットワーク推論を学ぶことに集中する。 我々は、アルゴリズムの軌跡にアクセスできることなく、モデルの中間計算を正規化できる自己教師対象を構築する。 CLRSic Algorithmic Reasoning Benchmarkのタスクにおいて,提案手法はトラジェクトリを教師する手法と競合することを示す。
  論文  参考訳（メタデータ） (2023-06-23T09:57:44Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。 私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。 以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-18T13:59:02Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)

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

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