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

Алгоритм скрытой марковской модели

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

Введение

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

Для HMM, подобного этому:

Временная эволюция скрытой марковской модели

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

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

Алгоритм

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

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

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

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

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

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

${\displaystyle \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})}$.

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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})}}.}$

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

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

в то время как оценка MMSE дается выражением ${\displaystyle x_{t}}$

${\displaystyle {\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. Инициализировать

   ${\displaystyle t=0}$,

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

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

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

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

2. Для того , чтобы ${\displaystyle t=1}$ ${\displaystyle T}$

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

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

Пример

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

Сложность

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

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

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

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

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

История

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

Приложения

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

Смотрите также

• Алгоритм Витерби
• Алгоритм прямого-обратного хода
• Алгоритм Баума-Велча

Ссылки

1. Пэн, Цзянь-Сюнь, Кан Ли и Дэ-Шуан Хуан. «Гибридный прямой алгоритм для построения нейронной сети RBF». Neural Networks, IEEE Transactions on 17.6 (2006): 1439-1451.
2. Чжан, Пин и Христос Г. Кассандр. «Улучшенный прямой алгоритм для оптимального управления классом гибридных систем». Автоматическое управление, IEEE Transactions 47.10 (2002): 1735-1739.
3. Пэн, Цзянь-Сюнь, Кан Ли и Джордж У. Ирвин. «Новый непрерывный прямой алгоритм для нейронного моделирования RBF». Автоматическое управление, IEEE Transactions on 52.1 (2007): 117-122.
4. Лоуренс Р. Рабинер , "Учебник по скрытым марковским моделям и избранным приложениям в распознавании речи". Труды IEEE , 77 (2), стр. 257–286, февраль 1989 г. 10.1109/5.18626
5. Чжан, Яньсюэ, Дунмэй Чжао и Цзиньсин Лю. «Применение алгоритма Баума-Велча в многошаговой атаке». Журнал Scientific World Journal 2014.

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

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

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

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