El algoritmo de la isla es un algoritmo para realizar inferencias sobre modelos ocultos de Markov o su generalización, redes bayesianas dinámicas . Calcula la distribución marginal para cada nodo no observado, condicionada a cualquier nodo observado.
El algoritmo de isla es una modificación de la propagación de creencias . Intercambia un uso menor de memoria por un tiempo de ejecución más largo: mientras que la propagación de creencias requiere O(n) tiempo y O(n) memoria, el algoritmo de isla requiere O(n log n) tiempo y O(log n) memoria. En una computadora con una cantidad ilimitada de procesadores, esto se puede reducir a un tiempo total de O(n), mientras que sigue utilizando solo O(log n) memoria. [1]
Para simplificar, describimos el algoritmo en modelos ocultos de Markov. Se puede generalizar fácilmente a redes bayesianas dinámicas mediante el uso de un árbol de uniones .
La propagación de creencias implica enviar un mensaje desde el primer nodo al segundo, luego usar este mensaje para calcular un mensaje desde el segundo nodo al tercero, y así sucesivamente hasta el último nodo (nodo N). Independientemente, realiza el mismo procedimiento comenzando en el nodo N y siguiendo en orden inverso. El i-ésimo mensaje depende del (i-1)-ésimo, pero los mensajes que van en direcciones opuestas no dependen entre sí. Los mensajes que vienen de ambos lados son necesarios para calcular la distribución marginal de un nodo. En la propagación de creencias normal, todos los mensajes se almacenan, lo que ocupa O(n) de memoria.
La isla comienza pasando mensajes como de costumbre, pero descarta el i-ésimo mensaje después de enviar el (i+1)-ésimo. Cuando los dos procedimientos de paso de mensajes se encuentran en el medio, el algoritmo recurre en cada mitad de la cadena.
Como la cadena se divide en dos en cada paso recursivo, la profundidad de la recursión es log(N). Como cada mensaje debe pasarse nuevamente en cada nivel de profundidad, el algoritmo toma O(n log n) tiempo en un solo procesador. Se deben almacenar dos mensajes en cada paso recursivo, por lo que el algoritmo usa espacio O(log n). Dados log(N) procesadores, el algoritmo se puede ejecutar en tiempo O(n) usando un procesador separado para realizar cada paso recursivo (tomando así N/2 + N/4 + N/8 ... = N tiempo en un solo procesador).