🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

本論文は、時相論理を用いて状態空間モデル（SSM）の表現力を分析しており、それらの能力がゲーティング機構や算術精度に応じて正規言語から非正規言語まで及ぶことを明らかにするとともに、これらの知見をトランスフォーマーアーキテクチャと体系的に比較している。

原著者： Eric Alsmann, Lowejatan Noori, Martin Lange

公開日 2026-01-28

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Eric Alsmann, Lowejatan Noori, Martin Lange

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、ロボットに物語を読ませ、出来事の順序を理解させる方法を教えようとしていると想像してください。人工知能の世界には、その仕事を巡って競い合っている2つの主要な「読者」（アーキテクチャ）が存在します。一つは有名なTransformer（現在のチャットボットを動かしているもの）であり、もう一つは新星と呼ばれる**状態空間モデル（SSM）**です。

この論文は、SSMの「脳の力」に関する理論的な調査です。著者たちは、これらのモデルが特定のテストでどれほど優れたパフォーマンスを発揮するかを問うているのではありません。彼らが問いかけているのは、**「どれほど訓練したとしても、これらのモデルが理解できる絶対的な限界はどこにあるのか？」**ということです。

この問いに答えるために、彼らは特別な「論理言語（時相論理）」を物差しとして使用しています。以下に、その知見を簡単な比喩を用いて解説します。

1. SSMの2つの主要なタイプ

この論文では、情報の扱い方に基づいて、SSMを2つの主要な種類に分類しています。

対角ゲート型SSM（「厳格な会計士」）: これらのモデルには、現在読んでいる単語に基づいて内部の「ゲート」（情報の流れを制御するスイッチ）を変更できるというルールがありますが、それらは常に「対角的」でなければなりません。これは、足し算をする数字は変えられるけれど、列を混ぜ合わせることはできない計算機のようなものです。
時不変型SSM（「一定の時計」）: これらのモデルのゲートは、どんな単語を読んでいる時でも決して変化しません。それはメトロノームや時計のようなもので、語られている物語に関わらず、常に一定の速さで刻みます。

2. 精度の問題：定規 vs メジャー

著者たちは、モデル内部の数学がいかに「精密」であるかについても調査しました。

固定精度: 10個の目盛りしかない定規を使う場面を想像してください。物語がどれほど長くても、その目盛りよりも小さいものは測定できません。これは標準的なコンピュータの数学（浮動小数点数）と同じです。
対数精度: 物語が長くなるにつれて、自動的に長く、かつ詳細になっていくメジャーを使う場面を想像してください。物語が100単語なら定規には100の目盛りがあり、1,000単語なら1,000の目盛りがあります。これにより、より細かなカウントが可能になります。

3. 彼らは実際に何を理解できるのか？

「厳格な会計士」（対角型SSM）

単純な定規を使用した場合（固定精度）: 彼らは出来事の順序を理解することに長けています。「AがBの前に起きた」や「Aが起きて、次にBが起きて、次にCが起きた」といったことは分かります。しかし、彼らには大きな盲点があります：周期的なカウントができません。
- 比喩: もし「偶数回の 'a'」というパターン（例：aa, aaaa, aaaaaa）を認識するように求められた場合、彼らは失敗します。彼らの数学は単調（増え続けるか、あるいは変わらないかのどちらか）であるため、最終的に「行き詰まって」しまい、2個の 'a' と4個の 'a' の区別がつかなくなります。
成長するメジャーを使用した場合（対数精度）: もし精密にカウントする能力を与えられれば、彼らは非常に賢くなります。過去に何かが何回起きたかを正確に数えられるようになります。「'a' の数＝ 'b' の数＝ 'c' の数」といった複雑なパターンも理解できるようになります。

「一定の時計」（時不変型SSM）

単純な定規を使用した場合: これらのモデルは、複雑な「〜以来」という関係（例：「最後に 'b' を見てから、'a' は現れたか？」）を追跡するのが苦手です。しかし、彼らにはスーパーパワーがあります：円を描くようにカウントできることです。
- 比喩: 彼らの内部メカニズムは一定のサイクルであるため、「これは2番目、4番目、あるいは6番目の単語か？」を知ることに優れています。「偶数回の 'a'」という、厳格な会計士が失敗したパターンを容易に認識できます。
成長するメジャーを使用した場合: 彼らは、円を描くカウントと、総数のカウントの両方をこなすことができます。

「ハイブリッド」（混合型SSM）

これら両方のタイプの層（厳格な会計士と一定の時計）を組み合わせると、両方の良いとこ取りができます。彼らは、ある程度の複雑さの限界までは、考えられるほぼすべての「正規」のパターンを認識できます。

4. Transformerとの比較

著者たちは、これらの知見を既知のTransformerと比較しました。

対角型SSM（固定精度）は、おおよそ位置情報のヒントを持たないTransformer（単語の順序は知っているが、正確な位置は知らない）と同等です。
時不変型SSMは、位置エンコーディングを持つTransformer（文の中の正確な位置を知っている）と同等です。
大きな違い: 「グローバル・アテンション（平均ハード・アテンション型など）」を持つTransformerは、物語全体を一度に見渡して、前後方向にカウントすることができます。一方、SSMはその性質上、過去（すでに読んだもの）のみを見ます。したがって、シーケンスの「後」に起こることをカウントするという点において、SSMは最も高度なTransformerよりも厳密に能力が劣ります。

5. 「不可能な」タスク

最も重要な教訓は、これらが決してできないことのリストです。これらは、どれほど訓練しても達成できません。

固定精度の対角型SSMは、繰り返されるアイテムの偶数と奇数（例：aa と aaa）を区別することを決して学習できません。これは訓練の失敗ではなく、アーキテクチャによるハードな限界です。
この限界を打破するには、アーキテクチャを変更するか（時不変層を追加する）、あるいは数学的精度を高める（成長するメジャーを使用する）必要があります。

まとめ

これらのモデルを、異なる種類の司書と考えてみてください。

対角型（固定）: 本を順番に読むのは得意ですが、特定のパターンを数えるよう頼まれると混乱します。
時不変型: ページ数（偶数/奇数）を数えるのは得意ですが、「それ以来」という複雑な物語の追跡には苦労します。
ハイブリッド: 両方のことができる究極の司書ですが、それでも次の章を見て、そこで起こることを数えることはできません。

この論文は、これらの限界がアーキテクチャのDNAに組み込まれていることを証明しています。「固定精度の対角型」の司書を、どれほど訓練しても「カウントができる」司書に変えることはできません。その能力を得るには、より優れた道具（対数精度）を与えるか、異なる脳の構造（混合層）を与える必要があるのです。

テクニカル・サマリー：時相論理を通じた状態空間モデルの表現力について

問題提起

状態空間モデル（SSM）は、シーケンスモデリング、特に大規模言語モデルにおいて、Transformerアーキテクチャに匹敵する競争力のある代替案として浮上している。しかし、経験的な進歩が急速に進んでいる一方で、SSMの表現力に関する理論的基礎は、Transformerと比較して未開拓のままである。本論文が取り組む中心的な問題は、学習ダイナミクスとは独立して、異なるSSMのバリアントが理論的にどのような言語クラスやパターンを表現できるかを決定することである。具体的には、以下の2つの主要なアーキテクチャ的次元が表現力にどのように影響するかを調査している：

ゲーティング機構： 時不変ゲート（定数行列、例：S4）、対角ゲーティング機構（入力依存の対角行列、例：S6）、および任意のゲートの区別。
算術精度： 固定幅算術（定数ビット、例：標準的な浮動小数点）と、対数精度算術（入力長に対して対数的にスケールする精度）の区別。

著者らは、これらのバリアントを形式論理のフラグメントおよび複雑性クラスへとマッピングすることで、厳密な下界を確立し、根本的なアーキテクチャ上のボトルネックを特定することを目指している。

手法

著者らは、Transformerに関する最近の基礎的研究（Strobl et al., 2024; Yang et al., 2024aなど）を反映させ、SSMの表現力を分析するために論理的および複雑性理論的なフレームワークを採用している。

形式モデル： SSMは、入力シーケンスを線形回帰（ $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ）によって変換し、続いて非線形出力関数（ReLU活性化されたフィードフォワードニューラルネットワークとしてモデル化）を適用する層として定式化される。
論理フレームワーク： 分析には、有限トレース上の線形時相論理（LTLf）、特に**純粋過去フラグメント（PLTLf）**を利用する。この論理は、カウントを行わないイベントの順序に基づく特性を捉える。
- 拡張： この論理は、周期的な位置を追跡するためのモジュラー述語、および出現回数をカウントする能力を分析するための後方参照カウンティング演算子（ $\overleftarrow{\#}$ ）によって拡張される。
構成的証明： 著者らは、特定の時相演算子（例：「昨日（Yesterday）」、「以前（Previously）」、「以来（Since）」）やカウンティングメカニズムを、特定のゲート構造と算術設定を通じてどのように実装できるかを示す、構成的証明を提供している。
不可能証明： 反対に、本論文は、固定精度対角SSMにおける単調性などの特性を用いて、特定の非スターフリー言語（例： $(aa)^*$ ）を認識できないことを示す非表現性の結果を確立している。

主要な貢献

1. SSMバリアントの表現力階層

本論文は、ゲーティングと精度に基づくSSMの能力の詳細な階層を確立している：

対角ゲーティングSSM（固定精度）：
- 能力： PLTLfで定義されるすべての言語を認識できる（スターフリー言語および順序付き一次論理、$FO[<]$と等価）。
- 限界： 同一の入力が繰り返されると状態が安定するという単調性の性質により、 $(aa)^*$ のような非スターフリー言語を認識できない。
対角ゲーティングSSM（対数精度）：
- 能力： 後方参照カウンティングを介して、非正規言語や非文脈自由言語（例： $\{a^n b^n c^n\}$ ）を含む言語を認識できる**PLTLf[ $\overleftarrow{\#}$ ]**の言語を認識できる。
時不変SSM（固定精度）：
- 能力： モジュラー述語を用いたUN-PLTLf[MOD]（単項PLTLf）の言語を認識できる。これらは巡回置換行列を用いて周期的な位置（例：偶数/奇数インデックスの区別）を追跡でき、 $(aa)^*$ を認識できる。
- 限界： 現在の情報と過去の情報を動的に組み合わせるための入力依存ゲートを欠いているため、「以来（Since）」演算子（例： $L(a \mathcal{S} b)$ ）を必要とする言語を認識できないと推測される。
混合SSM（対角＋時不変）：
- 能力： PLTLf[MOD]を認識でき、実質的に対角および時不変の能力の和集合を捉える。これは $AC^0$ における正規言語のクラスに対応する。
- 対数精度拡張： 対数精度を用いることで、**PLTLf[ $\overleftarrow{\#}$ , MOD]**を認識できる。

2. 決定要因としての算術精度

本論文は、非正規カウンティング言語を認識するためには対数精度が厳密に必要であることを厳密に示している。固定幅算術はSSMを正規言語（またはスターフリー言語）に制限するが、対数精度は $a^n b^n c^n$ のような言語に必要なカウントの蓄積を可能にする。

3. Transformerとの体系的な比較

著者らは、SSMの各バリアントを既知のTransformerの表現結果に直接マッピングしている：

対角SSM（固定精度） $\approx$ 位置エンコーディングのないユニーク・ハードアテンション・Transformer（UHAT）（共に $FO[<]$ を捉える）。
時不変SSM $\approx$ 位置エンコーディング付きUHAT（UHAT+PE）（共に $FO[<, MOD]$ を捉える）。
混合SSM（対数精度） $\approx$ 平均ハードアテンション・Transformer（AHAT）（共にカウンティング能力を捉えるが、SSMは後方参照カウンティングに限定される）。
任意のゲート： 任意のゲートを持つSSMはすべての正規言語を認識でき、より複雑なTransformerバリアントの上界と一致する。

主要な結果

定理1： 固定精度の対角SSMは、PLTLfのすべての言語を認識する。
定理3： 固定精度の対角SSMは $(aa)^*$ を認識できず、これにより時不変SSMからの厳密な分離を証明する。
定理4： 対数精度の対角SSMは、PLTLf[ $\overleftarrow{\#}$ ]のすべての言語を認識する。
定理7： 固定精度の時不変SSMは、UN-PLTLf[MOD]のすべての言語を認識する。
系8： 固定精度の混合SSMは、 $AC^0$ におけるすべての正規言語を認識する。
不可能証明： 本論文は、特定のアーキテクチャの選択（例：対角固定精度）が、どれほどの学習データや最適化を用いても克服できない根本的なボトルネックを生み出すことを示す不可能証明を提供している。

意義と主張

本論文は、SSMの表現力と形式論理の間の最初の接続を提供し、特定のSSMバリアントにとって理論的に学習可能であるパターン、あるいは証明不可能であるパターンの構造的な保証を提示していると主張している。

基礎的な洞察： 「不可能」なタスク（例：固定精度対角SSMにおける非単調なパターン）を明確にすることで、本研究は経験的なベンチマークを補完し、学習ダイナミクスとは独立したアーキテクチャの限界を特定している。
アーキテクチャの明晰化： 結果は、SSMとTransformerの関係を明確にしている。SSMは再帰を通じて位置情報を本質的にエンコードしている（Transformerにおける位置エンコーディングに相当する）が、カウンティングメカニズム（後方参照 vs グローバルアテンション）において異なっている。
複雑性の整合性： これらの知見は、制限されたSSM（固定精度の対角/時不変）が恐らく $AC^0$ 内で動作することを示唆しており、これは Merrill et al. (2024) によって確立された $TC^0$ の上界の真の部分集合である。これは、これらのアーキテクチャが、特定の修正なしにはパリティやその他の $AC^0$ 外の言語を認識できない可能性があることを意味している。

著者らは、彼らの研究が、ゲーティングメカニズムと算術精度の選択が、使用される具体的な学習手順に関わらず、SSMがモデルできる言語のクラスを根本的に決定するという厳密な理論的ベースラインを確立したと結論付けている。