Island algorithm

<h2 id="the-algorithm">The algorithm</h2>
<p>For simplicity, we describe the algorithm on hidden Markov models. It can be easily generalized to dynamic Bayesian networks by using a <a href="/facts/Junction_tree/p31V5rM2">junction tree</a>.  
</p><p>Belief propagation involves sending a message from the first node to the second, then using this message to compute a message from the second node to the third, and so on until the last node (node N).  Independently, it performs the same procedure starting at node N and going in reverse order.  The i-th message depends on the (i-1)-th, but the messages going in opposite directions do not depend on one another. The messages coming from both sides are required to calculate the marginal distribution for a node. In normal belief propagation, all messages are stored, which takes O(n) memory.
</p><p>The island begins by passing messages as usual, but it throws away the i-th message after sending the (i+1)-th one.  
When the two message-passing procedures meet in the middle, the algorithm recurses on each half of the chain.  
</p><p>Since the chain is divided in two at each recursive step, the depth of the <a href="/facts/Recursion/CxSKxJoW">recursion</a> is log(N).  Since every message must be passed again at each level of depth, the algorithm takes O(n log n) time on a single processor.  Two messages must be stored at each recursive step, so the algorithm uses O(log n) space.
Given log(N) processors, algorithm can be run in O(n) time by using a separate processor to do each recursive step (thus taking N/2 + N/4 + N/8 ... = N time on a single processor).
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>J. Binder, K. Murphy and S. Russell.  Space-Efficient Inference in Dynamic Probabilistic Networks.  Int'l, Joint Conf. on Artificial Intelligence, 1997. <a href="https://web.archive.org/web/20180102191353/https://pdfs.semanticscholar.org/8400/8ac8ea812b5955ffeedd4b27f4cb3a6958c8.pdf" target="_blank">https://web.archive.org/web/20180102191353/https://pdfs.semanticscholar.org/8400/8ac8ea812b5955ffeedd4b27f4cb3a6958c8.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Island algorithm open-in-new

Island algorithm