Алгоритм остров является алгоритм для выполнения вывода на скрытых марковских моделей , или их обобщения, динамических байесовских сетей . Он вычисляет предельное распределение для каждого ненаблюдаемого узла в зависимости от любых наблюдаемых узлов.
Алгоритм острова - это модификация распространения убеждений . Он использует меньшее использование памяти для более длительного времени работы: в то время как распространение убеждений занимает O (n) времени и O (n) памяти, алгоритм острова занимает O (n log n) времени и O (log n) памяти. На компьютере с неограниченным количеством процессоров это может быть уменьшено до O (n) общего времени, но при этом потребуется только O (log n) памяти. [1]
Алгоритм [ править ]
Для простоты опишем алгоритм на скрытых марковских моделях. Его можно легко обобщить на динамические байесовские сети с помощью дерева соединений .
Распространение веры включает отправку сообщения от первого узла ко второму, затем использование этого сообщения для вычисления сообщения от второго узла к третьему и так далее до последнего узла (узла N). Независимо, он выполняет ту же процедуру, начиная с узла N и в обратном порядке. I-е сообщение зависит от (i-1) -го, но сообщения, идущие в противоположных направлениях, не зависят друг от друга. Сообщения, поступающие с обеих сторон, необходимы для расчета предельного распределения для узла. При обычном распространении убеждений все сообщения сохраняются, что занимает O (n) памяти.
Остров начинает с передачи сообщений как обычно, но выбрасывает i-е сообщение после отправки (i + 1) -го. Когда две процедуры передачи сообщений встречаются посередине, алгоритм рекурсивно повторяется на каждой половине цепочки.
Поскольку цепочка делится на две части на каждом рекурсивном шаге, глубина рекурсии равна log (N). Поскольку каждое сообщение должно быть передано снова на каждом уровне глубины, алгоритм занимает время O (n log n) на одном процессоре. На каждом рекурсивном шаге должны храниться два сообщения, поэтому алгоритм использует пространство O (log n). Учитывая log (N) процессоров, алгоритм может быть запущен за O (n) раз, используя отдельный процессор для выполнения каждого рекурсивного шага (таким образом, принимая N / 2 + N / 4 + N / 8 ... = N раз на одном процессор).
Ссылки [ править ]
- ^ Дж. Биндер, К. Мерфи и С. Рассел. Эффективный по пространству вывод в динамических вероятностных сетях . Int'l, Joint Conf. по искусственному интеллекту, 1997.
