論文の概要: Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products
- arxiv url: http://arxiv.org/abs/2506.15793v1
- Date: Wed, 18 Jun 2025 18:23:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-23 19:00:04.792767
- Title: Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products
- Title（参考訳）: Kroneker回転生成物を用いたベクトルシンボリックキーバリューメモリの線形クリーンアップ
- Authors: Ruipeng Liu, Qinru Qiu, Simon Khan, Garrett E. Katz,
- Abstract要約: 現在のVector-Symbolic Architecturesにおける計算ボトルネックは、クリーンアップのステップである。
効率的なクリーンアップをサポートする新しいコードブック表現を提案する。
結果として生じるクリーンアップ時間の複雑さはリニアリチミック、すなわち$mathcalO(N,textlog,N)$である。
- 参考スコア（独自算出の注目度）: 4.502446902578007
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A computational bottleneck in current Vector-Symbolic Architectures (VSAs) is the ``clean-up'' step, which decodes the noisy vectors retrieved from the architecture. Clean-up typically compares noisy vectors against a ``codebook'' of prototype vectors, incurring computational complexity that is quadratic or similar. We present a new codebook representation that supports efficient clean-up, based on Kroneker products of rotation-like matrices. The resulting clean-up time complexity is linearithmic, i.e. $\mathcal{O}(N\,\text{log}\,N)$, where $N$ is the vector dimension and also the number of vectors in the codebook. Clean-up space complexity is $\mathcal{O}(N)$. Furthermore, the codebook is not stored explicitly in computer memory: It can be represented in $\mathcal{O}(\text{log}\,N)$ space, and individual vectors in the codebook can be materialized in $\mathcal{O}(N)$ time and space. At the same time, asymptotic memory capacity remains comparable to standard approaches. Computer experiments confirm these results, demonstrating several orders of magnitude more scalability than baseline VSA techniques.
- Abstract（参考訳）: 現在のVector-Symbolic Architectures (VSAs) における計算ボトルネックは ``clean-up'' ステップであり、アーキテクチャから取得したノイズの多いベクトルをデコードする。
クリーンアップは通常、ノイズの多いベクトルとプロトタイプベクトルの ‘codebook'' を比較する。
回転状行列のKroneker積に基づいて,効率的なクリーンアップを支援する新しいコードブック表現を提案する。
結果として生じるクリーアップ時間の複雑さは、例えば$\mathcal{O}(N\,\text{log}\,N)$ であり、$N$ はベクトル次元であり、コードブック内のベクトルの数でもある。
クリーンアップ空間の複雑性は$\mathcal{O}(N)$である。
さらに、コードブックはコンピュータメモリに明示的に格納されない:$\mathcal{O}(\text{log}\,N)$ spaceで表現でき、コードブック内の個々のベクトルは$\mathcal{O}(N)$ time and spaceで実体化できる。
同時に、漸近的メモリ容量は標準的なアプローチと同等である。
コンピュータ実験によりこれらの結果が確認され、ベースラインVSA技術よりも数桁のスケーラビリティが示された。
関連論文リスト
- A Walsh Hadamard Derived Linear Vector Symbolic Architecture [83.27945465029167]
シンボリックベクトルアーキテクチャ(VSAs)は、ニューロシンボリックAIを開発するためのアプローチである。
HLBは計算効率が良く、従来のVSAタスクで有効であるように設計されている。
論文 参考訳（メタデータ） (2024-10-30T03:42:59Z) - Matrix Compression via Randomized Low Rank and Low Precision
Factorization [47.902465710511485]
現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。
この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。
LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
論文 参考訳（メタデータ） (2023-10-17T06:56:57Z) - 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) - Factorizers for Distributed Sparse Block Codes [45.29870215671697]
分散ブロック符号(SBC)を高速かつ高精度に分解する手法を提案する。
我々の反復分解器は、しきい値に基づく非線形活性化、条件付きランダムサンプリング、および $ell_infty$-based similarity metricを導入している。
CIFAR-100, ImageNet-1K, RAVENデータセット上での4つの深層CNNアーキテクチャの実現可能性を示す。
論文 参考訳（メタデータ） (2023-03-24T12:31:48Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - On the well-spread property and its relation to linear regression [4.619541348328937]
頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
論文 参考訳（メタデータ） (2022-06-16T11:17:44Z) - Orthogonal Matrices for MBAT Vector Symbolic Architectures, and a "Soft"
VSA Representation for JSON [0.0]
ベクトルアーキテクチャ(VSAs)は、類似したオブジェクトが類似したベクトル表現を持つように、複雑なオブジェクトを単一の固定長ベクトルとして表現する方法を提供する。
提案手法であるMBAT(Matrix Binding of Additive Terms)について述べる。
論文 参考訳（メタデータ） (2022-02-08T18:41:32Z) - Impossibility Results for Grammar-Compressed Linear Algebra [14.85374185122389]
膨大な量のデータを扱うためには、ベクトルや行列を圧縮することが自然で一般的である。
本稿では, 圧縮されたデータに対して, 元のデータがそんなに小さいかのように, 効率的に計算を実行できるかどうかを問う。
内積、行列ベクトル乗法、行列乗法など、最も基本的な線形代数演算を考える。
論文 参考訳（メタデータ） (2020-10-27T10:33:01Z) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。
これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。
我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
論文 参考訳（メタデータ） (2020-06-24T19:33:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。