Jump to content

Островной алгоритм

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

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

  1. ^ Дж. Биндер, К. Мерфи и С. Рассел. Экономичный вывод в динамических вероятностных сетях . Международная совместная конференция. по искусственному интеллекту, 1997.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 01da72f00ed99a97ca0f2afee96733b9__1619784540
URL1:https://arc.ask3.ru/arc/aa/01/b9/01da72f00ed99a97ca0f2afee96733b9.html
Заголовок, (Title) документа по адресу, URL1:
Island algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)