論文の概要: Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms

• arxiv url: http://arxiv.org/abs/2505.17190v1
• Date: Thu, 22 May 2025 18:01:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:33.638911
• Title: Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms
• Title（参考訳）: トロピカルアテンション: 組合せアルゴリズムのためのニューラルアルゴリズム推論
• Authors: Baran Hashemi, Kurt Pasque, Chris Teska, Ruriko Yoshida,
• Abstract要約: 本稿では,熱帯幾何の最大半減期で機能する新しい注意関数であるトロピカルアテンションを紹介する。 熱帯の注意は、ソフトマックスから外れたシャープでスケール不変な推論を復元することを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic programming (DP) algorithms for combinatorial optimization problems work with taking maximization, minimization, and classical addition in their recursion algorithms. The associated value functions correspond to convex polyhedra in the max plus semiring. Existing Neural Algorithmic Reasoning models, however, rely on softmax-normalized dot-product attention where the smooth exponential weighting blurs these sharp polyhedral structures and collapses when evaluated on out-of-distribution (OOD) settings. We introduce Tropical attention, a novel attention function that operates natively in the max-plus semiring of tropical geometry. We prove that Tropical attention can approximate tropical circuits of DP-type combinatorial algorithms. We then propose that using Tropical transformers enhances empirical OOD performance in both length generalization and value generalization, on algorithmic reasoning tasks, surpassing softmax baselines while remaining stable under adversarial attacks. We also present adversarial-attack generalization as a third axis for Neural Algorithmic Reasoning benchmarking. Our results demonstrate that Tropical attention restores the sharp, scale-invariant reasoning absent from softmax.
• Abstract（参考訳）: 組合せ最適化問題に対する動的プログラミング(DP)アルゴリズムは、その再帰アルゴリズムにおいて最大化、最小化、古典的な加算を行う。 関連値関数は、最大値 + 半環の凸多面体に対応する。 しかし、既存のニューラルネットワーク推論モデルは、滑らかな指数重み付けがこれらの鋭い多面体構造を曖昧にし、アウト・オブ・ディストリビューション(OOD)の設定で評価すると崩壊するソフトマックス正規化ドット積の注意に依存している。 本稿では,熱帯幾何の最大半減期においてネイティブに機能する新しい注意機能である熱帯アテンションを紹介する。 我々は,DP型組合せアルゴリズムの熱帯回路にトロピカルアテンションが近似可能であることを証明した。 そこで我々は,Tropical Transformer を用いることで,アルゴリズム的推論タスクにおいて,長さ一般化と値一般化の両面で経験的 OOD 性能が向上し,ソフトマックスベースラインを越えつつ,敵攻撃下で安定に保たれることを提案する。 また,ニューラルネットワーク推論ベンチマークの第3軸として,逆攻撃一般化を提案する。 その結果、熱帯の注意は、ソフトマックスから外れた鋭くスケール不変な推論を復元することを示した。

関連論文リスト

• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  我々はロバスト成分分析のためのアルゴリズムを設計する(A) 行列を低主行列とスパース主行列の和に分解する。
  論文  参考訳（メタデータ） (2023-07-12T03:48:26Z)
• EM's Convergence in Gaussian Latent Tree Models [22.987933817370305]
  人口のログライクな独特な非自明な点は、その大域的な最大点であることを示す。 予測最大化アルゴリズムは、単一の潜在変数の場合に収束することが保証される。
  論文  参考訳（メタデータ） (2022-11-21T23:12:58Z)
• Langevin dynamics based algorithm e-TH$\varepsilon$O POULA for stochastic optimization problems with discontinuous stochastic gradient [6.563379950720334]
  我々は,不連続勾配による最適化問題を解くために,e-TH$varepsilon$O POULAと呼ばれる新しいランゲヴィン力学に基づくアルゴリズムを導入する。 金融と保険の3つの重要な応用として、多周期ポートフォリオ最適化、多周期ポートフォリオ最適化におけるトランスファーラーニング、保険請求予測がある。
  論文  参考訳（メタデータ） (2022-10-24T13:10:06Z)
• Neural Basis Functions for Accelerating Solutions to High Mach Euler Equations [63.8376359764052]
  ニューラルネットワークを用いた偏微分方程式(PDE)の解法を提案する。 ニューラルネットワークの集合を縮小順序 Proper Orthogonal Decomposition (POD) に回帰する。 これらのネットワークは、所定のPDEのパラメータを取り込み、PDEに還元順序近似を計算する分岐ネットワークと組み合わせて使用される。
  論文  参考訳（メタデータ） (2022-08-02T18:27:13Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks [0.0]
  本稿では,Langevinベースのアルゴリズムを新たに導入し,一般的な適応的消滅アルゴリズムの欠点の多くを克服する。 特に、この新しいクラスのアルゴリズムの収束性についての漸近解析と完全な理論的保証を提供し、TH$varepsilon$O POULA(あるいは単にTheoPouLa)と名付けた。
  論文  参考訳（メタデータ） (2021-05-28T15:58:48Z)
• Intermediate Layer Optimization for Inverse Problems using Deep Generative Models [86.29330440222199]
  ILOは、深層生成モデルを用いて逆問題を解決するための新しい最適化アルゴリズムである。 提案手法は,StyleGAN-2 や PULSE で導入した最先端手法よりも幅広い逆問題に対して優れていることを示す。
  論文  参考訳（メタデータ） (2021-02-15T06:52:22Z)
• Algorithmic Complexities in Backpropagation and Tropical Neural Networks [0.0]
  トロピカル算術とトロピカル代数幾何学の観点で人工ニューラルネットワークを紹介します。 熱帯算術は通常の乗算の複雑さがないため、アルゴリズムの複雑さは通常のバックプロパゲーションよりも実質的に低いことを検証します。
  論文  参考訳（メタデータ） (2021-01-03T22:19:17Z)
• 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)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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