Fugu-MT 論文翻訳(概要): Ehrenfeucht-Haussler Rank and Chain of Thought

論文の概要: Ehrenfeucht-Haussler Rank and Chain of Thought

arxiv url: http://arxiv.org/abs/2501.12997v2
Date: Mon, 11 Aug 2025 16:54:09 GMT
ステータス: 翻訳完了
システム内更新日: 2025-08-12 16:55:51.652955
Title: Ehrenfeucht-Haussler Rank and Chain of Thought
Title（参考訳）: Ehrenfeucht-Haussler rank and Chain of Thought
Authors: Pablo Barceló, Alexander Kozachinskiy, Tomasz Steifer,
Abstract要約: 本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
参考スコア（独自算出の注目度）: 51.33559894954108
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The notion of \emph{rank} of a Boolean function has been a cornerstone in PAC learning theory, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees. We present a novel characterization of rank, grounded in the well-known Transformer architecture. We show that the rank of a function $f$ corresponds to the minimum number of \emph{Chain of Thought} (CoT) steps required by a single-layer Transformer with hard attention to compute $f$. Based on this characterization we establish tight bounds on the number of CoT steps required for specific problems, showing that $\ell$-fold function composition necessitates exactly $\ell$ CoT steps. Furthermore, we analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps. Finally, we introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.
Abstract（参考訳）: ブール関数のemph{rank}の概念はPAC学習理論の基盤となり、多項式サイズの決定木に対する準多項式時間学習アルゴリズムを可能にした。本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。関数 $f$ のランクは、f$ を計算するのに注意を要する単層トランスフォーマーが要求する最小値 \emph{Chain of Thought} (CoT) ステップに対応する。この特徴づけに基づいて、特定の問題に必要な CoT ステップの数を厳密に制限し、 $\ell$-折りたたみ関数の合成がちょうど $\ell$ CoT ステップを必要とすることを示す。さらに、ブール列における 1 の $k$-番目の発生位置を特定する問題を分析し、それが $k$ CoT ステップを必要とすることを証明した。最後に,多層単層変圧器を捕捉する多層階数の概念を導入し,有界多層階数を持つ関数群のPAC学習性の解析を行う。

関連論文リスト

Generalized Quantum Signal Processing [0.6768558752130311]
本稿では、一般的なSU(2)回転を信号処理演算子として用いた一般化量子信号処理手法を提案する。我々のアプローチは、達成可能な変換の族に対するすべての実用的な制限を持ち上げ、残りの唯一の条件は、$|P|leq 1$である。 P$しか知られていない場合、我々は1分以内で識別できる効率的なGPU最適化を提供し、それに対応する$Q$は107$である。
論文参考訳（メタデータ） (2023-08-03T01:51:52Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文参考訳（メタデータ） (2022-07-18T12:03:26Z)
A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文参考訳（メタデータ） (2022-02-09T06:05:38Z)
Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文参考訳（メタデータ） (2021-02-17T18:54:08Z)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文参考訳（メタデータ） (2020-06-22T17:53:54Z)
On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文参考訳（メタデータ） (2020-06-19T14:11:26Z)
Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文参考訳（メタデータ） (2020-06-11T00:55:35Z)

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

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