論文の概要: Log-Linear-Time Gaussian Processes Using Binary Tree Kernels

• arxiv url: http://arxiv.org/abs/2210.01633v1
• Date: Tue, 4 Oct 2022 14:30:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 14:49:56.110031
• Title: Log-Linear-Time Gaussian Processes Using Binary Tree Kernels
• Title（参考訳）: 二分木核を用いた対数線形時間ガウス過程
• Authors: Michael K. Cohen, Samuel Daulton, Michael A. Osborne
• Abstract要約: 我々は,$O((n+m)log(n+m))$ timeでガウス過程の回帰を可能にする新しいカーネルを提案する。 我々の"バイナリツリー"カーネルは、すべてのデータをバイナリツリーの葉に配置し、カーネルは最も深い共通の祖先の深さにのみ依存します。 大規模なデータセットでは、二分木GPはマタンGPよりも高速で、はるかに高速である。
• 参考スコア（独自算出の注目度）: 26.526204269075766
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gaussian processes (GPs) produce good probabilistic models of functions, but most GP kernels require $O((n+m)n^2)$ time, where $n$ is the number of data points and $m$ the number of predictive locations. We present a new kernel that allows for Gaussian process regression in $O((n+m)\log(n+m))$ time. Our "binary tree" kernel places all data points on the leaves of a binary tree, with the kernel depending only on the depth of the deepest common ancestor. We can store the resulting kernel matrix in $O(n)$ space in $O(n \log n)$ time, as a sum of sparse rank-one matrices, and approximately invert the kernel matrix in $O(n)$ time. Sparse GP methods also offer linear run time, but they predict less well than higher dimensional kernels. On a classic suite of regression tasks, we compare our kernel against Mat\'ern, sparse, and sparse variational kernels. The binary tree GP assigns the highest likelihood to the test data on a plurality of datasets, usually achieves lower mean squared error than the sparse methods, and often ties or beats the Mat\'ern GP. On large datasets, the binary tree GP is fastest, and much faster than a Mat\'ern GP.
• Abstract（参考訳）: ガウス過程(GP)は関数の優れた確率モデルを生成するが、ほとんどのGPカーネルは$O((n+m)n^2)$時間を必要とし、$n$はデータポイントの数、$m$は予測位置の数である。 我々は$O((n+m)\log(n+m))$ timeでガウス過程の回帰を可能にする新しいカーネルを提案する。 我々の"バイナリツリー"カーネルは、すべてのデータをバイナリツリーの葉に配置し、カーネルは最も深い共通の祖先の深さにのみ依存します。 結果のカーネル行列は$O(n)$空間を$O(n \log n)$時間に、スパース階数1の行列の和として保存し、約逆のカーネル行列を$O(n)$時間に保存することができる。 スパースGP法は線形実行時間も提供するが、より高次元のカーネルよりも予測精度が低い。 回帰タスクの古典的なスイートでは、カーネルをmat\'ern、sparse、およびスパース変分カーネルと比較します。 二分木GPは、複数のデータセットでテストデータに最も高い確率を割り当て、通常スパース法よりも低い平均二乗誤差を達成し、しばしばMat\'ern GPと結びつくか打ち負かす。 大規模なデータセットでは、バイナリツリーGPは、Mat\'ern GPよりも高速で、はるかに高速である。

関連論文リスト

• Large-Scale Gaussian Processes via Alternating Projection [23.79090469387859]
  本稿では,カーネル行列のサブブロックのみにアクセスする反復的手法を提案する。 我々のアルゴリズムは、交互プロジェクションに基づくもので、GPを非常に大きなデータセットにスケールするという現実的な課題の多くを解決し、各イテレーション時間と空間の複雑さを$mathcalO(n)で解決している。
  論文  参考訳（メタデータ） (2023-10-26T04:20:36Z)
• Data-Driven Linear Complexity Low-Rank Approximation of General Kernel Matrices: A Geometric Approach [0.9453554184019107]
  K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ はカーネル関数である。 我々は、点の集合 X$ と $Y$ が大きいカーネル行列に対する低ランク近似を求める。
  論文  参考訳（メタデータ） (2022-12-24T07:15:00Z)
• 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)
• 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)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
  他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。 スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。 我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
  論文  参考訳（メタデータ） (2021-08-21T02:14:55Z)
• Faster Kernel Matrix Algebra via Density Estimation [46.253698241653254]
  正半定核行列 $K の基本特性を $n$ 点に対応する n$ で計算するための高速アルゴリズムについて研究する。
  論文  参考訳（メタデータ） (2021-02-16T18:25:47Z)
• 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)

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

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