Скрытая марковская модель

Статистическая марковская модель

Скрытая марковская модель ( HMM ) — это марковская модель , в которой наблюдения зависят от латентного (или скрытого ) марковского процесса (называемого ). HMM требует, чтобы существовал наблюдаемый процесс , результаты которого зависят от результатов известным образом. Поскольку нельзя наблюдать напрямую, цель состоит в том, чтобы узнать о состоянии, наблюдая . По определению, будучи марковской моделью, HMM имеет дополнительное требование, что результат в момент времени должен быть «подвержен» исключительно влиянию результата в , а результаты и в должны быть условно независимыми от в заданный момент времени . Оценка параметров в HMM может быть выполнена с использованием оценки максимального правдоподобия . Для линейных цепных HMM алгоритм Баума–Велча может быть использован для оценки параметров. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle t=t_{0}}$ ${\displaystyle X}$ ${\displaystyle t=t_{0}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle t<t_{0}}$ ${\displaystyle Y}$ ${\displaystyle t=t_{0}}$ ${\displaystyle X}$ ${\displaystyle t=t_{0}}$

Скрытые марковские модели известны своими приложениями в термодинамике , статистической механике , физике , химии , экономике , финансах , обработке сигналов , теории информации , распознавании образов , таких как речь , ^[1] почерк , распознавание жестов , ^[2] разметка частей речи , отслеживание музыкальной партитуры, ^[3] частичные разряды ^[4] и биоинформатика . ^{[5] [6]}

Определение

Пусть и будут дискретными по времени стохастическими процессами и . Пара является скрытой марковской моделью, если ${\displaystyle X_{n}}$ ${\displaystyle Y_{n}}$ ${\displaystyle n\geq 1}$ ${\displaystyle (X_{n},Y_{n})}$

• ${\displaystyle X_{n}}$является марковским процессом , поведение которого не поддается непосредственному наблюдению («скрыто»);
• ${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{1}=x_{1},\ldots ,X_{n}=x_{n}{\bigr )}=\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{n}=x_{n}{\bigr )}}$,

для каждого , и каждого набора Бореля . ${\displaystyle n\geq 1}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle A}$

Пусть и будут непрерывными во времени стохастическими процессами. Пара является скрытой марковской моделью, если ${\displaystyle X_{t}}$ ${\displaystyle Y_{t}}$ ${\displaystyle (X_{t},Y_{t})}$

• ${\displaystyle X_{t}}$это марковский процесс, поведение которого не поддается непосредственному наблюдению («скрыто»);
• ${\displaystyle \operatorname {\mathbf {P} } (Y_{t_{0}}\in A\mid \{X_{t}\in B_{t}\}_{t\leq t_{0}})=\operatorname {\mathbf {P} } (Y_{t_{0}}\in A\mid X_{t_{0}}\in B_{t_{0}})}$,

для каждого , каждого борелевского множества и каждого семейства борелевских множеств . ${\displaystyle t_{0}}$ ${\displaystyle A}$ ${\displaystyle \{B_{t}\}_{t\leq t_{0}}}$

Терминология

Состояния процесса (соответственно) называются скрытыми состояниями , а (соответственно) называются вероятностью испускания или вероятностью выхода . ${\displaystyle X_{n}}$ ${\displaystyle X_{t})}$ ${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\mid X_{n}=x_{n}{\bigr )}}$ ${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{t}\in A\mid X_{t}\in B_{t}{\bigr )})}$

Примеры

Извлечение шаров из скрытых урн

Рисунок 1. Вероятностные параметры скрытой марковской модели (пример)
X — состояния
y — возможные наблюдения
a — вероятности перехода состояний
b — вероятности выхода

В своей дискретной форме скрытый марковский процесс можно визуализировать как обобщение задачи об урне с заменой (где каждый элемент из урны возвращается в исходную урну перед следующим шагом). ^[7] Рассмотрим такой пример: в комнате, которая не видна наблюдателю, находится джинн. В комнате находятся урны X1, X2, X3, ..., каждая из которых содержит известную смесь шаров, причем каждый шар имеет уникальную метку y1, y2, y3, ... . Джинн выбирает урну в этой комнате и случайным образом вытаскивает шар из этой урны. Затем он кладет шар на конвейерную ленту, где наблюдатель может наблюдать последовательность шаров, но не последовательность урн, из которых они были вытащены. У джинна есть некоторая процедура для выбора урн; выбор урны для n -го шара зависит только от случайного числа и выбора урны для ( n − 1)-го шара. Выбор урны не зависит напрямую от урн, выбранных до этой единственной предыдущей урны; поэтому это называется марковским процессом . Его можно описать верхней частью рисунка 1.

Марковский процесс нельзя наблюдать, только последовательность помеченных шаров, поэтому такое расположение называется скрытым марковским процессом . Это иллюстрирует нижняя часть диаграммы, показанной на рисунке 1, где можно увидеть, что шары y1, y2, y3, y4 могут быть извлечены в каждом состоянии. Даже если наблюдатель знает состав урн и только что наблюдал последовательность из трех шаров, например y1, y2 и y3 на конвейерной ленте, наблюдатель все еще не может быть уверен, из какой урны ( т. е . в каком состоянии) джинн вытащил третий шар. Однако наблюдатель может выработать другую информацию, такую ​​как вероятность того, что третий шар пришел из каждой из урн.

Игра в угадывание погоды

Рассмотрим двух друзей, Алису и Боба, которые живут далеко друг от друга и ежедневно обсуждают по телефону, что они делали в тот день. Боба интересуют только три занятия: прогулки в парке, шопинг и уборка квартиры. Выбор того, что делать, определяется исключительно погодой в данный день. У Алисы нет определенной информации о погоде, но она знает общие тенденции. Основываясь на том, что Боб рассказывает ей о своих ежедневных занятиях, Алиса пытается угадать, какая была погода.

Алиса считает, что погода работает как дискретная цепь Маркова . Есть два состояния, «Дождливо» и «Солнечно», но она не может наблюдать их напрямую, то есть они скрыты от нее. В каждый день есть определенная вероятность того, что Боб выполнит одно из следующих действий, в зависимости от погоды: «прогулка», «шопинг» или «уборка». Поскольку Боб рассказывает Алисе о своих действиях, это и есть наблюдения . Вся система является скрытой марковской моделью (СММ).

Алиса знает общие погодные тенденции в этом районе и то, что Боб любит делать в среднем. Другими словами, параметры HMM известны. Их можно представить следующим образом на Python :

состояния  =  ( "Дождливо" ,  "Солнечно" )наблюдения  =  ( "прогулка" ,  "магазин" ,  "чистка" )start_probability  =  { "Дождливо" :  0,6 ,  "Солнечно" :  0,4 }transition_probability  =  {  "Дождливо" :  { "Дождливо" :  0,7 ,  "Солнечно" :  0,3 },  "Солнечно" :  { "Дождливо" :  0,4 ,  "Солнечно" :  0,6 }, }emit_probability  =  {  "Дождливый" :  { "прогулка" :  0,1 ,  "магазин" :  0,4 ,  "чистый" :  0,5 },  "Солнечный" :  { "прогулка" :  0,6 ,  "магазин" :  0,3 ,  "чистый" :  0,1 }, }

В этом фрагменте кода start_probabilityпредставляет убеждение Алисы о том, в каком состоянии находится HMM, когда Боб впервые звонит ей (все, что она знает, это то, что в среднем идет дождь). Конкретное распределение вероятностей, используемое здесь, не является равновесным, которое (с учетом вероятностей перехода) приблизительно равно {'Rainy': 0.57, 'Sunny': 0.43}. transition_probabilityпредставляет изменение погоды в базовой цепи Маркова. В этом примере существует только 30%-ная вероятность того, что завтра будет солнечно, если сегодня дождливо. emission_probabilityпредставляет вероятность того, что Боб выполнит определенное действие в каждый день. Если идет дождь, есть 50%-ная вероятность того, что он убирается в своей квартире; если солнечно, есть 60%-ная вероятность того, что он гуляет на улице.

Графическое представление данной HMM

Похожий пример более подробно рассмотрен на странице алгоритма Витерби .

Структурная архитектура

На диаграмме ниже показана общая архитектура инстанцированной HMM. Каждая овальная форма представляет собой случайную величину, которая может принимать любое из ряда значений. Случайная величина x ( t ) является скрытым состоянием в момент времени t (с моделью из приведенной выше диаграммы, x ( t ) ∈ { x ₁ , x ₂ , x ₃ }) . Случайная величина y ( t ) является наблюдением в момент времени t (с y ( t ) ∈ { y ₁ , y ₂ , y ₃ , y ₄ }) . Стрелки на диаграмме (часто называемой решетчатой ​​диаграммой ) обозначают условные зависимости.

Из диаграммы видно, что условное распределение вероятностей скрытой переменной x ( t ) в момент времени t , при заданных значениях скрытой переменной x во все моменты времени, зависит только от значения скрытой переменной x ( t − 1 ) ; значения в момент времени t − 2 и ранее не оказывают никакого влияния. Это называется свойством Маркова . Аналогично, значение наблюдаемой переменной y ( t ) зависит только от значения скрытой переменной x ( t ) (оба в момент времени t ).

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

Предполагается, что скрытое пространство состояний состоит из одного из N возможных значений, смоделированных как категориальное распределение. (См. раздел ниже о расширениях для других возможностей.) Это означает, что для каждого из N возможных состояний, в которых может находиться скрытая переменная в момент времени t , существует вероятность перехода из этого состояния в каждое из N возможных состояний скрытой переменной в момент времени , для общего числа вероятностей перехода. Набор вероятностей перехода для переходов из любого заданного состояния должен в сумме давать 1. Таким образом, матрица вероятностей перехода является матрицей Маркова . Поскольку любая вероятность перехода может быть определена, если известны другие, существует общее число параметров перехода. ${\displaystyle t+1}$ ${\displaystyle N^{2}}$ ${\displaystyle N\times N}$ ${\displaystyle N(N-1)}$

Кроме того, для каждого из N возможных состояний существует набор вероятностей эмиссии, управляющих распределением наблюдаемой переменной в определенное время с учетом состояния скрытой переменной в это время. Размер этого набора зависит от природы наблюдаемой переменной. Например, если наблюдаемая переменная дискретна с M возможными значениями, управляемыми категориальным распределением , будут отдельные параметры для общей суммы параметров эмиссии по всем скрытым состояниям. С другой стороны, если наблюдаемая переменная представляет собой M -мерный вектор, распределенный в соответствии с произвольным многомерным гауссовым распределением , будет M параметров, управляющих средними значениями , и параметров, управляющих ковариационной матрицей , для общей суммы параметров эмиссии. (В таком случае, если значение M не мало, может быть более практичным ограничить природу ковариаций между отдельными элементами вектора наблюдения, например, предположив, что элементы независимы друг от друга, или, что менее строго, независимы от всех, кроме фиксированного числа соседних элементов.) ${\displaystyle M-1}$ ${\displaystyle N(M-1)}$ ${\displaystyle {\frac {M(M+1)}{2}}}$ ${\displaystyle N\left(M+{\frac {M(M+1)}{2}}\right)={\frac {NM(M+3)}{2}}=O(NM^{2})}$

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

Вывод

Вероятности перехода состояний и выходов HMM обозначены непрозрачностью линии в верхней части диаграммы. Учитывая, что выходная последовательность наблюдается в нижней части диаграммы, интерес представляет наиболее вероятная последовательность состояний, которая могла бы ее создать. На основе стрелок, присутствующих на диаграмме, следующие последовательности состояний являются кандидатами:
5 3 2 5 3 2
4 3 2 5 3 2 3
1 2 5 3 2
Наиболее вероятную последовательность можно найти, оценив совместную вероятность как последовательности состояний, так и наблюдений для каждого случая (просто умножив значения вероятности, которые здесь соответствуют непрозрачности задействованных стрелок). В общем, этот тип проблемы (т. е. нахождение наиболее вероятного объяснения для последовательности наблюдений) можно эффективно решить с помощью алгоритма Витерби .

Со скрытыми марковскими моделями связано несколько проблем вывода , как описано ниже.

Вероятность наблюдаемой последовательности

Задача состоит в том, чтобы вычислить наилучшим образом, учитывая параметры модели, вероятность конкретной выходной последовательности. Это требует суммирования по всем возможным последовательностям состояний:

Вероятность наблюдения последовательности

${\displaystyle Y=y(0),y(1),\dots ,y(L-1)}$,

длины L определяется как

${\displaystyle P(Y)=\sum _{X}P(Y\mid X)P(X)}$,

где сумма пробегает все возможные последовательности скрытых узлов

${\displaystyle X=x(0),x(1),\dots ,x(L-1)}$.

Применяя принцип динамического программирования , эту задачу также можно эффективно решить с помощью прямого алгоритма .

Вероятность скрытых переменных

В ряде связанных задач рассматривается вероятность одной или нескольких скрытых переменных с учетом параметров модели и последовательности наблюдений . ${\displaystyle y(1),\dots ,y(t)}$

Фильтрация

Задача состоит в том, чтобы вычислить, учитывая параметры модели и последовательность наблюдений, распределение по скрытым состояниям последней скрытой переменной в конце последовательности, т.е. вычислить . Эта задача используется, когда последовательность скрытых переменных рассматривается как базовые состояния, через которые проходит процесс в последовательности точек во времени, с соответствующими наблюдениями в каждой точке. Тогда естественно спросить о состоянии процесса в конце. ${\displaystyle P(x(t)\ |\ y(1),\dots ,y(t))}$

Эту проблему можно эффективно решить с помощью прямого алгоритма . Примером является случай, когда алгоритм применяется к скрытой марковской сети для определения . ${\displaystyle \mathrm {P} {\big (}h_{t}\ |v_{1:t}{\big )}}$

Сглаживание

Это похоже на фильтрацию, но спрашивает о распределении скрытой переменной где-то в середине последовательности, то есть для вычисления некоторого . С точки зрения, описанной выше, это можно рассматривать как распределение вероятностей по скрытым состояниям для момента времени k в прошлом относительно времени t . ${\displaystyle P(x(k)\ |\ y(1),\dots ,y(t))}$ ${\displaystyle k<t}$

Алгоритм «вперед-назад» является хорошим методом вычисления сглаженных значений для всех скрытых переменных состояния.

Наиболее вероятное объяснение

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

Эта задача требует нахождения максимума среди всех возможных последовательностей состояний и может быть эффективно решена с помощью алгоритма Витерби .

Статистическая значимость

Для некоторых из вышеперечисленных проблем также может быть интересно спросить о статистической значимости . Какова вероятность того, что последовательность, взятая из некоторого нулевого распределения, будет иметь вероятность HMM (в случае прямого алгоритма) или максимальную вероятность последовательности состояний (в случае алгоритма Витерби), по крайней мере такую ​​же большую, как и у конкретной выходной последовательности? ^[8] Когда HMM используется для оценки релевантности гипотезы для конкретной выходной последовательности, статистическая значимость указывает на ложноположительный уровень , связанный с невозможностью отвергнуть гипотезу для выходной последовательности.

Обучение

Задача обучения параметров в HMM заключается в том, чтобы найти, учитывая выходную последовательность или набор таких последовательностей, наилучший набор вероятностей перехода состояний и выбросов. Обычно задача состоит в том, чтобы вывести оценку максимального правдоподобия параметров HMM, учитывая набор выходных последовательностей. Неизвестно ни одного поддающегося обработке алгоритма для точного решения этой задачи, но локальное максимальное правдоподобие может быть эффективно получено с помощью алгоритма Баума-Велча или алгоритма Балди-Шовена. Алгоритм Баума-Велча является частным случаем алгоритма максимизации ожидания .

Если HMM используются для прогнозирования временных рядов, более сложные методы байесовского вывода, такие как выборка Монте-Карло с цепями Маркова (MCMC), как доказано, более предпочтительны по сравнению с поиском единственной модели максимального правдоподобия как с точки зрения точности, так и стабильности. ^[9] Поскольку MCMC налагает значительную вычислительную нагрузку, в случаях, когда масштабируемость вычислений также представляет интерес, можно в качестве альтернативы прибегнуть к вариационным приближениям к байесовскому выводу, например ^[10] Действительно, приближенный вариационный вывод обеспечивает вычислительную эффективность, сравнимую с максимизацией ожидания, при этом обеспечивая профиль точности, лишь немного уступающий точному байесовскому выводу типа MCMC.

Приложения

Профиль HMM, моделирующий множественное выравнивание последовательностей белков в Pfam

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

• Вычислительные финансы ^{[11] [12]}
• Кинетический анализ одиночных молекул ^[13]
• Нейробиология ^{[14] [15]}
• Криптоанализ
• Распознавание речи , включая Siri ^[16]
• Синтез речи
• Тегирование частей речи
• Разделение документов в решениях сканирования
• Машинный перевод
• Частичный разряд
• Генное предсказание
• Распознавание рукописного ввода ^[17]
• Выравнивание биопоследовательностей
• Анализ временных рядов
• Распознавание активности
• Сворачивание белка ^[18]
• Классификация последовательностей ^[19]
• Обнаружение метаморфических вирусов ^[20]
• Открытие мотива последовательности (ДНК и белки) ^[21]
• Кинетика гибридизации ДНК ^{[22] [23]}
• Открытие состояния хроматина ^[24]
• Прогнозирование транспорта ^[25]
• Изменчивость солнечного излучения ^{[26] [27] [28]}

История

Скрытые марковские модели были описаны в серии статистических работ Леонарда Э. Баума и других авторов во второй половине 1960-х годов. ^{[29] [30] [31] [32] [33]} Одним из первых применений HMM было распознавание речи , начавшееся в середине 1970-х годов. ^{[34] [35] [36] [37]} С точки зрения лингвистики скрытые марковские модели эквивалентны стохастической регулярной грамматике. ^[38]

Во второй половине 1980-х годов HMM начали применять для анализа биологических последовательностей, ^[39] в частности ДНК . С тех пор они стали повсеместно использоваться в области биоинформатики . ^[40]

Расширения

Общие пространства состояний

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

В настоящее время вывод в скрытых марковских моделях выполняется в непараметрических условиях, где структура зависимости обеспечивает идентифицируемость модели ^[41] , а пределы обучаемости все еще изучаются. ^[42]

Байесовское моделирование вероятностей переходов

Скрытые марковские модели являются генеративными моделями , в которых моделируется совместное распределение наблюдений и скрытых состояний или, что эквивалентно, как априорное распределение скрытых состояний ( вероятности перехода ), так и условное распределение наблюдений с учетом состояний ( вероятности эмиссии ). Вышеуказанные алгоритмы неявно предполагают равномерное априорное распределение по вероятностям перехода. Однако также возможно создавать скрытые марковские модели с другими типами априорных распределений. Очевидным кандидатом, учитывая категориальное распределение вероятностей перехода, является распределение Дирихле , которое является сопряженным априорным распределением категориального распределения. Обычно выбирается симметричное распределение Дирихле, отражающее незнание того, какие состояния по своей сути более вероятны, чем другие. Единственный параметр этого распределения (называемый параметром концентрации ) контролирует относительную плотность или разреженность результирующей матрицы перехода. Выбор 1 дает равномерное распределение. Значения больше 1 приводят к плотной матрице, в которой вероятности перехода между парами состояний, скорее всего, будут почти равны. Значения меньше 1 приводят к разреженной матрице, в которой для каждого заданного исходного состояния только небольшое количество целевых состояний имеют не пренебрежимо малые вероятности перехода. Также можно использовать двухуровневое априорное распределение Дирихле, в котором одно распределение Дирихле (верхнее распределение) управляет параметрами другого распределения Дирихле (нижнее распределение), которое, в свою очередь, управляет вероятностями перехода. Верхнее распределение управляет общим распределением состояний, определяя вероятность возникновения каждого состояния; его параметр концентрации определяет плотность или разреженность состояний. Такое двухуровневое априорное распределение, в котором оба параметра концентрации установлены для получения разреженных распределений, может быть полезным, например, при неконтролируемой разметке частей речи , где некоторые части речи встречаются гораздо чаще других; алгоритмы обучения, которые предполагают равномерное априорное распределение, как правило, плохо справляются с этой задачей. Параметры моделей такого рода с неравномерными априорными распределениями можно узнать с помощью выборки Гиббса или расширенных версий алгоритма максимизации ожидания .

Расширение ранее описанных скрытых марковских моделей с априорными распределениями Дирихле использует процесс Дирихле вместо распределения Дирихле. Этот тип модели допускает неизвестное и потенциально бесконечное число состояний. Обычно используется двухуровневый процесс Дирихле, аналогичный ранее описанной модели с двумя уровнями распределений Дирихле. Такая модель называется иерархической скрытой марковской моделью процесса Дирихле , или сокращенно HDP-HMM . Первоначально она была описана под названием «Бесконечная скрытая марковская модель» ^[43] и была далее формализована в «Иерархических процессах Дирихле». ^[44]

Дискриминационный подход

Другой тип расширения использует дискриминативную модель вместо генеративной модели стандартных HMM. Этот тип модели напрямую моделирует условное распределение скрытых состояний с учетом наблюдений, а не моделирует совместное распределение. Примером этой модели является так называемая модель Маркова с максимальной энтропией (MEMM), которая моделирует условное распределение состояний с использованием логистической регрессии (также известная как « модель с максимальной энтропией »). Преимущество этого типа модели заключается в том, что можно моделировать произвольные признаки (т. е. функции) наблюдений, что позволяет вводить в модель знания, специфичные для конкретной области, о рассматриваемой проблеме. Модели такого рода не ограничиваются моделированием прямых зависимостей между скрытым состоянием и связанным с ним наблюдением; скорее, признаки близлежащих наблюдений, комбинации соответствующего наблюдения и близлежащих наблюдений или фактически произвольные наблюдения на любом расстоянии от заданного скрытого состояния могут быть включены в процесс, используемый для определения значения скрытого состояния. Более того, нет необходимости, чтобы эти признаки были статистически независимы друг от друга, как это было бы в случае использования таких признаков в генеративной модели. Наконец, можно использовать произвольные признаки по парам смежных скрытых состояний вместо простых вероятностей перехода. Недостатки таких моделей: (1) Типы априорных распределений, которые можно разместить на скрытых состояниях, серьезно ограничены; (2) Невозможно предсказать вероятность увидеть произвольное наблюдение. Это второе ограничение часто не является проблемой на практике, поскольку многие общие применения HMM не требуют таких предсказательных вероятностей.

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

Другие расширения

Еще одним вариантом является факторная скрытая марковская модель , которая позволяет обуславливать одно наблюдение соответствующими скрытыми переменными набора независимых марковских цепей, а не одной марковской цепи. Она эквивалентна одной HMM с состояниями (предполагая, что для каждой цепи есть состояния), и поэтому обучение в такой модели затруднено: для последовательности длины простой алгоритм Витерби имеет сложность . Чтобы найти точное решение, можно использовать алгоритм дерева соединений, но это приводит к сложности. На практике можно использовать приближенные методы, такие как вариационные подходы. ^[45] ${\displaystyle K}$ ${\displaystyle N^{K}}$ ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle O(N^{2K}\,T)}$ ${\displaystyle O(N^{K+1}\,K\,T)}$

Все вышеперечисленные модели могут быть расширены для учета более отдаленных зависимостей между скрытыми состояниями, например, позволяя данному состоянию зависеть от предыдущих двух или трех состояний, а не от одного предыдущего состояния; т. е. вероятности перехода расширены для охвата наборов из трех или четырех смежных состояний (или в общем случае смежных состояний). Недостатком таких моделей является то, что алгоритмы динамического программирования для их обучения имеют время выполнения для смежных состояний и общих наблюдений (т. е. длина цепи Маркова). Это расширение широко использовалось в биоинформатике , при моделировании последовательностей ДНК . ${\displaystyle K}$ ${\displaystyle O(N^{K}\,T)}$ ${\displaystyle K}$ ${\displaystyle T}$ ${\displaystyle T}$

Другим недавним расширением является модель триплета Маркова ^[46] , в которой вспомогательный базовый процесс добавляется для моделирования некоторых особенностей данных. Было предложено много вариантов этой модели. Следует также упомянуть интересную связь, которая была установлена ​​между теорией доказательств и моделями триплета Маркова ^[47] , и которая позволяет объединять данные в марковском контексте ^[48] и моделировать нестационарные данные. ^{[49] [50]} Альтернативные стратегии объединения многопоточных данных также были предложены в недавней литературе, например, ^[51]

Наконец, в 2012 году было предложено другое обоснование для решения проблемы моделирования нестационарных данных с помощью скрытых марковских моделей. ^[52] Оно заключается в использовании небольшой рекуррентной нейронной сети (RNN), в частности, резервуарной сети, ^[53] для захвата эволюции временной динамики в наблюдаемых данных. Эта информация, закодированная в форме многомерного вектора, используется в качестве условной переменной вероятностей перехода состояний HMM. При такой настройке в конечном итоге получается нестационарная HMM, вероятности перехода которой развиваются со временем таким образом, который выводится из данных, в отличие от некоторой нереалистичной ad-hoc модели временной эволюции.

В 2023 году были представлены два инновационных алгоритма для скрытой марковской модели. Эти алгоритмы позволяют вычислять апостериорное распределение HMM без необходимости явного моделирования совместного распределения, используя только условные распределения. ^{[54] [55]} В отличие от традиционных методов, таких как алгоритмы «вперед-назад» и Витерби, которые требуют знания совместного закона HMM и могут быть вычислительно интенсивными для обучения, дискриминационные алгоритмы «вперед-назад» и «дискриминационный алгоритм Витерби» обходят необходимость в законе наблюдения. ^{[56] [57]} Этот прорыв позволяет применять HMM в качестве дискриминационной модели, предлагая более эффективный и универсальный подход к использованию скрытых марковских моделей в различных приложениях.

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

Теория меры

Скрытая часть скрытой марковской модели, наблюдаемые состояния которой немарковские.

При наличии матрицы перехода Маркова и инвариантного распределения на состояниях вероятностная мера может быть наложена на множество подсдвигов. Например, рассмотрим цепь Маркова, заданную слева на состояниях , с инвариантным распределением . Игнорируя различие между , это пространство подсдвигов проецируется на в другое пространство подсдвигов на , и эта проекция также проецирует вероятностную меру вниз до вероятностной меры на подсдвиги на . ${\displaystyle A,B_{1},B_{2}}$ ${\displaystyle \pi =(2/7,4/7,1/7)}$ ${\displaystyle B_{1},B_{2}}$ ${\displaystyle A,B_{1},B_{2}}$ ${\displaystyle A,B}$ ${\displaystyle A,B}$

Любопытно, что вероятностная мера на подсдвиги на не создается цепью Маркова на , даже не несколькими порядками. Интуитивно это происходит потому, что если наблюдать длинную последовательность , то становится все более и более уверенным, что , что означает, что наблюдаемая часть системы может быть затронута чем-то бесконечно в прошлом. ^{[60] [61]} ${\displaystyle A,B}$ ${\displaystyle A,B}$ ${\displaystyle B^{n}}$ ${\displaystyle Pr(A|B^{n})\to {\frac {2}{3}}}$

Наоборот, существует пространство подсдвигов на 6 символах, проецируемое на подсдвиги на 2 символах, такое, что любая марковская мера на меньшем подсдвиге имеет прообразную меру, которая не является марковской ни одного порядка (пример 2.6 ^[61] ).

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

• Андрей Марков
• Алгоритм Баума-Велча
• Байесовский вывод
• Байесовское программирование
• Ричард Джеймс Бойз
• Условное случайное поле
• Теория оценки
• HH-suite (HHpred, HHsearch) бесплатный сервер и программное обеспечение для поиска белковых последовательностей
• HMMER , бесплатная программа скрытой марковской модели для анализа последовательности белка
• Скрытая модель Бернулли
• Скрытая полумарковская модель
• Иерархическая скрытая марковская модель
• Многослойная скрытая марковская модель
• Последовательная динамическая система
• Стохастическая контекстно-свободная грамматика
• Анализ временных рядов
• Марковская модель переменного порядка
• Алгоритм Витерби

Ссылки

1. «Google Академия».
2. Тэд Старнер, Алекс Пентланд. Визуальное распознавание американского языка жестов в реальном времени на видео с использованием скрытых марковских моделей. Магистерская работа, Массачусетский технологический институт, февраль 1995 г., программа по медиаискусству
3. Б. Пардо и В. Бирмингем. Форма моделирования для онлайн-слежения за музыкальными выступлениями. Архивировано 06.02.2012 в Wayback Machine . AAAI-05 Proc., июль 2005 г.
4. Сатиш Л., Гурурадж Б.И. (апрель 2003 г.). «Использование скрытых марковских моделей для классификации моделей частичных разрядов». Труды IEEE по диэлектрикам и электроизоляции .
5. Ли, Н; Стивенс, М (декабрь 2003 г.). «Моделирование неравновесия сцепления и выявление точек рекомбинации с использованием данных однонуклеотидного полиморфизма». Генетика . 165 (4): 2213–33. doi :10.1093/genetics/165.4.2213. PMC 1462870 . PMID  14704198. 
6. Эрнст, Джейсон; Келлис, Манолис (март 2012 г.). «ChromHMM: автоматическое обнаружение и характеристика состояния хроматина». Nature Methods . 9 (3): 215–216. doi :10.1038/nmeth.1906. PMC 3577932 . PMID  22373907. 
7. Лоуренс Р. Рабинер (февраль 1989 г.). «Учебник по скрытым марковским моделям и избранным приложениям в распознавании речи» (PDF) . Труды IEEE . 77 (2): 257–286. CiteSeerX 10.1.1.381.3454 . doi :10.1109/5.18626. S2CID  13618539. [1]
8. Ньюберг, Л. (2009). "Статистика ошибок скрытой модели Маркова и результаты скрытой модели Больцмана". BMC Bioinformatics . 10 : 212. doi : 10.1186/1471-2105-10-212 . PMC 2722652. PMID  19589158 . 
9. Сипос, И. Роберт. Параллельная стратифицированная выборка MCMC AR-HMM для стохастического прогнозирования временных рядов . В: Труды 4-й Международной конференции по методам стохастического моделирования и анализу данных с семинаром по демографии (SMTDA2016), стр. 295-306. Валлетта, 2016. PDF
10. Chatzis, Sotirios P.; Kosmopoulos, Dimitrios I. (2011). "Вариационная байесовская методология для скрытых марковских моделей с использованием смесей Стьюдента" (PDF) . Pattern Recognition . 44 (2): 295–306. Bibcode :2011PatRe..44..295C. CiteSeerX 10.1.1.629.6275 . doi :10.1016/j.patcog.2010.09.001. Архивировано из оригинала (PDF) 2011-04-01 . Получено 2018-03-11 . 
11. Сипос, И. Роберт; Сеффер, Аттила; Левендовский, Янош (2016). «Параллельная оптимизация разреженных портфелей с помощью AR-HMM». Вычислительная экономика . 49 (4): 563–578. doi : 10.1007/s10614-016-9579-y. S2CID  61882456.
12. Петропулос, Анастасиос; Чатзис, Сотириос П.; Ксантопулос, Стилианос (2016). «Новая система корпоративного кредитного рейтинга на основе скрытых марковских моделей Стьюдента». Экспертные системы с приложениями . 53 : 87–105. doi :10.1016/j.eswa.2016.01.015.
13. Николаи, Кристофер (2013). «Решение кинетики ионных каналов с помощью программного обеспечения QuB». Biophysical Reviews and Letters . 8 (3n04): 191–211. doi :10.1142/S1793048013300053.
14. Хиггинс, Кэмерон; Видаурре, Диего; Коллинг, Нильс; Лю, Юньчжэ; Беренс, Тим; Вулрич, Марк (2022). «Пространственно-временной разрешенный многомерный анализ паттернов для М/ЭЭГ». Картирование человеческого мозга . 43 (10): 3062–3085. doi :10.1002/hbm.25835. PMC 9188977. PMID 35302683  . 
15. Diomedi, S.; Vaccari, FE; Galletti, C.; Hadjidimitrakis, K.; Fattori, P. (2021-10-01). «Динамика нейронов, подобная моторной, в двух теменных областях во время вытягивания руки». Progress in Neurobiology . 205 : 102116. doi : 10.1016/j.pneurobio.2021.102116. hdl : 11585/834094 . ISSN  0301-0082. PMID  34217822. S2CID  235703641.
16. Домингос, Педро (2015). Верховный алгоритм: как поиски совершенной обучающейся машины изменят наш мир . Basic Books. стр. 37. ISBN 9780465061921.
17. Кунду, Амлан, Ян Хе и Парамвир Бахл. «Распознавание рукописного слова: подход на основе скрытых марковских моделей первого и второго порядка ^{[ мертвая ссылка ]} ». Распознавание образов 22.3 (1989): 283-297.
18. Stigler, J.; Ziegler, F.; Gieseke, A.; Gebhardt, JCM; Rief, M. (2011). «Сложная складчатая сеть отдельных молекул кальмодулина». Science . 334 (6055): 512–516. Bibcode :2011Sci...334..512S. doi :10.1126/science.1207598. PMID  22034433. S2CID  5502662.
19. Блазиак, С.; Рангвала, Х. (2011). «Скрытый вариант марковской модели для классификации последовательностей». Труды IJCAI — Международная совместная конференция по искусственному интеллекту . 22 : 1192.
20. Вонг, В.; Стэмп, М. (2006). «Охота на метаморфические двигатели». Журнал компьютерной вирусологии . 2 (3): 211–229. doi :10.1007/s11416-006-0028-7. S2CID  8116065.
21. Вонг, К. -С.; Чан, Т. -М.; Пэн, К.; Ли, И.; Чжан, З. (2013). «Выяснение мотива ДНК с использованием распространения убеждений». Nucleic Acids Research . 41 (16): e153. doi :10.1093/nar/gkt574. PMC 3763557. PMID  23814189 . 
22. Шах, Шалин; Дубей, Абишек К.; Рейф, Джон (2019-05-17). «Улучшенное оптическое мультиплексирование с временными ДНК-штрихкодами». ACS Synthetic Biology . 8 (5): 1100–1111. doi :10.1021/acssynbio.9b00010. PMID  30951289. S2CID  96448257.
23. Шах, Шалин; Дубей, Абишек К.; Рейф, Джон (2019-04-10). «Программирование временных ДНК-штрихкодов для снятия отпечатков пальцев с одной молекулы». Nano Letters . 19 (4): 2668–2673. Bibcode : 2019NanoL..19.2668S. doi : 10.1021/acs.nanolett.9b00590. ISSN  1530-6984. PMID  30896178. S2CID  84841635.
24. "ChromHMM: Открытие и характеристика состояния хроматина". compbio.mit.edu . Получено 01.08.2018 .
25. Эль Зарви, Фераз (май 2011 г.). «Моделирование и прогнозирование эволюции предпочтений с течением времени: скрытая марковская модель поведения при поездках». arXiv : 1707.09133 [stat.AP].
26. Морф, Х. (февраль 1998 г.). «Стохастическая модель солнечного излучения с двумя состояниями (STSIM)». Solar Energy . 62 (2): 101–112. Bibcode :1998SoEn...62..101M. doi :10.1016/S0038-092X(98)00004-8.
27. Мункхаммар, Дж.; Виден, Дж. (август 2018 г.). «Подход к индексу ясного неба на основе распределения вероятностей с использованием смеси марковских цепей». Солнечная энергия . 170 : 174–183. Bibcode : 2018SoEn..170..174M. doi : 10.1016/j.solener.2018.05.055. S2CID  125867684.
28. Мункхаммар, Дж.; Виден, Дж. (октябрь 2018 г.). «Модель распределения смеси цепей Маркова с N-состояниями индекса ясного неба». Солнечная энергия . 173 : 487–495. Bibcode : 2018SoEn..173..487M. doi : 10.1016/j.solener.2018.07.056. S2CID  125538244.
29. Баум, Л. Э.; Петри, Т. (1966). «Статистический вывод для вероятностных функций конечных цепей Маркова». Анналы математической статистики . 37 (6): 1554–1563. doi : 10.1214/aoms/1177699147 .
30. Baum, LE; Eagon, JA (1967). "Неравенство с приложениями к статистической оценке вероятностных функций марковских процессов и к модели для экологии". Бюллетень Американского математического общества . 73 (3): 360. doi : 10.1090/S0002-9904-1967-11751-8 . Zbl  0157.11101.
31. Baum, LE; Sell, GR (1968). «Преобразования роста для функций на многообразиях». Pacific Journal of Mathematics . 27 (2): 211–227. doi : 10.2140/pjm.1968.27.211 .
32. Baum, LE ; Petrie, T.; Soules, G.; Weiss, N. (1970). «Метод максимизации, встречающийся в статистическом анализе вероятностных функций цепей Маркова». Анналы математической статистики . 41 (1): 164–171. doi : 10.1214/aoms/1177697196 . JSTOR  2239727. MR  0287613. Zbl  0188.49603.
33. Баум, Л. Э. (1972). «Неравенство и связанный с ним метод максимизации в статистической оценке вероятностных функций марковского процесса». Неравенства . 3 : 1–8.
34. Бейкер, Дж. (1975). «Система DRAGON — обзор». Труды IEEE по акустике, речи и обработке сигналов . 23 : 24–29. doi :10.1109/TASSP.1975.1162650.
35. Jelinek, F.; Bahl, L.; Mercer, R. (1975). «Разработка лингвистического статистического декодера для распознавания непрерывной речи». Труды IEEE по теории информации . 21 (3): 250. doi :10.1109/TIT.1975.1055384.
36. Xuedong Huang ; M. Jack; Y. Ariki (1990). Скрытые марковские модели для распознавания речи . Издательство Эдинбургского университета. ISBN 978-0-7486-0162-2.
37. Xuedong Huang ; Alex Acero; Hsiao-Wuen Hon (2001). Обработка устной речи . Prentice Hall. ISBN 978-0-13-022616-7.
38. Карраско, Рафаэль К.; Онсина, Хосе (1994). Карраско, Рафаэль К.; Онсина, Хосе (ред.). «Изучение стохастических регулярных грамматик с помощью метода слияния состояний». Грамматический вывод и приложения . Берлин, Гейдельберг: Springer: 139–152. doi :10.1007/3-540-58473-0_144. ISBN 978-3-540-48985-6.
39. М. Бишоп и Э. Томпсон (1986). «Выравнивание последовательностей ДНК с максимальным правдоподобием». Журнал молекулярной биологии . 190 (2): 159–165. doi :10.1016/0022-2836(86)90289-5. PMID  3641921. (требуется подписка)
40. Дурбин, Ричард М .; Эдди, Шон Р.; Крог , Андерс ; Митчисон, Грэм (1998), Анализ биологических последовательностей: вероятностные модели белков и нуклеиновых кислот (1-е изд.), Кембридж, Нью-Йорк: Cambridge University Press , ISBN 0-521-62971-3, OCLC  593254083
41. Гассья, Э.; Клейнен, А.; Робин, С. (2016-01-01). "Вывод в непараметрических скрытых марковских моделях с конечным пространством состояний и их применение". Статистика и вычисления . 26 (1): 61–71. doi :10.1007/s11222-014-9523-8. ISSN  1573-1375.
42. Абрахам, Квеку; Гассиат, Элизабет; Нолет, Захари (март 2023 г.). «Фундаментальные ограничения для изучения скрытых параметров марковской модели». Труды IEEE по теории информации . 69 (3): 1777–1794. arXiv : 2106.12936 . doi : 10.1109/TIT.2022.3213429. ISSN  0018-9448.
43. Бил, Мэтью Дж., Зубин Гахрамани и Карл Эдвард Расмуссен. «Бесконечная скрытая марковская модель». Достижения в области нейронных систем обработки информации 14 (2002): 577-584.
44. Тех, Йи Уай и др. «Иерархические процессы Дирихле». Журнал Американской статистической ассоциации 101.476 (2006).
45. Гахрамани, Зубин ; Джордан, Майкл И. (1997). «Факторные скрытые марковские модели». Машинное обучение . 29 (2/3): 245–273. doi : 10.1023/A:1007425814087 .
46. Печинский, Войцех (2002). «Тройня Шаин де Марков» (PDF) . Comptes Rendus Mathématique . 335 (3): 275–278. дои : 10.1016/S1631-073X(02)02462-7.
47. Печински, Войцех (2007). «Мультисенсорные триплетные цепи Маркова и теория доказательств». Международный журнал приближенного рассуждения . 45 : 1–16. doi : 10.1016/j.ijar.2006.05.001 .
48. Бударен и др. Архивировано 11 марта 2014 г. в Wayback Machine , MY Boudaren, E. Monfrini, W. Pieczynski и A. Aissani, Слияние сигналов нескольких датчиков Демпстера-Шейфера в нестационарном марковском контексте, EURASIP Journal on Advances in Signal Processing, № 134, 2012.
49. Ланчантин и др., П. Ланчантин и В. Печински, Неконтролируемое восстановление скрытой нестационарной цепи Маркова с использованием доказательных априорных данных, Труды IEEE по обработке сигналов, т. 53, № 8, стр. 3091-3098, 2005.
50. Бударен и др., MY Бударен, Э. Монфрини и В. Печински, Неконтролируемая сегментация случайных дискретных данных, скрытых с помощью распределения шума переключения, IEEE Signal Processing Letters, т. 19, № 10, стр. 619-622, октябрь 2012 г.
51. Сотириос П. Хатзис, Димитриос Космопулос, «Визуальное распознавание рабочего процесса с использованием вариационной байесовской обработки многопотоковых объединенных скрытых марковских моделей», IEEE Transactions on Circuits and Systems for Video Technology, т. 22, № 7, стр. 1076-1086, июль 2012 г.
52. Chatzis, Sotirios P.; Demiris, Yiannis (2012). "Нестационарная скрытая марковская модель, управляемая резервуаром". Pattern Recognition . 45 (11): 3985–3996. Bibcode :2012PatRe..45.3985C. doi :10.1016/j.patcog.2012.04.018. hdl : 10044/1/12611 .
53. М. Лукошевичус, Х. Йегер (2009) Подходы к рекуррентному обучению нейронных сетей на основе резервуарных вычислений, Computer Science Review 3 : 127–149.
54. Азераф, Э., Монфрини, Э. и Печински, В. (2023). Эквивалентность между LC-CRF и HMM и дискриминативное вычисление MPM и MAP на основе HMM. Алгоритмы, 16(3), 173.
55. Азераф, Э., Монфрини, Э., Виньон, Э. и Печинский, В. (2020). Скрытые цепи Маркова, энтропийный перенос вперед-назад и разметка частей речи. Препринт arXiv arXiv:2005.10629.
56. Азераф, Э., Монфрини, Э. и Печински, В. (2022). Выведение дискриминантных классификаторов из генеративных моделей. Препринт arXiv arXiv:2201.00844.
57. Нг, А. и Джордан, М. (2001). О дискриминативных и генеративных классификаторах: сравнение логистической регрессии и наивного байеса. Достижения в области нейронных систем обработки информации, 14.
58. Wiggins, LM (1973). Анализ панели: модели скрытой вероятности для процессов отношения и поведения . Амстердам: Elsevier.
59. Бартолуччи, Ф.; Фаркомени, А.; Пеннони, Ф. (2013). Латентные марковские модели для продольных данных. Бока-Ратон: Chapman and Hall/CRC. ISBN 978-14-3981-708-7.
60. Софикские меры: характеристики скрытых цепей Маркова с помощью линейной алгебры, формальных языков и символической динамики - Карл Петерсен, Математика 210, весна 2006 г., Университет Северной Каролины в Чапел-Хилл
61. Бойл, Майк; Петерсен, Карл (2010-01-13), Скрытые марковские процессы в контексте символической динамики , arXiv : 0907.1858

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

Концепции

• Teif, VB; Rippe, K. (2010). "Статистически–механические решеточные модели для связывания белка и ДНК в хроматине". J. Phys.: Condens. Matter . 22 (41): 414105. arXiv : 1004.5514 . Bibcode :2010JPCM...22O4105T. doi :10.1088/0953-8984/22/41/414105. PMID  21386588. S2CID  103345.
• Познавательное введение в скрытые марковские модели, Марк Стэмп, Университет штата Сан-Хосе.
• Подгонка HMM с максимизацией ожиданий – полный вывод
• Пошаговое руководство по HMM. Архивировано 13 августа 2017 г. в Wayback Machine (Университет Лидса)
• Скрытые Марковские модели (изложение с использованием базовой математики)
• Скрытые марковские модели (Нарада Варакагода)
• Скрытые Марковские модели: основы и приложения Часть 1, Часть 2 (В. Петрушин)
• Лекция Джейсона Эйснера об электронных таблицах, видео и интерактивные электронные таблицы