Fugu-MT 論文翻訳(概要): Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

論文の概要: Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

arxiv url: http://arxiv.org/abs/2505.08146v1
Date: Tue, 13 May 2025 00:47:17 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-14 20:57:54.381671
Title: Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
Title（参考訳）: Tensor Sketch: 高速でスケーラブルな多項式近似
Authors: Ninh Pham, Rasmus Pagh,
Abstract要約: textitTensor Sketchは、カーネルを近似するための効率的なランダムな特徴マップである。 Sketchは、$BOn(d+D logD)$の低次元埋め込みを時間内に計算する。誤差近似に関する理論的保証を提供し、その結果のカーネル関数の推定精度を確実にする。
参考スコア（独自算出の注目度）: 19.363672064425504
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose \textit{Tensor Sketch}, an efficient random feature map for approximating polynomial kernels. Given $n$ training samples in $\R^d$ Tensor Sketch computes low-dimensional embeddings in $\R^D$ in time $\BO{n(d+D \log{D})}$ making it well-suited for high-dimensional and large-scale settings. We provide theoretical guarantees on the approximation error, ensuring the fidelity of the resulting kernel function estimates. We also discuss extensions and highlight applications where Tensor Sketch serves as a central computational tool.
Abstract（参考訳）: ランダムな特徴写像を用いた非線形カーネルの近似は、カーネルメソッドを大規模データセットにスケーリングする強力な手法となった。多項式カーネルを近似する効率的なランダム特徴写像である「textit{Tensor Sketch}」を提案する。 $\R^d$ Tensor Sketch に$n$のトレーニングサンプルが与えられた場合、$\R^D$ in time $\BO{n(d+D \log{D})}$は高次元および大規模設定に適している。近似誤差を理論的に保証し、その結果のカーネル関数の推定精度を保証します。また、Tensor Sketchが中央の計算ツールとして機能する拡張と強調アプリケーションについても論じる。

関連論文リスト

Dimensionality Reduction for General KDE Mode Finding [12.779486428760373]
高次元確率分布のモードを$D$で見つけることは、統計学とデータ解析の基本的な問題である。我々は、$mathitP = MathitNP$ でない限り、カーネル密度推定のモードを見つけるための時間アルゴリズムがないことを示す。
論文参考訳（メタデータ） (2023-05-30T05:39:59Z)
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation [24.166833799353476]
カーネルグラフ上では$textitweighted edge sample$、カーネルグラフ上では$textitweighted walk$、行列で$textitweighted sample$からKernel Density Estimationへ効率よく還元する。当社の削減は、それぞれのアプリケーションにおいて中心的な要素であり、それらが独立した関心事である可能性があると信じています。
論文参考訳（メタデータ） (2022-12-01T16:42:56Z)
Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文参考訳（メタデータ） (2022-10-21T15:56:13Z)
Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation [4.061135251278187]
広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
論文参考訳（メタデータ） (2022-06-16T17:59:48Z)
Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel [15.535749953841274]
p$ベクトルの積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。本稿では、実乱射影を複素射影に置き換える、よく知られたスケッチの単純な複素対Real (CtR) 修正を提案する。本手法は,文献の他のランダム化近似と比較して,精度と速度の面で最先端の性能を達成することを示す。
論文参考訳（メタデータ） (2022-02-04T09:15:43Z)
Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
論文参考訳（メタデータ） (2021-08-21T02:14:55Z)
Scaling Neural Tangent Kernels via Sketching and Random Features [53.57615759435126]
最近の研究報告では、NTKレグレッションは、小規模データセットでトレーニングされた有限範囲のニューラルネットワークより優れている。我々は、アークコサインカーネルの拡張をスケッチして、NTKの近距離入力スパーシティ時間近似アルゴリズムを設計する。 CNTKの特徴をトレーニングした線形回帰器が,CIFAR-10データセット上での正確なCNTKの精度と150倍の高速化を実現していることを示す。
論文参考訳（メタデータ） (2021-06-15T04:44:52Z)
Random Features for the Neural Tangent Kernel [57.132634274795066]
完全接続型ReLUネットワークのニューラルタンジェントカーネル(NTK)の効率的な特徴マップ構築を提案する。得られた特徴の次元は、理論と実践の両方で比較誤差境界を達成するために、他のベースライン特徴マップ構造よりもはるかに小さいことを示しています。
論文参考訳（メタデータ） (2021-04-03T09:08:12Z)
Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文参考訳（メタデータ） (2020-12-22T12:59:30Z)
Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文参考訳（メタデータ） (2020-06-12T10:21:40Z)

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