読者です 読者をやめる 読者になる 読者になる

Multiplexed Reservoir Sampling

Xixuan Feng Arun Kumar Benjamin Recht Christopher Ré: "Towards a Unified Architecture for in-RDBMS Analytics", In. Proc, SIGMOD, 2012.

だいぶ昔に読んだ論文だけどIn-database AnalyticsのBismarckの論文にMultiplexed Reservoir Samplingというのがあって、それを使うと収束が早いというのが?に思ったので書く。

まず、Reservoir samplingについての前提知識を必要とするのでWikipediaのエントリを参照のこと。 次のようなアルゴリズムで最後に残ったsamplesはランダムなものになっているサンプリング手法。

Multiplexed Reservoir Samplingの概念図は次のとおり。

  • Reservoir samplingではBサイズのReservoirバッファを用意して、I/Oワーカをone passだけ回す。ここは通常のReservoir Samplingと同じ。ただし、Reservoirバッファの置換時に捨てたoldも確率的勾配降下法の勾配の計算に用いる。

  • one pass回し終わったらMemoryワーカのバッファとスワップする。

  • Memoryワーカは自分のバッファはランダムなので順に出力。I/Oワーカと並行して勾配の計算を行う。

  • I/Oワーカは次のパスではMemoryワーカのバッファをReservoirバッファとして用いて、学習を行う。

f:id:myui:20140108181851j:plain

I/Oワーカでone-passだけ処理し(このときに学習に利用されるのはReservoirバッファからdropしたエントリ)、2回目以降のiterationではI/Oワーカとmemoryワーカが同時に勾配を更新する*1

Reservoir sampling使ってsubsampling(データの一部分だけ使う?)する場合やサンプリングしない*2場合より早く収束するらしい。

1回目のパスでReservoirバッファから落ちるエントリはランダムとはならず入力順に応じたものになる(1,2,...,Nと入力していけばわかる)のでちょっと疑問。

Bismarckの実装も公開されているので確認してみたかったが、公開されているコードではこのテクニックは残念ながら使われていなかった。

*1:I/OワーカとMemoryワーカを並行させて走らせると、Memoryワーカの方のエントリの頻度が大きくなってしまうと思うがセマフォを利用するかな。

*2:ただし、実験では入力順のままで順序を順不同にしていない