論文の概要: Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval
- arxiv url: http://arxiv.org/abs/2605.05189v1
- Date: Wed, 06 May 2026 17:53:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-07 18:41:07.977268
- Title: Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval
- Title（参考訳）: 線形連想記憶におけるシャープ容量閾値 - Winner-Take-All から Listwise Retrieval へ
- Abstract要約: $dtimes d$ リニアメモリストアはいくつのキー値アソシエーションが可能ですか?
この答えは、メモリマトリックスの$d2$自由度だけでなく、検索基準にも依存する。
- 参考スコア（独自算出の注目度）: 59.859592671274704
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: How many key-value associations can a $d\times d$ linear memory store? We show that the answer depends not only on the $d^2$ degrees of freedom in the memory matrix, but also on the retrieval criterion. In an isotropic Gaussian model for the stored pairs, we show that top-1 retrieval, where every signal must beat its largest distractor, requires the logarithmic model-size scale $d^2\asymp n\log n$. We prove that the correlation matrix memory construction, which stores associations by superposing key-target outer products, achieves this scale through a sharp phase transition, and that the same scaling is necessary for any linear memory. Thus the logarithm is the intrinsic extreme-value price of winner-take-all decoding. We next consider listwise retrieval, where the correct target need not be the unique top-scoring item but should remain among the strongest candidates. To formalize this regime, we propose the Tail-Average Margin (TAM), a convex upper-tail criterion that certifies inclusion of the correct target in a controlled candidate list. Under this listwise retrieval criterion, the capacity follows the quadratic scale $d^2\asymp n$. At load $n/d^2\toα$, we develop an exact asymptotic theory for the TAM empirical-risk minimizer through a two-parameter scalar variational principle. The theory has a rich phenomenology: in the ridgeless limit it yields a closed-form critical load separating satisfiable and unsatisfiable phases, and it predicts the limiting laws of true scores, competitor scores, margins, and percentile profiles. Finally, a small-tail extrapolation further leads to the conjectural sharp top-1 threshold $d^2\sim 2n\log n$.
- Abstract（参考訳）: $d\times d$ リニアメモリストアのキーと値の関連性はいくつありますか?
この答えは、メモリマトリックスの$d^2$自由度だけでなく、検索基準にも依存することを示す。
保存されたペアに対する等方的ガウスモデルでは、全ての信号が最大のトラクタを破らなければならないトップ-1 検索は対数モデルサイズ $d^2\asymp n\log n$ を必要とすることを示す。
キーターゲット外積を重畳して関連性を保持する相関行列メモリ構造は, 急激な位相遷移によってこのスケールを達成し, 任意のリニアメモリに同じスケーリングが必要であることを証明した。
したがって、対数は真に極値の値である。
次に、リストワイズ検索について検討する。ここでは、正しいターゲットがユニークなトップスコアアイテムである必要はないが、最有力候補に留まるべきである。
この制度を定式化するために、制御された候補リストに正しいターゲットを組み込むための凸上尾基準であるTail-Average Margin (TAM)を提案する。
このリストワイズ検索基準の下では、キャパシティは2次スケール $d^2\asymp n$ に従う。
負荷$n/d^2\toα$では、2パラメータスカラー変動原理を用いて、TAM経験リスク最小化器の正確な漸近理論を開発する。
この理論には豊富な現象論があり、隆起のない極限では、満足し難い位相と満足できない位相を分離する閉形式の臨界荷重をもたらし、真のスコア、競合スコア、マージン、パーセンタイルプロファイルの制限則を予測する。
最後に、小さな尾の補間はさらに、射影的鋭いトップ-1しきい値$d^2\sim 2n\log n$に繋がる。
関連論文リスト
- Batch Size or Negatives? A Selection Rule for Memory-Constrained Recommender Training [0.8782033967242784]
大規模ニューラルレコメンダシステムは、通常、全項目語彙に対してソフトマックスのクロスエントロピー目的で訓練される。
固定予算が$B = n k$の場合、より大きなバッチを優先するか、よりネガティブな項目を含めるべきかどうかは不明だ。
本稿では,リコメンデータシステムのトレーニング中のメモリ構成に関する理論的かつ実証的な基礎を提案する。
論文 参考訳（メタデータ） (2026-08-11T15:29:01Z) - Wavelet Variance Equipartition as a Threshold for World-Model Quality and Quantum Kernel TN-Simulability [0.0]
我々はウェーブレットスケーリング指数$$を臨界診断として同定する。
振幅符号化された量子カーネルの古典的シミュラビリティのシャープな遷移境界として$=1/2$を確立する。
この分散は、厳密には$Var[X] = (d-2)$としてスケールする。
論文 参考訳（メタデータ） (2026-05-12T05:41:12Z) - Factual recall in linear associative memories: sharp asymptotics and mechanistic insights [11.11958822145404]
ニューラルネットワークによる入力出力関連の保存と検索の限界について検討する。
線形連想メモリは$p$入力埋め込みを$mathbbRd$で対応する$d$次元のターゲットにマッピングする。
分離されたモデルでは最大$p_c log p_c / d2 = 1 / 2$のアソシエーションを保存できることを示す。
論文 参考訳（メタデータ） (2026-05-11T16:24:02Z) - Linear-Readout Floors and Threshold Recovery in Computation in Superposition [0.0]
重ね合わせにおける計算に対する最近の2つのアプローチは、異なるキャパシティレジームに到達している。
これらの結果は異なるインターフェース不変性を維持するため矛盾しない。
Hnniテンプレート以外のロバストな非線形リセットは開のままである。
論文 参考訳（メタデータ） (2026-05-02T02:11:31Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - How Many Features Can a Language Model Store Under the Linear Representation Hypothesis? [8.283029791278187]
線形表現仮説(LRH)の数学的枠組みを導入する。
LRHは言語モデルの中間層が線形に格納されると主張している。
d = O_(frack2log klog (m/k))$ は必要であり、$d = O_(k2log m)$ suffices は必要であることを示す。
論文 参考訳（メタデータ） (2026-02-11T17:49:32Z) - Transformers as Support Vector Machines [54.642793677472724]
自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。
勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。
これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
論文 参考訳（メタデータ） (2023-08-31T17:57:50Z) - Deletion and Insertion Tests in Regression Models [1.2891210250935148]
説明可能なAI(XAI)の基本課題は、ブラックボックス関数$f$による予測の背後にある最も重要な特徴を特定することである。
Petsiuk et al. Kernel の挿入と削除テストは、分類においてピクセルを最も重要視するアルゴリズムの品質を判断するために用いられる。
論文 参考訳（メタデータ） (2022-05-25T00:55:47Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Policy Optimization Using Semiparametric Models for Dynamic Pricing [1.3428344011390776]
商品の市場価値が観測された特徴と市場ノイズに線形である状況的動的価格問題について検討する。
一般化線形モデルからの半パラメトリック推定と未知のリンクとオンライン意思決定を組み合わせた動的統計的学習と意思決定ポリシーを提案する。
論文 参考訳（メタデータ） (2021-09-13T23:50:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。