Цепи Маркова и Пайтон — разбираемся в теории и собираем генератор текстов

  • Tutorial

Понимаем и создаём


Хорошие новости перед статьей: высоких математических скиллов для прочтения и (надеюсь!) понимания не требуется.

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

Итак, поехали!

Структура такая:

  • Что такое цепь Маркова?
  • Пример работы цепочки
  • Матрица переходов
  • Модель, основанная на Марковской цепи при помощи Пайтона — генерация текста на основе данных

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


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

Держа в голове жирношрифтовое слово только, выведем свойство цепи Маркова:

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

Иначе говоря, новое значение всегда пляшет от того, которое его непосредственно держит за ручку.

Пример работы цепочки


Как и автор статьи, из которой позаимствована кодовая реализация, возьмем рандомную последовательность слов.

Старт — искусственная — шуба — искусственная — еда — искусственная — паста — искусственная — шуба — искусственная — конец

Представим, что на самом деле это великолепный стих и нашей задачей является скопировать стиль автора. (Но делать так, конечно, неэтично)

Как решать?


Первое явное, что хочется сделать — посчитать частотность слов (если бы мы делали это с живым текстом, для начала стоило бы провести нормализацию — привести каждое слово к лемме (словарной форме)).

Старт == 1
Искусственная == 5
Шуба == 2
Паста == 1
Еда == 1
Конец == 1

Держа в голове, что у нас цепочка Маркова, мы можем построить распределение новых слов в зависимости от предыдущих графически:



Словесно:

  • состояние шубы, еды и пасты 100% за собой влекут состояние искусственная p = 1
  • состояние “искусственная” равновероятно может привести к 4 состояниям, и вероятность прийти к состоянию искусственной шубы выше, чем к трём остальным
  • состояние конца никуда не ведет
  • состояние «старт» 100% влечет состояние «искусственная»

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



Что на русском означает «сумма ряда вероятностей для некоторого события k, зависимого от i == сумме всех значений вероятностей события k в зависимости от наступления состояния i, где событие k == m+1, а событие i == m (то есть событие k всегда на единицу отличается от  i)».

Но для начала поймем, что такое матрица.

Матрица переходов


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

Да, да, звучит так, как звучит.

Но выглядит не так страшно:



P — это обозначение матрицы. Значения на пересечении столбцов и строк здесь отражают вероятности переходов между состояниями.

Для нашего примера это будет выглядеть как-то так:



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

Голый пример без искусственных шуб и паст:



Ещё более голый пример — единичная матрица для:

  • случая когда нельзя из А перейти обратно В, а из В — обратно в А[1]
  • случая, когда переход из А в В обратно возможен[2]



Респекто. С теорией закончили.
Используем Пайтон.

Модель, основанная на Марковской цепи при помощи Пайтона — генерация текста на основе данных


Шаг 1

Импортируем релевантный пакет для работы и достаём данные.

import numpy as np
data = open('/Users/sad__sabrina/Desktop/док1.txt', encoding='utf8').read()

print(data)

В теории вероятностей и смежных областях, марковский процесс , названный в честь русского математика Андрея Маркова , является случайным процессом , который удовлетворяет свойство Маркова (иногда характеризуются как « memorylessness »). Грубо говоря, процесс удовлетворяет свойству Маркова , если можно делать прогнозы на будущее процесса , основанного исключительно на его нынешнем состоянии точно так же , как можно было бы знать всю историю процесса, а значит , независимо от такой истории; т.е., условно на нынешнее состояние системы, ее прошлое и будущее государства независимы .

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

Шаг 2

Разделим данные на слова.

ind_words = data.split()
print(ind_words)

['\ufeffВ', 'теории', 'вероятностей', 'и', 'смежных', 'областях,', 'марковский', 'процесс', ',', 'названный', 'в', 'честь', 'русского', 'математика', 'Андрея', 'Маркова', ',', 'является', 'случайным', 'процессом', ',', 'который', 'удовлетворяет', 'свойство', 'Маркова', '(иногда', 'характеризуются', 'как', '«', 'memorylessness', '»).', 'Грубо', 'говоря,', 'процесс', 'удовлетворяет', 'свойству', 'Маркова', ',', 'если', 'можно', 'делать', 'прогнозы', 'на', 'будущее', 'процесса', ',', 'основанного', 'исключительно', 'на', 'его', 'нынешнем', 'состоянии', 'точно', 'так', 'же', ',', 'как', 'можно', 'было', 'бы', 'знать', 'всю', 'историю', 'процесса,', 'а', 'значит', ',', 'независимо', 'от', 'такой', 'истории;', 'т.е.,', 'условно', 'на', 'нынешнее', 'состояние', 'системы,', 'ее', 'прошлое', 'и', 'будущее', 'государства', 'независимы', '.']

Шаг 3

Создадим функцию для связки пар слов.

def make_pairs(ind_words):
    for i in range(len(ind_words) - 1):
        yield (ind_words[i], ind_words[i + 1])
pair = make_pairs(ind_words)

Главный нюанс функции в применении оператора yield(). Он помогает нам удовлетворить критерию цепочки Маркова — критерию хранения без памяти. Благодаря yield, наша функция будет создавать новые пары в процессе итераций(повторений), а не хранить все.

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

Шаг 4

word_dict = {}
for word_1, word_2 in pair:
    if word_1 in word_dict.keys():
        word_dict[word_1].append(word_2)
    else:
        word_dict[word_1] = [word_2]

Здесь:

  • если у нас в словаре уже есть запись о первом слове в паре, функция добавляет следующее потенциальное значение в список.
  • иначе: создаётся новая запись.

Шаг 5

Рандомно выберем первое слово и, чтобы слово было действительно случайным, зададим условие while при помощи строкового метода islower(), который удовлетворяет True в случае, когда в строке значения из букв нижнего регистра, допуская наличие цифр или символов.
При этом зададим количество слов 20.

first_word = np.random.choice(ind_words)
 
while first_word.islower():
    chain = [first_word]
    n_words = 20
    first_word = np.random.choice(ind_words)
    
    for i in range(n_words):
        chain.append(np.random.choice(word_dict[chain[-1]]))

Шаг 6

Запустим нашу рандомную штуку!

print(' '.join(chain))
независимо от такой истории; т.е., условно на нынешнее состояние системы, ее прошлое и смежных областях, марковский процесс удовлетворяет свойству Маркова (иногда


Функция join() — функция для работы со строками. В скобках мы указали разделитель для значений в строке(пробел).

А текст… ну, звучит по-машинному и почти логично.

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

P.P.S. Если моя практика кода вышла непонятной для вас, прилагаю исходную статью. Обязательно примените код на практике — чувство, когда оно «побежало и сгенерировало» заряжает!

Жду ваших мнений и буду рада конструктивным замечаниям по статье!

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 10

    +1

    Ухх, после прочтения статьи меня тоже "поперло". Спасибо вам за новые идеи и мотивацию. Ни за что бы не понял что это перевод

      +1
      Благодарю за обратную связь!
      +1
      Важное дополнение от пользователя berez

      Приведение слов к лемме затруднит генерацию нового текста, тк слова придется приводить обратно в исходную форму.

      Это справедливо, но как тогда сделать значимые взаимосвязи в больших текстах? Или это, всё-таки, не требуется? Буду рада мнениям, как решить эту ситуацию!

      Также хочу поблагодарить каждого, и пользователя berez в частности за внимательность к опечаткам. У меня две проблемы — западающие клавиши и «торопыжность». Впредь буду внимательнее!
        0

        Спасибо за аккуратную статью и доходчивые объяснения!
        Тоже недавно пробегался по теме — но вышло более обзорно и сумбурно, и потому, когда возникла потребность объяснить начинающему, пришлось выискивать материал с более мягким входом. Ваша статья как раз самое то!

          +1
          Начала читать вашу статью. Пока для моего уровня действительно выглядит не совсем просто, но я 100% разберу её для себя (особенно замотивировал пример на немецком — учила сей язык всё школьное время) :D

          Благодарю за обратную связь!
          +1
          Почему-то цепи Маркова любят разбирать на примере цепочки слов, хотя цепочки букв, как мне кажется, разбирать гораздо проще. Заодно при разборе цепей Маркова на буквах отпадают вопросы типа «а не надо ли привести слова к словарной форме?».

          Ну и да, в цепях Маркова нет контекста, но есть текущее состояние. А оно вовсе не обязательно ограничивается одним словом или буквой: состояние может содержать и более длинные цепочки. Тогда таблица переходов выглядит примерно так:
          "аб" -> [ "б": 0.2, "з": 0.2, "о": 0.2, "с": 0.1 ]
          "ба" -> [ "б": 0.3, "к": 0.2, "н": 0.2, "о": 0.1, "я": 0.2 ]

          Скажем, начальное состояние у нас — «ба». По таблице состояний видно, что из «ба» с вероятностью 0,3 получится «баб», с вероятностями 0,2 — «бак», «бан» или «бая», и с вероятностью 0,1 — «бао». Далее от получившейся цепочки отбрасываем один символ слева, и у нас получается следующее состояние (допустим, выпало у нас «баб» — значит, следующее состояние будет «аб»).

          Ну и последнее, что в голову пришло: автор программы схалявил и не стал вычислять правильную таблицу переходов (с нормализованными вероятностями и вот этим всем). Просто запихал все слова в списки, и если одно и то же слово встречается в каком-то состоянии много раз — оно просто много раз повторится в списке. Это, конечно, сильно упрощает программу, но при обработке больших текстов вам никакой памяти не хватит. :)
            0
            Ещё раз спасибо за ваши дополнение и внимательность!

            "... автор программы схалявил и не стал вычислять правильную таблицу переходов ..." — буду понимать, в какую сторону улучшать!
            +1
            Спасибо за интересный материал.
            В восьмидесятых периодически покупал и читал журнал «в мире науки» (что есть перевод «Scientific American»). И была в нём прекрасная рубрика «занимательный компьютер» (автор рубрики — Дьюдни. Автор «Core War», статей о множествах Мандельброта, клеточных автоматов и многого другого.
            Среди прочих интересных статей прочёл там и о программах генерации текстов на основе цепей Маркова. Упоминалось и название программы, если правильно помню «Mark V Chains» (от «цепи Маркова»). Захотелось попробовать реализовать что-то подобное, но в этих математиках я не смыслил, а придуманный мною, с позволения сказать, «алгоритм», реализовать на БК-0010 было просто невозможно. Памяти мало, сохранять промежуточные данные вычислений на МК-60, а потом подгружать когда надо — это то ещё занятие. Да и надвигающийся призыв в армию не располагал к созерцанию искусственных текстов.
            После армии, уже сидя на Спектруме, вновь вспомнилась статья. И снова всё упиралось в память, уже начал было контроллер на ВГ93 паять, как вдруг попался мне в руки ноунейм ноутбук на халяву, с жестким диском аж на 60 мегабайт, процессором 386SX16 и целыми двумя мегабайтами оперативки (храниться до сих пор, но разобран). Поиграв в цивилизацию, водрузил Win 3.11 и попавшийся под руки дельфи.
            Попробовал написать что-то подобное. И да, на программиста я не учился…

            Код был не просто кошмарен — на него смотреть было нельзя. Кнопочки были красивее. Но кое-как всё работало. Насколько я помню, принцип состоял в скармливании txt файла с текстом с последующей выдачей огромного файла, где в простом текстовом формате в каждой строке было слово, за ним через пробел то слово, которое встречалось за первым в исходном тексте и число, показывающее число, которое означало сколько раз пара первое-второе число встречалось в исходном тексте. Посему и исходный текст должен быть большим (чтобы сочетаний было больше одного) и результат обработки был громоздкий.
            Вторым шагом выданный файл вновь скармливался той же программе. Все числа суммировались и программа генерировала случайные числа, по которым из второго файла выбиралось пара слов. Затем «второе» слово становилось «первым» и процесс повторялся. Пока программа не падала с ошибками. Как то примерно так.
            Жаль что флоппи отказался хранить такой неаккуратный код, может быть вспомнил бы процесс точнее…

            Образец сгенераченного текста нашёл в своём архиве:
            «У него будет внимательнейшим образом изучено но замерев с моржами да стрелами пехота не унимается».
            (Судя по поиску в гугле — это Перумов, «рождение мага». Хотя не помню у него моржов.)

            Спасибо за интересную статью.

            P.S. Соврал про дельфи. Visual Basic, конечно.
              0
              Благодарю за обратную связь и повествование из опыта. Выходит, знакомство с переложением каких-либо теорий на код (особенно «первые» опыты) у каждого — интересная и местами забавная история, и осознание этого факта очень помогает мне, как новичку, ошибаться с настроем «будет что вспомнить»! :)
              0
              Сейчас получить начальное представление о подобной текстогенерации можно даже без программирования. Во многих клавиатурах для мобильных ОС есть подсказки слов для начала набора фразы. Понажимав несколько раз, можно получить некоторый осмысленный текст, «натренированный» на конкретно вашем лексиконе.

              Only users with full accounts can post comments. Log in, please.