確率的カウントアルゴリズム Morris Counting の話

確率的アルゴリズム

ちゃお。舞い降り......†

ハイパフォーマンスPython

ハイパフォーマンスPython

11/20にオライリーのHigh Performance Pythonの日本語版が出るようです。 著者のMicha Gorelickさんの紹介文がエキセントリックなことで一部で話題沸騰中な本です。(未来から来たマッドサイエンティストらしい...†)

私は先に出た英語版を読んでMorris Countingという推定カウントアルゴリズムが面白いと思ったんですけど、検索してみたら日本語だとあまりヒットしなかったので、今回はそのお話をしたいと思います。トニーモリス (有名人) の話じゃないよ〜。

さてMorris Counting [Morris, 1978] はベル研究所のRobbert Morrisが1970年代後半に発表したアルゴリズムで、ざっくり言うと指数だけを保持すれば少ないbitで推定値を表現できるんじゃね？っていう確率的なカウンターです。

たとえば、65536 という数は 216 を計算すれば求められるから、常に2の累乗であるということが決まっていれば、指数が16であるということだけ覚えてればいいのです。こうすることで、通常だったら65536を表現するには16bitいるところを、指数が 16=24 ということだけを覚えておけばいい――つまりたったの 4bitで表現できるっていう考え。

カウントはどんな流れになるかというと、

  1. まず指数部が0の状態でスタート。このときカウント命令がきたら、1/20 = 1 となるので必ず指数部が加算されます。
  2. 次は 1/21 = 0.5 なので1/2の確率で指数部が加算されます。
  3. もし加算されてたら 1/22 = 0.25 なので1/4の確率で指数部が加算されます。されてなかったら1/2の確率で指数部が加算...

みたいな感じです。

指数 推定カウント値 指数部を加算する確率
0 1 1
1 2 1/2
2 4 1/4
3 8 1/8
4 16 1/16

指数が大きくなるごとに次の推定カウント値との間隔が大きくなるので、 それに応じて指数部分が加算される確率を低くしていくってところがなるほどって面白いです。 推定カウント値が4から8に行くには1/4の確率なので、4回回せばだいたい8にいくみたいな。

さらに少ないbitで大きな数を表現したいときは、底を2ではなくもっと大きい数にします。

このインクリメントする確率を式で表現すると { \displaystyle \Pr(C) = b^{-C} } となります。Cは指数、bは底 (さっきの例だと2) をあらわします。

カウントした推定値 {\tilde{\gamma}} は { \tilde{\gamma} = \frac{b^{C} - 1}{b - 1} } によって求められます。

Pythonでコード書いてみました。

でも乱数を使っているので当然、必ずしもきれいにカウントできるわけじゃなくて、指数が増えるごとに誤差が大きくなります。 なので、正確に数を知りたいというより「これはなんかめちゃくちゃでかい」「これはかなり小さい」みたいな大雑把な傾向を掴む用途で使えそうです。 当時は、画像認識や音声認識のような大量のデータを扱うタスクをあんまりメモリが使えない環境で行うときに使われたそうです。

最近だと、機械学習のメモリ使用量を減らすために浮動小数点の精度を特徴量ごとに調節する目的で特徴量それぞれの出現頻度をカウントするのに使われています [Golovin et al, 2013]

というわけで、モリスカウンティングのお話でした。他にもハイパフォーマンスPythonにはmarisa-trieというちょっとマニアックなアルゴリズムのライブラリも紹介されています。修士のころ研究の実装でmarisa-trieにだいぶお世話になったのでうれしいです＾＾

参考