Островной алгоритм
Алгоритм острова — это алгоритм выполнения вывода по скрытым марковским моделям или их обобщению, динамическим байесовским сетям . Он вычисляет предельное распределение для каждого ненаблюдаемого узла в зависимости от любых наблюдаемых узлов.
Алгоритм острова представляет собой модификацию распространения убеждений . Он обменивает меньшее использование памяти на более длительное время работы: в то время как распространение убеждений требует времени 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 времени на один процессор).
Ссылки
[ редактировать ]- ^ Дж. Биндер, К. Мерфи и С. Рассел. Экономичный вывод в динамических вероятностных сетях . Международная совместная конференция. по искусственному интеллекту, 1997.