The island algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for performing inference on
hidden Markov models
A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ob ...
, or their generalization,
dynamic Bayesian networks.
It calculates the
marginal distribution
In probability theory and statistics, the marginal distribution of a subset of a collection of random variables is the probability distribution of the variables contained in the subset. It gives the probabilities of various values of the varia ...
for each unobserved node, conditional on any observed nodes.
The island algorithm is a modification of
belief propagation
A belief is an attitude that something is the case, or that some proposition is true. In epistemology, philosophers use the term "belief" to refer to attitudes about the world which can be either true or false. To believe something is to take i ...
.
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.
[J. Binder, K. Murphy and S. Russell.]
Space-Efficient Inference in Dynamic Probabilistic Networks
Int'l, Joint Conf. on Artificial Intelligence, 1997.
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
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
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).
References
{{reflist
Bioinformatics algorithms
Hidden Markov models