Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 198
Текст из файла (страница 198)
Является ли такое предположение обоснованным, зависит от самой проблемной области. Марковское предположение первого порядка указывает, что переменные состояния содержат всю Глава 15. Вероятностные рассуждения во времени 723 информацию, необходимую для описания распределения вероятностей для следующего временного среза. Иногда такое предположение полностью соответствует истине; например, если некоторая частица совершает 'ж случайное блуждание вдоль оси х, изменяя свою позицию на величину ч 1 в каждый интервал времени, то применение в качестве состояния координаты х позволяет определить марковский процесс первого порядка.
Иногда такое предположение является лишь приблизительным, как и в случае предсказания дождя лишь на основании того, был ли дождь в предыдущие сутки. Как описано ниже, существуют два возможных метода корректировки, если такое приближение оказывается слишком неточным. 1. Повышение порядка модели марковского процесса. Например, можно перейти к использованию модели второго порядка, введя переменную Яадп,, в качестве родительской по отношению к дауд„ что позволит получить немного более точные предсказания (например, в Пало-Альто дождь очень редко идет больше двух дней подряд). 2.
Расширение множества переменных состояния. Например, можно ввести переменную с обозначением времени года деалоп„чтобы иметь возможность включить хронологические данные о дождливых временах года, или ввести переменные для температуры тегарела гиле„влажности нитЫдеу, и атмосферного давления рлельиле„чтобы иметь возможность использовать физическую модель условий, способствующих возникновению дождя. В упр. 15.1 предлагается показать, что первое решение (увеличение порядка молели) можно всегда переформулировать как расширение множества переменных состояния, при сохранении фиксированного порядка.
Следует отметить, что введение дополнительных переменных состояния может увеличить прогностическую мощь системы, но вместе с тем повысить требования к прогнозированию, поскольку при этом придется также прогнозировать значения новых переменных. Поэтому обычно исследователи стараются найти "самодостаточное" множество переменных, а это фактически означает, что прежде всего они стремятся понять "физику" моделируемого процесса.
Очевидно, что требования к точному моделированию процесса можно ослабить, если есть возможность ввести новые результаты восприятия (например, результаты измерения температуры и атмосферного давления), которые непосредственно предоставляют информацию о новых переменных состояния. Рассмотрим, например, задачу слежения за роботом, блуждающим случайным образом на плоскости Х вЂ” У. Можно было бы предложить, что достаточно воспользоваться таким множеством переменных состояния, как положение и скорость, — ведь для вычисления нового положения можно просто использовать законы Ньютона, а скорость будет изменяться непредсказуемо.
Но если робот получает питание электрической энергией от аккумулятора, то разрядка аккумулятора будет оказывать систематическое влияние на изменение скорости. А поскольку само это влияние зависит от того, сколько электроэнергии было израсходовано во всех предыдуших маневрах, то свойство принадлежности марковской цепи к модели определенного порядка (или просто марковосгль) нарушается. Марковость цепи можно восстановить, включив уровень зарядки аккумулятора даееетз, в состав переменных состояния, которые входят в множество х,.
Это позволит лучше предсказывать движения робота, но, в свою очередь, потребует создания модели для предсказания значе- 724 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности ния Вас селу, на основании значения ва с еегу,, и скорости. В некоторых случаях такое моделирование может быть выполнено достаточно надежно, а повышения точности можно будет добиться, введя для измерения уровня заряда аккумулятора новый датчик. 15.2. ВЕРОЯТНОСТНЫЙ ВЫВОД ВО ВРЕМЕННБ7Х МОДЕЛЯХ После определения структуры универсальной временной модели мы получаем возможность сформулировать основные задачи вероятностного вывода, которые должны быть решены с помощью этой модели, как описано ниже.
° ск Фильтрация, или 'в. текущий контроль. В этом состоит задача вычисления Ъ. доверительного состояния — распределения апостериорных вероятностей переменных, относящихся к текущему состоянию, при наличии всех полученных к данному моменту свидетельств. Это означает, что требуется вычислить значение Р (Х,) е„,,), при условии, что фактические свидетельства поступают в виде непрерывного потока, начиная со времени г=).. В примере с зонтиком это может означать вычисление вероятности дождя сегодня, если даны все результаты наблюдений о носителе зонтика, полученные до сих пор. А фильглралией называется та операция, которую должен выполнять рациональный агент в ходе слежения за текущим состоянием так, чтобы иметь возможность принимать рациональные решения (см.
главу 17). Как оказалось, почти идентичные расчеты должны осуществляться в процессе определения правдоподобия последовательности свидетельств, (е...). ° Ж Предсказание. В этом состоит задача вычисления распределения апостериорных вероятностей значений переменных в будущем состоянии, если даны все свидетельства, полученные к данному моменту. Это означает, что может потребоваться вычислить в (х„„) е„,,) для некоторого )с>0.
В примере с зонтиком такое вычисление может сводиться к определению вероятности дождя через три дня от нынешнего, если даны все результаты наблюдений за носителем зонтика, полученные до сих пор. Предсказание является полезным для оценки возможных стратегий. ° ек Сглаживание, или ск ретроспективный анализ. В этом состоит задача вычисления распределения апостериорных вероятностей значений переменных, относящихся к прошлому состоянию, если даны все свидетельства вплоть до нынешнего состояния. Это означает, что может потребоваться вычислить значение в (х„) е...) для некоторого )с, такого, что 0<я< с. В примере с зонтиком это может означать вероятность того, что дождь шел в прошлую среду, если даны все результаты наблюдений за носителем зонтика, полученные до сих пор. Ретроспективный анализ обеспечивает лучшую оценку информации о состоянии, которая была доступна к тому времени (поскольку включает больше свидетельств).
° Наиболее правдоподобное обаяснеиие. Если дан ряд результатов наблюдений, то может потребоваться найти последовательность состояний, которые с наибольшей вероятностью стали причиной получения результатов 725 Глава 15. Вероятностные рассуждения во времени наблюдений.
Это означает, что может потребоваться вычислить значение акулах„ р(хм.)ем,). Например, если директор приходил с зонтиком в каждый из первых трех дней, а на четвертый пришел без зонтика, то наиболее вероятным объяснением становится наличие дождя в первые три дня и отсутствие в четвертый. Алгоритмы решения такой задачи являются полезными во многих приложениях, включая распознавание речи (целью которого является поиск наиболее вероятной последовательности слов, если дан ряд звуков) и реконструкцию цепочек битов, передаваемых по зашумленному каналу. Кроме этих задач, необходимы методы для создания с помощью обучения моделей перехода и моделей восприятия на основании наблюдений. Также как и в случае статических байесовских сетей, обучение в динамических байесовских сетях может осуществляться в виде получения побочного результата от вероятностного вывода.
Вероятностный вывод предоставляет оценку того, какие переходы между состояниями фактически происходили и какие состояния привели к получению данных результатов восприятия, а эти оценки могут использоваться для обновления моделей. Обновленные модели предоставляют новые оценки, и в этом процессе происходят итерации до тех пор, пока все вычисления не сходятся.
Весь этот процесс представляет собой пример применения алгоритма "ожидания — максимизации", нли алгоритма ЕМ (Ехрес(абоп — Мах)гп)ха((оп) (см. раздел 20.3). Важно отметить, что для обучения требуется вероятностный вывод с полным сглаживанием, а не с фильтрацией, поскольку он предоставляет лучшие оценки состояний процесса. Обучение с фильтрацией может не позволить добиться правильной сходимости; рассмотрим, например, задачу обучения раскрытию убийств: чтобы узнать из наблюдаемых переменных с помощью вероятностного вывода, что скорее всего произошло на месте убийства, всегда требуется ретроспективный анализ. Алгоритмы для решения четырех задач вероятностного вывода, перечисленных в начале данного раздела, можно прежде всего описать на общем уровне, независимо от конкретного типа применяемой модели.
Усовершенствования этих алгоритмов, относящиеся к каждой модели, будут описаны в соответствующих разделах. Фильтрация и предсказание Начнем с фильтрации. Мы покажем, что эту задачу можно решить простым рекурсивным способом: если есть результаты фильтрации вплоть до момента с, можно легко вычислить результат для с+1 из нового свидетельства е„,. Это означает, что для некоторой функции Г имеет место следующее: Р(Хь,1)е~, 1) = Г(е„мР(Х,(ем,) ) Такой процесс часто называют 'ск рекурсивной оценкой. Соответствующее вычисление может рассматриваться как фактически состоящее из двух частей; прежде всего распределение вероятностей для текущего состояния проектируется вперед от с к се1, затем оно обновляется с использованием нового свидетельства е„„.
Такое двухэтапное протекание процесса можно выразить формально весьма просто: Р(Х, )еи„1) = Р(Х, 1(е1 ь,еьм) (Разделение саидетельстаа) ц Р(еь,г)хм1,еь ь)Р(Хь 1(ег ь) (Прмменение прааила Байеса) = а Р(еь,~~Хьм)Р(хь 1~е1 ь) (Преобразование в соответствии со свойством маркоаости свидетельства) 726 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности Здесь и далее в данной главе а представляет собой нормализуюшую константу, используемую для того, чтобы вероятности в сумме составляли 1.
Второй терм, Р (х„, ~ е,,), представляет одношаговое предсказание следующего состояния, а первый терм обновляет его новым свидетельством; обратите внимание на то, что значение Р (е„, ~ Х„, ) можно получить непосредственно из модели восприятия. Теперь определим одношаговое предсказание для текущего состояния путем обусловливания вероятностей значений переменных для текущего состояния х,: Р(х,.;)е..е) = а Р(е...)х.е) ~) Р(х„Пиь,е,,) Р(х-.(еи,) = а Р(е„,)Х,,) ~ Р(Хье)х )Р(иь)еи,) ее (Преобразование в соответствии со свойством марковости) (15.3) В операциях суммирования первым множителем является модель перехода, а вторым — распределение вероятностей для текущего состояния.
Поэтому получена требуемая рекурсивная формулировка. Отфильтрованная оценка Р (х, ~ е,,) может рассматриваться как "сообщение" ди „которое распространяется в прямом направлении вдоль последовательности состояний, будучи модифицируемым при каждом переходе и обновляемым при получении каждого нового результата наблюдения. Этот процесс можно представить следующим образом: Ви с+1 = а Роь наса ( лис, еь,1) где функция рохыагс( реализует обновление, описанное в уравнении 15.3. Если все переменные состояния являются дискретными, то затраты времени на каждое обновление остаются постоянными (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
