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

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

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

Для такого HMM:

эта вероятность записывается как . Здесь есть скрытое состояние , которое сокращенно и является наблюдением в . Состояние доверия может быть вычислено на каждом временном шаге, но выполнение этого, в строгом смысле, дает не наиболее вероятную последовательность состояний , а скорее наиболее вероятное состояние на каждом временном шаге с учетом предыдущей истории.${\ Displaystyle P (x_ {t} | y_ {1: t})}$${\ Displaystyle х (т)}$${\ displaystyle x_ {t}}$${\ displaystyle y_ {1: t}}$${\ displaystyle 1}$${\ displaystyle t}$

История [ править ]

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

Алгоритм [ править ]

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

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

${\ Displaystyle \ альфа _ {t} (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 _{t}(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 _{t}(x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha _{t-1}(x_{t-1})}$.

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

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

Сглаживание [ править ]

Чтобы учесть будущую историю (то есть, если кто-то хочет улучшить оценку для прошлых времен), вы можете запустить обратный алгоритм, который дополняет прямой алгоритм. Это называется сглаживанием . ^{[ почему? ]} В вперед / назад алгоритм вычисляет для . Таким образом, полный алгоритм прямого / обратного направления учитывает все свидетельства.${\displaystyle P(x_{k}|y_{1:t})}$${\displaystyle 1<k<t}$

Расшифровка [ править ]

Для достижения наиболее вероятной последовательности требуется алгоритм Витерби . Он вычисляет наиболее вероятную последовательность состояний с учетом истории наблюдений, то есть максимальную последовательность состояний .${\displaystyle P(x_{0:t}|y_{0:t})}$

Псевдокод [ править ]

 для .${\displaystyle t=t+1}$ ${\displaystyle \alpha _{t}(x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha _{t-1}(x_{t-1})}$ пока t = T

Пример [ править ]

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

Применение алгоритма [ править ]

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

Варианты алгоритма [ править ]

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

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

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

Сложность [ править ]

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

См. Также [ править ]

• Алгоритм Витерби
• Вперед-назад алгоритм

Дальнейшее чтение [ править ]

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

Ссылки [ править ]

• Стратонович Р.Л. «Условные марковские процессы». Теория вероятностей и ее приложения 5, вып. 2 (1960): 156178.
• Лоуренс Р. Рабинер, Б. Х. Хуанг (январь 1986 г.). «Введение в скрытые марковские модели». Журнал IEEE ASSP : 4–15.

• Роджер Бойл, Учебное пособие по скрытым марковским моделям. 24 апреля 2016 г. [5]
• Чжан, Пинг и Христос Г. Кассандрас. «Улучшенный прямой алгоритм для оптимального управления классом гибридных систем». Автоматическое управление, транзакции IEEE от 47.10 (2002): 1735-1739.

Внешние ссылки [ править ]

Программное обеспечение [ править ]

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