論文の概要: Fast Sketching of Polynomial Kernels of Polynomial Degree

• arxiv url: http://arxiv.org/abs/2108.09420v1
• Date: Sat, 21 Aug 2021 02:14:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-24 15:56:17.402369
• Title: Fast Sketching of Polynomial Kernels of Polynomial Degree
• Title（参考訳）: 多項式次数の多項式核の高速スケッチ
• Authors: Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang
• Abstract要約: 他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。 スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。 我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
• 参考スコア（独自算出の注目度）: 61.83993156683605
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Kernel methods are fundamental in machine learning, and faster algorithms for kernel approximation provide direct speedups for many core tasks in machine learning. The polynomial kernel is especially important as other kernels can often be approximated by the polynomial kernel via a Taylor series expansion. Recent techniques in oblivious sketching reduce the dependence in the running time on the degree $q$ of the polynomial kernel from exponential to polynomial, which is useful for the Gaussian kernel, for which $q$ can be chosen to be polylogarithmic. However, for more slowly growing kernels, such as the neural tangent and arc-cosine kernels, $q$ needs to be polynomial, and previous work incurs a polynomial factor slowdown in the running time. We give a new oblivious sketch which greatly improves upon this running time, by removing the dependence on $q$ in the leading order term. Combined with a novel sampling scheme, we give the fastest algorithms for approximating a large family of slow-growing kernels.
• Abstract（参考訳）: カーネルメソッドは機械学習の基本であり、カーネル近似の高速アルゴリズムは機械学習における多くのコアタスクを直接高速化する。 多項式核は、テイラー級数展開を通じて多項式核によって近似されることが多いため、特に重要である。 最近の斜めスケッチ技術では、多項式核の指数関数から多項式への次数 q$ に対する実行時間の依存性が小さくなっており、これはガウス核にとって有用であり、q$ は多対数として選択できる。 しかし、ニューラル・タンジェントやアークコサイン・カーネルのようなよりゆっくりと成長するカーネルの場合、$q$は多項式でなければならない。 この実行時間を大幅に改善し、先行注文項の$q$への依存をなくすことにより、新たな不明瞭なスケッチを提示する。 新しいサンプリングスキームと組み合わせることで、成長の遅いカーネルの大規模なファミリーを近似するための最速のアルゴリズムを与える。

関連論文リスト

• Spectral Truncation Kernels: Noncommutativity in $C^*$-algebraic Kernel Machines [12.11705128358537]
  スペクトルトランケーションに基づく正定値カーネルの新しいクラスを提案する。 性能向上につながる要因であることを示す。 また,スペクトルトランケーションカーネルの表現能力を高めるための深層学習の視点も提案する。
  論文  参考訳（メタデータ） (2024-05-28T04:47:12Z)
• Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives [0.5735035463793009]
  厳密な誤り解析を伴う非等間隔高速フーリエ変換(NFFT)に基づく手法を提案する。 また,本手法は,カーネルの分化に伴う行列の近似に適していることを示す。 複数のデータセット上で高速な行列ベクトル積を持つ付加的カーネルスキームの性能について述べる。
  論文  参考訳（メタデータ） (2024-04-26T11:50:16Z)
• Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms [0.0]
  カーネルベースの手法は機械学習で多用されている。 彼らは考慮されたデータポイントの$O(N2)$複雑さに悩まされる。 近似法を提案し、この複雑さを$O(N)$に削減する。
  論文  参考訳（メタデータ） (2024-01-16T10:31:27Z)
• Neural Networks can Learn Representations with Gradient Descent [68.95262816363288]
  特定の状況下では、勾配降下によって訓練されたニューラルネットワークは、カーネルメソッドのように振る舞う。 実際には、ニューラルネットワークが関連するカーネルを強く上回ることが知られている。
  論文  参考訳（メタデータ） (2022-06-30T09:24:02Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Kernel Identification Through Transformers [54.3795894579111]
  カーネル選択はガウス過程(GP)モデルの性能決定において中心的な役割を果たす。 この研究は、高次元GP回帰モデルのためのカスタムカーネル関数を構築するという課題に対処する。 KITT: Kernel Identification through Transformersを提案する。
  論文  参考訳（メタデータ） (2021-06-15T14:32:38Z)
• The Fast Kernel Transform [21.001203328543006]
  本稿では,FKT(Fast Kernel Transform:高速カーネル変換)を提案する。 FKT はガウス、マテルン、ラショナル四次共分散関数や物理的に動機付けられたグリーン関数など、幅広い種類のカーネルに容易に適用できる。 本稿では、時間と精度のベンチマークを提供することによりFKTの有効性と汎用性を説明し、それを近隣埋め込み(t-SNE)とガウス過程を大規模実世界のデータセットに拡張する。
  論文  参考訳（メタデータ） (2021-06-08T16:15:47Z)
• Kernel approximation on algebraic varieties [0.7614628596146599]
  スパースデータやローランクデータにまつわる問題において, より優れた近似が得られることを示す。 この結果は、アプリケーションで使用されるカーネルの主要なクラスであるスムーズな等方性カーネルに対して提示される。
  論文  参考訳（メタデータ） (2021-06-04T23:42:19Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• PolyScientist: Automatic Loop Transformations Combined with Microkernels for Optimization of Deep Learning Primitives [55.79741270235602]
  深層学習カーネル開発のためのハイブリッドソリューションを開発する。 我々は、高度な多面体技術を用いて、パフォーマンスのために外部ループを自動的に調整する。
  論文  参考訳（メタデータ） (2020-02-06T08:02:34Z)

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

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