Прямой алгоритм

Не путать с алгоритмом вперед-назад .

в Прямой алгоритм контексте скрытой марковской модели (HMM) используется для расчета «состояния убеждения»: вероятности состояния в определенный момент времени с учетом истории доказательств. Этот процесс также известен как фильтрация . Прямой алгоритм тесно связан с алгоритмом Витерби , но отличается от него .

Введение

Прямой и обратный алгоритмы следует рассматривать в контексте вероятности, поскольку они представляют собой просто имена, данные набору стандартных математических процедур в нескольких полях. Например, ни «прямой алгоритм», ни «Витерби» не фигурируют в Кембриджской энциклопедии математики. Основное наблюдение, которое следует извлечь из этих алгоритмов, заключается в том, как организовать байесовские обновления и вывод, чтобы они были эффективными в вычислительном отношении в контексте ориентированных графов переменных (см. Сети сумм-продуктов ).

Для HMM, такого как этот:

Temporal evolution of a hidden Markov model

эта вероятность записывается как $p(x_{t}|y_{1:t})$. Здесь $x(t)$ это скрытое состояние, которое сокращенно обозначается как $x_{t}$ и $y_{1:t}$ это наблюдения $1$ к $t$.

Обратный алгоритм дополняет прямой алгоритм, принимая во внимание будущую историю, если кто-то хочет улучшить оценку прошлого времени. Это называется сглаживанием , и алгоритм прямого/обратного вычисления вычисляет $p(x_{t}|y_{1:T})$ для $1<t<T$. Таким образом, полный алгоритм вперед/назад учитывает все доказательства. Обратите внимание, что состояние убеждения может быть рассчитано на каждом временном шаге, но это, в строгом смысле, не создает наиболее вероятную последовательность состояний , а, скорее, наиболее вероятное состояние на каждом временном шаге, учитывая предыдущую историю. Для достижения наиболее вероятной последовательности алгоритм Витерби необходим . Он вычисляет наиболее вероятную последовательность состояний с учетом истории наблюдений, то есть последовательность состояний, которая максимизирует $p(x_{0:t}|y_{0:t})$.

Алгоритм

Цель прямого алгоритма — вычислить совместную вероятность $p(x_{t},y_{1:t})$, где для удобства обозначений мы сократили $x(t)$ как $x_{t}$ и $(y(1),y(2),...,y(t))$ как $y_{1:t}$. Как только совместная вероятность $p(x_{t},y_{1:t})$ вычисляется, остальные вероятности $p(x_{t}|y_{1:t})$ и $p(y_{1:t})$ легко получаются.

И государство $x_{t}$ и наблюдение $y_{t}$ предполагаются дискретными, конечными случайными величинами. Вероятности перехода состояний скрытой модели Маркова $p(x_{t}|x_{t-1})$, вероятности наблюдения/эмиссии $p(y_{t}|x_{t})$и начальная априорная вероятность $p(x_{0})$ предполагаются известными. Кроме того, последовательность наблюдений $y_{1:t}$ предполагается, что они даны.

Вычисление $p(x_{t},y_{1:t})$ наивно потребовалось бы маргинализировать все возможные последовательности состояний $\{x_{1:t-1}\}$, число которых растет экспоненциально с увеличением $t$. Вместо этого прямой алгоритм использует условной независимости правила скрытой модели Маркова (HMM) для рекурсивного выполнения вычислений.

Чтобы продемонстрировать рекурсию, позвольте

$\alpha (x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})$.

Использование правила цепочки для расширения $p(x_{t},x_{t-1},y_{1:t})$, мы можем тогда написать

$\alpha (x_{t})=\sum _{x_{t-1}}p(y_{t}|x_{t},x_{t-1},y_{1:t-1})p(x_{t}|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})$.

Потому что $y_{t}$ условно независима ни от чего, кроме $x_{t}$, и $x_{t}$ условно независима ни от чего, кроме $x_{t-1}$, это упрощается до

$\alpha (x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})$.

Таким образом, поскольку $p(y_{t}|x_{t})$ и $p(x_{t}|x_{t-1})$ модели задаются распределением выбросов и вероятностями перехода , которые предполагаются известными, можно быстро вычислить $\alpha (x_{t})$ от $\alpha (x_{t-1})$ и избежать экспоненциального времени вычислений.

Приведенную выше рекурсивную формулу можно записать в более компактном виде. Позволять $a_{ij}=p(x_{t}=i|x_{t-1}=j)$ - вероятности перехода и $b_{ij}=p(y_{t}=i|x_{t}=j)$ быть вероятности выбросов, тогда

$\mathbf {\alpha } _{t}=\mathbf {b} _{t}^{T}\odot \mathbf {A} \mathbf {\alpha } _{t-1}$

где $\mathbf {A} =[a_{ij}]$ – матрица вероятности перехода, $\mathbf {b} _{t}$ — i-я строка матрицы вероятности выбросов $\mathbf {B} =[b_{ij}]$ что соответствует фактическому наблюдению $y_{t}=i$ во время $t$, и $\mathbf {\alpha } _{t}=[\alpha (x_{t}=1),\ldots ,\alpha (x_{t}=n)]^{T}$ является альфа-вектором. $\odot$ является произведением Адамара между транспонированием $\mathbf {b} _{t}$ и $\mathbf {A} \mathbf {\alpha } _{t-1}$.

Начальное условие задается в соответствии с априорной вероятностью по $x_{0}$ как

$\alpha (x_{0})=p(y_{0}|x_{0})p(x_{0})$.

Как только совместная вероятность $\alpha (x_{t})=p(x_{t},y_{1:t})$ была вычислена с использованием прямого алгоритма, мы можем легко получить соответствующую совместную вероятность $p(y_{1:t})$ как

$p(y_{1:t})=\sum _{x_{t}}p(x_{t},y_{1:t})=\sum _{x_{t}}\alpha (x_{t})$

и требуемая условная вероятность $p(x_{t}|y_{1:t})$ как

$p(x_{t}|y_{1:t})={\frac {p(x_{t},y_{1:t})}{p(y_{1:t})}}={\frac {\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.$

После расчета условной вероятности мы также можем найти точечную оценку $x_{t}$. Например, оценка MAP $x_{t}$ дается

${\widehat {x}}_{t}^{MAP}=\arg \max _{x_{t}}\;p(x_{t}|y_{1:t})=\arg \max _{x_{t}}\;\alpha (x_{t}),$

в то время как оценка MMSE $x_{t}$ дается

${\widehat {x}}_{t}^{MMSE}=\mathbb {E} [x_{t}|y_{1:t}]=\sum _{x_{t}}x_{t}p(x_{t}|y_{1:t})={\frac {\sum _{x_{t}}x_{t}\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.$

Прямой алгоритм легко модифицируется для учета наблюдений из вариантов скрытой модели Маркова, таких как линейная система скачка Маркова .

Псевдокод

1. Инициализировать

   $t=0$,

   вероятности перехода, $p(x_{t}|x_{t-1})$,

   вероятности выбросов, $p(y_{t}|x_{t})$,

   наблюдаемая последовательность, $y_{1:T}$

   априорная вероятность, $\alpha (x_{0})$

2. Для $t=1$ к $T$

   $\alpha (x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})$.

3. Возвращаться $p(x_{T}|y_{1:T})={\frac {\alpha (x_{T})}{\sum _{x_{T}}\alpha (x_{T})}}$

Пример

Этот пример наблюдения за возможными состояниями погоды по наблюдаемому состоянию морских водорослей. У нас есть наблюдения за морскими водорослями в течение трех дней подряд: они были сухими, влажными и сырыми. Возможные состояния погоды могут быть солнечными, облачными или дождливыми. Всего может быть $3^{3}=27$ такие погодные последовательности. Исследование всех таких возможных последовательностей состояний требует очень больших вычислительных затрат. Чтобы уменьшить эту сложность, пригодится алгоритм Forward, где хитрость заключается в использовании условной независимости шагов последовательности для расчета частичных вероятностей: $\alpha (x_{t})=p(x_{t},y_{1:t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})$ как показано в приведенном выше выводе. Следовательно, мы можем рассчитать вероятности как произведение соответствующей вероятности наблюдения/выброса: $p(y_{t}|x_{t})$ (вероятность состояния $y_{t}$ наблюдаемое в момент времени t из предыдущего наблюдения) с суммой вероятностей достижения этого состояния в момент времени t, рассчитанной с использованием вероятностей перехода. Это снижает сложность проблемы: от поиска по всему пространству поиска до простого использования ранее вычисленных $\alpha$и вероятности перехода.

Сложность

Сложность прямого алгоритма $\Theta (nm^{2})$, где $m$ — количество скрытых или латентных переменных, таких как погода в приведенном выше примере, и $n$ – длина последовательности наблюдаемой переменной. Это явное сокращение от специального метода исследования всех возможных состояний со сложностью $\Theta (nm^{n})$.

Варианты алгоритма

• Гибридный прямой алгоритм : Вариант прямого алгоритма, называемый гибридным прямым алгоритмом (HFA), можно использовать для построения нейронных сетей с радиальной базисной функцией (RBF) с настраиваемыми узлами. Нейронная сеть RBF строится с использованием традиционных алгоритмов выбора подмножества. Структура сети определяется путем объединения как пошаговой прямой конфигурации сети, так и непрерывной оптимизации параметров RBF. Он используется для эффективного и действенного создания экономной RBF-нейронной сети, которая хорошо обобщает. Это достигается за счет одновременного определения структуры сети и оптимизации параметров в непрерывном пространстве параметров. HFA решает сложную проблему смешанных целых чисел с помощью интегрированной аналитической среды, что приводит к повышению производительности сети и снижению использования памяти для построения сети.

• Прямой алгоритм оптимального управления в гибридных системах : Этот вариант алгоритма Forward основан на структуре производственной среды, которая объединяет управление процессами и операциями. Мы выводим новое свойство структуры оптимальной траектории состояния, которое выполняется при модифицированном условии на функцию стоимости. Это позволяет нам разработать простой масштабируемый алгоритм для явного определения оптимальных средств управления, который может быть более эффективным, чем прямой алгоритм.

• Алгоритм непрерывного продвижения : Алгоритм непрерывного прямого распространения (CFA) можно использовать для нелинейного моделирования и идентификации с использованием нейронных сетей с радиальной базисной функцией (RBF). Предложенный алгоритм выполняет две задачи построения сети и оптимизации параметров в рамках интегрированной аналитической структуры и предлагает два важных преимущества. Во-первых, производительность модели можно значительно улучшить за счет непрерывной оптимизации параметров. Во-вторых, нейронное представление может быть построено без генерации и хранения всех кандидатов-регрессоров, что приводит к значительному снижению использования памяти и сложности вычислений.

История

Прямой алгоритм — один из алгоритмов, используемых для решения задачи декодирования. С момента развития распознавания речи и распознавание образов и смежные области, такие как вычислительная биология , в которых используются HMM, прямой алгоритм приобрел популярность.

Приложения

Прямой алгоритм в основном используется в приложениях, которым необходимо определить вероятность нахождения в определенном состоянии, когда мы знаем о последовательности наблюдений. Алгоритм можно применять везде, где мы можем обучать модель по мере получения данных с использованием метода Баума-Велча. или любой общий алгоритм EM. Затем алгоритм Forward расскажет нам о вероятности данных относительно того, что ожидается от нашей модели. Одно из приложений может относиться к области финансов, где оно может помочь принять решение о том, когда покупать или продавать материальные активы.Он может найти применение во всех областях, где мы применяем скрытые марковские модели. К популярным из них относятся области обработки естественного языка, такие как маркировка частей речи и распознавание речи. В последнее время он также используется в области биоинформатики.Алгоритм форварда также можно применять для прогнозирования погоды. У нас может быть HMM, описывающая погоду и ее связь с состоянием наблюдений в течение нескольких дней подряд (некоторые примеры могут быть сухими, влажными, сырыми, солнечными, облачными, дождливыми и т. д.). Мы можем рассмотреть возможность вычисления вероятности наблюдения любой последовательности наблюдений рекурсивно с учетом HMM. Затем мы можем вычислить вероятность достижения промежуточного состояния как сумму всех возможных путей к этому состоянию. Таким образом, частичные вероятности окончательного наблюдения будут содержать вероятность достижения этих состояний, пройдя всеми возможными путями.

См. также

• Алгоритм Витерби
• Алгоритм вперед-назад
• Алгоритм Баума – Уэлча

Дальнейшее чтение

• Книга Рассела и Норвига « Искусственный интеллект, современный подход» , начиная со страницы 570 издания 2010 года, представляет собой краткое изложение этой и связанных с ней тем.
• Смит, Падрайк, Дэвид Хекерман и Майкл И. Джордан. «Вероятностные сети независимости для скрытых марковских вероятностных моделей». Нейронные вычисления 9.2 (1997): 227-269. [1]
• Читай, Джонатон. «Скрытые марковские модели и динамическое программирование». Университет Осло (2011). [2]
• Кольшайн, Кристиан, Введение в скрытые марковские модели [3]
• Манганьелло, Фабио, Мирко Маркетти и Микеле Колаянни. Многоэтапное обнаружение атак и корреляция предупреждений в системах обнаружения вторжений. Информационная безопасность и гарантия. Springer Berlin Heidelberg, 2011. 101–110. [4]
• Чжан, Пин и Христос Г. Кассандрас. «Улучшенный прямой алгоритм для оптимального управления классом гибридных систем». Автоматическое управление, транзакции IEEE от 47.10 (2002 г.): 1735-1739.
• Стратонович Р.Л. "Условные марковские процессы". Теория вероятностей и ее приложения 5, вып. 2 (1960): 156178.

Программное обеспечение

• R-пакет скрытой марковской модели содержит функциональные возможности для вычисления и получения прямой процедуры.
• momentuHMM R-Package предоставляет инструменты для использования и вывода HMM.
• Библиотека GHMM для Python
• Библиотека Haskell пакета hmm для HMMS реализует алгоритм Forward.
• Библиотека для Java содержит реализации алгоритмов машинного обучения и искусственного интеллекта.