Что такое цепи Маркова и как они работают

В «Коде» уже вышло несколько проектов, где мы генерировали какой-то случайный текст, чтобы показать его пользователю:

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

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

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

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

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

Допустим, у нас есть событие «Взять зонт», которое всегда идёт только после события «Идёт дождь». Даже если сейчас середина декабря, кругом снег, но внезапно случилась оттепель и пошёл дождь — следом за ним по этой логике будет событие «Взять зонт». 

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

Чтобы было понятнее, разберём на тексте.

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

Возьмём такую скороговорку:

Ехал грека через реку, видит грека — в реке рак, сунул грека руку в реку, рак за руку греку цап.

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

❗️ Для простоты мы опустим знаки препинания и большие буквы. В нормальных алгоритмах это, конечно, учитывается, но пока мы учимся, можно и так.

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

Считаем слова

Посчитаем, сколько раз встречается каждое слово в нашем тексте:

Ехал — 1

грека — 3

через — 1

реку — 2

видит — 1

в — 2

реке — 1

рак — 2

сунул — 1

руку — 2

за — 1

греку — 1

цап — 1

Ещё нам нужно пометить, что после «цап» ничего нет, просто ставим точку. 

👉 Такие отдельные элементы в цепи Маркова называют звеньями. А цепь как раз и состоит из звеньев :-)

Составляем пары

Теперь составим пары связанных событий. Связные — это когда одно событие идёт только после конкретного другого события. В нашем тексте первая пара будет такая:

Ехал → грека

Так как в исходном тексте слово «Ехал» только одно и после него идёт «грека», то алгоритм запомнит, что после «Ехал» нужно обязательно поставить только «грека», без вариантов. 

А вот со второй парой уже поинтереснее:

грека → (через, в, руку)

Чтобы было понятно, откуда появились три слова, выделим жирным все слова сразу после греки:

Ехал грека через реку, видит грека — в реке рак, сунул грека руку в реку, рак за руку греку цап.

Получается, что наш алгоритм, когда дойдёт до «грека», с какой-то долей вероятности выберет одно из трёх следующих слов.

Составим точно так же остальные пары:

через → реку

реку → (видит, рак)

видит → грека

в → (реке, реку)

реке → рак

рак → (сунул, за)

сунул → грека

руку → (в, греку)

за → руку

греку → цап

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

НАЧАЛО → Ехал

цап → КОНЕЦ

Составим схему связей

Это необязательный этап, но с ним может быть понятнее, как работает алгоритм в целом. 

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

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

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

Ехал грека руку греку цап.

Ехал грека через реку видит грека через реку видит грека руку греку цап.

Ехал грека через реку видит грека руку в реке рак сунул грека руку греку цап.

Всё, что делает алгоритм, — идёт по схеме и переходит по стрелочкам. Это и есть цепи Маркова. 

Как сделать текст более осмысленным

У нас в примере про греку алгоритм всегда выдаёт чушь, потому что исходный текст (корпус) слишком маленький для составления связей и в нём мало слов. Если мы возьмём текст побольше, например, Конституцию или «Войну и мир», то алгоритм сможет составлять текст, похожий на язык оригинала, как будто его написал человек.

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

Понимает ли сам алгоритм смысл сказанного?

Нет. Всё, что делает алгоритм, — выдаёт следующее слово на основе вероятностей. Ему неважно, что получается в итоге, потому что алгоритм не умеет думать.

Что дальше

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