論文の概要: On the Computational Complexity of Structural Generalization
- arxiv url: http://arxiv.org/abs/2607.19573v1
- Date: Tue, 21 Jul 2026 21:00:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-23 18:51:37.927683
- Title: On the Computational Complexity of Structural Generalization
- Title（参考訳）: 構造一般化の計算複雑性について
- Authors: Zichao Wei,
- Abstract要約: 構造一般化は2つの前提(構成構造と非有界一般化)を数学的言語に定義する。
この問題は、純粋変換器の学習可能な天井$mathrmTC0$に対して計算の下限$mathrmNC1$を落としている。
純粋な変換器は両面を同時に学ばなければならないが、クラウスら (2026) は学習可能なクラス $subseteq mathrmTC0$ が構造的一般化を学べないことを証明している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Structural generalization has been measured repeatedly by several benchmarks, yet it has never been formally defined. We give a definition that translates the two premises (compositional structure and unbounded generalization) into mathematical language. The definition itself is neutral: a compiler that hard-codes the rules satisfies it just as well. But structural generalization becomes a scientific question only insofar as the capacity can autonomously emerge from finite data. This question pits the computational lower bound $\mathrm{NC}^1$ against the learnable ceiling $\mathrm{TC}^0$ of pure Transformers. Under a Montagovian instantiation, each compositional rule splits into two projections: a syntactic face ($F_γ$) and a semantic face ($G_γ$). Tree evaluation on the $G_γ$ side is an instantiation of BFVP, which is $\mathrm{NC}^1$-complete (Buss, 1987). A pure Transformer must learn both faces at once, but Kraus et al. (2026) prove that its learnable class $\subseteq \mathrm{TC}^0$. Under the standard assumption $\mathrm{TC}^0 \neq \mathrm{NC}^1$, a pure Transformer cannot learn structural generalization. Neuro-symbolic systems achieve the best benchmark scores precisely because they inject $G_γ$, sidestepping the genuinely hard half. Benchmark scores cannot distinguish "learned" from "given." This is what this paper sets out to make clear.
- Abstract（参考訳）: 構造一般化はいくつかのベンチマークによって繰り返し測定されてきたが、公式には定義されていない。
2つの前提(構成構造と非有界一般化)を数学的言語に変換する定義を与える。
定義そのものは中立的であり、ルールをハードコードするコンパイラも同様に満足している。
しかし、構造的一般化は、能力が有限データから自律的に現れるため、科学的な問題となる。
この問題は、純粋な変換器の学習可能な天井に対して計算の下界$\mathrm{NC}^1$を落としている。
モンタゴラスのインスタンス化の下で、各構成規則は、構文的面(F_γ$)と意味的面(G_γ$)の2つの射影に分かれる。
G_γ$側の木の評価はBFVPのインスタンス化であり、これは$\mathrm{NC}^1$-completeである(Buss, 1987)。
純粋な変換器は両方の面を同時に学ばなければならないが、クラウスら (2026) は学習可能なクラス $\subseteq \mathrm{TC}^0$ を証明している。
標準的な仮定である $\mathrm{TC}^0 \neq \mathrm{NC}^1$ では、純粋な変換子は構造的一般化を学べない。
ニューロシンボリックシステムは、G_γ$を注入し、真に硬いハーフをサイドステッピングするため、正確なベンチマークスコアを得る。
ベンチマークスコアは、"学習"と"ギヴン"を区別できない。
これが、この論文の明解な点だ。
関連論文リスト
- Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees [0.0]
本稿では,PAC学習のレンズを通して統計的側面を再考する。
滑らかな作用素の有限語彙から構築された合成関数木に着目する。
論文 参考訳（メタデータ） (2026-06-28T10:59:01Z) - What Your Model Threw Away and Why You'll Want It Back: Masking, Fingerprinting, and Privacy from Discarded Geometry [0.0]
We developed a framework for machine learning model that inputs carry a Lie group action。
$mathbbR$ への滑らかな写像について、プレメージの定理は、ヌルファイバーがジェネリックインプットにおいて少なくとも$dim G - 1$ の次元を持つことを保証している。
ヌルファイバー要素は、軌道地図上のニュートンを通して効率的に計算できることを示す。
論文 参考訳（メタデータ） (2026-06-17T01:03:26Z) - Context-Free Recognition with Transformers [57.46376097734401]
我々は、$mathcalO(log n)$ looping layerと$mathcalO(n6)$ padding tokensで全てのCFLを認識可能であることを示す。
実験の結果を実証的に検証し,対数深度を必要とする言語にループが有効であることを示す。
論文 参考訳（メタデータ） (2026-01-05T03:14:23Z) - Similarity Field Theory: A Mathematical Framework for Intelligence [0.0]
本稿では、実体間の類似性値の原則とその進化を定式化する数学的枠組みである「類似性場理論」を紹介する。
高いレベルでは、このフレームワークは、類似性に関する幾何学的な問題として、知性と解釈可能性を再設計する。
我々は、2つの定理を証明している: (i)非対称性は相互包含をブロックし、 (ii)安定性はアンカー座標または準位集合内の最終的な閉じ込めを必要とする。
論文 参考訳（メタデータ） (2025-09-21T22:34:00Z) - Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。