#### 論文の概要、ライセンス

 # (参考訳) 高速カーネル変換 [全文訳有] The Fast Kernel Transform ( http://arxiv.org/abs/2106.04487v1 ) ライセンス: CC BY 4.0 John Paul Ryan, Sebastian Ament, Carla P. Gomes, Anil Damle (参考訳) カーネルメソッドは、現代の機械学習アルゴリズムの非常に効果的で広く使われているコレクションである。 このような方法の事実上の基本的な制限は、二次的にスケールするカーネル行列(例えば、カーネル行列と行列ベクトルの乗算)や、データ集合 n の大きさの立方体(線形系)を含む計算である。\$ は、任意の次元のデータセットに対する行列ベクトル乗算(mvms)を計算する一般的なアルゴリズムであるfast kernel transform (fkt)を提案する。 通常、解析的に基底付けられた高速乗算法は特定のカーネルに対して特別な開発を必要とする。 対照的に、本手法は、基盤となるカーネルの分析構造を利用する自動微分と自動記号計算に基づいている。 これにより、FKT はガウス、マテルン、ラショナル二次共分散函数や、ラプラス方程式やヘルムホルツ方程式を含む物理的に動機付けられたグリーン函数を含む幅広い種類の核に容易に適用できる。 さらに、FKTは、多くの加速法に欠けている特性である高い、定量化され、制御可能な精度を維持している。 本稿では,fktの有効性と汎用性を,タイミングと精度のベンチマークを提供し,確率的近傍埋め込み (t-sne) とガウス過程を大規模実世界のデータセットにスケールするために適用する。 Kernel methods are a highly effective and widely used collection of modern machine learning algorithms. A fundamental limitation of virtually all such methods are computations involving the kernel matrix that naively scale quadratically (e.g., constructing the kernel matrix and matrix-vector multiplication) or cubically (solving linear systems) with the size of the data set \$N.\$ We propose the Fast Kernel Transform (FKT), a general algorithm to compute matrix-vector multiplications (MVMs) for datasets in moderate dimensions with quasilinear complexity. Typically, analytically grounded fast multiplication methods require specialized development for specific kernels. In contrast, our scheme is based on auto-differentiation and automated symbolic computations that leverage the analytical structure of the underlying kernel. This allows the FKT to be easily applied to a broad class of kernels, including Gaussian, Matern, and Rational Quadratic covariance functions and physically motivated Green's functions, including those of the Laplace and Helmholtz equations. Furthermore, the FKT maintains a high, quantifiable, and controllable level of accuracy -- properties that many acceleration methods lack. We illustrate the efficacy and versatility of the FKT by providing timing and accuracy benchmarks and by applying it to scale the stochastic neighborhood embedding (t-SNE) and Gaussian processes to large real-world data sets. 公開日: Tue, 8 Jun 2021 16:15:47 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

#### 翻訳結果

Page: /

1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] G L . 8 ] G L。 0.81
s c [ 1 v 7 8 4 4 0 sc [ 1 v 7 8 4 4 0 0.68
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
The Fast Kernel Transform Department of Computer Science 高速カーネル変換 計算機科学専攻 0.56
Department of Computer Science John Paul Ryan 計算機科学専攻 ジョン・ポール・ライアン 0.58
Cornell University Ithaca, NY 14853 コーネル大学イタカ, NY 14853 0.69
johnryan@cs.cornell. edu johnryan@cs.cornell. edu 0.59
Department of Computer Science Department of Computer Science 計算機科学専攻 計算機科学専攻 0.61
Carla P. Gomes Carla P. Gomes 0.94
Cornell University Ithaca, NY 14853 コーネル大学イタカ, NY 14853 0.69
gomes@cs.cornell.edu gomes@cs.cornell.edu 0.59
Sebastian Ament セバスティアン・アメン 0.53
Cornell University Ithaca, NY 14853 コーネル大学イタカ, NY 14853 0.69
sea79@cornell.edu sea79@cornell.edu 0.67
Anil Damle Cornell University Ithaca, NY 14853 アニル・ダム コーネル大学イタカ, NY 14853 0.54
damle@cornell.edu damle@cornell.edu 0.78
Abstract Kernel methods are a highly effective and widely used collection of modern machine learning algorithms. 概要 カーネルメソッドは、現代の機械学習アルゴリズムの非常に効果的で広く使われているコレクションである。 0.53
A fundamental limitation of virtually all such methods are computations involving the kernel matrix that naïvely scale quadratically (e g , constructing the kernel matrix and matrix-vector multiplication) or cubically (solving linear systems) with the size of the data set N. We propose the Fast Kernel Transform (FKT), a general algorithm to compute matrix-vector multiplications (MVMs) for datasets in moderate dimensions with quasilinear complexity. そのような手法の基本的な制限は、データセット N の大きさのカーネル行列(例えば、カーネル行列と行列ベクトル乗算を構成する)や立方体(線形系を解く)を2次にスケールするカーネル行列を含む計算である。我々は、準線形複雑性のあるデータセットに対する行列ベクトル乗算(MVM)を計算するための一般的なアルゴリズムであるFKTを提案する。 0.78
Typically, analytically grounded fast multiplication methods require specialized development for speciﬁc kernels. 通常、解析的に基底付けられた高速乗算法は特定のカーネルに対して特別な開発を必要とする。 0.44
In contrast, our scheme is based on auto-differentiation and automated symbolic computations that leverage the analytical structure of the underlying kernel. 対照的に、本手法は、基盤となるカーネルの分析構造を利用する自動微分と自動記号計算に基づいている。 0.69
This allows the FKT to be easily applied to a broad class of kernels, including Gaussian, Matérn, and Rational Quadratic covariance functions and physically motivated Green’s functions, including those of the Laplace and Helmholtz equations. これにより、FKT はガウス、マテラン、ラショナル四進共分散函数や、ラプラス方程式やヘルムホルツ方程式を含む物理的に動機付けられたグリーン函数など、幅広い種類の核に容易に適用できる。 0.72
Furthermore, the FKT maintains a high, quantiﬁable, and controllable level of accuracy—properties that many acceleration methods lack. さらにfktは、多くの加速法に欠けている高い量化可能で制御可能な精度を維持している。 0.52
We illustrate the efﬁcacy and versatility of the FKT by providing timing and accuracy benchmarks and by applying it to scale the stochastic neighborhood embedding (t-SNE) and Gaussian processes to large real-world data sets. 本稿では,fktの有効性と汎用性を,タイミングと精度のベンチマークを提供し,確率的近傍埋め込み (t-sne) とガウス過程を大規模実世界のデータセットにスケールするために適用する。 0.67
1 Introduction Kernel methods are fundamental to machine learning and many of its applications. 1 はじめに カーネルメソッドは機械学習とその多くの応用の基礎である。 0.73
Examples include kernel density estimation, kernel regression, Gaussian processes, support vector machines, kernel clustering, and kernel PCA (Shawe-Taylor et al , 2004; Scholkopf & Smola, 2018). 例えば、カーネル密度推定、カーネル回帰、ガウス過程、サポートベクターマシン、カーネルクラスタリング、カーネルPCA(Shawe-Taylor et al , 2004; Scholkopf & Smola, 2018)などがある。 0.61
While these methods are highly expressive by computing with an inﬁnite-dimensional feature space using the “kernel trick,” most methods require solving linear systems with the kernel matrix—an operation that scales cubically with the number of data points. これらの手法は「カーネルトリック」を用いて無限次元の特徴空間で計算することで非常に表現力が高いが、ほとんどの手法では線形系をカーネル行列で解く必要がある。 0.72
This is prohibitively expensive for increasingly large modern data sets and fundamentally limits the applicability of kernel methods. これは、ますます大規模なデータセットにとって非常に高価であり、カーネルメソッドの適用性が基本的に制限される。 0.48
To remedy this, a large number of methods have been developed that accelerate operations involving kernel matrices. この問題を解決するために、カーネル行列を含む操作を加速する多くの方法が開発されている。 0.55
Typically, these methods provide faster matrix vector products and may be paired with classical iterative methods to solve the necessary linear systems. 通常、これらの手法はより高速な行列ベクトル積を提供し、必要な線形系を解くために古典的反復法と組み合わせることができる。 0.62
For example, in the machine learning community, a popular approach is the Nyström method, which constructs a low-rank approximation based on a random sample of a kernel matrix’s columns (Williams & Seeger, 2001; 例えば、機械学習コミュニティでは、カーネル行列の列のランダムなサンプルに基づいて低ランク近似を構築するNyström法が一般的なアプローチである(Williams & Seeger, 2001)。 0.72
Preprint. Under review. プレプリント。 レビュー中。 0.63

Drineas et al , 2005; Kumar et al , 2009, 2012). Drineas et al , 2005; Kumar et al , 2009)。 0.64
In the context of Gaussian Process (GP) regression, Snelson & Ghahramani (2005) introduced inducing inputs, leading to O(N m2) runtime for N data points and m inducing inputs. ガウス過程(GP)回帰(英語版)の文脈において、Snelson & Ghahramani (2005) は入力を誘導し、NデータポイントのO(N m2) 実行とm入力を誘導する。 0.80
In Section 3 we develop a new scheme for this problem based on analytical expansions which can be readily applied to a broad range of kernel functions that arise in a diverse set of applications—a feature we highlight in Section 5. 第3節では、多種多様なアプリケーションで生じる幅広いカーネル関数に容易に適用可能な解析的拡張に基づいて、この問題に対する新たなスキームを開発する。

0.72
In scientiﬁc computing and applied mathematics, a large body of work concerns the acceleration of physical simulations in which the force two particles exert on each other is modeled by a kernel function, like the inverse-square law ∼ 1/(cid:107)x − y(cid:107)2 for gravitational and electromagnetic forces. 科学計算や応用数学において、大きな研究は、2つの粒子が互いに作用する力が、重力と電磁力の逆二乗法則である 1/(cid:107)x − y(cid:107)2 のようにカーネル関数によってモデル化される物理シミュレーションの加速に関するものである。

0.89
Famously, Greengard & Rokhlin (1987) introduced the Fast Multipole Method (FMM), which provides linear-time computation of approximate matrix-vector multiplications with certain Green’s function kernel matrices based on analytical expansions. 有名なことに、Greengard & Rokhlin (1987) はFMM(Fast Multipole Method)を導入し、解析的展開に基づくグリーン関数カーネル行列と近似行列ベクトル乗算の線形時間計算を提供した。 0.85
The Fast Gauss Transform (FGT) (Greengard & Strain, 1991) applied similar analysis to the Gaussian kernel, and was subsequently improved to enable efﬁcient computations in higher dimensions (Yang et al , 2003) and applied to kernelbased machine learning methods (Yang et al , 2004). Fast Gauss Transform (FGT) (Greengard & Strain, 1991) はガウスカーネルに類似した解析を適用し、その後高次元での効率的な計算を可能にするために改良され(Yang et al , 2003)、カーネルベースの機械学習手法(Yang et al , 2004)に応用された。 0.79
Importantly, in these cases it is possible to derive concrete error bounds based on the analytical expansions. 重要なことに、これらのケースでは、解析的展開に基づいて具体的な誤差境界を導出することができる。

0.73
However, extending these methods relies on extensive work per kernel and is dependent on ﬁnding/developing appropriate analytical expansions. しかし、これらのメソッドの拡張はカーネルごとの広範囲な作業に依存しており、適切な分析拡張の発見と開発に依存している。 0.50
In contrast, our method leverages a new general analytical expansion to allow for immediate application to a variety of kernels. 対照的に,本手法では,様々なカーネルへの即時適用を可能にするために,新たな一般解析拡張を利用する。 0.66
Even with this generality, we are still able to provide bounds and computational complexity analysis in Section 4 that is experimentally demonstrated in Section 5. この一般化にもかかわらず、セクション5で実験的に実証されたセクション4において、境界および計算複雑性解析を提供することができる。 0.73
Contribution In this work, we propose the Fast Kernel Transform (FKT), an algorithm that allows for matrix-vector multiplication with kernel matrices in O(N log N ) operations and is applicable to any isotropic kernel which is analytic away from the origin and any dataset in moderate dimensions. 本稿では,O(N log N ) 演算におけるカーネル行列との行列ベクトル乗算を可能にするアルゴリズムである Fast Kernel Transform (FKT) を提案する。

0.77
The FKT achieves this combination of computational efﬁciency and broad applicability by leveraging a new general analytical expansion introduced herein, which is implemented in Julia using modern computer algebra and auto-differentiation technologies and is provided open-source. FKTはこの計算効率と広い適用性の組み合わせを、現代の計算機代数と自動微分技術を用いてユリアで実装され、オープンソースとして提供される新しい一般的な解析拡張を活用して実現している。 0.65
We demonstrate the FKT’s scaling on synthetic data and apply it to stochastic neighborhood embedding (t-SNE) and Gaussian process regression using real-world oceanographic data to highlight the method’s versatility. 合成データに対するFKTのスケーリングを実証し、それを確率的近傍埋め込み(t-SNE)とガウス過程の回帰に応用し、実世界の海洋データを用いて手法の汎用性を強調する。 0.75
2 Prior Work Algorithms that compute (approximate) matrix vector products with kernel matrices have a long history and include algorithms of various ﬂavors. 2 先行作業 カーネル行列を持つ行列ベクトル積を計算するアルゴリズムは長い歴史を持ち、様々なフレーバーのアルゴリズムを含んでいる。 0.75
Simplistically, these methods either leverage a regular grid in the underlying domain or adaptive decompositions, and either use analytical expansions for kernel functions or purely computational schemes for compression. 単純化すると、これらの手法は基底領域の正則格子を利用するか、適応分解を利用するか、カーネル関数の解析拡張を使うか、純粋に圧縮のための計算スキームを使う。 0.54
Concretely, our FKT leverages adaptive decompositions and a semi-analytic scheme for compressing long-range interactions. 具体的には、FKTは適応分解と、長距離相互作用を圧縮するための半解析スキームを利用する。 0.48
Adaptive Methods The need for fast summation methods in N-body problems for unstructured data (i.e., matrix vector products with speciﬁc kernels) drove the development of methods that take advantage of two key features: (1) adaptive decompositions of the underlying spatial domain and (2) the ability to compress interactions between points that are well separated. 適応手法 非構造化データ(例えば、特定のカーネルを持つ行列ベクトル積)の n-体問題における高速な総和法の必要性は、(1)空間領域の適応分解と(2)分離された点間の相互作用を圧縮する能力という2つの重要な特徴を生かした手法の開発を促した。 0.82
This led to the development of the Barnes-Hut algorithm (Barnes & Hut, 1986) and the FMM (Greengard & Rokhlin, 1987) for computing matrix vector products. これによりBarnes-Hutアルゴリズム (Barnes & Hut, 1986) と FMM (Greengard & Rokhlin, 1987) が開発された。

0.81
While the FMM attains O(N ) scaling (with a constant that depends mildly on the desired accuracy), it explicitly leverages an analytical expansion for the underlying kernel and associated translation operators. FMMはO(N)スケーリング(所望の精度にやや依存する定数)を達成するが、基盤となるカーネルと関連する変換演算子に対する解析的拡張を明示的に活用する。 0.76
Therefore, extending the algorithm to additional kernels requires extensive work. したがって、アルゴリズムを追加のカーネルに拡張するには広範な作業が必要である。 0.56
This has been done for e g the Helmholtz kernel via the use of Bessel and Hankel functions (Greengard et al , 1998). これは例えば、ベッセル関数とハンケル関数(greengard et al , 1998)を用いてヘルムホルツカーネルに対して行われた。 0.74
To expand the applicability of these adaptive methods to more general kernels, numerical schemes were developed to compress long-range kernel interactions. これらの適応法をより一般的なカーネルに適用するために、長距離カーネル相互作用を圧縮する数値スキームが開発された。 0.61
These schemes led to algorithms such as the kernel independent FMM (Ying et al , 2004; Ying, 2006) and, more generally, so-called rank-structured factorizations and fast direct methods for matrices (see, e g , (Martinsson, 2019) for an overview of these methods in the context of integral equations). これらのスキームは、カーネル独立なFMM (Ying et al , 2004; Ying, 2006) のようなアルゴリズムや、より一般的には、行列の階数構造的分解や高速な直接法 (例えば、Martinsson, 2019) を積分方程式の文脈におけるこれらの手法の概要として導いた。 0.82
Moreover, these methods have been successfully applied to Gaussian Process regression (Börm & Garcke, 2007; Ambikasaran et al , 2015; Minden et al , 2017). さらに、これらの手法はガウス過程の回帰にうまく適用されている(Börm & Garcke, 2007; Ambikasaran et al , 2015; Minden et al , 2017)。 0.84
While broadly applicable, these methods can be sub-optimal if analytical expansions for kernel functions are available, as they rely on algebraic factorizations such as the interpolative decomposition (Cheng et al , 2005). 広く適用できるが、これらの方法は、補間分解 (cheng et al , 2005) のような代数的分解に依存するため、カーネル関数の解析的拡張が利用可能であれば最適である。 0.67
2 2 0.85

Grid-Based Methods For certain data distributions it can be advantageous to leverage regular grids on the computational domain to accelerate matrix vector products (and/or build effective preconditioners). 特定のデータ分布に対するグリッドベースの手法 計算領域上の正規格子を利用して行列ベクトル積を加速する(あるいは効果的なプリコンディショナーを構築する)ことは有利である。 0.68
Notably, if the observation points lie on a regular grid and the kernel function has certain structural properties it is possible to leverage the Fast Fourier Transform (FFT) to compute matrix vector products in O(N log N ) time. 特に、観測点が正則格子上に置かれ、カーネル関数が一定の構造特性を持つ場合、O(N log N )時間で行列ベクトル積を計算するために高速フーリエ変換(FFT)を利用することができる。 0.85
However, observation points typically do not lie precisely on a regular grid. しかし、観測点は通常、正則格子上に正確には配置されない。 0.65
The so-called pre-corrected FFT (Phillips & White, 1994; White et al , 1994) solves this problem by incorporating aggregation and interpolation operators to allow for computations using a regular grid that are then accelerated by the FFT. いわゆる修正FFT (Phillips & White, 1994; White et al , 1994) は、FFTによって加速される正規グリッドを用いた計算を可能にするために、集約演算子と補間演算子を統合することでこの問題を解決する。 0.73
An analogous method called structured kernel interpolation (SKI) is popular within the Gaussian Process community (Wilson & Nickisch, 2015) as an acceleration of the so-called inducing point method (Snelson & Ghahramani, 2005). 構造化カーネル補間(SKI)と呼ばれる類似の手法は、いわゆる誘導点法(Snelson & Ghahramani, 2005)の加速としてガウス過程群(Wilson & Nickisch, 2015)で人気である。 0.79
3 The Fast Kernel Transform 3 カーネル変換の高速化 0.74
We are interested in computing the matrix-vector product matrix-vector 製品の計算に興味があります 0.74
N(cid:88) zi = n(cid:88) zi = 0.81
K(|ri − rj|)yj. K(|ri − rj|)yj。 0.92
(1) j=0 where y is a given vector of real or complex numbers, ri ∈ Rd for i = 0, . (1) j=0 y が実数あるいは複素数の与えられたベクトルであるとき、i = 0 に対して ri ∈ Rd が成立する。 0.72
. . , N, and K is an isotropic kernel. . . , n, k は等方性核である。 0.78
Henceforth, we will overload notation to say that Kij := K(|ri − rj|) and (1) can be written as z = Ky. したがって、Kj := K(|ri − rj|) と (1) は z = Ky と書くことができるという表記をオーバーロードする。 0.81
The technique we propose is based on the famous Barnes-Hut (Barnes & Hut, 1986) style of tree-code algorithm. 提案手法は有名なBarnes-Hut (Barnes & Hut, 1986) 方式のツリーコードアルゴリズムに基づいている。 0.82
A tree decomposition is performed of the space containing the dataset’s points, and for each tree node, we compute a set of distant points whose kernel interactions with the node’s points can be compressed. データセットの点を含む空間で木分解を行い、各ツリーノードに対して、ノードの点とのカーネルの相互作用を圧縮できる離れた点の集合を計算する。 0.71
In the original Barnes-Hut scheme, this compression is done by summing interactions with the center of mass—in our scheme we generalize this to a new multipole expansion which can more accurately represent the points inside the node. 元のbarnes-hutスキームでは、この圧縮は質量中心との相互作用を総和することで行われ、この方法ではノード内の点をより正確に表現できる新しい多極展開に一般化する。 0.73
Compressing these interactions will produce low-rank approximations for large off-diagonal blocks of the kernel matrix, yielding an efﬁcient matrix multiplication algorithm. これらの相互作用を圧縮することで、カーネル行列の大きな対角ブロックに対する低ランク近似が発生し、効率的な行列乗算アルゴリズムが得られる。

0.73
We review each of these components in the following sections. それぞれのコンポーネントについて、以下のセクションでレビューする。 0.69
3.1 Tree decomposition We use a decomposition inspired by the binary partitioning of the k-d tree (Bentley, 1975). 3.1 木分解 我々は k-d 木の二分分割に着想を得た分解を用いる(Bentley, 1975)。 0.70
This scheme begins with a single hypercube root node containing all points, and iteratively splits nodes in half via axis-aligned separating hyperplanes. このスキームは、すべての点を含む単一のハイパーキューブ根ノードから始まり、軸方向の分離超平面を通して繰り返しノードを半分に分割する。 0.67
At each split the hyperplane is chosen to (a) split the node in half, (b) keep the aspect ratio (the maximum ratio between pairs of node side lengths) below two, and (c) optimally divide the points evenly while satisfying the ﬁrst two constraints. 各分割において、ハイパープレーンは(a)ノードを半分に分割し、(b)アスペクト比(ノード側の長さの対の最大比)を2以下に保ち、(c)最初の2つの制約を満たすことなくポイントを最適に分割する。 0.84
These qualities are chosen to encourage hyperrectangular nodes with minimal aspect ratio while maintaining the divide-and-conquer nature of binary space partitionings commonly applied in this domain. これらの性質は、この領域でよく適用される二分空間分割の分割対等性を維持しつつ、最小アスペクト比で超矩形ノードを奨励するために選択される。 0.62
When a node contains fewer than some prescribed threshold of points, it is not split and becomes a leaf node. あるノードが所定の点のしきい値以下である場合、それは分割されず、リーフノードとなる。 0.79
An example of this decomposition is shown in Figure 1. この分解の例を図1に示す。 0.64
Once a domain decomposition is computed, our algorithm requires, for every tree node i, a set Fi of far points which are far enough from the node to allow accurate compression, and such that Fi ∩ Fj = ∅ if i is a descendent of j. 整域分解が計算されると、アルゴリズムは、すべての木ノード i に対して、正確な圧縮を可能にするためにノードから十分離れている遠点の集合 fi を必要とし、i が j の次数であるなら fi を fj とする。 0.83
Throughout this work we use the following condition for ‘far enough’: この作業を通じて、以下の条件を‘十分に’使用します。 0.76
max r(cid:48)∈node max (複数形 maxs) 0.52
|r(cid:48) − rc|/|r − rc| < θ r(cid:48) − rc|/|r − rc| < θ 0.68
(2) where rc is the center of the relevant node. (2) rcは関連するノードの中心です。 0.73
If r satisﬁes this inequality, it is judged to be far enough away for compression. r がこの不等式を満たすならば、圧縮には十分遠いと判断される。 0.72
The distance parameter θ may then be varied to trade-off accuracy and computation time. 距離パラメータθは、トレードオフ精度と計算時間に変化させることができる。 0.78
3.2 Fast Matrix-Vector Multiplication 3.2 高速行列ベクトル乗算 0.59
Once the sets of far points are generated for all nodes, the FKT proceeds as described in Algorithm 1. すべてのノードに対して遠点集合が生成されると、FKTはアルゴリズム1に記述されているように進行する。 0.67
For each node i, we use a low-rank approximation of the kernel to compute interactions between points in the node and those in the Fi. 各ノードiについて、ノードの点とfiの点の間の相互作用を計算するために、カーネルの低ランク近似を用いる。 0.77
Furthermore, for each leaf l we use exact dense computations for interactions between points in the leaf and its nearby points Nl, where Nl is deﬁned to be all points さらに、各葉 l について、Nl をすべての点と定義する葉の点とその近傍の点 Nl の間の相互作用に厳密な計算を用いる。 0.80
3 3 0.85

Algorithm 1 Barnes-Hut with Multipoles アルゴリズム1 マルチポール付きバーンハット 0.54
tree ← BinarySpacePartition ing(points) z ← 0 for n ∈ tree.nodes do tree > BinarySpace Partitioning(points) z > 0 for n ∈ tree.nodes do 0.68
{Compute compressed far interactions.} 計算圧縮遠距離相互作用 0.39
s2m ← source2mult(n) m2t ← mult2target(n) z[n.far] += m2t ∗ (s2m ∗ y[n.indices]) if isleaf(n) then s2m > source2mult(n) m2t > mult2target(n) z[n.far] += m2t ∗ (s2m ∗ y[n.indices]) if isleaf(n) 0.77
{Compute nearby dense interactions.} 近くの密接な相互作用を計算すること。 0.46
near_mat ← K(n.near, n.indices) z[n.near] += near_mat ∗y[n.indices] near_mat K(n.near, n.indices) z[n.near] += near_mat ∗y[n.indices] 0.66
end if end for return z end if end for return z 0.85
Figure 1: 2D domain decomposition on points from a Gaussian mixture. 図1: ガウス混合の点上の2次元領域分解。 0.69
Points outside the circle are considered distant enough for compression with the circled box, for a certain θ in (2). 円の外側の点は円箱で圧縮できるほど遠く、(2) のある θ に対して十分であると考えられている。 0.65
such that Nl ∩ Fj = ∅ for all j in the path from the leaf to the root. 葉から根への経路のすべての j に対して Nl > Fj = > となる。 0.61
In summary the approximation is given by まとめると、近似は与えられる。 0.55
z = Ky = KNl,l ∗ yl + z = Ky = KNl,l ∗ yl + 0.85
b∈nodes l∈leaves b ノード l- +leaves 0.40
b∈nodes KNl,l ∗ yl + b ノード KNl,l ∗ yl + 0.68
K Fb,b ∗ yb, K Fb,b ∗ yb, 0.85
(cid:88) KFb,b ∗ yb ≈ (cid:88) (cid:88) KFb,b ∗ yb (cid:88) 0.83
(cid:88) (cid:88) (cid:88) (cid:88) 0.78
l∈leaves l- +leaves 0.27
where KNl,l is the submatrix of K whose columns correspond to points in the leaf node l and whose rows correspond to points in the near ﬁeld Nl of the leaf node l, KFb,b is the analogous submatrix for any node b and its far ﬁeld Fb, yl and yb are the subvectors of y corresponding to the points in the leaf l or box b respectively, and K Fbb is a low rank approximation to the typically large KFbb. KNl,l が葉ノード l の点に対応する K の部分行列であり、その列が葉ノード l, KFb,b の近傍領域 Nl の点に対応する K の部分行列であるとき、KFb,b は任意のノード b の類似部分行列であり、その遠点 Fb, yl, yb はそれぞれ葉ノード l または箱 b の点に対応する y の部分行列であり、K Fbb は典型的には大きな KFbb に対する低階近似である。 0.85
In Algorithm 1, s2m and m2t refer to “source-to-multipole” and “multipole-to-target” matrices respectively, and collectively form the low-rank approximation K Fbb. アルゴリズム1では、s2m と m2t はそれぞれ "source-to-multipole& quot; と "multipole-to-target& quot; の行列を参照し、ローランク近似 K Fbb を総称する。 0.59
3.3 Low-rank kernel approximations 3.3 低ランクカーネル近似 0.62
Given the preceding approach, the key to a fast algorithm is the availability of a sufﬁciently accurate low-rank approximation K Fb,b ≈ KFb,b valid when the sets Fb and b contain well-separated points. 前者のアプローチでは、高速アルゴリズムの鍵は、集合 Fb と b がよく区切られた点を持つときに有効な十分正確な低ランク近似 KFb,b の可用性である。 0.77
Our approach to building these approximations is inspired by multipole methods (speciﬁcally the FMM (Greengard & Rokhlin, 1987)) for solving the N-body problem (1) when K is the electrostatic potential. これらの近似を構築するためのアプローチは、Kが静電ポテンシャルである場合のN体問題の解法として多極法(特にFMM(Greengard & Rokhlin, 1987))に着想を得たものである。 0.75
If |b| = M and |Fb| = N, multiplying by this matrix requires O(M N ) work. もし |b| = M と |Fb| = N のとき、この行列による乗法は O(M N ) の作業を必要とする。 0.66
However, if we have access to a low rank approximation しかし、低階近似にアクセスできるなら、 0.56
K(|ri − rj|) ≈ K(|ri − rj|) 0.71
Uk(ri)Vk(rj) Uk(ri)Vk(rj) 0.85
(3) P(cid:88) (3) p(cid:88) 0.82
k=0 valid for i ∈ b and j ∈ Fb we can use it to accelerate the computation. K=0 i ∈ b と j ∈ Fb を有効にすれば、計算を高速化することができる。 0.67
Speciﬁcally, using (3) we can rewrite (1) as 具体的には (3) を使って (1) を書き換えることができます 0.73
yi ≈ N(cid:88) yi > N(cid:88) 0.79
P(cid:88) Uk(ri)Vk(rj)xj = p(cid:88) Uk(ri)Vk(rj)xj = 0.82
Uk(ri) Uk (複数形 Uks) 0.57
Vk(rj)xj P(cid:88) Vk(rj)xj p(cid:88) 0.82
N(cid:88) j=0 n(cid:88) j=0 0.68
k=0 k=0 j=0 K=0 K=0 j=0 0.55
and the two sums may be computed in O(P(M + N )) time. そして、2つの和は o(p(m + n ) 時間で計算できる。 0.74
In this case, the Vk sum corresponds to the s2m matrix in Algorithm 1 and the Uk sum corresponds to the m2t matrix. この場合、Vk和はアルゴリズム1のs2m行列に対応し、Uk和はm2t行列に対応する。 0.69
For example, let r(cid:48), r ∈ R3 with r(cid:48) := |r(cid:48)| < r := |r|. 例えば、r(cid:48), r ∈ R3 を r(cid:48) := |r(cid:48)| < r := |r| とする。 0.86
A classic example of an expansion of the form in (3) which is low rank for well-separated points is the multipole expansion of the electrostatic 十分に分離された点に対して低いランクである(3)の形の拡大の古典的な例は、静電の多極展開である 0.77
4 4 0.85

potential 1 r ( r(cid:48) where γ is the angle between r(cid:48) and r. Expanding in powers of r(cid:48) polynomials potential 1 r ( r(cid:48) ここで γ は r(cid:48) と r. は r(cid:48) 多項式の力で拡大する。 0.82
K(|r(cid:48) − r|) = K(|r(cid:48) − r|) = 0.86
|r(cid:48) − r| = |r(cid:48) − r| = 0.78
1 + r(cid:48) 1 + r(cid:48) 0.92
1 r r − 2 cos γ) r yields the expansion in Legendre 1 r r − 2 cos γ) r はルジャンドルにおける拡大を与える 0.82
(4) This may be put into the form of (3) by splitting Pk(cos γ) into functions of r(cid:48) and r using the spherical harmonic addition theorem (see Sec. (4) これは、pk(cos γ) を球面調和加法定理を用いて r(cid:48) と r の関数に分割することによって (3) の形にすることができる( sec を参照)。 0.76
12.8 in (Arfken, 1985)). 12.8 in (Arfken, 1985)。 0.84
Pk(cos γ). Pk(cos γ)。 0.78
k=0 r K(|r(cid:48) − r|) = K=0 r K(|r(cid:48) − r|) = 0.75
2k + 1 4π Pk(cos γ) = 2k + 1 4π Pk(cos γ) = 0.86
k (r(cid:48))Y h Y h k(r(cid:48))y h y h 0.95
k (r)∗ (5) k (r)∗ (5) 0.78
(cid:113) (cid:18) r(cid:48) (cid:113) (cid:18) r(cid:48) 0.76
(cid:19)k ∞(cid:88) (cid:19)k ∞(cid:88) 0.84
1 r k(cid:88) 1R k(cid:88) 0.78
h=−k The FKT leverages modern computational tools to build analogous low-rank approximations for a broad class of kernels. h=−k FKTは現代の計算ツールを活用し、幅広い種類のカーネルに対して類似の低ランク近似を構築する。

0.61
3.4 The Generalized Multipole Expansion 3.4 一般化多極拡大 0.79
We build our new technique by developing an expansion for general kernels into separable radial and angular functions as in (4). 一般のカーネルを可分なラジアル関数と角関数に拡張することで,新しい手法を構築する(4)。 0.68
We begin by deﬁning ε := r(cid:48) , where γ is again the angle between r(cid:48) and r. Then K(|r(cid:48) − r|) = K(r 1 + ε) by the law of cosines, and, assuming r > 0 and K is analytic except possibly at the origin, we can form a Taylor expansion around ε = 0 すると K(|r(cid:48) − r|) = K(r1 + ε) をコサインの法則で定義し、r > 0 と K が解析可能であると仮定すると、原点を除いて ε = 0 のテイラー展開を形成することができる。

0.80
√ r (cid:16) r(cid:48) r − 2 cos γ √ r (cid:16) r(cid:48) r − 2 cos γ 0.87
(cid:17) K(|r(cid:48) − r|) = (cid:17) K(|r(cid:48) − r|) = 0.82
∞(cid:88) n=0 ∞(cid:88) n=0 0.71
εn n! ∂n ∂εn K(r εn n! ∂n ∂εn K(r) 0.80
√ 1 + ε)ε=0. √ 1 + ε)ε=0. 0.91
(6) By expanding the εn terms via the binomial theorem, transforming from powers of cosine into Gegenbauer polynomials of cosine (via an identity from Avery (1989), given in the appendix in (17)), and using Faa di Bruno’s theorem for the derivatives with respect to ε, this sum can be rewritten as an expansion in (hyper)spherical harmonics, as given by Theorem 3.1 Theorem 3.1. (6) 二項定理によりεn項を拡大し、コサインのパワーからコサインのゲゲンバウアー多項式へと変換し(アヴェリー(1989年)から17の付録で与えられる)、 ε に関する微分に対するファア・ディ・ブルーノの定理を用いて、この和は Theorem 3.1 Theorem 3.1 で与えられるような(超)球面調和の展開として書き直すことができる。 0.82
If K is analytic except possibly the origin, then for r(cid:48),r within the radius of convergence, k が原点を除いて解析的であれば、r(cid:48)r は収束半径内である。 0.73
where K(|r(cid:48) − r|) = どこに K(|r(cid:48) − r|) = 0.77
Y h k (r)Y h Y h k (r)Y h 0.85
k (r(cid:48))∗K(k)(r(cid:48), r) k(r(cid:48))∗K(k)(r(cid:48), r) 0.93
K(k)(r(cid:48), r) := K(k)(r(cid:48), r) := 0.91
r(cid:48)j r(cid:48)j 0.88
K (m)(r)rm−jT (α) jkm, K (m)(r)rm−jT (α) jkm, 0.97
(7) (cid:88) (7) (cid:88) 0.82
h∈Hk ∞(cid:88) ∞(cid:88) h.hk ∞(cid:88) ∞(cid:88) 0.59
k=0 j(cid:88) K=0 j(cid:88) 0.68
j=k m=1 jkm are constants which depend only on the dimension and not on the kernel or data. j=k m=1。 jkmは次元のみに依存し、カーネルやデータに依存しない定数である。 0.60
The and T (α) radius of convergence is the same as that of (6). そして T (α) の収束半径は (6) と同じである。 0.52
(See Section A.2 for the proof and the deﬁnition of T (α) underlying the Fast Kernel transform, a truncated expansion with truncation parameter p. (高速カーネル変換の基盤となる t (α) の証明と定義については a.2 節を参照のこと。

0.75
jkm). We thus arrive at the approximation jkm)。 したがって私たちは近似にたどり着く 0.76
Y h k (r)Y h Y h k (r)Y h 0.85
k (r(cid:48))∗K(k) k(r(cid:48))∗K(k) 0.91
p (r(cid:48), r) p(r(cid:48), r) 0.92
(8) K(|r(cid:48) − r|) ≈ p(cid:88) (8) K(|r(cid:48) − r|) > p(cid:88) 0.84
(cid:88) k=0 (cid:88) K=0 0.65
h∈Hk p where K(k) is the p-term truncation of the inﬁnite sum in the deﬁnition of K(k). h.hk p ここで K(k) は K(k) の定義における無限和の p 項の切り離しである。 0.69
This expansion represents the kernel as a sum of products of functions of r with functions of r(cid:48), which is the form called for by (3). この展開は、核を r(cid:48) の函数を持つ r の函数の積の和として表す。

0.84
We may use this expansion to generate the s2m and m2t matrices in Algorithm 1 by collecting the functions of r(cid:48) into the s2m matrix and the functions of r into the m2t matrix. この展開をアルゴリズム1におけるs2mおよびm2t行列の生成に用い、r(cid:48) の関数をs2m行列に、r の関数をm2t行列に集める。 0.74
The sums over j and k in the deﬁnition of K(k) turns out to have interesting and helpful properties for our algorithm. K(k) の定義における j と k 上の和は、我々のアルゴリズムにとって興味深く有益な性質を持つことが分かる。 0.74
In particular, for certain types of kernels it is possible to automatically compute more concise expansions than the form given in (7), resulting in better complexity. 特に、あるタイプのカーネルでは、 (7) で与えられる形式よりも簡潔な展開を自動で計算することができ、より複雑になる。 0.66
The details of this additional compression can be found in Section A.4. この追加圧縮の詳細はセクションA.4で見ることができる。 0.81
5 5 0.85

Table 1: Commonly used covariance functions in Gaussian process regression 表1:ガウス過程回帰における一般的な共分散関数 0.74
Exponential Matérn (ν = 3/2) 指数関数 マテラン(ν = 3/2) 0.57
Cauchy Rational Quadratic (α = 1/2) コーシー 有理二次(α = 1/2) 0.55
4 Analysis K(r) = e−r ρ )e−√ 4 分析 K(r) = e−r ρ )e−! 0.79
√ 3r σ2(1 + √ 3r σ2(1 + 0.87
1 1+r2/σ2 1√ 1 1+r2/σ2 1√ 0.64
1+r2/σ2 3r/ρ 1+r2/σ2 3r/ρ 0.38
4.1 Truncation Error The truncation (8) yields error |EP|, which we bound using Lemma 4.1. 4.1 トランニケーション誤差 トランニケーション (8) は |EP| となり、Lemma 4.1 を用いる。 0.72
Lemma 4.1 (Truncation Error). Lemma 4.1 (Truncation Error)。 0.87
∞(cid:88) (cid:18)k + d − 3 ∞(cid:88) (cid:18)k + d − 3 0.90
k=0 k |EP| ≤ K=0 k |EP| ≤ 0.69
∞(cid:88) (cid:19)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12)(cid:12) j(cid:88) k (cos γ)| ≤(cid:0)k+d−3 ∞(cid:88) (cid:19)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12)(cid:12) j(cid:88) k (cos γ)| ≤(cid:0)k+d−3) 0.79
j=max (p+1,k) j=max (p+1,k) 0.75
m=1 k (cid:18) r(cid:48) m=1。 k (cid:18) r(cid:48) 0.70
r (cid:19)j T (α) r (cid:19)j T(α) 0.90
jkm (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12) jkm (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) 0.85
K (m)(r)rm K (m)(r)rm 0.85
(9) (cid:1) on Gegenbauer polynomials (DLMF) (9) (素数:1)ゲゲンバウアー多項式(DLMF)について 0.70
Proof. This follows from the bound |C (α) and bringing the absolute value inside the sum. 証明。 これは境界 |c (α) から従い、和の内部に絶対値をもたらす。 0.68
In Figure 2, right, we report several empirical ﬁndings on this bound. 図2では、この境界についていくつかの経験的な発見を報告します。 0.45
As in the error analysis of the FMM for the electrostatic and Helmholtz kernels, the error is observed to decay exponentially with the choice of truncation parameter. 静電気およびヘルムホルツ核のFMMの誤差解析と同様に、この誤差はトラクションパラメータの選択とともに指数関数的に減衰する。 0.73
In practice, the above bound turns out to be fairly loose—as we report in Section 5, a choice of p = 4 yields a residual less than 10−4 for reasonable distance criteria. 実際には、上記の境界はかなり緩く、セクション5で報告したように、p = 4 の選択は、合理的距離の基準に対して 10−4 未満の残差を与える。 0.67
Because the bound in Lemma 4.1 is observed to be fairly loose (albeit descriptive) in practice, we omit further analysis. Lemma 4.1のバウンドは、実際にはかなり緩い(記述的ではあるが)ので、さらなる分析は省略する。 0.64
It is of interest to further develop and analyze tighter upper bounds. より強固な上界を発達させ、分析することに関心がある。 0.56
4.2 Computational Complexity To assess the computational complexity of the FKT, we need to understand the size of our compressed far-ﬁeld expansion. 4.2 計算複雑性 fktの計算複雑性を評価するには、圧縮された遠方拡大の大きさを理解する必要がある。 0.64
Our low rank approximation takes the form 我々の低いランク近似は形を取る 0.74
(cid:88) and it is not hard to show (see Section A.3) that P =(cid:0)p+d (cid:88)で、P = (cid:0)p+d を示すのは難しくない(セクションA.3)。 0.75
K(|ri − rj|) ≈ K(|ri − rj|) 0.71
Uk(ri)Vk(rj) = Uk(ri)Vk(rj) = 0.85
P(cid:88) p(cid:88) p(cid:88) p(cid:88) 0.82
h∈Hk k=0 k=0 h.hk K=0 K=0 0.47
d k (r(cid:48))∗K(k) d k(r(cid:48))∗K(k) 0.88
p (r(cid:48), r), p(r(cid:48), r) 0.80
Y h k (r)Y h Y h k (r)Y h 0.85
(cid:1) ∼ dp. (cid:1) は dp である。 0.62
We note that this is exactly the これはまさにこれです。 0.36
same as the number of terms in the expansion underlying the Improved FGT ((Yang et al , 2003)), and is achieved for a much broader class of kernels by the FKT. Improved FGT ((Yang et al , 2003) の根底にある拡張の項の数と同じであり、FKT によってより広い種類のカーネルに対して達成される。 0.74
The complexity of Algorithm 1 is the sum of the cost of computing the dense matrices for nearby interactions, the cost of computing the s2m matrices for every node, and the cost of computing the m2t matrices for every node. アルゴリズム1の複雑さは、近傍の相互作用に対する密度行列の計算コスト、各ノードに対するs2m行列の計算コスト、各ノードに対するm2t行列の計算コストの合計である。

0.80
For simplicity of this analysis, we assume that every leaf has at most m points, each leaf has at most Nd points in its near ﬁeld, and each point is in the far ﬁeld of at most Fd nodes. この解析の単純さのために、すべての葉は最大 m 個の点を持ち、各葉は最大 Nd 個の点をその近傍の場に有し、各点は最大 Fd 個のノードの遠点にあると仮定する。 0.74
If the total number of points is N, the total cost is given by FKTcost = O 点数の合計が N であれば、総費用は FKT Cost = O で与えられる。 0.80
= O (N (Nd+ log (N/m)dp + Fddp)) . = O (Nd+ log (N/m)dp + Fddp))。 0.85
(10) In practice, Fd can be made to depend on the intrinsic1 dimension of the data by the choice of tree decomposition, but is generally exponential in that intrinsic dimension and has an additional factor of log (N/m) coming from the depth of the tree. (10) 実際には、Fdは木分解の選択によってデータの内在1次元に依存することができるが、一般にその内在次元において指数関数であり、木の深さから来る対数(N/m)の付加因子を持つ。 0.74
Nd depends on the maximum leaf capacity m and a Ndは最大葉容量mとaに依存する 0.77
mNd + N log (N/m)P + N FdP mNd + N log (N/m)P + N FdP 0.99
(cid:18) N (cid:19) (cid:18)n (cid:19) 0.79
m 1Data which approximately lies on a lower-dimensional manifold has intrinsic dimension equal to that of the manifold. M 下次元多様体のほぼ上の 1Data は、多様体のそれと等しい内在次元を持つ。 0.68
The ambient dimension is the dimension of the space in which the data is expressed (e g a circle has intrinsic dimension 1 and ambient dimension 2). 周囲次元は、データが表現される空間の次元である(例えば、円は内在次元 1 と周囲次元 2 を持つ)。 0.67
6 6 0.85

Figure 2: Left: Runtimes of the FKT for matrix-vector multiplies for the Matérn kernel with ν = 1/2. 図2:左: ν = 1/2 のマテラン核に対する行列ベクトル乗法に対する FKT のランタイム。 0.78
Dashed lines show results for p = 4 and dotted lines show p = 6. ダッシュラインはp = 4の結果を示し、点線はp = 6を示す。 0.86
Right: The lines are estimates of the upper bound for d = 3 in (9) for various kernels found by ﬁxing r(cid:48)/r = 1/2, summing from p + 1 to 30, and taking the maximum over 2000 uniformly chosen points in r ∈ [0, 20] (we do not see growth in r). 右: ラインは、r(cid:48)/r = 1/2 を固定し、p + 1 から 30 に和を付け、r ∈ [0, 20] において2000 以上の一様選択点を取ることにより得られる様々な核に対する d = 3 in (9) の上界の推定である。 0.76
These estimates are shown for the Exponential, Matérn, Cauchy, and Rational Quadratic kernels as described in Table 1. これらの推定は表1に示すように指数、マテラン、コーシー、およびラショナル二次核に対して示される。

0.73
The triangles are experimentally observed errors which are calculated for the p = 4 Cauchy kernel FKT approximation by taking the maximum absolute error of the truncated expansion for 1000 randomly selected pairs of points r(cid:48), r satisfying |r(cid:48)| = 1,|r| = 2. これらの三角形は、p = 4 コーシー核 FKT 近似に対して、ランダムに選択された1000個の点 r(cid:48)、r を満たす |r(cid:48)| = 1,|r| = 2 に対するトランケート展開の最大絶対誤差を取ることによって計算される実験的誤差である。 0.71
FKTcost = O(cid:16) fktcost = o(cid:16) 0.80
(cid:16) (cid:17)(cid:17) (cid:16) (cid:17)(cid:17) 0.77
= O(cid:16) = O(cid:16) 0.88
a (cid:17) あ (cid:17) 0.64
factor exponential in the intrinsic dimension. 内在次元における指数係数。 0.68
Letting di, da be the intrinsic and ambient dimensions of the data, we have di, da をデータの内在的かつ周囲的次元とするなら、 0.57
N mcdi where we have set m = O(dp a) and cn, cf are constants which depend on the problem geometry, typically between 2 and 5. N m = O(dp a) と cn, cf を持つような mcdi は、通常 2 から 5 の間の問題幾何学に依存する定数である。 0.82
Note that in cases where the additional compression described at the end of Section 3.4 is applied, the size P of the expansion can be reduced by a factor of d and the dp a term in (11) becomes dp−1 注意すべき点は、セクション3.4の最後に記述された追加圧縮が適用される場合、拡張のサイズ P は d の因子によって減少し、11 の項 dp は dp−1 となることである。 0.81
f ) log(N/m)dp f) log(N/m)dp 0.93
N log(N/dp N log(N/dp) 0.72
n + (1+cdi n + (1+cdi) 0.73
(11) . a a) × cdi (11) . あ cdi (複数形 cdis) 0.68
f × dp a 4.3 Limitations f × dp あ 4.3 制限 0.67
The FKT will generally not scale well to datasets in high dimensions, although its underlying expansions remain accurate. FKTは一般的に高次元のデータセットにはスケールしないが、基礎となる拡張は正確である。 0.70
The problem is that the method requires dense computation of points nearby each other, which leads to poor scaling in high dimensions when points tend to be closer together. 問題は、この手法が互いに近接する点の密接な計算を必要とするため、点が近接する傾向がある場合、高次元のスケーリングが不十分になる。 0.67
In contrast, the FGT provide a low-rank approximation for points nearby to each other based on the global low-rankness of the Gaussian kernel. 対照的に、FGT はガウス核の大域的低ランク性に基づいて、互いに近くの点に対する低ランク近似を提供する。 0.61
Although the FKT can provide low-rank approximations for distant points, it cannot yet do so for nearby points. fkt は遠方の点に対して低位近似を与えることができるが、近傍の点に対してはまだそうはならない。 0.57
Although the FKT automatically ﬁnds the analytical expansions foundational to the FMM, it scales quasi-linearly rather than linearly as the FMM does. FKTはFMMに根ざした解析的展開を自動的に見つけるが、FMMのように線形ではなく準線形にスケールする。 0.75
One way to make the FKT a linear algorithm (taking further inspiration from the FMM) would be to develop translation operators for the expansion general to any kernel. FKTを線形アルゴリズム(FMMからさらにインスピレーションを得た)にする一つの方法は、任意のカーネルへの拡張一般のための変換演算子を開発することである。

0.86
Finally, in contrast to the FGT and the FMM, the FKT lacks particularly helpful theoretical bounds on the error, owing mainly to its dense theoretical underpinning. 最後に、FGT と FMM とは対照的に、FKT は、主にその密度の強い理論的基盤のため、誤差に特に有用な理論的境界を欠いている。 0.72
We present empirical observations in this work, but future developments should provide deeper illumination into the error guarantees that can be given for kernels with known bounds on their derivatives. 我々はこの研究で経験的な観察を行うが、将来の発展は、その導関数に既知の境界を持つカーネルに与えられる誤差保証をより深く照らすべきである。 0.67
5 Experiments We’ve implemented the FKT in Julia as part of an open source toolkit2, making use of the NearestNeighbors.jl package (Carlsson et al , 2020) to compute near and far sets of points, and the TaylorSeries.jl package (Benet & Sanders, 2019) to automatically compute derivatives. 5 実験 我々は、JuliaのFKTをオープンソースツールキット2の一部として実装し、NearestNeighbors.jlパッケージ(Carlsson et al , 2020)を使って、近点と遠点の計算を行い、TaylorSeries.jlパッケージ(Benet & Sanders, 2019)を使って、導関数を自動的に計算しました。 0.76
Both packages are licensed under the MIT “Expat” License. どちらのパッケージもMIT “Expat” Licenseでライセンスされている。 0.73
The synthetic experiments were performed 2https://github.com/ jpryan1/FastKernelTr ansform.jl 合成実験が行われた 2https://github.com/ jpryan1/FastKernelTr ansform.jl 0.61
7 2×1044×1048×1041.6×105Number of points100101102103Ti me (s)Runtime vs. problem sized=3d=4d=5tntn25.07.510.012.5 15.017.520.0p1071061 05104103102101Abs. 7 2×1044×1048×1041.6×105Number of points100101102103Ti me (s)Runtime vs. problem size=3d=4d=5tntn25.07.510.012.5 15.017.520.0p1071061 05104103102101Abs 0.56
errorError vs. Truncation ParameterExpCauchyMa ternRQd=3d=9 errorError vs. TruncationパラメータExpCauchyMaternRQd=3d=9 0.47

Figure 3: Left: Runtimes and relative errors for a series of matrix vector multiplies using the Cauchy kernel on a 2D dataset of 20k uniformly distributed points in the unit square. 図3:左: 単位正方形の20k点の2次元データセット上のコーシーカーネルを用いた一連の行列ベクトル乗法に対する実行時と相対誤差。 0.73
B-H refers to the Barnes-Hut method, which is equivalent to the p = 0 FKT with centers of masses as the expansion centers. B-H は、膨張中心として質量の中心を持つ p = 0 FKT に相当するBarnes-Hut 法を指す。 0.80
The maximum leaf capacity was 512, and for each p, we varied the distance parameter θ between 0.25 and 0.75. 最大葉容量は512で, それぞれ0.25から0.75までの距離パラメータθを変動させた。 0.75
Right: A t-SNE embedding of the MNIST training set of 60,000 images of digits computed via application of FKT. 右: MNIST トレーニングセットの t-SNE 埋め込みは FKT の応用により計算された 60,000 桁の画像である。 0.72
single-threaded on a 2020 Apple Macbook Air with an M1 CPU and 8GB of RAM, and the regression experiment was performed on a 2017 MacBook with a Dual-Core Intel Core i7 and 16GB of RAM. 2020年のApple Macbook AirにはM1 CPUと8GBのRAMが搭載され、2017年のMacBookにはデュアルコアのIntel Core i7と16GBのRAMが搭載された。 0.80
5.1 Synthetic Data To test the runtime of the algorithm, we generate a synthetic dataset of points uniformly distributed on a unit hypersphere. 5.1 合成データ アルゴリズムのランタイムをテストするために,単位超球面上に均一に分布する点の合成データセットを生成する。 0.76
We then approximate a matrix-vector multiplication with a Matérn kernel matrix (see Table 1) on this dataset against a random vector. 次に、行列ベクトル乗法を、このデータセット上のマテラン核行列とランダムベクトルとを近似する(表1参照)。 0.75
Our test uses an distance parameter value of θ = 0.75, maximum leaf capacity of 512, and includes results for truncation parameter p = 4, 6. 本試験では,最大リーフ容量が512であるθ = 0.75 の距離パラメータ値を用い,切断パラメータ p = 4, 6 の値を含む。 0.82
Results for this test in a variety of dimensions and problem sizes are shown in Figure 2, left—the runtime is seen to be quasi-linear in the problem size. このテストの結果、様々な次元と問題のサイズが図2に示されています。

0.84
We observe the FKT to become faster than dense matrix multiplication at N = 1000 for d = 3, N = 5000 for d = 4, and N = 20, 000 for d = 5. 我々は FKT が d = 3, N = 5000 for d = 4, N = 20 000 for d = 5 において N = 1000 よりも高速になるのを観察する。 0.78
To test the accuracy of the approximation, we compare the truncated expansion to the true kernel value for the Cauchy kernel in 3 and 9 dimensions. 近似の精度をテストするために、3次元および9次元のコーシーカーネルの真のカーネル値と比較する。 0.54
The errors are calculated for the p-term approximation for 1000 randomly selected pairs of points r(cid:48), r satisfying |r(cid:48)| = 1,|r| = 2, and p is swept from 6 to 18 (see Figure 2, right). 誤差は、1000個のランダムに選択された点 r(cid:48)、|r(cid:48)| = 1,|r| = 2 を満たす r の p 項近似に対して計算され、p は 6 から 18 にずれる(図 2 を参照)。 0.79
The error is seen to decay exponentially with p in both kernels, and not be affected by dimension. この誤差は両カーネルのpで指数関数的に崩壊し、次元に影響されない。 0.68
Results for this experiment in more dimensions and for more kernels can be found in Section B.2. この実験の結果は、より多くの次元とより多くのカーネルに対して、セクションB.2で見ることができる。 0.57
5.2 Stochastic Neighborhood Embedding 5.2 確率的近傍埋め込み 0.52
The stochastic neighborhood embedding (SNE) was proposed by Hinton & Roweis (2002), and Van Der Maaten & Hinton (2008) followed-up that work with the improved t-distributed SNE (t-SNE). 確率的近傍埋め込み (SNE) は Hinton & Roweis (2002) と Van Der Maaten & Hinton (2008) によって提案され、改良された t 分散 SNE (t-SNE) で動作する。 0.78
The t-SNE is widely used as an effective tool for dimensionality reduction for data visualization. t-SNEは、データ視覚化のための次元削減の有効なツールとして広く利用されている。 0.61
An implementation of its optimization routine requires sums of and matrix-vector-produc ts with kernel matrices with N 2 entries, which does not scale well to large data sets. 最適化ルーチンの実装には、n2エントリを持つカーネル行列を持つ行列と行列ベクトル-積の和が必要である。 0.63
In particular, the relevant gradient of the t-SNE objective contains matrix-vector products with a kernel matrix of the Cauchy kernel (1 + r2)−1 with two-dimensional inputs, which is a prime candidate for the application of FKT. 特に、t-SNE目的物の関連する勾配は、2次元入力を持つコーシー核(1 + r2)−1の核行列を持つ行列ベクトル積を含み、これはFKTの適用の素候補である。 0.79
Previously, Van Der Maaten (2014) proposed accelerated methods for t-SNE based on tree codes including the aforementioned Barnes-Hut scheme. 以前、Van Der Maaten (2014) は前述のBarnes-Hutスキームを含む木コードに基づいた t-SNE の高速化手法を提案した。 0.60
While the Barnes-Hut scheme is simpler, Fig. Barnes-Hutのスキームはシンプルだが、Fig。 0.61
3, left shows that FKT exhibits a superior accuracy-runtime trade-off if more accuracy is desired. 3では、FKTがより正確であれば、より優れた精度-実行時のトレードオフを示すことを示す。 0.58
The plot was generated by varying the θ distance parameter in a similar vein as Van Der Maaten (2014). このプロットは、Van Der Maaten (2014)と同様の静脈でθ距離パラメータを変化させることで生成された。 0.72
While very high accuracy might not be of utmost concern for the optimization of a t-SNE, which has a more qualitative goal, this result more generally demonstrates that FKT achieves a very high degree of accuracy, while also highlighting FKT’s generality, since it needs no manual adaption to work on the relevant matrices and compute the visualization of MNIST (LeCun & Cortes, 2010) in Fig. 非常に高い精度は、より定性的ゴールを持つt-SNEの最適化には最も懸念されないかもしれないが、この結果はより一般的に、FKTが非常に高い精度を達成する一方で、FKTの一般性を強調している。

0.72
3. The MNIST data is licensed under the CC BY-SA 3.0 license. 3. MNISTデータはCC BY-SA 3.0ライセンスでライセンスされている。 0.76
8 4×1018×1011.6×100Time (s)10910810710610510 4103102Relative errorTime & error with varying distance param B-Hp=2p=4p=60123456789 8 4×1018×101×101×100time (s)10910810710610510 4103102 パラムb-hp=2p=60123456789 0.69

Figure 4: Sea surface temperatures collected by a single satellite throughout one day (left) and the posterior mean of a Gaussian process with a Matérn kernel conditioned on seven days of data. 図4: 単一の衛星が1日(左)を通して収集した海面温度と、マテラン核が7日間のデータで条件付けられたガウス過程の後部平均値。 0.84
5.3 Gaussian Process Regression of Sea Surface Temperature 5.3 海面温度のガウス過程回帰 0.80
Gaussian processes (GPs) constitute another important class of a kernel methods. ガウス過程(GP)は、カーネルメソッドの別の重要なクラスを構成する。 0.69
Importantly, inference of the posterior predictive mean of a GP can be carried out exclusively through matrixvector multiplications with kernel matrices and a diagonal “noise” variance matrix (Wang et al , 2019). 重要なことに、GPの後方予測平均の推論は、カーネル行列と対角的な「ノイズ」分散行列との行列ベクトル乗法(Wang et al , 2019)によってのみ行うことができる。 0.77
To highlight the generality of FKT, we use it here to compute a GP regressor on sea surface temperature data from Copernicus, the European Union’s Earth Observation Programme (Merchant et al , 2019), which is licensed under the CC-BY 4.0 license. FKTの一般性を強調するために、我々は、CC-BY 4.0ライセンスの下でライセンスされた欧州連合の地球観測プログラム(Merchant et al , 2019)であるCopernicusの海面温度データ上のGP回帰器をここで計算する。 0.86
The data set is collected by a satellite orbiting the earth several times per day, leading to measurement locations with a complex spatial structure (see Fig 4, left). データセットは1日に数回地球を周回する衛星によって収集され、複雑な空間構造を持つ測定場所へと導かれる(図4参照)。 0.85
Each data point comes with an uncertainty estimate, which we use to populate the diagonal noise variance matrix of the model. 各データポイントには不確実性推定が付属しており、これはモデルの対角的雑音分散行列を配置するのに使用される。

0.78
We consider data for the ﬁrst seven days of 2019, for which more than 8 million data points were collected and sub-sampled it down to a still considerable 145,913 observations by taking every 56th data point in the temporal order in which they were collected. 2019年の最初の7日間のデータでは、800万以上のデータポイントが収集され、収集された時間順の56番目のデータポイントごとに、まだかなりの145,913の観測結果にサブサンプリングされた。 0.78
We then evaluated the posterior predictive mean of a GP with the Matérn-3/2 kernel conditioned on the observations and their uncertainties at 480,000 predictive points to arrive at the result on the right of Fig 4. 次に,観測に基づいて条件づけられたmatérn-3/2カーネルを用いたgpの後方予測平均と,その不確かさを480,000の予測点で評価した。 0.75
We restricted the predictions to be within 60 degrees of latitude of the equator, since the satellite data is very sparse in the polar regions. 我々は、衛星データは極域では非常に少ないため、赤道の緯度60度以内の予測を制限した。 0.67
The entire computation completed in around twelve minutes on a 2017 MacBook with a Dual-Core Intel Core i7 and 16GB of RAM, highlighting once more the rare combination of generality and high efﬁciency that FKT achieves. 計算は2017年のMacBookの約12分で完了し、デュアルコアのIntel Core i7と16GBのRAMを搭載しました。

0.65
6 Discussion and broader impacts 6 議論と幅広い影響 0.75
We’ve presented the Fast Kernel Transform, a general method for the automatic computation of analytical expansions of isotropic kernels which can be used in hierarchical matrix algorithms on datasets in moderate dimensions. 我々は、中間次元のデータセット上の階層行列アルゴリズムで使用できる等方性カーネルの解析的拡張の自動計算法であるFast Kernel Transformを発表した。 0.71
The FKT has a high, quantiﬁable, and controllable level of accuracy, and its cost grows only quasi-linearly in the number of data points and polynomially in the ambient dimension. FKTは高い、定量化され、制御可能な精度を持ち、そのコストはデータポイントの数と周辺次元の多項式数でほぼ直線的に増大する。 0.66
While our work is entirely algorithmic in nature, it is important to remark that using approximation schemes such as the FKT can introduce additional variation in downstream tasks that are not anticipated. 我々の研究は本質的に完全にアルゴリズム的だが、fktのような近似スキームを用いることで、期待できない下流タスクにさらなるバリエーションをもたらすことは重要である。 0.60
While we provide controllable levels of accuracy, it is still important to assess the level of sensitivity of different applications to such perturbations and validate models developed with these methods across a broad range of criteria. 我々は、制御可能な精度レベルを提供するが、これらの摂動に対する異なる応用の感度レベルを評価し、これらの手法で開発されたモデルを幅広い基準で検証することが依然として重要である。 0.65
The method develops a new analytic approximation scheme whose number of terms is equal to those of the expansions developed for the Improved FGT, but for a much broader set of kernels. この手法は、改良されたFGTのために開発された拡張の項数に等しい新しい解析近似法を開発するが、より広い範囲のカーネルに対してである。 0.79
At its core, our method reﬂects a generalization of the mathematical tools underlying seminal works in kernel methods, such as the FMM and the FGT, and opens up many opportunities for further theoretical study and algorithmic development, such as work on a more rigorous foundation for the class of kernels for which the FKT excels, and work on removing the ambient dimension from the cost of FKT via an appropriate selection of harmonics to retain when an underlying intrinsically lower-dimensional manifold is known or may be discovered. At its core, our method reﬂects a generalization of the mathematical tools underlying seminal works in kernel methods, such as the FMM and the FGT, and opens up many opportunities for further theoretical study and algorithmic development, such as work on a more rigorous foundation for the class of kernels for which the FKT excels, and work on removing the ambient dimension from the cost of FKT via an appropriate selection of harmonics to retain when an underlying intrinsically lower-dimensional manifold is known or may be discovered. 0.89
Further, the logarithmic term could be removed by the creation of translation operators so as to completely generalize the FMM to this broad class of kernels. さらに、対数項は、FMMをこの広い種類のカーネルに完全に一般化するために翻訳演算子を作成することによって取り除くことができる。 0.68
These translation operators are the subject of current development by the authors. これらの翻訳オペレータは、著者による現在の開発対象である。 0.75
9 −150−100−50050100150−75−50−25025507505101520253 035degrees Clatitudelongitude−150−100−50050100150−75−50−250255075longitudela titude−150−100−50050100150−60−3003060longitudelati tude 9 -150−100−5005050150−75−50−50255050505050152025 3035度 クラティ度経度−150−100−50050150−75−250255075経度−150−100−5005050150−60−3003060経度 0.46

We believe that the methods contained herein could prove useful for a wide range of practitioners and researchers of kernel methods, enabling them to apply their methods to much larger problem instances than without acceleration, and have made an open-source implementation of FKT available. この手法は、カーネルメソッドの幅広い実践者や研究者にとって有用であり、アクセラレーションなしでよりもはるかに大きな問題インスタンスにメソッドを適用することが可能であり、FKTのオープンソース実装を利用可能にしている。 0.75
References Ambikasaran, S., Foreman-Mackey, D., Greengard, L., Hogg, D. W., and O’Neil, M. Fast direct methods for gaussian processes. Ambikasaran, S., Foreman-Mackey, D., Greengard, L., Hogg, D. W., and O'Neil, M. Fast direct methods for gaussian process。 0.89
IEEE transactions on pattern analysis and machine intelligence, 38(2):252–265, 2015. IEEEによるパターン分析とマシンインテリジェンスに関するトランザクション 38(2):252–265, 2015 0.88
Arfken, G. Mathematical Methods for Physicists. G. 物理学者の数学的方法 0.69
Academic Press, Inc., San Diego, third edition, Academic Press, Inc., San Diego, 第3版 0.83
1985. Askey, R. and Ismail, M. E.-H. A generalization of ultraspherical polynomials. 1985. Askey, R. and Ismail, M. E.-H. 超球面多項式の一般化 0.78
In Studies in pure mathematics, pp. 純粋に研究し 数学、p.。 0.68
55–78. Springer, 1983. 55–78. 1983年、スプリンガー。 0.62
Avery, J. Gegenbauer Polynomials, pp. Avery, J. Gegenbauer Polynomials, pp。 0.92
25–46. Springer Netherlands, Dordrecht, 1989. 25–46. オランダ、ドルトレヒト、1989年。 0.58
ISBN 978-94-009-2323-2. doi: 10.1007/978-94-009-2 323-2_3. ISBN 978-94-009-2323-2. doi: 10.1007/978-94-009-2 323-2_3 0.28
URL https://doi.org/10.1 007/ 978-94-009-2323-2_3. URL https://doi.org/10.1 007/978-94-009-2323- 2_3 0.18
Barnes, J. and Hut, P. A hierarchical o (n log n) force-calculation algorithm. Barnes, J. and Hut, P. A hierarchical o (n log n) force-calculation algorithm。 0.94
nature, 324(6096): 自然 324(6096): 0.66
446–449, 1986. 446–449, 1986. 0.84
Benet, L. and Sanders, D. P. Taylorseries.jl: Taylor expansions in one and several variables in julia. benet, l. and sanders, d. p. taylorseries.jl: taylor expansions in one and several variable in julia (英語) 0.71
Journal of Open Source Software, 4(36):1043, 2019. doi: 10.21105/joss.01043. Journal of Open Source Software, 4(36):1043, 2019. doi: 10.21105/joss.01043 0.84
URL https://doi.org/10.2 1105/joss.01043. URL https://doi.org/10.2 1105/joss.01043 0.41
Bentley, J. L. Multidimensional binary search trees used for associative searching. Bentley, J. L. 多次元二分探索木を連想探索に用いる。 0.67
Commun. ACM, 18(9):509–517, September 1975. Commun ACM, 18(9):509-517, 1975年9月。 0.60
ISSN 0001-0782. doi: 10.1145/361002.36100 7. ISSN 0001-0782. doi: 10.1145/361002.36100 7 0.53
URL https://doi.org/10.1 145/361002.361007. URL https://doi.org/10.1 145/361002.361007 0.41
Börm, S. and Garcke, J. Approximating gaussian processes with H2-matrices. Börm, S. and Garcke, J. Approximating gaussian process with H2-matrices。 0.79
In European Confer- in European Confer- 0.87
ence on Machine Learning, pp. ence on Machine Learning, pp。 0.80
42–53. Springer, 2007. 42–53. 2007年、スプリンガー。 0.63
Businger, P. and Golub, G. H. Linear least squares solutions by householder transformations. Businger, P. and Golub, G. H. Linear least squares Solutions by householder transformations。 0.97
Numerische Mathematik, 7(3):269–276, 1965. Numerische Mathematik, 7(3):269–276, 1965。 0.90
Carlsson, K., Karrasch, D., Bauer, N., Kelman, T., Schmerling, E., Hofﬁmann, J., Visser, M., San-Jose, P., Christie, J., Ferris, A., Anthony Blaom, P., Foster, C., Saba, E., Goretkin, G., Orson, I., Samuel, O., Choudhury, S., and Nagy, T. Kristofferc/nearestn eighbors.jl: v0.4.8. Carlsson, K., Karrasch, D., Bauer, N., Kelman, T., Schmerling, E., Hoffimann, J., Visser, M., San-Jose, P., Christie, J., Ferris, A., Anthony Blaom, P., Foster, C., Saba, E., Goretkin, G., Orson, I., Samuel, O., Choudhury, S., and Nagy, T. Kristofferc/nearestn eighbors.jl: v0.4.8。 0.98
December 2020. doi: 10.5281/zenodo.43016 93. 2020年12月 doi 10.5281/zenodo.43016 93 0.52
URL https://doi.org/10.5 281/zenodo.4301693. URL https://doi.org/10.5 281/zenodo.4301693 0.41
Chan, T. F. Rank revealing qr factorizations. Chan, T. F. Ranking qr factorizations 0.70
Linear algebra and its applications, 88:67–82, 1987. 線型代数とその応用, 88:67-82, 1987 0.72
Cheng, H., Gimbutas, Z., Martinsson, P. G., and Rokhlin, V. On the compression of low rank matrices. Cheng, H., Gimbutas, Z., Martinsson, P. G., Rokhlin, V. 低階行列の圧縮について 0.77
SIAM J. Sci. SIAM J. Sci 0.77
Comput., 26(4):1389–1404, April 2005. 論文26(4):1389–1404, 2005年4月 0.68
ISSN 1064-8275. doi: 10.1137/030602678. ISSN 1064-8275. doi: 10.1137/030602678 0.62
URL https://doi.org/10.1 137/030602678. URL https://doi.org/10.1 137/030602678 0.46
Cheng, H., Crutchﬁeld, W., Gimbutas, Z., Greengard, L., Ethridge, J., Huang, J., Rokhlin, V., Yarvin, N., and Zhao, J. Cheng, H., Crutchfield, W., Gimbutas, Z., Greengard, L., Ethridge, J., Huang, J., Rokhlin, V., Yarvin, N., Zhao, J。 0.82
A wideband fast multipole method for the helmholtz equation in three dimensions. 3次元のヘルムホルツ方程式に対する広帯域高速多重極法 0.70
Journal of Computational Physics, 216(1):300–325, July 2006. Journal of Computational Physics, 216(1):300–325, July 2006 0.92
ISSN 0021-9991. doi: 10.1016/j.jcp.2005.1 2.001. ISSN 0021-9991. doi: 10.1016/j.jcp.2005.1 2.001 0.39
Funding Information: The authors were supported in part by DARPA/AFOSR under the contracts F49620-03-C-0052 and F49620-03-C-0041, and by DARPA under contract HR0011-05-P-0001. F49620-03-C-0052とF49620-03-C-0041、HR0011-05-P-0001の契約でDARPA/AFOSRの支援を受けた。 0.47
De G. Matthews, A. G., Van Der Wilk, M., Nickson, T., Fujii, K., Boukouvalas, A., León-Villagrá, P., Ghahramani, Z., and Hensman, J. Gpﬂow: A gaussian process library using tensorﬂow. De G. Matthews, A. G., Van Der Wilk, M., Nickson, T., Fujii, K., Boukouvalas, A., León-Villagrá, P., Ghahramani, Z., and Hensman, J. Gpflow: テンソルフローを用いたガウス的なプロセスライブラリ。 0.89
The Journal of Machine Learning Research, 18(1):1299–1304, 2017. journal of machine learning research, 18(1):1299–1304, 2017年。 0.90
Deisenroth, M. and Ng, J. W. Distributed gaussian processes. Deisenroth, M. and Ng, J. W. Distributed Gaussian Process 0.88
In International Conference on Machine 国際機械会議に参加して 0.75
Learning, pp. 1481–1490. 学業、p.。 1481–1490. 0.64
PMLR, 2015. 2015年、PMLR。 0.70
10 10 0.85

DLMF. NIST Digital Library of Mathematical Functions. DLMF NIST Digital Library of Mathematical Functions (英語) 0.67
http://dlmf.nist.gov /, Release 1.1.1 of 2021-03-15. http://dlmf.nist.gov /, Release 1.1.1 of 2021-03-15 0.51
URL http://dlmf.nist.gov /. URL http://dlmf.nist.gov / 0.58
F. W. J. Olver, A. f・w・j・オルヴァー a. 0.58
B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, M. A. McClain, eds。 0.83
Dong, K., Eriksson, D., Nickisch, H., Bindel, D., and Wilson, A. G. Scalable log determinants for gaussian process kernel learning. Dong, K., Eriksson, D., Nickisch, H., Bindel, D. and Wilson, A. G. Scalable log determinants for gaussian process kernel learning。 0.89
In Advances in Neural Information Processing Systems, pp. ニューラル・インフォメーション・プロセッシング・システムにおける進歩, pp. 0.59
6327–6337, 2017. 6327–6337, 2017. 0.84
Drineas, P., Mahoney, M. W., and Cristianini, N. On the nyström method for approximating a gram drineas, p., mahoney, m. w., and cristianini, n. on the nyström method for approximating a gram 0.78
matrix for improved kernel-based learning. カーネルベースの学習を改善するためのマトリックス。 0.57
journal of machine learning research, 6(12), 2005. journal of machine learning research, 6(12) 2005年。 0.82
Gardner, J., Pleiss, G., Weinberger, K. Q., Bindel, D., and Wilson, A. G. Gpytorch: Blackbox matrixmatrix gaussian process inference with gpu acceleration. Gardner, J., Pleiss, G., Weinberger, K. Q., Bindel, D. and Wilson, A. G. Gpytorch: Blackbox matrixmatrix gaussian process inference with gpu accelerate。 0.92
In Advances in Neural Information Processing Systems, pp. ニューラル・インフォメーション・プロセッシング・システムにおける進歩, pp. 0.59
7576–7586, 2018. 7576–7586, 2018. 0.84
Greengard, L. and Rokhlin, V. A fast algorithm for particle simulations. Greengard, L. and Rokhlin, V. 粒子シミュレーションのための高速アルゴリズム 0.89
Journal of computational Journal of Computer 0.66
physics, 73(2):325–348, 1987. 物理学、73(2):325–348, 1987。 0.78
Greengard, L. and Strain, J. Greengard, L. and Strain, J. 0.94
The fast gauss transform. 速いガウスは変態する。 0.57
SIAM Journal on Scientiﬁc and Statistical SIAM Journal on Scientific and Statistical 0.85
Computing, 12(1):79–94, 1991. 12(1):79-94、1991年。 0.66
Greengard, L., Huang, J., Rokhlin, V., and Wandzura, S. Accelerating fast multipole methods for the helmholtz equation at low frequencies. Greengard, L., Huang, J., Rokhlin, V., and Wandzura, S. Accelerating fast multipole method for the helmholtz equation at low frequency。 0.84
IEEE Computational Science and Engineering, 5(3):32–38, 1998. doi: 10.1109/99.714591. IEEE Computational Science and Engineering, 5(3):32-38, 1998. doi: 10.1109/99.714591 0.76
Hinton, G. E. and Roweis, S. Stochastic neighbor embedding. Hinton, G. E. and Roweis, S. Stochastic neighbor embeddeding 0.93
Advances in neural information processing systems, 15:857–864, 2002. 神経情報技術の進歩 処理システム 15:857–864, 2002。 0.76
Kumar, S., Mohri, M., and Talwalkar, A. Kumar, S., Mohri, M., Talwalkar, A。 0.74
Ensemble nystrom method. Ensemble nystrom メソッド。 0.71
Advances in Neural Information ニューラル情報技術の進歩 0.69
Processing Systems, 22:1060–1068, 2009. 処理システム 22:1060–1068, 2009 0.85
Kumar, S., Mohri, M., and Talwalkar, A. Kumar, S., Mohri, M., Talwalkar, A。 0.74
Sampling methods for the nyström method. nyström法におけるサンプリング法 0.61
The Journal of journal (複数形 journals) 0.44
Machine Learning Research, 13(1):981–1006, 2012. 機械学習研究 13(1):981–1006, 2012 0.80
LeCun, Y. and Cortes, C. MNIST handwritten digit database. LeCun, Y. and Cortes, C. MNIST 手書き桁データベース 0.82
2010. URL http://yann.lecun. 2010. URL http://yann.lecun.co m 0.71
com/exdb/mnist/. com/exdb/mnist/。 0.42
Martinsson, P.-G. Fast direct solvers for elliptic PDEs. martinsson, p.-g. fast direct solvers for elliptic pdes 0.79
SIAM, 2019. 2019年、SIAM。 0.73
Merchant, C. J., Embury, O., Bulgin, C. E., Block, T., Corlett, G. K., Fiedler, E., Good, S. A., Mittaz, J., Rayner, N. A., Berry, D., et al Satellite-based time-series of sea-surface temperature since 1981 for climate applications. Merchant, C. J., Embury, O., Bulgin, C. E., Block, T., Corlett, G. K., Fiedler, E., Good, S. A., Mittaz, J., Rayner, N. A., Berry, D., et al Satellite-based temperature of sea-ground temperature for climate applications。

0.98
Scientiﬁc data, 6(1):1–18, 2019. 科学データ 6(1):1-18, 2019。 0.87
Minden, V., Damle, A., Ho, K. L., and Ying, L. Fast spatial gaussian process maximum likelihood estimation via skeletonization factorizations. Minden, V., Damle, A., Ho, K. L., and Ying, L. Fast space gaussian process maximum estimation by skeletonization factorizations。 0.81
Multiscale Modeling & Simulation, 15(4):1584–1611, 2017. マルチスケールモデリングとシミュレーション, 15(4):1584–1611, 2017 0.87
Phillips, J. R. and White, J. Philips, J. R. and White, J. 0.89
A precorrected-fft method for capacitance extraction of complicated 3-d 複雑3次元キャパシタンス抽出のための補正fft法 0.72
structures. In ICCAD, volume 94, pp. 構造。 ICCAD, Volume 94, pp。 0.69
268–271. Citeseer, 1994. 268–271. 1994年、Citeseer。 0.70
Rasmussen, C. E. and Williams, C. K. I. Gaussian Processes for Machine Learning (Adaptive Rasmussen, C. E. and Williams, C. K. I. Gaussian Processs for Machine Learning (Adaptive) 0.88
Computation and Machine Learning). The MIT Press, 2005. 計算と機械学習)。 2005年、MIT出版。 0.60
ISBN 026218253X. ISBN 026218253X 0.76
Riordan, J. Derivatives of composite functions. Riordan, J. 合成関数の導関数。 0.76
Bulletin of the American Mathematical Society, 52 The American Mathematical Society, 52(英語) 0.82
(8):664 – 667, 1946. doi: bams/1183509573. (8):664 - 667, 1946. doi: bams/1183509573 0.90
URL https://doi.org/. URL https://doi.org/ 0.67
Scholkopf, B. and Smola, A. J. Scholkopf, B. and Smola, A. J. 0.98
Learning with kernels: support vector machines, regularization, カーネルによる学習: ベクトルマシンのサポート、正規化、 0.75
optimization, and beyond. 最適化、そしてその先。 0.63
Adaptive Computation and Machine Learning series, 2018. Adaptive Computation and Machine Learning series, 2018。 0.79
Shawe-Taylor, J., Cristianini, N., et al Kernel methods for pattern analysis. Shawe-Taylor, J., Cristianini, N., et al Kernel 法によるパターン解析 0.90
Cambridge university press, 2004. ケンブリッジ大学 2004年出版。 0.67
Snelson, E. and Ghahramani, Z. Snelson, E. and Ghahramani, Z 0.81
Sparse gaussian processes using pseudo-inputs. 擬似入力を用いたスパースガウス過程 0.65
Advances in neural information processing systems, 18:1257–1264, 2005. 神経の進歩 情報処理システム 18:1257–1264, 2005。 0.73
11 11 0.85

Van Der Maaten, L. Accelerating t-sne using tree-based algorithms. Van Der Maaten, L. Accelerating t-sne using tree-based algorithm 0.83
The Journal of Machine Learning Research, 15(1):3221–3245, 2014. 機械学習の日誌 研究報告 15(1):3221–3245, 2014 0.73
Van Der Maaten, L. and Hinton, G. Visualizing data using t-sne. Van Der Maaten, L. and Hinton, G. t-sne を用いたデータの可視化 0.73
Journal of machine learning research, 9(Nov):2579–2605, 2008. 機械学習の日誌 9(Nov):2579–2605, 2008。 0.72
Wang, K., Pleiss, G., Gardner, J., Tyree, S., Weinberger, K. Q., and Wilson, A. G. Exact gaussian processes on a million data points. Wang, K., Pleiss, G., Gardner, J., Tyree, S., Weinberger, K. Q., Wilson, A. G. Exact Gaussian process on 100 million data points。 0.85
In Advances in Neural Information Processing Systems, pp. ニューラル・インフォメーション・プロセッシング・システムにおける進歩, pp. 0.59
14648–14659, 2019. 14648–14659, 2019. 0.84
Wen, Z. and Avery, J. Wen, Z. and Avery, J. 0.94
Some properties of hyperspherical harmonics. 超球面高調波のいくつかの性質 0.54
Journal of Mathematical Physics, Journal of Mathematical Physics (英語) 0.74
26(3):396–403, 1985. doi: 10.1063/1.526621. 26(3):396–403, 1985. doi: 10.1063/1.526621 0.66
URL https://doi.org/10.1 063/1.526621. URL https://doi.org/10.1 063/1.526621 0.40
White, J., Phillips, J., and Korsmeyer, T. Comparing precorrected-fft and fast multipole algorithms In Proceedings of the Colorado White, J., Phillips, J. and Korsmeyer, T. Comparing precorrected-fft and fast multipole algorithm in Proceedings of the Colorado 0.95
for solving three-dimensional potential integral equations,". 三次元ポテンシャル積分方程式の解法」。 0.74
Conference on Iterative Methods, pp. 反復的手法に関する会議, pp. 0.81
4–10. Citeseer, 1994. 4–10. 1994年、Citeseer。 0.70
Williams, C. K. and Seeger, M. Using the nyström method to speed up kernel machines. Williams, C. K. and Seeger, M. using the nyström method to speed up kernel machines。 0.96
In Advances in neural information processing systems, pp. 進歩して 神経情報処理システム p。 0.52
682–688, 2001. 682–688, 2001. 0.84
Wilson, A. and Nickisch, H. Kernel interpolation for scalable structured gaussian processes (kiss-gp). Wilson, A. and Nickisch, H. Kernel interpolation for scalable structured Gaussian process (kiss-gp)。 0.85
In International Conference on Machine Learning, pp. 英語) international conference on machine learning, pp. 0.80
1775–1784, 2015. 1775–1784, 2015. 0.84
Yang, C., Duraiswami, R., Gumerov, N. A., and Davis, L. Improved fast gauss transform and efﬁcient Yang, C., Duraiswami, R., Gumerov, N. A. and Davis, L. Improved fast gauss transform and efficient 0.92
kernel density estimation. カーネル密度の推定。 0.78
IEEE, 2003. 2003年、IEEE。 0.71
Yang, C., Duraiswami, R., and Davis, L. S. Efﬁcient kernel machines using the improved fast gauss Yang, C., Duraiswami, R. and Davis, L. S. Efficient kernel machines using the improve fast gauss 0.92
transform. Advances in neural information processing systems, 17:1561–1568, 2004. 変身。 神経情報処理システムの進歩 17:1561–1568, 2004 0.71
Ying, L. A kernel independent fast multipole algorithm for radial basis functions. Ying, L. A kernel independent fast multipole algorithm for radial basis function。 0.85
Journal of Computational Physics, 213(2):451–457, 2006. 日誌 計算物理学 213(2):451–457, 2006 0.68
Ying, L., Biros, G., and Zorin, D. A kernel-independent adaptive fast multipole algorithm in two and ying, l., biros, g. and zorin, d. a kernel-independent adaptive fast multipole algorithm in two and 0.90
three dimensions. Journal of Computational Physics, 196(2):591–626, 2004. 3次元。 Journal of Computational Physics, 196(2):591–626, 2004 0.81
A Technical Details In this section, we lay out the derivation of the expansion underlying the Fast Kernel transform. 技術的詳細 本稿では,高速カーネル変換の基盤となる拡張の導出について概説する。 0.71
Before the derivation, we review the Gegenbauer polynomials which will feature heavily. 導出前には,gegenbauer 多項式について概説する。 0.57
Additionally, we expand on the opportunity for additional compression for certain types of kernels alluded to in the main text. さらに、本文で暗示される特定の種類のカーネルに対して、さらなる圧縮を行う機会を拡大する。 0.69
Finally we will show the details of the computation of the number of terms in the FKT expansion. 最後に、FKT展開における項数の計算の詳細を示す。 0.52
A.1 Gegenbauer Polynomials A.1 Gegenbauer polynomials 0.68
The generalized multipole expansion is expressed in terms of Gegenbauer polynomials, also known as ultraspherical polynomials (Askey & Ismail, 1983). 一般化多重極拡大は、超球面多項式としても知られるゲゲンバウアー多項式(Askey & Ismail, 1983)で表される。 0.76
For our purposes, these polynomials are best seen as generalizations of the Legendre polynomials which have higher dimensional addition theorems. 我々の目的のために、これらの多項式はより高次元の加算定理を持つルジャンドル多項式の一般化と見なされる。 0.56
They satisfy the recurrence relation 彼らは再発関係を満たす 0.67
C α C α C α 0 (x) = 1, 1 (x) = 2αx, Cα Cα Cα 0 (x) = 1, 1 (x) = 2αx, 0.87
n (x) =(cid:2)2x(n + α − 1)C α n (x) =(cid:2)2x(n + α − 1)C α 0.98
n−1(x) − (n + 2α − 2)C α and the hyperspherical harmonic addition theorem (Wen & Avery, 1985) k (r)∗, n−1(x) − (n + 2α − 2)C α と超球面調和付加定理 (Wen & Avery, 1985) k (r)∗, 0.81
k (r(cid:48))Y h Y h k(r(cid:48))y h y h 0.95
(cid:88) k (cos γ) = (cid:88) k (cos γ) = 0.82
C (α) n−2(x)(cid:3)/n, C (α) n−2(x)(cid:3)/n, 0.82
1 Z (α) k where r, r(cid:48) ∈ Rd have angle γ between them, α = d 1 Z (α) k r, r(cid:48) ∈ rd がそれらの間の角 γ, α = d を持つとき 0.83
is a normalization term, and Hk := {(µ1, . 正規化という用語で Hk := {(μ1, 。 0.72
. . µd−2) : k ≥ µ1 ≥ ··· ≥ |µd−2| ≥ 0}. . . μd−2) : k ≥ μ1 ≥ ··· ≥ |μd−2| ≥ 0}。 0.79
h∈Hk 2 − 1, Z (α) h・Hk 2 − 1, Z(α) 0.87
k 12 (12) (13) k 12 (12) (13) 0.85

A.2 Derivation of the FKT expansion A.2 FKT拡大の導出 0.87
√ Before going through the proof of the main theorem of the main text, we will need a lemma concerning the application of Faa di Bruno’s theorem to our particular composition of functions (f (g(ε)) where 1 + ε). √ 主文の主定理の証明を経る前に、ファア・ディ・ブルーノの定理を函数の特定の構成(f(g(ε))に応用する際の補題(英語版)(lemma)が必要である(ただし、1 + ε)。 0.74
Before that lemma, we prove a combinatorial identity g(ε) = r which will be necessary. その補題の前には、必要となる組合せ恒等式 g(ε) = r が証明される。 0.69
Lemma A.1. 1 + ε and f (g(ε)) = K(r A.1。 1 + ε および f(g(ε)) = K(r) 0.80
√ (cid:19)(cid:18)m − (2k + 1) √ (cid:19)(cid:18)m − (2k + 1) 0.86
(cid:19) n − k (cid:19) n − k 0.82
. Proof. As a preliminary, note that the LHS are entries in Bernoulli’s triangle, and hence satisfy . 証明。 予備として、LHSはベルヌーイの三角形のエントリーであり、従って満足していることに注意してください。

0.70
bm−1,n + bm−1,n−1, m > n > 0 1, bm−1,n + bm−1,n−1,m > n > 0 1 0.89
n = 0. m = n n = 0。 m = n 0.83
n(cid:88) k=0 n(cid:88) K=0 0.68
n(cid:88) k=0 n(cid:88) K=0 0.68
k k = k=0 bm,n = k k = K=0 bm,n = 0.78
(cid:18)2k + 1 (cid:18)2k+1 0.73
(cid:18)m + 1 (cid:19) n(cid:88) 2m − 1, (cid:19)(cid:18)m − (2k + 1) (cid:18)2k + 1 (cid:18)m − k − 1 (cid:19) n(cid:88) n−1(cid:88) (cid:18)(cid:18)m − k − 1 (cid:19) n−1(cid:88) (cid:18)m − k (cid:19) n−1(cid:88) (cid:18)m + 1 (cid:18)m + 1 (cid:88)n(cid:18)m − (cid:18)m − (2k + 1) (cid:18)2k + 1 (cid:18)m − k − 1 (cid:19)n(cid:88) (cid:18)(cid:18)m − k − 1 (cid:19)n−1(cid:88) (cid:18)m − k − 1 (cid:19)m − k (cid:88) (cid:18)m − k (cid:19)n−1(cid:88)

0.78
n − k n − k n − k n − k 0.85
n − k 2k + k=0 n − k 2k+ K=0 0.75
k=0 k=0 k n − k K=0 K=0 k n − k 0.69
2k = = 2n + 2k= = 2n + 0.90
k=0 = 2n + K=0 = 2n + 0.73
(cid:19) = (cid:19) = 0.82
k=0 n − k (cid:18)m − k (cid:19) n(cid:88) (cid:18)m − k − 1 (cid:19) (cid:18)m − k − 1 (cid:19)(cid:19) (cid:18)m − k (cid:19) n(cid:88) K=0 n − k (cid:18)m − k (cid:19) n(cid:88) (cid:18)m − k − 1 (cid:19) (cid:18)m − k − 1 (cid:19)(cid:19) (cid:18)m − k (cid:19) n(cid:88) 0.73
n − k − 1 n − k − 1 n − k − 1 n − k − 1 0.85
2k + n − k 2k + n − k 0.83
2k. k=0 2k. 2kだ K=0 2kだ 0.71
2k It will sufﬁce to show that the RHS follows the same recurrence. 2k RHSが同じ再発を辿っていることを示すのが十分です。 0.76
We refer to the following result from Jenson, 1902: 我々は、Jenson, 1902 の以下の結果を参照する。 0.72
By inspection the m = n and n = 0 cases are immediately conﬁrmed. 検査により、m = n と n = 0 のケースが直ちに確認される。 0.76
If m > n > 0 then m > n > 0 ならば 0.76
Lemma A.2. When n > 0, A.2。 n > 0 の場合。 0.76
∂n ∂εn (cid:0)K(r ∂n ∂εn (cid:0)K(r) 0.70
1 + ε)(cid:1)|ε=0 = 1 + ε(cid:1)|ε=0 = 0.89
√ n(cid:88) √ n(cid:88) 0.85
m=1 where Bnm = (−1)n+m (2n − 2m − 1)! m=1。 どこに Bnm = (−1)n+m (2n − 2m − 1)! 0.67
! 2n and we will use the notation K (m)(r) to mean ∂m ! 2n と表記 k (m)(r) を用いて ∂m を表す。 0.82
∂rm K(r). ∂rm k(r) である。 0.63
Proof. Let g(ε) = r 証明。 g(ε) = r とする 0.69
√ 1 + ε and note that √ 1 + ε と注意してください 0.86
BnmK (m)(r)rm, BnmK (m)(r)rm 0.70
(cid:18)2n − m − 1 (cid:18)2n − m − 1 0.88
(cid:19) m − 1 (cid:19) m − 1 0.82
, (14) g(i)(ε)ε=0 = (−1)i+1 (2i − 3)!! , (14) g(i)(ε)ε=0 = (−1)i+1 (2i − 3)! 0.89
where we will let (2i − 3)!! ここで (2i − 3) とします。 0.71
= 1 when i = 1. i = 1 のとき 1 である。 0.85
By Riordan (1946) n(cid:88) ∂n ∂εn Riordan (1946) n(cid:88) ∂n ∂εn 0.85
1 + ε)(cid:1)|ε=0 = 1 + ε(cid:1)|ε=0 = 0.89
(cid:0)K(r (cid:0)K(r) 0.81
√ 2i m=1 K (m)(g(ε)ε=0) · Bn,m(g(cid:48)(ε)ε=0, g(cid:48)(cid:48)(ε)ε=0, ..., g(n−m+1)(ε)ε=0) √ 2i m=1。 K(m)(g(ε)ε=0) · Bn,m(g(cid:48)(ε)ε=0, g(cid:48)(cid:48)(ε)ε=0, ..., g(n−m+1)(ε)ε=0) 0.75
r, (15) where Bn,m are the Bell polynomials (henceforth we will drop their arguments). rだ (15) ここで Bn,m はベル多項式である(その後、議論を破棄する)。 0.72
Per usual, we set いつも通り 私たちは 0.59
B0,0 = 1 Bn,0 = B0,m = 0. b0,0 = 1 bn,0 = b0,m = 0 0.81
13 13 0.85

Then the Bell polynomials satisfy the recurrence relation するとベル多項式は繰り返し関係を満たす 0.72
We will use this to prove これを使って証明します 0.63
i=1 n−m+1(cid:88) i=1 n−m+1(cid:88) 0.56
(cid:18)n − 1 (cid:19) (cid:18)n − 1(cid:19) 0.84
i − 1 Bn,m = i − 1 Bn,m = 0.85
g(i)(ε)ε=0Bn−i,m−1. g(i)(ε)ε=0Bn−i,m−1。 0.75
Bn,m = (−1)n+m (2n − 2m − 1)!! Bn,m = (−1)n+m (2n − 2m − 1)! 0.96
(2n − m − 1)! (2n − m − 1)! 0.94
2n = (−1)n+mrm 2n = (−1)n+mrm 0.78
(m − 1)! (n − m)!22n−m n ≥ m > 0, (m − 1)! (n − m)!22n−m n ≥ m > 0, 0.91
(cid:18)2n − m − 1 (cid:19) (cid:18)2n − m − 1(cid:19) 0.83
m − 1 rm by induction. m − 1 rm 誘導によって 0.77
We begin with the base cases of n = m = 1 and n > m = 1. まず、n = m = 1 と n > m = 1 の基本ケースから始める。 0.72
For the former, the recurrence relation yields 前者の場合、反復関係は帰結する 0.61
B1,1 = g(cid:48)(ε)ε=0 = B1,1 = g(cid:48)(ε)ε=0 = 0.78
1 2 r, When n > m = 1 the recurrence relation gives 1 2 rだ n > m = 1 のとき、再発関係が与えられる 0.78
B1,1 = (−1)2r1 B1,1 = (−1)2r1 0.63
0! 210!0! = 0! 210!0! = 0.85
1 2 r. and our claim yields 1 2 r. 私たちの主張は 0.73
n(cid:88) (cid:18)n n(cid:88) (cid:18)n 0.84
(cid:19) i=1 (cid:19) i=1 0.69
0 Bn,1 = and our claim yields 0 Bn,1 = 私たちの主張は 0.68
Bn,1 = (−1)n+1r1 Bn,1 = (−1)n+1r1 0.59
g(i)(ε)ε=0Bn−i,0 = g(n)(ε)ε=0 = (−1)(n+1)r g(i)(ε)ε=0Bn−i,0 = g(n)(ε)ε=0 = (−1)(n+1)r 0.85
(2n − 3)! ! (2n − 3)! ! 0.91
2n , (2n − 2)! 2n , (2n − 2)! 0.87
2(2n−1)0! (n − 1)! 2(2n−1)0! (n − 1)! 0.84
(2n − 3)! 2(2n−2)(n − 2)! (2n − 3)! 2(2n−2)(n−2)! 0.93
= (−1)(n+1)r = (−1)(n+1)r 0.88
(2n − 3)! (2n − 2) (2n − 3)! (2n − 2) 0.98
2(2n−2)(n − 2)! 2(2n−2)(n−2)! 0.89
(2n − 2) = (−1)(n+1)r (2n − 2) = (−1)(n+1)r 0.94
(2n − 3)! ! (2n − 3)! ! 0.91
2n For the inductive step, we need to show that 2n 帰納的なステップでは、それを示さなければなりません。 0.59
= (−1)(n+1)r = (−1)(n+1)r 0.88
n−m+1(cid:88) n−m+1(cid:88) 0.53
(cid:19) (cid:18)n − 1 (cid:19) (cid:18)n − 1 0.84
Bn,m = i=1 Bn,m = i=1 0.72
(n − i − m + 1)! (n − i − m + 1)! 0.85
Separating the i = 1 term out so that the double factorial is of positive integers 二重因子が正の整数であるように i = 1 項を分離する 0.72
22n−m+1(m − 2)! 22n−m+1(m − 2)! 0.72
i=1 = rm i − 1 (−1)n+m i=1 =rm i − 1 (−1)n+m 0.72
r 2i (−1)i+1 (2i − 3)!! r 2i (−1)i+1 (2i − 3)! 0.86
(cid:18)n − 1 (cid:19) n−m+1(cid:88) n−m+1(cid:88) (cid:18)n − 1 (cid:19) n−m+1(cid:88) n−m+1(cid:88) 0.62
i − 1 2(2n − m − 2)! i − 1 2(2n − m − 2)! 0.89
(n − m)! + (n − m)! + 0.85
i=2 (cid:32) i=2 (cid:32) 0.69
(−1)n−i+m−1rm−1(2n − 2i − m)! (−1)n−i+m−1rm−1(2n − 2i − m)! 0.61
(m − 2)! (n − i + m − 1)!22n−2i−m+1 (m − 2)! (n − i + m − 1)!22n−2i−m+1 0.78
2i (2i − 3)!! 2i (2i − 3)! 0.94
(2n − 2i − m)! (2n − 2i − m)! 0.96
(cid:18)n − 1 (cid:19) (cid:18)n − 1(cid:19) 0.84
. i − 1 2i (2i − 3)!! . i − 1 2i (2i − 3)! 0.88
(2n − 2i − m)! (2n − 2i − m)! 0.96
(n − i − m + 1)! (n − i − m + 1)! 0.85
(cid:33) . (cid:33) . 0.82
= rm (−1)n+m =rm (−1)n+m 0.73
22n−m+1(m − 2)! 22n−m+1(m − 2)! 0.72
Moving some terms out and rewriting the double factorial 項の移動と二重因子の書き換え 0.57
(cid:32) · (cid:32) · 0.82
m − 1 2n − m − 1 m − 1 2n − m − 1 0.92
+ m − 1 (2n − m − 1)! + m − 1 (2n − m − 1)! 0.88
= rm (−1)n+m(2n − m − 1)! = rm (−1)n+m(2n − m − 1)! 0.93
22n−m(m − 1)! 22n−m(m − 1)! 0.86
(n − m)! n−m+1(cid:88) (n − m)! n−m+1(cid:88) 0.69
(cid:18)n − 1 n−m+1(cid:88) (cid:18)n − 1 n−m+1(cid:88) 0.68
i − 1 (cid:19) 2i−1 (2i − 3)! i − 1 (cid:19) 2i−1 (2i − 3)! 0.81
(2n − 2i − m)! (2n − 2i − m)! 0.96
(n − m)! 2i−2(i − 2)! (n − m)! 2i−2(i−2)! 0.84
(n − i − m + 1)! (n − i − m + 1)! 0.85
(cid:18)n − 1 (cid:18)n − 1 0.92
(2i − 3)! (2n − 2i − m)! (2i − 3)! (2n − 2i − m)! 0.97
(n − m)! (cid:19) (n − m)! (cid:19) 0.82
(cid:33) . (cid:33) . 0.82
i=2 i − 1 2 i=2 i − 1 2 0.76
(i − 2)! (n − i − m + 1)! (i − 2)! (n − i − m + 1)! 0.85
Evidently we are done if the large parenthetical is equal to 1, which is equivalent to 2n − m − 1 − (m − 1) 大きな括弧が 1 で 2n − m − 1 − (m − 1) と同値であれば、我々は確実に達成される。 0.86
m − 1 2n − m − 1 m − 1 2n − m − 1 0.92
= (2n − m − 1)! = (2n − m − 1)! 0.90
i=2 14 i=2 14 0.72

(2n − m − 2)! (2n − m − 2)! 0.94
= (m − 1) Starting the sum at i = 1, = (m − 1) i = 1 で和を開始する。 0.74
(2n − m − 2)! (2n − m − 2)! 0.94
= (m − 1) (cid:18)n − 1 (cid:19) (2i − 3)! = (m − 1) (cid:18)n − 1 (cid:19) (2i − 3)! 0.87
(2n − 2i − m)! (2n − 2i − m)! 0.96
(n − m − 1)! (n − m − 1)! 0.85
n−m+1(cid:88) (cid:19) (2i − 1)! n−m+1(cid:88) (cid:19) (2i − 1)! 0.72
(2n − 2i − m − 2)! (2n − 2i − m − 2)! 1.00
(n − m − 1)! (n − m − 1)! 0.85
(cid:18)n − 1 n−m(cid:88) (cid:18)n − 1 n−m(cid:88) 0.76
(i − 2)! (n − i − m + 1)! (i − 2)! (n − i − m + 1)! 0.85
i − 1 i=2 . i − 1 i=2 . 0.76
(i − 1)! (n − i − m)! (i − 1)! (n − i − m)! 0.85
i=1 i Now we break the binomial coefﬁcient into factorials and rearrange into new binomial coefﬁcients i=1 私は 二項係数を因子数に分解し 新しい二項係数に再構成します 0.59
Moving m − 1 into the sum and some factorials to the LHS m − 1 を和に、いくつかの因子を lhs に移す 0.73
(2n − m − 2)! (2n − m − 2)! 0.94
= (m − 1) (2n − m − 2)! = (m − 1) (2n − m − 2)! 0.90
= (m − 1) i=1 = (m − 1) i=1 0.72
(n − 1 − i)!(i)! (n − 1 − i)!(i)! 0.85
(i − 1)! (n − i − m)! (i − 1)! (n − i − m)! 0.85
(n − 1)! (2i − 1)! (n − 1)! (2i − 1)! 0.91
(2n − 2i − m − 2)! (2n − 2i − m − 2)! 1.00
(n − m − 1)! (n − m − 1)! 0.85
n−m(cid:88) (cid:18)2i − 1 n−m(cid:88) (cid:18)2i − 1 (cid:19) (cid:18)2n − m − 2 n−m(cid:88) (cid:18)2i − 1 (cid:19)(cid:18)2n − 2i − m − 1 (cid:19)(cid:18) n−m(cid:88) 1 − 2(n − i − m) 2n − 2i − m − 1 (cid:18)2i − 1 (cid:19)(cid:18)2n − 2i − m − 1 (cid:18)2i − 1 n−m−1(cid:88) n-m(cid:88) (cid:18)2i − 1 n-m(cid:88) (cid:18)2i − 1 (cid:19) (cid:18)2n − m − 2 n-m(cid:18)2i − 1 (cid:19)(cid:18)2n − 2i − m − 1 (cid:19)(cid:18)n-m( cid:88) 1 − 2(n − i − m) 2n − 2i − m − 1 (cid:18)2i − 1 (cid:19)(cid:18)2n − 2i − m − 1 (cid:18)2i − m − 1 (cid:88) 0.78
(cid:19)(cid:18)2n − 2i − m − 1 (cid:19) (n − 1)! (cid:19)(cid:18)2n − 2i − m − 1 (cid:19) (n − 1)! 0.87
(n − m − 1)! (n − m − 1)! 0.85
(cid:19) (cid:19)(cid:18)2n − 2i − m − 1 (cid:19) (cid:19)(cid:18)2n − 2i − m − 1 0.80
(cid:19)(cid:18)2n − 2i − m − 2 (cid:19) (cid:19)(cid:18)2n − 2i − m − 2(cid:19) 0.80
(2n − 2i − m − 1) (2n − 2i − m − 1) 0.98
2n − 2i − m − 1 2n − 2i − m − 1 0.94
n − m − 1 n − i − 1 n − m − 1 n − i − 1 0.85
n − i − 1 n − i − 1 n − i − 1 n − i − 1 0.85
m − 1 (cid:19) m − 1 (cid:19) 0.82
(cid:19) i=1 (cid:19) i=1 0.69
i=1 i=1 = = i=1 i=1 = = 0.72
i i i . 私は 私は 私は . 0.61
. Note that the second sum goes to n − m − 1 since the i = n − m term gave zero. . 第二の和は i = n − m 項が 0 であるため n − m − 1 となることに注意。 0.87
We set the sum variable to start at zero sum変数を 0 から始めるように設定します 0.76
n−m−1(cid:88) n−m−1(cid:88) 0.53
i=0 = (cid:18)2i + 1 (cid:18)2n − m − 2 i=0 = (cid:18)2i + 1 (cid:18)2n − m − 2 0.76
i n − m − 1 私は n − m − 1 0.69
i n − i − 1 私は n − i − 1 0.69
(cid:19)(cid:18)2n − m − 2 − (2i + 1) (cid:19)(cid:18)2n − m − 2 − (2i + 1) 0.88
(cid:19) n − i (cid:19) n − i 0.82
− 2 − 2 (cid:19) − 2 − 2 (cid:19) 0.83
= n−m−1(cid:88) = n−m−1(cid:88) 0.69
(cid:18)2n − m − 1 (cid:18)2n − m − 1 0.88
i=0 i Applying Lemma A.1 to both sums yields i=0 私は 両和にLemma A.1を適用する 0.57
i i=1 n−m−2(cid:88) (cid:19) 私は i=1 n−m−2(cid:88)(cid:19) 0.57
i=0 − 2 (cid:18)2i + 1 i=0 − 2 (cid:18)2i+1 0.72
i n−m−2(cid:88) 私は n−m−2(cid:88) 0.53
i=0 n − i − 2 i=0 n − i − 2 0.72
. (cid:19)(cid:18)2n − m − (2i + 1) − 1 (cid:18)2n − m − 2 (cid:19) . (cid:19)(cid:18)2n − m − (2i + 1) − 1 (cid:18)2n − m − 2 (cid:19) 0.85
n − i − 1 (cid:19) n − i − 1 (cid:19) 0.82
. i . n−m(cid:88) . 私は . n−m(cid:88) 0.72
i=1 = Applying Pascal’s identity to the ﬁrst sum and then combining the two into a telescoping sum yields the desired result. i=1 = パスカルのアイデンティティを最初の和に当てはめ、その2つをテレスコープ和に組み合わせると、望ましい結果が得られる。

0.72
We now move to the derivation of the FKT’s expansion. 我々は現在、FKTの拡大の導出に移行している。 0.72
In short, the derivation proceeds by Taylor expanding in a variable which is small for well-separated points, rearranging into a Gegenbauer expansion, and replacing the derivative term with the simpler form via the above lemma. つまり、導出はテイラーがよく分離された点に対して小さい変数に拡張し、ゲゲンバウアー展開に再配置し、上の補題を通して微分項をより単純な形式に置き換えることによって進行する。 0.66
Theorem A.3. If K is analytic except possibly the origin, then for r(cid:48),r within the radius of convergence, A.3。 k が原点を除いて解析的であれば、r(cid:48)r は収束半径内である。 0.67
K(|r(cid:48) − r|) = K(|r(cid:48) − r|) = 0.86
where K(k)(r(cid:48), r) := どこに K(k)(r(cid:48), r) := 0.79
Y h k (r)Y h Y h k (r)Y h 0.85
k (r(cid:48))∗K(k)(r(cid:48), r), k (r(cid:48))∗k(k)(r(cid:48), r) 0.87
j(cid:88) K (m)(r)rm−jT (α) jkm, j(cid:88) K (m)(r)rm−jT (α) jkm, 0.91
∞(cid:88) (cid:88) ∞(cid:88) ∞(cid:88) (cid:88) ∞(cid:88) 0.78
k=0 h∈Hk r(cid:48)j K=0 h.hk r(cid:48)j 0.59
and T (α) radius of convergence is the same as that of 6. そして、T(α)の収束半径は6と同じである。 0.72
jkm are constants which depend only on the dimension and not on the kernel or data. jkmは次元のみに依存し、カーネルやデータに依存しない定数である。 0.75
The j=k m=1 15 j=k m=1。 15 0.55

err 翻訳エラー 0.00

So our current form of the expansion is ですから、この拡張の現在の形は 0.76
j(cid:88) n= j+k j(cid:88) n=j+k 0.69
2 ∞(cid:88) ∞(cid:88) ∞(cid:88) 2 ∞(cid:88) ∞(cid:88) ∞(cid:88) 0.83
j=k k=0 = C (α) j=k K=0 = C (α) 0.70
k (cos γ) k (複数形 ks) 0.58
Ak,(2n−j)C (α) Ak,(2n−j)C(α) 0.98
k (cos γ) k (複数形 ks) 0.58
r(cid:48)2(n−(2n−j)) r2(n−(2n−j)) r(cid:48)2(n−(2n−j)) r2(n−(2n−j)) 0.75
−2 r(cid:48) r −2 r(cid:48) r 0.83
∞(cid:88) j(cid:88) ∞(cid:88) j(cid:88) 0.84
j=k n= j+k 2 j=k n=j+k 2 0.66
Ak,(2n−j) r(cid:48)2(n−(2n−j)) r2(n−(2n−j)) Ak,(2n−j) r(cid:48)2(n−(2n−j)) r2(n−(2n−j)) 0.81
−2 (cid:18) (cid:18) −2 (cid:18)(cid:18) 0.75
(cid:19)(2n−j) 1 (cid:19)(2n−j) 1 (cid:19)(2n−j) 1 (cid:19)(2n−j) 1 0.71
n! ∂n ∂εn ∂n ∂εn N! ∂n ∂εn ∂n ∂εn 0.65
n! √ (cid:0)K(r (cid:0)K(r N! √ (cid:0)K(r (cid:0)K(r) 0.82
1 + ε)(cid:1) 1 + ε)(cid:1) 1 + ε (cid:1) 1 + ε (cid:1) 0.92
√ ε=0 ε=0 . √ ε=0 ε=0 . 0.84
(19) The pieces are now in place for us to arrive at the FKT’s ﬁnal form. (19) 作品は現在、FKTの最終形態に着くための準備が整っている。 0.72
Plugging (14) into (19) yields 14)を(19)収率に差し込む 0.59
r(cid:48) r r(cid:48) r 0.88
(cid:18) (cid:19)(2n−j) 1 (cid:18) (cid:19)(2n−j)1 0.74
Ak,(2n−j) r(cid:48)2(n−(2n−j)) r2(n−(2n−j)) Ak,(2n−j) r(cid:48)2(n−(2n−j)) r2(n−(2n−j)) 0.81
−2 r(cid:48) r −2 r(cid:48) r 0.83
BnmK (m)(r)rm BnmK (m)(r)rm 0.85
n! k=0 ∞(cid:88) N! K=0 ∞(cid:88) 0.71
∞(cid:88) n(cid:88) ∞(cid:88) n(cid:88) 0.84
C (α) k (cos γ) C (α) k (複数形 ks) 0.71
k=0 j=k n= j+k K=0 j=k n=j+k 0.55
m=1 j(cid:88) ∞(cid:88) m=1。 j(cid:88) ∞(cid:88) 0.64
2 = C (α) k (cos γ) 2 = C (α) k (複数形 ks) 0.78
where k=0 T (α) k,j,m := どこに K=0 T(α)k,j,m := 0.68
j(cid:88) ∞(cid:88) j(cid:88) ∞(cid:88) 0.84
r(cid:48)j r(cid:48)j 0.88
j(cid:88) j=k j(cid:88) j=k 0.71
m=1 K (m)(r)rm−jT (α) m=1。 K(m)(r)rm−jT(α) 0.71
k,j,m, n=max ( j+k k、j、m、 n=max(j+k) 0.61
2 ,m) Ak,(2n−j)(−2)(2n−j) 1 n! 2m)。 Ak,(2n−j)(−2)(2n−j) 1 n! 0.68
Bnm. Finally, expanding the Gegenbauer polynomial into hyperspherical harmonics yields Bnm。 最後に、ゲゲンバウアー多項式を超球面調和へ拡張する 0.71
∞(cid:88) (cid:88) ∞(cid:88) (cid:88) 0.81
k=0 h∈Hk = K=0 h.hk = 0.58
∞(cid:88) j(cid:88) ∞(cid:88) j(cid:88) 0.84
j=k m=1 k (r)Y h Y h j=k m=1。 k (r)Y h Y h 0.63
k (r(cid:48))∗ k(r(cid:48))∗ 0.83
r(cid:48)j r(cid:48)j 0.88
K (m)(r)rm−jT (α) K(m)(r)rm−jT(α) 0.97
k,j,m, where T (α) k、j、m、 t (複数形 ts) 0.64
k,j,m = Z (α) k,j,m = Z(α) 0.84
k T (α) k (複数形 ks) 0.53
k,j,m. A.3 Number of terms in FKT k、j、m。 A.3 FKTにおける用語の数 0.68
The “rank” of the low-rank expansion is given by 低ランク拡大の「ランク」は 0.39
where |Hk| is the number of linearly independent hyperspherical harmonics of order k, and (cid:98) P−k is the rank of K(k) start by writing (cid:98) P−k ここで |hk| は順序 k の線型独立超球面調和数の数であり、 (cid:98) p−k は (cid:98) p−k を書き始める k(k) のランクである。 0.72
2 (1k=P mod 2) and addressing the ﬁrst term ﬁrst. 2 (1k=P mod2) であり, 第一項に対処する。 0.64
2 + 1 (cid:1) in Wen & Avery (1985). 2 + 1 (cid:1) in wen & avery (1985)。 0.84
We 2 +1(cid:99) 私たち 2+1(cid:99) 0.67
k=0 k (20) K=0 k (20) 0.74
P(cid:88) + 1(cid:99), p(cid:88) + 1(cid:99) 0.86
2 2 + 1(cid:99) = P−k+1 2 2 + 1(cid:99) = P−k+1 0.78
|Hk|(cid:98) P − k p . Hk| (cid:98) P − k p。 0.79
The former is given by |Hk| =(cid:0)k+d−1 (cid:18)k + d − 3 − P(cid:88) P(cid:88) 前者は |Hk| = (cid:0)k+d−1 (cid:18)k + d − 3 − P(cid:88) P(cid:88) 0.81
(cid:18)(cid:18)k + d − 1 (cid:19) P(cid:88) (cid:19) P − k + 1 (cid:18)k + d − 1 (cid:19) (cid:18)k + d − 1 P(cid:88) (cid:18)(cid:18)k + d − 1 (cid:19) P(cid:88) (cid:19) P − k + 1 (cid:18)k + d − 1 (cid:19) (cid:18)k + d − 1 P(cid:88) 0.87
P(cid:88) k − 2 p(cid:88) k − 2 0.82
− k=0 k=0 k=2 − K=0 K=0 k=2 0.62
= k k 2 k−2 = k k 2 k−2 0.80
(cid:1) −(cid:0)k+d−3 (cid:19)(cid:19) P − k + 1 (cid:19) P − k + 1 (cid:18)k + d − 3 (cid:18)k + d − 1 (cid:19) (cid:1) −(cid:0)k+d−3 (cid:19)(cid:19) P − k + 1 (cid:19) P − k + 1 (cid:18)k + d − 3 (cid:18)k + d − 1 (cid:19) 0.83
k − 2 2 2 (k − 1) k − 2 2 2 (k − 1) 0.85
. k=0 k k=0 . K=0 k K=0 0.69
k = P 1 2 − 1 2 k = P 1 2 − 1 2 0.85
17 Further breaking apart the sum, 17 合計をさらに分解する 0.69

err 翻訳エラー 0.00

d 1 r 1 r2 1 r3 d 1 r 1 r2 1 r3 0.88
1 r e−r e−r re−r e−1/r e−1/r2 1 r e−r e−r re−r e−1/r e−1/r2 0.61
3 11 2 3 4 2 3 11 2 3 4 2 0.85
414 2 5 21 2 3 4 4 2 414 2 5 21 2 3 4 4 2 0.85
624 2 7 32 3 4 5 4 2 624 2 7 32 3 4 5 4 2 0.85
834 2 9 43 4 5 6 4 2 834 2 9 43 4 5 6 4 2 0.85
Table 2: For a variety of different kernels in different dimensions, the value of Rk achievable in (21), independent of P . 表2: 異なる次元の異なる異なるカーネルに対して、(21) における Rk の値は P とは独立である。 0.71
Dashes indicate that Rk was always found to be equal to its upper bound of (cid:98) P +k−2 (cid:99). ダッシュは、Rk が (cid:98) P +k−2 (cid:99) の上界と常に等しいことを示している。 0.70
By automatically ﬁnding these shorter expressions for the radial expansions when possible, we are able to change the (cid:98) P−k+2 (cid:99) term in (20) to a constant. 可能な限り短い半径展開の式を自動的に見つけることで、 (20) において (cid:98) P−k+2 (cid:99) 項を定数に変えることができる。 0.70
The 2-term radial expansion for e−r is given in Table 3. e-r の 2 項の半径展開は表3で与えられる。 0.65
2 2 k = 0 k = 1 k = 2 2 2 k = 0 k = 1 k = 2 0.85
... i = 0 re−r r2e−r 3 r2 + 1 ( 1 ... i = 0 re−r r2e−r 3 r2 + 1 (1) 0.63
3 r3)e−r Fk,i(r) 3 r3)e−r Fk,i(r) 0.79
Gk,i(r(cid:48)) Gk,i(r(cid:48)) 0.98
i = 1 − 1 3 e−r e−r( −1 5 r + −1 5 ) 42 r3 + −1 42 r2 + 1 i = 1 − 1 3 e−r e−r( −1 5 r + −1 5 ) 42 r3 + −1 42 r2 + 1 0.87
7 )e−r ( −1 7 r + −1 7 )e−r ( −1 7 r + −1 0.85
1 + 1 1 + 1 1 + 1 1 + 1 0.85
6 r(cid:48)2 + 1 10 r(cid:48)2 + 1 1 + −1 6 r(cid:48)2 + 1 10 r(cid:48)2 + 1 1 + −1 0.94
i = 0 120 r(cid:48)4 + 1 280 r(cid:48)4 + 1 504 r(cid:48)4 i = 0 120 r(cid:48)4 + 1 280 r(cid:48)4 + 1 504 r(cid:48)4 0.96
5040 r(cid:48)6 15120 r(cid:48)6 5040 r(cid:48)6 15120 r(cid:48)6 0.90
r(cid:48)2 + 1 r(cid:48)2 + 1 r(cid:48)2 + 1 r(cid:48)2 + 1 0.93
i = 1. 10 r(cid:48)4 + 1 14 r(cid:48)4 + 1 r(cid:48)2 + 1 18 r(cid:48)4 i = 1。 10 r(cid:48)4 + 1 14 r(cid:48)4 + 1 r(cid:48)2 + 1 18 r(cid:48)4 0.83
280 r(cid:48)6 504 r(cid:48)6 280 r(cid:48)6 504 r(cid:48)6 0.90
k = 0 k = 1 k = 2 k = 0 k = 1 k = 2 0.85
... Table 3: Note that we are using K(r) as shorthand for K(|r(cid:48) − r|). ... 表3: K(r) を K(|r(cid:48) − r|) の略語として用いていることに注意。 0.68
For K(r) = e−r we have K(k)(r, r(cid:48)) = Fk,1Gk,1 + Fk,2Gk,2. K(r) = e−r に対して、K(k)(r, r(cid:48)) = Fk,1Gk,1 + Fk,2Gk,2 となる。 0.67
2 (cid:99). 2 (cid:99)。 0.83
rk+1 , Gk,1(r(cid:48)) = r(cid:48)k, and Rk = 1. rk+1 , Gk,1(r(cid:48)) = r(cid:48)k, そして Rk = 1。 0.83
For general kernels, we only have r(cid:48)k/rk+1 and so Fk,1(r) = 1 Rk ≤ (cid:98) p−k+2 However, it is possible for us to automatically detect when Fk,i, Gk,i exist so that Rk in (21) is smaller. 一般のカーネルでは、r(cid:48)k/rk+1 しか存在せず、したがって fk,1(r) = 1 rk ≤ (cid:98) p−k+2 である。

0.77
Consider a kernel which satisﬁes the differential equation K(cid:48)(r) = q(r)K(r), where q is a Laurent polynomial. 微分方程式 k(cid:48)(r) = q(r)k(r) を満たす核を考える。

0.78
In this case, the mth derivatives of the kernel will result in products of Laurent polynomials and the kernel itself, and hence the kernel may be pulled completely out of the double sum deﬁning K(k) この場合、カーネルの m 番目の微分はローラン多項式とカーネル自体の積となり、したがって核は k(k) を定義する二重和から完全に引き出される。 0.65
p , yielding a binomial in r(cid:48) and r K(k) p (r(cid:48), r) = K(r) p , r(cid:48) と r k(k) p (r(cid:48), r) = k(r) の二項を与える 0.85
(cid:88) (cid:88) (cid:88) (cid:88) 0.78
r(cid:48)jrmAj,m, r(cid:48)jrmAj,m, 0.96
j m where the Aj,m coefﬁcients are computed based on the T (α) jkm terms in the FKT expansion and the coefﬁcients of the Laurent polynomial q. j M ここで Aj,m 係数は FKT 展開における T (α) jkm 項とローラン多項式 q の係数に基づいて計算される。 0.77
The sums over j, m are ﬁnite and their range depends on the powers of the argument in the Laurent polynomial. j, m 上の和は有限であり、その範囲はローラン多項式の引数のパワーに依存する。 0.66
If the Aj,m are rational, then a concise representation of the form (21) may be found in the following way: (i) insert the coefﬁcients Aj,m into a matrix with rows and columns corresponding to the respective powers of r and r(cid:48) in the binomial, (ii) perform a rank-revealing QR factorization (Businger & Golub, 1965; Chan, 1987) of the matrix but skip the normalization step so that all entries remain rational, and (iii) recover the functions Fk,i from the coefﬁcients in Q and the functions Gk,i from the coefﬁcients in R. Because the entries remained rational, the rank found will exactly be the sought value of Rk. If the Aj,m are rational, then a concise representation of the form (21) may be found in the following way: (i) insert the coefﬁcients Aj,m into a matrix with rows and columns corresponding to the respective powers of r and r(cid:48) in the binomial, (ii) perform a rank-revealing QR factorization (Businger & Golub, 1965; Chan, 1987) of the matrix but skip the normalization step so that all entries remain rational, and (iii) recover the functions Fk,i from the coefﬁcients in Q and the functions Gk,i from the coefﬁcients in R. Because the entries remained rational, the rank found will exactly be the sought value of Rk. 0.92
19 19 0.85

In our implementation, we automatically perform this computation of Rk, Fk,i(r), and Gk,i(r(cid:48)) as a pre-computation when the given kernel satisﬁes K(cid:48)(r) = q(r)K(r) (this is indicated by a user-toggled ﬂag). 我々の実装では、与えられたカーネルがK(cid:48)(r) = q(r)K(r) を満たす場合、プリ計算として、Rk, Fk,i(r) および Gk,i(cid:48) のこの計算を自動で行う(これはユーザトグルフラグで示される)。 0.83
In order to keep entries rational during the factorization, we use a special Rational type within the Julia language rather than standard ﬂoating point operations. 因子化の間にエントリを合理的に保つために、標準的な浮動小数点演算ではなく、Julia言語で特別なRationional型を使用する。 0.61
Although we ﬁnd (cid:99) for the squared exponential, we do see signiﬁcant reductions in the size of the Rk = (cid:98) p−k+2 expansion for other kernels, notably Matérn kernels. 平方指数に対して (cid:99) が見つかるが、Rk = (cid:98) p−k+2 の他の核、特にマテラン核に対する拡張は著しく減少する。 0.69
See Table 2 for some values of Rk for various kernels and dimensions, and Table 3 for the functions Fk,i and Gk,i for the exponential kernel, for which Rk = 2. 様々な核と次元に対するRkの値の表 2 と指数核に対する関数 Fk,i と Gk,i の表 3 を、Rk = 2 である。

0.79
2 B Additional Information for Experiments 2 b 実験のための追加情報 0.83
B.1 Additional implementation details b.1 追加実装の詳細 0.66
The major components of our implementation of the FKT are the tree decomposition and the population of the s2m and m2t matrices. fkt の実装の主要な構成要素は木分解と s2m および m2t 行列の集団である。 0.68
Here we make additional comments on the latter, in which the novelty of the FKT is most manifest. ここでは、FKTの新規性が最も顕著である後者について追加のコメントを行う。 0.70
To compute the s2m and m2t matrices requires (i) computation of hyperspherical harmonics, (ii) computation of the mth derivative of K evaluated at r in 8, and (iii) computation of the Tk,j,m coefﬁcients. s2mおよびm2t行列を計算するには、(i)超球面調和の計算、(ii) r で評価された K の mth 微分の計算、(iii) Tk,j,m 係数の計算が必要である。 0.66
(i) is a complicated expression of cosines, sines, and complex exponentials, which is daunting but doable with standard function calls in Julia, and our implementation aims to do this work in as vectorized a fashion as possible. i) はcosines, sines, complex exponentialsの複雑な表現であり、juliaの標準的な関数呼び出しと相容れないが実行可能である。

0.75
(iii) is a similar task, although we remark that the coefﬁcients do not depend on the data and can be stored once computed. (iii)も同様なタスクであるが、係数はデータに依存しず、一度計算すれば保存できる。 0.65
(ii) is where auto-differentiation is leveraged—assuming the user has written their kernel in a format consumable by TaylorSeries.jl (e g kernel(r) = exp(−r2)), then the tools from that package can compute any order derivative evaluated at any valid point. (ii) ユーザがtaylorseries.jl (e g kernel(r) = exp(−r2)) で消費可能なフォーマットでカーネルを記述した場合、そのパッケージのツールは任意の有効な点で評価された任意の順序微分を計算できる。 0.77
B.2 Further error results for synthetic experiments b.2 合成実験のさらなる誤差結果 0.88
We performed the accuracy measurement experiment detailed in the section of the main text concerning synthetic experiments for many kernels in many dimensions. 我々は,多数のカーネルの合成実験について,本文のセクションで詳述した精度測定実験を行った。 0.78
The results are presented in Table 4. 結果は表4で示されます。 0.81
Notably the error is not signiﬁcantly impacted by dimension (an observed increased accuracy with d may be due to the experimental setup exploring relatively less of the space of function arguments), and shows consistent exponential decrease with the truncation parameter p. We also remark that oscillatory kernels are known to have higher ranks for off-diagonal blocks. 特に、誤差は次元によって大きく影響されない(dで観測された精度の増加は、関数引数の空間の相対的に小さい実験的な設定による可能性がある)。

0.78
In kernel-independent FMMs which use factorizations of subblocks of the matrix, the result of attempting to compress a kernel matrix whose kernel has high-frequency oscillations is that little compression is achieved, accuracy is maintained, and runtime is comparable to a dense operation. 行列のサブブロックの分解を利用したカーネル非依存のFMMでは、カーネルが高周波発振を持つカーネル行列を圧縮しようとする結果、圧縮がほとんど得られず、精度が維持され、実行は密接な操作に匹敵する。 0.63
For the FKT, the result would be consistent compression and runtime, but accuracy lost (since the interactions being compressed are not low-rank, as is assumed for the method). fktの場合、結果は一貫性のある圧縮とランタイムになるが、精度は失われる(圧縮された相互作用はメソッドのように低ランクではない)。 0.74
The user may, acknowledging this behavior of the kernel matrix, increase the truncation parameter so that accuracy is maintained at the cost of runtime, but our implementation of the FKT currently has no hooks to automatically detect the need for this. カーネルマトリックスの動作を認識したユーザは,実行時のコストで精度が維持されるようにトラクションパラメータを増大させることができるが,FKTの実装には,その必要を自動的に検出するためのフックが存在しない。 0.73
A wealth of literature exists for these kernels (c.f. これらのカーネル(c.f.)には豊富な文献が存在する。 0.52
Cheng et al (2006)), and it is likely that an analogous extension of the FKT to incorporate considerations present in the directional FMM would improve performance with highly oscillatory kernels. Cheng et al (2006) と、FKT の方向性 FMM における考察を取り入れた類似の拡張により、高振動性カーネルの性能が向上する可能性が高い。 0.79
B.3 Gaussian Processes A Gaussian Process (GP) is a distribution over functions whose ﬁnite-dimensional marginal distributions are distributed according to a multivariate normal law. b.3 ガウス過程 ガウス過程(英: Gaussian Process, GP)は、有限次元の辺分布が多変量正規法則に従って分布する関数上の分布である。 0.67
That is, for any sample f of a GP, and any ﬁnite set of inputs X, we have f (X) ∼ N (µX, ΣX), for some mean vector µX and covariance matrix ΣX. すなわち、GP の任意のサンプル f と任意の有限個の入力 X に対して、ある平均ベクトル μX と共分散行列 ΣX に対して f ( X) > N (μX, ΣX) が成立する。 0.88
In fact, analogous to the multivariate case, a GP is completely deﬁned by its ﬁrst and second moments: a mean function µ(·) and a covariance kernel κ(·,·), also known as a kernel. 実際、多変量の場合と同様に、gp はその第一モーメントと第二モーメントによって完全に定義される:平均函数 μ(·) と共分散核 κ(·,·) 、あるいは核としても知られる。 0.77
In particular, if f ∼ GP(µ, κ) then for any ﬁnite collection of inputs X, 特に、f が gp(μ, κ) であれば、任意の入力の有限集合 x, 0.74
(22) where κ(X, X) is the matrix whose (i, j)nth entry is κ(Xi, Xj). (22) ここで κ(X, X) は (i, j)n 番目のエントリーが κ(Xi, Xj) である行列である。 0.89
Fortunately, the posterior mean µp and posterior covariance κp of a GP conditioned on observations with normally-distributed noise 幸いなことに、正規分布雑音による観測に基づくGPの後方平均μpと後方共分散κp 0.72
f (X) ∼ N (µ(X), κ(X, X)), f(x) は n(μ(x), κ(x, x)) である。 0.74
20 20 0.85

Kernel Dim. p = 3 p = 6 p = 9 p = 12 p = 15 p = 18 Kernel Dim. カーネルdim。 p = 3 p = 6 p = 9 p = 12 p = 15 p = 18 Kernel Dim。 0.63
p = 3 p = 6 p = 9 p = 12 p = 15 p = 18 p = 3 p = 6 p = 9 p = 12 p = 15 p = 18 0.85
K(r) = e−r K(r) = e−r 0.92
Maximum Absolute Error 3 1.03e-2 7.32e-4 5.48e-5 4.62e-6 4.25e-7 4.14e-8 最大絶対誤差 3 1.03e-2 7.32e-4 5.48e-5 4.62e-6 4.25e-7 4.14e-8 0.48
3 1.41e-2 2.17e-3 1.58e-4 1.71e-5 1.62e-6 1.39e-7 3 1.41e-2 2.17e-3 1.58e-4 1.71e-5 1.62e-6 1.39e-7 0.25
9 6 1.02e-2 1.02e-2 6.52e-4 6.78e-4 5.40e-5 5.47e-5 4.59e-6 4.57e-6 4.20e-7 4.24e-7 4.14e-8 4.04e-8 K(r) = (1 + r2)−1 6 1.41e-2 1.61e-3 1.42e-4 1.54e-5 1.27e-6 1.02e-7 9 6 1.02e-2 1.02e-2 6.52e-4 6.78e-4 5.40e-5 5.47e-5 4.59e-6 4.57e-6 4.20e-7 4.24e-7 4.14e-8 4.04e-8 K(r) = (1 + r2)−1 6 1.41e-2 1.61e-3 1.42e-4 1.54e-5 1.27e-6 1.02e-7 0.31
9 1.41e-2 1.11e-3 1.39e-4 1.19e-5 9.35e-7 7.69e-8 9 1.41e-2 1.11e-3 1.39e-4 1.19e-5 9.35e-7 7.69e-8 0.25
12 1.02e-2 6.56e-4 5.02e-5 4.31e-6 3.98e-7 4.04e-8 12 1.02e-2 6.56e-4 5.02e-5 4.31e-6 3.98e-7 4.04e-8 0.25
12 1.41e-2 1.11e-3 9.51e-5 8.29e-6 9.18e-7 6.40e-8 12 1.41e-2 1.11e-3 9.51e-5 8.29e-6 9.18e-7 6.40e-8 0.25
3 5.44e-2 7.60e-3 7.68e-4 6.03e-5 9.92e-6 1.70e-6 3 5.44e-2 7.60e-3 7.68e-4 6.03e-5 9.92e-6 1.70e-6 0.25
3 4.86e-2 9.42e-3 9.32e-4 4.80e-5 2.29e-6 9.88e-8 3 4.86e-2 9.42e-3 9.32e-4 4.80e-5 2.29e-6 9.88e-8 0.25
K(r) = cos r/r 6 3.07e-2 2.74e-3 3.65e-4 3.23e-5 3.48e-6 5.23e-7 K(r) = cos r/r 6 3.07e-2 2.74e-3 3.65e-4 3.23e-5 3.48e-6 5.23e-7 0.38
9 3.07e-2 2.01e-3 2.34e-4 3.06e-5 3.05e-6 3.12e-7 9 3.07e-2 2.01e-3 2.34e-4 3.06e-5 3.05e-6 3.12e-7 0.25
K(r) = e−r2 K(r) = e−r2 0.82
6 4.27e-2 7.85e-3 5.45e-4 4.10e-5 2.29e-6 9.88e-8 6 4.27e-2 7.85e-3 5.45e-4 4.10e-5 2.29e-6 9.88e-8 0.25
9 2.95e-2 4.91e-3 5.40e-4 4.10e-5 1.96e-6 6.39e-8 9 2.95e-2 4.91e-3 5.40e-4 4.10e-5 1.96e-6 6.39e-8 0.25
12 3.06e-2 2.00e-3 1.93e-4 2.01e-5 2.59e-6 2.82e-7 12 3.06e-2 2.00e-3 1.93e-4 2.01e-5 2.59e-6 2.82e-7 0.25
12 2.95e-2 4.86e-3 3.87e-4 2.64e-5 1.51e-6 4.07e-8 12 2.95e-2 4.86e-3 3.87e-4 2.64e-5 1.51e-6 4.07e-8 0.25
Table 4: Experimentally observed errors which are calculated for the p = 4 FKT approximation by taking the maximum absolute error of the truncated expansion for 1000 randomly selected pairs of points r(cid:48), r satisfying |r(cid:48)| = 1,|r| = 2. 表4: ランダムに選択された1000個の点 r(cid:48), r が |r(cid:48)| = 1,|r| = 2 であるような点 truncated 展開の最大絶対誤差を取ることにより、p = 4 FKT 近似に対して計算される誤差を実験的に観測する。

0.88
have closed forms and only require linear algebraic operations: µp(X∗) = µ(X∗) + κ(X∗, X)Σ−1 閉形式を持ち、線型代数演算のみを必要とする: μp(X∗) = μ(X∗) + κ(X∗, X)Σ−1 0.86
X (y − µ(X)), X κ(X, X(cid:48) ∗), X (y − μ(X)), X κ(X, X(cid:48) ∗) 0.77
(23) κp(X∗, X(cid:48) (23) κp(X∗, X(cid:48) 0.87
∗) = κ(X∗, X(cid:48) ∗) = κ(X∗, X(cid:48) 0.92
∗) − κ(X∗, X)Σ−1 ∗) − κ(X∗, X)Σ−1 0.93
where, ΣX = k(X, X) + σ2 yI and σy is the standard error of the target y. ここで、σx = k(x, x) + σ2 yi と σy は対象 y の標準誤差である。 0.85
We use the ﬁrst formula to calculate the predictive mean of a GP for the oceanographic data in the main text using FKT. FKTを用いて本文の海洋データに対するGPの予測平均を計算する。

0.79
For more background on Gaussian processes, see (Rasmussen & Williams, 2005). ガウス過程のさらなる背景についてはRasmussen & Williams, 2005を参照。 0.66
C Existing Codes, GPU acceleration, and GP speciﬁc improvements cの既存のコード、gpuアクセラレーション、gp特有の改善 0.72
Deisenroth & Ng (2015) introduced the robust Bayesian Committee Machine (rBCM) which trains local GP "experts" on subsets of the data and combines their predictions. Deisenroth & Ng (2015) はロバストなベイズ委員会機械 (rBCM) を導入し、データのサブセット上でローカルGPの「専門家」を訓練し、それらの予測を組み合わせた。 0.66
All computations of rBCM can be carried out in a distributed fashion, but no constituent model is trained on the entire data. rBCMの計算はすべて分散方式で行うことができるが、データ全体に対して構成モデルを訓練することはない。 0.84
De G. Matthews et al (2017) introduced GPﬂow, a GP library based on accelerating variational inference procedures with GPUs via the TensorFlow framework. De G. Matthews氏(2017)は、TensorFlowフレームワークを介してGPUによる変分推論手順の高速化に基づくGPライブラリであるGPflowを発表した。 0.66
GPyTorch is also a GPU-accelerated library, but is based on PyTorch and instead of variational inference, expresses all GP inference equations via MVMs (Gardner et al , 2018), relying on stochastic estimators to compute log-determinant and trace terms (Dong et al , 2017). gpytorchはgpuアクセラレーションライブラリでもあるが、pytorchをベースとしており、変分推論ではなく、mvm(gardner et al , 2018)を介して全てのgp推論方程式を表現している(dong et al , 2017)。 0.52
21 21 0.85
ページの最初に戻る