概要
ガウス過程回帰(GPR)を計算する時の、ボトルネックとなる箇所や、
高速化する際の計算の工夫手法に対してのまとめ、
よくわかっていないところなどをまとめてみます。
主題とするのは、
- Constant-Time Predictive Distributions for Gaussian Processes
- Product Kernel Interpolation for Scalable Gaussian Processes
こちらの論文です。
忙しい人のためのまとめ
Constant-Time Predictive Distributions for Gaussian Processes
の論文では、以下の様な論点があるよ
-
GPR を計算するには、カーネルによる共分散行列、共分散行列の逆行列の計算が必要だよ
-
逆行列の計算には、主に２つが使われるよ
- Cholesky Decomposition（オーダーO(n^3))
- Linear conjugate gradients による近似ループによる解放(O(k*n^2), kはループの回数）
-
Lanczos アルゴリズムは、大きな対称行列をLow Rank 行列の積に変換するアルゴリズムだよ
-
カーネルを用いた共分散行列は、
Structured kernel interpolation（SKI)により近似できるよ -
LancorsアルゴリズムとSKIの組み合わせにより、GPRは定数時間で（nによらず）計算できるよ
ガウス過程回帰とは
ガウス過程回帰自体の解説については他のいろいろな素晴らしい記事に委ねます。
腑に落ちた表現は、
https://gochikika.ntt.com/Modeling/gp_regression.html
こちらの
ガウス過程回帰モデルはガウス過程というランダムな関数の確率分布を利用した回帰モデルで、回帰曲面の関数形を具体的に指定することなしにデータの情報を利用して回帰問題の推論を行うことができます。
という表現です。
つまり、回帰に必要な関数を具体的に解くのではなく、
学習に使用したデータをもとに、回帰の期待値と分散について確率的に導出できるというアルゴリズムです。
学習データにどの程度予測したい入力データが類似しているかわかれば、その類似度によってある程度
対応する予測データの重ね合わせで結果を導出できるとは直感的にも考えられますよね。
その類似度を計算するときに必要となるのがカーネル関数であり、共分散行列なわけです。
他にも
こちらや
こちらをぜひ参考にしてみてください。
ガウス過程回帰を構成するのに必要な演算
平均と分散は、上の式の様に共分散行列と、
行列の逆行列を計算することで取得可能なことがわかります。
Kernel Interpolation について
必要な共分散行列のエントリは、学習データの数をnとすると(n, n) ですが、
このKernel Interpolation を用いることで小さくすることができます。
ここに書かれている様に、xという点をm点のinducing points を使って補間します。
言葉で説明すれば、xを補間ベクトルで置き換え、
共分散行列も全てのデータ点に対するものではなく、inducing points の共分散行列に置き換えています。
そうすることでカーネルの共分散行列のオーダーはO(n)にすることができます。
Lanczos アルゴリズムについて
ここで説明されている様に、Lanczosアルゴリズムを利用することで、
Q,Tという行列の積でAを表しています。
Lanczosアルゴリズムは、対称行列を低ランク行列の積で表す手法です。
Lanczosアルゴリズムのイテレーション回数をk回とすると、
nk, kk の行列積に落とすことができます。
わかりやすい図があったので載せておきます。
Product Kernel Interpolation for Scalable Gaussian Processesより
本論文の高速化のまとめ
上で言及した、
- Kernel Interpolation
- Lanczos アルゴリズム
の二つをどちらも使うことにより、
まずカーネルの共分散行列を小さくし、
その上でさらにLanczos アルゴリズムを利用して推論に必要な行列を低ランクに近似します。
そうすることで高速化を図っています。
計算オーダーについて
まとめ
今回は、ガウス過程回帰を高速に演算する工夫について言及している論文を可能な範囲で解説してみました。
自分的にはまだ疑問点がいくつかあります。
- どうやってカーネル共分散行列を小さくするための補間ベクトルを計算するのか？補間ポイントをどうやって選ぶ（作る）のか？
- Lanczosアルゴリズムのループの実装は具体的にどうするのか？（書いてみないと感覚がわからない）
- CholeskeyやLinear conjugate gradients メソッドについての実装は？
以上についても解決できる様にもう少し追ってみようと思います。
今回はこの辺で。