Введение в цепи Маркова с примерами - цепи Маркова с Python



Эта статья «Введение в цепи Маркова» поможет вам понять основную идею цепей Маркова и то, как их можно смоделировать с помощью Python.

Введение в цепи Маркова:

Вы когда-нибудь задумывались, как Google оценивает веб-страницы? Если вы провели свое исследование, вы должны знать, что он использует алгоритм PageRank, который основан на идее цепей Маркова. Эта статья «Введение в цепи Маркова» поможет вам понять основную идею цепей Маркова и то, как их можно смоделировать как решение реальных проблем.

Вот список тем, которые будут рассмотрены в этом блоге:





  1. Что такое цепь Маркова?
  2. Что такое марковское свойство?
  3. Понимание цепей Маркова на примере
  4. Что такое матрица перехода?
  5. Цепь Маркова в Python
  6. Приложения цепи Маркова

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

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

Андрей Марков впервые представил цепи Маркова в 1906 году. Он объяснил цепи Маркова следующим образом:



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

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

Это подводит нас к вопросу:



Что такое марковское свойство?

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

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

Выведем это математически:

Пусть случайный процесс есть, {Xm, m = 0,1,2, ⋯}.

Этот процесс является цепью Маркова, только если

Формула цепи Маркова - Введение в цепи Маркова - Edureka

Цепи Маркова - Введение в цепи Маркова - Edureka

для всех m, j, i, i0, i1, ⋯ im & minus1

Для конечного числа состояний S = {0, 1, 2, ⋯, r} это называется конечной цепью Маркова.

P (Xm + 1 = j | Xm = i) здесь представляет вероятности перехода для перехода из одного состояния в другое. Здесь мы предполагаем, что вероятности перехода не зависят от времени.

Это означает, что P (Xm + 1 = j | Xm = i) не зависит от значения «m». Таким образом, мы можем резюмировать,

Формула цепи Маркова - Введение в цепи Маркова - Edureka

Итак, это уравнение представляет цепь Маркова.

Теперь давайте разберемся, что такое цепи Маркова на примере.

Пример цепи Маркова

Прежде чем я приведу пример, давайте определим, что такое марковская модель:

Что такое марковская модель?

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

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

массив сортировки c ++

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

Пример цепи Маркова - Введение в цепи Маркова - Edureka

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

  1. Ключи обозначают уникальные слова в предложении, т.е. 5 ключей (один, два, рад, счастливый, едурека)

  2. Токены обозначают общее количество слов, т.е.8 токенов.

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

Ключи и частоты - Введение в цепи Маркова - Edureka

Таким образом, левый столбец здесь обозначает клавиши, а правый столбец обозначает частоты.

Из приведенной выше таблицы мы можем сделать вывод, что ключ «edureka» в 4 раза больше, чем любой другой ключ. Такая информация важна, потому что она может помочь нам предсказать, какое слово может произойти в определенный момент времени. Если бы мне пришлось угадывать следующее слово в предложении-примере, я бы выбрал «edureka», поскольку оно имеет самую высокую вероятность появления.

Говоря о вероятности, вы должны знать еще одну меру. взвешенные распределения.

В нашем случае взвешенное распределение для «edureka» составляет 50% (4/8), потому что его частота равна 4 из 8 токенов. Остальные ключи (один, два, приветствую, счастливы) имеют шанс выпадения 1/8 (и асимп 13%).

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

Понимание цепей Маркова - Введение в цепи Маркова - Edureka

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

Теперь давайте назначим частоту и для этих клавиш:

Обновленные ключи и частоты - Введение в цепи Маркова - Edureka

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

что такое хэш-карта в Java

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

На диаграмме ниже вы можете увидеть, как каждый токен в нашем предложении ведет к другому. Это показывает, что будущее состояние (следующий токен) основано на текущем состоянии (текущий токен). Итак, это самое основное правило модели Маркова.

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

Пары цепей Маркова - Введение в цепи Маркова - Edureka

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

Массив пар цепей Маркова - Введение в цепи Маркова - Edureka

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

  1. Начальное распределение вероятностей (то есть начальное состояние в момент времени = 0, (клавиша «Start»))

  2. Вероятность перехода из одного состояния в другое (в данном случае вероятность перехода с одного токена на другой)

Мы определили взвешенное распределение в самом начале, поэтому у нас есть вероятности и начальное состояние, а теперь давайте продолжим пример.

  • Итак, начальный токен - [Start]

  • Далее у нас есть только один возможный токен, то есть [один]

  • В настоящее время в предложении есть только одно слово, то есть «одно».

  • Из этого токена следующий возможный токен - [edureka]

  • Предложение заменено на «один эдурека».

  • От [edureka] мы можем перейти к любому из следующих жетонов [два, привет, счастье, конец]

  • Существует 25% -ная вероятность того, что будет выбрано «два», это, возможно, приведет к формированию исходного предложения (один edureka, два edureka, hail edureka, happy edureka). Однако, если выбрать «конец», процесс останавливается, и в конечном итоге мы генерируем новое предложение, то есть «одну эдуреку».

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

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

Давайте перейдем к следующему шагу и нарисуем модель Маркова для этого примера.

Диаграмма перехода состояний - Введение в цепи Маркова - Edureka

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

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

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

Что такое матрица вероятности перехода?

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

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

Матрица перехода - Введение в цепи Маркова - Edureka

Обратите внимание, что pij & ge0 и ‘i’ для всех значений:

Формула матрицы перехода - Введение в цепи Маркова - Edureka

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

Что такое диаграмма перехода состояний?

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

Пример матрицы перехода

Рассмотрим цепь Маркова с тремя состояниями 1, 2 и 3 и следующими вероятностями:

Пример матрицы перехода - введение в цепи Маркова - Edureka

Пример диаграммы перехода состояний - Введение в цепи Маркова - Edureka

На приведенной выше диаграмме представлена ​​диаграмма переходов между состояниями для цепи Маркова. Здесь 1,2 и 3 - три возможных состояния, а стрелки, указывающие от одного состояния к другому, представляют вероятности перехода pij. Когда pij = 0, это означает, что нет перехода между состоянием «i» и состоянием «j».

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

Цепь Маркова в Python

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

  1. Как изучить Python 3 с нуля - Руководство для начинающих

А теперь приступим к кодированию!

Генератор текста цепи Маркова

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

Описание набора данных: Текстовый файл содержит список выступлений Дональда Трампа в 2016 году.

Логика: Примените свойство Маркова для создания речи Дональда Трампа, рассматривая каждое слово, используемое в речи, и для каждого слова создайте словарь слов, которые будут использоваться далее.

что такое виртуальный метод

Шаг 1. Импортируйте необходимые пакеты

импортировать numpy как np

Шаг 2: прочтите набор данных

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () # отобразить данные print (trump) РЕЧЬ 1 ... Спасибо вам так нравится. Это так мило. Разве он не отличный парень. У него нет честной прессы, он этого не понимает. Это просто не справедливо. И я должен сказать вам, что я здесь, и очень сильно здесь, потому что я очень уважаю Стива Кинга, а также очень уважаю Citizens United, Дэвида и всех остальных, а также огромное внимание к Чаепитию. А также жители Айовы. У них есть что-то общее. Трудолюбивые люди ....

Шаг 3. Разделите набор данных на отдельные слова

corpus = trump.split () # Отображение корпуса print (corpus) 'мощный,', 'но', 'не', 'мощный', 'нравится', 'нам.', 'Иран', 'имеет', ' посеяны ',' террор ', ...

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

Шаг 4: Создание пар для ключей и последующих слов

def make_pairs (corpus): для i в диапазоне (len (corpus) - 1): yield (corpus [i], corpus [i + 1]) pair = make_pairs (corpus)

Затем давайте инициализируем пустой словарь для хранения пар слов.

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

Шаг 5. Добавление словаря

word_dict = {} для word_1, word_2 в парах: if word_1 в word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

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

Шаг 6: Постройте марковскую модель

# случайно выбрать первое слово first_word = np.random.choice (corpus) # Выбрать первое слово как слово с заглавной буквы, чтобы выбранное слово не бралось между предложениями, а first_word.islower (): # Начать цепочку с выбранная цепочка слов = [first_word] # Инициализировать количество стимулируемых слов n_words = 20

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

для i в диапазоне (n_words): chain.append (np.random.choice (word_dict [цепочка [-1]]))

Шаг 7: прогнозы

Наконец, давайте отобразим стимулированный текст.

#Join возвращает цепочку в виде строки print ('' .join (chain)) Количество невероятных людей. И у Хиллари Клинтон есть наши люди и такая отличная работа. И мы не победим Обаму

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

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

Приложения цепи Маркова

Вот список реальных приложений цепей Маркова:

  1. Google PageRank: Всю сеть можно рассматривать как модель Маркова, где каждая веб-страница может быть состоянием, а ссылки или ссылки между этими страницами можно рассматривать как переходы с вероятностями. Итак, в основном, независимо от того, на какой веб-странице вы начинаете просматривать, шанс попасть на определенную веб-страницу, скажем, X - это фиксированная вероятность.

  2. Прогнозирование слова: Цепи Маркова, как известно, используются для предсказания предстоящих слов. Их также можно использовать в автозаполнении и предложениях.

  3. Subreddit Simulation: Наверняка вы сталкивались с Reddit и взаимодействовали в одной из их цепочек или субреддитов. Reddit использует симулятор subreddit, который потребляет огромное количество данных, содержащих все комментарии и обсуждения, проведенные в их группах. Используя цепи Маркова, симулятор выдает дословные вероятности для создания комментариев и тем.

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

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

На этом мы подошли к концу этого блога «Введение в цепи Маркова». Если у вас есть вопросы по этой теме, оставьте комментарий ниже, и мы свяжемся с вами.

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

Если вы ищете структурированное онлайн-обучение по Data Science, edureka! имеет специально подобранный программа, которая поможет вам получить опыт в статистике, обработке данных, исследовательском анализе данных, алгоритмах машинного обучения, таких как кластеризация K-средних, деревья решений, случайный лес, наивный байесовский анализ. Вы познакомитесь с концепциями временных рядов, интеллектуального анализа текста, а также познакомитесь с глубоким обучением. Новые партии для этого курса скоро начнутся !!