Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 200
Текст из файла (страница 200)
Ключом к созданию алгоритма с линейными затратами времени является регистрация результатов прямой фильтрации по всей последовательности. В таком случае можно выполнить обратную рекурсию от с вплоть до 1, вычисляя сглаженную оценку для каждого этапа К из вычисленного обратного сообщения Ь„„, и хранимого прямого сообщения Ег,ы Этот алгоритм, обоснованно названный 'в. прямым — обратным алгоритмом ((опчаг(( — Ьас]очагб а(яог(1]згп), показан в листинге 15.1.
Листинг 15.1. Прямой-обратный алгоритм лля вычисления авестериерных вероятностей последовательности состояний при наличии последовательности наблюдений. Операторы вогчагд и васиеагд определены в уравнениях 15.3 в 15.7 Еппсевоп Рогиагб-васкиагб(еч,ргдог) геецгпв вектор распределений вероятностей Епрпев: еч, вектор значений свидетельств для этапов 1,...,С ргдог, распределение априорных вероятностей в начальном состоянии, Р(ХО) 1оса1 чаг1аЬ1ев: Еч, вектор прямых сообыений для этапов О,..., С Ь, представление обратного сообаения, первоначально состоящее из одних единиц, 1 вч, вектор сглаженных оценок для этапов 1,..., С Еч(О] ь- ргдог Еог 1=1 Со С со Еч(1] + — Рогыагб(яч[1-1],еч(1]) Еог Е=С боепсо 1 бо вч[1] ь- ногва11ге(Еч(1]хЬ) Ь ь- Васкыагд(Ь,еч(1]) геспгп вч Внимательный читатель должен был заметить, что структура байесовской сети, показанной на рис.
15.3, представляет собой полидерево, согласно терминологии главы ! 4. Это означает, что непосредственное применение алгоритма кластеризации также приводит к созданию алгоритма с линейными затратами времени, который 731 Глава 15. Вероятностные рассуждения во времени вычисляет сглаженные оценки для всей последовательности. Итак, вполне понятно, что прямой — обратный алгоритм фактически представляет собой частный случай алгоритма распространения в полидереве, используемого в сочетании с методами кластеризации (хотя эти два алгоритма были разработаны независимо). Прямой — обратный алгоритм лежит в основе вычислительных методов, применяемых во многих таких приложениях, где приходится иметь дело с последовательностями зашумленных результатов наблюдений, начиная от распознавания речи и заканчивая слежением за самолетами с помощью радара.
Как было описано выше, с точки зрения практики он имеет два недостатка. Первым из них является пространственная сложность, которая может оказаться слишком высокой применительно к приложениям, где пространство состояний велико, а последовательности имеют большую длину. В нем используется пространство О( ( Е ~ С), где ~ Е ~ — размер представления прямого сообщения. Такую потребность в пространстве можно уменьшить до О( ~ х ~ 1од С) с помощью соответствующего увеличения временной сложности на коэффициент 1од с, как показано в упр. 15.3, В некоторых случаях (см, раздел 15.3) может использоваться алгоритм с постоянными потребностями в пространстве, но без лишних затрат времени.
Вторым недостатком этого несложного алгоритма является то, что он требует модификации для использования в оперативных приложениях, где сглаженные оценки должны вычисляться для более ранних временных срезов по мере того, как к концу последовательности непрерывно добавляются новые наблюдения. Наиболее часто возникает требование по обеспечению 'в. сглаживания с постоянным запаздыванием, при котором необходимо вычислять сглаженную оценку и (х,.а ~ е...) для постоянного значения с).
Это означает, что сглаживание выполняется для временного среза, отстоящего на с) этапов от текущего времени с; по мере возрастания с сглаживание не лолжно отставать. Безусловно, что прямой — обратный алгоритм можно вызывать на выполнение применительно к данным д-этапного "окна" по мере добавления результатов каждого нового наблюдения, но такой подход, по-видимому, является неэффективным. В разделе 15.3 будет показано, что сглаживание с постоянным запаздыванием в некоторых случаях может выполняться за постоянное время в расчете на каждое обновление, независимо от запаздывания с).
Поиск наиболее вероятной последовательности Предположим, что (сгце, ение, йа?ве, схие, ские) — последовательность истинностных значений с результатами наблюдений за появлением директора с зонтиком, которые проводил охранник в течение первых пяти дней своей работы. Какая последовательность состояний погоды может стать наиболее вероятным объяснением для этих данных? Означает ли отсутствие зонтика в день 3, что не было дождя или директор забыл его взять? А если в день 3 не было дождя, то, возможно, дождь не шел и в день 4 (поскольку погода обычно является устойчивой), однако директор захватил с собой зонтик просто на всякий случай. В целом существуют 2' возможных последовательностей состояний погоды, которые могут быть приняты в качестве объяснения. Но есть ли способ найти наиболее вероятную из этих последовательностей, не перебирая их все? Один из подходов, который может быть опробован, состоит в использовании следующей процедуры с линейными затратами времени: с помощью алгоритма 732 Часть Ч.
Неопределенные знания и рассуждения в условиях неопределенности сглаживания найти распределения апостериорных вероятностей погоды на каждом временном интервале; после этого составить последовательность, используя на каждом этапе наиболее вероятное состояние погоды, соответствуюшее этим апостериорным вероятностям.
Но такой подход должен вызвать у читателя сомнения, поскольку апостериорные вероятности, вычисленные с помошью сглаживания, представляют собой распределения вероятностей для отдельных временных интервалов, тогла как, чтобы найти наиболее вероятную последовательность, необходимо рассматривать совместные вероятности по всем временным интервалам.
Соответствующие результаты фактически могут оказаться довольно различными (см. упр. 15.4). Тем не менее алгоритм поиска наиболее вероятной последовательности с линейными затратами времени существует, но чтобы его найти, необходимо продумать все обстоятельства немного более тшательно. Алгоритм должен быть основан на том же свойстве марковости (неизменности порядка марковской цепи), которое позволило создать эффективные алгоритмы фильтрации и сглаживания. Проще всего можно подойти к решению этой задачи, рассматривая каждую последовательность как путь в графе, узлами которого являются возможные состояния на каждом временном интервале.
Такой граф показан для мира задачи с зонтиком на рис. 15.4, а. Теперь рассмотрим задачу поиска наиболее вероятного пути через этот граф, где значение правдоподобия любого пути представляет собой произведение вероятностей перехода вдоль этого пути и вероятностей конкретных наблюдений в каждом состоянии. В частности, сосредоточимся на тех путях, которые достигают состояния яа1п,= спце. Ввиду наличия свойства марковости можно прийти к заключению, что наиболее вероятный путь к состоянию дауп,= спца состоит из наиболее вероятного пути к некоторому состоянию, достигнутому во время 4, за которым следует переход в состояние ла1п,= спце, а состоянием во время 4, которое станет частью пути к состоянию па1п,= веце, является именно то состояние, которое максимизирует значение правдоподобия этого пути.
Иными словами, сж- существует рекурсивная связь между наиболее вероятными путями в каждое состояние хс„и наиболее вероятными путями в киждое состояние х,. Эту связь можно записать в виде уравнения, соединяюшего вероятности путей, следующим образом: пспх Р(хс, .,х„Х, с ) ес:с.с хс...мс = Я Р(ес+с ) хс.с) псах Р(х, с ) хс) пах Р(х„...,х, с,мс ) ес.,) хс ( мс...х,.с ( 1 9 . 9 ) Уравнение 15.9 идентично уравнению фильтрации 15.3, за исключением описанных ниже отличий. 1.
ПРЯМОЕ СООбЩЕНИЕ й,, = Р(Х„~Е,,с) ЗаМЕНЯЕтСЯ СЛЕДУЮЩИМ СООбШЕНИЕМ, т.е. вероятностями наиболее правдоподобного пути в каждое состояние х,: псы, = псах Р(мс, ...,хс с Хс ) ес,,) хс...мс с 2. Суммирование по переменным х, в уравнении 15.3 заменяется максимизацией по переменным х, в уравнении 15.9. Таким образом, алгоритм вычисления наиболее вероятной последовательности аналогичен алгоритму фильтрации: он проходит в прямом направлении вдоль по- Глава 15. Вероятностные рассуждения во времени 733 следовательности, вычисляя сообщение т на каждом временном интервале с помощью уравнения 15.9. Ход этих вычислений показан на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
