Цепи Маркова простыми словами. Пишем пирожки.

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

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

Если кто-то захочет узнать что такое цепи Маркова, то в первом переложении он узнает, что:
"Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего)."

Может быть дальше станет понятно? Как бы не так, дальше пошли две страницы формул:

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

Цепи маркова - это всего-лишь описание вероятностей перехода системы из одного состояния в другое. Все состояния можно описать вершинами графа. Например, такими вершинами могут быть положения человека: [лежит], [сидит], [стоит], [идет]

Здесь видно, что граф ориентированный, это значит, что не из всякого состояния можно попасть в другое. Например, если вы лежите, то невозможно сразу пойти. Нудно сначала сесть, потом встать, а только потом пойти. Но упасть и оказаться лежачим можно из любого положения ))
Каждая связь имеет некую вероятность. Так, например, вероятность упасть из стоячего положения очень маленькая, гораздо вероятнее стоять дальше, пойти или сесть. Сумма всех вероятностей равна 1.

Кроме всего прочего цепи Маркова позволяют генерировать события. Так или иначе на цепях Маркова построены все большинство генераторов текстов.

Попробуем написать генератор пирожков.

Пирожки

Пирожки - четверостишия без рифмы, знаков препинания, цифр, без прописных букв. Количество слогов должно быть 9-8-9-8.

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

Например, после слога "при", могут идти такие слоги (ребра и их веса):
'чем'(1) 'хо'(4) 'ме'(1) 'ду'(2) 'чи'(4) 'ятель'(4) 'шёл'(5) 'ку'(1) ' '(9) 'су'(1) 'выч'(3) 'ми'(1) 'кос'(1) 'об'(1) 'дёт'(2) 'ехал'(1) 'учи'(1) 'му'(1) 'би'(1) 'це'(1) 'цел'(2) 'том'(1) 'ко'(1) 'вал'(1) 'нес'(1) 'дет'(1) 'но'(1) 'вез'(1) 'мет'(1) 'вет'(1) 'дя'(1) 'вы'(1)

Теперь все что нужно - это взять случайный слог (например, "при"). Сумма всех слогов, которые идут после него равна 58. Теперь нужно взять следующий слог с учетом частоты (количества) этих слогов:

size_t nth = rand() % count;

size_t all = 0;

for (const auto &n : next) {

    all += n.count;

    if (all >= nth)

        return n.word;

}

Таким образом генерируем строки так, чтобы в первой строке было 9 слогов, во второй - 8, далее 9 и 8, получаем:

жил шутить будильник до что ком
похищен он поку это
тебе афаначальник здесь да
онегин эффекты диван


Пока на особо связный текст не похоже. Часто встречаются несуществующие слова ("поку"). В качестве ключа сейчас только один слог. Но на основании одного слога сложно строить предложение. Увеличим количество слогов, на основании которых будем генерировать следующий слог хотя-бы до 3:

асфальта для ума довольно
на часах семь разделить на
стол выносят чёрный ящик а
он вырос отомстил нашёл

Вот и первый пирожек, который более-менее можно принять за написаный человеком.
Чтобы текст вышел более осмысленным, то нужно использовать морфологические анализаторы, и тогда в качестве узлов будут не слоги, а метаописания слов (например "глагол, множественного числа, прошедшего времени").

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