論文の概要: Provably Learning Multi-Head Attention with Queries

• arxiv url: http://arxiv.org/abs/2608.03294v2
• Date: Fri, 07 Aug 2026 05:20:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-10 14:11:30.965846
• Title: Provably Learning Multi-Head Attention with Queries
• Title（参考訳）: クエリによる多面的アテンション学習の可能性
• Abstract要約: ブラックボックス入力出力アクセスからマルチヘッドソフトマックスアテンションを学習する問題について検討する。 最近の作業では、シングルヘッドパラメータの$(W,v)$を復元するために$O(d2)$値クエリを使用するアルゴリズムが提供されている。 シングルヘッドリカバリアルゴリズムを別々にヘッドに適用するには、これらのサブスペースを知るためのベースが必要である。
• 参考スコア（独自算出の注目度）: 5.8565739627322095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning multi-head softmax attention from black-box input-output access. The learner may query arbitrary real-valued token sequences and observe only the scalar output at the final token. Recent work gives an algorithm using $O(d^2)$ value queries to recover the single-head parameters $(W,v)$. For multiple heads, the same work establishes identifiability under the assumption that the heads occupy pairwise orthogonal subspaces. Applying the single-head recovery algorithm separately to the heads additionally requires bases for these subspaces to be known. We recover a canonical representation by merging heads with the same $W_h$, summing their corresponding $v_h$, and discarding a merged head when this sum is zero, without these subspace assumptions. By varying the number of copies of a token, our algorithm obtains samples of a rational function whose interpolation separates the canonical heads. Additional queries formed by adding selected token vectors then match the same head across different queries. When the oracle outputs and all subsequent computations are exact, the learner chooses its query vectors at random and recovers the canonical pairs $\{(W_h,v_h):h\in[H]\}$ up to permutation with probability one. When $H$ is known, it uses exactly $4Hd^2-2H+1$ value queries of maximum length $2H+1$. If only a known upper bound $H_0$ is available, the algorithm uses $4H_0d^2-2H_0+1$ value queries of maximum length $2H_0+1$. For approximate oracle outputs, we give conditions under which the parameter error is at most a model- and query-dependent constant multiple of the output error. Finally, we extend our result to a one-layer Transformer with multi-head attention followed by a bias-free ReLU feed-forward network. Under additional conditions, we recover a functionally equivalent Transformer without relying on a separate algorithm for learning the feed-forward network.
• Abstract（参考訳）: ブラックボックス入力出力アクセスからマルチヘッドソフトマックスアテンションを学習する問題について検討する。 学習者は任意の実数値のトークンシーケンスをクエリし、最終トークンでのスカラー出力のみを観測することができる。 最近の作業では、シングルヘッドパラメータの$(W,v)$を復元するために$O(d^2)$値クエリを使用するアルゴリズムが提供されている。 複数のヘッドに対して、同じ作業は、ヘッドがペア直交部分空間を占めるという仮定の下で、識別可能性を確立する。 シングルヘッドリカバリアルゴリズムを別々にヘッドに適用するには、これらのサブスペースを知るためのベースが必要である。 我々は、同じ$W_h$でヘッドをマージし、対応する$v_h$を和し、この和がゼロのときにマージされたヘッドをこれらの部分空間仮定なしで破棄することで、標準表現を回復する。 トークンのコピー数を変化させることで、補間が正準ヘッドを分離する有理関数のサンプルを得る。 選択されたトークンベクトルを追加して生成された追加クエリは、異なるクエリで同じヘッドにマッチする。 オラクルが出力され、その後の全ての計算が正確であれば、学習者はランダムにクエリベクトルを選択し、確率1で置換するまでの正準対 $\{(W_h,v_h):h\in[H]\}$ を復元する。 H$が知られている場合、$4Hd^2-2H+1$の値クエリを最大2H+1$で使用する。 既知の上限$H_0$のみが利用できる場合、アルゴリズムは最大長さ2H_0+1$の4H_0d^2-2H_0+1$値クエリを使用する。 近似オラクル出力に対して、パラメータエラーが少なくとも、出力エラーの複数のモデルおよびクエリ依存定数である条件を与える。 最後に,マルチヘッド対応の一層トランスに拡張し,バイアスのないReLUフィードフォワードネットワークで処理を行う。 追加条件下では、フィードフォワードネットワークを学習するための別個のアルゴリズムに頼ることなく、機能的に等価なトランスフォーマーを復元する。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method [1.2799130177714182]
  量子近似カウントの2重決定版について検討する。 オラクルが$xin0,1N$にアクセスすると、$|x|=M$と$|x|=M+$を区別する。 乗法逆法を用いて、$left(maxleftsqrt(N-M)(M+)/,sqrtN/rightright)$を証明する。
  論文  参考訳（メタデータ） (2026-09-09T07:01:11Z)
• The Head Complexity of Boolean Functions in Single-Layer Attention [2.2727733134290813]
  単層アテンションのみのモデルで関数を計算するのに必要なアテンションヘッドの最小数について検討する。 k$headは$k$-bitパリティを計算するが、$(k+1)$-bitパリティを計算できない。 また、埋め込み次元と数値精度のためのコンパクト性境界を確立する。
  論文  参考訳（メタデータ） (2026-09-03T16:22:02Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• On the Computational Hardness of Transformers [14.73362105392153]
  この結果から, トランスフォーマーの効率は, 独立評価値のLH$よりも高いことがわかった。 小さな埋め込み方式では、$LH$アテンションヘッドは別々に$LHN2 + o(1)$時間を必要とする。 大規模な埋め込み方式では、$LHN+ o(1)$算術演算を使用して別々に$LH$アテンションヘッドを計算することができる。
  論文  参考訳（メタデータ） (2026-03-11T21:48:43Z)
• Provably Learning Attention with Queries [15.606567893781367]
  出力にブラックボックスアクセスを持つトランスフォーマーに基づくシーケンスモデルを学習する際の問題点について検討する。 この設定では、学習者は任意のベクトル列でオラクルを適応的にクエリし、対応する実数値出力を観察することができる。
  論文  参考訳（メタデータ） (2026-01-23T16:28:22Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。 クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。 このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
  論文  参考訳（メタデータ） (2026-01-07T22:07:44Z)
• Statistical and computational challenges in ranking [53.03724383992195]
  質問に対する回答の正しさに基づいて,専門家の能力に応じて$n$をランク付けする問題を考察する。 ここでは,この問題に対する統計的に最適かつ計算学的に効率的な手順の存在について検討する。
  論文  参考訳（メタデータ） (2025-12-24T11:18:06Z)
• One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem [1.4146420810689422]
  ベルンシュタイン・ヴァジラニ問題(Bernstein-Vazirani problem)は、隠れ部分群問題(HSP)の例である。 インデックス-$q$ HSP: 隠された部分群 $H le G$ がインデックス 1$ または $q$ を持つかどうかを判定し、可能であれば$H$ を識別する。
  論文  参考訳（メタデータ） (2025-10-12T10:42:50Z)
• Learning Partitions with Optimal Query and Round Complexities [16.815943270621638]
  未知の$n$要素を少なくとも$k$集合に分割することの基本的な問題を考える。 非適応アルゴリズムには$Theta(n2)$クエリが必要ですが、適応アルゴリズムには$Theta(nk)$クエリが必要です。 我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(log log n)$ラウンドしか必要としない。
  論文  参考訳（メタデータ） (2025-05-08T07:27:29Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Query complexity of heavy hitter estimation [6.373263986460191]
  我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。 それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。 それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-05-29T07:15:46Z)

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

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