Multiplexed Reservoir Sampling
だいぶ昔に読んだ論文だけど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バッファとして用いて、学習を行う。
I/Oワーカでone-passだけ処理し（このときに学習に利用されるのはReservoirバッファからdropしたエントリ）、2回目以降のiterationではI/Oワーカとmemoryワーカが同時に勾配を更新する*1。
Reservoir sampling使ってsubsampling（データの一部分だけ使う?)する場合やサンプリングしない*2場合より早く収束するらしい。
1回目のパスでReservoirバッファから落ちるエントリはランダムとはならず入力順に応じたものになる（1,2,...,Nと入力していけばわかる）のでちょっと疑問。
Bismarckの実装も公開されているので確認してみたかったが、公開されているコードではこのテクニックは残念ながら使われていなかった。
