Объяснение цепи Маркова

Понять, как работают цепи Маркова, и реализовать их в Python для генерации текста

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

Цепь Маркова - это стохастическая модель, созданная Андреем Марковым, которая описывает вероятность, связанную с последовательностью событий, происходящих на основе состояния в предыдущем событии. Очень распространенная и простая для понимания модель, которая широко используется в различных отраслях, которые часто имеют дело с последовательными данными, например в финансах. Алгоритм, который Google использует в своей поисковой системе, чтобы указать, какие ссылки показывать в первую очередь, называется алгоритмом Page Rank, это разновидность цепи Маркова. С помощью математики эта модель будет использовать наши наблюдения для приблизительного прогнозирования будущих событий!

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

Что такое цепь Маркова

Как указано выше, марковский процесс - это случайный процесс, который имеет характеристики без памяти. Термин «отсутствие памяти» в математике - это свойство вероятностных распределений. Обычно это относится к сценариям, когда время, связанное с наступлением определенного события, не зависит от того, сколько времени уже прошло. Другими словами, когда модель обладает свойством без памяти, это означает, что модель «забывает», в каком состоянии находится система. Следовательно, на вероятности не будут влиять предыдущие состояния процесса. Это свойство отсутствия памяти - основная характеристика марковского процесса. Прогнозы, связанные с марковским процессом, зависят от его текущего состояния и не зависят от прошлых и будущих состояний.

Этот атрибут отсутствия памяти является одновременно благословением и проклятием для модели Маркова в приложении. Представьте себе сценарий, в котором вы хотите предсказывать слова / предложения на основе ранее введенного текста (аналогично тому, как это делает Google для Gmail). Что ж, преимущество использования марковского процесса для этого состоит в том, что вновь созданные прогнозы не будут зависеть от того, что вы написали несколько параграфов назад. Однако недостатком этого является то, что вы не сможете предсказать текст, который имеет контекст в предыдущем состоянии модели. Это обычная проблема в NLP (обработка естественного языка), с которой сталкиваются многие модели.

Модель

Модель цепи Маркова зависит от двух ключевых частей информации:

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

      +-----+-----+-----+          
      |  A  |  B  |  C  |   - Represents the network above
+-----+-----+-----+-----+   - NxN transition matrix 
|  A  |  .2 |  .3 |  .5 |   - element hold probabilities
+-----+-----+-----+-----+   - row sum of probabilities = 1  
|  B  |  .6 |  0  |  .4 |   - .3 is the probability for state A 
+-----+-----+-----+-----+     to go to state B
|  C  |  .1 | .7  |  .2 |   - .7 is the probability for state C
+-----+-----+-----+-----+     to go to state B

Вектор начального состояния (обозначается S) - этот вектор Nx1 представляет распределение вероятности запуска в каждом из N возможных состояний. Каждый элемент в векторе представляет вероятность начала в этом состоянии.

Учитывая эти 2 зависимости, вы можете определить начальное состояние цепи Маркова, взяв произведение P x I. Чтобы предсказать вероятность возникновения будущих состояний, вы можете возвести матрицу перехода P в M в степени.

Пример

Очень распространенное применение цепей Маркова в науке о данных - предсказание текста. Это область НЛП, которая обычно используется в технологической индустрии такими компаниями, как Google, LinkedIn и Instagram. Когда вы пишете электронные письма, Google предсказывает и предлагает вам слова / фразы для автозаполнения вашего электронного письма, когда вы получаете сообщения в Instagram или LinkedIn, приложение предлагает некоторые возможные ответы. Это приложения цепи Маркова, которые мы рассмотрим, хотя на самом деле типы моделей, которые эти крупные компании используют в производстве для этих функций, определенно более сложны.

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

В целях наглядности эта сеть, представленная выше, имеет небольшое количество слов в своем корпусе, при работе с большим объемом текста, например, в серии о Гарри Поттере, эта сеть станет очень большой и сложной. Если вы посмотрите на начальное слово Hello, за ним следуют 3 возможных других слова / символа Everyone , There с соответствующими вероятностями. Самый простой способ вычисления этих вероятностей - это частота слова в корпусе.

Hello --> ['Everyone', ',', 'Everyone', 'Everyone', 'There', 'There', 'There', There', There', ...]

Если бы в приведенном выше списке было 20 слов, где каждое слово указано после слова Hello, тогда вероятность появления каждого слова была бы следующей формулой:

P(word) = Frequency of Word / Total Number of Words in List
P(Everyone) = 9 / 20
P(,) = 1 / 20
P(There) = 10 / 20

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

Реализация

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

Резюме

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