論文の概要: Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms

• arxiv url: http://arxiv.org/abs/2401.08260v2
• Date: Wed, 12 Jun 2024 10:20:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-13 23:03:49.500918
• Title: Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms
• Title（参考訳）: スライシングとフーリエ変換による高次元カーネルの高速化
• Authors: Johannes Hertrich,
• Abstract要約: カーネルベースの手法は機械学習で多用されている。 彼らは考慮されたデータポイントの$O(N2)$複雑さに悩まされる。 近似法を提案し、この複雑さを$O(N)$に削減する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kernel-based methods are heavily used in machine learning. However, they suffer from $O(N^2)$ complexity in the number $N$ of considered data points. In this paper, we propose an approximation procedure, which reduces this complexity to $O(N)$. Our approach is based on two ideas. First, we prove that any radial kernel with analytic basis function can be represented as sliced version of some one-dimensional kernel and derive an analytic formula for the one-dimensional counterpart. It turns out that the relation between one- and $d$-dimensional kernels is given by a generalized Riemann-Liouville fractional integral. Hence, we can reduce the $d$-dimensional kernel summation to a one-dimensional setting. Second, for solving these one-dimensional problems efficiently, we apply fast Fourier summations on non-equispaced data, a sorting algorithm or a combination of both. Due to its practical importance we pay special attention to the Gaussian kernel, where we show a dimension-independent error bound and represent its one-dimensional counterpart via a closed-form Fourier transform. We provide a run time comparison and error estimate of our fast kernel summations.
• Abstract（参考訳）: カーネルベースの手法は機械学習で多用されている。 しかし、考慮されたデータポイントの$O(N^2)$の複雑さに悩まされている。 本稿では,この複雑性を$O(N)$に縮める近似法を提案する。 私たちのアプローチは2つの考えに基づいている。 まず,解析基底関数を持つ任意のラジアルカーネルを,ある1次元カーネルのスライス版として表現し,その1次元カーネルの解析式を導出する。 1-次元核と$d$次元核の関係は、一般化されたリーマン・リウヴィル分数積分によって与えられる。 したがって、$d$-dimensional kernel summation を 1 次元の設定に還元することができる。 第二に、これらの一次元問題を効率的に解くために、非等間隔データ、ソートアルゴリズム、あるいは両者の組み合わせに高速なフーリエ和を適用する。 その実用的重要性のため、我々はガウス核に特別な注意を払っており、そこでは次元非依存の誤差境界を示し、閉形式フーリエ変換によってその1次元の逆を表現している。 高速なカーネル和のランタイム比較とエラー推定を行う。

関連論文リスト

• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives [0.5735035463793009]
  厳密な誤り解析を伴う非等間隔高速フーリエ変換(NFFT)に基づく手法を提案する。 また,本手法は,カーネルの分化に伴う行列の近似に適していることを示す。 複数のデータセット上で高速な行列ベクトル積を持つ付加的カーネルスキームの性能について述べる。
  論文  参考訳（メタデータ） (2024-04-26T11:50:16Z)
• On The Relative Error of Random Fourier Features for Preserving Kernel Distance [7.383448514243228]
  有名なラプラシアカーネルを含むかなりの範囲のカーネルに対して、RFFは低次元を用いて小さな相対誤差でカーネル距離を近似することはできないことを示す。 一般シフト不変カーネルに対するデータ公開次元還元に向けての第一歩を踏み出し、ラプラシアンカーネルに対して同様の$mathrmpoly(epsilon-1 log n)$ dimension を得る。
  論文  参考訳（メタデータ） (2022-10-01T10:35:12Z)
• Neural Networks can Learn Representations with Gradient Descent [68.95262816363288]
  特定の状況下では、勾配降下によって訓練されたニューラルネットワークは、カーネルメソッドのように振る舞う。 実際には、ニューラルネットワークが関連するカーネルを強く上回ることが知られている。
  論文  参考訳（メタデータ） (2022-06-30T09:24:02Z)
• Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation [4.061135251278187]
  広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。 提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
  論文  参考訳（メタデータ） (2022-06-16T17:59:48Z)
• Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
  他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。 スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。 我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
  論文  参考訳（メタデータ） (2021-08-21T02:14:55Z)
• Kernel approximation on algebraic varieties [0.7614628596146599]
  スパースデータやローランクデータにまつわる問題において, より優れた近似が得られることを示す。 この結果は、アプリケーションで使用されるカーネルの主要なクラスであるスムーズな等方性カーネルに対して提示される。
  論文  参考訳（メタデータ） (2021-06-04T23:42:19Z)
• High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
  低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。 最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
  論文  参考訳（メタデータ） (2021-02-15T13:24:41Z)
• Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
  我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。 私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
  論文  参考訳（メタデータ） (2020-06-12T17:25:39Z)
• 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)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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