Blog

オープンソースライブラリbreezeを導入したときちょっと困ったこと


こんにちは、AMoAdの清水です。AMoAdでは広告配信ネットワークを提供しており、その配信システムを最適化するために広告毎のCTR(click率), CPM(1000回表示あたりの課金額)やimpression数(広告表示回数:imp)など様々な予測を行っています。
予測バッチ他、多くのバッチをAMoAdではScalaで実装しています。
なぜScalaを採用しているのか、それは

  • 元々のシステムのコードはJavaで書かれていたため資産を引き継ぎやすい
  • Javaよりコードが簡潔に書くことができ、可読性/保守性が高くなる
  • Scala大好き

という理由です^^

今日は予測バッチにScalaで行列計算ができるオープンソースライブラリ「scalanlp/breeze」を導入してみてちょっと困った話を紹介したいと思います!

予測モデルについてざっくりと

 

まず、一定期間のデータを元に重回帰分析を用いて予測モデルを作りますが
例えばZの値を予測したい場合、Zに相関のあるA, B, C, D,… といった値とベクトルβを掛けて計算します。

z
Z = impとして予測する場合、A, B, C, D,…にはimpに相関関係のあると思われる指標を入れるというイメージです。
相関しそうなものなんてCPMとかCTRとか色々ありますがそこは工夫次第…。

nは当日をn = 0, 前日をn = 1のように表した値です。
ここまでは特別なことではありませんね。
秘伝のタレβをどれだけ上手に作るかが予測精度に大きく関係してきます。
予測モデルの話をしたいわけではないのでこの辺はさっと飛ばします。というかできません笑

ではβを求めます。

beta
X:過去のimpやCPMやCTRやイベント変数等の行列
Y:impやCPMのベクトル
これをバッチ化して計算するのは非常に大変です。
まずXの行列のデータを何で持つか、二次元配列?List?
転置と逆行列に相当する関数を自分で実装するのは非常にめんどくさい上にバグの保証はどうするのかと…?

そんなときに便利なのが冒頭でも説明したScalaで行列が書けてしまうオープンソースライブラリ、ScalaNLPの「breeze」です!

基本的な使い方はgithubのドキュメントとこちらのブログで勉強しました。(ブログ主様にリンク許可は頂きました)

ScalaでRやMatlabみたいに行列の操作をおこなう

 

 

ではbreezeで実装していきましょう

 breezeのバージョンはv0.9を使用

式はもうあるのであとは実装していくだけです。

XYにDBから取ってきた値を詰めていざ計算してみます^ω^

(めっちゃ端折ってますが笑)

 

 

結果:MatrixSingularException

あれ??

原因を考えると、日によって行列Xに縦に0が並ぶことがある -> 1行全部0は逆行列の定義的に計算できない!
はい。高校のときに習ったやつを思い出します。

 

2 × 2 の正則行列で逆行列の存在条件は「 ad-bc ≠ 0 」でした。

4 × 4 でも10 × 10でも縦に0が並んだら存在条件を満たさなくなってしまいます。
よってエラるのは納得です^ω^

そうゆうわけで疑似逆行列を使いたいところですが幸いなことにbreezeにはムーア・ペンローズの疑似逆行列関数も実装されていました。
pinvってやつです。

では早速…

 

結果:MatrixSingularException

あ?(^ω^#)

色々試してダメなので簡単にpinvの検証をすることにします。

 

結果は同じく MatrixSingularException

これが既にだめですね。

一旦、本来期待する値をRの疑似逆行列関数ginvで出してみましょう

 

これですよこれ。

なぜRなら計算できるのにbreezeだと計算できないのか?
それぞれの実装を見てみました。

R(3.1.0)の実装 (関数実装のコンソール出力より)

 

breezeの実装 (doc略)
math/src/main/scala/breeze/linalg/functions/inv.scala: 54

 

(X.t * X) \ X.t
あれ、なんだこれ?

公式ドキュメントに
Breeze is a generic, clean and powerful Scala numerical processing library patterned after NumPy, Matlab and R and licensed under Apache Public License 2.0.
て書いてあったのでてっきりbreezeRNumPyの機能を踏襲して作ってあるのかと思い込んでいました!
仮にも一部では有名なOSSでありプロダクションコードで実用されている例もいくつもあったので。。

これは僕のような一般人にはわからない思想の違いがあるのかと思い、breezeのメインコントリビューターのDavidさんに聞いてみたところ、
頂いた回答は本来は特異値分解(SVD)を使って実装しなければならない、修正する必要がある、との事でした。
つまりぶっちゃけpinvはほぼ未実装です。
またpinvだけでなく、breeze自体結構バグや未実装機能が多く存在するので使用するときは注意が必要です。

そうですよね、オープンソースってそうゆうことですよね…
そもそもまだバージョン1.0に達してませんし。

また機会があればbreezeで便利な機能やバグにあたるので注意すべきところを紹介したいと思います。(需要ないか…)

 

 

ということで詰みました

 

このままでは行列計算が使えません!
しかしbreezeをやめるのはもっと時間が掛かります。

よって一番手っ取り早い方法としてRginvを自分で実装してしまえばいいわけです^ω^
ginvの実装はわかっているので簡単ですね!中学生でも書けちゃいますね!!

* 実装してみた結果

 

こんなことに/(^o^)\
なんでこんなに内部関数作ってんだよと罵ってください。

Rにはbreezeにない機能があり

という行列と

というベクトルから

という行列を生成できる関数が標準で備わっていたり、

ベクトル×行列の計算はRではできるけどbreezeではできない等の理由から、補助関数を作る必要がありました。
残念ながら関数multipleVectorの中の実装が良くないため、この自家製ginvは正則行列以外には対応しておりません。
とりあえず今回は正則行列だけ対応できれば問題ありませんでした。
今後改良する機会が来るだろうか…
というかもうちょっと汎用的に実装してbreezeにプルリクエスト送れって話ですね笑

 

まとめ

 

ScalaNLPbreezeの一機能を紹介しました。
breezeは行列計算ライブラリの中でもかなり直感的でわかりやすい仕様になっていて、数学が得意でない人も気軽に使えるライブラリになっています。
何かのデータをバッチで計算するときにbreezeの行列を使うことで計算過程のわかりやすいコードが書け、後から見た人にやさしい保守性の高い実装ができるかもしれません。
しかしまだまだ発展途上のライブラリであるため、今回紹介したpinvのように簡易実装になっている機能やバグがいくつかありますので、各機能を使う前に十分に検証してみたほうがいいかと思います^ω^

それでは良いお年を。

Author

アバター
shimizu

関連記事