Алгоритм пересылки

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

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

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

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

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

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

Содержание

  • 1 История
  • 2 Алгоритм
  • 3 Сглаживание
  • 4 Декодирование
  • 5 Псевдокод
  • 6 Пример
  • 7 Применение алгоритма
  • 8 Варианты алгоритма
  • 9 Сложность
  • 10 См. Также
  • 11 Дополнительная литература
  • 12 Ссылки
  • 13 Внешние ссылки
    • 13.1 Программное обеспечение

История

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

Алгоритм

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

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

α t (xt) = p (xt, y 1: t) = ∑ xt - 1 p (xt, xt - 1, y 1: t) {\ displaystyle \ alpha _ {t} (x_ {t}) = p (x_ {t}, y_ {1: t}) = \ sum _ {x_ {t-1}} p (x_ {t}, x_ {t) -1}, y_ {1: t})}\ alpha _ {t} (x_ {t}) = p (x_ {t}, y _ {{1: t}}) = \ sum _ {{x _ {{t-1}}}} p (x_ {t}, x _ {{t-1}}, y _ {{1: t}}) .

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

α t (xt) = ∑ xt - 1 p (yt | xt, xt - 1, y 1: t - 1) p (xt | xt - 1, y 1: t - 1) p (xt - 1, y 1: t - 1) {\ 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})}\ 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 }}) .

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

α t (xt) = p (yt | xt) ∑ xt - 1 п (xt | xt - 1) α t - 1 (xt - 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})}\ 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}}) .

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

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

Сглаживание

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

Декодирование

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

Псевдокод

init t = 0 {\ displaystyle t = 0}t = 0 , вероятности перехода p (xt | xt - 1) {\ displaystyle p (x_ {t} | x_ {t-1})}p (x_ {t} | x _ {{t-1}}) , вероятности выбросов, p (yj | xi) {\ displaystyle p (y_ {j} | x_ {i})}{\ displaystyle p (y_ {j} | x_ {i})} , наблюдаемая последовательность, y (1: t) {\ displaystyle y (1: t)}{\ displaystyle y (1: t)}

для t = t + 1 {\ displaystyle t = t + 1}t знак равно t + 1 α t (xt) = p (yt | xt) ∑ xt - 1 p (xt | xt - 1) α t - 1 (xt - 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_ { т-1})}\ 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

return p (y (1: t)) = α T {\ displaystyle p (y (1: t)) = \ alpha _ {T}}{\ displaystyle p (y (1: t)) = \ alpha _ {T}}

Пример

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

Приложения алгоритма

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

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

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

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

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

Сложность

Сложность прямого алгоритма составляет θ (нм 2) {\ displaystyle \ theta (nm ^ {2})}{\ displaystyle \ theta (nm ^ {2})} , где m {\ displaystyle m}m - количество скрытых или скрытых переменных, таких как погода в примере выше, а n {\ displaystyle n}n - длина последовательности наблюдаемой переменной. Это явное сокращение от специального метода исследования всех возможных состояний со сложностью θ (nmn) {\ displaystyle \ theta (nm ^ {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.

Внешние ссылки

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

Последняя правка сделана 2021-05-20 12:25:52
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте