アイランドアルゴリズムは、隠れマルコフモデル、あるいはその一般化である動的ベイジアンネットワークにおいて推論を行うアルゴリズムです。観測ノードを条件として、観測されていないノードごとに 周辺分布を計算します。
アイランドアルゴリズムは、ビリーフプロパゲーションの改良版です。メモリ使用量は少なくなりますが、実行時間は長くなります。ビリーフプロパゲーションはO(n)の時間とO(n)のメモリを必要としますが、アイランドアルゴリズムはO(n log n)の時間とO(log n)のメモリを必要とします。プロセッサ数が無制限のコンピュータでは、メモリ使用量はO(log n)のまま、合計実行時間をO(n)に短縮できます。[ 1 ]
アルゴリズム
簡潔にするために、隠れマルコフモデル上でアルゴリズムを説明します。ジャンクションツリーを用いることで、動的ベイジアンネットワークにも容易に一般化できます。
ビリーフプロパゲーションでは、最初のノードから2番目のノードへメッセージを送信し、このメッセージを用いて2番目のノードから3番目のノードへのメッセージを計算し、これを最後のノード（ノードN）まで繰り返します。独立して、ノードNから逆順に同じ手順を実行します。i番目のメッセージはi-1番目のメッセージに依存しますが、反対方向に送信されるメッセージは互いに依存しません。両側から送信されるメッセージは、ノードの周辺分布を計算するために必要です。通常のビリーフプロパゲーションでは、すべてのメッセージが保存されるため、O(n)のメモリを消費します。
島は通常通りメッセージの受け渡しから開始しますが、(i+1)番目のメッセージを送信した後、i番目のメッセージを破棄します。2つのメッセージ受け渡し手順が途中で出会うと、アルゴリズムはチェーンの各半分を再帰的に実行します。
再帰の各ステップでチェーンは2つに分割されるため、再帰の深さはlog(N)です。各深さレベルですべてのメッセージを再度渡す必要があるため、このアルゴリズムは単一プロセッサでO(n log n)の時間がかかります。各再帰ステップで2つのメッセージを格納する必要があるため、このアルゴリズムはO(log n)の空間を使用します。log(N)個のプロセッサがある場合、各再帰ステップを別々のプロセッサで実行することで、このアルゴリズムはO(n)の時間で実行できます（つまり、単一プロセッサではN/2 + N/4 + N/8 ... = Nの時間がかかります）。
参考文献
- ^ J. Binder、K. Murphy、S. Russell. 動的確率ネットワークにおける空間効率の高い推論. 国際人工知能合同会議、1997年。
