Island algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The island algorithm is an algorithm for performing inference on hidden Markov models, or their generalization, dynamic Bayesian networks. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. The island algorithm is a modification of belief propagation. It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.

The island algorithm is an algorithm for performing inference on hidden Markov models, or their generalization, dynamic Bayesian networks. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. The island algorithm is a modification of belief propagation. It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.

The algorithm

For simplicity, we describe the algorithm on hidden Markov models. It can be easily generalized to dynamic Bayesian networks by using a junction tree. 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. 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.

Since the chain is divided in two at each recursive step, the depth of the recursion 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, the 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).

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1358123584 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001358123584 · captured 1780764152.0 · version history

Cite this page as: encyclopegia.org, “Island algorithm”, snapshot enwiki-001358123584. https://encyclopegia.org/a/island-algorithm

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.