Алгоритм острова - Island algorithm

В островной алгоритм является алгоритм для выполнения вывода на скрытые марковские модели, или их обобщение, динамические байесовские сети.Он вычисляет предельное распределение для каждого ненаблюдаемого узла в зависимости от наблюдаемых узлов.

Алгоритм острова представляет собой модификацию распространение веры. Он торгуется меньше использование памяти для более длительного времени: в то время как распространение убеждений занимает На) времени и 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) -го. Когда две процедуры передачи сообщений встречаются посередине, алгоритм повторяется на каждой половине цепочки.

Поскольку на каждом рекурсивном шаге цепочка делится на две части, глубина рекурсия это журнал (N). Поскольку каждое сообщение должно быть передано снова на каждом уровне глубины, алгоритм занимает время O (n log n) на одном процессоре. На каждом рекурсивном шаге должны храниться два сообщения, поэтому алгоритм использует пространство O (log n). С учетом количества процессоров log (N) алгоритм может быть запущен за O (n) времени, используя отдельный процессор для выполнения каждого рекурсивного шага (таким образом, принимая N / 2 + N / 4 + N / 8 ... = N раз на одном процессоре).

Рекомендации