論文の概要: Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms
- arxiv url: http://arxiv.org/abs/2505.17190v2
- Date: Thu, 23 Oct 2025 08:31:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 03:08:06.526839
- Title: Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms
- Title（参考訳）: トロピカルアテンション: 組合せアルゴリズムのためのニューラルアルゴリズム推論
- Authors: Baran Hashemi, Kurt Pasque, Chris Teska, Ruriko Yoshida,
- Abstract要約: 本稿では,注意核を熱帯射影空間に引き上げる,熱帯幾何学に基づく注意機構である熱帯注意機構を紹介する。
本稿では,熱帯アテンション(Tropical Attention, 熱帯アテンション)が, 摂動騒音に対する強い頑健さと, 長さと値の両方において, より強い分布一般化をもたらすことを示す。
初めて、PTIME問題以外の神経推論をNP-hardおよびNP-complete問題に拡張する。
- 参考スコア（独自算出の注目度）: 1.43494686131174
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Can algebraic geometry enhance the sharpness, robustness, and interpretability of modern neural reasoning models by equipping them with a mathematically grounded inductive bias? To answer this, we introduce Tropical Attention, an attention mechanism grounded in tropical geometry that lifts the attention kernel into tropical projective space, where reasoning is piecewise-linear and 1-Lipschitz, thus preserving the polyhedral decision structure inherent to combinatorial reasoning. We prove that Multi-Head Tropical Attention (MHTA) stacks universally approximate tropical circuits and realize tropical transitive closure through composition, achieving polynomial resource bounds without invoking recurrent mechanisms. These guarantees explain why the induced polyhedral decision boundaries remain sharp and scale-invariant, rather than smoothed by Softmax. Empirically, we show that Tropical Attention delivers stronger out-of-distribution generalization in both length and value, with high robustness against perturbative noise, and substantially faster inference with fewer parameters compared to Softmax-based and recurrent attention baselines. For the first time, we extend neural algorithmic reasoning beyond PTIME problems to NP-hard and NP-complete problems, paving the way toward sharper and more expressive Large Reasoning Models (LRMs) capable of tackling complex combinatorial challenges in phylogenetics, cryptography, particle physics, and mathematical discovery.
- Abstract（参考訳）: 代数幾何学は、数学的に基底付けられた帰納バイアスを装備することにより、現代の神経推論モデルのシャープネス、ロバストネス、解釈可能性を高めることができるか?
これに対応するために、熱帯幾何学に基づく注意機構であるトロピカル・アテンション(Tropical Attention)を導入する。これは、注意核を熱帯射影空間に上げ、推論は片方向線形で 1-Lipschitz であり、組合せ的推論に固有の多面的決定構造を保存する。
我々は,MHTA(Multi-Head Tropical Attention, マルチヘッド熱帯注意)が熱帯の回路を概ね近似し, 構成による熱帯性推移的閉鎖を実現し, 繰り返し機構を起動することなく多項式資源境界を実現することを証明した。
これらの保証は、なぜ誘導される多面的決定境界がSoftmaxによって滑らかにされるのではなく、シャープでスケール不変であるのかを説明する。
実験により,Tropical Attentionは,長さと値の両方において,摂動騒音に対する強い頑健性を持ち,Softmaxベースや繰り返しの注意ベースラインに比べてパラメータが少なく,かなり高速な推論を実現することを示した。
初めて、PTIME問題以外のニューラルネットワーク推論をNP-hardおよびNP-complete問題に拡張し、系統学、暗号学、素粒子物理学、数学的発見における複雑な組合せ問題に対処できる、よりシャープでより表現力の高いLarge Reasoning Models(LRMs)への道を開く。
関連論文リスト
- Self-Supervised Coarsening of Unstructured Grid with Automatic Differentiation [55.88862563823878]
本研究では,微分可能物理の概念に基づいて,非構造格子を階層化するアルゴリズムを提案する。
多孔質媒質中のわずかに圧縮可能な流体流を制御した線形方程式と波動方程式の2つのPDE上でのアルゴリズムの性能を示す。
その結果,検討したシナリオでは,関心点におけるモデル変数のダイナミクスを保ちながら,格子点数を最大10倍に削減した。
論文 参考訳（メタデータ） (2025-07-24T11:02:13Z) - Quantum and classical correlations in shrinking algorithms for optimization [0.0]
最適化問題(COP)の解法として量子コンピューティングを用いる。
本研究では,再帰的に縮小することでCOPを解くアルゴリズムを拡張し,解析する。
量子近似最適化アルゴリズム(QAOA)と古典線形計画法(LP)と半定値計画法(SDP)の相関性を備えたアルゴリズムの性能を比較した。
論文 参考訳（メタデータ） (2024-04-26T08:29:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。