Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 201
Текст из файла (страница 201)
15.4, б. В конечном итоге этот алгоритм позволяет получить вероятность наиболее правдоподобной последовательности, достигающей каждого из заключительных состояний. Поэтому с его помощью можно легко выбрать последовательность, которая является наиболее правдоподобной среди всех прочих (соответствующие ей состояния обозначены на рисунке жирными контурами). Для того чтобы иметь возможность определить фактически наблюдаемую последовательность, а не просто вычислить ее вероятность, в этом алгоритме необходимо также сопровождать указатели от каждого состояния обратно к наилучшему состоянию, приведшему к нему (эти указатели показаны на рисунке жирными стрелками); соответствующую последовательность можно найти, проследовав по указателям в обратном направлении от наилучшего заключительного состояния. Ао!и ~ Лвтз Лвиз Лв~нз Явт„ еие ] (вье а) Г)мьге))а, заве вие гте яие ~те м) ! м! 2 м1 з и~в м| 5 Рис.
)5.4. Пример применения алгоритма Витерби: возможные последовательности состояний для переменной наьп, могут рассматриваться как пути через гра4г возможных состояний на каждом временном интервале (состояния обозначены прямоугольниками для предотвращения путаницы с узлами в байесовской сети) (а); результаты применения алгоритма Витерби к последовательности наблюдений за появлением директора с зонтиком, (Схсе, Схае, Га1зе, Ссце, Ссце) (б). Для каждого значения с показано значение сообщения ш~ „которое представляет собой вероятность наилучшей последовательности, достигающей каждого состояния во время с.
Кроме того, для каждого состояния ведущая в него жирная стрелка показывает его наилучшего преемника, соезасно оценке, представляющей собой произведение вероятности предшествующей последовательности и вероятности перехода. Наиболее вероятную последовательность можно определить, проходя по жирным стрелкам в обратном направлении от наиболее вероятного состояния в интерваяе времени т~ з Только что описанный алгоритм называется сзь алгоритмом Витерби в честь его разработчика. Временная сложность этого алгоритма, как и алгоритма фильтрации, линейно зависит от С, от длины последовательности.
Но в отличие от алгоритма фильтрации его потребность в пространстве также линейно зависит от с. Это связано с тем, что в алгоритме Витерби необходимо следить за указателями, которые обозначают наилучшую последовательность, ведущую к каждому состоянию. 734 Часть Ч. Неопределенные знания и рассухогения в условиях неопределенности 15.3.
СКРЫТЫЕ МАРКОВСКИЕ МОДЕЛИ В предыдущем разделе были разработаны алгоритмы формирования временных вероятностных рассуждений с использованием общей инфраструктуры, которая была независимой от конкретной формы моделей перехода и моделей восприятия. В этом и следующих двух разделах будут описаны более конкретные модели и приложения, которые иллюстрируют мощь этих простых алгоритмов, а в некоторых случаях допускают дополнительные усовершенствования. Начнем с описания Ъ.скрытой марковской модели, или сокращенно НММ (Н!г)реп Маг)(оч Мог)е!). Любая модель НММ вЂ” зто временная вероятностная модель, в которой состояние процесса описано с помощью единственной дискретной случайной переменной.
Возможными значениями этой переменной являются возможные состояния мира. Поэтому пример с зонтиком, описанный в предыдущем разделе, представляет собой одну из моделей НММ, поскольку в нем применяется лишь единственная переменная состояния, лазп,. Во временную модель могут быть введены дополнительные переменные состояния без выхода за пределы инфраструктуры НММ, но только путем комбинирования всех переменных состояния в единственную "мегапеременную*', значениями которой являются все возможные кортежи значений отдельных переменных состояния. В данном разделе будет показано, что благодаря такой жестко регламентированной структуре моделей НММ появляется возможность создавать очень простые и элегантные матричные реализации всех основных алгоритмов'.
В разделе 15.6 показано, как модели НММ используются для распознавания речи. Упрощенные матричные алгоритмы При использовании единственной, дискретной переменной состояния х„можно определить более сжатую форму представлений модели перехода, модели восприятия, а также прямых и обратных сообщений. Предположим, что переменная состояния х, имеет значения, обозначенные целыми числами 1, ..., Б, где Б — количество возможных состояний. В таком случае модель перехода в (х, ! х, „) преобразуется в матрицу т с размерами н х я, где т» = Р(хь=У!Хь ь=б) Таким образом, тьз представляет собой вероятность перехода из состояния з в состояние ~. Например, матрица перехода для мира задачи с зонтиком выглядит следующим образом: 0.7 0.3 т = Р(хь(хь ь) = ( 0 3 0,)) Переведем также в матричную форму модель восприятия.
В данном случае, поскольку известно, что значение переменной свидетельства х, равно, скажем, е„необходимо использовать только ту часть модели, в которой определена вероятность появления значения е,. Для каждого временного интервала с мы составим диагональную матрицу О„диагональные элементы которой задаются значениями з Читателю, не знакомому с основными операциями над векторами и матрицами, может потребоваться обратиться к приложению А, прежде чем продолжать чтение данного раздела. 735 Глава 15. Вероятностные рассуждения во времени Р( е, (Х,=з), а ОСтаЛЬНыЕ ЭЛЕмситЫ равНЫ О. Например, в мире задачи с зонтиком вдень 1 было получено значение (г;-ение, поэтому, согласно рис.
15.2, имеет место следующее: 0.9 0 ( о о.г) Теперь, если для представления прямых и обратных сообщений будут использоваться векторы столбцов, то все вычисления преобразуются в простые матричновекторные операции. Прямое уравнение 15.3 принимает следующий вид: Е,,,=аоат' Е,, (15.10) а обратное уравнение 15.7 становится следующим: Ьх+ас = т Ога Ьх+г ~ (15. 11) Как показывают эти уравнения, временная сложность прямо~о — обратного алгоритма (см. листинг !5.1), применяемого к последовательности с длиной с, равна О(~20), ПОСКОЛЬКУ На каждОм этапе требуется умножать векторе ~ элементами на матрицу яхя.
Потребность в пространстве измеряется величиной О(яе), так как при проходе в прямом направлении необходимо сохранить в памяти е векторов с размером Я. Такая матричная формулировка не только становится изящным описанием алгоритмов фильтрации и сглаживания для моделей НММ, но и открывает возможности для создания улучшенных алгоритмов.
Первым из таких алгоритмов является простой вариант прямого — обратного алгоритма, который обеспечивает выполнение сглаживания за счет использования постоянного пространства, независимо от длины последовательности. Идея этого алгоритма состоит в том, что для выполнения сглаживания в любом конкретном временном срезе )г требуется одновременное присутствие в памяти и прямого, и обратного сообщений, Е...
и Ь~„,„согласно уравнению 15.6. В прямом — обратном алгоритме это достигается за счет хранения значений Е, вычисленных во время прохода в прямом направлении, для того, чтобы они были доступными во время прохода в обратном направлении. Еще один способ достижения этой цели состоит в использовании одного прохода, в котором и значение Е, и значение Ь распространяются в одном и том же направлении. Например, можно добиться распространения "прямого" сообщения Е в обратном направлении, преобразовав уравнение 15.10 таким образом, чтобы оно действовало в другом направлении, как показано ниже.
-1 Е,,=а (т) Оеа Е,... Этот модифицированный алгоритм сглаживания действует так, что в нем вначале осуществляется стандартный проход в прямом направлении для вычисления значения Е... (при этом все промежуточные результаты уничтожаются), после чего выполняется проход в обратном направлении для совместного вычисления и Ь, и Е, а затем эти значения используются для вычисления сглаженной оценки для каждого интервала. Поскольку требуется только одна копия каждого сообщения, потребности в памяти являются постоянными (т.е.
независимыми от е, длины последовательности). Тем не менее этот алгоритм имеет одно существенное ограничение — в нем требуется, чтобы матрица перехода была обратимой, а модель восприятия не имела нулей, иными словами, чтобы каждое наблюдение было возможным в любом состоянии. 736 Часть У. Неопределенные знания и рассуждения в условиях неопределенности Матричная формулировка открывает возможности усовершенствования еше водном направлении — в области создания методов оперативного сглаживания с постоянным запаздыванием. Тот факт, что сглаживание может быть выполнено за счет постоянных затрат пространства, наводит на мысль, что может существовать эффективный рекурсивный алгоритм для оперативного сглаживания, т.е.
алгоритм, временная сложность которого остается независимой от величины запаздывания. Предположим, что запаздывание равно а); это означает, что сглаживание проводится во временном срезе с-с), притом что текущее время равно е. Согласно уравнению 15.6, для среза е-с) необходимо рассчитать значение следующего выражения: а Ег с аЬс-а г.с В таком случае после поступления новых результатов наблюдения необходимо будет вычислить следующее выражение для среза е-с)+ 1: и Ег.с.а сЪс-а+г.с+г Как можно выполнить эту операцию инкрементно? Прежде всего, можно вычис- ЛИТЬ Е...,„ ИЗ Е,, а С ИСПОЛЬЗОВаНИЕМ СтаНдартНОГО ПрсцЕССа фИЛЬтрацИИ, В СООтветствии с уравнением 15.3.
Инкрементное вычисление обратного сообщения является более сложным, поскольку не существует простого соотношения между старым обратным сообщением Ь, „;, И НОВЫМ ОбратНЫМ СООбщЕНИЕМ Ьс.„,,„,. ВМЕСТО ЭТОГО раССМОтрИМ СООтношение между старым обратным сообщением Ь, а„,, и обратным сообщением в начале последовательности, Ь„,,, Для этого с) раз применим уравнение ! 5.11, чтобы получить следующее уравнение: Ьсагс — П тпа Ьсг.с = Всаг, ° 1 г=с-а+1 115.12) где матрица В,,„,, яВляЕтСя ПрОиЗВЕдениЕм ПоследОВатЕльности матриц 0 и Е.
Матрицу В можно рассматривать как "оператор преобразования", который преобразует более позднее обратное сообщение в более раннее. Аналогичное уравнение остается справедливым для новых обратных сообщений, сформированных после поступления результатов следующего наблюдения: С 1 Ъс-а г.с 1 П ~ог Ьс+г.с г = Вс.а+г с+г 1 =с-д+2 (15.13) Исследуя выражения для произведений в уравнениях 15.12 и 15.13, можно определить, что их связывает между собой простое соотношение, — чтобы получить второе произведение, достаточно "разделить" первое произведение на первый элемент тО, а„и умножить на новый последний элемент ЕО„г.
Поэтому на языке алгебры матриц можно представить следующее простое соотношение между старой и новой матрицами в: -1 -1 Вс-а+г.с+г = Ос а+г 'Е Вс-а+г:с тОс+г 737 Глава 15. Вероятностные рассуждения во времени Это уравнение предоставляет способ вычисления инкрементного обновления для матрицы в, которая, в свою очередь (в силу уравнения 15.13), позволяет вычислить новое обратное сообщение Ь, а, „„. Полный алгоритм, в котором предусматривается хранение и обновление значений Е и в, показан в листинге 15.2. Листинг 15.2. Алгоритм сглаживания е постоянным временным запаздыванием на й этапов, реализованный как оперативный алгоритм, который выводит новую сглаженную оценку после получения данных наблюдения, относящихся к новому временному интервалу Еппсс1оп Рьхес-Ьад-ЭщооСЬ1пд(е„ Ьщщ, й) кесцкпв распределение по Хь-а Еприсв: еь, текущее свидетельство для временного интервала С Ьтт, скрытая марковская модель с матрицей переходов т с размерами Я х я б, величина запаздывания при сглаживании всаеас: С, текущее время, первоначально равно 1 Е, распределение вероятностей (прямое сообщение Р(Х,]еыь)) первоначально Ртьот[ллип] В, матоица с]-этапного обратного преобразования, первоначально матрица идентичного преобразования еь-юь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
