問題
木構造因子グラフにおける積和アルゴリズムのメッセージパッシングの手続きについて考える。
メッセージはまずすべての葉ノードから任意に選ばれた根ノードに向かつて伝播され、
その後根ノードから葉ノードへと伝播される。
各ステップにおいて、メッセージを送るべきノードが、
そのメッセージを計算するために必要なすべてのメッセージをすでに受け取っているように
メッセージパッシングのスケジュールを組むことが可能であることを、帰納法を用いて示せ。
解答
ノードが つの場合、渡されるメッセージがないため、メッセージパッシングのスケジュールを組むことが可能です。
次に、ノードが 個の時、メッセージパッシングのスケジュールを組むことが可能と仮定します。
その木構造因子グラフにノードを追加します。
この新しい葉ノードは、送信メッセージを送信するために他のノードからのメッセージを待つ必要がないため、
他のメッセージが送信される前に、最初に送信するようにスケジュールできます。
その親ノードはこのメッセージを受信します。
その後、メッセージの伝播は、条件が成立すると想定されるノードがN個の元のツリーのスケジュールに従います。
根ノードから葉ノードへのメッセージの伝播では、
最初に、条件が成立すると仮定したノードが 個の元のツリーの伝播スケジュールに従います。
これが完了すると、新しい葉ノードの親は、その送信メッセージを新しい葉ノードに送信する準備が整います。
これにより、ノードが 個のメッセージパッシングのスケジュールを組むことが可能です。
以上より、題意が示せました。
