論文の概要: The Expressive Limits of Diagonal SSMs for State-Tracking

• arxiv url: http://arxiv.org/abs/2603.01959v1
• Date: Mon, 02 Mar 2026 15:08:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-03 19:50:56.931024
• Title: The Expressive Limits of Diagonal SSMs for State-Tracking
• Title（参考訳）: 状態追従のための対角形SSMの表現限界
• Authors: Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar,
• Abstract要約: 逐次状態追跡タスクにおける入力値の複素依存対角(DCD)SSMの表現性について検討する。 単層DCD SSMは有限精度で任意の非アベリア群の状態追跡を表現できないことを示す。 より一般に、$k$層DCD SSM が群の状態追跡を表現することは、その群が長さ$k$のサブ正規直列を持つ場合に限る。
• 参考スコア（独自算出の注目度）: 28.080402626116353
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State-Space Models (SSMs) have recently been shown to achieve strong empirical performance on a variety of long-range sequence modeling tasks while remaining efficient and highly-parallelizable. However, the theoretical understanding of their expressive power remains limited. In this work, we study the expressivity of input-Dependent Complex-valued Diagonal (DCD) SSMs on sequential state-tracking tasks. We show that single-layer DCD SSMs cannot express state-tracking of any non-Abelian group at finite precision. More generally, we show that $k$-layer DCD SSMs can express state-tracking of a group if and only if that group has a subnormal series of length $k$, with Abelian factors. That is, we identify the precise expressivity range of $k$-layer DCD SSMs within the solvable groups. Empirically, we find that multi-layer models often fail to learn state-tracking for non-Abelian groups, highlighting a gap between expressivity and learnability.
• Abstract（参考訳）: State-Space Models (SSM) は、様々な長距離シーケンスモデリングタスクにおいて、効率と高い並列性を維持しながら、強力な経験的性能を達成することが最近示されている。 しかし、その表現力の理論的理解は依然として限られている。 本研究では,入力依存型複素数値対角線(DCD)SSMの逐次状態追跡タスクに対する表現性について検討する。 単層DCD SSMは有限精度で任意の非アベリア群の状態追跡を表現できないことを示す。 より一般に、$k$層DCD SSM が群の状態追跡を表現することは、その群が長さ$k$のサブ正規直列を持つ場合に限る。 すなわち, 可解群内のDCD SSMの正確な表現範囲を$k$-layer DCD SSMで同定する。 経験的に、多層モデルは非アベリア群の状態追跡を学ばず、表現性と学習可能性のギャップを浮き彫りにする。

関連論文リスト

• How to Tame Your LLM: Semantic Collapse in Continuous Systems [0.0]
  連続状態機械 (Continuous State Machines, CSM) として形式化することで, 大規模言語モデルに対する意味力学の理論を開発する。 意味的特徴論的定理(SCT)の証明 我々は、SCTをドリフトカーネルや断熱的な設定に拡張し、徐々にコンパクト性、スペクトルコヒーレンス、盆地構造を保っていることを示す。
  論文  参考訳（メタデータ） (2025-12-04T11:33:02Z)
• Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics [13.202844408027412]
  我々は3つの一般的な離散拡散モデルに対する新しい鋭い収束保証を開発する。 各手法の計算複雑性は, 対数的因子まで, 次元で線形にスケールすることを示した。 この研究は、これらのノイズ発生過程に対する最初の非漸近収束保証を提供する。
  論文  参考訳（メタデータ） (2025-11-29T18:24:43Z)
• On Structured State-Space Duality [18.259743010069613]
  スカラー時間同一性状態行列を持つ構造化状態空間モデルは、マスク付き自己アテンションと1ドルで分離可能な因果マスクと等価である。 この双対性を形式化し一般化し、対角SSMがスカラーケースのトレーニング複雑性の低い境界に一致することを示す。 これらの結果は、繰り返しSSMとトランスフォーマーの間の橋渡しを強化し、表現的かつ効率的なシーケンスモデルの設計空間を広げる。
  論文  参考訳（メタデータ） (2025-10-06T15:46:50Z)
• Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models [68.31088463716269]
  状態空間モデル(SSM)における遷移行列の構造的スパースパラメトリゼーションを提案する。 我々の方法PD-SSMは、遷移行列をカラム1ホット行列(P$)と複素数値対角行列(D$)の積としてパラメータ化する。 このモデルは、様々なFSA状態追跡タスクにおいて、現代のSSMの多種多様なバリエーションを著しく上回っている。
  論文  参考訳（メタデータ） (2025-09-26T12:46:30Z)
• Bridging Expressivity and Scalability with Adaptive Unitary SSMs [15.244653633181303]
  本稿では,適応ユニタリ状態空間モデル(Adaptive Unitary State Space Model, AUSSM)を紹介する。 AUSSMとそのハイブリッド変種であるMambaoutperformが、パリティやモジュラー算術といった形式的なタスクでSSMに先立つことを示す。 この結果から,ユニタリ反復は記号的および連続的シーケンスモデリングの両方において,強力かつ効率的な帰納的バイアスを与えることが示された。
  論文  参考訳（メタデータ） (2025-07-07T17:47:16Z)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought [64.43689151961054]
  連続CoTのD$ステップを持つ2層トランスが有向グラフ到達可能性問題を解くことができることを証明した。 我々の構成では、各連続思考ベクトルは複数の探索フロンティアを同時に符号化する重ね合わせ状態である。
  論文  参考訳（メタデータ） (2025-05-18T18:36:53Z)
• Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothing [56.66469232740998]
  構造化状態空間モデル (Structured State Space Models, SSMs) は, 強い相対バイアスによって本質的に制限されていることを示す。 このバイアスにより、モデルが遠方の情報を思い出す能力が損なわれ、堅牢性の問題がもたらされる。 本研究では, 状態遷移行列の2つのチャネルをSSMで分極し, それぞれ0と1に設定し, 電流バイアスと過平滑化に同時に対処することを提案する。
  論文  参考訳（メタデータ） (2024-12-31T22:06:39Z)
• Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models [2.4889993472438383]
  低座標次数関数が高次元データにおけるカテゴリー構造の存在をテストできるかどうかについて検討する。 これはLCDFの連続構造試験における性能について研究したこのシリーズの最初の論文を補完するものである。
  論文  参考訳（メタデータ） (2024-12-30T18:34:36Z)
• On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages [56.22289522687125]
  SSM(Selective State-space Model)はTransformerの代替品である。 正規言語タスクにおける表現性や長さの一般化性能を解析する。 本稿では,Selective Dense State-Space Model (SD-SSM)を紹介する。
  論文  参考訳（メタデータ） (2024-12-26T20:53:04Z)
• Provable Benefits of Complex Parameterizations for Structured State Space Models [51.90574950170374]
  構造化状態空間モデル (Structured State Space Model, SSM) は、指定された構造に固執する線形力学系である。 パラメータ化が現実の典型的なニューラルネットワークモジュールとは対照的に、SSMは複雑なパラメータ化を使用することが多い。 本稿では,実対角 SSM と複素対角 SSM の形式的ギャップを確立することにより,SSM の複雑なパラメータ化の利点を説明する。
  論文  参考訳（メタデータ） (2024-10-17T22:35:50Z)
• Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs [1.433758865948252]
  直交非巡回グラフ(DAG)上での線形力学系(LDS)の相互作用や依存性を学習する際の最適なサンプル複雑性について検討する。 静的DAG設定にインスパイアされ,観測時系列のPSD行列に基づくメトリックとアルゴリズムが提案され,DDAGを再構築する。
  論文  参考訳（メタデータ） (2023-08-31T17:03:34Z)
• Simplifying and Understanding State Space Models with Diagonal Linear RNNs [56.33053691749856]
  本研究は、離散化ステップを解消し、バニラ対角線形RNNに基づくモデルを提案する。 概念的にはるかに単純であるにもかかわらず、$mathrmDLR$は以前提案したSSMと同じくらいのパフォーマンスを示す。 また、合成シーケンス・ツー・シーケンス・タスクのスイートによって、SSMとアテンションベースモデルの表現性も特徴付ける。
  論文  参考訳（メタデータ） (2022-12-01T18:53:06Z)

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

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