FXボーグ | テクニカル実験室

テクニカル分析を使った自動売買プログラムの開発に挑戦!

スポンサーリンク

SSAの特異値分解をArmadilloで高速化。

前回の「SSA Slope インジケーター」の速度が気になっていたので計測してみたところ、やはり特異値分解がボトルネックになっていました。

現在のプログラムはOpenCV2を使用しているのですが、Eigen3とArmadilloでも試してみました。結果としてはArmadilloに軍配が上がりました。

※とりあえず目の前のプログラムが高速化されればよいので、ライブラリの優劣をつけたり厳密なベンチマークを提示する意図はありません。

密行列でSVDの高速化

SSAで扱う行列は価格データをしきつめた行列なので、密行列を高速に特異値分解するアルゴリズムを探していたのですが、残念ながらあまり見つかりませんでした。

そんな中で、今回は制約があって試さなかったのですが「I-SVD」などは期待できそうです。

また、こちらの記事にあるMatrix sketchというアイデアは機会があれば使ってみたいと思います。

Matrix sketchとは簡単に言うと、元の大きなNxM行列Aを、はるかに小さなℓxM行列B(N >> ℓ)で近似するものです。

https://research.preferred.jp/2013/08/sketch/ より引用)

特異値分解のライブラリ集

決定的な密行列におけるSVDの高速化アルゴリズムが見つからなかったので、とりあえず、以下のリンク集を参考に他のライブラリを試すことにしました。

ということでEigenとArmadilloをチョイス。

Eigenはヘッダファイルだけで作られているので、インクルードディレクトリに設定するだけで使えます。逆にArmadilloはOpenBlasもインストールしないといけないのでちょっと面倒そうです。(Installation Guide · xianyi/OpenBLAS Wiki )

本家にはMinGWでmakeする等いろいろ書かれているのですが、実はNuGet からビルド済みライブラリが提供されているのでこちらを使うと一瞬で終わります。

f:id:fxborg:20171014232912p:plain

それぞれのSVDコード

まずは既存のOpenCV2でのコードです。OpenCVの行列は行優先なので配列内のデータを横方向にしき詰めて行くことが出来ます。

f:id:fxborg:20171014233838p:plain

こちらはEigen3のコードです。Eigenの行列は基本的には列優先ですが、RowMagerを指定すると行優先に変えることが出来ます。

f:id:fxborg:20171014234318p:plain

こちらがArmadilloのコードです。Armadilloの行列は列優先なのでデータを流し込むのに工夫が必要です。

f:id:fxborg:20171014233720p:plain

測定結果

SSAのパラメータは以下の設定で10回連続で実行し、SVDだけにかかった時間とSSA全体にかかった時間を測定しました。

  • ・N・・・・・時系列データの長さ (1000)
  • ・L・・・・・キャタピラーのウインドウ長(200)
  • ・ω0・・・・トレンド成分判定用のしきい値(0.01)
  • ・max_ET・・成分数の上限(32)

▼OpenCV v2.4.13.2 の結果

f:id:fxborg:20171015000534p:plain

▼Eigen v3.3.4 の結果

f:id:fxborg:20171015000956p:plain

▼Armadillo v8.200.0 の結果

f:id:fxborg:20171015001304p:plain

最後に

3つのライブラリでSVDの時間を計ったところArmadillo が期待以上の結果でした。条件等を変えればまた違った結果になるかもしれませんが、とりあえずはArmadilloで行こうと思います。

こちらからどうぞ

ssa.zip