Fugu-MT 論文翻訳(概要): Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers

論文の概要: Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers

arxiv url: http://arxiv.org/abs/2603.23823v1
Date: Wed, 25 Mar 2026 01:10:42 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-26 21:06:11.078551
Title: Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers
Title（参考訳）: 階層的知識追跡の回路複雑度とログ精度変換器への応用
Authors: Naiming Liu, Richard Baraniuk, Shashank Sonkar,
Abstract要約: 経験的に、再帰不変木で訓練されたトランスフォーマーエンコーダは、置換不変ショートカットに収束する。これらの知見は, 階層構造に基づく事前知識追跡のための構造認識的目的と反復的メカニズムを動機付けている。
参考スコア（独自算出の注目度）: 2.688207424884465
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Knowledge tracing models mastery over interconnected concepts, often organized by prerequisites. We analyze hierarchical prerequisite propagation through a circuit-complexity lens to clarify what is provable about transformer-style computation on deep concept hierarchies. Using recent results that log-precision transformers lie in logspace-uniform $\mathsf{TC}^0$, we formalize prerequisite-tree tasks including recursive-majority mastery propagation. Unconditionally, recursive-majority propagation lies in $\mathsf{NC}^1$ via $O(\log n)$-depth bounded-fanin circuits, while separating it from uniform $\mathsf{TC}^0$ would require major progress on open lower bounds. Under a monotonicity restriction, we obtain an unconditional barrier: alternating ALL/ANY prerequisite trees yield a strict depth hierarchy for \emph{monotone} threshold circuits. Empirically, transformer encoders trained on recursive-majority trees converge to permutation-invariant shortcuts; explicit structure alone does not prevent this, but auxiliary supervision on intermediate subtrees elicits structure-dependent computation and achieves near-perfect accuracy at depths 3--4. These findings motivate structure-aware objectives and iterative mechanisms for prerequisite-sensitive knowledge tracing on deep hierarchies.
Abstract（参考訳）: 知識追跡モデルは相互接続された概念よりも熟達し、しばしば前提条件によって組織される。本研究では,回路複雑度レンズによる階層的前提条件の伝搬解析を行い,深い概念階層上での変圧器型計算で何が証明可能なのかを明らかにする。対数精度変換器がlogspace-uniform $\mathsf{TC}^0$ にあるという最近の結果を用いて、再帰的成熟度マスターリー伝搬を含む前提木タスクを定式化する。無条件で、再帰的マジョリティ伝播は$O(\log n)$-depth有界ファイン回路を介して$\mathsf{NC}^1$にあるが、均一な$\mathsf{TC}^0$は開下界の大きな進歩を必要とする。単調性制限の下では, ALL/ANYプレ条件木を交互に変化させることで, しきい値回路に対して厳密な深さ階層が得られる。明示的な構造だけではそれを防ぎませんが、中間部分木に対する補助的な監督は構造に依存した計算を導き、深さ3-4でほぼ完璧な精度を実現します。これらの知見は, 階層構造に基づく事前知識追跡のための構造認識的目的と反復的メカニズムを動機付けている。

関連論文リスト

Thinking Deeper, Not Longer: Depth-Recurrent Transformers for Compositional Generalization [1.5736899098702974]
本稿では,パラメータ数から計算深度を分離するDepth-recurrent Transformerを提案する。アーキテクチャには3つのメカニズムが組み込まれています(20以上のステップ)。我々は,タスクの複雑さに対処して,思考ステップがスケールするにつれて,パフォーマンスが機会からほぼ完璧に遷移する,明確な計算フロンティアを観察する。
論文参考訳（メタデータ） (2026-03-23T08:06:45Z)
Wave-Attractor-Tree: A Hierarchical Binary Tree Reduction Architecture for Efficient Sequence Modeling [0.0]
作業は階層的なバイナリツリーベースのリダクションを導入し、通常の自己アテンションを置き換える。このモデルは、コンバージェンス速度と長距離構造上の依存関係の精度の両方において、標準トランスフォーマーを著しく上回っている。
論文参考訳（メタデータ） (2026-02-28T21:17:27Z)
Rational Transductors [30.916600771560933]
EmphRational Transductorsは,行列値の繰り返しでトランスフォーマーを増強するデュアルストリームアーキテクチャである。 EmphDeep Rational Injection スキームにより,有理状態情報をアテンション機構に注入することにより,トランスフォーマーの表現力を厳密に一般化する。
論文参考訳（メタデータ） (2026-02-07T16:01:10Z)
Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version) [49.462399222747024]
本研究では,大規模状態空間を持つ決定過程(MDP)における非マルコフ報酬の論理的仕様に関する新しい枠組みを提案する。我々のアプローチは有限トレース(LTLfMT)上での線形時間論理モデュロ理論を利用する本稿では,報酬マシンとHER(Hindsight Experience Replay)をベースとした一階述語論理仕様の翻訳手法を提案する。
論文参考訳（メタデータ） (2026-02-05T22:11:28Z)
Theoretical Foundations of Prompt Engineering: From Heuristics to Expressivity [0.0]
本研究では,トランスフォーマーのバックボーンをエグゼキュータとして固定し,プロンプトのみを変化させることで得られる機能群について検討する。一つの固定されたバックボーンがプロンプトだけで対象の行動の幅広いクラスを近似できることを示す。
論文参考訳（メタデータ） (2025-12-14T13:42:20Z)
Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization [53.89723291716722]
AI推論に関する重要な問題は、モデルが学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。定数深度変換器はCoTで$mathsfNC1$-complete問題を確実に学習することを保証する。
論文参考訳（メタデータ） (2025-11-10T18:40:24Z)
ProtInvTree: Deliberate Protein Inverse Folding with Reward-guided Tree Search [77.55575655986252]
ProtInvTreeはタンパク質逆フォールディングのための報酬誘導ツリー検索フレームワークである。シークエンス生成は、意図的に、ステップワイズな意思決定プロセスとして再構成される。検索深度と幅を広げて、再トレーニングすることなく、フレキシブルなテストタイムスケーリングをサポートする。
論文参考訳（メタデータ） (2025-06-01T09:34:20Z)
A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks [0.0]
非決定論的有限オートマトン(NFA)の時間分割・深度制御型フィードフォワードネットワーク(TS-FFN)を用いたフォーマルで建設的なシミュレーションフレームワークを提案する。我々の定式化は、二進ベクトルとしてのオートマトン状態、スパース行列変換としての遷移、および共有しきい値更新の合成としての$varepsilon$-closuresを含む非決定的分岐を含む非決定論的分岐を象徴的に符号化する。
論文参考訳（メタデータ） (2025-05-30T01:18:35Z)
Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
論文参考訳（メタデータ） (2025-01-22T16:30:58Z)
Understanding Token-level Topological Structures in Transformer-based Time Series Forecasting [52.364260925700485]
Transformer-based method has achieved state-of-the-art performance in time series forecasting (TSF) 既存のトランスフォーマーが中間層全体を通してトークン間の固有位相構造を完全に活用しているかどうかは不明である。トークンレベルのトポロジを明示的にかつ適応的に保存するトランスフォーマーベースの新しいTSF手法であるトポロジ拡張法(TEM)を提案する。
論文参考訳（メタデータ） (2024-04-16T07:21:39Z)
A Closer Look at Branch Classifiers of Multi-exit Architectures [103.27533521196817]
一定の複雑さのブランチはすべてのブランチを同じに保ちますが、複雑性の増大と複雑性の低下は、それぞれバックボーンの遅かれ早かれ複雑なブランチを配置します。知識の整合性を利用して,背骨に枝を追加する効果を探索する。以上の結果から,複雑性が増大する分岐は,背骨の特徴的抽象的階層を最小限に破壊することが明らかとなった。
論文参考訳（メタデータ） (2022-04-28T08:37:25Z)

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

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