Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 199
Текст из файла (страница 199)
независимыми от с) и потребность в пространстве также остается постоянной. (Соответствующие постоянные показатели временной и пространственной сложности, безусловно, зависят от размера пространства состояний и от конкретного типа используемой временной модели.) св Требования ко времени и пространству для обновления должны быть постоянными, если агент с ограниченной памятью обязан следить за распределением вероятностей для текущего состонния на протяжении неограниченной последовательности наблюдений. Проиллюстрируем процесс фильтрации, состоящий из двух этапов, на простом примере с зонтиком (см. рис. 15.2). Предполагается, что охранник обладает с определенной степенью уверенности сведениями о распределении априорных вероятностей дождя в день О, непосредственно до того, как началась данная последовательность наблюдений.
ПРедположим, что данным РаспРеделением ЯвлЯетсЯ Р(дь) =<О. 5, О. 5>. Теперь обработаем результаты двух наблюдений, как показано ниже. ° В ДЕНЬ 1 дИрЕКтОр ПРИШЕЛ С ЗОНТИКОМ, ПОЭтОМу (7,= Ст ОЕ. РЕЗуЛЬтатЫ ПрсдСКазания перехода от 0=0 к 0=1 состоят в следующем; Р(дь) = )' Р(Л1(сь) Р(сь) 'о <0.7,0.3>х0.5+<0.3,0.7>х0.5 = <0.5,0.5> Глава 15.
Вероятностные рассуждения во времени 727 а их обновление с помощью свидетельства, полученного для 0 = 1, является таковым: В(лг)иг) = а В(иг)лг)В(лг) = а <0.9,0.2><0.5,0.5> — а <0.45,0.1> = <0.818,0.182> ° В день 2 директор также пришел с зонтиком, поэтому г~г= схие.
Результаты предсказания перехода от 0=1 к 0=2 являются следующими: Р (Яг ~ сгг ) = ~ Р ( Яг ) г г ) Р ( гг ! ис ) г1 — <0.7,0.3> х 0.818 + <0.3,0.7> х 0.182 = <0.627,0.373> а обновление их с помощью свидетельства для 0=2 позволяет получить следующее: В(лг)иг,иг) = а В(иг)лг) В(лг~иг) = а <0.9,0.2><0.627,0.373> а <0.565,0.075> = <0.883,0.117> Интуитивно ясно, что вероятность дождя от дня 1 ко дню 2 повышается, поскольку дождь продолжается.
В упр. 15.2, а предлагается исследовать такую тенденцию дальше. Задача предсказания может рассматриваться просто как фильтрация без добавления новых свидетельств. В действительности процесс фильтрации уже включает одношаговое предсказание, и поэтому можно легко вывести следующую формулу рекурсивного вычисления для предсказания состояния в момент времени 0+)с+1 на основании предсказания для 0+)п Р(к„с,г ~ ес,) =,) Р(Х, с с)гсс.с) Р(х„с)ег с) хгсК (15.4) Естественно, что в этом вычислении участвует только модель перехода, а не модель восприятия. Интересно рассмотреть, что произойдет при попытке предсказывать все дальше и дальше в будущее. Как показано в упр.
15.2, б, прогнозируемое распределение для дождя сходится к фиксированной точке <О. 5, О. 5>, после чего продолжает оставаться неизменным. Это — так называемое стационарное распределение для марковского процесса, определяемого с помощью модели перехода (см.
также с. 1). О свойствах таких распределений и о Ж продолжительности смешивания (грубо говоря, о затратах времени, необходимых лля достижения фиксированной точки) известно очень многое. С точки зрения практики эти знания сводятся к печальному выводу, что любая попытка предсказать фактическое состояние для количества этапов, составляющего не больше чем небольшую часть количества, соответствующего продолжительности смешивания, обречена на неудачу. Чем более неопределенной является модель перехода, тем короче будет продолжительность смешивания и тем более туманным становится будущее.
Рекурсия в прямом направлении может использоваться не только для фильтрации и предсказания, но и для вычисления правдоподобия последовательности свидетельств, )г(ег.„) . Такое значение может оказаться применимым, если потребуется сравнить различные временные модели, которые способны вырабатывать олну и ту 728 Частью. Неопределенные знания и рассуждения в условиях неопределенности же последовательность свидетельств; например, в разделе 15.6 сравниваются раз- личные слова, при произношении которых может создаваться одна и та же последо- вательность звуков. Для такой рекурсии используется сообщение о правдоподобии Гг,, = Р(х„е,,).
Несложнопоказать, что справедливоследуюшеесоотношение: Рог иатг) ((м„е„г) После вычисления ег, к получим фактическое значение правдоподобия, исключая путем суммирования значение Х„: Ьг к = Р(ег „) = ~~~~ (г.к(хк) (15.5) Сглаживание Как было указано выше, сглаживание — это процесс вычисления распределения вероятностей значений переменных в прошлых состояниях при наличии СВИДЕтЕЛЬСтВ ВПЛОТЬ ДО НЫНЕШНЕГО СОСТОЯНИЯ, ИНЫМИ СЛОВаМИ, Р(Хк ~ Е...) ДЛЯ 1<К<с (рис. 15.3.) Такие вычисления наиболее удобно разбить на две части: применительно к свидетельствам вплоть до момента времени )г и к свидетельст- ВаМ От Ке1 дО С: Р(Хк(е...) = Р(хк)ег:к,ек г к) = и Р(хк)ег:к) Р(ек,г.к(хк,ег.к) (Применение правила Байеса) = а Р(Х«(ег:к) Р(ек+г:к(хк) (Применение правила условной независимости) = а Ег.к Ьк+г:к (15.6) Р (ек+к.к (хк) = ) Р (ек,г.к(хк, хк+г) Р (хк,г ) хк) (Обусловливание по хк,г) х), 1 Р(ек.г.к(хк,г ) Р (хк+г (Хк) Х хКк1 (Применение правила условной независимости) Х Р ( ек.г, ек.г, к ( хк.г ) Р (хк+ г ! Хк) хК+1 Р(ек г(хк+г) Р(ек г.к(хк+г) Р (хк+г (Хк) Х хКк1 (15.7) где используется сообщение Ь,,,=Р(ек,,( хк), определяемое как "обратное", по аналогии с прямым сообщением тг.к.
Прямое сообщение тг,к может быть вычислено путем фильтрации в прямом направлении от 1 до )с в соответствии с уравнением 15,3. Как оказалось, обратное сообщение Ьк„,, может быть вычислено с помошью рекурсивного процесса, который осуществляется в обратном направлении от с: 729 Глава ! 5. Вероятностные рассуждения во времени где последний этап преобразования следует из свойства условной независимости ек,г и ек„г,ы если дано хк,г Из трех множителей в этой операции суммирования первый и третий можно получить непосредственно с помощью модели, а второй представляет собои "рекурсивный вызов".
С использованием обозначения для сообщений получим следующее: Ь„,, = Вас)сыахс((ЬХ.г,„аг.гы) где функция вас)сыахс) осуществляЕт Обновление, описанное в уравнении )5.7. Как и при рекурсии в прямом направлении, время и пространство, требуемые для каждого обновления, являются постоянными и поэтому независимыми от с. О Рис.!5.3. ПРоЦесс сглаисиваниЯ, в котоРом вычислЯетсЯ Р(кь)аг.ь), распределение апостериорных вероятностей значений переменных в состоянии, наблюдавшемся в какой-то прошлый момент времени )<, если дона полная последовательность наблюдений от 1 до е Теперь становится вполне очевидно, что оба терма, приведенные в уравнении )5.6, можно вычислить с помощью рекурсий по времени, одна из которых проходит в прямом направлении от 1 до )с и в которой используется уравнение фильтрации )5.3, а другая проходит в обратном направлении от е до 7сь1 и в ней используется уравнение !5.7.
Следует отметить, что этап обратной рекурсии инициализируется с помощью выражения Ь„,,=Р (в„,, ~ К,) =1, где 1 — вектор из единиц (поскольку в„г, „— пустая последовательность, вероятность наблюдения равна 1). Итак, применим этот алгоритм к примеру с зонтиком и вычислим сглаженную оценку вероятности дождя в момент времени 0=1 по данным наблюдений за появлением директора с зонтиком в дни 1 и 2. Согласно уравнению )5.6, это значение определяется следующим образом; Р(кг)иг, иг) = (х Р(дг!иг) Р(иг)лг) (15.8) Как нам уже известно, первый терм равен <. 818, .182>, согласно результатам применения процесса прямой фильтрации, описанного выше. Второй терм можно вычислить, применив обратную рекурсию по уравнению ! 5.7; Р(иг!Яг) = () Р(иг)хг) Р()гг) Р(гг)дг) г2 — (0.9 х 1 х <0.7,0.3>) + (0.2 х 1 х <0.3,0.7>) — <0.69,0.41> Подставляя эти значения в уравнение ! 5.8, можно найти, что сглаженная оценка вероятности дождя в день ! такова: Р(дг! и„иг) = гх <О.
818, О. 182>х<0. 69, О. 41> = <О. 883, 0 117> 730 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности Таким образом, в данном случае сглаженная оценка выше, чем отфильтрованная оценка (О . 818). Это связано с тем, что появление директора с зонтиком в день 2 повышает вероятность того, что в день 2 шел дождь; в свою очередь, поскольку дожди обычно являются затяжными, это приводит к повышению вероятности дождя и вдень (.
И для прямой, и для обратной рекурсии требуется постоянное количество времени в расчете на каждый этап; поэтому временния сложность сглаживания по отношению к свидетельству е:,, составляет О( с) . Этим выражением определяется также сложность сглаживания в конкретном интервале времени ]с А если требуется провести сглаживание всей последовательности, то один из очевидных методов состоит в выполнении всего процесса сглаживания по одному разу для каждого интервала времени, в котором должно быть выполнено сглаживание.
Такой подход приводит к получению временной сложности о ( с') . Но в лучшем подходе можно было бы использовать очень простое приложение динамического программирования, чтобы свести сложность к величине О ( с) . Олин из намеков на то, как это сделать, можно найти в приведенном выше анализе примера с зонтиком, где была показана возможность повторного использования результатов прямой фильтрации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
