«Скрытые модели Маркова объяснены на примере реальной жизни с использованием кода Python»

«Понимание скрытых моделей Маркова на реальных примерах и с помощью Python кода»

Скрытые модели Маркова – это вероятностные модели, используемые для решения реальных проблем, охватывающих такие вещи, о которых каждый думает хотя бы раз в неделю – какая будет погода завтра?[1] – а также сложные задачи молекулярной биологии, такие как предсказание пептидных связываемых с молекулой класса II гуманного MHC[2].

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

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

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

• Together AI выпускает RedPajama v2 Открытый набор данных с 30 триллионами токенов для обучения больших языковых моделей.
• Прекратите быть плохими в сетевом общении! Выделитесь на переполненном рынке работы в области науки о данных с помощью этих 6 обязательных шагов (от Spotify Data Scientist)
• Создание разборщика резюме на основе искусственного интеллекта GenAI на хакатоне DataRobot и AWS 2023

Хотя движимые факторами, которые мы не можем наблюдать, с помощью Скрытой модели Маркова возможно моделировать эти явления как вероятностные системы.

Марковские модели с скрытыми состояниями

Скрытые модели Маркова, известные как HMM в сокращенном виде, являются статистическими моделями, которые работают как последовательность проблем с маркировкой. Это типы проблем, которые описывают эволюцию наблюдаемых событий, которые сами по себе зависят от внутренних факторов, которые не могут быть прямо наблюдаемыми – они являются скрытыми [3].

Скрытая модель Маркова состоит из двух различных стохастических процессов, то есть таких процессов, которые можно определить как последовательности матриц случайных чисел – переменные, которые зависят от случайных событий.

Есть невидимый процесс и наблюдаемый процесс.

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

Скрытые модели Маркова описывают эволюцию наблюдаемых событий, которые сами по себе зависят от внутренних факторов, которые не могут быть прямо наблюдаемыми – они являются скрытыми [3].

Как и любая другая цепь Маркова, чтобы узнать, в какое состояние вы пойдете дальше, единственное, что имеет значение, это то, где вы сейчас находитесь – в каком состоянии цепи Маркова вы находитесь сейчас. Ни одна предыдущая история состояний, в которых вы были в прошлом, не имеет значения для понимания, куда вы идете дальше.

Такая краткосрочная память является одной из ключевых характеристик HMM и она называется Марковским предположением, указывающим на то, что вероятность достижения следующего состояния зависит только от вероятности текущего состояния.

Другой ключевой характеристикой HMM является то, что он также предполагает, что каждое наблюдение зависит только от состояния, которое его породило, поэтому оно полностью независимо от любого другого состояния в цепочке [5].

Гипотеза Маркова утверждает, что вероятность достижения следующего состояния зависит только от вероятности текущего состояния.

Все это отличная фоновая информация о скрытых марковских моделях, но в каких классах задач они на самом деле используются?

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

• Вероятность или оценка, то есть определение вероятности наблюдения последовательности
• Декодинг – лучшая последовательность состояний, породившая конкретное наблюдение
• Обучение параметрам скрытой марковской модели, приведшей к наблюдению данной последовательности, проследивая определенный набор состояний.

Давайте посмотрим, как это работает на практике!

Результаты тренировки собаки в виде скрытой марковской модели

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

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

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

Помните о скрытых марковских моделях искренне рассматривайте возможность предсказать, как ваша собака себя чувствовала во время экзамена. Они могли получить определенный балл, потому что у них было чувство усталости, быть может, они были голодными или раздражены тренером.

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

Чтобы построить скрытую марковскую модель, описывающую испытательную работу вашей собаки в ходе тренировки, вам понадобятся:

• Скрытые состояния
• Матрица переходов
• Последовательность наблюдений
• Матрица вероятностей наблюдения
• Начальное распределение вероятностей

Скрытые состояния – это наблюдаемые факторы, влияющие на последовательность наблюдений. Вы будете учитывать только то, устал ваша собака или она счастлива.

Зная вашу собаку очень хорошо, единственные наблюдаемые факторы, которые могут повлиять на ее успех в экзамене – это усталость и счастье.

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

Независимо от того, какую проблему вы решаете, вам всегда нужна Последовательность наблюдений. Каждое наблюдение представляет результат прохождения скрытой марковской цепи. Каждое наблюдение извлекается из определенного словаря.

В случае экзамена вашей собаки вы наблюдаете за баллами, которые они получают после каждой попытки, их может быть Фейл, ОК или Идеально. Это все возможные термины в словаре наблюдений.

Вам также понадобится Матрица вероятности наблюдений, которая представляет собой вероятность генерации наблюдения из определенного состояния.

Наконец, есть Начальное распределение вероятностей. Это вероятность того, что цепь Маркова начнется с каждого определенного скрытого состояния.

В цепи Маркова также могут быть состояния, которые никогда не будут начальными состояниями. В таких ситуациях их начальная вероятность равна нулю. И, подобно вероятностям в Матрице переходов, сумма всех начальных вероятностей должна быть равна единице.

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

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

Во время экзамена ваша собака представит три попытки и получит диплом только в том случае, если на двух из них не будет провала.

В конце дня, если вашей собаке нужно больше тренировки, вы все равно заботитесь о ней. Большой вопрос, который вас волнует, это Как они себя чувствуют во время экзамена.

Представим себе ситуацию, когда они окончат экзамен со счетом ОК — Фейл — Идеально именно в таком порядке, в какой последовательности эмоциональных состояний они будут находиться? Они будут в основном уставшими или голодными на протяжении всего времени, или, возможно, комбинацией обоих состояний?

Такая задача попадает в категорию задач декодирования, к которым применяются скрытые марковские модели (HMM). В этом случае вас интересует определение наилучшей последовательности состояний, которая сгенерировала определенную последовательность наблюдений ОК — Фейл — Идеально.

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

Алгоритм Прямого расчета

Если бы вы моделировали эту задачу как обычную Марковскую цепь и хотели рассчитать вероятность наблюдения последовательности результатов ОК, Фейл, Идеально, вы бы перебирали все состояния цепи, которые генерируют желаемый результат. На каждом шаге вы бы брали условную вероятность текущего результата при условии, что вы наблюдали предыдущий результат, и умножали эту вероятность на вероятность перехода от одного состояния к другому.

Большая разница в том, что в обычной Марковской цепи все состояния хорошо известны и наблюдаемы. Но в скрытой марковской модели это не так! В скрытой марковской модели вы наблюдаете последовательность результатов, не зная, какая конкретная последовательность скрытых состояний должна быть преодолена для наблюдения за ними.

Большая разница в том, что в обычной Марковской цепи все состояния хорошо известны и наблюдаемы. Но в скрытой марковской модели это не так!

На этом этапе вы можете подумать: «Что если я просто пройдусь по всем возможным путям и в конечном итоге найду правило выбора между эквивалентными путями? Математическое определение этого подхода выглядит примерно так

Это определенно одна из стратегий! Вам нужно будет рассчитать вероятность наблюдения последовательности ОК, Ошибка, Идеально для каждой возможной комбинации скрытых состояний, которые могут породить эту последовательность.

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

К счастью, только что определенная вами скрытая модель Маркова относительно проста, с 3 наблюдаемыми исходами и 2 скрытыми состояниями.

Для наблюдаемой последовательности исходов длиной L, в модели Маркова с M скрытыми состояниями у вас есть “M в степени L” возможных состояний, что в вашем случае означает 2 в степени 3, то есть 8 возможных путей для последовательности ОК – Ошибка – Идеально, с экспоненциальной вычислительной сложностью O(M^L *L), описанной в Big O-нотации. По мере увеличения сложности модели количество путей, которые нужно учитывать, растет экспоненциально.

По мере увеличения сложности модели количество путей, которые нужно учитывать, растет экспоненциально.

Вот где сияет Алгоритм прямого прохода.

Алгоритм прямого прохода вычисляет вероятность нового символа в наблюдаемой последовательности без необходимости рассчитывать вероятности всех возможных путей, формирующих эту последовательность [3].

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

Факт использования рекурсии – ключевая причина, по которой этот алгоритм работает быстрее, чем расчет всех вероятностей возможных путей. Фактически, он может рассчитать вероятность наблюдения последовательности x за только «L раз M в квадрате» вычислений, вместо «M в степени L раз L».

В вашем случае, с 2 скрытыми состояниями и последовательностью из 3 наблюдаемых исходов, это разница между расчетом вероятностей O(MˆL * L) = 2³x3 = 8×3 = 24 раза вместо O(L Mˆ2) = 3*2²=3×4=12 раз.

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

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

Вернемся к вашей проблеме декодирования с помощью алгоритма Витерби.

Алгоритм Витерби

Думая о псевдокоде, если вы собирались насильно декодировать последовательность скрытых состояний, порождающих конкретную последовательность наблюдаемых исходов, вам нужно было просто:

• сгенерировать все возможные перестановки путей, которые приводят к желаемой последовательности наблюдений
• использовать алгоритм Forward для вычисления вероятности каждой последовательности наблюдений для каждой возможной последовательности скрытых состояний
• выбрать последовательность скрытых состояний с наибольшей вероятностью

Для вашей конкретной HMM существует 8 возможных путей, которые приводят к состоянию OK — Fail — Perfect. Добавьте только одно наблюдение, и у вас будет в два раза больше возможных последовательностей скрытых состояний! Подобно описанному для алгоритма Forward, вы легко получите экспоненциально сложный алгоритм и достигнете предела производительности.

Алгоритм Витерби вам поможет с этим.

При обходе последовательности скрытых состояний в HMM на каждом шаге вероятность vt(j) – это вероятность того, что HMM находится в скрытом состоянии j после просмотра наблюдения и проходит через наиболее вероятное состояние, которое приводит к j.

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

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

Можно провести параллель между алгоритмом Forward и алгоритмом Витерби. Где алгоритм Forward суммирует все вероятности для определения вероятности достижения определенного состояния с учетом всех путей, которые приводят туда, а алгоритм Витерби не хочет исследовать все возможности. Он фокусируется на наиболее вероятном пути, ведущем к любому заданному состоянию.

Вернемся к задаче расшифровки последовательности скрытых состояний, которые приводят к оценкам OK — Fail — Perfect на экзамене. Выполнение алгоритма Витерби вручную будет выглядеть так

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

Указатели на предыдущие состояния – это ключ для определения наиболее вероятного пути, ведущего к последовательности наблюдений.

В примере с экзаменом ваших собак, при расчете Витерби-путей v3(Happy) и v3(Tired) вы выбираете путь с наибольшей вероятностью и начинаете двигаться назад, т.е. возвращаться назад, через все пути, которые привели вас туда, где вы находитесь.

Алгоритм Витерби на Python

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

Хорошая новость в том, что вы можете воспользоваться библиотеками программного обеспечения, такими как hmmlearn, и всего лишь с несколькими строками кода вы можете расшифровать последовательность скрытых состояний, которые приводят к тому, что ваша собака получает оценку OK — Fail — Perfect в испытаниях, именно в таком порядке.

от hmmlearn импортируйте мммimport numpy as np## Часть 1. Создание МММ с определенными параметрами и моделирование экзаменаprint("Настройка модели МММ с параметрами")# init_params - параметры, используемые для инициализации модели для обучения# s -> начальная вероятность# t -> вероятности перехода# e -> вероятности испусканияmodel = hmm.CategoricalHMM(n_components=2, random_state=425, init_params='ste')# начальные вероятности# вероятность начать в состоянии "усталость" = 0# вероятность начать в состоянии "счастье" = 1initial_distribution = np.array([0.1, 0.9])model.startprob_ = initial_distributionprint("Шаг 1. Завершено - Задано начальное распределение")# вероятности перехода#        усталость    счастье# усталость     0.4      0.6# счастье     0.2      0.8transition_distribution = np.array([[0.4, 0.6], [0.2, 0.8]])model.transmat_ = transition_distributionprint("Шаг 2. Завершено - Задана матрица переходов")# вероятности наблюдений#        Неудача     ОК      Идеально# усталость     0.3    0.5       0.2# счастье     0.1    0.5       0.4observation_probability_matrix = np.array([[0.3, 0.5, 0.2], [0.1, 0.5, 0.4]])model.emissionprob_ = observation_probability_matrixprint("Шаг 3. Завершено - Задана матрица вероятностей наблюдений")# моделирование проведения 100 000 испытаний, т.е. тестовых экзаменовиспытания, смоделированные_состояния = model.sample(100000)# Вывод выборки смоделированных испытаний# 0 -> Неудача# 1 -> ОК# 2 -> Идеальноprint("\nВыборка смоделированных испытаний - на основе параметров модели")print(trials[:10])## Часть 2 - Декодирование последовательности скрытых состояний, которая приводит к последовательности наблюдений: ОК - Неудача - Идеально# разделяем данные на обучающий и тестовый наборы (разделение 50/50)X_train = trials[:trials.shape[0] // 2]X_test = trials[trials.shape[0] // 2:]model.fit(X_train)# экзамен состоял из 3 испытаний, на вашей собаке были следующие оценки: ОК, Неудача, Идеально (1, 0, 2)экзамен_наблюдения = [[1, 0, 2]]предсказанные_состояния = model.predict(X=[[1, 0, 2]])print("Предсказание скрытых состояний, которые предшествовали оценкам экзамена ОК, Неудача, Идеально: \n 0 -> Усталость , "      "1 -> Счастье")print(predicted_states)

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

Вывод

Удивительно, насколько мощными и применимыми к реальным проблемам в различных областях являются скрытые марковские модели, созданные в середине 1960-х годов [6]. Они применяются в таких задачах, как прогноз погоды и определение следующего слова в предложении.

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

Будь то выполнение расчетов вручную или использование кода TensorFlow, надеюсь, вы насладились погружением в мир скрытых марковских моделей.

Спасибо за чтение!

Ссылки

1. D. Khiatani and U. Ghose, «Weather forecasting using Hidden Markov Model,» 2017 International Conference on Computing and Communication Technologies for Smart Nation (IC3TSN), Gurgaon, India, 2017, pp. 220–225, doi: 10.1109/IC3TSN.2017.8284480.
2. Noguchi H, Kato R, Hanai T, Matsubara Y, Honda H, Brusic V, Kobayashi T. Hidden Markov model-based prediction of antigenic peptides that interact with MHC class II molecules. J Biosci Bioeng. 2002;94(3):264–70. doi: 10.1263/jbb.94.264. PMID: 16233301.
3. Yoon BJ. Hidden Markov Models and their Applications in Biological Sequence Analysis. Curr Genomics. 2009 Sep;10(6):402–15. doi: 10.2174/138920209789177575. PMID: 20190955; PMCID: PMC2766791.
4. Eddy, S. What is a hidden Markov model?. Nat Biotechnol 22, 1315–1316 (2004). https://doi.org/10.1038/nbt1004-1315
5. Jurafsky, Dan and Martin, James H.. Speech and language processing : an introduction to natural language processing, computational linguistics, and speech recognition. Upper Saddle River, N.J.: Pearson Prentice Hall, 2009.
6. Baum, Leonard E., and Ted Petrie. “Statistical Inference for Probabilistic Functions of Finite State Markov Chains.” The Annals of Mathematical Statistics 37, no. 6 (1966): 1554–63.