УПРАЖНЕНИЯ
15.1. Покажите, что любой марковский процесс второго порядка может быть переоформлен в виде марковского процесса первого порядка с дополненным множеством переменных состояния. Может ли такое преобразование всегда быть выполнено экономно, т.е. без увеличения количества параметров, необходимых для определения модели перехода?
15.2. В этом упражнении рассматривается, что происходит с вероятностями в мире задачи с зонтиком по мере приближения к пределу в длинных временнь/х последовательностях.
а) Предположим, что наблюдается нескончаемая последовательность дней,
в которых директор появляется на работе с зонтиком или без зонтика.
Покажите, что, по мере того, как проходят эти дни, вероятность дождя в
текущий день возрастает монотонно в направлении к фиксированной
точке. Рассчитайте эту фиксированную точку.
б) Теперь рассмотрим задачу прогнозирования все дальше и дальше в буду-
щее по данным только первых двух наблюдений с зонтиком. Вначале рас-
считайте вероятность P(R2+k \ Ulf U2) для 7с=1...20 и нанесите результаты
на график. Вы должны обнаружить, что эта вероятность сходится в фиксиро-
ванной точке. Рассчитайте точное значение для этой фиксированной точки.
15.3. В данном упражнении разрабатывается вариант прямого—обратного алгорит-
ма, приведенного в листинге 15.1, характеризующийся эффективным исполь-
зованием пространства. Требуется вычислить значение P(xk|e1:t) для
k=l,...,t. Такую задачу можно решить с помощью подхода по принципу
"разделяй и властвуй".
а) Для упрощения примем предположение, что значение t является нечет-
ным, и допустим, что промежуточная точка определяется выражением
h= (t+1) 12. Покажите, что значение P(xk|e1:t) можно вычислить для
Jc=l,...,h, если даны лишь первоначальное прямое сообщение f1:0, об-
ратное сообщение bh+1. t и свидетельство e1:h.
б) Покажите аналогичный результат для второй половины последовательности.
в) Если даны результаты выполнения заданий 15.3, а и 15.3, б, рекурсивный
алгоритм "разделяй и властвуй" можно сформировать, вначале выполнив
прогон в прямом направлении вдоль последовательности, а затем в обрат-
ном направлении от ее конца, сохранив лишь необходимые сообщения в
середине и в концах. Затем алгоритм вызывается на каждой половине по-
следовательности. Составьте подробный листинг этого алгоритма.
г) Определите временную и пространственную сложность алгоритма как
функцию от t, длины последовательности. Как изменятся эти результа-
ты, если входные данные будут разделены больше чем на две части?
15.4. На с. 732 была кратко описана ошибочная процедура определения наиболее вероятной последовательности состояний, в которой используется последовательность наблюдений. В этой процедуре предусматривается поиск в каждом временном интервале наиболее вероятного состояния, применение операции сглаживания и возврат последовательности, в которой собраны эти состояния. Покажите, что при использовании некоторых временных вероятностных моделей и последовательностей наблюдений эта процедура возвращает невозможную последовательность состояний (т.е. такую последовательность, что ее апостериорная вероятность равна нулю).
15.5. Часто возникает необходимость осуществлять текущий контроль за системой с непрерывным состоянием, поведение которой переключается непредсказуемым образом с одного режима на другой в множестве из к различных режимов. Например, самолет, пытающийся избежать поражения ракетой, может выполнить ряд различных маневров, которые попытается отследить система управления ракетой. Представление такой модели переключательного фильтра Калмана в виде байесовской сети показано на рис. 15.17.
а) Допустим, что дискретное состояние St имеет к возможных значений и
что априорная непрерывная оценка состояния Р (х0) представляет собой
многомерное гауссово распределение. Покажите, что предсказание Р (хх)
представляет собой сочетание гауссовых распределений, т.е. такую взве-
шенную сумму гауссовых распределений, что веса в сумме составляют 1.
б) Покажите, что если текущая оценка непрерывного состояния Р (xt | e1:t)
представляет собой сочетание т гауссовых распределений, то в общем
случае обновленная оценка состояния Р (xt+11 e1:t+1) будет представлять
собой сочетание km гауссовых распределений.
в) Какой аспект временного процесса представляют веса в сочетании гаус-
совых распределений?
Результаты выполнения заданий 15.5, а и 15.5, б, вместе взятые, показывают, что объем этого представления апостериорных вероятностей беспредельно возрастает даже при использовании переключательных фильтров Калмана, которые являются простейшими гибридными динамическими моделями.
15.6. Дополните недостающий этап вывода уравнения 15.17 — первый этап обновления для одномерного фильтра Калмана.
15.7. Рассмотрим ход выполнения операции обновления дисперсии в уравнении 15.18.
а) Нанесите на график значения выражения at2 как функции от t при на-
личии различных значений для <тх2 и <т22.
б) Покажите, что эта операция обновления имеет фиксированную точку,
такую, что a2(7t2—><т2, по мере того как t—»«>, и рассчитайте значение о2.
в) Дайте качественное объяснение того, что происходит по мере того, как
<Тх2-*0 И C7z2-*0.
15.8. Покажите, как представить модель НММ в виде рекурсивной реляционной вероятностной модели в соответствии с предложением, приведенным в разделе 14.6.
15.9. В этом упражнении более подробно анализируется устойчивая к отказам модель для датчика аккумулятора, показанная на рис. 15.11, а.
а) График на рис. 15.11, б обрывается при t=32. Дайте качественное описа-
ние того, что должно произойти по мере стремления t к бесконечности,
t->°°, если датчик продолжает выдавать показания 0.
б) Предположим, что температура окружающей среды влияет на датчик акку-
мулятора таким образом, что по мере возрастания температуры временные
отказы становятся все более вероятными. Покажите, как дополнить с уче-
том этого структуру сети DBN, приведенную на рис. 15.11, а, и объясните,
какие изменения потребуется внести в таблицы условных вероятностей.
в) После определения новой структуры этой сети, может ли робот использо-
вать показания датчика аккумулятора для вероятностного вывода данных
о текущей температуре?
15.10. Рассмотрите задачу применения алгоритма устранения переменной к сети
DBN для задачи с зонтиком, развернутую на три временнь/х среза, в которой
используется запрос Р (R3 \ ulf U2, и3). Покажите, что сложность этого алгоритма (размер наибольшего фактора) является одинаковой, независимо от того, устраняются ли переменные, касающиеся дождя, в прямом или обратном порядке.
15.11. В модели произношения слова "tomato", приведенной на рис. 15.15, допускается коартикуляция с первой гласной, поскольку даны две возможные фонемы. Альтернативный подход состоит в использовании трехфонемной модели, в которой фонема [ow(t,m) ] автоматически включает изменение в гласном звуке. Составьте полную трехфонемную модель для слова "tomato", включая вариант, касающийся диалекта.
15.12. Вычислите наиболее вероятный путь через модель НММ, приведенную на рис. 15.16, для выходной последовательности [Clt С2, С3, С4, С4, Сб, С7]. Кроме того, приведите значение его вероятности.