El algoritmo de isla es un algoritmo para realizar inferencias en modelos de Markov ocultos , o su generalización, redes dinámicas bayesianas . Calcula la distribución marginal para cada nodo no observado, condicionada a cualquier nodo observado.
El algoritmo de la isla es una modificación de la propagación de creencias . Cambia el uso de memoria más pequeño por un tiempo de ejecución más largo: mientras que la propagación de creencias toma O (n) tiempo y O (n) memoria, el algoritmo de isla toma O (n log n) tiempo y O (log n) memoria. En una computadora con un número ilimitado de procesadores, esto se puede reducir a O (n) tiempo total, sin dejar de ocupar solo O (log n) de memoria. [1]
El algoritmo
Para simplificar, describimos el algoritmo en modelos de Markov ocultos. Se puede generalizar fácilmente a redes bayesianas dinámicas mediante el uso de un árbol de unión .
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 yendo en orden inverso. El i-ésimo mensaje depende del (i-1) -ésimo, pero los mensajes que van en direcciones opuestas no dependen unos de otros. Los mensajes provenientes 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) memoria.
La isla comienza pasando mensajes como de costumbre, pero tira 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 se repite en cada mitad de la cadena.
Dado que la cadena se divide en dos en cada paso recursivo, la profundidad de la recursividad es log (N). Dado que cada mensaje debe transmitirse 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 el espacio O (log n). Dados los procesadores log (N), el algoritmo se puede ejecutar en O (n) tiempo usando un procesador separado para hacer cada paso recursivo (por lo tanto, tomando N / 2 + N / 4 + N / 8 ... = N tiempo en una sola procesador).
Referencias
- ^ J. Binder, K. Murphy y S. Russell. Inferencia espacial eficiente en redes probabilísticas dinámicas . Int'l, Joint Conf. sobre Inteligencia Artificial, 1997.