СКРЫТЫЕ МАРКОВСКИЕ МОДЕЛИ

В предыдущем разделе были разработаны алгоритмы формирования временнь/х вероятностных рассуждений с использованием общей инфраструктуры, которая была независимой от конкретной формы моделей перехода и моделей восприятия. В этом и следующих двух разделах будут описаны более конкретные модели и приложения, которые иллюстрируют мощь этих простых алгоритмов, а в некоторых случаях допускают дополнительные усовершенствования.
Начнем с описания скрытой марковской модели, или сокращенно НММ (Hidden Markov Model). Любая модель НММ — это временная вероятностная модель, в которой состояние процесса описано с помощью единственной дискретной случайной переменной. Возможными значениями этой переменной являются возможные состояния мира. Поэтому пример с зонтиком, описанный в предыдущем разделе, представляет собой одну из моделей НММ, поскольку в нем применяется лишь единственная переменная состояния, Raint. Во временную модель могут быть введены дополнительные переменные состояния без выхода за пределы инфраструктуры НММ, но только путем комбинирования всех переменных состояния в единственную "мегапеременную", значениями которой являются все возможные кортежи значений отдельных переменных состояния. В данном разделе будет показано, что благодаря такой жестко регламентированной структуре моделей НММ появляется возможность создавать очень простые и элегантные матричные реализации всех основных алгоритмов3. В разделе 15.6 показано, как модели НММ используются для распознавания речи.
Упрощенные матричные алгоритмы
При использовании единственной, дискретной переменной состояния Xt можно определить более сжатую форму представлений модели перехода, модели восприятия, а также прямых и обратных сообщений. Предположим, что переменная состояния Xt имеет значения, обозначенные целыми числами 1,..., S, где S— количество возможных состояний. В таком случае модель перехода Р (Xt | Xt_x) преобразуется в матрицу Т с размерами S х S, где
TID = P{Xt=j\Xt-1=i)
Таким образом, представляет собой вероятность перехода из состояния i в состояние j. Например, матрица перехода для мира задачи с зонтиком выглядит следующим образом:
0.7 0.3
т = PUtlXt-!) = ( 0 3 0 1)
Переведем также в матричную форму модель восприятия. В данном случае, поскольку известно, что значение переменной свидетельства Et равно, скажем, et, необходимо использовать только ту часть модели, в которой определена вероятность появления значения et. Для каждого временного интервала t мы составим диагональную матрицу Ot, диагональные элементы которой задаются значениями
P( et I Xt=i), а остальные элементы равны 0. Например, в мире задачи с зонтиком вдень 1 было получено значение untrue, поэтому, согласно рис. 15.2, имеет место следующее:
Теперь, если для представления прямых и обратных сообщений будут использоваться векторы столбцов, то все вычисления преобразуются в простые матрично-векторные операции. Прямое уравнение 15.3 принимает следующий вид:
fl:t + l = ОС Ot + l ТТ fl!t (15.10)
а обратное уравнение 15.7 становится следующим:
bk+1:t = Т Ok+i bk+2:t (15.11)
Как показывают эти уравнения, временная сложность прямого—обратного алгоритма (см. листинг 15.1), применяемого к последовательности с длиной t, равна 0(S2t), поскольку на каждом этапе требуется умножать вектор с S элементами на матрицу SxS. Потребность в пространстве измеряется величиной О (St), так как при проходе в прямом направлении необходимо сохранить в памяти t векторов с размером S.
Такая матричная формулировка не только становится изящным описанием алгоритмов фильтрации и сглаживания для моделей НММ, но и открывает возможности для создания улучшенных алгоритмов. Первым из таких алгоритмов является простой вариант прямого—обратного алгоритма, который обеспечивает выполнение сглаживания за счет использования постоянного пространства, независимо от длины последовательности. Идея этого алгоритма состоит в том, что для выполнения сглаживания в любом конкретном временном срезе к требуется одновременное присутствие в памяти и прямого, и обратного сообщений, f1:k и bk+1:t, согласно уравнению 15.6. В прямом—обратном алгоритме это достигается за счет хранения значений f, вычисленных во время прохода в прямом направлении, для того, чтобы они были доступными во время прохода в обратном направлении. Еще один способ достижения этой цели состоит в использовании одного прохода, в котором и значение f, и значение b распространяются в одном и том же направлении. Например, можно добиться распространения "прямого" сообщения f в обратном направлении, преобразовав уравнение 15.10 таким образом, чтобы оно действовало в другом направлении, как показано ниже.
fi:t = ос' (TV1 of1 f1:t+i
Этот модифицированный алгоритм сглаживания действует так, что в нем вначале осуществляется стандартный проход в прямом направлении для вычисления значения f 1.1 (при этом все промежуточные результаты уничтожаются), после чего выполняется проход в обратном направлении для совместного вычисления и Ь, и f, а затем эти значения используются для вычисления сглаженной оценки для каждого интервала. Поскольку требуется только одна копия каждого сообщения, потребности в памяти являются постоянными (т.е. независимыми от t, длины последовательности). Тем не менее этот алгоритм имеет одно существенное ограничение — в нем требуется, чтобы матрица перехода была обратимой, а модель восприятия не имела нулей, иными словами, чтобы каждое наблюдение было возможным в любом состоянии.

Матричная формулировка открывает возможности усовершенствования еще в одном направлении — в области создания методов оперативного сглаживания с постоянным запаздыванием. Тот факт, что сглаживание может быть выполнено за счет постоянных затрат пространства, наводит на мысль, что может существовать эффективный рекурсивный алгоритм для оперативного сглаживания, т.е. алгоритм, временная сложность которого остается независимой от величины запаздывания. Предположим, что запаздывание равно d; это означает, что сглаживание проводится во временном срезе t-d, притом что текущее время равно t. Согласно уравнению 15.6, для среза t-d необходимо рассчитать значение следующего выражения:
ОС f l:t-dbt-d+l:t
В таком случае после поступления новых результатов наблюдения необходимо будет вычислить следующее выражение для среза t-d+1:
ОС f l:t-d+lbt-d+2:t + l
Как можно выполнить эту операцию инкрементно? Прежде всего, можно вычислить f i:t_d+i из f i:t-d с использованием стандартного процесса фильтрации, в соответствии с уравнением 15.3.
Инкрементное вычисление обратного сообщения является более сложным, поскольку не существует простого соотношения между старым обратным сообщением bt-d+i:t и новым обратным сообщением bt_d+2:t+i- Вместо этого рассмотрим соотношение между старым обратным сообщением bt_d+1:t и обратным сообщением в начале последовательности, bt+1:t. Для этого d раз применим уравнение 15.11, чтобы получить следующее уравнение:
где матрица Bt_d+1:t является произведением последовательности матриц О и т. Матрицу в можно рассматривать как "оператор преобразования", который преобразует более позднее обратное сообщение в более раннее. Аналогичное уравнение остается справедливым для новых обратных сообщений, сформированных после поступления результатов следующего наблюдения:
Исследуя выражения для произведений в уравнениях 15.12 и 15.13, можно определить, что их связывает между собой простое соотношение, — чтобы получить второе произведение, достаточно "разделить" первое произведение на первый элемент TOt_d+i и умножить на новый последний элемент TOt+i. Поэтому на языке алгебры матриц можно представить следующее простое соотношение между старой и новой матрицами в:
Это уравнение предоставляет способ вычисления инкрементного обновления для матрицы в, которая, в свою очередь (в силу уравнения 15.13), позволяет вычислить новое обратное сообщение bt_d+2;t+i. Полный алгоритм, в котором предусматривается хранение и обновление значений f ив, показан в листинге 15.2.
Листинг 15.2. Алгоритм сглаживания с постоянным временнь/м запаздыванием на d этапов, реализованный как оперативный алгоритм, который выводит новую сглаженную оценку после получения данных наблюдения, относящихся к новому временному интервалу
function Fixed-Lag-Smoothing(et, hmmf d) returns распределение no Xt-d inputs: et, текущее свидетельство для временного интервала t hmm, скрытая марковская модель с матрицей переходов Т
с размерами 5X5 d, величина запаздывания при сглаживании static: t, текущее время, первоначально равно 1
f, распределение вероятностей (прямое сообщение P(Xt|ei:t)),
первоначально Prior[hmm] В, матрица d-зтапного обратного преобразования,
первоначально матрица идентичного преобразования et-d:t/ двухсторонний список свидетельств от t-d до t, первоначально пустой local variables: Ot-d,Ot, диагональные матрицы, содержащие
информацию модели восприятия
добавить et к концу списка et-d:t
Ot <— диагональная матрица, содержащая P(et|Xt)
if t>d then
f <— Forward (f, et)
удалить et-d-i с начала списка et-d:t
Ot-d <— диагональная матрица, содержащая Р (et-d |-Xt-d) В <- Ot-d_1Т_1BTOt else В <— BTOt
t if t>d then return Normalize(fxBl) else return пустое значение







Материалы

Яндекс.Метрика