Скрытая марковская модель (HMM ) - это статистическая марковская модель, в которой система, моделируемая, предполагается марковским процессом - назовите это - с ненаблюдаемыми («скрытыми») состояниями. HMM предполагает, что существует другой процесс , поведение которого «зависит» от . Цель состоит в том, чтобы узнать о , наблюдая за . HMM устанавливает, что для каждого временного интервала условное распределение вероятностей с учетом истории должен не зависеть от
Скрытые марковские модели известны своим применением в термодинамике, статистической механике, физика, химия, экономика, финансы, обработка сигналов, теория информации, распознавание образов - например, речь, рукописный ввод, распознавание жестов, тегирование части речи, музыкальное сопровождение, частичные разряды и биоинформатика.
Пусть и быть дискретными случайными процессами и . Пара является скрытой марковской моделью, если
для каждого и произвольный (измеримый ) набор .
Состояния процесса называются скрытыми состояниями, а называется вероятностью выброса или вероятностью выхода.
В своей дискретной форме скрытый марковский процесс может быть визуализирован как обобщение проблемы урны с заменой (где каждый элемент из урны вернулся в исходную урну перед следующим шагом). Рассмотрим такой пример: в комнате, невидимой для наблюдателя, находится джинн. В комнате находятся урны X1, X2, X3,..., каждая из которых содержит известную смесь шаров, каждый шар помечен как y1, y2, y3,.... Джинн выбирает урну в этой комнате и случайным образом вытаскивает из нее шар. Затем он помещает мяч на конвейерную ленту, где наблюдатель может наблюдать последовательность шаров, но не последовательность урн, из которых они были извлечены. У джинна есть процедура выбора урн; выбор урны для n-го шара зависит только от случайного числа и выбора урны для (n - 1) -го шара. Выбор урны не зависит напрямую от урн, выбранных перед этой единственной предыдущей урной; поэтому это называется марковским процессом. Его можно описать с помощью верхней части рисунка 1.
Сам марковский процесс нельзя наблюдать, только последовательность помеченных шаров, поэтому такое расположение называется «скрытым марковским процессом». Это иллюстрируется нижней частью диаграммы, показанной на рисунке 1, где видно, что шары y1, y2, y3, y4 могут быть нарисованы в каждом состоянии. Даже если наблюдатель знает состав урн и только что наблюдал последовательность из трех шаров, например y1, y2 и y3 на конвейерной ленте, наблюдатель все еще не может быть уверен, из какой урны (т.е.в каком состоянии) джинн вытащил третий шар. Однако наблюдатель может получить другую информацию, например, вероятность того, что третий шар попал из каждой урны.
Рассмотрим двух друзей, Алису и Боба, которые живут далеко друг от друга и ежедневно обсуждают по телефону, что они сделали в тот день. Боба интересуют только три занятия: прогулки в парке, покупки и уборка в квартире. Выбор того, чем заняться, определяется исключительно погодой в данный день. Алиса не имеет точной информации о погоде, но знает общие тенденции. Основываясь на том, что Боб говорит ей, что он делал каждый день, Алиса пытается угадать, какой должна была быть погода.
Алиса считает, что погода действует как дискретная цепь Маркова. Есть два состояния: «Дождливый» и «Солнечный», но она не может наблюдать их напрямую, то есть они скрыты от нее. Каждый день есть определенная вероятность, что Боб будет выполнять одно из следующих действий, в зависимости от погоды: «гулять», «делать покупки» или «убирать». Поскольку Боб рассказывает Алисе о своей деятельности, это и есть наблюдения. Вся система представляет собой скрытую марковскую модель (HMM).
Алиса знает общие погодные тенденции в этом районе и то, что Боб любит делать в среднем. Другими словами, параметры HMM известны. Они могут быть представлены следующим образом в Python :
states = ('Rainy', 'Sunny') monitoring = ('walk,' shop ',' clean ') start_probability = {' Rainy ': 0.6,' Солнечный ': 0,4} transition_probability = {' Rainy ': {' Rainy ': 0,7,' Sunny ': 0,3},' Sunny ': {' Rainy ': 0,4,' Sunny ': 0,6},} selection_probability = {' Rainy ': {' прогулка ': 0,1,' магазин ': 0,4,' очистка ': 0,5},' солнечный ': {' прогулка ': 0,6,' магазин ': 0,3,' очистка ': 0,1},}
В этом фрагменте кода start_probability
представляет мнение Алисы о том, в каком состоянии находится HMM, когда Боб впервые звонит ей (все, что она знает, это то, что в среднем обычно бывает дождливо). Используемое здесь конкретное распределение вероятностей не является равновесным, которое (с учетом вероятностей перехода) составляет приблизительно {'Rainy': 0,57, 'Sunny': 0,43}
. transition_probability
представляет изменение погоды в основной цепи Маркова. В этом примере вероятность того, что завтра будет солнечным, составляет всего 30%, если сегодня дождливый день. вероятность_выпуска
показывает, насколько вероятно, что Боб будет выполнять определенное действие каждый день. Если идет дождь, вероятность того, что он убирает свою квартиру, составляет 50%; если на улице солнечно, то с вероятностью 60% он выйдет на прогулку.
Аналогичный пример более подробно рассматривается на странице алгоритм Витерби.
На схеме ниже показана общая архитектура созданного экземпляра HMM. Каждая овальная форма представляет собой случайную переменную, которая может принимать любое из ряда значений. Случайная величина x (t) - это скрытое состояние в момент времени t (с моделью из приведенной выше диаграммы, x (t) ∈ {x 1, x 2, x 3 }). Случайная величина y (t) - это наблюдение в момент времени t (при y (t) ∈ {y 1, y 2, y 3, y 4 }). Стрелки на диаграмме (часто называемой решетчатой диаграммой ) обозначают условные зависимости.
Из диаграммы ясно, что условное распределение вероятностей скрытой переменной x (t) в момент времени t, учитывая постоянные значения скрытой переменной x, зависит только от от значения скрытой переменной x (t - 1); значения в момент времени t - 2 и ранее не влияют. Это называется марковским свойством. Точно так же значение наблюдаемой переменной y (t) зависит только от значения скрытой переменной x (t) (оба в момент времени t).
В рассматриваемом здесь стандартном типе скрытой марковской модели пространство состояний скрытых переменных является дискретным, в то время как сами наблюдения могут быть дискретными (обычно генерируются из категориального распределения ) или непрерывный (обычно из распределения Гаусса ). Параметры скрытой марковской модели бывают двух типов: вероятности перехода и вероятности выбросов (также известные как вероятности выхода). Вероятности перехода определяют способ выбора скрытого состояния в момент времени t с учетом скрытого состояния в момент времени .
Предполагается, что скрытое пространство состояний состоит из одного из N возможных значений., смоделированный как категориальное распределение. (См. Раздел о расширениях ниже, чтобы узнать о других возможностях.) Это означает, что для каждого из N возможных состояний, в которых может находиться скрытая переменная в момент времени t, существует вероятность перехода из этого состояния в каждое из N возможных состояний скрытая переменная во время , всего вероятностей перехода. Обратите внимание, что набор вероятностей перехода для переходов из любого данного состояния должен быть суммирован до 1. Таким образом, матрица вероятностей переходов является Марковская матрица. Поскольку любая вероятность перехода может быть определена после того, как известны другие, существует всего параметров перехода.
Кроме того, для каждого из N возможных состояний существует набор вероятностей выбросов, управляющих распределением наблюдаемой переменной в конкретный момент времени с учетом состояния скрытой переменной в это время. Размер этого набора зависит от природы наблюдаемой переменной. Например, если наблюдаемая переменная дискретна с M возможными значениями, регулируемыми категориальным распределением, будет отдельных параметров., всего параметров излучения для всех скрытых состояний. С другой стороны, если наблюдаемая переменная является M-мерным вектором, распределенным согласно произвольному многомерному распределению Гаусса, будут M параметров, управляющих средними и параметров, управляющих ковариационной матрицей, всего параметры выбросов. (В таком случае, если значение M не является небольшим, может быть более практичным ограничить характер ковариаций между отдельными элементами вектора наблюдения, например, предположив, что элементы независимы друг от друга, или менее ограничительно, независимы от всех, кроме фиксированного числа смежных элементов.)
Некоторые проблемы вывода связаны со скрытыми марковскими моделями, так как изложены ниже.
Задача состоит в том, чтобы вычислить наилучшим образом с учетом параметров модели вероятность конкретной выходной последовательности. Для этого требуется суммирование по всем возможным последовательностям:
Вероятность наблюдения последовательности
длины L задается как
где сумма вычисляется по всем возможным последовательностям скрытых узлов
Применяя принцип динамического программирования, эта проблема тоже может эффективно обрабатываться с помощью прямого алгоритма.
В ряде связанных задач задается вопрос о вероятности одной или нескольких скрытых переменных с учетом параметров модели и последовательности наблюдения
Задача состоит в том, чтобы вычислить, учитывая параметры модели и последовательность наблюдений, распределение по скрытым состояниям последняя скрытая переменная в конце последовательности, то есть для вычисления . Эта задача обычно используется, когда последовательность скрытых переменных рассматривается как базовые состояния, через которые процесс проходит в последовательности моментов времени, с соответствующими наблюдениями в каждый момент времени. Затем естественно спросить о состоянии процесса в конце.
Эту проблему можно эффективно решить с помощью прямого алгоритма.
Это похоже на фильтрацию, но спрашивает о распределении скрытой переменной где-то в середине последовательности, то есть для вычисления для некоторого
алгоритм прямого-обратного - хороший метод для вычисления сглаженных значений для всех скрытых переменных состояния.
Задача, в отличие от двух предыдущих, спрашивает о совместной вероятности всей последовательности скрытых состояний, которые породили определенную последовательность наблюдений (см. иллюстрацию справа). Эта задача обычно применима, когда HMM применяются к разным типам задач, нежели те, для которых применимы задачи фильтрации и сглаживания. Примером является тегирование части речи, где скрытые состояния представляют лежащие в основе части речи, соответствующие наблюдаемой последовательности слов. В этом случае интерес представляет собой всю последовательность частей речи, а не просто часть речи для отдельного слова, как при фильтрации или сглаживании.
Эта задача требует нахождения максимума по всем возможным последовательностям и может быть эффективно решена с помощью алгоритма Витерби.
Для некоторых из вышеперечисленных проблем это может Также будет интересно спросить о статистической значимости. Какова вероятность того, что последовательность, полученная из некоторого нулевого распределения, будет иметь вероятность HMM (в случае прямого алгоритма) или максимальную вероятность последовательности состояний (в случае алгоритма Витерби), по крайней мере, как большой, как у конкретной выходной последовательности? Когда HMM используется для оценки релевантности гипотезы для конкретной выходной последовательности, статистическая значимость указывает на частоту ложных срабатываний, связанную с неспособностью отклонить гипотезу для выходной последовательности.
Задача изучения параметров в HMM состоит в том, чтобы найти, учитывая выходную последовательность или набор таких последовательностей, лучший набор вероятностей перехода между состояниями и выбросов. Задача обычно состоит в том, чтобы получить оценку максимального правдоподобия параметров HMM с учетом набора выходных последовательностей. Неизвестно ни одного поддающегося обработке алгоритма для точного решения этой проблемы, но локальное максимальное правдоподобие может быть эффективно получено с использованием алгоритма Баума – Велча или алгоритма Бальди – Шовена. Алгоритм Баума – Велча является частным случаем алгоритма максимизации ожидания. Если HMM используются для прогнозирования временных рядов, более сложные методы байесовского вывода, такие как выборка методом Монте-Карло (MCMC), являются более предпочтительными по сравнению с поиском единой модели максимального правдоподобия как с точки зрения точности, так и стабильности.. Поскольку MCMC накладывает значительную вычислительную нагрузку, в случаях, когда вычислительная масштабируемость также представляет интерес, можно в качестве альтернативы прибегнуть к вариационным приближениям к байесовскому выводу, например В самом деле, приближенный вариационный вывод предлагает вычислительную эффективность, сравнимую с максимизацией ожидания, в то же время давая профиль точности, лишь немного уступающий точному байесовскому выводу типа MCMC.
HMM может применяться во многих областях, где цель состоит в том, чтобы восстановить последовательность данных, которая не является немедленно наблюдаемой (но другие данные, которые зависят от последовательность есть). Приложения включают:
Алгоритм «вперед – назад», используемый в HMM, впервые был описан Русланом Л. Стратоновичем в 1960 году (страницы 160–162) и в конце 1950-х годов в его статьях на русском языке. Скрытые марковские модели были позже описаны в серии статистических статей Леонарда Э. Баума и других авторов во второй половине 1960-х годов. Одним из первых применений HMM было распознавание речи, начиная с середины 1970-х годов.
Во второй половине 1980-х HMM начали применять для анализа биологических последовательностей, в частности ДНК. С тех пор они стали повсеместными в области биоинформатики.
В рассмотренных выше скрытых марковских моделях пространство состояний скрытых переменных является дискретным, в то время как сами наблюдения могут быть либо дискретный (обычно генерируется из категориального распределения ) или непрерывный (обычно из Гауссова распределения ). Скрытые марковские модели также могут быть обобщены, чтобы разрешить непрерывные пространства состояний. Примерами таких моделей являются модели, в которых марковский процесс по скрытым переменным является линейной динамической системой с линейной зависимостью между связанными переменными и где все скрытые и наблюдаемые переменные подчиняются распределению Гаусса. В простых случаях, таких как только что упомянутая линейная динамическая система, возможен точный вывод (в данном случае с использованием фильтра Калмана ); однако в целом точный вывод в HMM с непрерывными скрытыми переменными невозможен, и необходимо использовать приближенные методы, такие как расширенный фильтр Калмана или фильтр частиц.
Скрытые модели Маркова генеративные модели, в которых совместное распределение наблюдений и скрытых состояний, или, что то же самое, предварительное распределение скрытых состояний (вероятностей перехода) и условное Моделируется распределение наблюдений по заданным состояниям (вероятности излучения). Вышеупомянутые алгоритмы неявно предполагают однородное априорное распределение по вероятностям перехода. Однако также возможно создавать скрытые марковские модели с другими типами априорных распределений. Очевидным кандидатом, учитывая категориальное распределение вероятностей перехода, является распределение Дирихле, которое является сопряженным априорным распределением категориального распределения. Обычно выбирается симметричное распределение Дирихле, отражающее незнание того, какие состояния по своей природе более вероятны, чем другие. Единственный параметр этого распределения (называемый параметром концентрации) контролирует относительную плотность или разреженность полученной переходной матрицы. Выбор 1 дает равномерное распределение. Значения больше 1 создают плотную матрицу, в которой вероятности перехода между парами состояний, вероятно, будут почти равны. Значения меньше 1 приводят к разреженной матрице, в которой для каждого заданного исходного состояния только небольшое количество конечных состояний имеет немалую вероятность перехода. Также возможно использовать двухуровневое априорное распределение Дирихле, в котором одно распределение Дирихле (верхнее распределение) управляет параметрами другого распределения Дирихле (нижнее распределение), которое, в свою очередь, определяет вероятности перехода. Верхнее распределение управляет общим распределением состояний, определяя вероятность возникновения каждого состояния; его параметр концентрации определяет плотность или разреженность состояний. Такое двухуровневое априорное распределение, в котором оба параметра концентрации настроены для получения разреженных распределений, может быть полезно, например, в неконтролируемом тегировании части речи, где некоторые части речи встречаются гораздо чаще, чем другие; алгоритмы обучения, предполагающие равномерное априорное распределение, обычно плохо справляются с этой задачей. Параметры моделей этого типа с неоднородными априорными распределениями могут быть изучены с использованием выборки Гиббса или расширенных версий алгоритма максимизации ожидания.
Расширение ранее описанного скрытого Маркова. модели с априорными значениями Дирихле используют процесс Дирихле вместо распределения Дирихле. Этот тип модели допускает неизвестное и потенциально бесконечное количество состояний. Обычно используется двухуровневый процесс Дирихле, аналогичный ранее описанной модели с двумя уровнями распределений Дирихле. Такая модель называется иерархической скрытой марковской моделью процесса Дирихле, или сокращенно HDP-HMM. Первоначально он был описан под названием «Бесконечная скрытая марковская модель» и был дополнительно формализован в.
Другой тип расширения использует дискриминативную модель вместо генеративной модели стандартных HMM. Этот тип модели непосредственно моделирует условное распределение скрытых состояний с учетом наблюдений, а не моделирует совместное распределение. Примером этой модели является так называемая марковская модель максимальной энтропии (MEMM), которая моделирует условное распределение состояний с помощью логистической регрессии (также известной как «максимальная энтропия модель »). Преимущество этого типа модели состоит в том, что можно моделировать произвольные характеристики (то есть функции) наблюдений, что позволяет внедрить в модель предметно-ориентированные знания о рассматриваемой проблеме. Модели такого типа не ограничиваются моделированием прямых зависимостей между скрытым состоянием и связанным с ним наблюдением; скорее, в процесс, используемый для определения значения скрытого состояния, могут быть включены особенности близлежащих наблюдений, комбинаций связанных наблюдений и близлежащих наблюдений или фактически произвольных наблюдений на любом расстоянии от данного скрытого состояния. Кроме того, нет необходимости в том, чтобы эти признаки были статистически независимыми друг от друга, как это было бы в случае, если бы такие признаки использовались в генеративной модели. Наконец, вместо простых вероятностей перехода можно использовать произвольные функции по парам смежных скрытых состояний. Недостатками таких моделей являются: (1) типы априорных распределений, которые могут быть помещены в скрытые состояния, сильно ограничены; (2) Невозможно предсказать вероятность увидеть произвольное наблюдение. Это второе ограничение часто не является проблемой на практике, поскольку многие распространенные случаи использования HMM не требуют таких прогнозных вероятностей.
Вариантом ранее описанной дискриминантной модели является линейно-цепочечное условное случайное поле. При этом используется неориентированная графическая модель (также известная как Марковское случайное поле ), а не направленные графические модели MEMM и подобных моделей. Преимущество этого типа модели состоит в том, что она не страдает от так называемой проблемы смещения метки MEMM и, таким образом, может делать более точные прогнозы. Недостатком является то, что обучение может быть медленнее, чем для MEMM.
Еще одним вариантом является факториальная скрытая марковская модель, которая позволяет одно наблюдение быть обусловлено соответствующими скрытыми переменными набора из независимых Цепи Маркова, а не одиночная цепь Маркова. Это эквивалентно одному HMM, с состояниями (при условии, что есть состояния для каждая цепочка), и поэтому обучение в такой модели затруднено: для последовательности длиной простой алгоритм Витерби имеет сложность . Чтобы найти точное решение, можно использовать алгоритм дерева соединений, но он дает сложность. На практике можно использовать приближенные методы, такие как вариационные подходы.
Все вышеперечисленные модели могут быть расширены, чтобы учесть более отдаленные зависимости между скрытыми состояниями, например позволяя данному состоянию зависеть от предыдущих двух или трех состояний, а не от одного предыдущего состояния; то есть вероятности перехода расширены, чтобы охватить наборы из трех или четырех соседних состояний (или, в общем, смежных состояний). Недостатком таких моделей является то, что алгоритмы динамического программирования для их обучения имеют время работы для смежные состояния и общие наблюдения (т. Е. Длина- Марковская цепь).
Еще одно недавнее расширение - это триплетная марковская модель, в которой вспомогательный базовый процесс добавлен для моделирования некоторых особенностей данных. Было предложено множество вариантов этой модели. Следует также упомянуть интересную связь, которая была установлена между теорией свидетельств и триплетными марковскими моделями и которая позволяет объединять данные в марковском контексте и моделировать нестационарные данные. Обратите внимание, что альтернативные стратегии слияния многопотоковых данных также были предложены в недавней литературе, например,
Наконец, в 2012 году было предложено другое обоснование решения проблемы моделирования нестационарных данных с помощью скрытых марковских моделей. состоит в использовании небольшой рекуррентной нейронной сети (RNN), в частности сети коллектора, для захвата эволюции временной динамики в наблюдаемых данных. Эта информация, закодированная в форме многомерного вектора, используется в качестве обусловливающей переменной вероятностей перехода состояний HMM. При такой настройке мы в конечном итоге получаем нестационарную HMM, вероятности перехода которой меняются со временем таким образом, который выводится из самих данных, в отличие от некой нереалистичной специальной модели временной эволюции.
Модель, подходящая в контексте продольных данных, называется скрытой марковской моделью. Базовая версия этой модели была расширена, чтобы включить отдельные ковариаты, случайные эффекты и моделировать более сложные структуры данных, такие как многоуровневые данные. Полный обзор скрытых марковских моделей с особым вниманием к допущениям модели и их практическому использованию представлен в
На Викискладе есть материалы, связанные с Скрытой марковской моделью. |