論文の概要: KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems

• arxiv url: http://arxiv.org/abs/2509.15239v1
• Date: Wed, 17 Sep 2025 15:44:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-22 18:18:10.809583
• Title: KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems
• Title（参考訳）: KNARsack: Pseudo-Polynomial問題の解法をニューラルネットワークで教える
• Authors: Stjepan Požgaj, Dobrik Georgiev, Marin Šilić, Petar Veličković,
• Abstract要約: 我々は、古典的なアルゴリズムをブリッジして最適化する擬似多項式問題であるKnapsackを解くことができるニューラルネットワーク推論器を構築した。 我々のニューラルアルゴリズム推論器は、Knapsack問題のための2相パイプラインを忠実に追従するように設計されている。
• 参考スコア（独自算出の注目度）: 2.0952603334062436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural algorithmic reasoning (NAR) is a growing field that aims to embed algorithmic logic into neural networks by imitating classical algorithms. In this extended abstract, we detail our attempt to build a neural algorithmic reasoner that can solve Knapsack, a pseudo-polynomial problem bridging classical algorithms and combinatorial optimisation, but omitted in standard NAR benchmarks. Our neural algorithmic reasoner is designed to closely follow the two-phase pipeline for the Knapsack problem, which involves first constructing the dynamic programming table and then reconstructing the solution from it. The approach, which models intermediate states through dynamic programming supervision, achieves better generalization to larger problem instances than a direct-prediction baseline that attempts to select the optimal subset only from the problem inputs.
• Abstract（参考訳）: ニューラルアルゴリズム推論(Neural Algorithmic reasoning, NAR)は、古典的なアルゴリズムを模倣することによって、アルゴリズム論理をニューラルネットワークに埋め込むことを目的とした成長分野である。 この拡張抽象化では、古典的アルゴリズムと組合せ最適化を橋渡しする擬似多項式問題であるKnapsackを解くことができるが、標準のNARベンチマークでは省略できるニューラルネットワーク推論器を構築する試みについて詳述する。 我々のニューラルアルゴリズム推論器は、動的プログラミングテーブルを最初に構築し、その解を再構成するKnapsack問題のための2相パイプラインを忠実に追従するように設計されている。 動的プログラミングの監督を通じて中間状態のモデル化を行うこのアプローチは、問題入力のみから最適なサブセットを選択しようとする直接予測ベースラインよりも、より大きな問題インスタンスへのより優れた一般化を実現する。

関連論文リスト

• Primal-Dual Neural Algorithmic Reasoning [14.433843795079083]
  NAR(Neuralic Reasoning)は、ニューラルネットワークをトレーニングして古典的なアルゴリズムをシミュレートし、アルゴリズムデータに対する構造化および解釈可能な推論を可能にする。 本稿では,古典近似アルゴリズムである原始双対パラダイムを基盤としたフレームワークを提案する。 その結果,本モデルはシミュレーションだけでなく,複数のタスクに対する近似アルゴリズムよりも優れていることがわかった。
  論文  参考訳（メタデータ） (2025-05-29T23:20:07Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。 私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。 以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-18T13:59:02Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。 本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
  論文  参考訳（メタデータ） (2022-11-22T16:30:33Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)

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

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