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

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

Первые заметки о скрытых марковских моделях опубликовал Баум (англ.) в 1960-х, и уже в 70-х их впервые применили при распознавании речи. С середины 1980-х СММ применяются при анализе биологических последовательностей, в частности ДНК.

Основное применение СММ получили в области распознавания речи, письма, движений и биоинформатике. Кроме того, СММ применяются в криптоанализе, машинном переводе.

Пример

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

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

Структура скрытой марковской модели

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

Диаграмма, представленная ниже, показывает общую структуру СММ. Овалы представляют собой переменные со случайным значением. Случайная переменная <math>x(t)</math> представляет собой значение скрытой переменной в момент времени <math>t</math>. Случайная переменная <math>y(t)</math> — это значение наблюдаемой переменной в момент времени <math>t</math>. Стрелки на диаграмме символизируют условные зависимости.

Из диаграммы становится ясно, что значение скрытой переменной <math>x(t)</math> (в момент времени <math>t</math>) зависит только от значения скрытой переменной <math>x(t-1)</math> (в момент <math>t-1</math>). Это называется свойством Маркова. Хотя в то же время значение наблюдаемой переменной <math>y(t)</math> зависит только от значения скрытой переменной <math>x(t)</math> (обе в момент времени <math>t</math>).

Вероятность увидеть последовательность <math>Y=y(0), y(1),\dots,y(L-1)</math> длины <math>L</math> равна

<math>P(Y)=\sum_{X}P(Y\mid X)P(X),</math>

здесь сумма пробегает по всем возможным последовательностям скрытых узлов <math>X=x(0), x(1), \dots, x(L-1).</math> Метод подсчёта полным перебором значений <math>P(Y)</math> — очень трудоёмкий для многих задач из реальной жизни в силу того, что количество возможных последовательностей скрытых узлов очень велико. Но применение процедуры прямого-обратного хода позволяет существенно увеличить скорость вычислений.

Базовые алгоритмы

Существуют три основных задачи, связанные с СММ:

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

См. также

• Теорема Марелье

Ссылки

• [ru.wikibooks.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D1%8B%D0%B5_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8#.D0.A2.D1.80.D0.B8_.D0.BE.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D1.85_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87.D0.B8_.D0.A1.D0.9C.D0.9C Скрытые Марковские Модели]
• Сергей Николенко. Лекции [logic.pdmi.ras.ru/~sergey/teaching/mlbayes/06-hmm.pdf № 6] и [logic.pdmi.ras.ru/~sergey/teaching/mlbayes/07-hmm2.pdf № 7] (слайды), посвящённые скрытым марковским моделям, из курса [www.csin.ru/courses/probabilistic-learning «Вероятностное обучение»]

Отрывок, характеризующий Скрытая марковская модель

Балашев, чувствуя необходимость возражать, сказал, что со стороны России дела не представляются в таком мрачном виде. Наполеон молчал, продолжая насмешливо глядеть на него и, очевидно, его не слушая. Балашев сказал, что в России ожидают от войны всего хорошего. Наполеон снисходительно кивнул головой, как бы говоря: «Знаю, так говорить ваша обязанность, но вы сами в это не верите, вы убеждены мною».
В конце речи Балашева Наполеон вынул опять табакерку, понюхал из нее и, как сигнал, стукнул два раза ногой по полу. Дверь отворилась; почтительно изгибающийся камергер подал императору шляпу и перчатки, другой подал носовои платок. Наполеон, ne глядя на них, обратился к Балашеву.
– Уверьте от моего имени императора Александра, – сказал оц, взяв шляпу, – что я ему предан по прежнему: я анаю его совершенно и весьма высоко ценю высокие его качества. Je ne vous retiens plus, general, vous recevrez ma lettre a l'Empereur. [Не удерживаю вас более, генерал, вы получите мое письмо к государю.] – И Наполеон пошел быстро к двери. Из приемной все бросилось вперед и вниз по лестнице.


После всего того, что сказал ему Наполеон, после этих взрывов гнева и после последних сухо сказанных слов:
«Je ne vous retiens plus, general, vous recevrez ma lettre», Балашев был уверен, что Наполеон уже не только не пожелает его видеть, но постарается не видать его – оскорбленного посла и, главное, свидетеля его непристойной горячности. Но, к удивлению своему, Балашев через Дюрока получил в этот день приглашение к столу императора.
На обеде были Бессьер, Коленкур и Бертье. Наполеон встретил Балашева с веселым и ласковым видом. Не только не было в нем выражения застенчивости или упрека себе за утреннюю вспышку, но он, напротив, старался ободрить Балашева. Видно было, что уже давно для Наполеона в его убеждении не существовало возможности ошибок и что в его понятии все то, что он делал, было хорошо не потому, что оно сходилось с представлением того, что хорошо и дурно, но потому, что он делал это.
Император был очень весел после своей верховой прогулки по Вильне, в которой толпы народа с восторгом встречали и провожали его. Во всех окнах улиц, по которым он проезжал, были выставлены ковры, знамена, вензеля его, и польские дамы, приветствуя его, махали ему платками.
За обедом, посадив подле себя Балашева, он обращался с ним не только ласково, но обращался так, как будто он и Балашева считал в числе своих придворных, в числе тех людей, которые сочувствовали его планам и должны были радоваться его успехам. Между прочим разговором он заговорил о Москве и стал спрашивать Балашева о русской столице, не только как спрашивает любознательный путешественник о новом месте, которое он намеревается посетить, но как бы с убеждением, что Балашев, как русский, должен быть польщен этой любознательностью.
– Сколько жителей в Москве, сколько домов? Правда ли, что Moscou называют Moscou la sainte? [святая?] Сколько церквей в Moscou? – спрашивал он.
И на ответ, что церквей более двухсот, он сказал:
– К чему такая бездна церквей?
– Русские очень набожны, – отвечал Балашев.
– Впрочем, большое количество монастырей и церквей есть всегда признак отсталости народа, – сказал Наполеон, оглядываясь на Коленкура за оценкой этого суждения.
Балашев почтительно позволил себе не согласиться с мнением французского императора.
– У каждой страны свои нравы, – сказал он.
– Но уже нигде в Европе нет ничего подобного, – сказал Наполеон.
– Прошу извинения у вашего величества, – сказал Балашев, – кроме России, есть еще Испания, где также много церквей и монастырей.
Этот ответ Балашева, намекавший на недавнее поражение французов в Испании, был высоко оценен впоследствии, по рассказам Балашева, при дворе императора Александра и очень мало был оценен теперь, за обедом Наполеона, и прошел незаметно.
По равнодушным и недоумевающим лицам господ маршалов видно было, что они недоумевали, в чем тут состояла острота, на которую намекала интонация Балашева. «Ежели и была она, то мы не поняли ее или она вовсе не остроумна», – говорили выражения лиц маршалов. Так мало был оценен этот ответ, что Наполеон даже решительно не заметил его и наивно спросил Балашева о том, на какие города идет отсюда прямая дорога к Москве. Балашев, бывший все время обеда настороже, отвечал, что comme tout chemin mene a Rome, tout chemin mene a Moscou, [как всякая дорога, по пословице, ведет в Рим, так и все дороги ведут в Москву,] что есть много дорог, и что в числе этих разных путей есть дорога на Полтаву, которую избрал Карл XII, сказал Балашев, невольно вспыхнув от удовольствия в удаче этого ответа. Не успел Балашев досказать последних слов: «Poltawa», как уже Коленкур заговорил о неудобствах дороги из Петербурга в Москву и о своих петербургских воспоминаниях.