Введение в цепи Маркова:
Вы когда-нибудь задумывались, как Google оценивает веб-страницы? Если вы провели свое исследование, вы должны знать, что он использует алгоритм PageRank, который основан на идее цепей Маркова. Эта статья «Введение в цепи Маркова» поможет вам понять основную идею цепей Маркова и то, как их можно смоделировать как решение реальных проблем.
Вот список тем, которые будут рассмотрены в этом блоге:
- Что такое цепь Маркова?
- Что такое марковское свойство?
- Понимание цепей Маркова на примере
- Что такое матрица перехода?
- Цепь Маркова в Python
- Приложения цепи Маркова
Чтобы получить глубокие знания о данных и машинном обучении с использованием Python, вы можете зарегистрироваться в прямом эфире от Edureka с круглосуточной поддержкой и пожизненным доступом.
Что такое цепь Маркова?
Андрей Марков впервые представил цепи Маркова в 1906 году. Он объяснил цепи Маркова следующим образом:
Стохастический процесс, содержащий случайные величины, переходящий из одного состояния в другое в зависимости от определенных предположений и определенных вероятностных правил.
Эти случайные переменные переходят из одного состояния в другое на основе важного математического свойства, называемого Марковская собственность.
Это подводит нас к вопросу:
Что такое марковское свойство?
Марковское свойство дискретного времени утверждает, что вычисленная вероятность перехода случайного процесса в следующее возможное состояние зависит только от текущего состояния и времени и не зависит от серии состояний, которые ему предшествовали.
Тот факт, что следующее возможное действие / состояние случайного процесса не зависит от последовательности предыдущих состояний, делает цепи Маркова процессом без памяти, который зависит исключительно от текущего состояния / действия переменной.
Выведем это математически:
Пусть случайный процесс есть, {Xm, m = 0,1,2, ⋯}.
Этот процесс является цепью Маркова, только если
Цепи Маркова - Введение в цепи Маркова - 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
Вышеупомянутое предложение является нашим примером, я знаю, что оно не имеет особого смысла (это не обязательно), это предложение, содержащее случайные слова, в которых:
Ключи обозначают уникальные слова в предложении, т.е. 5 ключей (один, два, рад, счастливый, едурека)
Токены обозначают общее количество слов, т.е.8 токенов.
Двигаясь вперед, нам нужно понять частоту встречаемости этих слов, на диаграмме ниже показано каждое слово вместе с числом, обозначающим частоту этого слова.
Ключи и частоты - Введение в цепи Маркова - Edureka
Таким образом, левый столбец здесь обозначает клавиши, а правый столбец обозначает частоты.
Из приведенной выше таблицы мы можем сделать вывод, что ключ «edureka» в 4 раза больше, чем любой другой ключ. Такая информация важна, потому что она может помочь нам предсказать, какое слово может произойти в определенный момент времени. Если бы мне пришлось угадывать следующее слово в предложении-примере, я бы выбрал «edureka», поскольку оно имеет самую высокую вероятность появления.
Говоря о вероятности, вы должны знать еще одну меру. взвешенные распределения.
В нашем случае взвешенное распределение для «edureka» составляет 50% (4/8), потому что его частота равна 4 из 8 токенов. Остальные ключи (один, два, приветствую, счастливы) имеют шанс выпадения 1/8 (и асимп 13%).
Теперь, когда у нас есть понимание взвешенного распределения и представление о том, почему определенные слова встречаются чаще, чем другие, мы можем перейти к следующей части.
Понимание цепей Маркова - Введение в цепи Маркова - Edureka
На приведенном выше рисунке я добавил два дополнительных слова, обозначающих начало и конец предложения, вы поймете, почему я сделал это, в следующем разделе.
Теперь давайте назначим частоту и для этих клавиш:
Обновленные ключи и частоты - Введение в цепи Маркова - Edureka
А теперь давайте создадим марковскую модель. Как упоминалось ранее, модель Маркова используется для моделирования случайных величин в определенном состоянии таким образом, что будущие состояния этих переменных зависят исключительно от их текущего состояния, а не от их прошлых состояний.
что такое хэш-карта в Java
Таким образом, в марковской модели, чтобы предсказать следующее состояние, мы должны учитывать только текущее состояние.
На диаграмме ниже вы можете увидеть, как каждый токен в нашем предложении ведет к другому. Это показывает, что будущее состояние (следующий токен) основано на текущем состоянии (текущий токен). Итак, это самое основное правило модели Маркова.
На диаграмме ниже показано, что есть пары токенов, в которых каждый токен в паре ведет к другому токену в той же паре.
Пары цепей Маркова - Введение в цепи Маркова - Edureka
На приведенной ниже диаграмме я создал структурное представление, которое показывает каждый ключ с массивом следующих возможных токенов, с которыми он может соединяться.
Массив пар цепей Маркова - Введение в цепи Маркова - Edureka
Подводя итог этому примеру, рассмотрим сценарий, в котором вам нужно будет сформировать предложение, используя массив ключей и токенов, который мы видели в приведенном выше примере. Прежде чем мы рассмотрим этот пример, еще один важный момент: нам нужно указать две начальные меры:
Начальное распределение вероятностей (то есть начальное состояние в момент времени = 0, (клавиша «Start»))
Вероятность перехода из одного состояния в другое (в данном случае вероятность перехода с одного токена на другой)
Мы определили взвешенное распределение в самом начале, поэтому у нас есть вероятности и начальное состояние, а теперь давайте продолжим пример.
Итак, начальный токен - [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, вы можете просмотреть следующие блоги:
А теперь приступим к кодированию!
Генератор текста цепи Маркова
Постановка задачи: Чтобы применить свойство Маркова и создать марковскую модель, которая может генерировать симуляции текста, изучая набор данных речи Дональда Трампа.
Описание набора данных: Текстовый файл содержит список выступлений Дональда Трампа в 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)) Количество невероятных людей. И у Хиллари Клинтон есть наши люди и такая отличная работа. И мы не победим Обаму
Итак, это сгенерированный текст, который я получил, рассматривая речь Трампа. Возможно, в этом нет большого смысла, но этого достаточно, чтобы вы поняли, как цепи Маркова могут использоваться для автоматической генерации текстов.
Теперь давайте рассмотрим еще несколько приложений. цепей Маркова и как они используются для решения реальных проблем.
Приложения цепи Маркова
Вот список реальных приложений цепей Маркова:
Google PageRank: Всю сеть можно рассматривать как модель Маркова, где каждая веб-страница может быть состоянием, а ссылки или ссылки между этими страницами можно рассматривать как переходы с вероятностями. Итак, в основном, независимо от того, на какой веб-странице вы начинаете просматривать, шанс попасть на определенную веб-страницу, скажем, X - это фиксированная вероятность.
Прогнозирование слова: Цепи Маркова, как известно, используются для предсказания предстоящих слов. Их также можно использовать в автозаполнении и предложениях.
Subreddit Simulation: Наверняка вы сталкивались с Reddit и взаимодействовали в одной из их цепочек или субреддитов. Reddit использует симулятор subreddit, который потребляет огромное количество данных, содержащих все комментарии и обсуждения, проведенные в их группах. Используя цепи Маркова, симулятор выдает дословные вероятности для создания комментариев и тем.
Генератор текста: Цепи Маркова чаще всего используются для создания фиктивных текстов или создания больших эссе и составления речей. Он также используется в генераторах имен, которые вы видите в Интернете.
Теперь, когда вы знаете, как решить реальную проблему с помощью цепей Маркова, я уверен, вам интересно узнать больше. Вот список блогов, которые помогут вам начать работу с другими статистическими концепциями:
На этом мы подошли к концу этого блога «Введение в цепи Маркова». Если у вас есть вопросы по этой теме, оставьте комментарий ниже, и мы свяжемся с вами.
Следите за новостями, чтобы увидеть больше блогов о новейших технологиях.
Если вы ищете структурированное онлайн-обучение по Data Science, edureka! имеет специально подобранный программа, которая поможет вам получить опыт в статистике, обработке данных, исследовательском анализе данных, алгоритмах машинного обучения, таких как кластеризация K-средних, деревья решений, случайный лес, наивный байесовский анализ. Вы познакомитесь с концепциями временных рядов, интеллектуального анализа текста, а также познакомитесь с глубоким обучением. Новые партии для этого курса скоро начнутся !!