x1, x2, ..., xN を独立かつ同一な分布に従う標本としたときの予測モデル、
密度推定」、「ミーンシフト」、「カーネル回帰」などが挙げられますが、このモデルは多項式のNが標本数と同じになるため、予測回数をMとするとき、その計算量は非常に高価で、O(MN)となります。
この問題に対して高速多重極法を起源とする高速ガウス変換では、エルミート展開を用いてガウシアンの近似式を作成することで、上式の多項式のNを誤差率に応じて決定される小さな非負整数Kに書き換えられ、その計算量はO(MK)となります。
この高速ガウス変換を改良したIFGTがありますが、
今回はオリジナルの高速ガウス変換を使ったカーネル密度推定のCライブラリを開発し、githubに上げました。
http://github.com/y-mitsui/fastKDE
また、32bit Linux環境ではSSE2で最適化されたアセンブラコードが利用できます。
詳細はREADME.mdをご覧ください。
また、前述のとおり高速ガウス変換には Kに応じた誤差が伴いますので、厳密な計算が必要な場面で利用する際には注意が必要です。
■実行結果
1000000 個の標準正規乱数からなる標本、予測回数を5000回 とし、Kを10と設定した場合の
1次元カーネル密度推定のCPU時間は最適化されていない場合の444秒に対して、
高速ガウス変換を使用した場合は0.6秒となり、大幅に速度が向上していることがわかります。
一方、Kの値が小さすぎた為、誤差が大きくなっています。
direct time:444.13400sec optimized time:0.60800sec
directValue[00000]:0.221897 optimizedValue[00000]:0.242221
directValue[00250]:0.233130 optimizedValue[00250]:0.252617
directValue[00500]:0.243662 optimizedValue[00500]:0.262466
directValue[00750]:0.253349 optimizedValue[00750]:0.271657
directValue[01000]:0.262056 optimizedValue[01000]:0.280076
directValue[01250]:0.269658 optimizedValue[01250]:0.287611
directValue[01500]:0.276041 optimizedValue[01500]:0.294152
directValue[01750]:0.281110 optimizedValue[01750]:0.299593
directValue[02000]:0.284789 optimizedValue[02000]:0.303839
directValue[02250]:0.287019 optimizedValue[02250]:0.306803
directValue[02500]:0.287767 optimizedValue[02500]:0.308415
directValue[02750]:0.287020 optimizedValue[02750]:0.308619
directValue[03000]:0.284790 optimizedValue[03000]:0.307384
directValue[03250]:0.281112 optimizedValue[03250]:0.304698
directValue[03500]:0.276040 optimizedValue[03500]:0.300573
directValue[03750]:0.269653 optimizedValue[03750]:0.295048
directValue[04000]:0.262046 optimizedValue[04000]:0.288185
directValue[04250]:0.253331 optimizedValue[04250]:0.280067
directValue[04500]:0.243634 optimizedValue[04500]:0.270803
directValue[04750]:0.233090 optimizedValue[04750]:0.260516
CPU: Core i5(Nehalem) MEM:4GB OS:Windows 7 COMPILER:mingw 4.62
