Фильтрация и предсказание
Начнем с фильтрации. Мы покажем, что эту задачу можно решить простым рекурсивным способом: если есть результаты фильтрации вплоть до момента t, можно легко вычислить результат для t+1 из нового свидетельства et+1. Это означает, что для некоторой функции f имеет место следующее:
P(Xt+i|ei:t+i) = f (et+i,P(Xt|e1:t) )
Такой процесс часто называют рекурсивной оценкой. Соответствующее вычисление может рассматриваться как фактически состоящее из двух частей: прежде всего распределение вероятностей для текущего состояния проектируется вперед от t к t+1, затем оно обновляется с использованием нового свидетельства et+1. Такое двухэтапное протекание процесса можно выразить формально весьма просто:
Р (Xt+i | ei:t+i) = Р (Xt+i I ei:t/et+i) (Разделение свидетельства)
= A P (et+i |Xt+i, ei:t) P (Xt+i I ei:t) (Применение правила Байеса)
= A P (et+i I Xt+i) P (Xt+i I ei:t) (Преобразование в соответствии со
свойством марковости свидетельства)
Здесь и далее в данной главе а представляет собой нормализующую константу, используемую для того, чтобы вероятности в сумме составляли 1. Второй терм, Р (xt+11 e1:t), представляет одношаговое предсказание следующего состояния, а первый терм обновляет его новым свидетельством; обратите внимание на то, что значение Р (et+11 xt+1) можно получить непосредственно из модели восприятия. Теперь определим одношаговое предсказание для текущего состояния путем обусловливания вероятностей значений переменных для текущего состояния xt:
В операциях суммирования первым множителем является модель перехода, а вторым — распределение вероятностей для текущего состояния. Поэтому получена требуемая рекурсивная формулировка. Отфильтрованная оценка Р (Xt | e1:t) может рассматриваться как "сообщение" f 1:t, которое распространяется в прямом направлении вдоль последовательности состояний, будучи модифицируемым при каждом переходе и обновляемым при получении каждого нового результата наблюдения. Этот процесс можно представить следующим образом:
fi:t+i = ОС Forward (fi:t, et+i)
где функция Forward реализует обновление, описанное в уравнении 15.3.
Если все переменные состояния являются дискретными, то затраты времени на каждое обновление остаются постоянными (т.е. независимыми от t) и потребность в пространстве также остается постоянной. (Соответствующие постоянные показатели временной и пространственной сложности, безусловно, зависят от размера пространства состояний и от конкретного типа используемой временной модели.) Ф~ Требования ко времени и пространству для обновления должны быть постоянными, если агент с ограниченной памятью обязан следить за распределением вероятностей для текущего состояния на протяжении неограниченной последовательности наблюдений.
Проиллюстрируем процесс фильтрации, состоящий из двух этапов, на простом примере с зонтиком (см. рис. 15.2). Предполагается, что охранник обладает с определенной степенью уверенности сведениями о распределении априорных вероятностей дождя в день 0, непосредственно до того, как началась данная последовательность наблюдений. Предположим, что данным распределением является Р (R0) =<0 . 5, 0 . 5>. Теперь обработаем результаты двух наблюдений, как показано ниже.
• В день 1 директор пришел с зонтиком, поэтому иг= true. Результаты предсказания перехода от t=0 к t=l состоят в следующем:
а их обновление с помощью свидетельства, полученного для t = 1, является таковым:
• В день 2 директор также пришел с зонтиком, поэтому U2=true. Результаты предсказания перехода от t=l к t=2 являются следующими:
а обновление их с помощью свидетельства для t=2 позволяет получить следующее:
Интуитивно ясно, что вероятность дождя от дня 1 ко дню 2 повышается, поскольку дождь продолжается. В упр. 15.2, а предлагается исследовать такую тенденцию дальше.
Задача предсказания может рассматриваться просто как фильтрация без добавления новых свидетельств. В действительности процесс фильтрации уже включает одношаговое предсказание, и поэтому можно легко вывести следующую формулу рекурсивного вычисления для предсказания состояния в момент времени t+k+1 на основании предсказания для t+k:
Естественно, что в этом вычислении участвует только модель перехода, а не модель восприятия.
Интересно рассмотреть, что произойдет при попытке предсказывать все дальше и дальше в будущее. Как показано в упр. 15.2, б, прогнозируемое распределение для дождя сходится к фиксированной точке <0 . 5, 0 . 5>, после чего продолжает оставаться неизменным. Это — так называемое стационарное распределение для марковского процесса, определяемого с помощью модели перехода (см. также с. 1). О свойствах таких распределений ио продолжительности смешивания (грубо говоря, о затратах времени, необходимых для достижения фиксированной точки) известно очень многое. С точки зрения практики эти знания сводятся к печальному выводу, что любая попытка предсказать фактическое состояние для количества этапов, составляющего не больше чем небольшую часть количества, соответствующего продолжительности смешивания, обречена на неудачу. Чем более неопределенной является модель перехода, тем короче будет продолжительность смешивания и тем более туманным становится будущее.
Рекурсия в прямом направлении может использоваться не только для фильтрации и предсказания, но и для вычисления правдоподобия последовательности свидетельств, P(e1:t). Такое значение может оказаться применимым, если потребуется сравнить различные временнь/e модели, которые способны вырабатывать одну и ту же последовательность свидетельств; например, в разделе 15.6 сравниваются различные слова, при произношении которых может создаваться одна и та же последовательность звуков. Для такой рекурсии используется сообщение о правдоподобии Ј1:t = Р (xt, ег. t). Несложно показать, что справедливо следующее соотношение:
i:t+i = Forward (i:t, et+i)
После вычисления Ј1:t получим фактическое значение правдоподобия, исключая путем суммирования значение xt: