ハリ・セルダンになりたくて

便利なエントリーへのリンク
矢野の講義サイトへのリンク集

2007-08-26

[][] 比較的高速な復元抽出アルゴリズム

現代の統計学では非復元抽出と復元抽出の高速処理が非常に重要です。例えば昨日のエントリーのbootstrap法などは現代統計学の最重要手法の一つですが、復元抽出が大きな役割を果たしますし、矢野が専門としているモンテカルロフィルター(粒子フィルター)でも復元抽出が必須です。bootstrapでもモンテカルロフィルター(粒子フィルター)でも復元抽出の実行速度は速ければ速い方がよいです(一般に実行回数が非常に大きくなるため)。

復元抽出ならばWalker's alias methodが(矢野の知る範囲内では)かなり速いと思います。

どの程度速くなるかは場合によると思いますが、矢野が作っているモンテカルロフィルター(粒子フィルター)のプログラムでは(linear search methodからWalker's alias methodに入れ替えただけで)約30秒ほどかかる処理が約15秒で終わるようになりました(1万個の重み付きデータサンプルからで1万回復元抽出するという作業を100回繰り返す)。

これはGNU Rのバージョン2.2.0でWalker's alias methodが採用された時に経験したことで、その採用までの経緯が以下のメーリングリストのアーカイブにあります。プログラム例などへのリンクもありますので、「復元抽出を出来るかぎり高速実行したい」という人がおられたら参考になると思います。

R devel archive: Re: [Rd] efficiency of sample() with prob.
http://tolstoy.newcastle.edu.au/R/devel/05/06/1403.html

[参考]
このエントリーは以下のエントリーを見て思い出したため、誰かの役に立つのではないかと思って書いてみました。

高速に非復元抽出をする方法はないだろうか?(アルゴリズムマニア2.0)
http://d.hatena.ne.jp/higotakayuki2/20070823/p1

残念ながらhigotakayuki2さんが必要としておられる非復元抽出の方は(現時点ではあまり使っていないので)分からないのであまり参考にならなくて大変に申し訳ないのですが・・・